鐘志強

（鞍山師范學(xué)院物理科學(xué)與技術(shù)學(xué)院，遼寧 鞍山 114007）

基于R語言的k-最近鄰法數(shù)字模式識別研究

鐘志強

（鞍山師范學(xué)院物理科學(xué)與技術(shù)學(xué)院，遼寧 鞍山 114007）

k-最近鄰法是常見的機器學(xué)習(xí)算法，R語言中通過kknn包完成算法實現(xiàn),但其無法實現(xiàn)圖像文件的處理。為此，本文先將圖像文件轉(zhuǎn)換成文本文件，再結(jié)合KNN算法對文件中數(shù)字圖像進行模式識別。實驗得出其判斷結(jié)果達(dá)到了預(yù)期指標(biāo)。

k-最近鄰法；模式識別；R語言

1．k-最近鄰法原理

k-最近鄰法(k-nearest neighbor，KNN)是最簡單的機器學(xué)習(xí)算法之一，可以用于分類和回歸。KNN認(rèn)為，待分類對象的類別可以通過在它附近的訓(xùn)練數(shù)據(jù)的類別來確定，所以采取的策略就是找到離待分類對象最近的K個鄰居進行分析[1]。將樣本特征空間中的k個最相似的樣本中的大多數(shù)劃屬某一個類別。KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別。KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。因此對于類域的交叉或重疊采用較多的待分樣本集更為適合。搜索k個近鄰算法的偽算法表示為：KNN(A[n]，k)，輸入：A[n]為N個訓(xùn)練樣本在空間中的坐標(biāo)，k為近鄰數(shù)；輸出：x所屬的類別。取A[1]～A[k]作為x的初始近鄰，for(i=k+1；i＜=n；i++)計算a[i]與x間的距離d(x，A[i])；if (d(x，A[i]))＜D else用A[i]代替最遠(yuǎn)樣本；按照d(x，A[i])升序排序，計算最遠(yuǎn)樣本與x間的距離D=max{d(x，A[j])|j=1，．．．，i}；計算前k個樣本A[i])，i=1，2，．．．，k所屬類別的概率，具有最大概率的類別即為樣本x的類。

2．R語言KNN實現(xiàn)基本實例

R是GNU系統(tǒng)的一個自由、免費、源代碼開放的軟件，主要用于統(tǒng)計分析與數(shù)據(jù)可視化。R語言使用起來簡潔、直觀、靈活，隨著大量新興研究領(lǐng)域算法不斷更新，R語言在機器學(xué)習(xí)領(lǐng)域有廣泛的應(yīng)用。R語言中k-最近鄰法常用包是kknn。其使用函數(shù)為：kknn(formula=formula(train)，train，test，na.action=na.omit()，k=7，distance=2，kernel="optimal"，ykernel=NULL，scale=TRUE，contrasts=c('unordered'="contr．dummy"，ordered="contr．ordinal"))其關(guān)鍵參數(shù)說明：formula：回歸模型，例如：分類變量～特征量；train：訓(xùn)練集，test：測試集；na．a(chǎn)ction：缺失值處理，默認(rèn)為去掉缺失值；k：默認(rèn)為7，通常k＜20；distance：包括euclidean（歐氏距離），minkowski（明科夫斯基距離），Mahalanobi（馬氏距離），Bhattacharyya（巴氏距離）；manhattan（曼哈頓距離），canberra（蘭式距離），Hamming（漢明距離）等[2]。

現(xiàn)以著名鳶尾花（iris）數(shù)據(jù)集實現(xiàn)算例：包含五個指標(biāo)花瓣長度(Petal．Length)、萼片寬度(Sepal.Width)、花瓣寬度(Petal.Width)、萼片長度(Sepal.Length)、三種花類型（Species：setosa，versicolor，virginica）150筆記錄。其結(jié)果見表1和圖1。

data(iris)；m＜-dim(iris)[1]；val＜-sample(1：m，size=round (m/3)，replace=FALSE，prob=rep(1/m，m))；iris．learn＜-iris[-val，]；iris．valid＜-iris[val，]；iris．kknn＜-kknn(Species～．，iris．learn，iris．valid，distance=1，kernel="triangular")；summary (iris．kknn)；fit＜-fitted(iris．kknn)；table(iris．valid$Species，fit)

pcol＜-as．character(as．numeric(iris．valid$Species))；pairs(iris．valid[1：4]，pch=pcol，col=c("green3"，"red")[(iris．valid$Species!=fit)+1])

表1 k-最近鄰法iris分類結(jié)果，模型預(yù)測準(zhǔn)確性為97%

圖1 k-最近鄰法iris分類（紅色為錯誤分類）

其結(jié)果表征說明kknn算法成功率較高。

3．KNN數(shù)字模式識別基本過程

R語言中關(guān)于k-最近鄰法建模，常用的是kknn包。但其無法針對圖像文件進行處理，如：針對圖2所示文檔0～9內(nèi)10個數(shù)字的識別。為此R語言對數(shù)字圖像的識別要經(jīng)過圖像的二值化文本和機器模式識別兩個過程。

