En Yakın Komşu Bulma Algoritması (KNN)

En Yakın Komşu Bulma Algoritması

Sınıflandırmada kullanılan bu algoritmaya göre sınıflandırma sırasında çıkarılan özelliklerden, sınıflandırılmak istenen yeni bireyin daha önceki bireylerden k tanesine yakınlığına bakılır. Örneğin k=3 için yeni bir eleman sınıflandırılmak istensin. Bu durumda eski sınıflandırılmış elemanlardan en yakın 3 tanesi alınır. k değeri çok küçük olursa model çok etkilenir. Çok büyük olursa da tek bir sınıf gibi olur.  Yani k sayısının sınıflandırmaya etkisi vardır.

Algoritmanın Adımları;

1- Yeni gelen birey sınıfa eklenir.

2- k komşusuna bakılır.

3- Çeşitli uzaklık fonksiyonları kullanılarak uzaklık hesaplanır. (Ki bu fonksiyonlardan en çok tercih edileni Öklid uzaklık fonksiyonudur.)

4- En yakın neresi ise birey oraya atanır.

Uzaklık Fonksiyonları

1- Manhattan Uzaklık Fonksiyonu:

d(i,j):|x_i1– x_j1|+|x_i2-x_j2|+….

2- Minkowski Uzaklık Fonksiyonu:

d(i,j):(|x_i1-x_j1|^q+|x_i2-x_j2|^q+…)^1/q

3- Öklid Uzaklık Fonksiyonu:

d(i,j):(|x_i1-x_j1|²+|x_i2-x_j2|²+…)^1/2

Bölgesel Ağırlıklandırılmış Ortalama Yöntemine göre W=1/d² hesaplanarak ağırlıklar belirlenir. Bu kestirme ve tahminleme için kullanılır.

Bir örnek verecek olursak:

10 tane verimiz olsun. X1=8 ve X2=4 değerleri için en yakın komşu bulma algoritmasını kullanarak hangi sınıfa ait olduğunu bulalım. k=4 verilmiş olsun. Öklid uzaklık fonksiyonunu kullanarak;

Hesaplamaları yaptık şimdi en yakın 4 noktayı alıp bakacağız. 2.24, 2.83, 3.16, 4.24 sonuçlarının  tabloda karşılık geldiği değerler GOOD,BAD,BAD,BAD olarak gözüküyor. 3tane BAD 1 tane GOOD olduğundan en çok olan sınıfa dahil ederiz. Yani BAD sınıfına dahil oldu.

İyi Çalışmalar..