基于粗糙超立方體和離散粒子群的特征選擇算法

王思朝，羅 川，李天瑞，陳紅梅

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065；2.西南交通大學(xué)計(jì)算機(jī)與人工智能學(xué)院，成都 611756）

引 言

面對(duì)日益增長(zhǎng)的數(shù)據(jù)維度和數(shù)據(jù)量，特征選擇以其能夠過(guò)濾冗余特征，對(duì)原始數(shù)據(jù)進(jìn)行降維，進(jìn)而提高學(xué)習(xí)效率和性能的特點(diǎn)，在文本挖掘［1］、圖像處理［2］和信息檢索［3］等諸多領(lǐng)域中都有著不可或缺的重要作用。一般來(lái)說(shuō)，過(guò)濾式、封裝式和嵌入式是目前特征選擇主要的3 種方法。過(guò)濾式特征選擇方法在評(píng)估特征質(zhì)量時(shí)，往往以某種評(píng)價(jià)準(zhǔn)則為依據(jù)排序特征，然后進(jìn)行挑選，該過(guò)程與學(xué)習(xí)算法無(wú)關(guān)，如Laplacian 得分［4］、Constraint 得分［5］等，或是基于某種搜索策略對(duì)優(yōu)化目標(biāo)進(jìn)行迭代求解，如基于前向搜索策略的mRMR［6］等。由于過(guò)濾式方法在特征選擇過(guò)程中并不需要構(gòu)建學(xué)習(xí)器對(duì)特征子集進(jìn)行評(píng)估，因此擁有較高的選擇效率。封裝式方法會(huì)先通過(guò)某種搜索方法獲取到特征子集，再由評(píng)價(jià)函數(shù)選取，最后采用學(xué)習(xí)算法對(duì)得到的特征子集進(jìn)行評(píng)估。封裝式方法中學(xué)習(xí)算法的選擇不盡相同，如常用的決策樹(shù)、貝葉斯等。該方法的求解結(jié)果比較好，主要是有學(xué)習(xí)算法的介入，但容易出現(xiàn)“過(guò)擬合”現(xiàn)象，即由貝葉斯選擇出來(lái)的特征子集在決策樹(shù)上的分類(lèi)效果往往不如人意。此外，構(gòu)建學(xué)習(xí)器對(duì)特征子集評(píng)估的開(kāi)銷(xiāo)較大，相對(duì)于過(guò)濾式會(huì)增加額外的時(shí)間消耗，從而效率低下。在嵌入式特征選擇方法中，伴隨著學(xué)習(xí)算法的構(gòu)建，最優(yōu)特征子集的求解也會(huì)一并進(jìn)行，即把特征選擇過(guò)程嵌入其中。但是由于嵌入式算法依賴于具體的學(xué)習(xí)算法，導(dǎo)致其通用性不佳［7］。

粗糙集理論以其在處理不精確和不完備數(shù)據(jù)的獨(dú)特優(yōu)勢(shì)，為不確定性特征選擇問(wèn)題提供了一套系統(tǒng)的基于決策語(yǔ)義保持的理論框架［8］。經(jīng)典粗糙集模型無(wú)法直接處理含有數(shù)值型數(shù)據(jù)的特征選擇任務(wù)，所以需要離散數(shù)據(jù)，但這個(gè)操作不可避免地會(huì)丟失部分特征信息。針對(duì)這一問(wèn)題，鄰域粗糙集［9］、模糊粗糙集［10］以及粗糙超立方體［11］等擴(kuò)展模型及方法被相繼提出，并被引入到面向數(shù)值型數(shù)據(jù)處理的特征選擇問(wèn)題中。然而，目前基于上述模型和方法的特征選擇算法中搜索策略均為前向搜索或后向消除的啟發(fā)式策略，無(wú)法得到全局最優(yōu)的特征子集。近年來(lái)，越來(lái)越多的元啟發(fā)式（Meta?heuristic）算法與粗糙集理論相結(jié)合被應(yīng)用于解決特征選擇問(wèn)題，特別是集群智能算法，包括粒子群優(yōu)化（Particle swarm optimization，PSO）［12］、人工蟻群優(yōu)化［13］等。Chen 等［14］通過(guò)條件與決策特征間的互信息定義出特征重要程度，進(jìn)而提出了基于蟻群優(yōu)化的特征選擇算法；Yamany 等［15］采用灰狼優(yōu)化算法作為搜索優(yōu)化方法，設(shè)計(jì)了基于粗糙集正區(qū)域的特征選擇算法；Chen 等［16］在鄰域粗糙集模型框架下選擇魚(yú)群優(yōu)化算法尋找最優(yōu)特征子集，可以很好地處理數(shù)值型數(shù)據(jù)。

