04.01. K-NN Algoritması

Bu yazımda, gözetimli öğrenme metotlarından sınıflandırma (classification) işleminde kullanılan K-KN (K-Nearest Neighborhood, En Yakın K Komşu) algoritması hakkında bilgi vermeye çalışacağım.  Sınıflandırma işleminde K değeri bakılacak eleman sayısını belirler.

Her ne kadar KNN algoritması k-means algoritmasındaki benzer özellikler taşısa da büyük farklılıklar da içermektedir. KNN algoritması bir eğitim verisi içerirken k-means algoritması bir eğitim verisi içermez. Yeni bir değer geldiğinde K değerine mesafeler hesaplanır ve yeni değer bir kümeye ilave edilir. Mesafe hesaplama işleminde ise k-means ve hiyerarşik kümeleme de kullanılan öklid uzaklığı, manhattan uzaklığı gibi mesafe hesaplama yöntemleri kullanılabilir. Bu örneğimizde yine öklid uzaklığı kullanılacaktır.

Bu algoritma beş adımdan oluşur.

  1. Öncelikle K değeri belirlenir.
  2. Diğer nesnelerden hedef nesneye olan öklit uzaklıkları hesaplanır.
  3. Uzaklıklar sıralanır ve en minimum uzaklığa bağlı olarak en yakın komşular bulunur.
  4. En yakın komşu kategorileri toplanır.
  5. En uygun komşu kategorisi seçilir.
Adımları örnek bir veri üzerinde inceleyelim. 4 adet verimiz ve verilerimizin sınıfları olsun. Hangi sınıfta olduğunu bilmediğimiz 5. verimiz gelsin. Bu veri hangi sınıftan olabilir?
     
Adım 1:
K değerini 3 olsun.
Adım 2: Yeni eklenen nesne ile diğer nesneler arasındaki uzaklıkları bul.
Adım 3: Uzaklıkları Sırala, k adet nesneyi seç.
Nesne 4, Nesne 3 ve Nesne 1 en yakın 3 uzaklıktır.
Adım 4: Sınıf kategori sayılarını belirleme: 2 adet Sınıf_2 ve 1 adet Sınıf_1 sınıfından vardır.
Adım 5: Seçim: Bu durumda kazanan Sınıf_2 kazanandır.
Eğitim kümesinin büyük olması ve k değerini uygun seçilmesi KNN açısından çok önemlidir. KNN algoritmasına karar verdiğinizde eğitim verinizi ve k değerini arttırarak başarınıza bakın. Başarı sabitlenmeye başladığında iyi bir KNN tahmin sistemi yapmışınızdır. Bu algoritmanın kötü tarafı her ekleme işleminde uzaklıkların hesaplanmasıdır. Yine de, veriye uygun filtreleme yöntemleri ile yazılım sürecinizi hızlandırabilirsiniz.
Örnek hesaplamaların yapıldığı Excel Dosyası.