胡天寒，葉明全，張 浩，盧小杰

?

基于禁忌搜索算法的特征選擇方法研究

胡天寒，葉明全，張 浩，盧小杰

為了提高特征選擇對(duì)分類結(jié)果的準(zhǔn)確率，本文提出了一種基于禁忌搜索算法的特征選擇方法。該方法利用禁忌搜索算法獲得包含特征權(quán)值和特征選擇向量的相對(duì)最優(yōu)解，然后用得到的最優(yōu)解向量對(duì)測(cè)試樣本做出預(yù)測(cè)。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的特征選擇方法相比，該方法的分類準(zhǔn)確率有了進(jìn)一步的提高，并且縮短了特征選擇的時(shí)間。

特征選擇；禁忌搜索；特征加權(quán)；距離度量

近十年，組合分類器已經(jīng)成為研究的熱點(diǎn)問題。一些學(xué)者將組合分類器應(yīng)用于許多實(shí)際領(lǐng)域，如手寫字符識(shí)別、人臉識(shí)別等[1，2]。一般來講，組合分類器的效果與基分類器的準(zhǔn)確率和多樣性有很大關(guān)系[3]。為了獲得KNN組合分類器的多樣性，Bao等人[4]提出組合基于不同距離函數(shù)的NN分類器來改善NN分類器的分類性能。雖然他們的組合方法采用了不同的距離度量，但他采用的特征子集卻是相同的。因此可能會(huì)出現(xiàn)一些樣本含有與分類無關(guān)的特征，并且這些特征的值比較大，從而引起基分類器犯相同的錯(cuò)誤。Bay[5]提出了一種不同的組合方法。他采用了單一的距離度量方法，用隨機(jī)產(chǎn)生的不同特征子集來訓(xùn)練各基分類器，最后采用簡單投票規(guī)則來組合各個(gè)NN分類器，使得分類效果得到了提升。

Zhang和Sun將禁忌搜索(Tabu Search，簡稱TS)算法運(yùn)用到特征選擇[6]。在他們的方法中，禁忌搜索以Mahalanobis距離作為目標(biāo)函數(shù)，這個(gè)目標(biāo)函數(shù)用來評(píng)估采用禁忌搜索獲得的特征子集的分類器的分類性能。TS中的特征選擇向量用0/1位串表示，0表示解向量沒有包含某個(gè)特征，1表示解向量包含了某個(gè)特征。他們的實(shí)驗(yàn)結(jié)果表明，禁忌搜索算法很容易獲得最優(yōu)解或次優(yōu)解，并且同其它次優(yōu)算法或遺傳算法相比，降低了計(jì)算代價(jià)。從此以后，禁忌搜索算法被廣泛應(yīng)用于特征選擇問題[7,8]。

Muhammad Atif Tahir和 James Smith對(duì)前面bao和Bay提出的問題進(jìn)行了綜合[9]。他們提出只要達(dá)到以下兩點(diǎn)要求，總體的分類性能就會(huì)得到提高：(1)采用禁忌搜索方法而不是隨機(jī)取樣方法來獲得各個(gè)特征子集；(2)采用不同的距離函數(shù)而不是單一的距離度量。并且應(yīng)該把兩者有機(jī)地融合到一起，而不是單獨(dú)的解決問題。為了達(dá)到以上目的，他們提出利用基于禁忌搜索方法進(jìn)行特征選擇，用最終得到的特征子集來訓(xùn)練五種不同距離度量的NN分類器，最后對(duì)各個(gè)NN分類器進(jìn)行組合，利用簡單投票原則做出分類預(yù)測(cè)。他們的實(shí)驗(yàn)獲得了很好的效果。然而他們僅僅利用禁忌搜索算法進(jìn)行了特征選擇，將與分類不相關(guān)的特征都去掉了，但在剩下的特征中還存在與特征強(qiáng)相關(guān)和弱相關(guān)的。顯然，將這些特征的權(quán)重全部等同起來，對(duì)分類的效果會(huì)產(chǎn)生不利的影響。陳振洲[10]等人指出， KNN算法中樣本的距離是由樣本的所有特征計(jì)算而來，而這些特征中有的特征與分類是強(qiáng)相關(guān)的，有的特征與分類是弱相關(guān)的，還有的特征與分類不相關(guān)。當(dāng)近鄰間的距離由大量的不相關(guān)特征所支配時(shí), 就會(huì)出現(xiàn)“維度災(zāi)難”的問題, 最近鄰方法對(duì)這個(gè)問題尤為敏感。

