基于相關(guān)族方法的特征選擇算法

謝棚宇， 楊 田， 代建華

(1. 中南林業(yè)科技大學(xué) 物流與交通學(xué)院 湖南 長沙 410004； 2. 湖南師范大學(xué) 智能計(jì)算與語言信息處理湖南省重點(diǎn)實(shí)驗(yàn)室 湖南 長沙 410081； 3.國防科技大學(xué) 系統(tǒng)工程學(xué)院 湖南 長沙 410073)

0 引言

突發(fā)事件是指在短時間內(nèi)突然發(fā)生、對社會和人民群眾的生命財(cái)產(chǎn)安全產(chǎn)生嚴(yán)重影響的事件。一般而言，突發(fā)事件數(shù)據(jù)的屬性集中存在大量冗余信息，可能會掩蓋突發(fā)事件信息系統(tǒng)中各要素的關(guān)系，影響應(yīng)急決策的質(zhì)量和效率。因此，需要對突發(fā)事件信息系統(tǒng)進(jìn)行有效的屬性約簡，以達(dá)到刪除冗余或不必要屬性、減少突發(fā)事件響應(yīng)時間和提高決策準(zhǔn)確性的目的。文獻(xiàn)[1-3]利用粗糙集理論[4]對各類突發(fā)事件進(jìn)行了屬性約簡，提高了分類的質(zhì)量。粗糙集的主要思想是在保持分類能力不變的情況下，通過知識約簡導(dǎo)出問題的決策或分類規(guī)則。利用粗糙集理論的屬性約簡一般采用區(qū)分矩陣[5]、鄰域粗糙集[6]、信息熵[7]等工具，但利用這些方法提出的約簡理論不能適用于所有的覆蓋粗糙集模型的屬性約簡。針對這一難題，文獻(xiàn)[8]基于逼近空間提出相關(guān)族方法，解決了M逼近空間覆蓋粗糙集模型的屬性約簡問題。此外，突發(fā)事件積累了大量的數(shù)據(jù)，而基于相關(guān)族方法設(shè)計(jì)的屬性約簡算法能快速地得到約簡結(jié)果，運(yùn)行時間短。因此，本文以粗糙集理論和相關(guān)族方法為基礎(chǔ)，針對突發(fā)事件的屬性約簡問題提出相應(yīng)的約簡理論和算法，將決策表中一致和非一致兩種情況整合為統(tǒng)一框架，進(jìn)而利用相關(guān)族理論對決策表進(jìn)行屬性約簡，在此基礎(chǔ)上設(shè)計(jì)了啟發(fā)式約簡算法，并對恐怖襲擊事件數(shù)據(jù)集進(jìn)行了實(shí)例分析。

1 相關(guān)概念

1.1 粗糙集

為避免在處理數(shù)值型數(shù)據(jù)過程中發(fā)生數(shù)據(jù)內(nèi)部結(jié)構(gòu)改變、數(shù)據(jù)挖掘性能下降和離散化產(chǎn)生誤差等問題，文獻(xiàn)[9]提出了覆蓋粗糙集模型。設(shè)U為一個非空有限論域，C為U的一個非空子集族，若∪C=U，則稱C為U上的一個覆蓋，序?qū)?U,C)稱為覆蓋逼近空間。

定義1(極小描述、鄰域、逼近空間)[10]令C為U上的一個覆蓋，MdC(x)={K∈C|x∈K∧(?S∈C∧x∈S∧S?K)?K=S}稱為x的極小描述，MC=∪{MdC(x)|x∈C }稱為覆蓋C的M逼近空間。NC(x)=∩{C∈C|x∈C}稱為x的鄰域，NC={NC(x)|x∈C}稱為覆蓋C的N逼近空間。當(dāng)不引起混淆時，可以省略下標(biāo)C。

定義2(第一型逼近算子)[10]令C為U上的一個覆蓋，對任意的X?U,集合CLC(X)=∪{K∈C|K?X}和FHC(X)=CLC(X)∪(∪{Md(x)|x∈X-CLC(X)})分別稱為X的下近似和上近似。當(dāng)不引起混淆時，可以省略下標(biāo)C。

