丁衛(wèi)平 王建東 管致錦 施 佺

(1南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京210016)

(2南通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南通226019)

(3南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,南京210093)

屬性約簡是粗糙集理論[1]中一個重要的研究內(nèi)容,其主要任務(wù)是在保證知識庫分類和決策能力不變的條件下, 刪除不相關(guān)或不重要的屬性.現(xiàn)有大部分屬性約簡研究工作主要是采用基于代數(shù)表示與信息表示的相關(guān)方法[2-3],由于Wong[4]等已證明求決策表的最小屬性約簡是一個NP-hard問題,因此要設(shè)計(jì)一種通用且高效的最小屬性約簡算法相當(dāng)困難.進(jìn)化算法作為一類有效的全局優(yōu)化技術(shù),通過模擬或揭示某些自然現(xiàn)象或過程而得到迅速發(fā)展,在解決NP-hard問題上顯示出較強(qiáng)的優(yōu)勢.近年來,一些學(xué)者為了改善傳統(tǒng)屬性約簡方法的不足,相繼開展了一些基于生物進(jìn)化算法的啟發(fā)式屬性約簡方法的研究,如Slezak等[5]提出了基于遺傳算法序列的近似熵屬性約簡算法;Jensen等[6]提出了基于蟻群優(yōu)化算法的粗糙屬性約簡方法;Ye等[7]提出了基于二進(jìn)制粒子群優(yōu)化的最小屬性約簡算法.上述屬性約簡算法能充分利用進(jìn)化算法搜索最優(yōu)解的優(yōu)勢,較好地進(jìn)行最小屬性約簡中最優(yōu)值的演化求解,然而這些屬性約簡算法往往也無法避免一般進(jìn)化算法易出現(xiàn)的早熟收斂和進(jìn)化停滯等問題,在求最小屬性約簡集時效率和精度大大降低.

云模型是一種定性知識描述和定性概念與其定量數(shù)值表示間的不確定性轉(zhuǎn)換模型,主要反映客觀世界事物或人類知識中概念的模糊性、隨機(jī)性,并把兩者完全集成在一起[8].云模型理論的隨機(jī)性可避免搜索陷入局部極值,而其穩(wěn)定傾向性又可很好地定位全局最優(yōu)值.近年來,融合云模型和進(jìn)化計(jì)算的云進(jìn)化算法引起了國內(nèi)外學(xué)者的關(guān)注.如戴朝華等[9]利用云發(fā)生器代替?zhèn)鹘y(tǒng)遺傳算法中的交叉、變異算子, 提出了一種全新的云遺傳算法;劉禹等[10]利用云模型的超熵變化控制進(jìn)化策略來模擬進(jìn)化選擇壓力和控制進(jìn)化基因頻率,提出了基于云模型霧化特性的進(jìn)化算法;張光衛(wèi)等[11]采用云模型對物種遺傳變異進(jìn)行統(tǒng)一建模,提出了基于云模型的進(jìn)化算法.上述研究表明采用云模型對進(jìn)化算法進(jìn)行優(yōu)化,可使其在定性知識的指導(dǎo)下能自適應(yīng)控制搜索空間范圍,具有快速的收斂速度和較強(qiáng)的全局搜索能力.

量子進(jìn)化算法具有獨(dú)特的相干性、疊加性和并行性等,能快速提高進(jìn)化算法尋求最優(yōu)解的速度,近年來受到眾多學(xué)者的高度關(guān)注[12].本文將云模型理論和量子進(jìn)化算法進(jìn)行融合并引入到粗糙集最小屬性約簡領(lǐng)域,提出了一種基于量子云模型演化的最小屬性約簡增強(qiáng)算法(QCMEARE).該算法能更好地發(fā)揮云模型和量子進(jìn)化算法在最小屬性演化約簡過程中的全局尋優(yōu)性能和最小約簡求解效率,實(shí)驗(yàn)結(jié)果表明其最小屬性約簡是高效和實(shí)用的.

1 屬性約簡概念與模型

