Arkadaşlar bitirme projesinde bu algoritmayı kullandık, aşağıdaki yazı da bitirme projemin ara raporunda kullandığım, son raporda da kullanacağım bir yazıdır, Oktay Hoca'dan proje alan arkadaşların yazıyı raporlarında kullanmamasını rica ediyorum.
Bu algoritmayı C#'da kodladık, ileride kısaca kodları da paylaşmak istiyorum. Umarım faydalı olur..
K-NN (En Yakın Komşuluk) Algoritması
KNN, eğitimli öğrenme algoritmasıdır ve amacı, yeni bir örnek geldiğinde varolan öğrenme verisi üzerinde sınıflandırma yapmaktır. Algoritma, yeni bir örnek geldiğinde, onun en yakın K komşusuna bakarak örneğin sınıfına karar verir. [1]
Bu algoritma ile yeni bir vektörü sınıflandırabilmek için doküman vektörü ve eğitim dokümanları vektörleri kullanılır. Tüm eğitim dökümanları ve kategorisi belirlenecek olan doküman vektörel olarak ifade edildikten sonra bu vektörler K-NN algoritması ile karşılaştırılırlar.
Kategorisi belirlenmek istenen metnin vektörü, öğrenme kümesindeki metinlerin vektörleri ile karşılaştırılır.
K-NN algoritmasında terim ağırlıklandırma için 3 çeşit yöntem kullanılabilir.
1-Bit ağırlıklandırma yöntemi,
2-Frekans ağırlıklandırma yöntemi,
3-Tf-IDF ağırlıklandırma yöntemi.
Algoritma En yakın komşuluk prensibine dayanır. Tüm dokümanlar vektörel olarak temsil edilir. Sorgu dokümanı ile diğer dokümanlar arasındaki cosinüs benzerliği hesaplanır. Benzerlik oranı 1’e en yakın olan n tane vektörün kategorisinden çok olanı dokümana atanır.
Uygulamada K-NN algoritmasının kullanılmasındaki nedenler aşağıdaki gibi sıralanabilir:
• Uygulanabilirliği basit bir algoritma olması.
• Gürültülü eğitim dokümanlarına karşı dirençli olması.
• Eğitim dokümanları sayısı fazla ise etkili olması
• Bu metot ölçeklendirilebilir bir metottur ve çok geniş veritabanları üzerinde de uygulanabilir.[4]
Her bir kelime vektörel uzayda bir boyuta karşılık gelmektedir. Her bir metin bu sayede vektörel uzayda ifade edilebilmektedir. K-NN algoritması ile vektörel uzayda bu metinlerin birbirlerine ne kadar benzedikleri tespit edilebilir. Bir başka ifadeyle birbirine en yakın metinler bulunabilir.
Şekil 1 İki Boyutlu Vektör Uzayı
Yukarıdaki şekilde iki kelimeden oluşan bir ortak sözlüğe sahip dört metnin vektörel uzayda ifadesi gösterilmiştir. Eğer sözlük üç kelimeden oluşsaydı grafiğimiz de üç boyutlu olacaktı. Burada d1, d2 ve d3 eğitim dokümanlarımızdan oluşan vektörler, q ise sınıfını bulmak istediğimiz dökümanın vektörüdür.
Q dökümanının d1, d2 ve d3 eğitim dokümanlarından hangisine daha fazla benzediğini bulmak için aralarındaki açının cosinüs değerine bakılır. Aralarındaki açı ne kadar küçükse elde edilen cos(açı) değeri o kadar 1’e yakın olacaktır. Elde edilen değerin 1’e yakın olması, iki dökümanın birbirine ne kadar benzediğini ifade eder.
Örneğin yukarıdaki örnekte q ile d2 arasındaki açı en küçüktür. Bu nedenle de q dökümanının en yakın olduğu doküman d2 dökümanıdır. Aralarındaki açının cosinüs degeri de 1’e yakın bir değer olarak karşımıza çıkmaktadır.
K-NN algoritmasında temel olarak aşağıdaki adımlar gerçekleştirilir:
1. K değerinin belirlenmesi.
2. Tüm öğrenme örnekleri ile olan uzaklığının hesaplanması.
3. Minimum uzaklıkğa göre sıralama işleminin yapılması.
4. Ait oldukları sınıf değerlerinin bulunması.
5. Değeri baskın olan sınıfın seçilmesi.
Burada k değerinin belirlenmesi, bize en yakın kaç vektöre bakılması gerektiğini ifade etmektedir. Örneğin k değerimiz 3 olsun. Bu durumda öğrenme kümesindeki dökümanlardan en yakın 3 tanesi alınarak dökümanın hangi sınıfa ait olduğuna karar verilir. Örneğin aşağıdaki gibi iki boyutlu kordinat sistemine yerleştirilmiş örneklerimiz olsun.
Şekil 2 Örnekler[2]
Yukarıdaki örneklerden maviye mi yoksa kırmızıya mı benzediğini tespit etmemiz gereken bir de yeşil örneğimiz olsun.
Şekil 3 Örnekler ve Sınıflandırılacak Veri[2]
K değerimizi 3 aldığımızdan yeşil örneğe en yakın olan 3 örneğe bakarız. K değeri 4 olsaydı en yakın 4 örneğe bakacaktık.
Şekil 4 En Yakın Üç Komşu[2]
En yakın 3 örnekten 2 tanesi kırmızı olduğundan yeşil örnek için de kırmızı sınıfına aittir diyebiliriz.
K-NN algoritmasında benzerlik hesabı aşağıdaki formülden yararlanılarak yapılabilir.
Denklem 1: K-NN Denklemi[4]
Yukarıdaki formülde: Wij terimin doküman içerisindeki ağırlığı, di eğitim dokümanı vektörüdür. q ise kategorisi bulunması istenen vektördür.
Kaynaklar
3. P. Hall; B. U. Park; R. J. Samworth (2008). "Choice of neighbor order in nearest-neighbor classification".
