基于ReliefF特征加权和KNN的自然图像分类方法

党宏社，白 梅，张 娜

(陕西科技大学 电气与信息工程学院，陕西 西安 710021)

基于ReliefF特征加权和KNN的自然图像分类方法

党宏社，白 梅，张 娜

(陕西科技大学 电气与信息工程学院，陕西 西安 710021)

为了对自然图像有效准确地分类，提出了一种对图像低层特征和KNN分类算法中的近邻样本分别进行加权的分类方法。针对不同类别图像的视觉特征的差异，通过ReliefF算法计算训练集中每个类别的特征权值，利用此权值来改进待测图像与训练集中图像的距离度量；按照不同近邻到待测样本的距离远近，为不同近邻赋予权值来改进KNN算法在类别决策上的不足。实验结果表明该方法较传统KNN和特征加权KNN方法，准确性提高且对不同K值具有良好的鲁棒性。

自然图像；ReliefF；特征加权；KNN；距离加权

随着互联网技术的快速发展，人们每天获取的图像资源也在快速增长。据不完全统计Facebook网站每天新增3亿张图像，互联网如何快速地对海量的图像资源进行处理是迫切需要解决的问题，对图像进行有效分类是其中重要的一步。

基于图像内容的分类方法通过提取图像所包含的视觉信息从而建立不同特征与图像类别之间的关系实现分类。通过提取图像的显著图表征图像特征信息，利用视觉注意机制，选择显著目标[1]进而实现分类，这种方法符合人类的生物认知能力，但是过度依赖前景目标的检测[2]。文献[3-4]使用图像低层的混合特征，即认为每个特征对于分类的权重是相同的。在进行实际分类的样本中，有的特征对某个类别的贡献可能大于对另一个类别的贡献，因此，在对这样的样本进行分类时，可根据不同样本对不同类别的贡献程度的大小，给图像不同特征赋予不同的权重。ReliefF算法在进行特征评估时，对数据类型没有限制，效率高，在解决多类数据分类特征选择的问题中取得了较好的效果[5-6]。

KNN分类算法是数据挖掘和机器学习领域应用最为广泛的算法之一。算法的基本思想是统计测试样本的K个近邻中多数样本的类别来决策该样本的所属类别[7]。K值大小的选取在很大程度上影响了分类效果，Gora等人[8]依照寻优的思想提出了一种自动选择最优K值的方法，取得了良好的分类效果。理论上来说，K值越大越好，但是随着K值的增大，近邻样本与测试样本距离越近才对分类更有意义。文献[9-10]也分别通过对距离进行加权来改进这一问题的不足。

本文方法在图像分类过程中，首先提取图像的颜色矩特征和灰度共生矩阵，利用ReliefF算法评估不同类别图像特征的重要程度，计算每个类别的特征权重，用加权特征来学习KNN分类模型；在选取K个近邻时，按照距离越近对分类贡献越大的原则，对不同的近邻赋予不同权重，使得KNN分类算法对K值的选取具有良好的鲁棒性。

1 基于ReliefF算法的特征加权

1.1 ReliefF算法简介

Relief算法是一种根据样本特征对近距离样本的区分能力来评估该特征重要程度的权重选择算法，最早由Kira提出。Relief算法简单，运行效率高，但是只能用于处理两类数据的分类问题[11]。因此后来出现了拓展的ReliefF算法和RRelieF算法，统称为Relief系列算法。其中RReliefF算法用来解决目标属性为连续值的回归问题，而本文中用到的ReliefF算法主要针对多类数据分类问题，即对样本集中的所有特征进行评估，给每一个特征赋予一定的权重。算法首先从训练集中随机选择一个样本R，然后从与R同类样本中找出q个近邻样本H，从与不同类样本中找出q个近邻样本M。对于样本R中的某维特征rk，如果R与同类样本的距离diff(rk,R,H)小于与不同类别样本的距离diff(rk,R,M)，说明特征rk对区分类别是有益的，则给予该特征较大的权重；反之如果R与不同类别样本的距离diff(rk,R,M)大于与同类样本的距离diff(rk,R,H)，则说明特征rk对分类有着消极的作用，赋之较小的权重。

