兩種基于K近鄰特征選擇算法的對(duì)比分析

薛又岷，嚴(yán)玉萍，古嘉玲，包曉蓉

（江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江　212003）

兩種基于K近鄰特征選擇算法的對(duì)比分析

薛又岷，嚴(yán)玉萍，古嘉玲，包曉蓉

（江蘇科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江212003）

在特征選擇過(guò)程中，針對(duì)近鄰錯(cuò)誤分類率較低的問(wèn)題，分別采用正向貪心和逆向貪心思想設(shè)計(jì)了兩種啟發(fā)式特征選擇算法，其目的是在降低數(shù)據(jù)集中特征數(shù)量的同時(shí)，能夠進(jìn)一步降低近鄰錯(cuò)誤分類率。通過(guò)8組UCI數(shù)據(jù)集上的交叉驗(yàn)證結(jié)果表明，相比于正向貪心算法，逆向貪心算法能夠刪除較多的冗余特征，從而得出逆向貪心算法能夠更有效地提高近鄰算法的分類精度的結(jié)論。

特征選擇；啟發(fā)式算法；貪心算法；近鄰錯(cuò)誤分類率

特征選擇，是機(jī)器學(xué)習(xí)與人工智能領(lǐng)域[1-4]內(nèi)的一項(xiàng)重要研究?jī)?nèi)容。眾所周知，在數(shù)據(jù)集中，每個(gè)特征的重要程度是不同的，而特征選擇就是考慮在一些評(píng)價(jià)指標(biāo)的前提條件下，選擇出數(shù)據(jù)集中重要的特征并刪除其中不相關(guān)或冗余的特征，以達(dá)到簡(jiǎn)化知識(shí)表示與數(shù)據(jù)分析的目的。近年的研究成果表明，現(xiàn)有的很多特征選擇算法大致可歸為兩類：Filter算法與Wrapper算法[5]。一般來(lái)說(shuō)，F(xiàn)ilter算法在特征子集的評(píng)價(jià)過(guò)程中 （特征選擇）不考慮數(shù)據(jù)的分類或?qū)W習(xí)過(guò)程，而Wrapper算法往往利用某種分類性能作為評(píng)價(jià)指標(biāo)，并采用一定的搜索策略[6]加以實(shí)現(xiàn)。在現(xiàn)實(shí)世界中，由于數(shù)據(jù)規(guī)模的高速增長(zhǎng)，目前已經(jīng)出現(xiàn)了多種類型的優(yōu)化搜索策略，其中啟發(fā)式算法作為一大類搜索方法，采用貪心的基本思想，以較快的速度逼近問(wèn)題的精確解或近似解，因而受到了眾多研究學(xué)者的廣泛關(guān)注。

在Wrapper算法[7]中，分類性能是一項(xiàng)重要的評(píng)價(jià)指標(biāo)。作為十大經(jīng)典分類算法之一，KNN（K近鄰）方法由于其分類思想簡(jiǎn)單且易于實(shí)現(xiàn)，因而在許多領(lǐng)域得到了廣泛的應(yīng)用。但在實(shí)際應(yīng)用中，當(dāng)訓(xùn)練樣本的特征較多時(shí)，KNN算法通常會(huì)面臨時(shí)間效率低下，精度下降等一系列的不足。為解決這一問(wèn)題，本文將采用兩種不同的貪心搜索策略并設(shè)計(jì)基于K近鄰分類器的特征選擇算法，其主要目的是選擇出對(duì)于分類影響較大的特征并剔除冗余特征，因而利用該思想有望提高KNN的分類性能。

1　基本知識(shí)

KNN算法[8]的主要分為3步：首先，計(jì)算待分類樣本與已知類別的訓(xùn)練樣本之間的距離或相似度，找到與待分類樣本最近的k個(gè)樣本，稱之為待分類樣本的k個(gè)近鄰；其次，根據(jù)這些樣本所屬的類別來(lái)判斷待分類樣本的類別，如果待分類樣本的k個(gè)近鄰都屬于同一個(gè)類別，那么待分類樣本也屬于該類別；否則的話，對(duì)每一個(gè)候選類別進(jìn)行評(píng)分，按照一定的規(guī)則來(lái)確定待分類樣本的類別。

K近鄰算法中的分類決策規(guī)則往往遵循多數(shù)表決[9]，多數(shù)表決是指由待分類樣本的k個(gè)近鄰（訓(xùn)練樣本）所得到的多數(shù)類別來(lái)決定輸入樣本的類別。盡管K近鄰算法可以在一定程度上有效地判斷出待分類樣本的類別，但其結(jié)果往往也伴隨著誤差，這樣的誤差文中稱為近鄰錯(cuò)誤分類率。

