近朱者赤近墨者黑的K近鄰算法

一. KNN算法原理

KNN算法在機器學習里面，屬于相對簡單的算法。KNN即K近鄰（K Nerest Neighbor）算法，KNN算法原理用一句話說肺缕，就是“近朱者赤近墨者黑”原理。舉個例子吨些，KNN算法是知道我朋友的是什么人搓谆，來判斷我是什么人的算法。根據(jù)我所有的朋友中豪墅，如果我多數(shù)朋友屬于待人誠懇的人，那我多半也是個待人誠懇的人（：））黔寇。

二. KNN算法的步驟

KNN算法可以用于分類和回歸偶器，所謂的分類，比如要把電影分為功夫片缝裤，喜劇片屏轰，愛情片等，得到的值是相當于一個枚舉值憋飞；回歸問題霎苗，結果是連續(xù)值中的一個，比如要求一個人的身高榛做，求一個而房屋的房價估值唁盏，這就算回歸。

KNN算法检眯，中的K是距離待分類物體的K個離它最近的鄰居厘擂，一般套路是：

計算要待分類與其他物體之間的距離。
得到與待分類物體的最近的K個物體锰瘸。
判斷這K個物體屬于什么類別刽严，那么這個待分類的物體就屬于什么類別。
K近鄰算法從上面看出避凝，其實不需要擬合什么模型舞萄，只是基于存儲的算法眨补。
也可以看出兩個最為關鍵：
1.K值如何選擇？
2.距離如何計算倒脓。
K值不能選的太小撑螺，太小，有可能是噪音節(jié)點和待分類節(jié)點靠近把还，那么就造成分類的錯誤实蓬；如果K值過大，不在一類的物體分到一類里面了吊履，容易造成欠擬和安皱，有可能沒有把物體的分類真正分出來。

舉個例子：

K近鄰算法

如上面的例子：
1）選擇K=3的時候艇炎，離綠色待分類點最近的三個點中酌伊，2個屬于紅色三角形，1個屬于藍色正方形這一類缀踪，我們把綠色節(jié)點歸于紅色三角類居砖。
2）選擇K=5的時候，離綠色待分類點最近的5個點中驴娃，3個屬于藍色正方形類奏候，2個屬于紅色三角類，所以綠色待分類的節(jié)點屬于藍色正方形類唇敞。
至于這些藍色正方形和紅色三角形確定好的分類蔗草，是以前標記過的。
好的疆柔，下面來看看KNN中的幾種計算距離的算法：
歐式距離
1.歐式距離咒精，就是空間中兩個點的直線距離。
空間兩個點的坐標分別為：(x1,y1)和(x2,y2)那么它們的歐式距離為：

公式

這個公式其實就是求出了如下圖中的AB之間的這個斜線的長度旷档。

歐式距離

N維空間中的AB兩點的歐式距離公式為：
A點的坐標為(x1,x2,x3...xn)
B點的坐標為(y1,y2,y3...yn)

N維空間中AB兩點中歐式距離

曼哈頓距離
2.曼哈頓距離是兩點的坐標的之差的絕對值之和模叙。點A坐標為(x1,y1),點B的坐標為（x2，y2）
公式為：

曼哈頓距離公式

曼哈頓距離

圖中的黃色的和灰色也就是最外面兩個折線就是曼哈頓距離鞋屈，紅色和藍色也是等價的曼哈頓距離范咨，綠色的為上面說的歐式距離。

N維的曼哈頓距離為：

N維曼哈頓距離

切比雪夫距離
3.切比雪夫距離在 二維空間 內(nèi)谐区，兩個點之間的切比雪夫距離為它們橫坐標之差的絕對值與縱坐標之差的絕對值的最大值湖蜕。比如A點坐標為(X1,Y1) B點坐標為(X2,Y2) .則 A,B 之間的切比雪夫距離用公式可以表示為：

切比雪夫距離

閔可夫斯基距離
這個閔可夫斯基距離不是一個距離，是一組距離的定義宋列，公式如下：

閔可夫斯基距離

p表示維度昭抒，如果p為1，則為曼哈頓距離，如果p為2則為歐式距離灭返，p為無窮大盗迟，則為切比雪距離。

余弦距離
余弦距離以前的文章有介紹熙含，其實算是求兩個向量的夾角罚缕，可以用來計算物品的相似度，或搜索文本的相似度怎静，適合做搜索邮弹。

KNN的近鄰算法需要大量計算兩個物體的距離，所以性能比較低蚓聘，為了提升性能腌乡，就有了KD數(shù)，這是對N維向量的二叉樹表示的數(shù)據(jù)結構夜牡，

三實戰(zhàn)

sklearn里面也有knn算法与纽，里面的核心函數(shù)說明如下：

def KNeighborsClassifier(n_neighbors = 5,
                       weights='uniform',
                       algorithm = '',
                       leaf_size = '30',
                       p = 2,
                       metric = 'minkowski',
                       metric_params = None,
                       n_jobs = None
                       )

參數(shù)說明：

n_neighbors：這個值就是指 KNN 中的 “K”。
weights：權重塘装，這個參數(shù)有三個可選參數(shù)的值急迂，決定了如何分配權重。參數(shù)選項如下：
? 'uniform'：不管遠近權重都一樣蹦肴，就是最普通的 KNN 算法的形式僚碎。
? 'distance'：權重和距離成反比，距離預測目標越近具有越高的權重阴幌。
? 自定義函數(shù)：自定義函數(shù)听盖，根據(jù)輸入的坐標值返回對應的權重，達到自定義權重的目的裂七。
algorithm: 在 sklearn 中，要構建 KNN 模型有三種構建方式：