1.2 特征权重的计算

本文中自然图像的特征通过颜色和纹理来表征。颜色矩利用线性代数中矩的概念，即图像中任何的颜色分布都可以用矩来表示。颜色分布主要集中在低阶矩中，将图像中的颜色分布用颜色一阶矩平均值(Average)、颜色二阶矩方差(Variance)和颜色三阶矩偏斜度(Skewness)来表示。利用颜色矩对图像进行描述，无需量化图像特征，由于每个像素具有颜色空间的三个颜色通道，因此总共用9个分量来描述一幅图像的颜色矩。图像纹理特征反映了图像区域内重复出现的结构变化及其灰度或色彩的排列规律，是图像的全局统计特征。基于Gabor滤波器的纹理特征提取方法利用Gabor小波多方向与多尺度的特点，提取相关纹理信息，但是算法处理过程中

计算数据量大。本文采用灰度共生矩阵反映不同图像在方向、间隔、变化幅度及快慢上的差异。选取corel图片库中的10个类别的500幅自然图像(每个类别选取50幅)分别提取每幅图像在0，π/4，π/2，3π/4方向上的4个特征参数(惯性矩、相关性、能量和均匀性)，共16个纹理特征属性。

通过颜色和纹理特征提取算法获取训练样本中每幅图像的特征向量R(r1,r2,…,r25)，为防止大数据淹没小数据，按照式(1)作归一化处理

(1)

对于某一类别，随机选择其中的一个样本，计算该样本与所有样本的距离，对所有距离值进行排序得到同类别中的q个近邻样本以及与之不同类别中的近邻样本，由此根据reliefF算法计算样本与样本之间的差异并按照式(2)更新该类别每个特征的权重。重复进行m次，得到每个类别中每个特征的权重，m和q是人为设定的参数。

(2)

式中：diff(A,R1,R2)表示2个样本R1和R2在特征A的差异，Hj表示同类样本中第j个样本，Mj(C)表示与R不同类别C中的第j个近邻样本。其中

(3)

图1是将权重训练主程序运行20次得到的每个类别属性权重大小的结果，由图中可以看出20次的结果趋势相同，将结果汇总统计求得每个类别图像特征属性权重的平均值得到表1，其中行为10个类别编号，列为每个类别的25个特征属性的权值，属性权重越大，说明该属性区分类别的贡献越大，即该类别图像与其他类别图像的差异最先表现在该属性上。

图1 各类别图像的特征属性权重训练结果

属性编号Africabeachbuildingbusdinosaurelephantflowerhorsejokulfood1042790549204328039680638804077008580573006607041802048010457004115043240696704469011380572404652050563052810629206111053690825604984014750703906848059664002190026700243002760026000201001010024300264001925002360032700265002670030000215000610025300285002236002240025700369003030023400221000490031600271002447000800009700081000770011300107000170008900073000818001030117500098001010014901113000130015300092000889000840007800110000760014600084000140009600088000611002662031640224502710032720313500015030770301802640110646006167072840783008817069150901206149065970594812006240063700609006250303900615008410059300658006071306013056260653206900087990620708622056290601505477140361404056028950242803984032050031702872046720346615063100603907179077270855406788088700605606450058711600547005680054300557029970055400758005300059100546170579505440063200675008760060220840205478057630533818028500262602446018840386002343001850245002867032521906447061750726807870085820692108979062060660805925200060100614005960061603013006020082900591006490059321059220562706480069520878506211085930567905994054632203965041310299202638047910322200380030610475103426230631406041071830774208463067980886406058064590586924005490067000546005590298900555007560053300594005462505800054500633306762087410603508407054770577905346

