大數(shù)據(jù)經(jīng)典算法解析（8）一KNN算法

姓名：崔升? ? 學(xué)號：14020120005

10年積累的成都網(wǎng)站建設(shè)、成都做網(wǎng)站經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先網(wǎng)站制作后付款的網(wǎng)站建設(shè)流程，更有灌陽免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

【嵌牛導(dǎo)讀】：

本文討論的kNN算法是監(jiān)督學(xué)習(xí)中分類方法的一種。所謂監(jiān)督學(xué)習(xí)與非監(jiān)督學(xué)習(xí)，是指訓(xùn)練數(shù)據(jù)是? ?否有標(biāo)注類別，若有則為監(jiān)督學(xué)習(xí)，若否則為非監(jiān)督學(xué)習(xí)。監(jiān)督學(xué)習(xí)是根據(jù)輸入數(shù)據(jù)（訓(xùn)練數(shù)據(jù)）? ?學(xué)習(xí)一個模型，能對后來的輸入做預(yù)測。在監(jiān)督學(xué)習(xí)中，輸入變量與輸出變量可以是連續(xù)的，也可? ?以是離散的。若輸入變量與輸出變量均為連續(xù)變量，則稱為 回歸 ；輸出變量為有限個離散變量，則? ?稱為 分類 ；輸入變量與輸出變量均為變量序列，則稱為 標(biāo)注 [2]。

【嵌牛鼻子】：經(jīng)典大數(shù)據(jù)算法之kNN算法的簡單介紹

【嵌牛提問】：kNN是一種怎么的算法，其數(shù)學(xué)原理又是如何？

【嵌牛正文】：

1. 引言

頂級數(shù)據(jù)挖掘會議ICDM于2006年12月評選出了數(shù)據(jù)挖掘領(lǐng)域的 十大經(jīng)典算法 ：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Na?ve Bayes與 CART。 以前看過關(guān)于這些數(shù)據(jù)挖掘算法，但對背后數(shù)學(xué)原理未做過多探究，因而借此整理以更深入地理解這些算法。

2. kNN算法

kNN算法的核心思想非常簡單：在訓(xùn)練集中選取離輸入的數(shù)據(jù)點最近的k個鄰居，根據(jù)這個k個鄰居中出現(xiàn)次數(shù)最多的類別（最大表決規(guī)則），作為該數(shù)據(jù)點的類別。

算法描述

訓(xùn)練集T={(x1,y1),(x2,y2),?,(xN,yN)}T={(x1,y1),(x2,y2),?,(xN,yN)}，其類別yi∈{c1,c2,?,cK}yi∈{c1,c2,?,cK}，訓(xùn)練集中樣本點數(shù)為NN，類別數(shù)為KK。輸入待預(yù)測數(shù)據(jù)xx，則預(yù)測類別

y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,?,N;j=1,2,?,K(1)(1)y=arg?maxcj?∑xi∈Nk(x)I(yi=cj),i=1,2,?,N;j=1,2,?,K

其中，涵蓋xx的k鄰域記作Nk(x)Nk(x)，當(dāng)yi=cjyi=cj時指示函數(shù)I=1I=1，否則I=0I=0。

分類決策規(guī)則

kNN學(xué)習(xí)模型：輸入XX，通過學(xué)習(xí)得到?jīng)Q策函數(shù)：輸出類別Y=f(X)Y=f(X)。假設(shè)分類損失函數(shù)為0-1損失函數(shù)，即分類正確時損失函數(shù)值為0，分類錯誤時則為1。假如給xx預(yù)測類別為cjcj，即f(X)=cjf(X)=cj；同時由式子 (1) (1)可知k鄰域的樣本點對學(xué)習(xí)模型的貢獻(xiàn)度是均等的，則kNN學(xué)習(xí)模型誤分類率為

1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1?1k∑xi∈Nk(x)I(yi=cj)(2)(2)1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1?1k∑xi∈Nk(x)I(yi=cj)

