k-NN algoritması (Nearest Neighbor: En Yakın Komşuluk)

k-NN (k-Nearest Neighbor: En Yakın Komşuluk) tüm makine öğrenmesi algoritmaları arasında bence öğrenmesi ve uygulaması en kolay algoritmalardan biridir. Çünkü konsept olarak çok basittir. Diğer algoritmalarda olduğu gibi burada çok kompleks fonksiyonlar işin içinde olmadığı için matematiğe çok girmenize gerek yoktur. Makine öğrenmesi hakkında fikri olmayan birine bile bu konsepti çok rahat anlatabilirsiniz.

İncelemeye algoritmanın sözde kodunu (pseudo code) yazarak başlayalım isterseniz:

k-NN sınıflandırma algoritması
1- Bir k değeri ve uzaklık metriği seçelim
2- Veri seti içerisinde sınıflandırmak istediğimiz örneğe ait en yakın k adet komşuyu bulalım
3- Çoğunluk kararına göre örneğin sınıfı atanır

kNN

Şekilde belirtildiği gibi en fazla sayıdaki sınıfın etiketi örneğimize atanır.

k-NN bu kadar etkin ve kolay bir algoritma olmasına karşın bazı önemli dezavantajlara sahiptir.

  • Örnek sayısı arttığında yapmamız gereken karşılaştırma işlemlerinin sayısı da lineer bir şekilde artmaktadır ve bu çok ağır bir işlem yükü getirmektedir.
  • Özellikle boyut sayısı ve k sayısı arttığında kNN algoritması "overfitting" problemi ile karşı karşıya kalmaktadır.

Küçük bir kodlama örneği yapalım şimdi. Bu örnek için iris veri setini kullanalım. (Laf aramızda ben sıkıldım bu iris veri setinden artık :) İlerleyen yazılarımızda daha başka veri setleri kullanmaya çalışacağım)

In [2]:
# pandas yüklemek lazım!
import pandas as pd
# numpy
import numpy as np

# matplotlib
import matplotlib.pyplot as plt
# ggplot stilinde kullanalım
plt.style.use('ggplot')

# Scikit Learn
from sklearn import datasets
from sklearn.decomposition import PCA
from sklearn.neighbors import KNeighborsClassifier
In [3]:
%matplotlib notebook
In [4]:
# iris verisetini yukluyoruz
iris = datasets.load_iris()

# 1. ve 3. özniteliği alalım 
X = iris.data[:, [0,2]]
y = iris.target

plt.figure()
# Haydi çizdirelim bunu
# Setosa için
plt.scatter(X[y==0,0],X[y==0,1],c="b")
# Versicolor için
plt.scatter(X[y==1,0],X[y==1,1],c='r')
# Virginica için
plt.scatter(X[y==2,0],X[y==2,1],c="g")

plt.legend(iris["target_names"])
plt.xlabel(iris.feature_names[0]);
plt.ylabel(iris.feature_names[2]);
In [5]:
# Çizdirmeyi gerçekleştirmek için yardımcı fonksiyonu çağıralım
import sys
sys.path.append("..")
from datafloyd.plot import plot_decision_region
In [6]:
# Sınıflandırıcıyı eğitelim ve görselleştirelim
kNN = KNeighborsClassifier(n_neighbors=3,metric="euclidean")
kNN.fit(X,y)

plt.figure()
plot_decision_region(X,y,kNN,legend=iris.target_names)

plt.xlabel(iris.feature_names[0]);
plt.ylabel(iris.feature_names[2]);
plt.title("kNN'de en yakın 3 komşu kullanıldı");

Şimdi isterseniz bir de k değerini arttıralım neler olacak bakalım. Değişimi daha iyi anlayabilmek için bu değeri 21 seçelim

In [7]:
# Sınıflandırıcıyı eğitelim ve görselleştirelim
kNN = KNeighborsClassifier(n_neighbors=21,metric="euclidean")
kNN.fit(X,y)

plt.figure()
plot_decision_region(X,y,kNN,legend=iris.target_names)

plt.xlabel(iris.feature_names[0]);
plt.ylabel(iris.feature_names[2]);
plt.title("kNN'de en yakın 3 komşu kullanıldı");

Gördüğünüz gibi sınır değişti, çünkü artık en yakın 21 komşuluk değerlendiriliyor. Bir de uzaklık ölçütünü değiştirelim bakalım neler olacak.

In [8]:
# Sınıflandırıcıyı eğitelim ve görselleştirelim
kNN = KNeighborsClassifier(n_neighbors=21,metric="chebyshev")
kNN.fit(X,y)

plt.figure()
plot_decision_region(X,y,kNN,legend=iris.target_names)

plt.xlabel(iris.feature_names[0]);
plt.ylabel(iris.feature_names[2]);
plt.title("kNN'de en yakın 3 komşu kullanıldı");

Buradaki "Chebysev" metriği "max(|x - y|)" şeklinde tanımlandığı için karar sınırları oldukça değişti gördüğünüz gibi.

Bir başka yazımızda tekrar görüşmek üzere esen kalın!