定義2在決策表S=(U,C∪D,V,f)中,對于?B∈C,存在POSB(D)=POSC(D),且若?ci∈B,POSB-{ci}(D)≠POSC(D),則稱B為C相對于D基于正區(qū)域的屬性約簡.

定義3在決策表S=(U,C∪D,V,f)中,C相對于D所有基于正區(qū)域的屬性約簡集為PR(C),Core(C)=∩PR(C)為基于正區(qū)域的核.

定義5屬性演化約簡模型是將進(jìn)化種群個體編碼成“0-1”組合形式,設(shè)條件屬性C的勢Card(C)=N,則其編碼表示為X={x1,x2,…,xN}∈{0,1}N,其中“1”表示對應(yīng)屬性被選中,“0”表示對應(yīng)屬性未被選中.

s.t.

x∈{0,1}N,γξ(x)=γC, Core(ξ(x))=ξ(x)

上述優(yōu)化目標(biāo)模型可利用二進(jìn)制優(yōu)化算法進(jìn)一步求解,設(shè)一個確定的布爾向量X={x1,x2,…,xN}∈{0,1}N代表一個種群個體,xi(i=1,2,…，N)表示種群中標(biāo)號為i的個體,N為進(jìn)化種群中個體總數(shù).

2 基于約簡屬性熵權(quán)的逆向云生成算法

云模型[8]所表達(dá)概念的整體特性可用云的3個數(shù)字特征來反映,即期望Ex、熵En和超熵He,記作(Ex,En,He).逆向云算法是云模型中的一個關(guān)鍵算法,它是將一定數(shù)量的精確數(shù)據(jù)有效轉(zhuǎn)換為以恰當(dāng)定性語言值(Ex,En,He)表示的概念,其輸入為n個云滴在數(shù)域空間的精確位置和每個云滴代表該概念的確定度,輸出則為這n個云滴表示定性概念的期望值Ex、熵En和超熵He.

下面根據(jù)屬性約簡過程各條件屬性熵權(quán)大小給出相應(yīng)逆向云生成算法,主要步驟如下:

① 根據(jù)屬性決策表S=(U,C∪D,V,f)構(gòu)建一個判斷矩陣R,即R=(ri,j)n×m(i=1,2,…,n;j=1,2,…,m),其中m為條件屬性C的個數(shù)，n為決策屬性D的個數(shù).

③ 將m個條件屬性和n個決策屬性所確定的屬性熵值定義為

④ 計(jì)算第i個條件屬性的熵權(quán)為

式中，Emax,Emin為條件屬性熵值中的最大值和最小值,則決策表?xiàng)l件屬性熵權(quán)集W={w1,w2,…,wn}.

⑤ 輸入n個云滴集合X={x1,x2,…,xn}和條件屬性熵權(quán)值集合W={w1,w2,…,wn},將各條件屬性確定的屬性熵權(quán)視作為每個云滴代表該屬性的確定度.

3 基于云模型的量子進(jìn)化算子

3.1 量子基因云編碼

在量子進(jìn)化算法中, 使用一對復(fù)數(shù)(α,β)定義一個量子比特位.一個具有k個量子比特位的種群可用長度為k的量子染色體(2k個態(tài))形式描述如下:

一個量子染色體可表征為解空間中任意解的疊加態(tài),在此采用基于約簡屬性熵權(quán)的逆向云生成算法完成數(shù)值空間到概念空間的轉(zhuǎn)換,用云模型模擬一個進(jìn)化種群中所有量子個體同一個基因的分布特征,并定義其為該種群的一個基因云.基因云是一個種群中個體基因值的定性表示,反映了種群基因的整體統(tǒng)計(jì)特征,量子進(jìn)化種群第i個基因的基因云可記為(Exi,Eni,Hei).這樣進(jìn)化過程中可利用定性進(jìn)化策略對種群進(jìn)化操作進(jìn)行定性控制,即通過調(diào)整種群基因云參數(shù)(Exi,Eni,Hei)來優(yōu)化子代種群的產(chǎn)生,并對染色體編碼,使種群多樣化,防止其陷入局部最優(yōu).通過上述策略使進(jìn)化種群在基因云定性知識指導(dǎo)下自適應(yīng)控制屬性約簡空間搜索范圍.

