KNN (K-En Yakin Komsu)

KNN algoritması, son derece basit, uygulaması kolay olan bir denetimli (supervised) makine öğrenmesi algoritmasıdır. KNN algoritması hem regresyon hem de classification için kullanılır.

KNN Nedir?

K en yakın komşu (KNN) algoritması, adından da anlaşılacağı üzere, komşularına bakarak tahminlemede bulunan bir algoritmadır. KNN algoritmasında, benzer olan şeyler birbirine yakındır varsayımı geçerlidir.

Yukarıdaki resim incelendiğinde, genel itibari ile, benzer olan sınıfların birbiri ile yakın mesafede oldukları gözlemlenmektedir. Dolayısıyla KNN algoritması da bu gözleme dayanarak, yeni gelecek tahminler bu noktalara yakınlığa göre tahminlenir.

Burada aklımıza bir soru gelmiş olabilir. Ölçülen mesafe nedir? Evet Machine learning algoritmalarında farklı mesafe ölçümleri kullanılmaktadır. Temel olarak Öklid mesafesi (Euclidean distance) kullanılsa da, daha farklı ölçümlerde mevcuttur. Bunlara örnek tablo aşağıda sunulmuştur. Bu bölümde KNN algoritmalarında sıklıkla kullanılan mesafelerden bahsedilmiştir. Makine öğrenmesinde kullanılan mesafeler hakkında daha detaylı bilgi için burayı ziyaret ediniz.

Öklid mesafesi (Euclidean distance) : Matemetikte pisagor bağlantısı kullanılarak bulunan iki nokta arasındaki mesafe ölçüm birimidir. Buna göre iki boyutlu düzlemde iki nokta arasındaki mesafe basitçe iki noktanın x ve y koordinatlarının ayrı ayrı farklarının hipotenüs’üne eşittir.

Öklid mesafesi, düşük boyutlu verileriniz olduğunda ve vektörlerin büyüklüğünün ölçülmesi önemli olduğunda harika çalışıyor. Düşük boyutlu verilerde Öklid mesafesi kullanılırsa, kNN ve HDBSCAN gibi yöntemler kutunun dışında harika sonuçlar gösterir.

Öklid mesafesinin dezavantajlarını hesaba katmak için birçok başka önlem geliştirilmiş olsa da, hala en çok kullanılan mesafe ölçülerinden biridir. Kullanımı inanılmaz derecede sezgiseldir, uygulaması basittir ve birçok kullanım durumunda harika sonuçlar gösterir.

Pythonda bulunan sklearn kütüphanesinde ölçüm metriği olarak bulunmaktadır.

from sklearn.metrics.pairwise import euclidean_distances

Manhattan mesafesi : Manhattan mesafesi, iki vektörün mutlak olarak farklarının toplamıdır. Yani iki nokta (X1, Y1) ve (X2, Y2) olarak verilirse Manhattan mesafesi |X1-X2| + |Y1 -Y2| olarak hesaplanır.

Pythonda bulunan sklearn kütüphanesinde ölçüm metriği olarak bulunmaktadır.

from sklearn.metrics.pairwise import manhattan_distances

Minkowski mesafesi : Minkowski mesafesi Öklid uzayı’nda bir metrik’tir, Öklid mesafesi ve Manhattan mesafesi’nin bir genelleştirilmesi ile oluşturulur. Burada eklenen p parametresine göre işlemler yapılır p=1 olduğunda, Minkowski mesafesi, Manhattan mesafesine eşit olur. p=2 olduğunda, Minkowski mesafesi, Öklid mesafesine eşit olur.

• p = 1 — Manhattan mesafesi
• p = 2 — Öklid mesafesi
• p = ∞ — Chebyshev mesafesi

Minkowski Mesafesi Formülü

Pythonda bulunan scipy kütüphanesinde, p parametresi değiştirilerek kullanılabilecek şekilde bir ölçüm metriği olarak bulunmaktadır.

from scipy.spatial import distance

Hamming Mesafesi : Hamming mesafesi, iki ikili veri dizisini karşılaştırmak için bir ölçümdür. Eşit uzunluktaki iki ikili diziyi karşılaştırırken, Hamming mesafesi, iki bitin farklı olduğu bit konumlarının sayısıdır. Hamming uzaklığı yöntemi tüm verilere bakar ve kaç özelliğin farklı olduğunun sonucunu verir.