針對(duì)以上問題，Muhammad Atif Tahir等人提出一種基于禁忌搜索的KNN分類器[11]。它同時(shí)采用了特征選擇和特征加權(quán)兩種技術(shù)。他們的方法中用的特征權(quán)值向量是權(quán)值的真實(shí)值，而特征二進(jìn)制向量由0/1位串構(gòu)成。KNN分類器被用來評(píng)估禁忌搜索的每一個(gè)權(quán)值向量。除了特征權(quán)值和二進(jìn)制向量以外，K值也被包含到解向量中。采用squared Euclidean distance進(jìn)行距離度量。在加權(quán)的KNN分類器中，訓(xùn)練樣本和測(cè)試樣本的特征值在分類之前被乘以相應(yīng)的權(quán)值。于是那些具有較高權(quán)值的的特征空間被擴(kuò)大了，而具有較少權(quán)值的特征空間被壓縮了，從而使得KNN分類器能夠利用具有較高權(quán)值的特征更加精確地進(jìn)行分類。

本文在總結(jié)前面文獻(xiàn)思想的基礎(chǔ)上，提出一種基于禁忌搜索算法的特征選擇方法。我們利用禁忌搜索的尋優(yōu)能力，對(duì)樣本同時(shí)進(jìn)行了特征選擇和特征加權(quán)，在去除不相關(guān)特征的同時(shí)，對(duì)強(qiáng)相關(guān)和弱相關(guān)的特征分別賦予不同的權(quán)重，進(jìn)而對(duì)各個(gè)特征對(duì)分類的影響做了全面的考慮。同時(shí)由于K值對(duì)分類效果也有影響，所以我們將K也包含到解向量當(dāng)中，隨著禁忌循環(huán)的執(zhí)行，不斷地搜索最適合的K值，從而獲得最佳的分類效果。實(shí)驗(yàn)結(jié)果表明，該方法一定程度上提高了分類的準(zhǔn)確率和縮短了分類的時(shí)間。

1 基于禁忌搜索算法的特征選擇

1.1 禁忌搜索算法

Glover在1986年首次提出禁忌搜索算法，它是從全局上逐步搜索得到最優(yōu)解的算法。TS算法通過建立一個(gè)存儲(chǔ)結(jié)構(gòu)和禁忌準(zhǔn)則來避免過多的不必要搜索，并通過特赦準(zhǔn)則將被禁忌的優(yōu)良狀態(tài)進(jìn)行釋放，從而實(shí)現(xiàn)全局優(yōu)化。TS從確定一個(gè)初始解開始搜索，在當(dāng)前解中確定若干候選解，再從這些候選解中選出最好的解作為最佳候選解。如果最佳候選解的目標(biāo)值比“best so far”狀態(tài)好，就忽視它的禁忌特性，用最佳候選解來代替當(dāng)前解和“best so far”狀態(tài)，并把相應(yīng)的對(duì)象加入到禁忌表中，同時(shí)將禁忌表中各對(duì)象的禁忌長度進(jìn)行修改；若不存在上述候選解，則選擇候選解中非禁忌的最佳狀態(tài)作為當(dāng)前解，同時(shí)將相應(yīng)的對(duì)象加入到禁忌表中，并修改禁忌表中各對(duì)象的禁忌長度；重復(fù)上面的迭代搜索的過程，直到滿足給出的停止準(zhǔn)則。

禁忌搜索算法流程如下：

(1)給出算法參數(shù)，給初始解x賦值，將禁忌表置為空。

(2)判斷算法結(jié)果是否滿足終止條件。若是，則結(jié)束算法并輸出最優(yōu)解；否則，繼續(xù)以下步驟。

(3)由當(dāng)前解的鄰域函數(shù)產(chǎn)生若干鄰解，并確定若干候選解。

(4)用藐視準(zhǔn)則判斷候選解是否滿足。若成立，用滿足藐視準(zhǔn)則的最佳狀態(tài)y代替x成為新的當(dāng)前解，即x=y，并用與y對(duì)應(yīng)的禁忌對(duì)象來替換最早進(jìn)入到禁忌表的禁忌對(duì)象，同時(shí)用y替換“best so far”狀態(tài)，然后轉(zhuǎn)步驟6；否則，繼續(xù)以下步驟。

(5)判斷候選解對(duì)應(yīng)的各對(duì)象的禁忌屬性，將候選解中非禁忌對(duì)象對(duì)應(yīng)的最佳狀態(tài)作為當(dāng)前解，并將它對(duì)應(yīng)的禁忌對(duì)象用來代替最早進(jìn)入禁忌表的禁忌對(duì)象。