粒子群優(yōu)化算法是集群智能算法中較為常用的方法之一。Wang 等［17］提出了一種基于粗糙正域的粒子群優(yōu)化算法，對(duì)比采用基因算法的粗糙集特征選擇算法有更好的表現(xiàn)；Bae 等［18］對(duì)傳統(tǒng)的粒子群優(yōu)化算法進(jìn)行了改進(jìn)，提出了一種新的稱為智能動(dòng)態(tài)集群的演化算法，同樣也是基于粗糙正域，但平均效率高于文獻(xiàn)［17］算法；Inbarani等［19］設(shè)計(jì)了一種基于粗糙集和粒子群優(yōu)化算法的相對(duì)約簡(jiǎn)和快速約簡(jiǎn)算法，并應(yīng)用于醫(yī)學(xué)診斷；Zhang 等［20］提出了一種基于鄰域粗糙集的離散粒子群優(yōu)化算法，用于解決基因特征選擇問(wèn)題。由于基于前向搜索策略的粗糙超立方體方法只能得到局部最優(yōu)結(jié)果，而計(jì)算所有特征子集組合開(kāi)銷(xiāo)過(guò)大，針對(duì)這一問(wèn)題，本文將離散粒子群優(yōu)化算法和粗糙超立方體方法相結(jié)合，提出了一種新穎的基于粗糙超立方體和離散粒子群的特征選擇算法（Feature selection based on rough hypercuboid and binary PSO，F(xiàn)SRHBPSO）。該算法在粒子生成階段引入了特征重要度這一先驗(yàn)知識(shí)，以提高收斂效率；并改進(jìn)了粗糙超立方體的目標(biāo)函數(shù)，消除了特征數(shù)量較多時(shí)導(dǎo)致特征相關(guān)度和重要度值過(guò)小的影響，用于優(yōu)化函數(shù)；最后引入了線性遞增的變異機(jī)制，使粒子不至于困入局部最優(yōu)解而無(wú)法逃脫。

1 相關(guān)基礎(chǔ)知識(shí)

本節(jié)闡述了粗糙超立方體方法的基本概念，并且介紹了離散粒子群的相關(guān)理論。

1.1 粗糙超立方體

假設(shè)論域U={u1，u2，…，un}是一個(gè)包含n個(gè)對(duì)象的集合，條件特征集C={A1，A2，…，Am}和決策特征集D=j5i0abt0b是一個(gè)非空的有限集合。由決策特征集D對(duì)論域U進(jìn)行劃分，得到等價(jià)類(lèi)U/D={β1，β2，…，βc}。條件特征Ak∈C相對(duì)于第i個(gè)等價(jià)類(lèi)βi的值域表示為區(qū)間[Li，Ui]，該區(qū)間包含了所有屬于等價(jià)類(lèi)βi的對(duì)象在Ak下的特征取值。

給定特征Ak，假設(shè)論域U相對(duì)于決策特征集D有c個(gè)等價(jià)類(lèi)，則定義超立方體等價(jià)劃分矩陣為H(Ak)=[hij(Ak)]，其中

等價(jià)類(lèi)βi在特征Ak下的粗糙近似集可由Ak的超立方體等價(jià)劃分矩陣和混淆向量表示為

則等價(jià)類(lèi)βi的邊界域定義為

條件屬性Ak和決策特征集D的依賴度定義為

式中0 ≤γAk(D)≤1。

給定兩個(gè)條件特征Ak、Al，特征子集{Ak，Al}的超立方體等價(jià)劃分矩陣可以計(jì)算為H({Ak，Al})=H(Ak)∧H(Al)，其中hij({Ak，Al})=hij(Ak)∧hij(Al)。

