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

Alakalı Yazılar

YDS Kelime Ezberleme Pro Uygulaması

16 Aralık, 2015

Yeni e-Ticaret Sitemiz Açıldı – webdenalin

17 Ağustos, 2015

Adbuddiz Reklam Geliri

14 Ağustos, 2015

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..