(6)轉(zhuǎn)步驟(2)。

1.2 基于禁忌搜索算法的特征選擇

1.2.1 編碼方法。本文提出的基于禁忌搜索算法的編碼解的結(jié)構(gòu)包含四個(gè)部分，如圖1所示。第一部分，W1，W2，…，Wn對(duì)應(yīng)的是n個(gè)特征的真實(shí)權(quán)值；第二部分，B1，B2，…，Bn對(duì)應(yīng)的是n個(gè)特征選擇向量，由0/1位串組成，0表示該特征不被選擇，1表示該特征被選擇；第三部分，K是KNN算法中近鄰的個(gè)數(shù)；第四部分是目標(biāo)函數(shù)值。

W1W2………WnB1B2………BnKCost

圖1 編碼解的結(jié)構(gòu)

1.2.2 目標(biāo)函數(shù)。本文中的目標(biāo)函數(shù)值指采用基于簡單投票方案的誤分類數(shù)目，定義為：

1.2.3 初始解。本文中，初始解的形式如圖2所示：

1.01.0……1.011……11K=1Cost=10

圖2 初始解

初始的情形是所有特征都被包含進(jìn)解向量中，而且權(quán)值全都為1.0，近鄰數(shù)也為1。

1.2.4 鄰解。鄰解是當(dāng)前解在鄰域中所產(chǎn)生的。在本文中，通過兩種方式來產(chǎn)生鄰解：

(1)對(duì)n個(gè)不同的特征賦予m個(gè)不同的權(quán)值，產(chǎn)生m*n個(gè)鄰解。

(2)通過對(duì)特征向量添加或刪除特征來產(chǎn)生鄰解。

從產(chǎn)生的N個(gè)鄰解中，選出最好的M個(gè)解作為候選解。從而，對(duì)Mn(n是距離度量的個(gè)數(shù))種集成候選解用目標(biāo)函數(shù)進(jìn)行評(píng)估，選出目標(biāo)函數(shù)值最小的一個(gè)解作為最優(yōu)候選解，即下一輪循環(huán)的當(dāng)前解。

1.2.5 禁忌移動(dòng)。從某個(gè)狀態(tài)轉(zhuǎn)移到其鄰域中的另一狀態(tài)叫做一次移動(dòng)。在本文中，如果在第i輪選中某個(gè)集成解，在接下來的T輪循環(huán)(T表示禁忌表的大小，也可稱為禁忌長度)中，禁止再次選中該集成解。

1.2.6 特赦準(zhǔn)則。也稱為期望準(zhǔn)則、藐視準(zhǔn)則。特赦準(zhǔn)則的機(jī)制是暫時(shí)停止禁忌移動(dòng)，在我們的方法中，如果在第i輪選中一個(gè)集成解，當(dāng)前的移動(dòng)會(huì)產(chǎn)生循環(huán)以來最優(yōu)的目標(biāo)函數(shù)值，所以即便它已經(jīng)在禁忌表中，仍然可以選中它作為下一輪的當(dāng)前解。

1.2.7 終止規(guī)則。常用的終止規(guī)則包括：

(1)給定一個(gè)迭代步數(shù)。

(2)連續(xù)迭代T次結(jié)果基本保持不變。

(3)當(dāng)前得到的最優(yōu)解數(shù)目達(dá)到預(yù)定要求。

給定的迭代步數(shù)是本文的終止條件。

1.2.8 本文方法的具體流程。(1)分類器的訓(xùn)練階段：

在每一輪的循環(huán)當(dāng)中，由每一種距離度量對(duì)應(yīng)的特征向量解產(chǎn)生N個(gè)鄰解。從N個(gè)鄰解中選出M個(gè)最好的候選解，接著將形成的Mn種集成候選解用簡單投票方案進(jìn)行評(píng)估，從而得到能夠產(chǎn)生不相關(guān)錯(cuò)誤的基于各種距離度量的特征子集及其權(quán)值。重復(fù)地進(jìn)行這一過程，不斷地改善集成分類性能，直至達(dá)到終止條件為止。最終我們會(huì)得到n種距離度量對(duì)應(yīng)的n個(gè)最優(yōu)特征子集。圖3描述了分類器的訓(xùn)練階段。

圖3 訓(xùn)練階段

(2)分類器的測(cè)試階段：

采用n種距離度量和n種相應(yīng)特征子集的KNN分類器被組合到一起，用來對(duì)測(cè)試樣本做出分類預(yù)測(cè)。圖4描述了分類器的測(cè)試階段。

圖4 測(cè)試階段

2 算法實(shí)現(xiàn)與比較