3.2 量子云旋轉(zhuǎn)門

根據(jù)約簡屬性熵權(quán)逆向云算法生成的(Exi,Eni,Hei),本文提出了一種自適應(yīng)的量子云旋轉(zhuǎn)角調(diào)整方法.在進(jìn)化初期,旋轉(zhuǎn)角θi根據(jù)逆向云生成的(Exi,Eni,Hei),將進(jìn)化個體適應(yīng)度f(x)i與當(dāng)前迭代中最優(yōu)適應(yīng)度f(b)i、全局最優(yōu)適應(yīng)度f(B)進(jìn)行比較,自適應(yīng)確定旋轉(zhuǎn)角,從而迅速完成全局搜索,使當(dāng)前迭代中的最優(yōu)解不斷趨近于全局最優(yōu)解.隨著種群進(jìn)化代數(shù)增加,旋轉(zhuǎn)角θi呈指數(shù)減小,從而種群轉(zhuǎn)向局部的精細(xì)化搜索.量子旋轉(zhuǎn)角計(jì)算公式定義如下:

式中,Δθi表示量子種群染色體中第i個量子比特與基態(tài)間的角距離,其定義為

式中,i表示當(dāng)前進(jìn)化代數(shù);Imax表示最大進(jìn)化代數(shù). Δθi的取值將保證量子種群染色體中所有量子比特都朝著與最優(yōu)解對應(yīng)的量子比特基態(tài)進(jìn)行偏轉(zhuǎn),使進(jìn)化種群在定性知識指導(dǎo)下能夠自適應(yīng)精細(xì)地搜索屬性空間范圍.

該量子旋轉(zhuǎn)角θi將進(jìn)化種群個體適應(yīng)度f(x)與當(dāng)前迭代中最優(yōu)適應(yīng)度f(b)i、全局最優(yōu)適應(yīng)度f(B),分別與云模型的(Exi,Eni,Hei) 3個特征進(jìn)行有效結(jié)合,可更加自適應(yīng)地調(diào)整量子旋轉(zhuǎn)角及其旋轉(zhuǎn)門,使進(jìn)化種群在云模型定性知識指導(dǎo)下自適應(yīng)調(diào)整屬性空間搜索范圍,有效地平衡全局搜索與局部搜索之間的矛盾,最終使得進(jìn)化種群穩(wěn)定而高效地收斂于全局最優(yōu)值.

3.3 量子云變異

量子進(jìn)化過程的變異操作可提升算法擺脫局部極值的性能,加速其全局收斂.本文采用基于約簡屬性熵權(quán)的逆向云模型設(shè)計(jì)動態(tài)變異概率,增強(qiáng)量子種群跳出局部極值的能力,以保證進(jìn)化的方向性和種群的多樣性.量子云變異操作隨著種群進(jìn)化,其個體退化程度將降低,變異概率將逐漸減小,以更好地保持前期所探索的解.

式中，0.05

量子云變異概率Pm的確定同時考慮了進(jìn)化種群的3個極值(f(x)i,f(b)i和f(B))和逆向云模型定性表示(Exi,Eni,Hei)的值,通過量子云變異操作更改相應(yīng)量子比特態(tài)疊加狀態(tài),使量子進(jìn)化算法穩(wěn)定而高效地收斂到全局最優(yōu)解.

3.4 量子云糾纏

量子進(jìn)化種群在量子云變異Pm后,結(jié)合逆向云的3個特征(Exi,Eni,Hei)和量子云旋轉(zhuǎn)角θi對操作進(jìn)行量子糾纏,第i個量子位上任意2個量子比特a,b的量子云糾纏算子定義為

量子進(jìn)化種群采用上述量子云糾纏可較好地進(jìn)行非定域量子門的定性操作,極大地提高其糾纏的成功幾率,使進(jìn)化種群在定性知識指導(dǎo)下能夠自適應(yīng)快速進(jìn)化.

4 基于量子云模型演化的最小屬性約簡增強(qiáng)算法