具有條件屬性和決策屬性的知識表達(dá)系統(tǒng)稱為決策表。若條件屬性中對象的關(guān)系表現(xiàn)為覆蓋C，則決策表為覆蓋決策表，記為S=(U,Δ,D)，其中Δ={C1, C2,…,Cn}為論域U上的一個覆蓋族。

1.2 覆蓋粗糙集的屬性約簡

屬性約簡的目標(biāo)就是尋找保持信息系統(tǒng)分類能力不變的屬性極小子集，但此時的逼近方式或空間卻沒有發(fā)生改變。本文的屬性約簡基于覆蓋決策表，即研究條件屬性所產(chǎn)生的分類相對于決策屬性所產(chǎn)生的分類之間的關(guān)系，產(chǎn)生的屬性約簡記為相對屬性約簡。相對屬性約簡有兩個重要概念：相對約簡和相對核(簡稱為約簡和核)。

定義4(約簡、核) 設(shè)S=(U,Δ,D)是一個覆蓋決策表，其中Δ={C1,C2,…,Cn}是論域U上的一個覆蓋族。對任意的Ci∈Δ，若POSΔ(D)?POSΔ-{Ci}(D)，則Ci在Δ中關(guān)于D不必要；否則，Ci在Δ中關(guān)于D必要。對于每一個P?Δ，若POSΔ(D)?POSP(D)，并且P的任意一個覆蓋都是必要的，稱P是Δ相對于D的一個屬性約簡。Δ中所有必要關(guān)系組成的集合稱為Δ的相對核，記為CORE(Δ)。Δ中所有約簡的集合記為RED(Δ)。

1.3 相關(guān)族

在粗糙集屬性約簡理論中，區(qū)分矩陣是最經(jīng)典的工具之一，其被廣泛地應(yīng)用到N逼近空間類型的覆蓋粗糙集屬性約簡中。在對M逼近空間類型的覆蓋粗糙集進(jìn)行屬性約簡時，區(qū)分矩陣這一工具不再適用，而相關(guān)族方法能對逼近空間為MC的覆蓋粗糙集模型進(jìn)行屬性約簡。因此，本文基于第一型覆蓋粗糙集模型和相關(guān)族方法對突發(fā)事件數(shù)據(jù)進(jìn)行屬性約簡。下面基于覆蓋決策表給出相關(guān)族的定義，覆蓋決策表分為一致和非一致兩種情況，為節(jié)省時間，在屬性約簡之前不再區(qū)分?jǐn)?shù)據(jù)是否一致，并將一致和不一致覆蓋決策表整合為統(tǒng)一框架，在此框架上討論相關(guān)族理論。

定義5令(U,Δ,D)為一個覆蓋決策表，其中U={x1,x2,…,xn}，S (U,Δ,D)={Ck∈∪Δ|?Xi∈U/Ds.t. Ck?Xi}稱為(U,Δ,D)的有效逼近集合，有效逼近集合中的對象稱為有效信息粒。

定義6令(U,Δ,D)為一個覆蓋決策表，S (U,Δ,D)為有效逼近集合，則對任意的xi∈∪S(U,Δ,D)，有

1)r(xi)={C∈Δ|?Ck∈S (U,Δ,D) s.t.xi∈Ck∈C}稱為xi的相關(guān)集合；

2)R(U,Δ,D)={r(xi)|xi∈Δ}稱為決策表(U,Δ,D)的相關(guān)族。

定理1令(U,Δ,D)為覆蓋決策表，P∈Δ，則

1) 對任意的xi∈S (U,Δ,D)，當(dāng)且僅當(dāng)P∩r(xi)≠?，有POS∪Δ(D)=POS∪P(D)；

2) 對于某些xi∈U，有CORE(Δ)={C∈Δ|r(xi)={C }}。

證明1) 假設(shè)POS∪Δ(D)=POS∪P(D)，對任意的xi∈∪S (U,Δ,D)，有?K∈S (U,P,D)={K|K∈∪P且?X∈U/D}，其中xi∈K。即有C∈P使得xi∈K∈C。因?yàn)镻∈Δ，很明顯C∈r(xi)，所以(C∈r(xi))∩P≠?。假設(shè)對任意的xi∈∪S (U,Δ,D)，有P∩r(xi)≠?，則存在C∈P使得C∈r(xi)，故∪S (U,Δ,D)=∪S (U,P,D)，所以POS∪Δ(D)=POS∪P(D)。

