k近邻法(k-nearest neighbor, k-NN)
一種基本分類與回歸方法
工作原理是：1、訓練樣本集+對應標簽
2、輸入沒有標簽的新數據，將新的數據的每個特征與樣本集中數據對應的特征進行比較，然后算法提取樣本最相似數據(最近鄰)的分類標簽。
3、一般來說，我們只選擇樣本數據集中前k個最相似的數據。
4、選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。
k-近鄰算法沒有進行數據的訓練，直接使用未知的數據與已知的數據進行比較，得到結果。因此，可以說k-鄰近算法不具有顯式的學習過程。
距離度量：歐氏距離
工作流程：
收集數據：可以使用爬蟲進行數據的收集，也可以使用第三方提供的免費或收費的數據。一般來講，數據放在txt文本文件中，按照一定的格式進行存儲，便于解析及處理。
準備數據：使用Python解析、預處理數據。
分析數據：可以使用很多方法對數據進行分析，例如使用Matplotlib將數據可視化。
測試算法：計算錯誤率。
使用算法：錯誤率在可接受范圍內，就可以運行k-近鄰算法進行分類。
KNN算法原理代碼：
1 import numpy as np
2 import operator
3
4 def classify0(inx,dataset,labels,k): #定義一個分類函數，測試數據，數據集，標簽集，k個
5 datasetsize = dataset.shape[0] #獲取數據集的第一維個數，為了計算測試數據與數據集中每個數據的距離
6 diffmat = np.tile(inx,(datasetsize,1)) - dataset #將測試數據在行上重復多次，列上重復一次，也就是不重復，
7 # 這樣可以與每個數據計算距離
8 sqdiffmat = diffmat**2 #距離的平方
9 sqdistance = sqdiffmat.sum(axis=1) # 行里的所有元素都加起來，1是行，0是列
10 distance = sqdistance**0.5 #距離的平方再開方
11 sorteddisindeces = distance.argsort() #距離進行從小到大的排序，返回的是排序后的索引值
12 classcount = {} #這個是用來記錄取得前k個值后，進行排序的字典， 鍵：距離對應的標簽，值：標簽出現的次數
13 for i in range(k):
14 voteilabel = labels[sorteddisindeces[i]] #鍵 = 標簽（前k個索引值） 鍵=前k個標簽
15 classcount[voteilabel] = classcount.get(voteilabel,0) + 1 # #計算前k個便簽出現的次數，次數就是值
16 sortedclasscount = sorted(classcount.items(),key=operator.itemgetter(1),reverse=True) #key=operator.itemgetter(1)定義函數，獲取對象1值
17 #按照值進行倒序排，元素格式是
18 #{ [標簽，次數],[標簽，次數].......}
19 return sortedclasscount[0][0] #排完值后，將排行老一的也就是最近距離的標簽
20
21 def createDataSet():
22 #四組二維特征
23 group = np.array([[1,101],[5,89],[108,5],[115,8]])
24 #四組特征的標簽
25 labels = ['愛情片','愛情片','動作片','動作片']
26 return group, labels
27
28 if __name__ == '__main__':
29 #創建數據集
30 group, labels = createDataSet()
31 #測試集
32 test = [101,20]
33 #kNN分類
34 test_class = classify0(test, group, labels, 3)
35 #打印分類結果
36 print(test_class)
View Code
使用sklearn運用KNN(鳶尾花數據集)
1 from sklearn import datasets
2 #導入內置的數據集
3 from sklearn.neighbors import KNeighborsClassifier
4 #導入sklearn.neighbors 里的KNN算法模塊
5 import numpy as np
6
7 np.random.seed(0)
8 #設置隨機種子，這樣每次調用隨機模塊時產生的隨機數就是一樣的了
9
10 iris=datasets.load_iris()
11 #導入鳶尾花數據集（data數據,target標簽）
12
13 iris_x=iris.data
14 #獲取樣本數據 type:nadarry
15 #是150*4二維數據，代表150個樣本，
16 # 一共三類花 Iris-Setosa 山鳶尾，Iris-Versicolour 變色鳶尾，Iris-Virginica 維吉尼亞鳶尾
17 # 每類有50個樣本，每個樣本4個屬性分別為花萼和花瓣的長、寬
18
19 iris_y = iris.target
20 #獲取樣本標簽，是150*1的一維數組, type:nadarry
21
22 indices = np.random.permutation(len(iris_x))
23 #permutation接收一個數作為參數(150),產生一個0-149一維數組，只不過是隨機打亂的，當然她也可以接收一個一維數組作為參數，結果是直接對這個數組打亂
24 #函數shuffle與permutation都是對原來的數組進行重新洗牌（即隨機打亂原來的元素順序）；區別在于shuffle直接在原來的數組上進行操作，改變原來數組的順序，無返回值。而permutation不直接在原來的數組上進行操作，而是返回一個新的打亂順序的數組，并不改變原來的數組。
25 #b=np.random.permutation(10) 返回的b是nadarry類型
26
27 iris_x_train = iris_x[indices[:-10]]
28 iris_y_train = iris_y[indices[:-10]]
29 #選取140個數據和標簽作為訓練數據集和訓練數據集的標簽
30
31 iris_x_test = iris_x[indices[-10:]]
32 iris_y_test = iris_y[indices[-10:]]
33 #最后十個作為測試數據集
34
35 knn = KNeighborsClassifier()
36 #定義了一個分類器對象
37 knn.fit(iris_x_train,iris_y_train)
38 #調用knn的訓練方法，主要接受兩個參數：訓練數據集和其樣本標簽
39
40 iris_y_predict = knn.predict(iris_x_test)
41 #調用該對象的測試方法，主要接受一個參數：測試數據集
42
43 probility = knn.predict_proba(iris_x_test)
44 #計算各測試樣本基于概率的預測
45
46 #score = knn.score(iris_x_test,iris_y_test,sample_weight=None)
47 #調用該對象的打分方法，計算出準確率
48
49 print('iris_y_predict=')
50 print(iris_y_predict)
51 #測試結果
52
53 print('iris_y_test=')
54 print(iris_y_test)
55 #真實的測試集的標簽
56
57 #print('accuracy:')
58 #print(score)
59 #正確率
60
61 #print(neighborpoint)
62 #臨點
63 print(probility)
64 #概率預測
View Code
第一步：定義分類器對象
knn = KNeighborClassifier()
第二步：訓練樣本
knn.fit(x_train,y_train)
第三步：測試數據集
y_predict = knn.predict(x_test)
第四步：顯示預測概率，顯示測試數據集標簽，顯示預測數據集標簽
probility = knn.predict_proba(x_test)
y_test
y_predict
方法解讀：
np.tile（A,B）
1 >>> import numpy 2 >>> numpy.tile([0,0],5) #在列方向上重復[0,0]5次，默認行1次 3 array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) 4 5 >>> numpy.tile([0,0],(1,3)) #行方向上重復1次，列方向上重復3次 6 array([[0, 0, 0, 0, 0, 0]])
sum()函數
1 #0：壓縮為一行，每列的元素全都加起來 2 第一維的元素，相應位置加起來 3 >>> np.sum([[0, 1], [0, 5]], axis=0) 4 array([0, 6]) 5 6 #1：壓縮為一列，每一行的元素都加起來 7 第二維的元素加起來 8 >>> np.sum([[0, 1], [0, 5]], axis=1) 9 array([1, 5])
argsort函數
argsort函數是Numpy模塊中的函數，返回的是數組值從小到大的索引值。
#One dimensional array:一維數組 >>> x = np.array([3, 1, 2]) >>> np.argsort(x) #也可以 x.argsort() array([1, 2, 0]) #Two-dimensional array:二維數組 >>> x = np.array([[0, 3], [2, 2]]) >>> x array([[0, 3], [2, 2]]) >>> np.argsort(x, axis=0) #按列排序 array([[0, 1], [1, 0]]) >>> np.argsort(x, axis=1) #按行排序 array([[0, 1], [0, 1]]) >>> x = np.array([3, 1, 2]) >>> np.argsort(x) #按升序排列 array([1, 2, 0]) >>> np.argsort(-x) #按降序排列 array([0, 2, 1])
字典的get()方法
dict.get(key, default=None)
>>>dict = {'A':1, 'B':2}
>>>print(dict.get('A'))
1
>>>print(dict.get('C'))
None
>>>print(dict.get('A', 0)) #A存在字典中時，返回對應值，不在時返回0
>>>1
>>>print(dict.get('C', 0))
>>>0
operator.itemgetter函數
operator模塊提供的itemgetter函數用于獲取對象的哪些維的數據，參數為一些序號。要注意，operator.itemgetter函數獲取的不是值，而是定義了一個函數，通過該函數作用到對象上才能獲取值。
1 a = [1,2,3] 2 >>> b=operator.itemgetter(1) //定義函數b，獲取對象的第1個域的值 3 >>> b(a) 4 2 5 >>> b=operator.itemgetter(1,0) //定義函數b，獲取對象的第1個域和第0個的值 6 >>> b(a) 7 (2, 1)
sorted函數
Python內置的排序函數sorted可以對list或者iterator進行排序。
sorted(iterable[,cmp[,key[,reverse]]])
（1）iterable指定要排序的list或者iterable
（2）cmp為函數，指定排序時進行比較的函數，可以指定一個函數或者lambda函數，如：
students = [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
sorted(students, key=lambda student : student[2])
（3）key為函數，指定取待排序元素的哪一項進行排序，函數用上面的例子來說明，代碼如下：
sorted(students, key=lambda student : student[2])
例如要通過student的第三個域排序，可以這么寫：
sorted(students, key=operator.itemgetter(2))
sorted函數也可以進行多級排序，例如要根據第二個域和第三個域進行排序，可以這么寫：
sorted(students, key=operator.itemgetter(1,2))
（4）reverse參數就不用多說了，是一個bool變量，默認為false（升序排列），定義為True時將按降序排列。
sklearn方法
KNeighborsClassifier是一個類，它集成了其他的NeighborsBase,KNeighborsMixin,SupervisedIntegerMixin, ClassifierMixin。
__init__()
初始化函數(構造函數) 它主要有一下幾個參數：
n_neighbors=5 int 型參數，knn算法中指定以最近的幾個最近鄰樣本具有投票權，默認參數為5
weights='uniform' str參數，即每個擁有投票權的樣本是按什么比重投票，'uniform'表示等比重投票，'distance'表示按距離反比投票，[callable]表示自己定義的一個函數， 這個函數接收一個距離數組，返回一個權值數組。默認參數為‘uniform’
algrithm='auto' str參數，即內部采用什么算法實現。有以下幾種選擇參數：'ball_tree':球樹、'kd_tree':kd樹、'brute':暴力搜索、'auto':自動根據數據的類型和結構選擇合適的算法。默認情況下是‘auto’。暴力搜索就不用說了大家都知道。具體前兩種樹型數據結構哪種好視情況而定。KD樹是對依次對K維坐標軸，以中值切分構造的樹,每一個節點是一個超矩形，在維數小于20時效率最高--可以參看《統計學習方法》第二章。ball tree 是為了克服KD樹高維失效而發明的，其構造過程是以質心C和半徑r分割樣本空間，每一個節點是一個超球體。一般低維數據用kd_tree速度快，用ball_tree相對較慢。超過20維之后的高維數據用kd_tree效果反而不佳，而ball_tree效果要好，具體構造過程及優劣勢的理論大家有興趣可以去具體學習。
leaf_size=30 int參數，基于以上介紹的算法，此參數給出了kd_tree或者ball_tree葉節點規模，葉節點的不同規模會影響數的構造和搜索速度，同樣會影響儲樹的內存的大小。具體最優規模是多少視情況而定。
matric='minkowski' str或者距離度量對象，即怎樣度量距離。默認是閔氏距離，閔氏距離不是一種具體的距離度量方法，它可以說包括了其他距離度量方式，是其他距離度量的推廣，具體各種距離度量只是參數p的取值不同或者是否去極限的不同情況，具體大家可以參考這里，講的非常詳細。
p=2 int參數 就是以上閔氏距離各種不同的距離參數，默認為2，即歐氏距離。p=1代表曼哈頓距離等等
metric_params=None 距離度量函數的額外關鍵字參數，一般不用管，默認為None
n_jobs=1 int參數 指并行計算的線程數量，默認為1表示一個線程，為-1的話表示為CPU的內核數，也可以指定為其他數量的線程，這里不是很追求速度的話不用管，需要用到的話去看看多線程。
.fit(traindata，trainlabels)
訓練函數，它是最主要的函數。參數：訓練數據集和標簽集，其實該函數并不是KNeighborsClassifier這個類的方法，而是它的父類SupervisedIntegerMixin繼承下來的方法。
.predict(testdata)
預測函數 接收輸入的數組類型測試樣本，一般是二維數組，每一行是一個樣本，每一列是一個屬性返回數組類型的預測結果，如果每個樣本只有一個輸出，則輸出為一個一維數組。如果每個樣本的輸出是多維的，則輸出二維數組，每一行是一個樣本，每一列是一維輸出。
predict_prob(testdata)
基于概率的軟判決，也是預測函數，只是并不是給出某一個樣本的輸出是哪一個值，而是給出該輸出是各種可能值的概率各是多少接收參數和上面一樣返回參數和上面類似，只是上面該是值的地方全部替換成概率，比如說輸出結果又兩種選擇0或者1，上面的預測函數給出的是長為n的一維數組，代表各樣本一次的輸出是0還是1.而如果用概率預測函數的話，返回的是n*2的二維數組，每一行代表一個樣本，每一行有兩個數，分別是該樣本輸出為0的概率為多少，輸出1的概率為多少。而各種可能的順序是按字典順序排列，比如先0后1，或者其他情況等等都是按字典順序排列。
score(testdata，reallabel，weigh)
計算準確率的函數，接受參數有3個。X:接收輸入的數組類型測試樣本，一般是二維數組，每一行是一個樣本，每一列是一個屬性。y:X這些預測樣本的真實標簽，一維數組或者二維數組。sample_weight=None,是一個和X第一位一樣長的各樣本對準確率影響的權重，一般默認為None.輸出為一個float型數，表示準確率。內部計算是按照predict()函數計算的結果記性計算的。其實該函數并不是KNeighborsClassifier這個類的方法，而是它的父類KNeighborsMixin繼承下來的方法。
kneighbors(目標樣本，臨近樣本數量，是否返回距離值)
計算某些測試樣本的最近的幾個近鄰訓練樣本。接收3個參數。X=None：需要尋找最近鄰的目標樣本。n_neighbors=None,表示需要尋找目標樣本最近的幾個最近鄰樣本，默認為None,需要調用時給出。return_distance=True:是否需要同時返回具體的距離值。返回最近鄰的樣本在訓練樣本中的序號。其實該函數并不是KNeighborsClassifier這個類的方法，而是它的父類KNeighborsMixin繼承下來的方法。
sklearn有數據集，需要引入： from sklearn import datasets
總結
以上是生活随笔為你收集整理的k近邻法(k-nearest neighbor, k-NN)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： HTML5 的段落首行缩进
- 下一篇： Musle比对软件（windows）