前言
這是機(jī)器學(xué)習(xí)最簡(jiǎn)單的算法错邦，當(dāng)然并不是說簡(jiǎn)單就沒人用土榴。knn算法的優(yōu)點(diǎn)就是簡(jiǎn)單而且便于實(shí)現(xiàn)荸哟，并且有一定好的效果锦积。
算法原理
K近鄰的算法思路很簡(jiǎn)單芒帕。
背景
假設(shè) 有兩個(gè)類別散落在這個(gè)特征空間中。
現(xiàn)在有一個(gè)新的樣本需要預(yù)測(cè)它屬于哪個(gè)類別充包。
思路介紹
step1: 暴力的求出新樣本與其余所有樣本的“距離”副签。
step2: 找到距離它最近的k的點(diǎn)。（這就是k近鄰的名稱由來）
step3: 進(jìn)行類別打分基矮，新樣本屬于分?jǐn)?shù)最高的哪個(gè)類別淆储。
然后展開細(xì)節(jié)講：
距離
歐式距離
歐式距離的計(jì)算就是每個(gè)維度的平方和開跟號(hào)也就是直線距離。這里用二維的比較好理解家浇。就是其實(shí)x(p)是預(yù)測(cè)的樣本本砰，x(t)訓(xùn)練樣本。
當(dāng)然x钢悲，y只有兩個(gè)特征点额，現(xiàn)實(shí)往往有很多個(gè)特征也就是說有很多個(gè)維度。
其中的下標(biāo)標(biāo)號(hào)就是對(duì)應(yīng)的不同維度莺琳。
簡(jiǎn)寫就是
曼哈頓距離
曼哈頓距離的由來是在城市中的行車距離还棱。
在現(xiàn)實(shí)生活中兩點(diǎn)之間并不是都是直線可達(dá)的，這樣可以把區(qū)域分成單元的小塊惭等。就像開出租車一樣慎皱。直線綠色的就是歐式距離楼雹，藍(lán)色凌蔬、紅色闲礼、黃色都是曼哈頓距離。（圖來自 維基百科）
明可夫斯基定理
仔細(xì)看曼哈頓距離和歐氏距離
曼哈頓距離
歐氏距離
貌似有個(gè)驚人的規(guī)律
這好像是找到了距離公式 的通式秤茅。這是新發(fā)現(xiàn)么稚补？答案是否定的，有個(gè)叫明可夫斯基的人早就發(fā)現(xiàn)了這個(gè)框喳。那么2以上都都叫明可夫斯基距離（名字起光了课幕，斷了后路啊厦坛。。撰豺。）
K
K值是KNN的一個(gè)超參數(shù)粪般。（超參數(shù)：也就是模型運(yùn)行前需要確定的參數(shù)，K就是KNN算法最為直觀的一個(gè)超參數(shù)）污桦。這個(gè)參數(shù)需要人為的去調(diào)，這也就是人工在其中起的最重要的作用（調(diào)參狗）匙监。至于怎么調(diào)參凡橱？一般需要經(jīng)驗(yàn)和專業(yè)的領(lǐng)域知識(shí)。當(dāng)然也可以老中醫(yī)式的調(diào)參亭姥。如果計(jì)算量比較小可以使用網(wǎng)格搜索的方法去調(diào)參稼钩。
分類決策
一般思路是這樣的，就是把測(cè)試數(shù)據(jù)丟進(jìn)去达罗，計(jì)算與訓(xùn)練集所有點(diǎn)的距離坝撑，找到前K個(gè)點(diǎn)的類別。然后進(jìn)行PK算出類別粮揉。
黑色點(diǎn)：測(cè)試樣本巡李。
紫色點(diǎn)：類別A。
藍(lán)色點(diǎn)：類別B
如圖所示扶认，不管使用的什么距離計(jì)算方式侨拦，我們可以找到與黑色點(diǎn)與所有點(diǎn)的距離。那么我們就可以找到距離它最近的K個(gè)點(diǎn)辐宾。然后進(jìn)行類別打分狱从，明顯藍(lán)色的分?jǐn)?shù)比較高。那么該點(diǎn)就屬于藍(lán)色點(diǎn)叠纹。
這樣做是沒有問題的季研。但是機(jī)器學(xué)習(xí)目前還是很依賴數(shù)據(jù)的而且不同的場(chǎng)景下的應(yīng)用也是不一樣的。
舉個(gè)栗子
由圖所示雖然藍(lán)色類的得分高誉察，但是黑色點(diǎn)距離紫色點(diǎn)的距離更近一點(diǎn)与涡。或許它更有可能是紫色類冒窍。那么我們的距離或許需要一個(gè)權(quán)重（注意：或許递沪。因?yàn)檫@個(gè)距離權(quán)重不一定有用，要去試）综液。這個(gè)距離權(quán)重一般采用距離的倒數(shù)作為權(quán)重款慨。
重新計(jì)算得分表
那么這個(gè)類就屬于紫色類了。
模型實(shí)現(xiàn)
這里自己造的數(shù)據(jù)谬莹，自己做的最簡(jiǎn)單的實(shí)現(xiàn)檩奠。只供理解參考桩了。
import numpy as np
import matplotlib.pyplot as plt
import math
from collections import Counter
rad_1=np.random.randint(1,10,size=(5,2))
rad_1
array([[9, 3],
[6, 6],
[3, 6],
[6, 7],
[7, 1]])
rad_2=np.random.randint(11,20,size=(5,2))
rad_2
array([[13, 18],
[15, 15],
[14, 19],
[13, 11],
[11, 17]])
raw_data_X=np.vstack([rad_1,rad_2])
raw_data_X
array([[ 9, 3],
[ 6, 6],
[ 3, 6],
[ 6, 7],
[ 7, 1],
[13, 18],
[15, 15],
[14, 19],
[13, 11],
[11, 17]])
raw_data_y=[0,0,0,0,0,1,1,1,1,1]
y_train=np.array(raw_data_y)
y_train
array([0, 0, 0, 0, 0, 1, 1, 1, 1, 1])
plt.scatter(raw_data_X[y_train==0,0],raw_data_X[y_train==0,1],color='b')
plt.scatter(raw_data_X[y_train==1,1],raw_data_X[y_train==1,1],color='r',alpha=0.5)
plt.show()
x=np.array([13,14])
x
array([13, 14])
plt.scatter(raw_data_X[y_train==0,0],raw_data_X[y_train==0,1],color='b')
plt.scatter(raw_data_X[y_train==1,1],raw_data_X[y_train==1,1],color='r')
plt.scatter(x[0],x[1],color='g',alpha=0.5,marker='*')
plt.show()
KNN過程
X_train=raw_data_X
distance=[]
for x_train in X_train:
d=np.sum((x-x_train)**2)**0.5
distance.append(d)
distance
[11.704699910719626,
10.63014581273465,
12.806248474865697,
9.8994949366116654,
14.317821063276353,
4.0,
2.2360679774997898,
5.0990195135927845,
3.0,
3.6055512754639891]
distance1=[math.sqrt(np.sum((x_train-x)**2)) for x_train in X_train]
distance1
[11.704699910719626,
10.63014581273465,
12.806248474865697,
9.899494936611665,
14.317821063276353,
4.0,
2.23606797749979,
5.0990195135927845,
3.0,
3.605551275463989]
distance=[(np.sum((x_train-x)**2)**0.5)for x_train in X_train]
distance
[11.704699910719626,
10.63014581273465,
12.806248474865697,
9.8994949366116654,
14.317821063276353,
4.0,
2.2360679774997898,
5.0990195135927845,
3.0,
3.6055512754639891]
nearest=np.argsort(distance)
nearest
array([6, 8, 9, 5, 7, 3, 1, 0, 2, 4])
k=6
topK_y=y_train[nearest[:6]]
topK_y
array([1, 1, 1, 1, 1, 0])
Votes=Counter(topK_y)
Votes.most_common(1)[0][0]
1
pwd
'/Users/zhangyan/Documents/SystemEnv/anaconda3/bin/boboML'
def knn(k,X_train,y_train,x):
assert 1<=k<= X_train.shape[0], "k不能大于訓(xùn)練樣本的個(gè)數(shù)"
assert X_train.shape[0]==y_train.shape[0], "訓(xùn)練樣本個(gè)數(shù)要等于標(biāo)簽數(shù)"
assert X_train.shape[1]==x.shape[0],"測(cè)試數(shù)據(jù)特征個(gè)數(shù)要與訓(xùn)練樣本相同"
distance=[]
distance=[(np.sum((x_train-x)**2)**0.5)for x_train in X_train]
nearest = np.argsort(distance)
topK_y = y_train[nearest[:6]]
Votes = Counter(topK_y)
return Votes.most_common(1)[0][0]
knn(6,X_train,y_train,x)
1
from KNN_function import knn_fun1
from mymodule import FirstML
FirstML.predict(1)
1
knn_fun1.knn(6,X_train,y_train,x)
1
scikit-learn的kNN
from sklearn.neighbors import KNeighborsClassifier
kNN_classifier=KNeighborsClassifier(n_neighbors=6)
kNN_classifier.fit(X_train,y_train)
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
metric_params=None, n_jobs=1, n_neighbors=6, p=2,
weights='uniform')
kNN_classifier.predict(x.reshape(1,-1))
array([1])
class KNNClassifier:
def __init__(self,k):
assert k>0,"k不能小于0"
self.k=k
def fit(self,X_train,y_train):
assert X_train.shape[0] == y_train.shape[0], "訓(xùn)練樣本個(gè)數(shù)要等于標(biāo)簽數(shù)"
self.X_train=X_train
self.y_train=y_train
return self
def prdict(self,x_predict):
assert self.X_train.shape[1] == x_predict.shape[1], "測(cè)試數(shù)據(jù)特征個(gè)數(shù)要與訓(xùn)練樣本相同"
return np.array([self._predict(x) for x in x_predict])
def _predict(self,x):
distance = [(np.sum((x_train - x) ** 2) ** 0.5) for x_train in X_train]
nearest = np.argsort(distance)
topK_y = y_train[nearest[:6]]
Votes = Counter(topK_y)
return Votes.most_common(1)[0][0]
cls=KNNClassifier(k=6)
cls.fit(X_train,y_train)
<__main__.KNNClassifier at 0x1094f3b00>
cls.prdict(x.reshape(1,-1))
array([1])
cls1=knn_fun1.KNNClassifier(6)
cls1.fit(X_train,y_train)
<KNN_function.knn_fun1.KNNClassifier at 0x1094f3320>
cls1.predict(x.reshape(1,-1))
array([1])
x=np.array([[1,4],[5,6],[12,12]])
x.shape[1]
2
X_train.shape[1]
2
cls1.predict(x)
array([0, 0, 1])
