基于混沌離散粒子群的粗糙集屬性約簡算法

欒雨雨，王錫淮，肖健梅

(上海海事大學物流工程學院，上海 201306)

1 引言

隨著大數據時代的到來，數據量激增。面對大量的數據，進行數據分析、分類與特征提取比較困難，需要有效的工具挖掘出數據中潛在有用的知識。數據挖掘中，屬性約簡是一個重要問題。屬性約簡是指在保持知識庫分類能力不變的情況下，刪除不重要或無關的屬性，從而降低數據的維度，簡化知識處理的過程[1]。

粗糙集理論(RST)是波蘭學者Z.pawlak在1982年提出的，用來處理不確定性和不完整性信息[2]。文獻[3]研究了基于粗糙集的屬性約簡算法，提出一種基于啟發式的依賴度計算方法，提高了RS約簡算法的運行速度。文獻[4]提出基于模糊粗糙集的屬性約簡算法，設計了一種貪婪收斂的約簡算法，實現了更好的性能。這些算法通常以屬性重要度或其它的重要信息作為啟發信息，依據一定的規則迭代運算，通常對計算有較高的要求，當數據量很大時，并不一定能得到最優子集。

為了提高RS約簡算法的精度，一些學者提出將智能算法與RS算法相結合。文獻[5]提出基于并行遺傳算法與粗糙集的特征選擇算法，減少了算法的運行時間，提高了分類器的精度。文獻[6]將魚群算法與鄰域粗糙集結合，定義三種魚群的覓食行為，以找到最佳屬性子集和適應度函數來評估最佳解，該算法更有可能找到最優約簡。文獻[7]提出一種混合人工蜂群算法，基于不可分辨原理，對粗糙集理論中的實值屬性進行約簡。文獻[8]提出一種結合飛蛾火焰的RS約簡算法，利用飛蛾火焰的探測能力和粗糙集的高性能進行屬性約簡，并應用于番茄病害的檢測，取得了不錯的效果。

粒子群算法(PSO)是一種通過模擬飛行鳥類的行為及其信息交換方式來解決優化問題的算法，具有運行速度快、易收斂的優點，更適合于維數較多的屬性約簡問題。文獻[9]提出基于粗糙集和粒子群的屬性約簡策略，并驗證了該算法比基于遺傳算法的約簡算法有更好的性能。然而傳統的粒子群優化算法容易陷入早熟現象，從而出現次優解。

為此，將混沌序列引入到粒子群優化算法?；煦缡欠蔷€性系統中的常見現象，一般情況下，由確定性方程得到的具有隨機性的運動狀態稱為混沌?；煦缇哂斜闅v性、無序性、隨機性、初始條件敏感等特性[10]。通過混沌優化，可以實現全局優化。因此，基于混沌的優化更有優勢。文獻[11]通過引入混沌優化算法和粒子群優化算法，提出一種新的最小二乘支持向量機的數據分類方法，實驗表明該方法有較好的分類能力，克服了傳統粒子群的缺點。

針對傳統粒子群約簡算法容易包含冗余屬性且容易發生早熟現象的缺點，本文提出混沌離散粒子群算法(CBPSO)，應用于粗糙集屬性約簡問題?；煦鐑灮惴ǖ囊?，使粒子可以向多個方向搜索，增加種群的多樣性。同時改進慣性因子和加速因子，提高了算法的全局搜索能力，使種群快速找到全局最優解。實驗證明，該算法可以在保持知識系統信息的條件下約簡更多的屬性，同時還可以提高分類精度和速度，是解決屬性約簡問題的有效方法。

2 粗糙集理論

在粗糙集理論中，定義一個知識表達系統S=(U，A，V，f)[12]。U稱為論域，是有限的非空對象集；A是有限的非空屬性集，A=C∪D，C和D分別為條件屬性集和決策屬性集；V=∪a∈AVa，Va是屬性a的值域；f：U×A→U是信息函數，使得對?a∈A，x∈U，有f(x，a)∈Va。

定義1[13]：給定一個論域U和U上的一簇等價關系S，若P?S，且P≠?，則∩P(P中所有等價關系的交集)仍然是論域U上的一個等價關系，稱為P上一個的不可分辨關系，記為IND(P)，也常簡記為P。而且

(1)

(2)

(3)

定義3[13]：在信息系統S=(U，A，V，f)中，對于每個子集X?U，X的P正域、P負域、P邊界域定義如下

(4)

(5)

(6)

定義4[14]：在信息系統S=(U，A，V，f)，(A=C∪D)中，條件屬性子集B∈C和決策屬性集D之間的依賴度定義如下

(7)

如果γB(D)=0，那么D獨立于B；如果γB(D)=1，那么D完全依賴于B；如果0<γB(D)<1，那么D部分依賴于B。

3 混沌離散粒子群優化算法

3.1 離散粒子群算法(BPSO)

