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):|xi1– xj1|+|xi2-xj2|+….
2- Minkowski Uzaklık Fonksiyonu:
d(i,j):(|xi1-xj1|q+|xi2-xj2|q+…)1/q
3- Öklid Uzaklık Fonksiyonu:
d(i,j):(|xi1-xj1|2+|xi2-xj2|2+…)1/2
Bölgesel Ağırlıklandırılmış Ortalama Yöntemine göre W=1/d2 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..
Güzel yazınız için teşekkürler. İleri derecede resmi ve formülasyon odaklı paylaşımlara göre, gayet sade ve anlaşılır bir paylaşım olmuş. Kolay gelsin.
teşekkürler yorumunuz için tuğrul bey
Sevgili Ali,
Rapidminer kullanarak veri madenciliği yapıyorum. K-nn algoritmasını kullanıyorum. Önceden pozitif ve negatif anahtar kelime listelerinin olduğu iki listeye göre metnin değerlendirilmesini sağlıyorum. Sonuçlar yönelimi gösterse de, istediğim ölçüde kesin değil. Bu kesinliği artırmak için neler yapılabilir?
Selamlar,
Oğuz
Bilgiler için sağol kardeşim.