2) 假設(shè)C∈CORE(Δ)，則說明C在Δ是必要的，即POS∪Δ(D)≠POS∪(Δ-C )(D)，存在xi∈U使得xi?∪{K|K∈∪(Δ-{C })且?X∈U/Ds.t.K?X}。因此，r(xi)={C }。如果對那些xi∈U有r(xi)={C }，很明顯有C∈CORE(Δ)。

以上定義闡述了相關(guān)族方法的基本思想，在求覆蓋決策表的屬性約簡時，相關(guān)族引入了布爾函數(shù)。

定理2令(U,Δ,D)為覆蓋決策表，f(U,Δ,D)為其相關(guān)方程。若g(U,Δ,D)為f(U,Δ,D)通過乘法律和吸收率得到的極小析取范式，即g(U,Δ,D)=(∧P1)∨…∨(∧Pm)，Pk?P,k=1,2,…,m且Pk中的任意元素至多出現(xiàn)一次，則RED(Δ)={P1,P2,…,Pm}。

2 基于相關(guān)族的快速屬性約簡算法

2.1 數(shù)據(jù)預(yù)處理

本文進(jìn)行屬性約簡的基礎(chǔ)是覆蓋決策表，若數(shù)據(jù)集的數(shù)據(jù)類型表現(xiàn)為混合數(shù)據(jù)或連續(xù)型數(shù)據(jù)，需對其進(jìn)行預(yù)處理使之形成覆蓋。對于連續(xù)型屬性下的對象xi(i=1,2,…,m)，首先對其進(jìn)行歸一化處理，使屬性值取值區(qū)間為[0,1],K(xi)={xj|d(xi,xj)≤δ}稱為關(guān)于對象xi形成的信息粒，其中：d(xi,xj)=|a(xi)-a(xj)|；δ是區(qū)間為[0,1]的可調(diào)節(jié)參數(shù)。若屬性為符號型，則K(xi)={xj|a(xi)=a(xj)}。單個屬性下所有K(xi)的集合形成了關(guān)于該屬性的覆蓋。

2.2 基于相關(guān)族的快速屬性約簡算法

本文提出的基于相關(guān)族的快速屬性約簡算法分為兩步。首先求得覆蓋決策表的相關(guān)族(Step 1)，再在相關(guān)族的基礎(chǔ)上求得決策表的屬性約簡結(jié)果(Step 2)。at∈A(t=1,2,…,n)表示屬性，xi∈U(i=1,2,…,m)表示對象，[xi]at表示對象xi在屬性at中根據(jù)δ形成的信息粒，[xi]D表示對象xi所在的決策類，|r(xi)|表示該集合的勢，‖at‖表示屬性at在R(U,Δ,D)中出現(xiàn)的頻次，算法的具體步驟如下。

Step1在覆蓋決策表上生成相關(guān)族。

輸入：決策表S(U,A,D)，參數(shù)δ；

輸出：相關(guān)族R(U,Δ,D)；

① 令R(U,Δ,D)=?,r(xi)=?

② forat∈A,Pt=?

③ forxi∈U,r(xj)=?

④if 存在xj∈U-[xi]D使得|at(xi)-at(xj)|≤δ

則[xi]at和[xj]at為無效粒子

⑤ else [xi]at為有效粒子

計(jì)算[xi]at，Pt=Pt∪[xi]at

⑥ end if

⑦ end for

⑧ ifxj∈Pt

⑨r(xj)=r(xj)∪{at}

Step2基于相關(guān)族得到屬性約簡。

輸入：相關(guān)族R(U,Δ,D)；

輸出：約簡RED；

① 令CORE=?,RED=?

② forr(xi)∈R(U,Δ,D)

③ if |r(xi)|=1

④CORE=CORE∪r(xi);從R(U,Δ,D)中刪去r(xi)

⑤ end if

⑥ end for

⑦RED=CORE

⑧ whileR(U,Δ,D)≠?

⑨ if ‖at‖=max{‖a‖|a∈A}

⑩RED=RED∪{at}

⑩ end if