定義1給定一個(gè)分類任務(wù)，分類函數(shù)為

其中ci為類別標(biāo)記，x為待分類樣本。

定義2對(duì)給定的待分類樣本x，可構(gòu)建判別函數(shù)

其中ci為x的真實(shí)類別標(biāo)記，k表示采用KNN分類器。

定義3對(duì)于一組給定的樣本集合X，特征集合為C，則該組樣本的近鄰正確分類率為

其中|X|表示集合X的基數(shù)。

定義4對(duì)于一組給定的樣本X，特征集合為C，對(duì)于a埸C，特征a相對(duì)于特征集合C的重要度為

2　基于貪心策略的K近鄰特征選擇算法

所謂特征選擇，是指從原始特征中選擇出一些最有效的特征以降低數(shù)據(jù)維數(shù)的過(guò)程[10]，是提高學(xué)習(xí)算法性能的一個(gè)重要手段，也是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)與模式識(shí)別中關(guān)鍵的數(shù)據(jù)預(yù)處理步驟。

其實(shí)，在樣本分類的過(guò)程中，有些特征對(duì)于分類的貢獻(xiàn)度很小，甚至毫無(wú)貢獻(xiàn)。顯然，在這種含有冗余特征的樣本中利用KNN分類器進(jìn)行分類[11]，會(huì)在一定的程度上影響分類的正確率。如果將那些對(duì)于分類重要的特征選取出來(lái)，以此組合成為一個(gè)新的測(cè)試樣本，然后在這個(gè)新的測(cè)試樣本上分類，就可以提高傳統(tǒng)的K近鄰算法的分類精度從而降低近鄰錯(cuò)誤分類率。根據(jù)這一思想，本文設(shè)計(jì)了兩種基于貪心策略的K近鄰特征選擇算法。

2.1正向貪心特征選擇算法

給定的一組待分類樣本集合X，正向貪心特征選擇算法可以分為2步：首先，利用正向貪心選擇出重要度較大的特征，并將該特征加入到候選特征集合Red中，從而構(gòu)建新的測(cè)試樣本集；其次，不斷重復(fù)上述步驟直到分類精度ACCRed（X）不再上升。

根據(jù)定義3所示的特征重要度，正向貪心特征選擇算法如算法1所示：

算法1正向貪心特征選擇算法（FGA）

輸入:待分類樣本集合X，特征集合C。

輸出:所選擇出的特征集合Red。

步驟1:計(jì)算ACCC（X）；

步驟 4:選擇特征 b∈C且滿足 Sig（b）=max{Sig（ai）:ai∈C}，若Sig（b）>0，令Red=Red∪，C=C-Red；轉(zhuǎn)至步驟3，否則轉(zhuǎn)至步驟5；

步驟5:輸出Red和ACCRed（X）。

2.2逆向貪心特征選擇算法

給定的一組待分類樣本集合X，逆向貪心特征選擇算法可以分為2步：首先，利用逆向貪心選擇出重要度較大的特征，并將該特征加入到候選特征集合Red中，從而構(gòu)建新的測(cè)試樣本集；其次，不斷重復(fù)上述步驟直到分類精度ACCRed （X）不再上升。

算法2逆向貪心特征選擇算法（RGA）

輸入:待分類樣本集合X，特征集合C。

輸出:所選擇出的特征集合Red。

步驟1:計(jì)算ACCC（X）；

步驟2:Red←C，ACCRed（X）=ACCC（X）；

步驟3:坌ai∈Red，計(jì)算屬性ai的重要度Sig（ai）=ACCRed（X）-ACCRed-{ai}（X）；

步驟4:選擇特征b∈C且滿足Sig（b）=min{Sig（aj）:坌aj∈C}，若Sig（b）>0，轉(zhuǎn)至步驟6，否則轉(zhuǎn)至步驟5；

步驟5:令Red=Red-，轉(zhuǎn)至步驟3；

步驟6:輸出Red和ACCRed（X）。

通過(guò)計(jì)算，可以得到傳統(tǒng)的K近鄰特征選擇算法的時(shí)間、空間復(fù)雜度分別為O（n2）和O（n）。而基于貪心策略的K近鄰特征選擇算法的時(shí)間、空間復(fù)雜度均為O（n），其中n表示數(shù)據(jù)中特征的個(gè)數(shù)。因此，正向貪心特征選擇算法與逆向貪心特征選擇算法可以一定程度提高算法效率。

3　實(shí)驗(yàn)結(jié)果

