使用Python處理KNN分類算法的實(shí)現(xiàn)代碼

更新時(shí)間：2022年09月06日 14:29:37 作者：阿里機(jī)器智能

KNN分類算法（K-Nearest-Neighbors?Classification），又叫K近鄰算法，是一個概念極其簡單，而分類效果又很優(yōu)秀的分類算法，這篇文章主要介紹了使用Python處理KNN分類算法,需要的朋友可以參考下

KNN分類算法的介紹

KNN分類算法（K-Nearest-Neighbors Classification），又叫K近鄰算法，是一個概念極其簡單，而分類效果又很優(yōu)秀的分類算法。

他的核心思想就是，要確定測試樣本屬于哪一類，就尋找所有訓(xùn)練樣本中與該測試樣本“距離”最近的前K個樣本，然后看這K個樣本大部分屬于哪一類，那么就認(rèn)為這個測試樣本也屬于哪一類。簡單的說就是讓最相似的K個樣本來投票決定。

這里所說的距離，一般最常用的就是多維空間的歐式距離。這里的維度指特征維度，即樣本有幾個特征就屬于幾維。

KNN示意圖如下所示。（圖片來源：百度百科）

上圖中要確定測試樣本綠色屬于藍(lán)色還是紅色。

顯然，當(dāng)K=3時(shí)，將以1：2的投票結(jié)果分類于紅色；而K=5時(shí)，將以3：2的投票結(jié)果分類于藍(lán)色。

KNN算法簡單有效，但沒有優(yōu)化的暴力法效率容易達(dá)到瓶頸。如樣本個數(shù)為N，特征維度為D的時(shí)候，該算法時(shí)間復(fù)雜度呈O（DN)增長。

所以通常KNN的實(shí)現(xiàn)會把訓(xùn)練數(shù)據(jù)構(gòu)建成K-D Tree（K-dimensional tree），構(gòu)建過程很快，甚至不用計(jì)算D維歐氏距離，而搜索速度高達(dá)O（D*log（N））。

不過當(dāng)D維度過高，會產(chǎn)生所謂的”維度災(zāi)難“，最終效率會降低到與暴力法一樣。

因此通常D>20以后，最好使用更高效率的Ball-Tree，其時(shí)間復(fù)雜度為O（D*log（N））。

人們經(jīng)過長期的實(shí)踐發(fā)現(xiàn)KNN算法雖然簡單，但能處理大規(guī)模的數(shù)據(jù)分類，尤其適用于樣本分類邊界不規(guī)則的情況。最重要的是該算法是很多高級機(jī)器學(xué)習(xí)算法的基礎(chǔ)。

當(dāng)然，KNN算法也存在一切問題。比如如果訓(xùn)練數(shù)據(jù)大部分都屬于某一類，投票算法就有很大問題了。這時(shí)候就需要考慮設(shè)計(jì)每個投票者票的權(quán)重了。

測試數(shù)據(jù)

測試數(shù)據(jù)的格式仍然和前面使用的身高體重?cái)?shù)據(jù)一致。不過數(shù)據(jù)稍微增加了一些

1.5 40 thin
1.5 50 fat
1.5 60 fat
1.6 40 thin
1.6 50 thin
1.6 60 fat
1.6 70 fat
1.7 50 thin
1.7 60 thin
1.7 70 fat
1.7 80 fat
1.8 60 thin
1.8 70 thin
1.8 80 fat
1.8 90 fat
1.9 80 thin
1.9 90 fat

Python代碼實(shí)現(xiàn)

scikit-learn提供了優(yōu)秀的KNN算法支持。

import numpy as np
from sklearn import neighbors
from sklearn.metrics import precision_recall_curve
from sklearn.metrics import classification_report
from sklearn.cross_validation import train_test_split
import matplotlib.pyplot as plt
 
''' 數(shù)據(jù)讀入 '''
data = []
labels = []
with open("data\\1.txt") as ifile:
 for line in ifile:
  tokens = line.strip().split(' ')
  data.append([float(tk) for tk in tokens[:-1]])
  labels.append(tokens[-1])
x = np.array(data)
labels = np.array(labels)
y = np.zeros(labels.shape)
 
''' 標(biāo)簽轉(zhuǎn)換為0/1 '''
y[labels=='fat']=1
 
''' 拆分訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù) '''
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size = 0.2)
 
''' 創(chuàng)建網(wǎng)格以方便繪制 '''
h = .01
x_min, x_max = x[:, 0].min() - 0.1, x[:, 0].max() + 0.1
y_min, y_max = x[:, 1].min() - 1, x[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
   np.arange(y_min, y_max, h))
 
''' 訓(xùn)練KNN分類器 '''
clf = neighbors.KNeighborsClassifier(algorithm='kd_tree')
clf.fit(x_train, y_train)
 
'''測試結(jié)果的打印'''
answer = clf.predict(x)
print(x)
print(answer)
print(y)
print(np.mean( answer == y))
 
'''準(zhǔn)確率與召回率'''
precision, recall, thresholds = precision_recall_curve(y_train, clf.predict(x_train))
answer = clf.predict_proba(x)[:,1]
print(classification_report(y, answer, target_names = ['thin', 'fat']))
 
''' 將整個測試空間的分類結(jié)果用不同顏色區(qū)分開'''
answer = clf.predict_proba(np.c_[xx.ravel(), yy.ravel()])[:,1]
z = answer.reshape(xx.shape)
plt.contourf(xx, yy, z, cmap=plt.cm.Paired, alpha=0.8)
 
''' 繪制訓(xùn)練樣本 '''
plt.scatter(x_train[:, 0], x_train[:, 1], c=y_train, cmap=plt.cm.Paired)
plt.xlabel(u'身高')
plt.ylabel(u'體重')
plt.show()

結(jié)果分析

輸出結(jié)果：
[ 0. 0. 1. 0. 0. 1. 1. 0. 0. 1. 1. 0. 0. 1. 1. 0. 1.]
[ 0. 1. 1. 0. 0. 1. 1. 0. 0. 1. 1. 0. 0. 1. 1. 0. 1.]
準(zhǔn)確率=0.94, score=0.94
precision recall f1-score support
thin 0.89 1.00 0.94 8
fat 1.00 0.89 0.94 9
avg / total 0.95 0.94 0.94 17