實(shí)驗(yàn)中，我們采用的樣本是江蘇大學(xué)附屬醫(yī)院提供的醫(yī)學(xué)數(shù)據(jù)。其中，樣本1包含120個(gè)樣本，含有9個(gè)特征，2個(gè)類別；樣本2包含190個(gè)樣本，含有18個(gè)特征，2個(gè)類別。實(shí)驗(yàn)程序采用Java語言編寫。使用的機(jī)器配置為3.00GHz Pentium(R) D CPU、2.00GB內(nèi)存、Windows XP操作系統(tǒng)。實(shí)驗(yàn)采用的各個(gè)參數(shù)值如下：

(2) M=2。M是選出的候選解的個(gè)數(shù)。

MuhammadAtifTahir等人提出一種基于禁忌特征選擇的NN分類器(記為T-NN)。為了做出對(duì)比，我們利用他們提出的NN分類器在兩個(gè)樣本上進(jìn)行了實(shí)驗(yàn)。同時(shí)我們認(rèn)為KNN分類器的分類效果與K值也有很大關(guān)系，因此在他們思想的基礎(chǔ)上，將K值也加入到解向量當(dāng)中(記為K-T-NN)，即K值在循環(huán)過程中也是在不斷變化的。并與本文提出的基于禁忌搜索算法的特征選擇方法進(jìn)行對(duì)比分析。為了得到較好的解，我們進(jìn)行了6次實(shí)驗(yàn)。

實(shí)驗(yàn)結(jié)果如表1所示，從表中數(shù)據(jù)可以看出，采用的數(shù)據(jù)為樣本1時(shí)，利用禁忌搜索算法進(jìn)行特征選擇的K-T-NN組合分類器比T-NN分類器獲得的效果要好，K-T-NN組合分類器在6次實(shí)驗(yàn)中的最高準(zhǔn)確率為95%，而T-NN分類器的最高準(zhǔn)確率為90%。這說明，K值對(duì)分類效果確實(shí)有影響。本文的方法獲得的最高準(zhǔn)確率可以達(dá)到100%，比上面獲得的最高準(zhǔn)確率分別高5%和10%，而且在禁忌循環(huán)次數(shù)相同(程序運(yùn)行時(shí)間相同)的情況下，更容易獲得最優(yōu)解。當(dāng)采用的數(shù)據(jù)為樣本2時(shí)，利用禁忌搜索算法進(jìn)行特征選擇的K-T-NN組合分類器和T-NN分類器，獲得的最高準(zhǔn)確率相同，都為85.7%。我們認(rèn)為這是由兩方面原因造成的：(1)樣本2含有18個(gè)特征，是樣本1含有特征個(gè)數(shù)的2倍，因此樣本2 較樣本1更不容易獲得最優(yōu)解；(2)由于KNN適合于大樣本分類，而本實(shí)驗(yàn)采用的樣本量過于偏小，因此，兩者的差別不明顯。本文的方法獲得的最高準(zhǔn)確率可以達(dá)到94.3%，比上面獲得的最高準(zhǔn)確率要高出8.6%，并且可以看出隨著循環(huán)次數(shù)的增加獲得最優(yōu)解的可能性也在不斷增加。

最后我們還可以看出無論是樣本1還是樣本2，經(jīng)過禁忌特征選擇后獲得的分類效果要比未經(jīng)特征選擇的單分類器和組合分類器要好很多。并且縮短了程序運(yùn)行的時(shí)間。

表1 本文算法同T-NN及K-T-NN算法在分類準(zhǔn)確率和程序運(yùn)行時(shí)間上的比較結(jié)果

在實(shí)驗(yàn)中我們將訓(xùn)練樣本分為兩部分，一部分作為訓(xùn)練階段的訓(xùn)練樣本，另一部分作為訓(xùn)練階段的測(cè)試樣本；測(cè)試階段則采用原始的訓(xùn)練樣本和測(cè)試樣本。通過多次實(shí)驗(yàn)，我們發(fā)現(xiàn)：訓(xùn)練階段的訓(xùn)練樣本和測(cè)試樣本的比例不同，得到的分類結(jié)果也會(huì)不同。實(shí)驗(yàn)過程中，我們把訓(xùn)練階段的訓(xùn)練樣本和測(cè)試樣本的比例分別設(shè)為9/1、3/1、1/1、4/1，通過實(shí)驗(yàn)發(fā)現(xiàn)75/25的比例獲得的效果最佳，因此上面我們采用了3/1的比例。

3 結(jié)束語