因此特征Ak相對(duì)于特征子集{Ak，Al}的重要度為

式中0 ≤σ{Ak，Al}(D，Ak)≤1。

根據(jù)上述定義，可以得到一些特征評(píng)估準(zhǔn)則，以選擇出特征間具有高重要度，特征與決策類(lèi)別具備高相關(guān)度和依賴度的最優(yōu)特征子集。

假設(shè)S(S?C)為已選特征子集，則它與決策特征集D的平均相關(guān)度為

特征子集S的平均重要度為

通過(guò)結(jié)合上述3 個(gè)特征評(píng)估準(zhǔn)則可以構(gòu)建出以下目標(biāo)函數(shù)，用于挑選最優(yōu)的特征子集，即

式中和λ為2 個(gè)權(quán)重參數(shù)。

特征選擇過(guò)程可以采用一種較為流行的前向搜索策略。依據(jù)目標(biāo)函數(shù)啟發(fā)式地挑選特征，直到所選特征數(shù)量滿足要求［11］。然而該方法搜索范圍僅限于部分特征空間，所得結(jié)果也只能看做是局部最優(yōu)。為了充分發(fā)揮粗糙超立方體方法的優(yōu)勢(shì)，依賴于離散粒子群優(yōu)化算法在整個(gè)特征空間中的搜索能力，將兩者相結(jié)合，提出了一個(gè)新的用于解決特征選擇問(wèn)題的組合優(yōu)化算法，以挑選出全局最優(yōu)的特征子集。

1.2 離散粒子群優(yōu)化算法

PSO 算法是Kennedy 等在1995 年提出［12］。該算法中粒子通過(guò)不斷學(xué)習(xí)自身和群體行為從而實(shí)現(xiàn)迭代優(yōu)化，具體過(guò)程為：在D維的問(wèn)題空間中，隨機(jī)產(chǎn)生1 組粒子，每個(gè)粒子可以認(rèn)為是該問(wèn)題的1 種可行的解決方案，并且用向量Xi=(xi1，xi2，…，xiD)和Vi=(vi1，vi2，…，viD)分別描述第i個(gè)粒子的位置和速度。另外，第i個(gè)粒子和整個(gè)群體在優(yōu)化搜索過(guò)程中，由目標(biāo)優(yōu)化函數(shù)計(jì)算得到的個(gè)體以及全局的最佳位置分別記作Pi=(pi1，pi2，…，piD)和Pg=(pg1，pg2，…，pgD)。搜索過(guò)程中，第i個(gè)粒子會(huì)依據(jù)式（11）和式（12）對(duì)其當(dāng)前位置和速度進(jìn)行重新計(jì)算，隨機(jī)移動(dòng)以尋找全局最優(yōu)的解決方案，即

為了將PSO 算法從連續(xù)空間應(yīng)用到離散搜索空間中的優(yōu)化問(wèn)題。Kennedy 等［21］進(jìn)一步設(shè)計(jì)出Bi?nary PSO（BPSO）算法。其中，粒子的位置向量可以用二進(jìn)制變量表示，即向量中的每1 位為1 或0。速度向量保持原有形式，不過(guò)其數(shù)值含義代表了粒子位置的某1 位將變?yōu)椤?”的概率，由Sigmoid 函數(shù)式（13）將速度向量的連續(xù)值映射到[0，1]，有

式中rand 為介于[0，1]間的隨機(jī)數(shù)。將BPSO 應(yīng)用于特征選擇問(wèn)題中，粒子位置向量的每一維就是1 個(gè)特征，值為1 表示特征被選擇。因此某一維速度越大，該對(duì)應(yīng)特征被選擇的概率也就越高。

2 本文方法