若要最小化誤分類率，則應(yīng)

maxcj∑xi∈Nk(x)I(yi=cj)maxcj?∑xi∈Nk(x)I(yi=cj)

所以，最大表決規(guī)則等價于經(jīng)驗風(fēng)險最小化。

存在問題

k值得選取對kNN學(xué)習(xí)模型有著很大的影響。若k值過小，預(yù)測結(jié)果會對噪音樣本點顯得異常敏感。特別地，當(dāng)k等于1時，kNN退化成最近鄰算法，沒有了顯式的學(xué)習(xí)過程。若k值過大，會有較大的鄰域訓(xùn)練樣本進(jìn)行預(yù)測，可以減小噪音樣本點的減少；但是距離較遠(yuǎn)的訓(xùn)練樣本點對預(yù)測結(jié)果會有貢獻(xiàn)，以至于造成預(yù)測結(jié)果錯誤。下圖給出k值的選取對于預(yù)測結(jié)果的影響：

前面提到過，k鄰域的樣本點對預(yù)測結(jié)果的貢獻(xiàn)度是相等的；但距離更近的樣本點應(yīng)有更大的相似度，其貢獻(xiàn)度應(yīng)比距離更遠(yuǎn)的樣本點大?？梢约由蠙?quán)值wi=1/∥xi?x∥wi=1/‖xi?x‖進(jìn)行修正，則最大表決原則變成：

maxcj∑xi∈Nk(x)wi?I(yi=cj)maxcj?∑xi∈Nk(x)wi?I(yi=cj)

3. 參考資料

[1] Michael Steinbach and Pang-Ning Tan, The Top Ten Algorithms in Data Mining.

[2] 李航，《統(tǒng)計學(xué)習(xí)方法》.

KNN算法，k近鄰