Bu, çoğunlukla verilerinizi tek tuşla kodladığınızda ve iki ikili vektör arasındaki mesafeleri bulmanız gerektiğinde kullanılır.

Aynı uzunlukta iki “ABCDE” ve “ABCDE” dizimiz olduğunu ve bunlar arasındaki hamming mesafesini bulmak istediğimizi varsayalım. Her dizede harf harf gideceğiz ve benzer olup olmadıklarına bakacağız, her iki dizenin ilk harfleri benzer, sonra ikinci harfleri benzer değil, üçüncü harfler benzer değil …

ABCDE ve ABCDE dizelerine bu işlemi uyguladığımızda, dizelerde sadece kalın yazılmış iki harfin benzer ve diğer üçünün farklı olduğunu göreceğiz. Bu nedenle, buradaki Hamming Mesafesi 3 olacaktır. İki dizi arasındaki Hamming Mesafesi ne kadar büyükse, bu diziler o kadar farklı olacaktır aynı şekilde Hamming Mesafesi ne kadar küçükse, bu diziler o kadar benzer olacaktır.

Tipik kullanım durumları, veriler bilgisayar ağları üzerinden iletildiğinde hata düzeltme / algılama içerir. Hatayı tahmin etmenin bir yolu olarak ikili bir sözcükteki bozulmuş bitlerin sayısını belirlemek için kullanılabilir.

Pythonda bulunan scipy kütüphanesinde ölçüm metriği olarak bulunmaktadır.

from scipy.spatial import distance
distance.hamming([1, 0, 0], [0, 1, 0])

Bu kısma kadar, KNN algoritması ve kullanılan mesafeler konusunda fikir sahibi olduk. Peki sklearn de bulunan KNN class’ının en önemli parametresi olan k nasıl seçilmelidir?

from sklearn.neighbors import KNeighborsClassifier

Bu konuda her zaman doğru olacak bir rakam belirtmek doğru değildir. Genel olarak ifade etmek gerekirse, k değerinin tek sayı seçilmesi, modelin 0 ve 1 tahmininde eşit sayı gelmemesi adına önemlidir. (Yani şunu demek istiyorum, k=4 seçersem ve model tahmin ederken en yakın iki komşusu 0, diğer en yakın iki komşusu 1 ise, burada hoş olmayan durum meydana gelir. Bu yüzden k değerinin tek sayı seçilmesinde fayda var) Bu ifadeyi daha genel hale getirmek gerekirse, sınıflandırma problemlerinde, k parametresi, sınıfların sayısının tam katları olmamalıdır ki model tahmin ederken eşitlik durumu olmasın.

Diğer önemli bir konu ise, k değeri düşük seçilirse, model overfit olmaya meyleder. k değeri büyük seçilirse model underfit olmaya meyleder. Buradaki bias-variance trade-off’una dikkat etmek gerekir. Buna en uygun olan k değerini seçmek önem arz etmektedir.

Diğer parametre olan “weights” için ise, uniform ve distance seçenekleri mevcuttur. Uniform seçilmesi durumunda, komşulukta bulunan tüm komşuların ağırlıkları eşit olacaktır. Distance seçilmesi durumunda; komşulukta bulunan tüm komşuların ağırlıkları data pointe olan mesafe arttıkça azalacaktır. Yani yakındakiler daha etkişi olacaktır.

p parametresi Minkowski mesafesinde kullanılan parametredir.

metric parametresi mesafe parametresidir. Varsayılan olarak minkovski mesafesini alır ve p=2'dir.

Regresyon probleminde kullanılan KNN algoritması ise, komşulukta bulunan değerlerin ortalasını vermektedir.

KNN algoritmasının Ölçeklemek Gerekir mi?:

Burada belirtmem gereken önemli bir konu var. KNN algoritması, mesafe temelli tahminde bulunduğundan dolayı, datanın scale edilmiş olması son derece önemlidir. m sayıda “örneklem” ve n sayıda “özellik” içeren bir veri kümesi hayal edin. Tam olarak 0 ile 1 arasında değerlere sahip bir özellik boyutu vardır. Bu arada -99999 ile 99999 arasında değişen bir özellik boyutu da vardır. Öklid Uzaklığı formülü dikkate alındığında bu, daha yüksek olan değişkenlere daha fazla ağırlık vererek performansı etkileyecektir.

