基于量子云模型演化的最小屬性約簡增強算法

丁衛平 王建東 管致錦 施 佺

(1南京航空航天大學計算機科學與技術學院,南京210016)

(2南通大學計算機科學與技術學院,南通226019)

(3南京大學計算機軟件新技術國家重點實驗室,南京210093)

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

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

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

1 屬性約簡概念與模型

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

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

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

s.t.

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

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

2 基于約簡屬性熵權的逆向云生成算法

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

下面根據屬性約簡過程各條件屬性熵權大小給出相應逆向云生成算法,主要步驟如下:

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

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

④ 計算第i個條件屬性的熵權為

式中，Emax,Emin為條件屬性熵值中的最大值和最小值,則決策表條件屬性熵權集W={w1,w2,…,wn}.

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

3 基于云模型的量子進化算子

3.1 量子基因云編碼

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

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

3.2 量子云旋轉門

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

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

式中,i表示當前進化代數;Imax表示最大進化代數. Δθi的取值將保證量子種群染色體中所有量子比特都朝著與最優解對應的量子比特基態進行偏轉,使進化種群在定性知識指導下能夠自適應精細地搜索屬性空間范圍.

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

3.3 量子云變異

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

式中，0.05

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

3.4 量子云糾纏

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

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

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

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

圖1 QCMEARE算法核心步驟流程

5 仿真實驗與結果分析

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

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

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

圖3 QCMEARE算法屬性約簡精度穩定性分析

6 結語

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

)

[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]李德毅, 劉常昱. 論正態云模型的普適性[J].中國工程科學, 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]戴朝華, 朱云芳, 陳維榮,等. 云遺傳算法及其應用[J]. 電子學報, 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]劉禹,李德毅,張光衛,等. 云模型霧化特性及在進化算法中的應用[J]. 電子學報, 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]張光衛,何銳,劉禹,等. 基于云模型的進化算法[J]. 計算機學報,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.