基于粒子群算法和粗糙集的特征選擇方法

楊祺 王謙

(南京熊貓漢達(dá)科技有限公司制造部,江蘇南京 210014)

1 引言

特征選擇也叫特征子集選擇,是選取一系列的特征構(gòu)成一個(gè)特征子集,能夠使得這個(gè)子集具有與特征全集相同或者更好的功能,特別是對(duì)于數(shù)據(jù)的分類。特征選擇算法是提高學(xué)習(xí)算法性能的一個(gè)重要手段,是模式識(shí)別中數(shù)據(jù)預(yù)處理的關(guān)鍵步驟[1]。在以往的數(shù)據(jù)分類過程中,數(shù)據(jù)集通常會(huì)包含大量的無關(guān)和冗余特征,導(dǎo)致維數(shù)的復(fù)雜度較高,造成一定的維數(shù)災(zāi)難,尤其是增加了分類的負(fù)擔(dān)。特征選擇算法的出現(xiàn)為此提供了一種行之有效的解決方式[2]。

粗糙集可以處理具有不確定性和模糊性的數(shù)據(jù),用于發(fā)現(xiàn)不一致數(shù)據(jù)中的模式。粗糙集已在模式識(shí)別中作為一種有用的特征選擇方法?；诖植诩奶卣鬟x擇的優(yōu)化準(zhǔn)則是找到最短的或最小約簡(jiǎn)的同時(shí)獲得高質(zhì)量的分類,而目前尚無最佳的屬性約簡(jiǎn)算法[3]。一般來說,基于粗糙集的特征選擇方法,主要以貪婪算法為主。貪婪算法通常采用粗糙集屬性重要性作為啟發(fā)式知識(shí),以空集或?qū)傩院碎_始,然后采用前向選擇或向后消除的方式。前向選擇是從空集開始,逐一增加,從候選集中選擇重要的屬性,直到選定的集合是一個(gè)約簡(jiǎn)集合。向后消除則從完整屬性集開始,并逐步移除屬性,從而獲得約簡(jiǎn)集。基于貪婪算法的粗糙集特征選擇,能夠獲得一定的屬性約簡(jiǎn),但是效率低下,不能保證所選特征的質(zhì)量,同時(shí)造成一定的資源浪費(fèi)。

特征選擇方法的劃分一般是根據(jù)評(píng)價(jià)函數(shù)的不同,大致可以分為封裝模式和過濾模式。過濾模式通過分析特征子集內(nèi)部的特點(diǎn)來衡量其好壞,一般用作預(yù)處理。封裝模式實(shí)質(zhì)上是一個(gè)分類器,用選取的特征子集對(duì)樣本集進(jìn)行分類,分類的精度作為衡量特征子集好壞的標(biāo)準(zhǔn)。在封裝模式中,分類學(xué)習(xí)算法封裝在特征選擇的過程中,以學(xué)習(xí)算法的性能作為子集的評(píng)價(jià)標(biāo)準(zhǔn)。當(dāng)滿足一定條件(一般設(shè)定的迭代次數(shù))時(shí)將最優(yōu)的特征子集輸出,同時(shí)獲得一個(gè)具有較高分類性能的模型。在封裝模式的特征選擇方法中,可以采用多種學(xué)習(xí)算法來評(píng)價(jià)特征子集,如貝葉斯分類器、鄰近算法、支持向量機(jī)及神經(jīng)網(wǎng)絡(luò)等。特征選擇實(shí)際是一個(gè)組合優(yōu)化問題,特征選擇過程中,往往特征數(shù)目繁多,搜索空間較大,所以需要搜索算法去獲得最優(yōu)的選擇方案,存在的搜索方法有序列前向選擇SFS和序列后向選擇SBS、粒子群算法(PSO)、蟻群算法(ASO)等。本文采用封裝模式的特征選擇方法,將粗糙集作為評(píng)價(jià)函數(shù),以骨干粒子群算法(Bare bones PSO)作為搜索算法,通過實(shí)驗(yàn)說明提出算法的有效性和實(shí)用性。

2 粒子群算法

2.1 傳統(tǒng)粒子群算法

粒子群算法是通過模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機(jī)搜索算法[4]。其描述如下:

