K近鄰(KNN)算法詳解及Python實現(xiàn)

今天瀏覽網(wǎng)頁看到一篇用Python實現(xiàn)K近鄰(KNN)算法的詳解教程佑惠，果斷收藏下來，雖然是五年前的文章，可能有些語法已經(jīng)不適合循狰，但文章語法思路還是可以值得借鑒的咧擂，收藏之后以后慢慢研究逞盆。

KNN依然是一種監(jiān)督學(xué)習(xí)算法

KNN（K Nearest Neighbors,K近鄰 ）算法是機(jī)器學(xué)習(xí)所有算法中理論最簡單，最好理解的松申。KNN是一種基于實例的學(xué)習(xí)云芦，通過計算新數(shù)據(jù)與訓(xùn)練數(shù)據(jù)特征值之間的距離，然后選取 K（K>=1）個距離最近的鄰居進(jìn)行分類判斷（投票法）或者回歸贸桶。如果K=1舅逸，那么新數(shù)據(jù)被簡單分配給其近鄰的類。KNN算法算是監(jiān)督學(xué)習(xí)還是無監(jiān) 督學(xué)習(xí)呢皇筛？首先來看一下監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)的定義琉历。對于監(jiān)督學(xué)習(xí)，數(shù)據(jù)都有明確的label（分類針對離散分布水醋，回歸針對連續(xù)分布）旗笔，根據(jù)機(jī)器學(xué)習(xí)產(chǎn)生 的模型可以將新數(shù)據(jù)分到一個明確的類或得到一個預(yù)測值。對于非監(jiān)督學(xué)習(xí)拄踪，數(shù)據(jù)沒有l(wèi)abel蝇恶，機(jī)器學(xué)習(xí)出的模型是從數(shù)據(jù)中提取出來的pattern（提取 決定性特征或者聚類等）。例如聚類是機(jī)器根據(jù)學(xué)習(xí)得到的模型來判斷新數(shù)據(jù)“更像”哪些原數(shù)據(jù)集合惶桐。KNN算法用于分類時撮弧，每個訓(xùn)練數(shù)據(jù)都有明確的 label，也可以明確的判斷出新數(shù)據(jù)的label姚糊，KNN用于回歸時也會根據(jù)鄰居的值預(yù)測出一個明確的值贿衍，因此KNN屬于監(jiān)督學(xué)習(xí)。

KNN算法的過程為:

• 選擇一種距離計算方式, 通過數(shù)據(jù)所有的特征計算新數(shù)據(jù)與已知類別數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)的距離
• 按照距離遞增次序進(jìn)行排序叛拷，選取與當(dāng)前距離最小的k個點(diǎn)
• 對于離散分類舌厨，返回k個點(diǎn)出現(xiàn)頻率最多的類別作預(yù)測分類；對于回歸則返回k個點(diǎn)的加權(quán)值作為預(yù)測值

KNN算法關(guān)鍵

KNN算法的理論和過程就是那么簡單忿薇，為了使其獲得更好的學(xué)習(xí)效果裙椭，有下面幾個需要注意的地方躏哩。

• 數(shù)據(jù)的所有特征都要做可比較的量化。
  若是數(shù)據(jù)特征中存在非數(shù)值的類型揉燃，必須采取手段將其量化為數(shù)值扫尺。舉個例子，若樣本特征中包含顏色（紅 黑藍(lán)）一項炊汤，顏色之間是沒有距離可言的正驻，可通過將顏色轉(zhuǎn)換為灰度值來實現(xiàn)距離計算。另外抢腐，樣本有多個參數(shù)姑曙，每一個參數(shù)都有自己的定義域和取值范圍，他們對 distance計算的影響也就不一樣迈倍，如取值較大的影響力會蓋過取值較小的參數(shù)伤靠。為了公平，樣本參數(shù)必須做一些scale處理啼染，最簡單的方式就是所有特 征的數(shù)值都采取歸一化處置宴合。
• 需要一個distance函數(shù)以計算兩個樣本之間的距離。
  距離的定義有很多迹鹅，如歐氏距離卦洽、余弦距離、漢明距離斜棚、曼哈頓距離等等阀蒂，關(guān)于相似性度量的方法可參考：機(jī)器學(xué)習(xí)中距離和相似性度量方法 。 一般情況下打肝，選歐氏距離作為距離度量脂新，但是這是只適用于連續(xù)變量挪捕。在文本分類這種非連續(xù)變量情況下粗梭，漢明距離可以用來作為度量。通常情況下级零，如果運(yùn)用一些特殊的算法來計算度量的話，K近鄰分類精度可顯著提高，如運(yùn)用大邊緣最近鄰法或者近鄰成分分析法耗美。