記對象個數(shù)為m，屬性個數(shù)為n。在本文提出的屬性約簡算法中，Step 1計(jì)算相關(guān)族的時間復(fù)雜度為O(m2n/2)，Step 2計(jì)算屬性約簡的時間復(fù)雜度為O(min{m,n})，因此本算法的時間復(fù)雜度為O(m2n/2+min{m,n})。其中在計(jì)算相關(guān)族時，考慮到2個對象之間的距離關(guān)系是對稱的，當(dāng)xi與xj不在同一決策類，而|d(xi,xj)|≤δ，此時由xi生成的信息粒視為無效信息粒，根據(jù)對稱性，xj所在的信息粒也視為無效信息粒，因此Step 1的時間復(fù)雜度為O(m2n/2)。當(dāng)判斷信息粒為無效粒子時，運(yùn)算中斷，此過程不會生成完整的信息粒。因此，實(shí)際計(jì)算量會遠(yuǎn)小于復(fù)雜度中的計(jì)算量。

3 實(shí)驗(yàn)分析

所有實(shí)驗(yàn)均在同一設(shè)備、同一環(huán)境下進(jìn)行。其中設(shè)備運(yùn)行系統(tǒng)為macOS10.14.4，處理器為2.7 GHz Intel Core I7，內(nèi)存為8 GB，實(shí)驗(yàn)所用軟件為Matlab R2018a。利用5個公開數(shù)據(jù)集來檢驗(yàn)本文算法的有效性，突發(fā)事件實(shí)例分析數(shù)據(jù)為環(huán)球恐怖主義數(shù)據(jù)集GTD。

3.1 算法有效性檢驗(yàn)

為驗(yàn)證本文算法的有效性，利用5個公開數(shù)據(jù)集與文獻(xiàn)[6]中基于鄰域粗糙集的NRS算法、文獻(xiàn)[7]中基于信息熵的HANDI算法、文獻(xiàn)[11]中基于區(qū)分矩陣的CDG算法進(jìn)行屬性約簡對比實(shí)驗(yàn)，對比項(xiàng)包括數(shù)據(jù)集的分類精度及約簡時間。判斷數(shù)據(jù)集分類精度的工具為支持向量機(jī)(SVM)和決策樹ID3，對比結(jié)果如表1、表2所示。在實(shí)驗(yàn)過程中，除CDG算法在對數(shù)據(jù)集texture進(jìn)行屬性約簡時，由于超出設(shè)備內(nèi)存而不能得到約簡結(jié)果外，其他算法對5個數(shù)據(jù)集均能計(jì)算出約簡結(jié)果。經(jīng)本文算法約簡后的數(shù)據(jù)集分類精度與初始精度相比，約簡結(jié)果均能保持或提升分類精度；與其他幾種算法約簡得到的分類精度進(jìn)行對比，也僅存在細(xì)微差別，約簡結(jié)果基本保持一致，證明了本文算法的有效性。在約簡時間對比上，本文算法具有明顯的時間優(yōu)勢，特別是對對象個數(shù)較多的大型數(shù)據(jù)集，時間差距更為明顯。因此，若將本文算法應(yīng)用于突發(fā)事件數(shù)據(jù)的屬性約簡，能極大地縮短得到關(guān)鍵因素的時間，協(xié)助救援機(jī)構(gòu)快速判斷突發(fā)事件的危害等級，以開展對應(yīng)等級的救援活動。

表1 不同算法的分類精度對比Table 1 Comparisons of classification accuracy of different algorithms 單位：%

表2 不同算法的約簡時間對比Table 2 Comparisons of reduction time of different algorithms 單位：s

圖1 分類精度及屬性個數(shù)在參數(shù)δ下的變化趨勢Figure 1 Variation of classification accuracies and number of attributes with δ

3.2 恐怖襲擊事件實(shí)例分析