假設(shè)在一個(gè)D維的目標(biāo)搜索空間, m個(gè)粒子組構(gòu)成一個(gè)群落,其中的第 i個(gè)粒子,表示一個(gè)D維的向量 Xi=(xi1, xi2....xiD),i = (1,2,3....m)。其中第 i個(gè)粒子在目標(biāo)搜索空間的位置是 xi。每一個(gè)粒子所在的位置就是一個(gè)潛在的備選解,將 xi代入到目標(biāo)函數(shù)中,計(jì)算其適應(yīng)度值。每個(gè)粒子 i還有一個(gè)速度決定其飛翔的方向和距離,Vi=(vi1,vi2...viD)速度也是一個(gè)D維的向量。第 i粒子搜索到的最優(yōu)位置記為 Popt(局部最優(yōu)解),整個(gè)粒子群迄今為止搜索到的最佳位置記為 Gopt(全局最優(yōu)解)。粒子速度和位置的更新公式如下:

其中, d = 1 ,2,3...D, i = 1 ,2,3...m 。 m是種群的規(guī)模; c1和c2加速常數(shù),r是[0,1]之間任意的隨機(jī)數(shù),t是迭代次數(shù)。上述的粒子群算法,只適應(yīng)于連續(xù)問題的求解。Kennedy和Eberhar提出了離散二進(jìn)制粒子群算法(BPSO)[5],這種算法采用的是二進(jìn)制的編碼形式。在二進(jìn)制的粒子群算法中,粒子的位置 Xi(10110011)采用二進(jìn)制的字符串表示,而速度向量則不做此要求。粒子的位置更新公式變?yōu)?

2.2 骨干粒子群算法

Kennedy在原始的粒子群算法的基礎(chǔ)之上提出了Bare bones粒子群算法[6]。這種算法舍棄粒子的速度,采用高斯模型,利用粒子的局部的全局最優(yōu)解來跟新粒子的位置,公式如下:

Pobj(t)代表局部最優(yōu)解, Gobj(t)代表全局最優(yōu)解。在上述公式中,粒子的位置被表示為局部和全局最優(yōu)解的均值和偏差的高斯分布。為了解決粒子群收斂于局部最優(yōu)解的問題,需從優(yōu)化算法全局探索能力和局部開發(fā)能力兩方面入手。粒子需要能夠跳出當(dāng)前局部最優(yōu)位置,并提高當(dāng)前鄰域內(nèi)細(xì)化搜索的能力。骨干粒子群算法的提出很好的解決了這一問題,同時(shí)保持了粒子多樣性和收斂之間的平衡,同時(shí)骨干粒子群算法參數(shù)較少,具有很高的應(yīng)用性。

在粒子群的初始化中將引入混沌模型,種群初始化采用隨機(jī)方式,即 xid= r 。混沌模型的初始化進(jìn)程為:

在離散粒子群算法的特征選擇中,粒子的位置向量Xi=(xi1, xi2...xiD)代表一個(gè)特征子集,其中的 xi1就代表一個(gè)特征。在離散粒子群算法中 xi1是二進(jìn)制,當(dāng) xi1取0時(shí),表示這個(gè)特征沒有被選中,當(dāng) xi1為1的時(shí)候則表示該特征被選中。例如, Xi=(01000111)表示該特征子集中有8個(gè)特征,1的個(gè)數(shù)為4,表示4個(gè)特征被選中。傳統(tǒng)的特征選擇算法中,都是采用離散粒子群算法,通過Sigmoid函數(shù)將粒子的位置向量由十進(jìn)制轉(zhuǎn)換為二進(jìn)制,但是在骨干粒子群算法中,粒子的速度向量被舍棄,無法使用Sigmoid函數(shù)。因此需要引入解碼機(jī)制,將特征被選入特征子集的可能性作為解碼的原理,把粒子群中的粒子作為解決問題的一個(gè)潛在方法。粒子Xi=(xi1,xi2...xiD),xi1∈ [ 0,1]表示第一個(gè)特征被選擇的可能性:

當(dāng) eij= 1時(shí),表示第j個(gè)特征被選入特征子集。如果為0,則表示該特征未被選入。在統(tǒng)計(jì)被選入的特征數(shù)目時(shí),可直接統(tǒng)計(jì) eij中的1的個(gè)數(shù)。

表1 實(shí)驗(yàn)數(shù)據(jù)

3 粗糙集

粗糙集理論是Pawlak在1982年提出的一種能夠定量分析處理不精確或者不完整信息的新型數(shù)學(xué)工具。粗糙集理論最初的原型來源于簡(jiǎn)單的信息模型,通過關(guān)系數(shù)據(jù)庫分類歸納形成概念和規(guī)則,在保持分類能力不變的前提下,通過等價(jià)關(guān)系的分類以及對(duì)于目標(biāo)的近似來實(shí)現(xiàn),由于粗糙集理論思想新穎、方法獨(dú)特,已成為一種重要的智能信息處理技術(shù),該理論已經(jīng)在機(jī)器學(xué)習(xí)等方面得到了廣泛應(yīng)用。特征選擇中存在的數(shù)據(jù)往往是不準(zhǔn)確的、冗余的,而粗糙集是一個(gè)強(qiáng)大的數(shù)據(jù)分析工具,它能夠表達(dá)和處理不完備信息,能在保留關(guān)鍵信息的前提下對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)化并求得數(shù)據(jù)的最小表達(dá)式,識(shí)別并評(píng)估數(shù)據(jù)之間的依賴關(guān)系,揭示出數(shù)據(jù)的簡(jiǎn)單模式。一個(gè)信息表數(shù)據(jù)表達(dá)系統(tǒng)表示為 S = ( U,A),U是樣本的集合, A是有限非空的屬性集合,V是屬性值集合,Va表示屬性 a∈A的屬性值范圍,fa:U→Va是一個(gè)信息函數(shù),它指定U中每一個(gè)樣本 x的屬性值。對(duì)于每個(gè)屬性子集 P?A定義一個(gè)不可分辨關(guān)系:

x,y在S中關(guān)于屬性集P是等價(jià)的,當(dāng)且僅當(dāng) fa（x ） = fa（y）對(duì)所有的f∈P成立,即 x,y不能用P 中的屬性加以區(qū)別。在信息系統(tǒng)S={U,A}中,設(shè)XU是個(gè)體全域上的子集,PA,則X的下近似集:根據(jù)現(xiàn)有的數(shù)據(jù)R,判斷U中所有屬于或者可能屬于集合X的對(duì)象組成的集合為:

其中[x]p表示等價(jià)關(guān)系P下包含x的等價(jià)類。上近似集:根據(jù)現(xiàn)有的數(shù)據(jù)R,判斷U中一定屬于或者可能屬于集合X的對(duì)象組成的集合。即:

其邊界區(qū)域?yàn)?BndP(X ) = PX - PX (10)

P,Q?A,如果 IND(P ) ? I ND(Q),則說明集合P依賴于Q,記為P?Q,一般采用依賴度來評(píng)價(jià)兩個(gè)集合的依賴性,即,

當(dāng)k=1時(shí),Q完全依賴于P, 0＜k＜1,Q部分依賴于P, k=0,Q完全獨(dú)立于P。

4 適應(yīng)度函數(shù)

特征選擇的目標(biāo)是在利用最少的特征條件獲得最好的分類模型,相比于過濾模式,封裝的適應(yīng)度函數(shù)往往能取得更好的分類效果。本文采用封裝模式粗糙集的適應(yīng)度函數(shù):

其中 λR( D)表示數(shù)據(jù)集D相對(duì)于條件屬性R的分類質(zhì)量,R表示選擇的特征數(shù)目,C表示所有的特征數(shù)目。其中a、b是調(diào)整因子,調(diào)整分類質(zhì)量與被選擇特征數(shù)目之間對(duì)于適應(yīng)度函數(shù)的影響。一般a∈ [ 0,1], b = 1 - a ,前期實(shí)驗(yàn)表明,分類質(zhì)量對(duì)于適應(yīng)度函數(shù)的影響明顯高于特征數(shù)目,因此將a的值設(shè)定為0.9,確保分類質(zhì)量起主導(dǎo)作用。