圖2 手寫圖像到圖像的二值文本化和模式識別圖

3．1 對數(shù)字圖像二值化處理

R語言對圖像的處理十分方便。其資源網(wǎng)站CRAN中有jpeg、png、tiff、bmp、rimage、biOps等多個包，協(xié)同機器學(xué)習(xí)中的包運算，能夠完成許多圖像模式識別算例[3]。對數(shù)字圖像二值文本化處理代碼如下：

library("jpeg")#加載jpeg包

mypic=readJPEG("d：/tempr/pic0．jpg")#讀取數(shù)字圖像文件

mydim=dim(mypic)

mydata=matrix(nrow=mydim[1]，ncol=mydim[2])#定義矩陣二值變量

for(i in 1：mydim[1]){for(j in 1：mydim[2]){#將圖像中的數(shù)據(jù)賦值給矩陣變量

if(any(mypic[i，j，]＞0)){mydata[i，j]=1}else{mydata[i，j]= 0}}}

write．table(mydata，"d：/tempr/text．txt"，row．names= F，col．names=F)#將矩陣變量寫入文檔，以便模式識別算法實現(xiàn)。為加快數(shù)據(jù)讀寫還可以加入快均值算法，本案例中省略。

3．2 k-最近鄰法數(shù)字模式識別

參考KNN基本原理、kknn包中k-最近鄰法的實現(xiàn)方式和文獻(xiàn)[4]，[5]。我們編寫了對文檔而不是變量進行操作的k-最近鄰法如下：

dis＜-function(datatest，datatrain，len){#最近鄰距離的計算函數(shù)

distance＜-rep(0，len)

for(i in 1：len)

distance[i]＜-sqrt(sum((get(datatest)-get(datatrain[i]))^2))

return((distance))}

judge＜-function(test，data){#學(xué)習(xí)結(jié)果的判斷函數(shù)

index＜-rep(0：9，c(189，198，195，199，186，187，195，201，180，204))#訓(xùn)練集正確判讀結(jié)果（0-9）

di＜-rep(0，length(data))

di[1：length(data)]＜-dis(test，data，length(data))

return(names(which．max(table(index[order(di)[1：5]])))) }

setwd("D：/tempr/trainingDigits")#訓(xùn)練集所在目錄

names＜-list．files()#讀取所有1934訓(xùn)練文件名

train＜-paste("train"，1：1934，sep="")#預(yù)留1934個train變量

for(i in 1：length(names))#將文件內(nèi)容寫入train

train[i]＜-as．matrix(read．fwf(names[i]，widths=rep(1，32)))

setwd("D：/tempr/testDigits")#測試集所在目錄

names＜-list．files()#讀取所有1934訓(xùn)練文件名

test＜-paste("test"，1：1934，sep="")#預(yù)留1934個test變量

for(i in 1：length(names))#將文件內(nèi)容寫入test

test[i]＜-as．matrix(read．fwf(names[i]，widths=rep(1，32)))

index1＜-rep(0：9，c(87，97，92，85，114，108，87，96，91，89))#測試集正確判讀結(jié)果（0-9）

error＜-0#計算判斷錯誤次數(shù)

for(i in 1：946){if(judge(test[i]，train，names)!=index1[i]) er ror＜-error+1}

最終error的計算結(jié)果為19誤差率為2%，達(dá)到可以接受的范圍。

4．結(jié)語

盡管上述算法基本能夠完成手寫文字的識別，但KNN分類本身也有不足：一是計算量大，對每一個待分類樣本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點，因而適用于小樣本數(shù)據(jù)分類；二是當(dāng)樣本不平衡時一個類的樣本容量很大，而其它類樣本容量很小時，輸入一個新樣本時，無法進行判別。其對應(yīng)改進算法也是我們研究的目標(biāo)。

[1]k-最近鄰法[DB/OL]．http：//blog．csdn．net/yujunbeta，2014，5．

[2]從K近鄰算法、距離度量談到KD樹、SIFT+BBF算法[DB/OL]．http：//blog．csdn．net/v_july_v/article/details/8203674，2014，5．

[3]Motloff．R語言編程藝術(shù)[M]．北京：機械工業(yè)出版社，2013．

[4]R語言與機器學(xué)習(xí)筆記[DB/OL]．http：//blog．csdn．net/ yujunbeta/article/details/14648343，2014，5．

[5]Peter Harrington．機器學(xué)習(xí)實戰(zhàn)[M]．北京：人民郵電出版社，2013．

Research on the K-Nearest Neighbor Digital Pattern Recognition Based on R Language

Zhong Zhiqiang
(Anshan Normal University,Anshan 114007,Liaoning)

tract】 k-nearest neighbor is used widely in machine learning.It can be realized with kknn in R language.However,kknn cannot deal with image file.This paper firstly translates image to text,then implements pattern recognition algorithm for the image based on kknn.Result shows that this method can achieve our expectation.

words】 k-nearest neighbor;pattern recognition;R language

鐘志強,男,遼寧遼陽人,碩士,講師，研究方向：人工智能教育。