本文方法中每1 個(gè)粒子代表1 種特征選擇子集。針對(duì)隨機(jī)生成粒子，缺乏先驗(yàn)知識(shí)這一問(wèn)題，充分考慮了特征與決策類(lèi)的相關(guān)度作為粒子初始化的依據(jù)。此外本文還結(jié)合特征相關(guān)度、依賴度和重要度這3 種標(biāo)準(zhǔn)在實(shí)驗(yàn)過(guò)程中的實(shí)際表現(xiàn)情況，對(duì)評(píng)價(jià)標(biāo)準(zhǔn)式（10）進(jìn)行了改進(jìn)，作為優(yōu)化函數(shù)。鑒于合適的優(yōu)化函數(shù)可以幫助優(yōu)化算法挑選出性能最好的特征子集。本文還引入了遺傳算法中的變異機(jī)制，進(jìn)一步加強(qiáng)了粒子的搜索能力。

2.1 粒子編碼

粒子群中每個(gè)粒子的位置向量對(duì)應(yīng)1 個(gè)特征子集，那么分量就是1 個(gè)特征。分量的值僅為1 或0。當(dāng)特征子集包含某個(gè)特征時(shí)，相應(yīng)地分量值設(shè)為1，否則為0。所以二進(jìn)制位串代表1 種特征選擇模式，它的長(zhǎng)度應(yīng)該等于m，即原始特征的總個(gè)數(shù)。

2.2 粒子初始化

該階段會(huì)初始化I個(gè)粒子，I代表粒子群中粒子個(gè)數(shù)。粒子初始化對(duì)于PSO 算法收斂速度和結(jié)果質(zhì)量非常重要。不考慮先驗(yàn)知識(shí)，隨機(jī)生成1 組粒子雖然在一定程度上有益于尋找最優(yōu)結(jié)果，特別是處理一些高維的優(yōu)化問(wèn)題。但是不排除會(huì)出現(xiàn)一些粒子距離最優(yōu)特征子集過(guò)遠(yuǎn)，使得優(yōu)化算法收斂速度過(guò)慢。為解決該問(wèn)題，本文在粒子初始化階段考慮了特征與決策特征之間的相關(guān)度，并采用了概率的策略，位置向量的生成方法具體為

式中：xij為第i個(gè)粒子的第j維位置分量；γAj(D)為特征Aj與決策特征集D之間的相關(guān)度；rank(γAj(D))是指對(duì)所有特征的相關(guān)度降序排列后特征Aj相關(guān)度的序值。式（15）表明特征的相關(guān)度越高，那么該特征序值越小，被選擇的可能性越高，該特征對(duì)應(yīng)的位置分量為1 的概率也就越大。

2.3 參數(shù)設(shè)置

慣性權(quán)重w可以調(diào)節(jié)前一時(shí)刻的運(yùn)動(dòng)狀態(tài)與現(xiàn)在時(shí)刻速度的關(guān)系，同時(shí)決定了粒子的局部和全局搜索能力。一般來(lái)說(shuō)，希望粒子在前期能在特征解空間中快速找到最優(yōu)特征子集的大致范圍，然后再聚焦該范圍，找出最優(yōu)的特征選擇子集。因此，本文選取了線性遞減方法，其計(jì)算方式為

式中wmin和wmax為w的最小和最大值，需預(yù)先設(shè)定。式（16）說(shuō)明粒子在迭代初始運(yùn)動(dòng)速度較快，全局搜索能力較強(qiáng)。當(dāng)處于中后期時(shí)，速度會(huì)越來(lái)越小，有利于粒子很好地進(jìn)行局部范圍探索。

2.4 優(yōu)化函數(shù)

優(yōu)化函數(shù)決定了特征選擇的質(zhì)量，合適的優(yōu)化函數(shù)能幫助BPSO 選擇出更好的特征子集，即保證分類(lèi)能力的同時(shí)保留更少的特征規(guī)模。式（10）中粗糙超立方體方法的目標(biāo)函數(shù)雖然綜合考慮了特征子集的平均相關(guān)度、依賴度和平均重要度，適合作為優(yōu)化函數(shù)，但實(shí)驗(yàn)過(guò)程中，本文發(fā)現(xiàn)在處理實(shí)際數(shù)據(jù)集時(shí)，多數(shù)特征子集計(jì)算得到的平均相關(guān)度和平均重要度要遠(yuǎn)小于1，特別是所選擇的特征子集中特征的個(gè)數(shù)較多時(shí)。這就使得目標(biāo)函數(shù)中依賴度對(duì)特征子集的評(píng)估影響遠(yuǎn)大于平均相關(guān)度和重要度。出現(xiàn)這種情況的原因是3 種評(píng)價(jià)指標(biāo)的取值范圍不相同，結(jié)合式（7），平均相關(guān)度的取值范圍為

