k近臨法的的是三個(gè)基本要素：k值的選擇，距離度量及分類(lèi)決策規(guī)則。
k近鄰算法和模型
什么是k近臨算法？即是：給定一個(gè)訓(xùn)練數(shù)據(jù)集，對(duì)新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最近臨的k個(gè)實(shí)例，這k個(gè)實(shí)例的多數(shù)屬于某個(gè)類(lèi)，就把該輸入實(shí)例歸為這個(gè)類(lèi)。
k近鄰模型對(duì)應(yīng)于基于訓(xùn)練數(shù)據(jù)集對(duì)特征空間的一個(gè)劃分。k近鄰算法中，當(dāng)訓(xùn)練集、距離度量、k值及分類(lèi)決策規(guī)則確定后，其結(jié)果唯一確定。
我理解的就是物以類(lèi)聚，人以群分。根據(jù)已有的人，將新來(lái)的人按照不同屬性特征來(lái)歸個(gè)類(lèi)。。。
度量實(shí)例點(diǎn)的相似程度
用特征空間中的兩個(gè)實(shí)例點(diǎn)的距離來(lái)度量?jī)蓚€(gè)實(shí)例點(diǎn)的相似程度。度量手段如下，最常用的是使用歐式距離。
math.pow()，pow() 方法返回 x^y（x的y次方的值。
In [13]:math.pow(3,3)
Out[13]: 27.0
In [14]:math.pow(100,-2)
Out[14]: 0.0001
#課本P39例3.1
In [1]:import math
...:from itertools import combinations
In [5]: def L(x, y, p=2):
...: if len(x) == len(y) and len(x) > 1:
...: sum = 0
...: for i in range(len(x)):
...: sum += math.pow(abs(x[i] - y[i]), p)
...: return math.pow(sum, 1/p)
...: else:
...: return 0
In [6]: x1 = [1, 1]
...: x2 = [5, 1]
...: x3 = [4, 4]
In [7]: for i in range(1, 5):
...: r = { '1-{}'.format(c):L(x1, c, p=i) for c in [x2, x3]}
...: print(min(zip(r.values(), r.keys())))
(4.0, '1-[5, 1]')
(4.0, '1-[5, 1]')
(3.7797631496846193, '1-[4, 4]')
(3.5676213450081633, '1-[4, 4]')
k近臨算法一般流程：
?收集數(shù)據(jù)： 可以使用任何方法
?準(zhǔn)備數(shù)據(jù)： 距離計(jì)算所需要的數(shù)值， 最后是結(jié)構(gòu)化的數(shù)據(jù)格式。
?分析數(shù)據(jù)： 可以使用任何方法
?訓(xùn)練算法： k近臨算法不需要訓(xùn)練數(shù)據(jù)
?測(cè)試算法： 計(jì)算錯(cuò)誤率
?使用算法： 首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運(yùn)行k-近鄰算法判定輸入數(shù)據(jù)分別屬于哪個(gè)分類(lèi)，最后應(yīng)用對(duì)計(jì)算出的分類(lèi)執(zhí)行后續(xù)的處理
如何選取合適的k值？
1、如果選擇較小的K值?！皩W(xué) 習(xí)” 的近似誤差（ approximation error)會(huì)減小， 但“學(xué)習(xí)” 的估計(jì)誤差（estimation error) 會(huì)增大，預(yù)測(cè)的結(jié)果會(huì)對(duì)近臨的實(shí)例點(diǎn)非常敏感。話句話說(shuō)，K值的減小就意味著整體模型變得復(fù)雜， 容易發(fā)生過(guò) 擬合.
2、如果選擇較大的K值。可以減少學(xué)習(xí)的估計(jì)誤差， 但缺點(diǎn)是學(xué)習(xí)的近似誤差會(huì)增大.K值的增大 就意味著整體的模型變得簡(jiǎn)單。
3、在應(yīng)用中，k值一般取一個(gè)比較小的數(shù)值。通常采用交叉驗(yàn)證法來(lái)選取最優(yōu)的k值。
分類(lèi)決規(guī)則？
k近臨法中的分類(lèi)決策規(guī)則往往是多數(shù)表決，即由輸入實(shí)例的k個(gè)鄰近的訓(xùn)練實(shí)例中的多數(shù)類(lèi)決定輸入實(shí)例的類(lèi)。
k近臨構(gòu)造kd樹(shù)
kd樹(shù)是一種對(duì)k維空間中的實(shí)例點(diǎn)進(jìn)行存儲(chǔ)以便對(duì)其進(jìn)行快速檢索的樹(shù)形數(shù)據(jù)結(jié)構(gòu)。kd樹(shù)是二叉樹(shù)，表示對(duì)k維空間的一個(gè)劃分。
構(gòu)造kd樹(shù)的方法如下：構(gòu)造根節(jié)點(diǎn)，使根節(jié)點(diǎn)對(duì)應(yīng)于k維空間中包含所有實(shí)例點(diǎn)的超矩形區(qū)域，通過(guò)遞歸方法（哪種遞歸方法，書(shū)上有所，太多文字了），不斷地對(duì)k維空間進(jìn)行切分，生成子節(jié)點(diǎn)。
書(shū)中例子如下?？床欢脑捒梢詤⒁?jiàn)完結(jié)篇|一文搞懂k近鄰（k-NN）算法（二），這個(gè)寫(xiě)的比較詳細(xì)。
k近臨搜索kd樹(shù)
k近臨搜索也是遞歸搜索，具體算法可以參見(jiàn)書(shū)本。
kd樹(shù)更適合于訓(xùn)練實(shí)例數(shù)遠(yuǎn)大于空間維數(shù)時(shí)的k近鄰搜索。當(dāng)空間維數(shù)接近訓(xùn)練實(shí)例數(shù)時(shí)，它的效率會(huì)迅速下降，幾乎接近線性掃描。具體可參見(jiàn)完結(jié)篇|一文搞懂k近鄰（k-NN）算法（二）
關(guān)于k近鄰的詳細(xì)實(shí)現(xiàn)過(guò)程建議參考《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》的第2章-k近鄰算法。另外參見(jiàn)李航《統(tǒng)計(jì)學(xué)習(xí)方法》K近鄰學(xué)習(xí)算法實(shí)現(xiàn)
調(diào)用scikitlearn的k近鄰算法包
#導(dǎo)入相關(guān)機(jī)器學(xué)習(xí)包
In [10]: import numpy as np
...: import pandas as pd
...: from sklearn.datasets import load_iris
...: from sklearn.model_selection import train_test_split
#利用鳶尾花數(shù)據(jù)集進(jìn)行測(cè)試
In [11]: iris = load_iris()
...: df = pd.DataFrame(iris.data, columns=iris.feature_names)
...: df['label'] = iris.target
...: df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
In [12]: data = np.array(df.iloc[:100, [0, 1, -1]])
...: X, y = data[:,:-1], data[:,-1]
...: X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
#導(dǎo)入機(jī)器學(xué)習(xí)包，并對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行擬合
In [13]: from sklearn.neighbors import KNeighborsClassifier
In [14]: clf_sk = KNeighborsClassifier()
...: clf_sk.fit(X_train, y_train)
...:
Out[14]:
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
metric_params=None, n_jobs=1, n_neighbors=5, p=2,
weights='uniform')
#對(duì)測(cè)試集進(jìn)行預(yù)測(cè)
In [15]: clf_sk.score(X_test, y_test)
Out[15]: 1.0
參考鏈接：
一文搞懂k近鄰（k-NN）算法（一）
完結(jié)篇|一文搞懂k近鄰（k-NN）算法（二）
【量化課堂】一只兔子幫你理解 kNN
【量化課堂】kd 樹(shù)算法之詳細(xì)篇
wzyonggege/statistical-learning-method