為了驗(yàn)證算法的有效性，本文選取了8組UCI數(shù)據(jù)集，并進(jìn)行了3組實(shí)驗(yàn)。這8組數(shù)據(jù)集的基本信息如表1所示。實(shí)驗(yàn)1是將本文提出的正向貪心算法與傳統(tǒng)的KNN算法進(jìn)行對(duì)比分析；實(shí)驗(yàn)2是將本文提出的逆向貪心算法與傳統(tǒng)的KNN算法進(jìn)行對(duì)比分析；實(shí)驗(yàn)3是將本文提出的正向貪心算法與逆向貪心算法進(jìn)行對(duì)比分析。這3組實(shí)驗(yàn)中我們都采用10倍交叉驗(yàn)證的方法。實(shí)驗(yàn)環(huán)境為PC機(jī)，雙核2.1 GHz CPU，2 GB內(nèi)存，Windows 8操作系統(tǒng)，MatlabR 2014a實(shí)驗(yàn)平臺(tái)。

表1　數(shù)據(jù)集的基本信息Tab.1　The information of used databases

實(shí)驗(yàn)1正向貪心特征選擇算法

在實(shí)驗(yàn)1中，我們將正向貪心特征選擇算法（FGA）與傳統(tǒng)的K近鄰算法（KNN）進(jìn)行了對(duì)比分析，結(jié)果如表2所示。從表2可以看出，所提出的正向貪心特征選擇算法可以在部分?jǐn)?shù)據(jù)集上有效地減少特征個(gè)數(shù)：如Abalone數(shù)據(jù)集原始數(shù)據(jù)有9個(gè)特征，利用正向貪心特征選擇算法（K=5）選擇出了2個(gè)特征，同時(shí)分類精度提高了近3個(gè)百分點(diǎn)。由此可以看出在部分?jǐn)?shù)據(jù)集中通過(guò)正向貪心策略進(jìn)行特征選擇，可以去除原始數(shù)據(jù)中的冗余特征（降低了數(shù)據(jù)的存儲(chǔ)空間），從而可以提高了KNN分類器的時(shí)間效率。因此正向貪心特征選擇算法在特征選擇和分類時(shí)間方面具有一定優(yōu)勢(shì)。但同時(shí)值得注意的是，特征數(shù)目的減少有可能帶來(lái)分類精度的降低，如Wine Quality數(shù)據(jù)集原始數(shù)據(jù)有12個(gè)特征，利用正向貪心特征選擇算法（K=1）選擇出了2個(gè)特征，分類精度相比于原始分類精度下降了近25個(gè)百分點(diǎn)，這是由于正向貪心策略的終止條件是分類精度不再上升，此時(shí)得到的分類精度有可能會(huì)小于利用所有特征所得到的分類精度。

表2　正向貪心算法與KNN算法的比較Tab.2　The comparison between forward greedy algorithm and KNN algorithm

實(shí)驗(yàn)2逆向貪心特征選擇算法

在實(shí)驗(yàn)2中，我們將逆向貪心特征選擇算法（RGA）與傳統(tǒng)的K近鄰算法（KNN）進(jìn)行了對(duì)比分析，結(jié)果如表3所示。從表3可以看出，利用所提出的逆向貪心特征選擇算法可以大幅度減少特征數(shù)，如在Breast Cancer Wisconsin數(shù)據(jù)集上，原始數(shù)據(jù)擁有31個(gè)特征，而逆向貪心特征選擇算法（K=1）僅選取了6個(gè)特征。由此可以看出通過(guò)逆向貪心策略進(jìn)行特征選擇，可以去除原始數(shù)據(jù)中的冗余特征（降低了數(shù)據(jù)的存儲(chǔ)空間）。此外，值得注意的是利用逆向貪心特征選擇算法得到的特征子空間可以有效地提高分類精度。原始數(shù)據(jù)通過(guò)逆向貪心特征選擇，去除了數(shù)據(jù)集中的冗余特征，且保留原數(shù)據(jù)集的特征信息，從而在保持分類精度上升或與原始分類精度差別不大的前提下，降低了時(shí)間和空間復(fù)雜度。因此，相比于傳統(tǒng)的K近鄰算法，逆向貪心特征選擇算法更加有效。

表3　逆向貪心算法和KNN算法的比較Tab.3　The comparison between reverse greedy algorithm and KNN algorithm

實(shí)驗(yàn)3正向貪心特征選擇算法與逆向貪心特征選擇算法的比較

在實(shí)驗(yàn)3中，我們將正向貪心特征選擇算法（FGA）與逆向貪心特征選擇算法（RGA）進(jìn)行對(duì)比分析，如表4所示。從表4可以看出，利用逆向貪心特征選擇算法所選取的特征數(shù)在大多數(shù)數(shù)據(jù)集上要少于利用正向貪心特征選擇算法所選取的特征數(shù)，且利用逆向貪心特征選擇出的特征子集進(jìn)行分類，其分類精度要普遍高于利用正向貪心特征選擇出的特征子集進(jìn)行分類所求出的分類精度。

