K-En Yakın Komşu Algoritması (K-Nearest Neighbors Algorithm)
K-En yakın komşu algoritması hem sınıflandırma hemde regresyon problemlerini çözmek için kullanılan,basit ve uygulaması kolay bir denetimli öğrenme algoritması dır.
Elimizde bir veri kümesi olduğunu varsayalım ve bu veri kümesine yeni bir eleman gelmesi durumunda,dahil edilecek sınıfın belirlenmesinde kullanılır.Endüstri dalında daha çok sınıflandırma kısmında tercih edilir.
Bizde bu makalemizde basit bir veri setini nasıl analiz ediyoruz adım adım anlatmaya çalışacağız.
Elimizde aşağıdaki grafikte yer alan veri setlerimiz olsun.
Bu veri setine bakarak elemanlarımızın uzaklıklarını gözlemleyecek olursak.
Üst kısımda yer alan gözlem değerleri tablosunu elde ederiz.
Şimdi algoritmamızı uygulamaya başlayacak olursak.İlk olarak oluşturduğumuz uzaklık matrisinin hesaplanması gerekmektedir.Bu hesaplamaları yaparken 3 çeşit uzaklık hesaplama yöntemi vardır.
Öklid Uzaklığı
2 boyutlu uzayı ele aldığımızda,aslında pisagor teoreminin uygulanmasıdır.
Üst kısımda yer alan tabloya bakacak olursak d noktasının uzaklığı,alt ksıımda belirttiğimiz formül ile hesaplanabilir.Bizde bu yazımızda Öklid Uzunluk hesaplama yöntemini kullanacağız.
Manhattan Uzaklığı
Diğer bir uzunluk hesaplama yöntemimiz ise Manhattan olarak isimlendirilir.Bu uzaklık ise noktalar arasında mutlak uzaklıkların toplamı alınır.
Minkowski Uzakığı
Q sayıda değişkene bağlı bir uzaklık hesaplamak isteniyorsa Minkowski yöntemi kullanılır.Formülde Q yerine 2 değerini verirsek aslında Öklid bağlantısını elde ettiğimizi görebiliriz.
Tekrar konumuza dönecek olursak. Oluşturduğumuz gözlem matrise bakarak noktaların birbirine olan uzaklıklarını Öklid bağlantısı yardımı ile hesaplayalım.Örnek olarak “a” noktasının “b,c,d,e” noktalarına uzaklıkları,diğer noktalarında birbirlerine uzaklıkları hesaplanır.
Hesaplamalarımızı yaptıktan sonra yaklaşık değerleri alarak uzaklıklar matrisi oluşturuyoruz.Her bir noktanın diğer noktalara göre uzaklık matrisi alt kısımda yer almaktadır.
Uzaklık matrisine baktığımızda en küçük değerin 1,41 olduğunu görüyoruz.Bu demek oluyor ki Min d(i,j) = 1,41 değerine sahiptir.Bu değer noktası “a” ve “b” değerlerinin kesişimi olduğundan bu iki noktayı ele alarak başlıyoruz. (Not : K-En uzak algoritmada da bunun tam tersini yaparak devam ediyoruz.)
Artık “a” ve “b” noktalarını bir bütün olarak ele alıp.Bu noktaların diğer noktalara olan uzaklıklarına bakarak en küçüğünü alıyoruz.
Örnek : ”a” noktasının “c” noktasına olan uzaklığı 2,82 ,”b” noktasının da “c” noktasına göre uzunluğu 3,16 bu durumda en küçük olanı alıp yeni bir uzunluk matrisi oluşturuyoruz.Yani 2,82 değerini alarak devam ediyoruz.
Bu tabloya göre yeni uzunluk matrisimiz şu şekilde olacaktır.
Tekrar bu tabloyu ele aldığımızda en düşük değerin 2,23 olduğunu görürüz. Min d (i,j) = 2,23 olarak belirlenir.Bu durumda daha önce oluşturduğumuz “a” ve “b” kümesine “e” değerini de ekleyerek yeni bir uzaklık matrisi oluştururuz.
Matrisi oluştururken daha net anlaşılması için alt kısımda uzunluk ölçülerini gösteren grafiğimizi oluşturuyoruz.
Bu değerlere göre yeni matrisimiz;
Tekrar uzaklık matrisimizi bakınca en küçük değerin Min d (i,j) = 2,82 olduğunu görürüz.Bu durumda daha önce oluşturduğumuz “a,b,e” kümesine “c” değerini de ekleyerek yeni bir uzaklık matrisi oluştururuz.
Bu değerlere göre son matrisimiz
Aslında her bir adımda en yakında ki elemanı (uzaklığı en az olan iki nokta arasını)alarak gruplama işlemi yaptığımızı görebiliriz. Algoritmamızın da amacı tam olarak bu aslında. Noktaları en yakınında bulunan noktalara göre gruplayarak yeni gelecek olan değerin hangi grup içinde yer alacağını belirlemek üzerinedir.
Bu bulduğumuz değerleri kümeleyecek olursak yeni gelecek değerin hangi kümeye dahil olacağını bulabiliriz.
Bu kümelere bakarak Öbekağacı (dendrogram) çizecek olursak;
Şeklini elde edebiliriz.