基于上述設(shè)計(jì)的量子云模型演化算子,根據(jù)粗糙集中最小屬性約簡模型,本文提出了一種基于量子云模型演化的最小屬性約簡增強(qiáng)算法(QCMEARE),其核心思想為:首先將屬性約簡集映射至進(jìn)化種群空間,然后基于約簡屬性熵權(quán)生成的逆向云模型,在逆向云模型3個特征(Exi,Eni,Hei)的定性指導(dǎo)下進(jìn)行量子種群基因云編碼,并結(jié)合種群精英量子個體進(jìn)行量子旋轉(zhuǎn)角自適應(yīng)調(diào)整、量子云變異和量子云糾纏操作,使進(jìn)化種群在定性知識指導(dǎo)下自適應(yīng)控制約簡屬性空間搜索范圍,較好地搜索到全局最優(yōu)解.該QCMEARE算法能夠在粗糙屬性約簡過程中盡可能地減少所包含的屬性數(shù)目,充分發(fā)揮云模型和量子進(jìn)化算法在最小屬性演化約簡過程中的全局尋優(yōu)性能,獲得較理想的最小屬性約簡集.該算法核心步驟流程如圖1所示.

圖1 QCMEARE算法核心步驟流程

5 仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證QCMEARE算法在屬性約簡優(yōu)化方面的性能,本文進(jìn)行了基于典型UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫[13]屬性演化約簡性能比較實(shí)驗(yàn).實(shí)驗(yàn)平臺為:Microsoft Windows 2003 Server,MSSQL Server 2005,Visual Studio 2008 C#.NET開發(fā)工具,Intel雙核CPU 1.66 GHz,1 GB內(nèi)存,120 GB硬盤.對比算法選取2種典型的快速屬性約簡算法:BPSOAR算法[7]和 PS-FS算法[14].以5倍的原數(shù)據(jù)代替其相應(yīng)數(shù)據(jù)集進(jìn)行大規(guī)模數(shù)據(jù)量擴(kuò)展決策表測試,在每個擴(kuò)展數(shù)據(jù)集上進(jìn)行20次交叉驗(yàn)證,實(shí)驗(yàn)結(jié)果為去除最初1次和最后1次,中間18次實(shí)驗(yàn)結(jié)果的平均值.圖2給出了其中5個UCI數(shù)據(jù)集取得最小屬性約簡集時平均約簡精度和約簡時間值.從圖中可看出,QCMEARE算法在5個UCI數(shù)據(jù)集上均取得了較好的約簡性能,其約簡精度普遍高于其他2種算法,尤其在Exactly和Mushroom數(shù)據(jù)集上平均約簡時間明顯低于其他2種算法,如在Mushroom數(shù)據(jù)集上,QCMEARE算法的屬性約簡平均時間為2.4 s, 而其他2種算法為4.0和6.1 s.這表明QCMEARE算法在屬性約簡過程中較好地解決了一般基于進(jìn)化的屬性算法所面臨的精度與效率沖突問題,從而獲得了較為滿意的屬性約簡效果, 提高了其實(shí)際可用性.

圖2 不同算法在UCI數(shù)據(jù)集上屬性演化約簡性能比較

圖3(a)、(b)是QCMEARE算法與BPSOAR, PS-FS算法在大規(guī)模Vehicle, Postoperative數(shù)據(jù)集上隨著屬性約簡器數(shù)量增加其屬性約簡精度穩(wěn)定性比較分析.從圖中可看出，QCMEARE算法在屬性約簡器數(shù)量動態(tài)增加時,約簡精度基本呈上升趨勢且精度值較高,逐步達(dá)到平穩(wěn)狀態(tài),這表明QCMEARE算法在粗糙屬性約簡時具有較好的穩(wěn)定性.

圖3 QCMEARE算法屬性約簡精度穩(wěn)定性分析

6 結(jié)語