4　結(jié)　論

為了進(jìn)一步降低K近鄰算法的近鄰錯(cuò)誤分類率，本文結(jié)合正向/逆向貪心搜索策略所設(shè)計(jì)了兩種啟發(fā)式特征選擇算法。由實(shí)驗(yàn)結(jié)果可知，正向貪心特征選擇算法僅能降低數(shù)據(jù)集中特征數(shù)量，但往往不能降低近鄰錯(cuò)誤分類率。而相比于正向貪心算法，逆向貪心算法不僅能夠刪除較多的冗余特征，而且能夠更有效地提高近鄰算法的分類精度。因此所提出的算法是有一定現(xiàn)實(shí)意義的。

表4　正向貪心算法和逆向貪心算法的比較Tab.4　The comparison between forward and reverse greedy algorithms

在本文工作的基礎(chǔ)上，筆者下一步會(huì)嘗試將正向/逆向貪心搜索策略與其他類型的分類器（如支持向量機(jī)SVM，決策樹(shù)等）相結(jié)合，并將其應(yīng)用到蛋白質(zhì)二級(jí)結(jié)構(gòu)類預(yù)測(cè)的問(wèn)題上。

[1]Qian Y H，Liang J Y，Pedrycz W，et al.Positive Approximation:An Accelerator for Attribute Reduction in Rough Set Theory[J].Artificial Intelligence，2010，174(9-10）:597-618.

[2]Yang X B，Yu D J，Yang J Y，et al.Dominance-based Rough Set Approach to Incomplete Interval-valued Information System[J].Data&Knowledge Engineering，2009，68（11）: 1331-1347.

[3]Yang X B，Yang Y，Wu C，et al.Dominance-based Rough Set Approach and Knowledge Reductions in Incomplete Ordered Information System[J].Information Sciences，2008，178（4）:1219-1234.

[4]Qian Y H，Liang J Y，Pedrycz W，et al.An Efficient Accelerator for Attribute Reduction From Incomplete Data in Rough Set Framework[J].Pattern Recognition，2011，44（8）:1658-1670.

[5]Zeng Z L，Zhang H J，Zhang R，et al.A Novel Feature Selection Method Considering Feature Interaction[J].Pattern Recognition，2015，48:2656-2666.

[6]Ding J Y，Song S J，Gupta J，et al.An Improved Iterated Greedy Algorithm With a Tabu-based Reconstruction Strategy for the No-wait Flowshop Scheduling Problem[J].Applied Soft Computing，2015，30（5）:604-613.

[7]Kohavi R，John G H.Wrappers for Feature Subset Selection [J].Artificial Intelligence，1997，97(1-2):273-324.

[8]Hu Q H，Pedrycz W，Yu D R，Lang J.Selecting Discrete and Continuous Features Based on Neighborhood Decision Error Minimization[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B:Cybernetics，2010，40（1）:137-150.

[9]梁立東，葉邦彥.一種最近鄰像素值的極大概率濾波算法[J].電子設(shè)計(jì)工程，2014（7）：181-183，187.

[10]劉軒，王衛(wèi)紅，唐曉斌，等.遺傳算法在SAR圖像目標(biāo)鑒別特征選擇上的應(yīng)用[J].電子科技，2014（5）：140-144.

[11]景永霞，茍和平，馮百明，等.不均衡數(shù)據(jù)集中KNN分類器樣本裁剪算法[J].科學(xué)技術(shù)與工程，2013（16）：4720-4723.

A comparison between two KNN based feature selection algorithms

XUE You-min，YAN Yu-ping，GU Jia-ling，BAO Xiao-rong
（School of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang 212003，China）

To reduce the nearest neighbor error classification rate in feature selection，two heuristic algorithms are proposed by using the forward and reverse greedy ideas，respectively.The purpose of our paper is not only to reduce the features in data sets，but also to further reduce the nearest neighbor error classification rate.By the cross validation on eight UCI data sets，the experimental results show that the reverse greedy algorithm can not only remove more redundant features，but also can effectively improve the classification accuracy of the nearest neighbor algorithm.

feature selection；heuristic algorithm；greedy algorithm；nearest neighborhood error classification rate

TN18

A

1674－6236（2016）01-0019-04

2015-06-11稿件編號(hào)：201506121

國(guó)家自然科學(xué)基金（61305058）；中國(guó)博士后科學(xué)基金（2014M550293）

薛又岷（1995—），男，江蘇南京人。研究方向：粗糙集、粒計(jì)算與數(shù)據(jù)挖掘。