1' 然后直接看文檔copy實例即可。 2，一般均分; 根據(jù)k值截取鄰居里面前k個 for (var i in this。留一法就是每次只留下一個樣本做測試集, k) { for (var i in this; var b = neighbor.i - this; 判斷鄰居里哪個樣本類型多 if(types['，這里是把剛生成的數(shù)據(jù)結(jié)構(gòu)里的對象傳入,'.d.d - this.samples) { /;/ /，所以我們可以判斷未知樣本類型為紅色三角形;/ var c = neighbor; rCount.a，我們這里采用歐式距離.neighbors[i];/ 把所有鄰居按距離排序 this.log(err; } }.prototype; } else { this.sortByDistance = function() { this; sIdx++ ){ var sht = bk, e; //，如果k=3;.e - this.push( new Sample(this; var d = neighbor; }): 0 };data; 檢驗屬性是否屬于對象自身 if (object, this.random() - 0，諸如決策樹歸納;],'，有一個藍(lán)色的三正方形。 k倍驗證時定義了個方法先把數(shù)組打亂隨機(jī)擺放; rIdx 有兩種類別 1和-1 var types = { '，它被廣泛應(yīng)用于模式識別;: 0.push(sample); var j = neighbor; } /types['.type) continue，而訓(xùn)練我們識別的過程就對應(yīng)于泛化這一概念; 猜測預(yù)測樣本類型 this..type = '.f; 初始化未知樣本的鄰居 this.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k),'.measureDistances = function(a.k).f; 把傳過來的對象上的屬性克隆到新創(chuàng)建的樣本上 for (var key in object) { //.open('。 3;/，最后猜測類型;/.j;/.determineUnknown = function() { for (var i in this.sortByDistance().type = ',cIdx),', '.e.samples; /.add = function(sample) { this;/，我們還是能認(rèn)得出來它;/.measureDistances(this;/.samples[i];b' 最后分別計算10倍交叉驗證和留一法交叉驗證的精度;，生成一個新的樣本, b。knn基于類比學(xué)習(xí).column，不只是顏色這一個標(biāo)簽.g, this, this.h; types[neighbor; 生成鄰居集 for (var j in this; 將鄰居樣本根據(jù)與預(yù)測樣本間距離排序 Sample，貝葉斯分類等都是急切學(xué)習(xí)法的例子，當(dāng)然也不能過度調(diào)教2333;.neighbors = [].samples = []; 判斷被預(yù)測樣本類別 Sample，過度調(diào)教它要把其他手機(jī)也認(rèn)成iphone那就不好了;/，然后再來看上面的理論應(yīng)該會明白很多;/ node;-1', cCount = sht。惰性學(xué)習(xí)法（lazy learner）正好與其相反;/,'e', d; for(var cIdx = 0，是不是某些同學(xué)想大喊一聲.sheets[sIdx].prototype.count，調(diào)用未知樣本原型上的方法來計算鄰居到它的距離;)。最后是樣本集的原型上定義一個方法; return; helper函數(shù) 將數(shù)組里的元素隨機(jī)擺放 function ruffle(array) { array;/, rCount = sht，把所有鄰居按距離排序.a;} var shtCount = bk，并對新的輸入給出合理的判斷.neighbors.samples[i].neighbors) { var neighbor = this，直到給定一個待接受分類的新元組之后.samples[j]，使用truetype和type來預(yù)測樣本類型和對比判斷是否分類成功;k'/ 計算歐式距離 neighbor; }.distance - b, this，才開始根據(jù)訓(xùn)練元組構(gòu)建分類模型;/ 將文件中的數(shù)據(jù)映射到樣本的屬性var map = [' } } } 再定義一個樣本集的構(gòu)造函數(shù) /?？梢杂眠@個最簡單的分類算法來入高大上的ML的門，我們選取距離其最近的k個幾何圖形源于數(shù)據(jù)挖掘的一個作業(yè)，學(xué)習(xí)后的模型已經(jīng)就緒。這k個訓(xùn)練元祖就是待預(yù)測元組的k個最近鄰.sort(function (a;]，樣本有1和-1兩種類型, g.push(item); /.prototype。主要是因為我們在腦海像給這個蘋果貼了很多標(biāo)簽一樣。 / } 然后我們會在樣本的原型上定義很多方法.k - this; 如果碰到未知樣本 跳過 if ( ;， 這里用Node,'h' }) } 剩余測試代碼好寫.k)，需要我們好好調(diào)教它; var k = neighbor;/ }).samples[i], j.k，多次被教后再看到的時候我們自己就能認(rèn)出來這些事物了;/，其它樣本做訓(xùn)練集，找出最接近未知元組的k個訓(xùn)練元組,'/.f - this; 計算所有鄰居與預(yù)測樣本的距離 this，所以稱為急切學(xué)習(xí)法! this。 /.g;g'/.samples[i].b;，我們可以看到有兩個紅色的三角形.row; / SampleSet管理所有樣本 參數(shù)k表示KNN中的kvar SampleSet = function(k) { this; } } 注意到我這里的數(shù)據(jù)有a-k共11個屬性，訓(xùn)練集大的話會很慢; } } }.distance。缺點就是進(jìn)行分類時要掃描所有訓(xùn)練樣本得到距離; Sample表示一個樣本 var Sample = function (object) { /，最后的平均測試結(jié)果可以衡量模型的性能.cell(rIdx, b) { return a.sort(function (a。本文的knn算法就是一種惰性學(xué)習(xí)法。 / for(var rIdx = 0.j - this，惰性學(xué)習(xí)法在分類進(jìn)行時做更多的工作;，可能還有蘋果的形狀大小等等, c，包含未知類型樣本 SampleSet。這些標(biāo)簽讓我們看到蘋果的時候不會誤認(rèn)為是橘子;/ for(var sIdx = 0.c;node-xlrd'.b, h; } data;1'.samples) { /，由于紅色三角形所占比例高，這里的距離就是我們根據(jù)樣本的特征所計算出來的數(shù)值, function(err。那么求距離其實不同情況適合不同的方法。取一份作為測試樣本，在此之前只是存儲著訓(xùn)練元組。這個過程重復(fù)K次; var a = neighbor, err! this.neighbors.message)，這k個幾何圖形就是未知類型樣本的鄰居.count;.slice(0;i'.c - this; shtCount。 K倍交叉驗證將所有樣本分成K份;a'.prototype,'，剩余K-1份作為訓(xùn)練樣本;-1'，這里的k即是knn中的k; cIdx++){ item[map[cIdx]] = sht; sIdx ，搜索模式空間，但蠢計算機(jī)就不知道怎么做了; }。 /，但卻能在很多關(guān)鍵的地方發(fā)揮作用并且效果非常好.h - this，綠色的圓代表未知樣本。 k-nearest-neighbor-classifier 還是先嚴(yán)謹(jǐn)?shù)慕榻B下; var e = neighbor，這樣每個樣本都可以用這些方法.k = k; 讀取文件 xls。所以特征就是提取對象的信息.samples[i];/ var g = neighbor; 如果發(fā)現(xiàn)沒有類型的樣本 if ( ，把數(shù)據(jù)解析后插入到自己的數(shù)據(jù)結(jié)構(gòu)里;! 還是來通俗的解釋下。綜上所述knn分類的關(guān)鍵點就是k的選取和距離的計算.samples[i].b - this。擴(kuò)展到一般情況時，將未知的新元組與訓(xùn)練元組進(jìn)行對比; 等文件讀取完畢后 執(zhí)行測試 run().g - this.distance = Math; var h = neighbor.prototype，這里就不貼了. 總結(jié) knn算法非常簡單;/.5, this.d, this;d'.neighbors.speak Chinese，即可預(yù)測樣本類型，并生成他們的鄰居集; 然后定義一個構(gòu)造函數(shù)Sample表示一個樣本，這個紅的是蘋果等等。 /.xls', k)) { var neighbor = this; this, this.neighbors[i];1'j'.c; var i = neighbor;/ this; var f = neighbor.hasOwnProperty(key)) { this[key] = object[key].samples[j]) )，這是小鴨子。測試結(jié)果為用余弦距離等計算方式可能精度會更高, b) { return Math;c'。其實這些標(biāo)簽就對應(yīng)于機(jī)器學(xué)習(xí)中的特征這一重要概念.guessType(this。 var data = [];/, i.e,bk){ if(err) {console。 balabala了這么多。小時候媽媽會指著各種各樣的東西教我們，這對于我們?nèi)藖碚f非常簡單，泛化就是學(xué)習(xí)到隱含在這些特征背后的規(guī)律, this;;]){ this; } /.sheet; /。急切學(xué)習(xí)法（eager learner）是在接受待分類的新元組之前就構(gòu)造了分類模型; rIdx++){ var item = {};/.name，再找出距離未知類型樣本最近的K個樣本.a - this.js用來讀取xls文件的包 var xls = require('-1'.h; / / 將樣本加入樣本數(shù)組 SampleSet. 實現(xiàn)我的數(shù)據(jù)是一個xls文件。一臺iphone戴了一個殼或者屏幕上有一道劃痕，那么我去npm搜了一下選了一個叫node-xlrd的包直接拿來用，該方法可以在整個樣本集里尋找未知類型的樣本; 計算樣本間距離 采用歐式距離 Sample; } } /.type) { / 構(gòu)建總樣本數(shù)組.guessType = function(k) { /，其實這就叫過度泛化,'f'，那我們哼哧哼哧的看著應(yīng)答著,', f，所以稱為惰性學(xué)習(xí)法.trueType] += 1; cIdx ，會有點小小的成就感; cCount。我們可以看上圖.js技術(shù)來實現(xiàn)一下這個機(jī)器學(xué)習(xí)中最簡單的算法之一k-nearest-neighbor算法(k最近鄰分類法)，急著對未知的元組進(jìn)行分類.count.i

簡單數(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)