因此，為了保證3 種評(píng)價(jià)標(biāo)準(zhǔn)取值范圍相同，提高平均相關(guān)度和重要度對(duì)評(píng)價(jià)特征子集的作用，本文選擇將兩者進(jìn)行歸一化。另外，為了減少特征重要度在迭代時(shí)的重復(fù)計(jì)算，保證算法效率，本文選擇在迭代前計(jì)算出兩兩特征的重要度之和，用大小為m×m的特征重要度矩陣Sig={sigij}表示，其中

式中：1 ≤i，j≤m，sigij表示特征Ai相對(duì)于特征子集{Ai，Aj}的重要度與特征Aj相對(duì)于特征子集｛Ai，Aj｝的重要度之和。

因此，結(jié)合粗糙超立方體方法的目標(biāo)函數(shù)式（10），粒子群的優(yōu)化函數(shù)為

2.5 變異機(jī)制

BPSO 算法容易出現(xiàn)迭代后期陷入到局部最優(yōu)的情形，而且該算法本身缺少逃脫局部最優(yōu)解的機(jī)制，為了增加粒子搜索過(guò)程中的多樣性，本文引入了線性遞增的變異機(jī)制，有

式中：rmut為變異率；rmax、rmin為2 個(gè)預(yù)先設(shè)定值?？梢钥闯?，粒子的變異概率在優(yōu)化過(guò)程中會(huì)越來(lái)越大，相應(yīng)的局部搜索能力也會(huì)越來(lái)越強(qiáng)。

2.6 時(shí)間復(fù)雜度分析

算法1 概括了本文算法的主要步驟。在其運(yùn)行過(guò)程中，第1 步需要計(jì)算每個(gè)特征的粗糙超立方體等價(jià)劃分矩陣，該矩陣大小為n×c，c表示類(lèi)別數(shù)，那么其時(shí)間復(fù)雜度為O(mnc)。同樣地，第2 步中每個(gè)特征相關(guān)度的計(jì)算仍然基于粗糙超立方體等價(jià)劃分矩陣，其時(shí)間復(fù)雜度同樣為O(mnc)。第3 步中由于式（6）的計(jì)算只涉及兩個(gè)粗糙超立方體等價(jià)劃分矩陣的計(jì)算，時(shí)間復(fù)雜度為O(nc)，而式（17）中特征重要度矩陣中有m2個(gè)元素，則其時(shí)間復(fù)雜度為O(m2nc)。在第（5）～（13）步中，主要計(jì)算部分為步驟6中的優(yōu)化函數(shù)式（18），由于相關(guān)度和重要度已計(jì)算出，只需計(jì)算依賴度式（8）。而依賴度的計(jì)算與所選特征個(gè)數(shù)有關(guān)。最壞情況下，每個(gè)特征均被選中，這時(shí)對(duì)于每個(gè)粒子，式（18）所需要的時(shí)間復(fù)雜度為O(mnc)，共有I個(gè)粒子，并進(jìn)行了M次迭代，所以步驟（5）～（13）的時(shí)間復(fù)雜度為O(MImnc)。由以上分析可知，本文算法的時(shí)間復(fù)雜度為O(MImnc)。

算法1FSRHBPSO 算法

輸入：決策信息系統(tǒng)DT=＜U，C∪D＞，原始特征個(gè)數(shù)m，最大迭代次數(shù)M，粒子個(gè)數(shù)I，學(xué)習(xí)因子c1，c2，粒子速度、慣性權(quán)重和變異率的最小和最大值，即Vmin，Vmax，wmin，wmax和rmax，rmin，權(quán)重參數(shù)和λ；

輸出：特征子集S

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

