Knn算法原理

如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 看下面這幅圖：

創(chuàng)新互聯(lián)服務(wù)項目包括榮縣網(wǎng)站建設(shè)、榮縣網(wǎng)站制作、榮縣網(wǎng)頁制作以及榮縣網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，榮縣網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到榮縣省份的部分城市，未來相信會繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

KNN的算法過程是是這樣的： 從上圖中我們可以看到，圖中的數(shù)據(jù)集是良好的數(shù)據(jù)，即都打好了label，一類是藍(lán)色的正方形，一類是紅色的三角形，那個綠色的圓形是我們待分類的數(shù)據(jù)。 如果K=3，那么離綠色點最近的有2個紅色三角形和1個藍(lán)色的正方形，這3個點投票，于是綠色的這個待分類點屬于紅色的三角形 如果K=5，那么離綠色點最近的有2個紅色三角形和3個藍(lán)色的正方形，這5個點投票，于是綠色的這個待分類點屬于藍(lán)色的正方形 我們可以看到，KNN本質(zhì)是基于一種數(shù)據(jù)統(tǒng)計的方法！其實很多機(jī)器學(xué)習(xí)算法也是基于數(shù)據(jù)統(tǒng)計的。 KNN是一種memory-based learning，也叫instance-based learning，屬于lazy learning。即它沒有明顯的前期訓(xùn)練過程，而是程序開始運行時，把數(shù)據(jù)集加載到內(nèi)存后，不需要進(jìn)行訓(xùn)練，就可以開始分類了。 具體是每次來一個未知的樣本點，就在附近找K個最近的點進(jìn)行投票。

KNN算法的實現(xiàn)就是取決于，未知樣本和訓(xùn)練樣本的“距離”。我們計算“距離”可以利用歐式距離算法：

求出K個最相近的元組后，用這些元組對應(yīng)的數(shù)值的平均值作為最終結(jié)果。

可以從K=1開始，逐步增加，用檢驗數(shù)據(jù)來分析正確率，從而選擇最優(yōu)K。這個結(jié)果要均衡考慮正確率與計算量，比如K=3時，正確率為90%，而K=10時，正確率為91%，則需要考慮計算量換來的1%提升是否合算了。

（1）如果可能的話先對樣本數(shù)據(jù)進(jìn)行排序，從而知道只需要與哪些數(shù)據(jù)進(jìn)行比較。但對于高維數(shù)據(jù)，這幾乎是不可行的。

（2）將樣本數(shù)據(jù)劃分為多個子集合，待分類數(shù)據(jù)只需要與其中的一個或者多個子集合進(jìn)行比較。比如屬性是經(jīng)緯度，距離是2個經(jīng)緯度點之間的距離，則可以將樣本根據(jù)經(jīng)緯度的整數(shù)部分將各個樣本分到不同的子集合去，待分類元組只需要跟與自己整數(shù)部分相同的子集合進(jìn)行比較即可，當(dāng)子集合內(nèi)的樣本數(shù)據(jù)不足K時，再和鄰近的集合進(jìn)行比較。

（1）理論成熟，思想簡單，既可以用來做分類又可以做回歸

（2）可以用于非線性分類

（3）訓(xùn)練時間復(fù)雜度比支持向量機(jī)之類的算法低

（4）和樸素貝葉斯之類的算法比，對數(shù)據(jù)沒有假設(shè)，準(zhǔn)確度高，對異常點不敏感

（5）由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬的類別，因此對于類域的交叉或重疊較多的待分類樣本集來說，KNN方法較其他方法更為適合

（6）該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量比較小的類域采用這種算法比較容易產(chǎn)生誤分類情況

（1）計算量大，尤其是特征數(shù)非常多的時候

（2）樣本不平衡的時候，對稀有類別的預(yù)測準(zhǔn)確率低

（3）KD樹，球樹之類的模型建立需要大量的內(nèi)存

