我是小蕉萍恕。
今天跟大家分享一下，機器學習中最簡單的算法之一车要，KNN近鄰算法允粤，這是一個有監(jiān)督的分類學習算法。
啥玩意叫有監(jiān)督呢？就是作為訓練的每個樣本都是有標記的类垫，比如樣本1是A類绳姨，樣本2是B類，這樣的有標記的樣本阔挠。而什么叫分類呢？輸出結(jié)果是離散的脑蠕，可窮盡的购撼，就叫分類。
KNN近鄰算法的核心思想是：
近朱者赤谴仙，近墨者黑迂求，選K而取其最大可能。
從哪開始聊呢晃跺？先從算法的核心過程開始吧揩局。
準備基本數(shù)據(jù)集 -> 計算待測試樣本整個數(shù)據(jù)集所有數(shù)據(jù)的距離 -> 根據(jù)距離進行排序 ->獲取前K個樣本，將他們的標簽進行統(tǒng)計 -> 獲取頻次最大的標簽作為結(jié)果輸出
舉個栗子：我想知道我現(xiàn)在最可能處于哪個小區(qū)掀虎，我們假設(shè)小區(qū)都一樣大凌盯。
我得到了一批小區(qū)的GPS定位經(jīng)緯度 -> 我得到了我自己的GPS經(jīng)緯度 -> 計算出我跟所有這些小區(qū)的距離，然后排序一下 ?-> 拿到前K個距離的樣本烹玉，對他們的小區(qū)名稱進行統(tǒng)計 -> bingo驰怎，頻次最大的那個小區(qū)就可能是我的小區(qū)了。
聽起來蠻簡單的二打，但是在實際操作過程中會遇到幾個問題县忌。如果基礎(chǔ)樣本數(shù)太多，該如何計算出所有的距離继效？如果不是空間距離症杏，比如是兩個文本，如何衡量兩個實體之間的距離瑞信？取K個樣本厉颤，那么K取多少對于結(jié)果比較好？
這些是我們作為使用者需要去考慮的事情凡简，模型本身不考慮這個東西走芋。就開放性地把問題拋出來吧，大家都思考思考潘鲫。
用一個識別手寫數(shù)字的例子來分享一下這個算法吧翁逞，代碼自己寫的，但是例子是書上的溉仑，輕噴挖函。首先我們的數(shù)據(jù)長下面這樣子，32*32的1024個像素的圖片浊竟，都是手寫的怨喘。
這是數(shù)字1
這是數(shù)字0
先定義一個函數(shù)津畸，參數(shù)inX是要用來計算的向量，dataSet是測試數(shù)據(jù)集必怜，labels是與dataSet一一對應(yīng)的標簽值肉拓，k是我們想獲取的前k個樣本的數(shù)值。
defclassify0(inX, dataSet, labels, k):
#獲得數(shù)據(jù)集的行數(shù)
dataSetSize = dataSet.shape[0]
#渲染出一個矩陣梳庆，行數(shù)跟dataSet行數(shù)一樣暖途，每一行都是要計算的圖片
diffMat = tile(inX, (dataSetSize,1)) - dataSet
#然后計算出（Xn - Xi）^2 每個維度的坐標的相見的值
#這里使用的是歐拉距離來衡量兩個圖片之間的距離
sqDiffMat = diffMat**2
#每一個值相加，再進行開方膏执，得到N維空間的距離sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances**0.5
#根據(jù)距離進行降序排序驻售，獲取前K個標簽進行頻次統(tǒng)計，然后取最大的那個sortedDistIndicies = distances.argsort()
classCount={}
foriinrange(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) +1
sortedClassCount =sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
returnsortedClassCount[0][0]
嘛更米，核心的分類算法就這樣實現(xiàn)完了欺栗，不難，好好看看應(yīng)該能看懂征峦，最好自己寫一遍迟几。算法的主要思想就是把我們要計算的問題轉(zhuǎn)變成能衡量距離的向量，然后計算向量之間的距離栏笆，用近朱者赤的觀點來進行標簽選擇瘤旨。
下面是一點工具類。這個函數(shù)是將一個文件轉(zhuǎn)變成向量的工具竖伯，因為我們這里是文本所以直接用遍歷的方式存哲，這里比較原始，可以使用numpy等工具來進行矩陣的渲染七婴。
defimg2Vector(fileName):
returnVect = zeros((1,1024))
fr =open(fileName)
foriinrange(32):
lineStr = fr.readline()
forjinrange(32):
returnVect[0,32*i+j] =int(lineStr[j])
returnreturnVect
如果是真正的圖片祟偷，我們可以用img庫來進行轉(zhuǎn)換，轉(zhuǎn)換完的矩陣會有三個通道打厘，RGB修肠，而且每個通道的每個像素都0-255。有幾百萬像素就有幾百萬的像素點户盯。
我們有一堆文本來訓練和測試這個模型嵌施。下面是測試方法，我就不細說了莽鸭。公眾號回復吗伤，"KNN"，所有的東西都下載去玩一玩硫眨，超好玩足淆。我寫完都震驚了一下，原來識別手寫體，最簡單的還能這樣識別巧号，還有這種操作Ｗ迳荨！
defhandWriterClassTest():
hwLabels = []
traningFileList = listdir('trainingDigits')
m =len(traningFileList)
traningMat = zeros((m,1024))
foriinrange(m):
fileNameStr = traningFileList[i]
fileStr = fileNameStr.split('.')[0]
classNumStr =int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
traningMat[i,:] = img2Vector('trainingDigits/%s'% fileNameStr)
testFileList = listdir('testDigits')
errorCount =0.0
mTest =len(testFileList)
foriinrange(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0]
classNumStr =int(fileStr.split('_')[0])
vectorUnderTest= img2Vector('testDigits/%s'% fileNameStr)
classiFierResult = classify0(vectorUnderTest, traningMat, 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 numer of Error is: % d ,the error rate is: %f"% (errorCount,(errorCount/float(mTest)))
測試的結(jié)果準確度大概在98.8%這樣子丹鸿，在這個數(shù)據(jù)集上效果還是不錯的越走，作為一個入門級算法。好了有什么好玩的大家再一次分享吧靠欢。什么你問歐拉距離是什么廊敌？？是他是他就是他掺涛。
好了就醬~各位親，賞了我是看不到是誰的喔疼进，最好留言一下薪缆，我好好好答謝一下。
感謝各位大大日成」悖互舔
