基于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).