2 基于特征和距离加权的KNN图像分类算法

2.1 KNN算法

KNN是一种理论成熟的分类算法，最早由Cover和Hart于1968年提出。算法的主要思想是：计算待测样本与已知类别的训练样本的欧氏距离，寻找距离该待测样本最近的K个邻居，K个已知类别样本中，多数样本所属的类别即为待测样本的类别。假设待测样本为Xi=(x1,x2,…,xn)，训练集中样本为Rj=(r1,r2,…,rn)。则二者之间的欧氏距离为

(4)

式中：xk，rk为待测样本和训练样本的特征属性；n为样本特征属性的个数。

2.2 基于特征和距离加权的KNN图像分类

本文采用ReliefF算法对训练集中各类别图像进行特征加权，在分类决策的时候使用距离平方的倒数对各个近邻样本进行加权。假设训练集L={(class,Rj),class=1,2,…,c;j=1,2,…,l}，共有l个训练样本，所属c个类别，且类别标签class已知。训练样本Rj=(r1,r2,…,rn)，每个样本有n个特征属性。待测样本Xi=(x1,x2,…,xn)，求所属类别class。本文分类算法具体步骤设计如下：

2)用ReliefF算法训练得到的权值进行特征加权后，待测样本与训练样本的距离为

(5)

式中：λk代表第k个特征属性的权值大小。

3)计算待测样本与所有训练样本的距离值，找出距离该待测样本最近的K个训练样本作为新的训练集，则待测样本与K个近邻样本的距离依次为dc1,dc2,…,dcK。

5)对每个近邻样本进行距离加权之后，则判别函数g定义为

(6)

式中：k_label为近邻样本的类别标签。

(7)

对所有的待测样本求判别函数g，则最大的g对应的class值为待测样本的类别标签，即

class=argmaxg(class,Xi)

(8)

3 仿真及实验结果分析

为了验证该算法的有效性，本文选取corel图片库中 1 000 幅自然图像来做实验，该1 000幅图像总共分为10个类别，每个类别100幅。实验中分别标记为Africa(非洲)、beach(海滩)、building(建筑)、bus(公共汽车)、dinosaur(恐龙)、elephant(大象)、flower(花朵)、horse(骏马)、jokul(雪山)、food(食物)共10个标签。选择其中的500幅作为训练样本，剩下的作为测试数据验证本文算法的有效性。

在MATLAB环境下，提取训练集中每幅图像的9维颜色特征和16维纹理特征，根据ReliefF算法训练得到每个类别中每个属性的权值大小(表1数据)。利用得到的属性权重训练KNN分类算法，计算特征加权后的待测样本与训练样本之间的距离，寻找K个近邻样本，判断K个近邻样本对分类的贡献程度，最终判定待测样本所属的类别。图2～图4是当K取10、20和30时，用标准KNN算法、ReliefF特征加权的KNN方法和同时使用特征加权和距离加权对500幅测试图像进行分类的结果。

图2 K=10时3种方法分类准确率

图3 K=20时3种方法分类准确率

图4 K=30时3种方法分类准确率

由图2～图4的仿真结果可以看出，随着K值取值的不同，KNN分类算法分类准确率波动起伏较大。dinosaur(恐龙)和flower(花朵)两个类别由于图像特征鲜明，所以仅采用标准KNN算法就可以将其准确分开，充分说明在分类过程中，不同图像类别内容对分类的重要性。对于其他类别图像用ReliefF算法对KNN分类算法进行特征加权后，增加了各自类别对特征区分能力，分类准确率有了一定的提高；在此基础上再对近邻样本进行距离加权，分类准确率相对于特征加权KNN又有了提高，同时对距离加权后的KNN算法克服了由于K值不同引起的分类效果的波动，具有一定的鲁棒性。

4 结语