暴力法仓坞，就是直接計算距離存儲比較的背零，適合小數(shù)據(jù)集合。
使用 kd 樹構建 KNN 模型
使用球樹構建无埃。
如果數(shù)據(jù)量比較大一般會選擇用 KD 樹構建 KNN 模型徙瓶，而當 KD 樹也比較慢的時候，則可以試試球樹來構建 KNN嫉称。參數(shù)選項如下：
? 'brute' ：蠻力實現(xiàn)
? 'kd_tree'：KD 樹實現(xiàn) KNN 適合數(shù)據(jù)量大的情況
? 'ball_tree'：球樹實現(xiàn) KNN 適合的數(shù)據(jù)量很大的情況侦镇。
? 'auto'：默認參數(shù)，自動選擇合適的方法構建模型织阅。
不過當數(shù)據(jù)較小或比較稀疏時壳繁，無論選擇哪個最后都會使用 'brute'

leaf_size：如果是選擇蠻力實現(xiàn)，那么這個值是可以忽略的，當使用KD樹或球樹闹炉，它就是是停止建子樹的葉子節(jié)點數(shù)量的閾值蒿赢。默認30，但如果數(shù)據(jù)量增多這個參數(shù)需要增大渣触，否則速度過慢不說羡棵，還容易過擬合。
p：和metric結合使用的嗅钻，當metric參數(shù)是"minkowski"的時候皂冰，p=1為曼哈頓距離， p=2為歐式距離养篓。默認為p=2秃流。

metric：指定距離度量方法，一般都是使用歐式距離觉至。
? 'euclidean' ：歐式距離
? 'manhattan'：曼哈頓距離
? 'chebyshev'：切比雪夫距離
? 'minkowski'：閔可夫斯基距離剔应，默認參數(shù)
6.n_jobs：指定多少個CPU進行運算，默認是-1语御，也就是全部都算峻贮。

利用sklearn里面的手寫數(shù)據(jù)集合做測試，手寫數(shù)據(jù)集合一共有1797個樣本应闯，每個樣本都是8*8 個像素點纤控，每個點的值為一個0-255的灰度值，可以先運行看看數(shù)據(jù)情況：

from sklearn.model_selection import train_test_split
from sklearn import preprocessing
from sklearn.metrics import accuracy_score
from sklearn.datasets import load_digits
from sklearn.neighbors import KNeighborsClassifier
from sklearn.svm import SVC
from sklearn.naive_bayes import MultinomialNB
from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt


# 加載數(shù)據(jù)
digits = load_digits()
data = digits.data
# 數(shù)據(jù)探索
print(data.shape)
# 查看第2幅圖像
print(digits.images[1])
# 第2幅圖像代表的數(shù)字含義
print(digits.target[1])
# 將第2幅圖像顯示出來
plt.gray()
plt.imshow(digits.images[1])
plt.show()

數(shù)據(jù)展示

最后展示下課中代碼碉纺，注意這里面在做多項式樸素貝葉斯分類的時候采用的是采用Min-Max規(guī)范化船万，是因為算法不準許為負數(shù)。

from sklearn.model_selection import train_test_split
from sklearn import preprocessing
from sklearn.metrics import accuracy_score
from sklearn.datasets import load_digits
from sklearn.neighbors import KNeighborsClassifier
from sklearn.svm import SVC
from sklearn.naive_bayes import MultinomialNB
from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt


# 加載數(shù)據(jù)
digits = load_digits()
#這個data可以看成一個二維數(shù)組骨田，第一維度為1797個耿导，
#每一個是由一個8*8個像素點的灰度值組成
data = digits.data
# 數(shù)據(jù)探索
print(data.shape)
# 查看第2幅圖像
print(digits.images[1])
# 第2幅圖像代表的數(shù)字含義
print(digits.target[1])
# 將第2幅圖像顯示出來
plt.gray()
plt.imshow(digits.images[1])
plt.show()

# 分割數(shù)據(jù)，將20%的數(shù)據(jù)作為測試集态贤，其余作為訓練集
train_x, test_x, train_y, test_y = train_test_split(data, digits.target, test_size=0.2, random_state=33)
# 采用Z-Score規(guī)范化
ss = preprocessing.StandardScaler()
train_ss_x = ss.fit_transform(train_x)
test_ss_x = ss.transform(test_x)


# 創(chuàng)建KNN分類器
knn = KNeighborsClassifier() 
knn.fit(train_ss_x, train_y) 
predict_y = knn.predict(test_ss_x) 
print("KNN準確率: %.4lf" % accuracy_score(test_y, predict_y))



# 創(chuàng)建SVM分類器
svm = SVC()
svm.fit(train_ss_x, train_y)
predict_y=svm.predict(test_ss_x)
print('SVM準確率: %0.4lf' % accuracy_score(test_y, predict_y))
# 采用Min-Max規(guī)范化
mm = preprocessing.MinMaxScaler()
train_mm_x = mm.fit_transform(train_x)
test_mm_x = mm.transform(test_x)
# 創(chuàng)建Naive Bayes分類器
mnb = MultinomialNB()
mnb.fit(train_mm_x, train_y) 
predict_y = mnb.predict(test_mm_x) 
print("多項式樸素貝葉斯準確率: %.4lf" % accuracy_score(test_y, predict_y))


# 創(chuàng)建CART決策樹分類器
dtc = DecisionTreeClassifier()
dtc.fit(train_mm_x, train_y) 
predict_y = dtc.predict(test_mm_x) 
print("CART決策樹準確率: %.4lf" % accuracy_score(test_y, predict_y))

看下結果：

計算結果

近朱者赤近墨者黑的K近鄰算法

一. KNN算法原理

二. KNN算法的步驟

三 實戰(zhàn)

三實戰(zhàn)