5 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證骨干粒子群算法與粗糙集結(jié)合的優(yōu)越性。本文選擇離散粒子群算法(BPSO)和遺傳算法(GA),同時(shí)作用在粗糙集適應(yīng)度函數(shù)上,采用數(shù)據(jù)集UCI機(jī)器學(xué)習(xí)庫中的數(shù)據(jù)(如表1所示)。設(shè)定粒子群種群數(shù)目20,迭代次數(shù)為100,遺傳算法的交叉概率為0.6,變異概率為0.4。比較不同算法作用在相同數(shù)據(jù)集上的分類效果,同時(shí)比較被選特征子集中的特征數(shù)目。

表2 各算法分類效果對(duì)比

6 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)結(jié)果如表2所示,三種不同的算法作用于九組不同數(shù)據(jù)集,比較分類效果以及被選特征數(shù)目。總體而言,相比于遺傳算法,傳統(tǒng)粒子群算法,骨干粒子群在數(shù)據(jù)分類、約簡(jiǎn)特征數(shù)目上的效果更佳。當(dāng)在數(shù)據(jù)集特征數(shù)目較少時(shí),例如在數(shù)據(jù)集Tic-tac-toe 和Breast caner中,骨干粒子群算法相比于其他兩種算法在分類的效果上有了一定的提高,特別是對(duì)于數(shù)據(jù)集Breast caner減少了被選特征的數(shù)目。隨著特征數(shù)目的增加,數(shù)據(jù)集也更加復(fù)雜,相比于其他兩種算法,基于骨干粒子群的特征選擇方法能夠取得較好的分類效果。在數(shù)據(jù)集Vote和Lymphography中,新算法的分類效果明顯提高。特別是在數(shù)據(jù)集Lung中,分類準(zhǔn)確率相比于傳統(tǒng)粒子群算法提高了近9%。其中數(shù)據(jù)集Led在迭代的前期就達(dá)到了100%的分類準(zhǔn)確率,說明骨干粒子群算法具有較快的收斂能力。此外,被選特征數(shù)目與分類的準(zhǔn)確率隨著迭代次數(shù)的增加基本上呈現(xiàn)反比例關(guān)系,即利用最少的特征數(shù)目可以獲得最優(yōu)的模型,當(dāng)分類的準(zhǔn)確率達(dá)到最高時(shí),被選特征數(shù)目幾乎不再變化,該約集簡(jiǎn)中的特征能夠使得這個(gè)子集具有與特征全集相同或者更好的分類能力。

7 結(jié)語

本文提出一種基于骨干粒子群算法和粗糙集的特征選擇方法。將骨干粒子群算法作為特征選擇產(chǎn)生過程的搜索算法,將粗糙集作為評(píng)價(jià)函數(shù)。在粒子群算法初始過程中引入混沌模型增加其初始粒子的多樣性,同時(shí)在更新機(jī)制中引入骨干因子增加其全局搜索能力。通過在九組不同特征數(shù)目的數(shù)據(jù)集上進(jìn)行測(cè)試,并與其它優(yōu)化算法的進(jìn)行比較,結(jié)果表明新的特征選擇方法在分類中能夠取得更好的效果。

[1]張麗新,王家欽,趙雁南,等.機(jī)器學(xué)習(xí)中的特征選擇[J].計(jì)算機(jī)科學(xué),2004,(11):180-184.

[2]周城,葛斌,唐九陽,等.基于相關(guān)性和冗余度的聯(lián)合特征選擇方法[J].計(jì)算機(jī)科學(xué),2012,(4):181-184.

[3]李志豪.基于離散粒子群算法的粗糙集屬性約簡(jiǎn)[J].工業(yè)控制計(jì)算機(jī),2016,(11):102-106.

[4]J. Kennedy, R. C. Eberhart. Particle swarm optimization[J].IEEE International Conference on Neural Networks,1995,(4):1942-1948.

[5]J Kennedy. Bare bones particle swarms[J].Swarm Intelligence Symposium,2003:80-87.

[6]J Kennedy , RC Eberhart. A discrete binary version of particle swarm algorithm[J].Systems, Man, and Cybernetics,1997,(5):4104-4108.