基于R语言的k-最近邻法数字模式识别研究

钟志强

（鞍山师范学院物理科学与技术学院，辽宁 鞍山 114007）

基于R语言的k-最近邻法数字模式识别研究

钟志强

（鞍山师范学院物理科学与技术学院，辽宁 鞍山 114007）

k-最近邻法是常见的机器学习算法，R语言中通过kknn包完成算法实现,但其无法实现图像文件的处理。为此，本文先将图像文件转换成文本文件，再结合KNN算法对文件中数字图像进行模式识别。实验得出其判断结果达到了预期指标。

k-最近邻法；模式识别；R语言

1．k-最近邻法原理

k-最近邻法(k-nearest neighbor，KNN)是最简单的机器学习算法之一，可以用于分类和回归。KNN认为，待分类对象的类别可以通过在它附近的训练数据的类别来确定，所以采取的策略就是找到离待分类对象最近的K个邻居进行分析[1]。将样本特征空间中的k个最相似的样本中的大多数划属某一个类别。KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此对于类域的交叉或重叠采用较多的待分样本集更为适合。搜索k个近邻算法的伪算法表示为：KNN(A[n]，k)，输入：A[n]为N个训练样本在空间中的坐标，k为近邻数；输出：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]代替最远样本；按照d(x，A[i])升序排序，计算最远样本与x间的距离D=max{d(x，A[j])|j=1，．．．，i}；计算前k个样本A[i])，i=1，2，．．．，k所属类别的概率，具有最大概率的类别即为样本x的类。

2．R语言KNN实现基本实例

R是GNU系统的一个自由、免费、源代码开放的软件，主要用于统计分析与数据可视化。R语言使用起来简洁、直观、灵活，随着大量新兴研究领域算法不断更新，R语言在机器学习领域有广泛的应用。R语言中k-最近邻法常用包是kknn。其使用函数为：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"))其关键参数说明：formula：回归模型，例如：分类变量～特征量；train：训练集，test：测试集；na．action：缺失值处理，默认为去掉缺失值；k：默认为7，通常k＜20；distance：包括euclidean（欧氏距离），minkowski（明科夫斯基距离），Mahalanobi（马氏距离），Bhattacharyya（巴氏距离）；manhattan（曼哈顿距离），canberra（兰式距离），Hamming（汉明距离）等[2]。

现以著名鸢尾花（iris）数据集实现算例：包含五个指标花瓣长度(Petal．Length)、萼片宽度(Sepal.Width)、花瓣宽度(Petal.Width)、萼片长度(Sepal.Length)、三种花类型（Species：setosa，versicolor，virginica）150笔记录。其结果见表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分类结果，模型预测准确性为97%

图1 k-最近邻法iris分类（红色为错误分类）

其结果表征说明kknn算法成功率较高。

3．KNN数字模式识别基本过程

R语言中关于k-最近邻法建模，常用的是kknn包。但其无法针对图像文件进行处理，如：针对图2所示文档0～9内10个数字的识别。为此R语言对数字图像的识别要经过图像的二值化文本和机器模式识别两个过程。

图2 手写图像到图像的二值文本化和模式识别图

3．1 对数字图像二值化处理

R语言对图像的处理十分方便。其资源网站CRAN中有jpeg、png、tiff、bmp、rimage、biOps等多个包，协同机器学习中的包运算，能够完成许多图像模式识别算例[3]。对数字图像二值文本化处理代码如下：

library("jpeg")#加载jpeg包

mypic=readJPEG("d：/tempr/pic0．jpg")#读取数字图像文件

mydim=dim(mypic)

mydata=matrix(nrow=mydim[1]，ncol=mydim[2])#定义矩阵二值变量

for(i in 1：mydim[1]){for(j in 1：mydim[2]){#将图像中的数据赋值给矩阵变量

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)#将矩阵变量写入文档，以便模式识别算法实现。为加快数据读写还可以加入快均值算法，本案例中省略。

3．2 k-最近邻法数字模式识别

参考KNN基本原理、kknn包中k-最近邻法的实现方式和文献[4]，[5]。我们编写了对文档而不是变量进行操作的k-最近邻法如下：

dis＜-function(datatest，datatrain，len){#最近邻距离的计算函数

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){#学习结果的判断函数

index＜-rep(0：9，c(189，198，195，199，186，187，195，201，180，204))#训练集正确判读结果（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")#训练集所在目录

names＜-list．files()#读取所有1934训练文件名

train＜-paste("train"，1：1934，sep="")#预留1934个train变量

for(i in 1：length(names))#将文件内容写入train

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

setwd("D：/tempr/testDigits")#测试集所在目录

names＜-list．files()#读取所有1934训练文件名

test＜-paste("test"，1：1934，sep="")#预留1934个test变量

for(i in 1：length(names))#将文件内容写入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))#测试集正确判读结果（0-9）

error＜-0#计算判断错误次数

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

最终error的计算结果为19误差率为2%，达到可以接受的范围。

4．结语

尽管上述算法基本能够完成手写文字的识别，但KNN分类本身也有不足：一是计算量大，对每一个待分类样本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点，因而适用于小样本数据分类；二是当样本不平衡时一个类的样本容量很大，而其它类样本容量很小时，输入一个新样本时，无法进行判别。其对应改进算法也是我们研究的目标。

[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语言编程艺术[M]．北京：机械工业出版社，2013．

[4]R语言与机器学习笔记[DB/OL]．http：//blog．csdn．net/ yujunbeta/article/details/14648343，2014，5．

[5]Peter Harrington．机器学习实战[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

钟志强,男,辽宁辽阳人,硕士,讲师，研究方向：人工智能教育。