K En Yakın Komşu (K-NN)

Şuanda bulunduğunuz tarihten 5–10 sene sonrasında olduğunuzu düşünün. Bir iş başvurusundan olumlu dönüş aldığınızı ve sizi mülakata çağırdıklarını varsayın. Şu anda o firmada mülakat için sıra bekliyorsunuz, rakiplerinizde yanınızda sizinle beraber heycanlı bir şekilde bekliyorlar ve bir anda onlar (en yakın komşularınız) hakkında endişelenmeye başladınız. Hemen telefonudaki gerçek zamanlı yüz algılama teknolojisi sunan uygulamayı açıp çevrenizdeki insanların geçmişi, arkadaş çevresi, ilgi alanları gibi özelliklerini öğrendikten sonra mülakata girerek neden sizi seçelim sorusuna rakiplerinizden iyi olduğunuz yönlerinizi söyleyerek o işi kaptığınızı düşünün.
Güzel olmaz mıydı?
Gizlilikle ilgili endişelerinizden öte k-NN nedir, nasıl çalışır, veri biliminde kullanım senaryoları nelerdir ve yüz tanıma teknolojilerindeki yenilikleri nasıl kolaylaştırdı?

Peki nedir bu K-NN?

k-NN, 19. yüzyıldan beri denetimli öğrenme(supervised) ortamlarındaki verileri analiz etmek için yaygın olarak kullanılan bir makine öğrenme algoritmasıdır. Popüleritesi, kullanım kolaylığı ve kolayca anlaşılabilir sonuçlarından kaynaklanmaktadır. K-NN’deki “k”, bir veri kümesindeki sonuçları sınıflandırmak veya tahmin etmek için kullanılan en yakın komşuların sayısını ifade eder. Her yeni gözlemin sınıflandırması veya tahmini, ağırlıklı ortalamalara göre belirlenen bir mesafeye (yani En Yakın Komşu) göre hesaplanır. K-NN analizi, verilerdeki gözlemlerin dağılımı hakkında önceden çok az bilgi olduğunda mantıklı bir seçimdir.

k-NN Sınıflandırmasından bir örnek — Adi Bronshtein

Her gözlem arasındaki ilişkiyi yakalamak amacıyla, etiketli bir veri seti verildiğinde k-NN kullanılabilir. Bu benzerlik ilişkisi, veri noktaları arasında bir uzaklık metriği olarak ifade edilir. Gözlemler arasındaki aralıklar Öklid, Manhattan, Chebyshev, Hamming mesafesi ve hatta Kosinüs benzerliği olarak ölçülebilir. k-NN parametrik olmayan bir algoritmdır, çünkü ilişkinin fonksiyonel formu hakkında açık bir varsayım yoktur. Ayrıca, belirli bir veri modelini uygulamaktan ziyade doğrudan eğitim örneklerine odaklandığı anlamda örnek tabanlı öğrenmenin bir örneğidir.

K-NN algoritması, verilerin bir test kümesinde eğitim yapmak yerine tüm veri kümesini işler. En yakın komşuların sayısı (k), veri seti için mümkün olan en iyi uyumu elde etmek için Veri bilimcisinin seçtiği hiperparametredir. K sayısı küçük olduğunda, tahmin bölgesini sınırlandırırız ve sınıflandırıcıyı genel dağılımı daha az hassas hale getiririz. Sınıflandırma problemleri için bu en yaygın sınıf değeri olabilir.(k=3) Regresyon problemleri için, bu ortalama çıkış değişkeni olabilir.(küme sayısı)

K-NN ne zaman kullanlır?

Algoritma, veri araştırmacısının benzer belgeler için semantik olarak aradığı konsept araştırmasında kullanılır. Keşfetmek, algoritmanın verilen soruyla ilgili tüm e-postaları, kısa özetleri, sözleşmeleri, vb. bulmak için kullanılabileceği başka bir kullanım senaryosudur. Tavsiye sistemlerinde genellikle bir müşterinin belirli bir öğeyi beğendiğini biliyorsanız, k-NN’yi entegre eder, daha sonra bunlara benzer öğeler önerebilirsiniz. Son olarak, k-NN, Yapay Sinir Ağları (ANN) ve Destek Vektör Makineleri (SVM) gibi daha karmaşık sınıflandırıcılar için bir ölçüt olarak sıklıkla kullanılır. [1]

k-NN’in Cııfar 10 veri seti üzerinde çalıştırılması — Andrej Karpathy

Algoritmasının sınırları nedir?

Hiperparametre k yüksek olduğunda tahmin, aykırı değerlere karşı daha dirençlidir. K-NN ayrıca verilerde bir gözlem sınıfı çok sık görülürse, çarpık sınıf dağılımlarından muzdariptir. k-NN’nin kullanım kolaylığı hem bellek hem de hesaplama açısından bir maliyete sahiptir, çünkü k-NN kullanımı bir örnek yerine tüm veri kümesinin işlenmesini gerektirir. Tüm bu nedenlerden ötürü, k-NN algoritması endüstriyel ortamlarda pratik olmayabilir.

Algoritmanın uygunluğunu geliştirmek için çeşitli teknikler vardır. Verileri yeniden ölçeklemek, mesafe ölçümlerini daha anlamlı hale getirebilir. Mesafe metriğinin doğasını değiştirmek, sınıflandırmaların / tahminlerin doğruluğunu geliştirmeye yardımcı olabilir (örneğin, Hamming veya Manhattan’ın Euclidian(Öklid) mesafesi yerine kullanılması). PCA gibi boyut azaltma teknikleri, daha yönetilebilir sonuçlar sağlamak için k-NN uygulanmadan önce uygulanabilir. Son olarak, eğitim gözlemlerini k-d ağaçları gibi yaklaşık En Yakın Komşu teknikleri kullanarak depolamak, test süresini azaltmak için kullanılabilir.

Çıkarımlar

Yüz tanıma ve İş mülakatına geri dönecek olursak, k-NN, Herta Güvenlik gibi uygulamalarda temel bir rol oynar. [2] Uygulamanın niteliği göz önüne alındığında, şehirde her kişi için ayrı bir sınıflandırıcı eğitmek hem zorlu hem de maliyetli olacaktır. Herta’nın veri bilimcileri, insanların yüzlerini temsil eden özellik vektörlerini oluşturmak için derin öğrenme algoritmaları geliştirdiler. Uygulama daha sonra yüzlerini bir izleme listesine benzeyen bireyleri tanımlamak için k-NN’yi kullanır. Bir referans belirlendikten sonra, hangi veritabanlarının bağlantılırı olduğu bulunabilir.[3]

[1] Kevin Zacka, (2016), A complete guide to K-Nearest Neighbors

[2] Herta Security, Technology

[3] Jon Christian, (2018), How Facial Recognition Could Tear Us Apart,