KNN, makine öğrenmesinde kullandığımız sınıflandırma algoritmalarından biridir. Bu algoritmayla, sisteme verileri girilen yeni bireyin, elimizde özelliklerinin bulunduğu birkaç gruptan hangisine ait olduğunu bulmayı hedefleriz.
Örneğin, elimizde yukarıdaki gibi bir veri kümesi var olduğunu varsayalım. Her renk, farklı bir popülasyonu belirtiyor. Veri kümesine yeni dahil olan bir bireyin grubunu ona en yakın k adet noktaya olan uzaklığını hesaplayarak bulabiliriz. Bu veri kümesi için, bireylerin popülasyon oluşturma kıstası birbirlerine yakınlıkları. Farklı veri kümeleri için çok boyutlu uzaylarda çalışmamız gerekebilir, bu da tamamen veri kümesinin türü ile ilgili bir olay.
Analitik geometriden de hatırlayabileceğiniz üzere, iki nokta arasındaki uzaklık, aşağıdaki gibi ifade edilir. (Euclidean Distance)
Burada ikinci boyut ile çalıştığımız için, formülü aşağıdaki şekilde ele alabiliriz:
Kullanım Alanları
Aslında her ne kadar farkında olmasak da bu ve benzeri algoritmaların kullanıldığı yazılımları hergün kullanıyoruz. Kitap satan bir web sitesini ele alalım. Kitapları alan insanlar, belli türlere -gruplara- ayrılmıştır. Bunlar; bilim kurgu, çizgi roman veya fikir kitapları seven kişiler olabilir.
Bizim web sitemize -kitap sitesi- yeni giren bir kişi, veri kümesine eklenecek bir bireydir. Gruba eklenme olayı, bireyin incelediği veya satın aldığı kitapların türüne göre belirlenir. Siteye yeni giriş yapmış bireyin sürekli bilim kurgu romanları incelediğini tespit etmiş olduğumuzu farz edelim. KNN algoritmasını kullanarak yazacağımız yazılım, kullanıcının bu taleplerini göz önünde bulundurarak onu “bilim kurgu” romanları okuyan gruba dahil edecek ve ona önerilen kitaplar kısmında -varsa- bilim kurgu kitapları sunacak… Anlayacağınız, kullanıcıyı analiz edip onun isteklerini öğrendikten sonra ona hitap edebilen bir yazılım geliştirmiş olacağız. Eh, bu da müşteriye istediği şeyleri vereceği bir sistem olduğu için ürün satmamızı kolaylaştıracaktır.
Bu ve buna benzer sayısız örnek verilebilir konu hakkında. Sadece programıcının -ya da matematikçinin- böyle bir şeyi elindeki probleme nasıl uygulayabileceğini bulması gerekiyor.
Algoritmanın Uygulanması
Burada işin yazılım boyutuna girmiş bulunuyoruz. KNN algoritmasının kullanıldığı gerçek bir uygulama olmayacak fakat mantığı aynı olacak. Veri kümesi olarak aşağıdaki kümeyi ele alacağız. (İlk fotoğraftaki küme)
data = {
'red': [
(1, 2),
(2, 3),
(2, 1),
(3, 1)
],
'black': [
(6, 5),
(7, 7),
(8, 6),
(5, 7)
],
'green': [
(1, 6),
(1, 7),
(3, 6),
(2, 5)
]
}
Veri kümemizde 3 adet grup bulunuyor. Bu gruplar sırasıyla, red, black ve green olarak adlandırıldılar. Gerçek hayatta herhangi bir gerçek veriyi temsil etmiyorlar. Grafik üzerinde aşağıdaki gibi konumlandırılmış durumdalar.
İlk önce işe bir KNN sınıfı yazarak başlayalım. Bu sınıf, noktalar arasındaki uzaklığı bulan (find_distance) ve tahmin yapan (predict) fonksiyonlarından oluşacak.
[...]
def find_distance(self, p, q):
return ((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** 0.5
[...]
Bu fonksiyon, p ve q adı altında noktaları temsil eden iki argüman alıyor ve formülü uygulayarak bize sonucu veriyor. Şimdi de, tahmin yapmakla (en yakın grubu bulmakla) görevli fonksiyonumuz olan predict fonksiyonunu yazalım.
[...]
def predict(self, predict):
distances = []
for group in self.data.keys():
for dot in self.data[group]:
distance = self.find_distance(dot, predict)
distances.append((distance, group, dot))
result = sorted(distances)[0][1]
return result, sorted(distances)
[...]
Bu fonksiyon, kendisine en yakın grubun bulunacağı noktanın kordinatlarını predict adı ile alıyor. Ardından, elimizdeki veri kümesinde bulunan her bir noktaya olan uzaklığını hesaplıyor ve bunları küçükten büyüğe doğru sıralıyor. En küçük değerin oluştuğu nokta, ona en yakın grubun bir üyesi demektir. Bu durumda, yeni girilen verinin de grubu bu noktayla aynı olarak işaretlenip sonuç veriliyor.
Sırasıyla (3,2),(4,5),(6,2) noktalarının hangi gruplarda olduğunu hesaplamaya çalışalım.
[...]
for val in [(3, 2), (4, 5), (6, 2)]:
result, distances = knn.predict(val)
print('%s\'s group: %s' % (str(val), result))
print('\n'.join(map(str, distances)))
plt.scatter(*val, color='blue')
print('-----')
for group in knn.data.keys():
for dot in knn.data[group]:
plt.scatter(*dot, color=group)
plt.show()
[...]
Bu kısım, yazılan predict fonksiyonunu kullanarak kendisine verilen noktaların gruplarını buluyor. Şimdi, yazdığımız yazılımın tüm parçalarını birleştirip çalıştıracağız ve sonuçları göreceğiz!
Grubu tahmin edilecek olan noktaları aşağıda görebilirsiniz. (Mavi noktalar).
Kendiniz göz kararı ile hangi noktanın hangi gruba ait olduğunu görebiliyorsunuzdur, işte programımızın verdiği sonuçlar:
(3, 2)'s group: red
(1.0, 'red', (3, 1))
(1.4142135623730951, 'red', (2, 1))
(1.4142135623730951, 'red', (2, 3))
[...]
-----
(4, 5)'s group: green
(1.4142135623730951, 'green', (3, 6))
(2.0, 'black', (6, 5))
(2.0, 'green', (2, 5))
[...]
-----
(6, 2)'s group: black
(3.0, 'black', (6, 5))
(3.162277660168379, 'red', (3, 1))
(4.123105625617661, 'red', (2, 1))
[...]
-----
Program, (3,2) noktasını red grubuna, (4,5) noktasını green grubuna ve son olarak (6,2) noktasını black grubuna yerleştirdi.* Sonuç olarak, tüm hesaplamaları doğru bir şekilde gerçekleştirdi ve bize sundu.
*O gruba yakın olduğunu buldu, yerleştirme diyemeyiz.