本節(jié)選取了多個(gè)數(shù)據(jù)集和對(duì)比算法進(jìn)行特征選擇，并對(duì)所得子集用兩種不同的分類(lèi)器比較它們的平均性能。最終結(jié)果顯示，本文算法在大多數(shù)情況上，可在保證分類(lèi)質(zhì)量的同時(shí)具備更少的特征數(shù)量。

3.1 數(shù)據(jù)集

為了更好地測(cè)試本文算法性能，本文從UCI數(shù)據(jù)庫(kù)選擇了6 個(gè)數(shù)據(jù)集，它們規(guī)模和維度不一，類(lèi)別數(shù)目也有所差異，但均只包含數(shù)值型特征，具體描述如表1 所示。

表1 數(shù)據(jù)集描述Table 1 Details of datasets

3.2 參數(shù)和λ 的取值分析

將本文算法運(yùn)行在表1 中不同的數(shù)據(jù)集上，實(shí)驗(yàn)中參數(shù)和λ的取值均從0.0 開(kāi)始，以0.1 為間隔遞增至1.0，共有11×11 種組合，例如，其余的實(shí)驗(yàn)參數(shù)如表2 所示。由于BPSO 算法運(yùn)行結(jié)果具有隨機(jī)性，為了避免偶然誤差對(duì)實(shí)驗(yàn)結(jié)論的影響，本文算法在每個(gè)數(shù)據(jù)集和每種參數(shù)組合都進(jìn)行了10 次實(shí)驗(yàn)。此外，本文還選用了Weka［22］中的C4.5 和Naive Bayes 兩種分類(lèi)算法，采用10 次十折交叉驗(yàn)證的方法用于分類(lèi)精度的評(píng)估。圖1 和圖2 分別描繪了本文算法在不同的權(quán)重參數(shù)組合以及C4.5 和Naive Bayes 兩種分類(lèi)器下的平均分類(lèi)精度和特征選擇個(gè)數(shù)。從圖1、2 中可以看出，隨著參數(shù)逐漸減小，λ逐漸增大，除了圖1（a）和圖2（a）外，其余子圖的分類(lèi)精度都表現(xiàn)出逐步升高的整體趨勢(shì)，并在接近該點(diǎn)處又呈現(xiàn)下降趨勢(shì)。同樣地，當(dāng)參數(shù)逐漸減小，λ逐漸增大時(shí)，所有子圖的顏色也在由藍(lán)色逐步過(guò)渡到橙色，表明特征選擇的個(gè)數(shù)也在逐漸增加。結(jié)合優(yōu)化函數(shù)式（18）可發(fā)現(xiàn)減小、λ增大時(shí)，特征子集依賴度的權(quán)重變大，會(huì)引起分類(lèi)精度的提高，同時(shí)特征數(shù)量也會(huì)增加。雖然本文算法在不同數(shù)據(jù)集同一分類(lèi)器或同一數(shù)據(jù)集不同分類(lèi)器上取得最優(yōu)分類(lèi)精度的權(quán)重參數(shù)值都不統(tǒng)一，但是在和λ∈［0.6，0.9］時(shí)，大多數(shù)數(shù)據(jù)集在特征個(gè)數(shù)較少的同時(shí)，擁有較高的平均分類(lèi)精度。

圖1 FSRHBPSO 算法在6 個(gè)數(shù)據(jù)集(C4.5 分類(lèi)器)不同的參數(shù)和λ 組合下的平均分類(lèi)精度和特征選擇個(gè)數(shù)Fig.1 Average classification accuracy and the number of selected features over 6 datasets with C4.5 classifier and the different combinations of parameters and λ

圖2 FSRHBPSO 算法在6 個(gè)數(shù)據(jù)集(Naive Bayes分類(lèi)器)不同的參數(shù)和λ組合下的平均分類(lèi)精度和特征選擇個(gè)數(shù)Fig.2 Average classification accuracy and the number of selected features over six datasets with Naive Bayes classifier and the different combinations of parameters and λ

3.3 分類(lèi)精度實(shí)驗(yàn)比較與分析

表2 4 種算法的參數(shù)設(shè)置Table 2 Parameter settings of four algorithms

