轉自：?http://blog.csdn.net/lsldd/article/details/41357931

1、KNN分類算法

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

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

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

KNN示意圖如下所示。（圖片來源：百度百科http://baike.baidu.com/view/1485833.htm?from_id=3479559&type=syn&fromtitle=knn&fr=aladdin）

上圖中要確定測試樣本綠色屬于藍色還是紅色。

顯然，當K=3時，將以1：2的投票結果分類于紅色；而K=5時，將以3：2的投票結果分類于藍色。

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

所以通常KNN的實現會把訓練數據構建成K-D Tree（K-dimensional tree），構建過程很快，甚至不用計算D維歐氏距離，而搜索速度高達O（D*log（N））。

不過當D維度過高，會產生所謂的”維度災難“，最終效率會降低到與暴力法一樣。

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

人們經過長期的實踐發現KNN算法雖然簡單，但能處理大規模的數據分類，尤其適用于樣本分類邊界不規則的情況。最重要的是該算法是很多高級機器學習算法的基礎。

當然，KNN算法也存在一切問題。比如如果訓練數據大部分都屬于某一類，投票算法就有很大問題了。這時候就需要考慮設計每個投票者票的權重了。

2、測試數據

測試數據的格式仍然和前面使用的身高體重數據一致。不過數據增加了一些：

[plain]?view plain?copy

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??

3、Python代碼

scikit-learn提供了優秀的KNN算法支持。使用Python代碼如下：

[python]?view plain?copy

#?-*-?coding:?utf-8?-*-??

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??

??

'''''?數據讀入?'''??

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)??

????

'''''?標簽轉換為0/1?'''??

y[labels=='fat']=1??

??

'''''?拆分訓練數據與測試數據?'''??

x_train,?x_test,?y_train,?y_test?=?train_test_split(x,?y,?test_size?=?0.2)??

??

'''''?創建網格以方便繪制?'''??

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))??

??

'''''?訓練KNN分類器?'''??

clf?=?neighbors.KNeighborsClassifier(algorithm='kd_tree')??

clf.fit(x_train,?y_train)??

??

'''''測試結果的打印'''??

answer?=?clf.predict(x)??

print(x)??

print(answer)??

print(y)??

print(np.mean(?answer?==?y))??

??

'''''準確率與召回率'''??

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']))??

??

'''''?將整個測試空間的分類結果用不同顏色區分開'''??

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)??

??

'''''?繪制訓練樣本?'''??

plt.scatter(x_train[:,?0],?x_train[:,?1],?c=y_train,?cmap=plt.cm.Paired)??

plt.xlabel(u'身高')??

plt.ylabel(u'體重')??

plt.show()??

4、結果分析

其輸出結果如下：

[ 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.]
準確率=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

?

KNN分類器在眾多分類算法中屬于最簡單的之一，需要注意的地方不多。有這幾點要說明：
1、KNeighborsClassifier可以設置3種算法：‘brute’，‘kd_tree’，‘ball_tree’。如果不知道用哪個好，設置‘auto’讓KNeighborsClassifier自己根據輸入去決定。

2、注意統計準確率時，分類器的score返回的是計算正確的比例，而不是R2。R2一般應用于回歸問題。

3、本例先根據樣本中身高體重的最大最小值，生成了一個密集網格（步長h=0.01），然后將網格中的每一個點都當成測試樣本去測試，最后使用contourf函數，使用不同的顏色標注出了胖、廋兩類。

容易看到，本例的分類邊界，屬于相對復雜，但卻又與距離呈現明顯規則的鋸齒形。

這種邊界線性函數是難以處理的。而KNN算法處理此類邊界問題具有天生的優勢。我們在后續的系列中會看到，這個數據集達到準確率=0.94算是很優秀的結果了。

總結

以上是生活随笔為你收集整理的用Python开始机器学习（4：KNN分类算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。