BPSO算法是James Kennedy 和Russell C. Eberhart為解決離散優化問題提出的的。BPSO算法中，使用Sigmoid函數將連續的位置向量映射到離散空間。設xim(t)和vim(t)表示在第t次迭代時，粒子i的第m維的位置和速度分量，pim是粒子局部最優位置pbest的分量，pgm是全局最優位置gbest的分量，粒子的速度變化和標準PSO一樣，如式(8)所示

vim(t+1)=ωvid(t)+c1r1(pim-xim(t))

+c2r2(pgm-xim(t))

(8)

其中c1和c2是兩個正的加速常數，通常取c1=c2=2，r1和r2是取值在[0，1]的均勻隨機數。ω是慣性因子，通常根據式(9)進行設置。ωmax和ωmin分別是初始權重和最終權重，一般取ωmax=0.9，ωmin=0.4。t是當前迭代次數，T是最大迭代次數。

(9)

粒子的位置更新如式(10)、(11)所示

(10)

(11)

3.2 混沌離散粒子群算法(CBPSO)

為解決BPSO易早熟、陷入次優解的缺點，引入混沌序列。常用的混沌模型為Logistic 模型，數學表示為

zn+1=μzn(1-zn)，zn∈(0，1)，n=0，1，2，…

(12)

式中，μ表示控制參數，n表示迭代次數。當μ=4，z0∈(0，1)時，Logistic方程處于完全混沌狀態。

混沌序列主要通過以下兩方面與粒子群算法結合[15]。

一方面，利用混沌序列的隨機性初始化粒子。通過式(12)生成一組與粒子數相同的混沌序列：Zi=(zi1，…，zim，…，ziM)。通過式(13)生成第i個粒子的連續位置變量xim。通過式(14)將位置變映射到離散空間，則Xi=(xi1，…，xim，…，xiM)對應為一個離散粒子。

xim=ximin+zim(ximax-ximin)

(13)

(14)

ximax和ximin分別為粒子位置的上限和下限。

另一方面，在種群迭代過程中，對種群最優粒子增加混沌擾動。在迭代過程中，計算每個粒子的適應度值fit(i)，對fit(i)高的前30%的粒子增加混沌擾動。

通過混沌序列Zi生成新的離散粒子，計算新粒子的適應度值，用適應度值高的粒子替換原有粒子，改變粒子的搜索方向。

3.3 加速因子和慣性因子的改進

BPSO算法中，合理設置c1和c2以及ω的值可以平衡算法的全局搜索和局部搜索能力，使粒子快速地飛向最優解。

對于屬性約簡問題，搜索前期，需要粒子搜索更多的空間，即前期c1和ω應該較大。而在進化的后期，需要加強粒子間的信息交流以達到最優值，即后期c2和ω應該較大。因此，本文中c1、c2和ω如式(15)(16)(17)所示

(15)

(16)

(17)

其中c1m、c1M和c2m、c2M均為固定的常數，取c1m=0.5，c1M=2，c2m=2，c2M=2.5。

4 基于混沌離散粒子群的粗糙集屬性約簡算法

本文采用改進后的粒子群算法，結合粗糙集理論，求解屬性約簡問題。設種群是一個包含所有屬性子集的大的屬性空間，屬性空間中的每一個位置表示一個屬性子集。最優位置代表分類質量最好、屬性數量最少的那個子集?，F在，假設數據集的條件屬性個數為M，則搜索空間為M維，在搜索空間中放N個粒子，每個粒子都代表一個潛在的屬性子集。粒子的目標是搜索整個屬性空間，找到最優位置。

4.1 粒子位置的表示

CBPSO算法中，將粒子的位置表示為長度為M的二進制字符串，粒子位置的每一維表示一個屬性，1表示選擇相應的屬性，0表示該屬性未被選擇，每個位置都是一個條件屬性子集。

4.2 粒子速度限制

CBPSO算法中，粒子速度最大值vmax可以決定搜索空間的精度。本文中，vmax=(1/4)*N，且速度范圍限制在[1，(1/4)*N]內。當vim<1時，令vim=1；當vim>(1/4)*N時，令vim=(1/4)*N。在這個范圍內，粒子通?？梢钥焖僬业阶顑灲狻?/p>

4.3 適應度函數

本文的適應度函數如式(18)所示

(18)

其中，γB(D)是條件屬性子集B和決策屬性集D之間的依賴度，|B|是選擇的條件屬性子集中屬性的個數，|C|是條件屬性的總個數。α越大，表示算法約簡效果越好，越符合粗糙集的約簡標準。β越大，表示刪減掉的屬性數目越多。本文中，α=0.8，β=0.2。設置較大的α值可以保留決策表的知識信息。每個位置的適應度值都將通過這個函數進行評估，算法的標準是最大限度的提高粒子的適應度值[16]。