由于RS?PSO 和RS?IDS 算法無(wú)法直接處理數(shù)值特征，本文選擇Weka 工具中有監(jiān)督的Kononenko離散化方法，對(duì)實(shí)驗(yàn)所用數(shù)據(jù)集進(jìn)行離散。同樣地，為了避免隨機(jī)誤差對(duì)實(shí)驗(yàn)結(jié)果的影響，除RH 算法外的5 種算法在每個(gè)數(shù)據(jù)集上均進(jìn)行10 次獨(dú)立地特征選擇。表3 比較了在所有數(shù)據(jù)集上，5 種算法10次選擇結(jié)果的平均特征個(gè)數(shù)（avg）和不同結(jié)果個(gè)數(shù)（diff），其中平均個(gè)數(shù)最小的結(jié)果加粗表示。此外，由于NRS?DPSO 算法的優(yōu)化函數(shù)是基于正區(qū)域的，所以當(dāng)生成的粒子群在迭代優(yōu)化過(guò)程中不存在與條件特征集合的正區(qū)域相等的粒子時(shí)，便會(huì)無(wú)法得到有效的特征子集，結(jié)果為空集，這里用“-”表示。同時(shí)由于RH 算法需要指定特征選擇的個(gè)數(shù)，除了數(shù)據(jù)集Texture 設(shè)置為7 外，其余數(shù)據(jù)集上均與本文算法所選特征個(gè)數(shù)保持一致，以驗(yàn)證在相同特征子集大小下，本文算法是否有更好的性能。

表3 特征子集大小比較Table 3 Comparison of the number of feature subsets

從表3 可以看出，就平均特征個(gè)數(shù)而言，本文算法在6 個(gè)數(shù)據(jù)集的特征個(gè)數(shù)都要少于RS?PSO、RS?IDS 和NRS?DPSO 算法，特別是在SpectfHeart 數(shù)據(jù)集上，本文算法的約簡(jiǎn)率為9.09%，而RS?PSO、RS?IDS 和NRS?DPSO 的約簡(jiǎn)率分別為36.36%，61.59%和24.77%。以外，除了在Wdbc 數(shù)據(jù)集上，本文算法的特征選擇個(gè)數(shù)均小于GBNRSFS 算法，尤其是在數(shù)據(jù)集Texture 和Satimage 上，GBNRSFS 算法的約簡(jiǎn)率分別是56.25%和69.72%，而本文算法的約簡(jiǎn)率僅為18%和16.67%。就10 次選擇結(jié)果中不同特征子集個(gè)數(shù)而言，RS?PSO、RS?IDS 和NRS?DPSO 三種粒子群算法的平均值分別為7.33，9.67 和7.67。這是由于它們很容易陷入局部最優(yōu)解，從而導(dǎo)致10 次獨(dú)立實(shí)驗(yàn)最終收斂的結(jié)果各不相同。而GBNRSFS 算法的值為8.5，這是其中k?means 算法聚類(lèi)結(jié)果的不確定造成的，從而使得特征選擇結(jié)果并不統(tǒng)一。而本文算法除了在數(shù)據(jù)集Segment 和Texture 上得到2 種不同的特征子集外，在其余數(shù)據(jù)集上均只有1 種結(jié)果，這是因?yàn)楸疚乃惴ㄖ械淖儺悪C(jī)制允許粒子以一定概率逃脫局部最優(yōu)，從而可以收斂到全局最優(yōu)的情況?？偟膩?lái)說(shuō)，本文算法相對(duì)于其余算法具有較強(qiáng)的穩(wěn)定性和全局搜索能力。本文進(jìn)一步對(duì)6 種算法的特征選擇結(jié)果進(jìn)行平均分類(lèi)精度的比較，同樣用到了Weka 中的C4.5 和Naive Bayes 兩種分類(lèi)器和10 次十折交叉驗(yàn)證的方法。表4、5 列出了6 種算法的特征子集分別在C4.5 和Naive Bayes分類(lèi)器上平均分類(lèi)精度的比較結(jié)果。

表4 特征子集在C4.5 分類(lèi)器上平均分類(lèi)精度的比較Table 4 Comparison of average classification accuracy of feature subsets using C4.5 classifier