（4）是慵懶散學(xué)習(xí)方法，基本上不學(xué)習(xí)，導(dǎo)致預(yù)測時速度比起邏輯回歸之類的算法慢

（5）相比決策樹模型，KNN模型的可解釋性不強(qiáng)

注：圖片來源于：

怎樣在spark里跑java版的knn算法

將KNN算法調(diào)用Spark的api進(jìn)行重寫。然后就可以在sparkshell里運行了

簡單數(shù)字識別(knn算法)

knn算法，即k-NearestNeighbor，后面的nn意思是最近鄰的意思，前面的k是前k個的意思，就是找到前k個離得最近的元素

離得最近這個詞具體實現(xiàn)有很多種，我使用的是歐式幾何中的距離公式

二維中兩點x(x1,y1),y(x2,y2)間距離公式為sqrt( (x1-x2)^2+(y1-y2)^2 )

推廣到n維就是

x(x1,x2, … ,xn),y(y1,y2, … ,yn)

sqrt [ ∑( x[i] - y[i] )^2 ] (i=1,2, … ,n)

knn算法是要計算距離的，也就是數(shù)字之間的運算，而圖像是png，jpg這種格式，并不是數(shù)字也不能直接參與運算，所以我們需要進(jìn)行一下轉(zhuǎn)換

如圖所示一個數(shù)字8，首先要確定的是這一步我做的是一個最簡單的轉(zhuǎn)換，因為我假定背景和圖之間是沒有雜物的，而且整個圖只有一個數(shù)字（0-9）如果遇到其他情況，比如背景色不純或者有其他干擾圖像需要重新設(shè)計轉(zhuǎn)換函數(shù)

接下來就是最簡單的轉(zhuǎn)換，將圖片白色部分（背景）變0，有圖像的部分變1。轉(zhuǎn)換后的大小要合適，太小會影響識別準(zhǔn)確度，太大會增加計算量。所以我用的是書上的32*32，轉(zhuǎn)換后結(jié)果如圖所示

這樣一來，圖片就變成了能進(jìn)行計算的數(shù)字了。

接下來我們需要創(chuàng)建一個庫，這個庫里面存著0-9這些數(shù)字的各種類似上圖的實例。因為我們待識別的圖像要進(jìn)行對比，選出前k個最近的，比較的對象就是我們的庫。假定庫中有0-9十個數(shù)字，每個數(shù)字各有100個這種由0和1表示的實例，那么我們就有了一共1000個實例。

最后一步就是進(jìn)行對比，利用開頭說的歐式幾何距離計算公式，首先這個32*32的方陣要轉(zhuǎn)換成一個1*1024的1024維坐標(biāo)表示，然后拿這個待識別的圖像和庫中的1000個實例進(jìn)行距離計算，選出前k個距離最近的。比如50個，這50個里面出現(xiàn)次數(shù)最多的數(shù)字除以50就是結(jié)果數(shù)字的概率。比如50個里面數(shù)字8出現(xiàn)40次，那么待識別數(shù)字是8的可能性就是40/50 = 80%

個人理解：

只能識別單個數(shù)字，背景不能有干擾。如果想多數(shù)字識別或者背景有干擾需要針對具體情況考慮具體的圖像轉(zhuǎn)01的方法。

數(shù)字識別非常依賴庫中的圖像，庫中的圖像的樣子嚴(yán)重影響圖像的識別（因為我們是和庫中的一一對比找出距離最近的前k個），所以數(shù)字的粗細(xì)，高低，胖瘦等待都是決定性因素，建庫時一定全面考慮數(shù)字的可能樣子

計算量比較大，待識別圖像要和庫中所有實例一一計算，如果使用32*32，就已經(jīng)是1024維了。如果庫中有1000個，那就是1024維向量之間的1000次計算，圖像更清晰，庫更豐富只會使計算量更大