• 確定K的值
  K是一個自定義的常數(shù)盛龄，K的值也直接影響最后的估計，一種選擇K值得方法是使用 cross-validate（交叉驗證）誤差統(tǒng)計選擇法序调。交叉驗證的概念之前提過醉锅，就是數(shù)據(jù)樣本的一部分作為訓(xùn)練樣本，一部分作為測試樣本发绢，比如選擇 95%作為訓(xùn)練樣本硬耍，剩下的用作測試樣本垄琐。通過訓(xùn)練數(shù)據(jù)訓(xùn)練一個機(jī)器學(xué)習(xí)模型，然后利用測試數(shù)據(jù)測試其誤差率经柴。 cross-validate（交叉驗證）誤差統(tǒng)計選擇法就是比較不同K值時的交叉驗證平均誤差率狸窘，選擇誤差率最小的那個K值。例如選擇 K=1,2,3,... 坯认， 對每個K=i做100次交叉驗證翻擒，計算出平均誤差，然后比較牛哺、選出最小的那個陋气。

KNN分類

訓(xùn)練樣本是多維特征空間向量，其中每個訓(xùn)練樣本帶有一個類別標(biāo)簽（喜歡或者不喜歡引润、保留或者刪除）恩伺。分類算法常采用“多數(shù)表決”決定，即k個鄰居中 出現(xiàn)次數(shù)最多的那個類作為預(yù)測類椰拒【“多數(shù)表決”分類的一個缺點(diǎn)是出現(xiàn)頻率較多的樣本將會主導(dǎo)測試點(diǎn)的預(yù)測結(jié)果，那是因為他們比較大可能出現(xiàn)在測試點(diǎn)的K鄰 域而測試點(diǎn)的屬性又是通過K領(lǐng)域內(nèi)的樣本計算出來的燃观。解決這個缺點(diǎn)的方法之一是在進(jìn)行分類時將K個鄰居到測試點(diǎn)的距離考慮進(jìn)去褒脯。例如，若樣本到測試點(diǎn)距離 為d缆毁，則選1/d為該鄰居的權(quán)重（也就是得到了該鄰居所屬類的權(quán)重）番川，接下來統(tǒng)計統(tǒng)計k個鄰居所有類標(biāo)簽的權(quán)重和，值最大的那個就是新數(shù)據(jù)點(diǎn)的預(yù)測類標(biāo) 簽脊框。

舉例颁督，K=5，計算出新數(shù)據(jù)點(diǎn)到最近的五個鄰居的舉例是（1,3,3,4,5）浇雹，五個鄰居的類標(biāo)簽是（yes沉御，no，no昭灵，yes吠裆，no）

若是按照多數(shù)表決法，則新數(shù)據(jù)點(diǎn)類別為no（3個no烂完，2個yes）试疙；若考慮距離權(quán)重類別則為yes（no：2/3+1/5,yes：1+1/4）。

下面的Python程序是采用KNN算法的實例（計算歐氏距離抠蚣，多數(shù)表決法決斷）：一個是采用KNN算法改進(jìn)約會網(wǎng)站配對效果祝旷，另一個是采用KNN算法進(jìn)行手寫識別。

約會網(wǎng)站配對效果改進(jìn)的例子是根據(jù)男子的每年的飛行里程、視頻游戲時間比和每周冰激凌耗量三個特征來判斷其是否是海倫姑娘喜歡的類型（類別為很喜歡怀跛、一般和討厭）奇昙，決策采用多數(shù)表決法。由于三個特征的取值范圍不同敌完，這里采用的scale策略為歸一化储耐。

使用KNN分類器的手寫識別系統(tǒng) 只能識別數(shù)字0到9。需要識別的數(shù)字使用圖形處理軟件滨溉，處理成具有相同的色 彩和大小 ：寬髙是32像素X32像素的黑白圖像什湘。盡管采用文本格式存儲圖像不能有效地利用內(nèi)存空間,為了方便理解，這里已經(jīng)將將圖像轉(zhuǎn)換為文本格式晦攒。訓(xùn)練數(shù)據(jù)中每 個數(shù)字大概有200個樣本闽撤，程序中將圖像樣本格式化處理為向量,即一個把一個32x32的二進(jìn)制圖像矩陣轉(zhuǎn)換為一個1x1024的向量。

from numpy import *
import operator
from os import listdir
import matplotlib
import matplotlib.pyplot as plt
import pdb

def classify0(inX, dataSet, labels, k=3):

#pdb.set_trace()
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() #ascend sorted,
#return the index of unsorted, that is to choose the least 3 item    
classCount={}          
for i in range(k):
    voteIlabel = labels[sortedDistIndicies[i]]
    classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1# a dict with label as key and occurrence number as value
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
'''descend sorted according to value, '''
return sortedClassCount[0][0]

def file2matrix(filename):
fr = open(filename)

#pdb.set_trace()
L = fr.readlines()
numberOfLines = len(L)         #get the number of lines in the file
returnMat = zeros((numberOfLines,3))        #prepare matrix to return
classLabelVector = []                       #prepare labels return       
index = 0
for line in L:
    line = line.strip()
    listFromLine = line.split('\t')
    returnMat[index,:] = listFromLine[0:3]
    classLabelVector.append(int(listFromLine[-1]))
    #classLabelVector.append((listFromLine[-1]))
    index += 1