KNN algoritmasının avantajları :

• Algoritma basit ve uygulanması kolaydır.
• Bir model oluşturmaya, birkaç parametreyi ayarlamaya veya ek varsayımlar yapmaya gerek yoktur.
• Algoritma çok yönlüdür. Sınıflandırma, regresyon ve arama için kullanılabilir

KNN algoritmasının Dezavantajları:

• Örneklerin ve/veya tahmin edicilerin/bağımsız değişkenlerin sayısı arttıkça algoritma önemli ölçüde yavaşlar. Hesaplama yönünden pahalıdır (Computationally expensive)
• Yüksek memory ihtiyacı. Çünkü bütün train datasını hafızada tutar
• Örneklem sayısı artınca, tahmin uzun sürebilir.

KNN algoritmasının Zaman ve space complexity değerleri nelerdir?

Eğitim aşamasında tüm veri noktalarını saklamamız gerekiyor.
Alan karmaşıklığı O(n*d) olacaktır; burada n, veri noktası sayısını ve d, her bir veri noktasını belirleyen özelliklerin sayısını temsil eder.

Time complexity : d özellikli n veri noktasını hesaplamak için gereken süre O(n*d) olacaktır.

Time complexity şunu da belirtmekte fayda var, KNN algoritması, eğitim süresinden ziyade test süresi üzerinde daha fazla hesaplama yapar. Çünkü KNN algoritmasının fikri, sınıflandırmak istediğimiz bir örneğe yakın olan k uzunluğunda bir örnek listesi bulmaktır. Bu nedenle, eğitim aşaması temel olarak bir eğitim kümesini depolarken, tahmin aşaması ise algoritma bu depolanan verileri kullanarak k-komşuları arar.

KNN neden Lazy Learner olarak tanımlanır?

Algoritma modellemesinde eğitim (train) aşaması genel olarak veriye göre kendini eğitmez , veriyi ezberler. Bu neredeyse eğitim ve test aşamalarının neredeyse aynı olması anlamına gelir ki bu nedenle tembel öğrenme (lazy learning) algoritması olarak bilinir. Yine bu sebeple büyük veri setlerinde kullanılması verimli sonuç vermeyecektir.

KNN neden bir non-parametrik algoritmadır?

“Parametrik olmayan” terimi ilk başta biraz kafa karıştırıcı gelebilir: parametrik olmaması, parametrelerinin YOK olduğu anlamına gelmez! Aksine, parametrik olmayan modeller artan miktarda veri ile giderek daha karmaşık hale gelebilir.

Dolayısıyla, parametrik bir modelde sınırlı sayıda parametremiz vardır ve parametrik olmayan modellerde parametre sayısı (potansiyel olarak) sonsuzdur. Veya başka bir deyişle, parametrik olmayan modellerde, modelin karmaşıklığı eğitim verisi sayısıyla birlikte artar; parametrik modellerde sabit sayıda parametremiz (veya isterseniz sabit bir yapımız) vardır.

Lineer regresyon, lojistik regresyon ve lineer Destek Vektör Makineleri gibi lineer modeller, parametrik “öğrenenlerin” tipik örnekleridir; burada, sabit bir parametre boyutuna sahibiz (ağırlık katsayısı). Buna karşılık, KNN, karar ağaçları veya RBF çekirdek SVM’leri, parametre sayısı eğitimin boyutuyla birlikte büyüdüğü için parametrik olmayan öğrenme algoritmaları olarak kabul edilir.

KNN, parametrik olmayan ve tembel bir öğrenme algoritmasıdır. Parametrik olmayan, temel veri dağılımı için bir varsayım olmadığı anlamına gelir. Başka bir deyişle, eğitim setindeki verilerin yerini öğrenir ve tahminlerini buna göre yapar. (Aslında belki de, verisetinde bulunan her bir datapoint bile, bir parametre olarak bile düşünülebilir.)

Son olarak KNN algoritmasına ait modellemeye buradan ulaşabilirsiniz, sabrınız için teşekkürler :)

Referanslar :

Most Popular Distance Metrics Used in KNN and When to Use Them - KDnuggets

What is the difference between a parametric learning algorithm and a nonparametric learning…