为了对自然图像进行有效准确地分类，本文提出了一种基于特征和距离加权的KNN分类方法，利用ReliefF算法进行特征加权，可以分析各个特征属性对分类的贡献程度，并利用距离平方的倒数对近邻样本进行距离加权，最后决定样本所属类别。仿真结果表明，本文提出的方法相比于标准KNN算法和特征加权KNN算法，具有更高的准确率，而且可以克服KNN分类算法由于K值取值大小的不同引起的分类误差。图像特征内容丰富，如何选用最具有代表图像内容的特征是下一步研究的主要工作内容。

[1] MARISA C.Visual attention：the past 25 years[J].Visio Research，2011，51(13)：1484-1525.

[2] TEOFILO DE C，GABRIELA C，FLORENT P.Images as sets of locally weighted features[J].Computer Vision and Image Understanding，2012，116(1)：68-85.

[3] 任建峰，郭雷，李刚.多类支持向量机的自然图像分类[J].西北工业大学学报，2005，23(3)：295-298.

[4] 谢文兰，石跃祥，肖平.应用BP神经网络对自然图像分类[J].计算机工程与应用，2010，46(2)：163-166.

[5] 李洁，高新波，焦李成.基于特征加权的模糊聚类新算法[J].电子学报，2006，34(1)：89-92.

[6] 郑洁，秦永彬，许道云.基于Relief的特征加权壳近邻分类算法[J].计算机工程与设计，2013，34(3)：951-954.

[7] HE J，TAN A H，TAN C L.A comparative study on chinese text categorization methods[C]//Proc. PRICAI’ 2000 Internantionnal Workshop on Text and Web Mining.Melbourne，Australia：[s.n.]，2000：24-35.

[8] GORA G，WOJNA A.A classifier combining rule induction and K-NN method with automated selection of optimal neighborhood[C]//Proc. 13th European Conference on Machine Learning. Berlin：[s.n.]，2002：111-123.

[9] 杨金福，宋敏，李明爱.一种新的基于距离加权的模板约简K近

邻算法[J].电子与信息学报，2011，33(10)：2378-2383.

[10] 肖辉辉，段艳明.基于属性值相关距离的KNN算法的改进研究[J].计算机科学，2013，40(11)：157-159.

[11] MALGORZATA W，PIOTR M.Automatic relief classification versusexpert and field based landform classification for the medium-altitude mountain range，the Sudetes，SW Poland[J].Geomorphology，2014(1)：133-146.

党宏社(1962— )，博士，教授，主要从事计算机控制、多源信息融合、数字图像处理等方面的研究；

白 梅(1990— )，女，硕士生，主研数字图像处理、图像检索，为本文通讯作者；

张 娜(1989— )，女，硕士生，主研压缩感知、图像处理。

责任编辑：时 雯

Classification Method of Feature Weighted for Natural Images Based on ReliefF and K-nearest Neighbors

DANG Hongshe，BAI Mei，ZHANG Na

(SchoolofElectricalandInformationEngineering，ShaanxiUniversityofScienceandTechnology，Xi’an710021，China)

In order to classify the natural images more effectively and accurately，a classification method weigh images feature and the nearest neighbors of KNN is proposed.Since diverse categories images have different visual features，ReliefF is used to obtain the feature weight vector of each category in training set for weighing the distance between test images and training images；different weights are given for the K-nearest neighbors according to the distance to training images，so that the weakness of traditional KNN at the classification decisions is overcome effectively.Compared with the traditional KNN and feature-weighted KNN，the experimental result shows that this method has more accuracy and strong robustness for the number of the nearest neighbors.

natural images；ReliefF；feature-weighed；KNN；distance-weighed

陕西省科技厅社会发展科技攻关计划项目(2015K18-05)

TP391

A

10.16280/j.videoe.2015.19.003

2015-02-13

【本文献信息】党宏社，白梅，张娜.基于ReliefF特征加权和KNN的自然图像分类方法[J].电视技术,2015，39(19).