本文提出一種基于同步特征加權(quán)和特征選擇的KNN分類器，并利用醫(yī)學(xué)數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明與現(xiàn)有的特征選擇方法相比，該方法使得分類準(zhǔn)確率得到了提高，并且縮短了程序運(yùn)行的時(shí)間。當(dāng)然，由于禁忌搜索本身的一些特點(diǎn)，本方法也存在一些不足，比如為了利用禁忌算法獲得最優(yōu)解，就需要設(shè)定充分的循環(huán)次數(shù)，不可避免地要耗費(fèi)時(shí)間資源。另外，由于本文的方法會(huì)涉及到一些參數(shù)，例如K值的范圍、權(quán)值的范圍、禁忌循環(huán)的次數(shù)、目標(biāo)函數(shù)值Cost的初始值、禁忌長度等，這些參數(shù)都需要人工來設(shè)定，這樣就不可避免地會(huì)引起因參數(shù)設(shè)定不當(dāng)而對(duì)分類效果帶來的負(fù)面影響。由于本方法使用了不同的距離度量來組合KNN分類器，而距離度量的個(gè)數(shù)是有限的，因此對(duì)多路分類的效果不是太理想?；谝陨喜蛔?，以后將對(duì)以下地方進(jìn)行改進(jìn)：(1)進(jìn)一步改進(jìn)禁忌算法，降低其帶來的時(shí)間代價(jià)；(2)研究解決參數(shù)設(shè)定問題。

[1] 張永宏, 曹健, 王麗華. 一種解決人臉識(shí)別誤匹配災(zāi)難問題的方法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2014, 31(9): 177-180.

[2] 楊志華. 一種基于紋理識(shí)別的手寫數(shù)字識(shí)別方法[J].計(jì)算機(jī)工程與應(yīng)用, 2008, 44(13): 27-29.

[3] 郭華平,袁俊紅,張帆等. 一種新的組合分類器學(xué)習(xí)方法[J].計(jì)算機(jī)科學(xué), 2014, 41(7): 283-289.

[4] Y. Bao and N. Ishii and X. Du. Cobmining Multiple k-Nearest Neighbor Classifiers Using Different Distance Functions [C]. 5th International Conference on Intelligent Data Engineering and Automated Learning, 2004: 634-641.

[5] S.D.Bay. Combining Nearest Neighbor Classifiers Through Multiple Feature Subsets[C]. Proceedings of the Fifteenth International Conference on Machine Learning, 1998: 37-45.

[6] Zhang, H., Sun, G.. Feature selection using Tabu Search method [J]. Pattern Recognition, 2002, 35(3): 701-711.

[7] 冶曉隆, 蘭巨龍, 郭通. 基于主成分分析禁忌搜索和決策樹分類的異常流量檢測(cè)方法[J].計(jì)算機(jī)應(yīng)用，2013, 33(10): 2846-2850.

[8] 張昊, 陶然, 李志勇, 蔡鎮(zhèn)河. 基于KNN算法及禁忌搜索算法的特征選擇方法在入侵檢測(cè)中的應(yīng)用研究[J]. 電子學(xué)報(bào), 2009, 37(7): 1628-1632.

[9] Muhammad Atif Tahir,James Smith. Improving Nearest Neighbor Classifier using Tabu Search and EnsembleDistance Metrics[C]. Proceedings of the Sixth International Conference on Data Mining (ICDM'06), 2006: 1086 - 1090.

[10] 陳振洲, 李磊, 姚正安. 基于SVM的特征加權(quán)KNN 算法[J].中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2005, 44(1):17-20.

[11] Muhammad Atif Tahir, Ahmed Bouridane, Fatih Kurugollu. Simultaneous feature selection and feature weighting using Hybrid Tabu Search/K-nearest neighbor classifier [J]. Pattern Recognition Letters, 2007, 28(4):438-446.

責(zé)任編輯：劉海濤

TP391

A

1673-1794(2016)05-0061-04

胡天寒，皖南醫(yī)學(xué)院公共基礎(chǔ)學(xué)院實(shí)驗(yàn)師，碩士；葉明全，皖南醫(yī)學(xué)院公共基礎(chǔ)學(xué)院教授；張浩，盧小杰，皖南醫(yī)學(xué)院公共基礎(chǔ)學(xué)院教師(安徽 蕪湖 241002)。

國家自然科學(xué)基金面上項(xiàng)目(61672386)；安徽省高校省級(jí)自然科學(xué)研究重點(diǎn)項(xiàng)目資助 (KJ2014A266)；皖南醫(yī)學(xué)院博士啟動(dòng)基金項(xiàng)目(WK2014RC01)

2016-01-06