KNN (K-Nearest Neighborhood)

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.

image

Ö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.

image

İ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).

image

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.

Blog: http://r0ark.xyz/machine-learning/2018/05/08/knn.html

2 Beğeni

Machine Learning benim daha ilgilenemediğim bir branş, yani sıra daha ona gelmedi. Kendimi bu branşa dalmak için yeterli görmüyorum. Fakat ilgimi de acayip çekiyor. :slight_smile:

Ethem Alpaydın’ın Yapay Öğrenme öğrenme kitabı başlangıç için güzel olabilir. Henüz bir lise öğrencisi olarak hakkıyla anlayamıyor olsam da Khan Academy ile öğrenmeye çalışıyorum :slight_smile:

Siz yine erken yaşta öğrenmeye başlamışsınız ve tahmin ediyorum benim yaşıma geldiğinizde oldukça ileri bir seviyede olacaksınız. Yaşım 32 ve 2 senedir branşım olmamasına rağmen programlamayla ilgileniyorum. Yeni bilgiler öğrenmek zevkli oluyor. Khan Academy’de bir hesabım vardı. Unuttuğum matematik konularını hatırlamak için üye olmuştum :slight_smile: Orada biraz zaman geçirdikten sonra da baya bir süre uğramadım. Belki sayenizde tekrar uğrarım. Kitap önerisi için de teşekkür ederim.

1 Beğeni

Bu sohbete değer bir konu.

Ne kadar erken yaşta başlansa iyi, ama artık geç diyip vazgeçmek de yanlış. @Nadir_Bencan dedem yaşında mesela, ama öğrenmeye çabalıyor. Ben de forumdaki en genç kişiyim büyük ihtimalle. Hatta benim için fazla erken bile denilebilir.

Herhalde forumdaki en genç benim çünkü aralık doğumluyum yaşıtız diye biliyorum :slight_smile:
önemli olan bu değil çalışmak gerçekten dediğiniz gibi çok önemli bir şey azim ondanda önemli

Kişisel düşüncem, artık okullarda temel programlama bilgilerinin öğretilmesi gerektiği yönünde. Genç arkadaşların problem çözme ve çok yönlü düşünme gibi becerilerine, yaratıcılıklarına katkı sağlayabileceğini düşünüyorum.

Maalesef bilime, teknolojiye çok önem veren bir ülke değiliz. Ülke gündeminin ne kadar saçma konularla meşgul edildiği görülüyor.

Ülkenin kendi kaynakları olan gençlere yatırım yapılmazsa, nasıl geleceğin umudu olmalarını bekleyebiliriz?

1 Beğeni

Yok, ben 1-2 yaş daha küçüğüm.

Katılıyorum. 6. Sınıf Bilişim teknolojileri dersinde bizim öğretmenimiz scratch’ı gösterdi. Ama ben hiç sevmedim. Scatch’da yaptıklarımızın java’da nasıl yapıldığını gösterdi, milletin gözü korktu.

Çocukların durumu daha fena. Hepsi türlü türlü ahlaksızlıklar, küfürler içinde, Dersler umurlarında değil… Gördükçe acıyorum hepsine… Asıl kötü olan, bunun feci derecede bulaşıcı olması.

Evet…

Yaşınız kaç acaba merak ettiğim için soruyorum :slight_smile:

13 yaşındayım ve 8. Sınıfa geçtim.

Geçen konuştuğumuzda lise öğrencisiyim v.s demiştiniz duruyor yazışmalar :slight_smile:

Yok öyle demedim siz liseliyim dediniz ama ben yorum yapmadım. Siz liseliyim sandınız.

Tamamdır o zaman ben yanlış anlamışımdır olabilir 2 yaş varmış aramızda

Çocukların durumu fena ? :smiley: 13 yaşındaki biri diyor bunu :slight_smile:

Küçük olma çabası ne böyle anlamadım :confused: