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

欒雨雨，王錫淮，肖健梅

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

1 引言

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

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

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

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

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

針對傳統(tǒng)粒子群約簡算法容易包含冗余屬性且容易發(fā)生早熟現(xiàn)象的缺點(diǎn)，本文提出混沌離散粒子群算法(CBPSO)，應(yīng)用于粗糙集屬性約簡問題?；煦鐑?yōu)化算法的引入，使粒子可以向多個(gè)方向搜索，增加種群的多樣性。同時(shí)改進(jìn)慣性因子和加速因子，提高了算法的全局搜索能力，使種群快速找到全局最優(yōu)解。實(shí)驗(yàn)證明，該算法可以在保持知識系統(tǒng)信息的條件下約簡更多的屬性，同時(shí)還可以提高分類精度和速度，是解決屬性約簡問題的有效方法。

2 粗糙集理論

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

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

(1)

(2)

(3)

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

(4)

(5)

(6)

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

(7)

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

3 混沌離散粒子群優(yōu)化算法

3.1 離散粒子群算法(BPSO)

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

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

+c2r2(pgm-xim(t))

(8)

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

(9)

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

(10)

(11)

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

為解決BPSO易早熟、陷入次優(yōu)解的缺點(diǎn)，引入混沌序列。常用的混沌模型為Logistic 模型，數(shù)學(xué)表示為

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

(12)

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

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

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

xim=ximin+zim(ximax-ximin)

(13)

(14)

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

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

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

3.3 加速因子和慣性因子的改進(jìn)

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

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

(15)

(16)

(17)

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

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

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

4.1 粒子位置的表示

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

4.2 粒子速度限制

CBPSO算法中，粒子速度最大值vmax可以決定搜索空間的精度。本文中，vmax=(1/4)*N，且速度范圍限制在[1，(1/4)*N]內(nèi)。當(dāng)vim<1時(shí)，令vim=1；當(dāng)vim>(1/4)*N時(shí)，令vim=(1/4)*N。在這個(gè)范圍內(nèi)，粒子通?？梢钥焖僬业阶顑?yōu)解。

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

本文的適應(yīng)度函數(shù)如式(18)所示

(18)

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

4.4 算法流程

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

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

輸出：決策表S的一個(gè)屬性約簡

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

步驟2：計(jì)算粒子的適應(yīng)度值fit(i)和個(gè)體最優(yōu)值pbest(i)，計(jì)算群體最優(yōu)值gbest。

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

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

步驟5：對種群中30%的最優(yōu)粒子增加混沌擾動，得到新的粒子。計(jì)算擾動后粒子的適應(yīng)度值gbest’，如果gbest’>gbest，則擾動后的粒子記錄為全局最優(yōu)點(diǎn)。

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

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

本文從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中挑選了4組數(shù)據(jù)，通過實(shí)驗(yàn)驗(yàn)證CBPSORS算法的有效性， 4組數(shù)據(jù)的基本說明見表1，其中KNN表示包含所有屬性的原始數(shù)據(jù)集的分類精度。

表1 實(shí)驗(yàn)中使用的UCI數(shù)據(jù)集

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

表2 算法參數(shù)設(shè)置

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

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

輸出：決策表S的一個(gè)屬性約簡

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

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

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

首先，將本文算法約簡后得到的數(shù)據(jù)集與原始數(shù)據(jù)集作比較，約簡前后的分類精度見表3?？梢钥闯觯糠?jǐn)?shù)據(jù)集的屬性約簡率達(dá)94%，且分類準(zhǔn)確率基本都有所提高。

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

最后，將本文算法與RS算法作比較，比較結(jié)果見表5?？梢?，在屬性個(gè)數(shù)和分類精度方面，本文算法優(yōu)勢明顯。

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

表3至表6從不同方面體現(xiàn)了本文算法的優(yōu)越性。說明了算法的搜索策略和屬性子集相關(guān)性的評價(jià)方法影響著屬性選擇的結(jié)果。

表3 約簡前后數(shù)據(jù)性能的比較

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

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

表6 四種算法對比結(jié)果

混沌優(yōu)化策略使種群的空間搜索更具多樣性，屬性子集的相關(guān)性評價(jià)策略使算法能找到更優(yōu)的子集。實(shí)驗(yàn)結(jié)果表明，本文算法保留了混沌優(yōu)化的優(yōu)點(diǎn)，又克服了傳統(tǒng)PSO算法的缺陷，可以很好地解決屬性約簡問題。在屬性約簡個(gè)數(shù)和分類準(zhǔn)確率方面，本文算法都有明顯的優(yōu)勢。

6 結(jié)語

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