fr.close()
return returnMat,classLabelVector

def plotscattter():
datingDataMat,datingLabels = file2matrix('datingTestSet2.txt') #load data setfrom file
fig = plt.figure()
ax1 = fig.add_subplot(111)
ax2 = fig.add_subplot(111)
ax3 = fig.add_subplot(111)
ax1.scatter(datingDataMat[:,0],datingDataMat[:,1],15.0array(datingLabels),15.0array(datingLabels))

#ax2.scatter(datingDataMat[:,0],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
#ax2.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
plt.show()

def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m,1))
normDataSet = normDataSet/tile(ranges, (m,1)) #element wise divide
return normDataSet, ranges, minVals

def datingClassTest(hoRatio = 0.20):

#hold out 10%
datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
numTestVecs = int(m*hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
    classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
    print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
    if (classifierResult != datingLabels[i]): errorCount += 1.0
print "the total error rate is: %.2f%%" % (100*errorCount/float(numTestVecs))
print 'testcount is %s, errorCount is %s' %(numTestVecs,errorCount)

def classifyPerson():
'''
input a person , decide like or not, then update the DB
'''
resultlist = ['not at all','little doses','large doses']
percentTats = float(raw_input('input the person' percentage of time playing video games:'))
ffMiles = float(raw_input('flier miles in a year:'))
iceCream = float(raw_input('amount of iceCream consumed per year:'))
datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
normMat, ranges, minVals = autoNorm(datingDataMat)
normPerson = (array([ffMiles,percentTats,iceCream])-minVals)/ranges
result = classify0(normPerson, normMat, datingLabels, 3)
print 'you will probably like this guy in:', resultlist[result -1]

#update the datingTestSet
print 'update dating DB'
tmp = '\t'.join([repr(ffMiles),repr(percentTats),repr(iceCream),repr(result)])+'\n'

with open('datingTestSet2.txt','a') as fr:
    fr.write(tmp)

def img2file(filename):

#vector = zeros(1,1024)
with open(filename) as fr:
    L=fr.readlines()
vector =[int(L[i][j]) for i in range(32) for j in range(32)]
return array(vector,dtype = float)

def handwritingClassTest():
hwLabels = []
trainingFileList = listdir('trainingDigits') #load the training set
m = len(trainingFileList)
trainingMat = zeros((m,1024))
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] #take off .txt
classNumStr = int(fileStr.split('')[0])
hwLabels.append(classNumStr)
trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
testFileList = listdir('testDigits') #iterate through the test set
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0] #take off .txt
classNumStr = int(fileStr.split('')[0])
vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)
if (classifierResult != classNumStr): errorCount += 1.0
print "\nthe total number of errors is: %d" % errorCount
print "\nthe total error rate is: %f" % (errorCount/float(mTest))

if name == 'main':
datingClassTest()

#handwritingClassTest()</pre> <h3>
KNN回歸</h3>

數(shù)據(jù)點(diǎn)的類別標(biāo)簽是連續(xù)值時應(yīng)用KNN算法就是回歸脯颜，與KNN分類算法過程相同哟旗，區(qū)別在于對K個鄰居的處理上。KNN回歸是取K個鄰居類標(biāo)簽值得加
權(quán)作為新數(shù)據(jù)點(diǎn)的預(yù)測值栋操。加權(quán)方法有：K個近鄰的屬性值的平均值（最差）闸餐、1/d為權(quán)重（有效的衡量鄰居的權(quán)重，使較近鄰居的權(quán)重比較遠(yuǎn)鄰居的權(quán)重大）矾芙、
高斯函數(shù)（或者其他適當(dāng)?shù)臏p函數(shù)）計算權(quán)重= gaussian(distance) （距離越遠(yuǎn)得到的值就越小舍沙，加權(quán)得到更為準(zhǔn)確的估計。

總結(jié)

K-近鄰算法是分類數(shù)據(jù)最簡單最有效的算法剔宪，其學(xué)習(xí)基于實例拂铡，使用算法時我們必須有接近實際數(shù)據(jù)的訓(xùn)練樣本數(shù)據(jù)。K-近鄰算法必須保存全部數(shù)據(jù)集葱绒，
如果訓(xùn)練數(shù)據(jù)集的很大感帅，必須使用大量的存儲空間。此外,由于必須對數(shù)據(jù)集中的每個數(shù)據(jù)計算距離值地淀，實際使用時可能非常耗時失球。k-近鄰算法的另一個缺陷是它
無法給出任何數(shù)據(jù)的基礎(chǔ)結(jié)構(gòu)信息，因此我們也無法知曉平均實例樣本和典型實例樣本具有什么特征骚秦。

原文來自：K近鄰(KNN)算法詳解及Python實現(xiàn)
)