4.4 算法流程

算法1基于混沌離散粒子群的粗糙集屬性約簡算法

輸入：一個決策表S=(U，C∪D，V，f)

輸出：決策表S的一個屬性約簡

步驟1：輸入粒子個數、粒子維數、最大運行次數、速度限制、位置限制。利用logistic模型映射得到粒子初始速度和位置。

步驟2：計算粒子的適應度值fit(i)和個體最優值pbest(i)，計算群體最優值gbest。

步驟3：對每個粒子，如果fit(i)> pbest(i)，則令pbest(i)=fit(i)；如果fit(i)> gbest，則令gbest=fit(i)；并將該粒子的位置作為全局最優位置記錄下來。

步驟4：更新粒子的速度vi和位置xi。

步驟5：對種群中30%的最優粒子增加混沌擾動，得到新的粒子。計算擾動后粒子的適應度值gbest’，如果gbest’>gbest，則擾動后的粒子記錄為全局最優點。

步驟6 判斷是否滿足終止條件，若連續10次全局最優位置不變或迭代次數達到T=200時，則算法終止，輸出全局最優粒子，即約簡得到的屬性集；否則，轉步驟3。

5 實驗結果及分析

本文從UCI機器學習數據庫中挑選了4組數據，通過實驗驗證CBPSORS算法的有效性， 4組數據的基本說明見表1，其中KNN表示包含所有屬性的原始數據集的分類精度。

表1 實驗中使用的UCI數據集

本文選擇了一種基于粗糙集的屬性約簡算法(RS，算法2)；兩種基于粗糙集的智能屬性約簡算法：基于粒子群的粗糙集屬性約簡算法(PSORS)和基于遺傳算法的粗糙集屬性約簡算法(GARS)，來進行實驗，這些算法參數設置見表2。并采用10折交叉驗證的方法，基于k最近鄰算法為每個樣本生成分類模型，計算這些算法的分類精度。

表2 算法參數設置

算法2：基于粗糙集的屬性約簡算法

輸入：一個決策表S=(U，C∪D，V，f)，C={a1，a2，…，an}

輸出：決策表S的一個屬性約簡

步驟1：計算條件屬性集C的D正域POSC(D)。

步驟2：對于屬性ai∈C，計算條件屬性子集C-{ai}的D正域POSC-{ai}(D)。

步驟3：若POSC-{ai}(D)=POSC(D)，則說明屬性ai對于決策屬性集D不是必要的，可以刪減掉該屬性，轉步驟2。否則，說明屬性ai不能刪減，輸出屬性約簡集C。

首先，將本文算法約簡后得到的數據集與原始數據集作比較，約簡前后的分類精度見表3?？梢钥闯觯糠謹祿膶傩约s簡率達94%，且分類準確率基本都有所提高。

其次，將本文算法與兩種基于智能算法的粗糙集約簡算法(GARS、PSOARS)進行對比，所得屬性子集見表4。對于所有的數據集，本文算法都可以得到屬性數量最少的子集。

最后，將本文算法與RS算法作比較，比較結果見表5?？梢姡趯傩詡€數和分類精度方面，本文算法優勢明顯。

四種算法的比較結果見表6。對于所有的數據集，本文算法都能得到數量最少的屬性子集。而且對于KNN分類器，由本文算法約簡后的數據集分類精度最高。

表3至表6從不同方面體現了本文算法的優越性。說明了算法的搜索策略和屬性子集相關性的評價方法影響著屬性選擇的結果。

表3 約簡前后數據性能的比較

表4 三種智能約簡算法得到的屬性子集

表5 RS算法與CBPSORS算法的約簡比較

表6 四種算法對比結果

混沌優化策略使種群的空間搜索更具多樣性，屬性子集的相關性評價策略使算法能找到更優的子集。實驗結果表明，本文算法保留了混沌優化的優點，又克服了傳統PSO算法的缺陷，可以很好地解決屬性約簡問題。在屬性約簡個數和分類準確率方面，本文算法都有明顯的優勢。

6 結語

本文針對屬性約簡問題，提出了基于混沌離散粒子群的粗糙集屬性約簡算法，解決了傳統屬性約簡算法效率低的問題。該算法引入混沌優化策略，避免了傳統粒子群算法陷入次優解，提高了算法的全局搜索能力。同時改進加速因子和慣性因子提高算法的運行效率。最后使用粗糙集中依賴度的概念來評估生成屬性子集的相關性，通過交叉驗證得到的分類精度和屬性約簡個數來評估算法的性能。實驗結果表明，與RS、GARS和PSORS算法相比，本文算法可以提高粒子的利用率，有更好的約簡能力。對于相同的數據集，本文算法能得到數量更少的屬性子集和更高的分類質量。但是，本文算法是用單個函數作為適應度函數，未來可以使用多個標準來評估屬性子集，發展該算法的多目標版本。