對于其他可以直接計算距離的數(shù)值型問題，可以用歐式距離，也可以用其他能代表距離的計算公式，對于非數(shù)值型的問題需要進(jìn)行合適的轉(zhuǎn)換，轉(zhuǎn)換方式很重要，我覺得首先信息不能丟失，其次要精確不能模糊，要實現(xiàn)圖片轉(zhuǎn)換前后是一對一的關(guān)系

參考資料：機(jī)器學(xué)習(xí)實戰(zhàn) [美] Peter Harrington 人民郵電出版社

python源碼

import numpy

import os

from PIL import Image

import heapq

from collections import Counter

def pictureconvert(filename1,filename2,size=(32,32)):

#filename1待識別圖像，filename2 待識別圖像轉(zhuǎn)換為01txt文件輸出，size圖像大小，默認(rèn)32*32

image_file = Image.open(filename1)

image_file = image_file.resize(size)

width,height = image_file.size

f1 = open(filename1,'r')

f2 = open(filename2,'w')

for i in range(height):

? ? for j in range(width):

? ? ? ? pixel = image_file.getpixel((j,i))

? ? ? ? pixel = pixel[0] + pixel[1] + pixel[2]

? ? ? ? if(pixel == 0):

? ? ? ? ? ? pixel = 0

? ? ? ? elif(pixel != 765 and pixel != 0):

? ? ? ? ? ? pixel = 1

? ? ? ? # 0代表黑色（無圖像），255代表白色（有圖像）

? ? ? ? # 0/255 = 0,255/255 = 1

? ? ? ? f2.write(str(pixel))

? ? ? ? if(j == width-1):

? ? ? ? ? ? f2.write('\n')

f1.close()

f2.close()

def imgvector(filename):

#filename將待識別圖像的01txt文件轉(zhuǎn)換為向量

vector = numpy.zeros((1,1024),numpy.int)

with open(filename) as f:

? ? for i in range(0,32):

? ? ? ? linestr = f.readline()

? ? ? ? for j in range(0,32):

? ? ? ? ? ? vector[0,32*i+j] = int(linestr[j])

return? vector

def compare(filename1,filename2):

#compare直接讀取資源庫識別

#filename1資源庫目錄，filename2 待識別圖像01txt文檔路徑

trainingfilelist = os.listdir(filename1)

m = len(trainingfilelist)

labelvector = []

trainingmatrix = numpy.zeros((m, 1024), numpy.int8)

for i in range(0,m):

? ? filenamestr = trainingfilelist[i]

? ? filestr = filenamestr.split('.')[0]

? ? classnumber = int(filestr.split('_')[0])

? ? labelvector.append(classnumber)

? ? trainingmatrix[i,:] = imgvector(filename1 + '/' + filenamestr)

textvector = imgvector(filename2)

resultdistance = numpy.zeros((1,m))

result = []

for i in range(0,m):

? ? resultdistance[0,i] = numpy.vdot(textvector[0],trainingmatrix[i])

resultindices = heapq.nlargest(50,range(0,len(resultdistance[0])),resultdistance[0].take)

for i in resultindices:

? ? result.append(labelvector[i])

number = Counter(result).most_common(1)

print('此數(shù)字是',number[0][0],'的可能性是','%.2f%%' % ((number[0][1]/len(result))*100))

def distinguish(filename1,filename2,filename3,size=(32,32)):

# filename1 png，jpg等格式原始圖像路徑，filename2 原始圖像轉(zhuǎn)換成01txt文件路徑，filename3 資源庫路徑

pictureconvert(filename1,filename2,size)

compare(filename3,filename2)

url1 = "/Users/wang/Desktop/number.png"

url2 = "/Users/wang/Desktop/number.txt"

traininglibrary = "/Users/wang/Documents/trainingDigits"

distinguish(url1,url2,traininglibrary)

當(dāng)前名稱：knn算法java源代碼 knn算法c++實現(xiàn)
網(wǎng)頁網(wǎng)址：http://www.yijiale78.com/article30/ddocspo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、商城網(wǎng)站、標(biāo)簽優(yōu)化、網(wǎng)站策劃、企業(yè)建站、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)