Anasayfa / Bilgisayar Mühendisliği / Algoritmanın Analizi / En Yakın Komşu Bulma Algoritması (KNN)

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:

Ekran Alıntısı

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;

Ekran Alıntısı

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

Hakkında Ali Demirci

Ben Ali Demirci... 1991 Ankara doğumluyum. Ankara da yaşıyorum. Fırsat buldukça öğrendiklerimi burada paylaşıyorum. Java ile haşır neşirim. Android'den asla vazgeçemem. Öğrenmeye bayılırım. Yeni şeyler öğrendiğimde, geçmişteki projelerimde keşke böyle yapsaydım diye çok üzülmüşümdür. O yüzden öğrenmekten korkmayın. Takıldığınız yerleri mutlaka sorun. Biliyorsam yanıt veririm. Bilmiyorsam yol gösteririm. Teşekkürler :)

Kontrol Et

Regex Nedir? Nasıl Kullanılır?

Regex(Regular Expression) yani düzenli ifadeler, metinlerde aranan bir tümceyi kolayca bulmamızı sağlayan bir çeşit algoritmadır. Yani …

4 Yorumlar

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

  2. Oğuz

    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

  3. Alper

    Bilgiler için sağol kardeşim.