python 實(shí)例簡(jiǎn)述 k-近鄰算法的基本原理

首先我們一個(gè)樣本集合，也稱為訓(xùn)練樣本集，在訓(xùn)練樣本集中每個(gè)數(shù)據(jù)都存在一個(gè)標(biāo)簽用來(lái)指明該數(shù)據(jù)的所屬分類。在輸入一個(gè)新的未知所屬分類的數(shù)據(jù)后，將新數(shù)據(jù)的所有特征和樣本集中的所有數(shù)據(jù)計(jì)算距離。從樣本集中選擇與新數(shù)據(jù)距離最近的 k 個(gè)樣本，將 k 個(gè)樣本中出現(xiàn)頻次最多的分類作為新數(shù)據(jù)的分類，通常 k 是小于20的，這也是 k 的出處。
k近鄰算法的優(yōu)點(diǎn)：精度高，對(duì)異常值不敏感，無(wú)數(shù)據(jù)輸入假定。
k 近鄰算法的缺點(diǎn)：時(shí)間復(fù)雜度和空間復(fù)雜度高
數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型
簡(jiǎn)單的k 近鄰算法實(shí)現(xiàn)
第一步：使用 python 導(dǎo)入數(shù)據(jù)
from numpy import *
import operator
'''simple kNN test'''
#get test data
def createDataSet():
        group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
        labels=['A','A','B','B']
        return group,labels
作為例子，直接創(chuàng)建數(shù)據(jù)集和標(biāo)簽，實(shí)際應(yīng)用中往往是從文件中讀取數(shù)據(jù)集和標(biāo)簽。array 是 numpy 提供的一種數(shù)據(jù)結(jié)構(gòu)，用以存儲(chǔ)同樣類型的數(shù)據(jù)，除了常規(guī)數(shù)據(jù)類型外，其元素也可以是列表和元組。這里 group 就是元素?cái)?shù)據(jù)類型為 list 的數(shù)據(jù)集。labels 是用列表表示的標(biāo)簽集合。其中 group 和 labels 中的數(shù)據(jù)元素一一對(duì)應(yīng)，比如數(shù)據(jù)點(diǎn)[1.0,1.1]標(biāo)簽是 A，數(shù)據(jù)點(diǎn)[0,0.1]標(biāo)簽是 B。
第二步：實(shí)施 kNN 算法
kNN 算法的自然語(yǔ)言描述如下：
1. 計(jì)算已知類別數(shù)據(jù)集中的所有點(diǎn)與未分類點(diǎn)之間的距離。
2. 將數(shù)據(jù)集中的點(diǎn)按照與未分類點(diǎn)的距離遞增排序。
3. 選出數(shù)據(jù)集中的與未分類點(diǎn)間距離最近的 n 個(gè)點(diǎn)。
4. 統(tǒng)計(jì)這 n 個(gè)點(diǎn)中所屬類別出現(xiàn)的頻次。
5. 返回這 n 個(gè)點(diǎn)中出現(xiàn)頻次最高的那個(gè)類別。
實(shí)現(xiàn)代碼：
def classify0(inX,dataSet,labels,k):
        dataSetSize=dataSet.shape[0]
        diffMat=tile(inX,(dataSetSize,1))-dataSet
        sqDiffMat=diffMat**2
        sqDistances=sqDiffMat.sum(axis=1)
        distances=sqDistances**0.5
        sortedDistIndicies=distances.argsort()
        classCount={}
        for i in range(k):
             voteIlabel=labels[sortedDistIndicies[i]]
             classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
             sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
        return sortedClassCount[0][0]
classify0函數(shù)中的四個(gè)參數(shù)含義分別如下：inX 是希望被分類的數(shù)據(jù)點(diǎn)的屬性向量，dataSet 是訓(xùn)練數(shù)據(jù)集向量，labels 是標(biāo)簽向量，k 是 kNN 算法的參數(shù) k。
接下來(lái)來(lái)看看本函數(shù)的語(yǔ)句都做了那些事。
第一行dataSetSize=dataSet.shape[0]，dataSet 是 array 類型，那么dataSet.shape表示 dataSet 的維度矩陣，dataSet.shape[0]表示第二維的長(zhǎng)度，dataSet.shape[1]表示第一維的長(zhǎng)度。在這里dataSetSize 表示訓(xùn)練數(shù)據(jù)集中有幾條數(shù)據(jù)。
第二行tile(inX,(dataSetSize,1))函數(shù)用以返回一個(gè)將 inX 以矩陣形式重復(fù)(dataSetSize,1)遍的array，這樣產(chǎn)生的矩陣減去訓(xùn)練數(shù)據(jù)集矩陣就獲得了要分類的向量和每一個(gè)數(shù)據(jù)點(diǎn)的屬性差，也就是 diffMat。
第三行**在 python 中代表乘方，那么sqDiffMat也就是屬性差的乘方矩陣。
第四行array 的 sum 函數(shù)若是加入 axis=1的參數(shù)就表示要將矩陣中一行的數(shù)據(jù)相加，這樣，sqDistances的每一個(gè)數(shù)據(jù)就代表輸入向量和訓(xùn)練數(shù)據(jù)點(diǎn)的距離的平方了。
第五行不解釋，得到了輸入向量和訓(xùn)練數(shù)據(jù)點(diǎn)的距離矩陣。
第六行sortedDistIndicies=distances.argsort()，其中 argsort 函數(shù)用以返回排序的索引結(jié)果，直接使用 argsort 默認(rèn)返回第一維的升序排序的索引結(jié)果。
然后創(chuàng)建一個(gè)字典。
接下來(lái)進(jìn)行 k 次循環(huán)，每一次循環(huán)中，找到 i 對(duì)應(yīng)的數(shù)據(jù)的標(biāo)簽，并將其所在字典的值加一，然后對(duì)字典進(jìn)行遞減的按 value 的排序。
這樣循環(huán)完成后，classCount 字典的第一個(gè)值就是kNN 算法的返回結(jié)果了，也就是出現(xiàn)最多次數(shù)的那個(gè)標(biāo)簽。
二維的歐式距離公式如下，很簡(jiǎn)單：

相同的，比如說(shuō)四維歐式距離公式如下：

第三步：測(cè)試分類器
在測(cè)試 kNN 算法結(jié)果的時(shí)候，其實(shí)就是討論分類器性能，至于如何改進(jìn)分類器性能將在后續(xù)學(xué)習(xí)研究中探討，現(xiàn)在，用正確率來(lái)評(píng)估分類器就可以了。完美分類器的正確率為1，最差分類器的正確率為0，由于分類時(shí)類別可能有多種，注意在分類大于2時(shí)，最差分類器是不能直接轉(zhuǎn)化為完美分類器的。