云模型克服了模糊數(shù)學(xué)用精確、唯一的隸屬函數(shù)嚴(yán)格表示模糊概念的缺點(diǎn),在定性與定量之間相互轉(zhuǎn)換時具有較好的特性.量子進(jìn)化算法具有獨(dú)特的量子相干性、變異性和糾纏性,能快速提高進(jìn)化種群全局最優(yōu)解的搜索能力.本文融合兩者優(yōu)勢提出了一種基于量子云模型演化的最小屬性約簡增強(qiáng)算法QCMEARE.相關(guān)實(shí)驗(yàn)結(jié)果及其分析表明，本文提出的QCMEARE算法是可行的和高效的,其屬性約簡效率和精度較其他算法具有明顯的增強(qiáng)優(yōu)勢.接下來將更深入地研究量子云進(jìn)化算法的自適應(yīng)性及其理論基礎(chǔ),以進(jìn)一步增強(qiáng)屬性演化約簡算法的性能.

)

[1]Pawlak Z. Rough sets[J].InternationalJournalofComputerandInformationSciences, 1982,11(5): 341-356.

[2]Wang G Y. Rough reduction in algebra view and information view[J].InternationalJournalofIntelligentSystems, 2003,18(6): 679-688.

[3]Yao Yiyu, Zhao Yan. Attribute reduction in decision-theoretic rough set models [J].InformationSciences, 2008,178(17): 3356-3373.

[4]Wong S K M, Ziarko W. On optimal decision rules in decision tables[J].BulletinofPolishAcademyofScience, 1985,33(11): 693-696.

[5]Slezak D, Wroblewski J. Order based genetic algorithms for the search of approximate entropy reducts[C]//ProceedingsofRSFDGrC’2003. Chongqing, China, 2003: 308-311.

[6]Jensen R, Shen Q. Finding rough set reducts with ant colony optimization [C]//Proceedingsofthe2003U.K.WorkshoponComputationalIntelligence. Bristol, UK, 2003:15-22.

[7]Ye Dongyi, Chen Zhaojiong, Liao Jiankun. A new algorithm for minimum attribute reduction based on binary particle population optimization with vaccination[C]//Proceedingsofthe11thPacific-AsiaConferenceonAdvancesinKnowledgeDiscoveryandDataMining. Nanjing, China, 2007: 1029-1036.

[8]李德毅, 劉常昱. 論正態(tài)云模型的普適性[J].中國工程科學(xué), 2004, 6(8):28-33.

Li Deyi, Liu Changyu. Study on the universality of the normal cloud model[J].EngineerandScienceofChina, 2004,6(8): 28-33. (in Chinese)

[9]戴朝華, 朱云芳, 陳維榮,等. 云遺傳算法及其應(yīng)用[J]. 電子學(xué)報(bào), 2007,35(7):1419-1424.

Dai Chaohua, Zhu Yunfang, Chen Weirong, et al. Cloud model based genetic algorithm and its applications[J].ActaElectronicaSinica, 2007,35(7): 1419-1424. (in Chinese)

[10]劉禹,李德毅,張光衛(wèi),等. 云模型霧化特性及在進(jìn)化算法中的應(yīng)用[J]. 電子學(xué)報(bào), 2009, 37 (8):1651-1658.

Liu Yu, Li Deyi,Zhang Guangwei, et al. Atomized feature in cloud based evolutionary algorithm[J].ActaElectronicaSinica, 2009,37(8):1651-1658. (in Chinese)

[11]張光衛(wèi),何銳,劉禹,等. 基于云模型的進(jìn)化算法[J]. 計(jì)算機(jī)學(xué)報(bào),2008,31(7):1082-1091.

Zhang Guangwei, He Rui, Liu Yu, et al. An evolutionary algorithm based on cloud model[J].ChineseJournalofComputers,2008,31(7):1082-1091. (in Chinese)

[12]Zhang G X. Quantum-inspired evolutionary algorithms: a survey and empirical study[J].JHeuristics, 2011,17(3): 303-335.

[13]Asuncion A, Newman D J. UCI repository of machine learning databases [EB/OL]. (2007-06) [2012-09-20]. http://www.ics. uci.edu/～mlearn/mlrepository.

[14]Chen Yumin, Miao Duoqian, Wang Ruizhi, et al. A rough set approach to feature selection based on power set tree[J].Knowledge-BasedSystems, 2011,24(2): 275-281.