從表4 結(jié)果來(lái)看，在C4.5 分類(lèi)器的平均分類(lèi)精度上，本文算法只有在Texture 和Satimage 數(shù)據(jù)集上略低于GBNRSFS 算法，但是結(jié)合特征選擇個(gè)數(shù)來(lái)看，本文算法在特征選擇個(gè)數(shù)約為GBNRSFS 算法特征個(gè)數(shù)的1/3 和1/4 的情況下，與其平均分類(lèi)精度僅相差0.878 6%和0.038 2%，不足1%。在6 個(gè)數(shù)據(jù)集上，相對(duì)于其余4 個(gè)對(duì)比算法，本文算法的平均分類(lèi)精度都要更高。具體來(lái)說(shuō)，本文算法在Ionosphere 上相對(duì)于RH、RS?PSO、RS?IDS、NRS?DPSO 和GBNRSFS 算法的平均分類(lèi)精度分別提高了1.604 0%，3.438 7%，4.025 8%，2.287 7%和5.868 9%。從平均結(jié)果上看，本文算法的平均分類(lèi)精度相對(duì)于RH、RS?PSO、RS?IDS 和GBNRSFS 算法分別提高了1.889 2%，1.318 2%，1.718 6%和1.237%；在前3 個(gè)數(shù)據(jù)集上，本文算法比NRS?DPSO 也有1.157 2%的提升。

同樣地，表5 結(jié)果顯示本文算法在Naive Bayes 分類(lèi)器上仍然優(yōu)于其他算法，尤其是在Segment 和Texture 兩個(gè)數(shù)據(jù)集上。在Segment 上，本文算法相對(duì)于RH、RS?PSO、RS?IDS 和GBNRSFS 算法的平均分類(lèi)精度分別有5.747 2%，5.224 6%，10.167 5%和10.582 3%的提高；在Texture 上，相對(duì)其他算法分別提高了7.592 2%，3.300 9%，8.302%和4.852 9%。最后從所有數(shù)據(jù)集的平均結(jié)果來(lái)看，本文算法相對(duì)于RH、RS?PSO、RS?IDS 和GBNRSFS 算法仍有較大幅度的優(yōu)勢(shì)，具體為3.186 0%，3.058 4%，4.682 8%和6.408 5%；在前3 個(gè)數(shù)據(jù)集上，NRS?DPSO 的平均分類(lèi)精度要低于本文算法3.108 9%。總體而言，在多數(shù)數(shù)據(jù)集上，F(xiàn)SRHBPSO 算法在C4.5 和Naive Bayes 分類(lèi)器的表現(xiàn)都要優(yōu)于另外5 種算法。

表5 特征子集在Naive Bayes 分類(lèi)器上平均分類(lèi)精度的比較Table 5 Comparison of average classification accuracy of feature subsets using Naive Bayes classifier

4 結(jié)束語(yǔ)

本文采用了適用于二元空間的離散粒子群優(yōu)化算法，引入粗糙超立方體方法中相關(guān)度的概念在粒子初始化階段加入了先驗(yàn)知識(shí)；同時(shí)添加變異機(jī)制，豐富了優(yōu)化算法搜索過(guò)程中的多樣性。此外還根據(jù)實(shí)驗(yàn)過(guò)程中粗糙超立方體3 種評(píng)估標(biāo)準(zhǔn)的實(shí)際表現(xiàn)情況，對(duì)目標(biāo)函數(shù)進(jìn)行了改進(jìn)，并將改進(jìn)后的目標(biāo)函數(shù)與離散粒子群優(yōu)化算法相結(jié)合，設(shè)計(jì)了新的基于離散粒子群和粗糙超立方體的特征選擇算法。最后實(shí)驗(yàn)結(jié)論表明該算法能在保證分類(lèi)質(zhì)量的同時(shí)選擇出數(shù)量更少的特征子集。同時(shí)相比前向搜索策略的粗糙超立方體方法及其他粒子群算法具有更好的性能。下一步工作考慮將該算法與云計(jì)算相結(jié)合，以增強(qiáng)算法面對(duì)大規(guī)模數(shù)據(jù)的計(jì)算能力。