K-Nearest Neighbors (KNN)

K en yakın komşu (KNN), yeni bir örneğin etiketini kendisine en yakın k etiketli örnekten tahmin eden bir denetimli öğrenme algoritmasıdır: sınıflandırmada bu komşuların çoğunluk oyu, regresyonda ise değerlerinin ortalaması kullanılır. KNN parametrik olmayan ve "tembel" bir algoritmadır: ağırlıklar öğrenmez, yalnızca eğitim verilerini saklar ve tüm işlemleri bir tahmin istendiğinde yapar. Evelyn Fix ve Joseph Hodges yöntemi 1951'de tanıttı; 1967'de Thomas Cover ve Peter Hart, sınırsız veri verildiğinde en yakın komşu kuralının hata oranının mümkün olan en iyi sınıflandırıcının hata oranının en fazla iki katı olduğunu kanıtladı. Aynı en yakın komşu araması artık vektör veritabanlarında ve sinir ağlarından alınan gömme vektörlerini karşılaştıran görüntü erişim sistemlerinde büyük ölçekte çalışıyor.

KNN Nasıl Tahmin Yapar#

KNN, her sorgu noktası için üç adım uygular:

1. Uzaklığı ölç: Sorgu noktası ile saklanan her örnek arasındaki uzaklığı hesaplar. Varsayılan ölçüt Öklid uzaklığıdır; Manhattan ve Minkowski uzaklıkları yaygın alternatiflerdir. Vektörün yönünün anlam taşıdığı gömme vektörlerinde ise kosinüs benzerliği standart ölçüttür.
2. Komşuları seç: Uzaklıkları en küçük olan k örneği alır.
3. Etiketleri birleştir: Sınıflandırmada komşular arasındaki en yaygın sınıf, regresyonda ise değerlerin ortalaması kullanılır. Uzaklığa göre ağırlıklandırmada (scikit-learn'de weights="distance"), daha yakın komşuların etkisi daha fazladır.

Her özellik uzaklığa katkıda bulunduğundan, ölçeği büyük olan özellikler baskın çıkar: dolar cinsinden gelir, yıl cinsinden yaşı gölgede bırakır. Bu nedenle KNN işlem hatları önce özellikleri standartlaştırır ya da bir özellik çıkarımı modelinin gömme vektörlerini karşılaştırır; böylece her boyut benzer ölçekte katkıda bulunur.

k Değerini Seçme#

k değeri, aşırı öğrenme ile yetersiz öğrenme arasındaki dengeyi belirler. k = 1 olduğunda, gürültülü ve yanlış etiketli olanlar da dâhil olmak üzere her eğitim noktası kendine ait bir bölge kaplar ve karar sınırı girintili çıkıntılı hâle gelir. k çok büyük olduğunda, her oy sorgu noktasından çok uzaklara erişir ve gerçek sınıf sınırlarını bulanıklaştırır. İki sınıfta tek bir k değeri, eşit oyları önler; k değerini seçmenin standart yolu çapraz doğrulamadır. scikit-learn'ün gürültülü iki ay kümesinde bu denge üç değerde görülür:

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

k = 1 olduğunda sınıflandırıcı eğitim noktalarını ezberler; bu noktalarda 1.00, ayrılmış noktalarda 0.83 puan alır. k = 15 ile sırasıyla 0.90 ve 0.89 puan alır; bu üç değer arasındaki en iyi test sonucudur. Eğitim noktalarının neredeyse yarısı olan k = 300 ise sınırı düzleştirir ve her iki puan da 0.84 ile 0.81'e düşer.

Komşu Aramasını Hızlandırma#

Kaba kuvvet araması, d boyutlu uzayda saklanan n noktanın tümünü sorguyla karşılaştırır; bu nedenle her tahminin maliyeti yaklaşık n × d işlem mertebesindedir ve bellek kullanımı veri kümesiyle birlikte artar. k-d ağaçları ve top ağaçları gibi uzay bölümlendirme yapıları, düşük boyutlarda karşılaştırmaların çoğunu atlar; scikit-learn'deki algorithm="auto" ise kaba kuvvet, k-d ağacı ve top ağacı arasında seçim yapar. Yüksek boyutlarda boyutluluk laneti, noktalar arasındaki uzaklıkları neredeyse eşit hâle getirir ve ağaç budama artık işe yaramaz. Bu nedenle büyük sistemler, HNSW grafikleri ve çarpım niceleme kullanan ters dosya (IVF) indeksleri gibi yaklaşık en yakın komşu (ANN) indekslerine geçer; bunlar FAISS gibi kütüphanelerde uygulanır. Bu indeksler, sorguyu saklanan vektörlerin küçük bir bölümüyle karşılaştırırken gerçek en yakın komşuların çoğunu döndürür:

KNN ve İlgili Yöntemler#

• K-means kümeleme: Etiketsiz noktaları öğrenilmiş küme merkezlerinin çevresinde k kümeye ayıran denetimsiz bir algoritmadır. Adlarının aynı harfi içermesi rastlantıdır: k-means'te k, küme sayısını belirtir.
• Vektör arama: Aynı işlemin erişim amaçlı biçimidir: genellikle yaklaşık bir indeks aracılığıyla, sorgu gömme vektörüne en yakın saklanan öğeleri döndürür ve uygulama bu öğeleri doğrudan kullanır.
• Destek vektör makineleri ve lojistik regresyon: Eğitim sırasında bir karar sınırı öğrenen parametrik modellerdir; bu nedenle tahmin maliyeti, eğitim kümesi büyüdükçe sabit kalır.

Gerçek Dünya Uygulamaları#

• Öneri sistemleri: Öğe tabanlı iş birlikçi filtreleme, puanlama veya satın alma vektörleri kullanıcının daha önce beğendiği öğelere en yakın olan ürünleri önerir.
• Anomali tespiti: Bir noktanın k'ıncı en yakın komşusuna olan uzaklığı anomali puanı olarak kullanılır; böylece normal örneklerin hepsinden uzaktaki işlemler veya sensör okumaları öne çıkar.
• Eksik değer atama: scikit-learn'deki KNNImputer, her eksik değeri en benzer k satırdaki ilgili özelliğin ortalamasıyla doldurur.
• Görüntü erişimi ve yeniden tanımlama: Sistemler, başka bir kamerada görülen aynı ürünü, yüzü veya kişiyi bulmak için bir görüntünün gömme vektörünü bir galeriyle karşılaştırır. Ultralytics benzerlik arama çözümü, bir görüntü klasörünü OpenAI'nin CLIP modeliyle gömme vektörlerine dönüştürür, indekslenmiş her görüntüyü "kırmızı araba" gibi bir metin sorgusuyla tam kaba kuvvet aramasında kosinüs benzerliği kullanarak puanlar ve varsayılan olarak en fazla 30 en yakın sonucu döndürür.