恐怖襲擊事件數(shù)據(jù)記錄了大量的情景與襲擊后果信息，若能刪除恐怖襲擊事件中的冗余知識，則可以明確屬性因素與襲擊后果的關(guān)系，有利于決策者根據(jù)少量關(guān)鍵情景因素做出判斷，實(shí)施相應(yīng)救援調(diào)度。環(huán)球恐怖主義數(shù)據(jù)集GTD獲取了1998—2017年近20年的恐怖襲擊的詳盡內(nèi)容，包含了大量的文本屬性和相似描述屬性，且很多對象屬性值為缺失值，不利于后續(xù)進(jìn)行約簡實(shí)驗(yàn)。因此，對數(shù)據(jù)集GTD進(jìn)行了處理，并得到了關(guān)于環(huán)球恐怖主義事件危害程度的決策表，該決策表有對象35 415個，屬性26個，其中條件屬性25個。用本文算法對決策表進(jìn)行屬性約簡，總約簡時間約為2 160.704 s，分類精度及屬性個數(shù)在參數(shù)δ下的變化趨勢如圖1所示?？梢钥闯?，當(dāng)鄰域變量δ在區(qū)間[0,1.0]變化時，約簡后的分類精度在區(qū)間[86.2%,87.9%]變動。當(dāng)δ=0.9時，SVM分類器下分類精度的最優(yōu)值為87.84%；當(dāng)δ=0.85時，ID3分類器下分類精度的最優(yōu)值為87.83%。兩種分類器最優(yōu)精度對應(yīng)的約簡結(jié)果相同，約簡后均剩余3個屬性，分別為受傷總?cè)藬?shù)、人質(zhì)總數(shù)、贖金支付總數(shù)。數(shù)據(jù)集GTD基于SVM和ID3分類器的原始分類精度分別為85.76%和85.57%。對比發(fā)現(xiàn)，約簡后的分類精度提升了2%左右，而原決策表的條件屬性個數(shù)由25個降至3個。

同樣地，本文也利用3.1小節(jié)的對比算法對恐怖襲擊事件數(shù)據(jù)進(jìn)行屬性約簡，數(shù)據(jù)集GTD的約簡結(jié)果對比如表3所示。CDG和HANDI算法由于所要求的計(jì)算空間超出設(shè)備內(nèi)存而無法計(jì)算，NRS算法只有在參數(shù)δ=0時得到約簡結(jié)果，其單次約簡時間約為1 853.54 s，為本文算法單次約簡時間(102.89 s)的18.01倍。NRS算法的分類精度均低于本文算法約簡后的分類精度。因此，根據(jù)算法的有效性檢驗(yàn)和恐怖襲擊事件實(shí)例分析可知，本文算法對數(shù)據(jù)集進(jìn)行屬性約簡后，不僅能繼續(xù)保持甚至提高分類精度，且相較于其他高效的屬性約簡算法具有明顯的時間優(yōu)勢。當(dāng)突發(fā)事件發(fā)生時，本文算法能幫助決策者或救援機(jī)構(gòu)快速地找到關(guān)鍵影響因素，減少數(shù)據(jù)收集的難度，使得決策者能根據(jù)有限的屬性判斷突發(fā)事件的危害等級，做出合理的救援決策。

表3 數(shù)據(jù)集GTD的約簡結(jié)果對比Table 3 Comparisons of reduction results of GTD dataset

4 小結(jié)

本文在相關(guān)族理論的基礎(chǔ)上提出了基于第一型覆蓋粗糙集的屬性約簡理論，設(shè)計(jì)了啟發(fā)式屬性約簡算法，并與現(xiàn)有的幾種有效算法進(jìn)行了比較。結(jié)果表明，本文算法能快速地進(jìn)行屬性約簡，縮短知識發(fā)現(xiàn)的時間，節(jié)省存儲空間。對數(shù)據(jù)規(guī)模較大的恐怖襲擊事件數(shù)據(jù)集進(jìn)行了實(shí)例分析，結(jié)果表明，該算法能快速地刪除數(shù)據(jù)庫中大量的冗余屬性，提高了約簡后數(shù)據(jù)分類的精度，提取出恐怖襲擊事件數(shù)據(jù)的關(guān)鍵屬性，降低了突發(fā)事件發(fā)生時數(shù)據(jù)收集的難度。此外，在該數(shù)據(jù)集存在屬性值缺失、信息不完備的情況下，本文算法依舊可以得到滿意的結(jié)果，說明此方法能解決此類不完備信息系統(tǒng)的屬性約簡問題，其實(shí)際應(yīng)用性更加廣泛。