基于可辨識集消解策略的覆蓋決策系統(tǒng)約簡算法

林榮德， 李進金,2， 陳東曉， 黃建新， 施晗娟

(1. 華僑大學(xué) 計算科學(xué)福建省高校重點實驗室 數(shù)學(xué)科學(xué)學(xué)院 福建 泉州 362000； 2. 閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院 福建 漳州 363000)

0 引言

特征選擇或?qū)傩约s簡是數(shù)據(jù)挖掘及機器學(xué)習(xí)中一種重要的數(shù)據(jù)預(yù)處理方法。在信息系統(tǒng)中數(shù)據(jù)對象的性質(zhì)是通過一系列屬性表達的，而其中部分屬性可能與對象的性質(zhì)無關(guān)。屬性約簡就是去除與保持某種分類性質(zhì)無關(guān)的屬性的過程。由Pawlak提出的粗糙集理論[1-2]作為一種重要理論工具在屬性約簡、規(guī)則提取、數(shù)據(jù)挖掘和知識發(fā)現(xiàn)中得到了多種應(yīng)用。經(jīng)典粗糙集通常只適合處理離散型的數(shù)據(jù)，當(dāng)處理連續(xù)數(shù)值型數(shù)據(jù)時需要先將其離散化，該操作會造成信息損失，因此鄰域粗糙集方法[3]被提出并運用于處理連續(xù)數(shù)值型數(shù)據(jù)和離散型數(shù)據(jù)的屬性約簡[4-10]。近年來，對連續(xù)數(shù)值型數(shù)據(jù)以及信息缺失的數(shù)據(jù)采用基于覆蓋粗糙集[11-13]的方法進行屬性約簡等方面的研究也已有許多研究成果[14-22]。

對象之間的可辨識集是指形成它們之間的可辨識關(guān)系所依賴的屬性、特征或其他要素等所構(gòu)成的集合。Skowron和Rauszer[23]建立了基于可辨識關(guān)系的屬性約簡理論框架。Yao等[24]提出通過屬性重要度將辨識矩陣轉(zhuǎn)化為最簡辨識矩陣從而得到屬性約簡的方法，但未給出得到各屬性重要度的方法。葛浩等[25]研究了信息粒度和辨識能力的關(guān)系，通過計算各屬性之間的相對辨識能力直接從信息系統(tǒng)得到約簡屬性集。楊蕾等[26]研究了在序決策系統(tǒng)中用辨識函數(shù)構(gòu)造一種樹型結(jié)構(gòu)，并利用其優(yōu)勢關(guān)系的分配性質(zhì)得到約簡集的啟發(fā)式算法。 陶玉枝等[27]研究了基于辨識矩陣的屬性約簡問題與集覆蓋求解問題的等價性，擴展了辨識矩陣的求解方法。在高效構(gòu)造辨識集的研究方面，楊濤等[28]提出了辨識矩陣的壓縮表示方法及相應(yīng)屬性集求核算法。 Wei等[29]和Ma等[30]分別研究了動態(tài)數(shù)據(jù)集中屬性增加時用增量法構(gòu)造辨識矩陣的問題，以及采用壓縮的布爾向量來存儲對象的可辨識集的屬性約簡算法。Chen等[31]研究了在覆蓋決策系統(tǒng)中建立對象之間的超鏈接圖來表達可辨識關(guān)系并進行屬性約簡的算法。此外，在不協(xié)調(diào)信息系統(tǒng)、序決策信息系統(tǒng)和概念格的屬性約簡中高效構(gòu)造辨識矩陣的問題等方面的研究有了啟發(fā)性的結(jié)果[32-34]。但上述工作主要針對可辨識集的構(gòu)造方法，或根據(jù)屬性之間的條件信息熵及相對優(yōu)勢關(guān)系確定屬性重要度等問題。

為了進一步挖掘覆蓋決策系統(tǒng)的可辨識集中所包含的信息來獲取約簡集，本文首先根據(jù)覆蓋決策系統(tǒng)協(xié)調(diào)覆蓋集與可辨識集簇之間的聯(lián)系，提出覆蓋在可辨識集簇中的相對辨識能力的概念，給出相對辨識能力下的覆蓋核心集的相關(guān)性質(zhì)。接下來給出可辨識集簇在給定覆蓋下進行消解操作的定義，得到提取最大辨識能力的覆蓋，然后對可辨識集簇進行消解的逐次“提取-消解”的迭代，直到可辨識集簇被完全消解最終得到約簡覆蓋集，同時對算法的正確性和計算復(fù)雜性進行分析。最后將若干UCI數(shù)據(jù)集轉(zhuǎn)化為覆蓋決策系統(tǒng)，并運用本算法進行了屬性約簡實驗，驗證了所提出算法的有效性。

1 覆蓋決策信息系統(tǒng)相關(guān)概念

本文的論域U={x1,x2,…,xn}為有限集,C={K1,K2,…,Kn}為U的冪集的一個子集。如果C上每一個集合K均為非空，且滿足∪{K|K∈C}=U，則稱C為U上的一個覆蓋。以下給出來自于文獻[11]和文獻[15]的覆蓋粗糙集相關(guān)定義和定理。

定義1[11]設(shè)C為U上的一個覆蓋，即∪{K|K∈C}=U,對于任意x∈U，令(x)C=∩{K∈C|x∈K},則稱Cov(C)={(x)C|x∈U}為覆蓋C所誘導(dǎo)的一個覆蓋。

定義2[11]設(shè)A為U上的一簇覆蓋，B={C1,C2,…,Cm}?A，對于任意x∈U，稱

(x)B=∩{K|x∈K,K∈Ci,i=1,2,…,m}

為x在覆蓋簇B下的鄰域。并稱覆蓋Cov(B)={(x)B|x∈U}為覆蓋簇B誘導(dǎo)的U上的一個覆蓋。

定理1[11]對于任意B?A，x,y∈U有性質(zhì)

1)y∈(x)C當(dāng)且僅當(dāng)(y)B?(x)B； 2) (x)B=∩C∈B(x)C； 3) (x)A?(x)B； 4) (x)B=(x)Cov(B)。

給定(U,A,D)的決策覆蓋D={K1,K2,…,Km}，對于任意Ki∈D，根據(jù)定義3有

因此下近似約簡集的求解可以按照上近似約簡集的求解方法進行。本文以下內(nèi)容僅考慮上近似協(xié)調(diào)覆蓋集或約簡集，并記Core(A,D)為上近似核心覆蓋集。

定義5[15]設(shè)(U,A,D)為覆蓋決策信息系統(tǒng)，對于任意x,y∈U，x相對于y的可辨識集

并稱L={d(x,y)|d(x,y)≠?，x,y∈U}為覆蓋決策信息系統(tǒng)(U,A,D)的可辨識集簇。

定理2[15]設(shè)L為(U,A,D)覆蓋決策信息系統(tǒng)的可辨識集簇，則有性質(zhì)1)、2)：

1)B為(U,A,D)的協(xié)調(diào)覆蓋集，當(dāng)且僅當(dāng)對于任意d(x,y)∈L，有B∩d(x,y)≠?;

2)C是(U,A,D)的核心覆蓋元C∈Core(A,D)，當(dāng)且僅當(dāng)存在d(x,y)∈L,d(x,y)={C}。

定理2在覆蓋決策信息系統(tǒng)(U,A,D)的協(xié)調(diào)覆蓋集與對象之間的可辨識關(guān)系中建立了一種聯(lián)系。其中1)指出了覆蓋決策信息系統(tǒng)(U,A,D)的可辨識集簇L中每個可辨識集d(x,y)必定包含協(xié)調(diào)覆蓋集B?A中的某些覆蓋，這說明出現(xiàn)在可辨識集d(x,y)中的某些覆蓋對于辨識對象x、y所起的影響。而2)則進一步強調(diào)了約簡覆蓋集B?A中的核心覆蓋對于辨識集d(x,y)非空的重要性。

2 覆蓋的辨識能力及可辨識集的消解

本節(jié)內(nèi)容將給出一種覆蓋C∈A相對于可辨識集簇L的辨識重要度和辨識影響度，以及覆蓋C∈A在可辨識集簇L上的消解等概念及相應(yīng)性質(zhì)。

定義6給定可辨識集簇L={d1,d2,…,dm}，其中每一個di表示覆蓋決策信息系統(tǒng)(U,A,D)中一個非空可辨識集d(x,y)≠?，對于任意覆蓋C∈A，d∈L，記

令CapL(C)=(SigL(C),ScaleL(C)), 稱CapL(C)為覆蓋C相對于可辨識集簇L的辨識能力(簡稱覆蓋的辨識能力)，并記Cap(L)={CapL(C)|C∈A}。

定義7給定任意兩個覆蓋C1和C2相對于L的辨識能力CapL(C1)=(SigL(C1),ScaleL(C1))和CapL(C2)=(SigL(C2),ScaleL(C2))，則CapL(C1)≥CapL(C2)當(dāng)且僅當(dāng)SigL(C1)>SigL(C2)，或，SigL(C1)=SigL(C2)且ScaleL(C1)≥ScaleL(C2)，并記max(L)={C∈A|CapL(C)≥cap,?cap∈Cap(L)}，表示L中具有最大辨識能力的覆蓋構(gòu)成的集合。

從上述定義6可知，如果L中某個可辨識集是由單覆蓋C組成的單點集時，則CapL(C)=1，因此定理2中的2)在可辨識集簇L的重要度上也得到了保證，由定理3給出。

定理3設(shè)(U,A,D)的可辨識集簇L是根據(jù)定義5所構(gòu)造的，則覆蓋C∈Core(A,D)當(dāng)且僅當(dāng)CapL(C)=1。

證明略

定義8給定覆蓋C∈A和可辨識集簇L={d1,d2,…,dm}，其中每一個di表示在(U,A,D) 中一個非空可辨識集d(x,y) ≠?。設(shè)LCL是所有包含覆蓋C的可辨識集構(gòu)成的集合，即LC={d|d∈L,C∈d}，則稱Diss(L,C)=L-LC是覆蓋C∈A對L中的可辨識集的消解，并稱V=Diss(L,C) 為C對L消解的結(jié)果。

定義8描述了通過給定覆蓋C來清除原可辨識集簇L中所有包含覆蓋C的可辨識集，因此經(jīng)過一次消解運算后得到的可辨識集簇V將不含有覆蓋C的任何信息，原來的可辨識集簇L規(guī)模也嚴(yán)格縮小了，即有V?L。

由定義8可看出，如果可辨識集簇V含有核心覆蓋，則它在新可辨識集簇V中重要度仍然不變。即這些核心覆蓋不被消解過程所去除，可由定理4給出。

定理4給定(U,A,D)的可辨識集簇L，V為可辨識集簇L在某個覆蓋C′下的消解結(jié)果：V=Diss(L,C′)，則當(dāng)C≠C′時，如果SigL(C)=1, 則SigV(C)=1。

證明根據(jù)定義8中的一次消解操作的過程可以得到，如果L中有一個由單覆蓋C(滿足C≠C′)組成的可辨識集d={C}，則d不可能被覆蓋C′對L的消解操作所去除，仍存在于消解后的結(jié)果V中。再由定義6有關(guān)覆蓋相對于可辨識集簇的重要度定義可得結(jié)論成立。

3 基于可辨識集消解策略的覆蓋約簡算法

由定義6～8，以及定理3和定理4可得到基于“求協(xié)調(diào)集-去冗余”二階段求約簡集的算法，如算法1所示。

算法1基于可辨識集消解策略的覆蓋決策信息系統(tǒng)(U,A,D)的約簡算法。

輸入：覆蓋決策信息系統(tǒng)(U,A,D)；

輸出：(U,A,D)的約簡集B。

Calculate L ∥計算可辨識集簇L

Let B=?

While (L≠?)∥取出最大辨識能力的覆蓋，消解迭代直至L為空

Let C=max(L).get()

Let B=B∪{C}

Let L=Diss(L,C)

EndWhile∥第一階段結(jié)束，以下開始第二階段去除冗余覆蓋

Let redundant=true

While(redundant==true)

Let redundant=false

Let Q=duplicate(B)∥從B復(fù)制一份到Q

While (Q≠?)

Let C=Q.get()∥從Q中取一個覆蓋

Let B′=B-{C}∥根據(jù)定義4對B′進行協(xié)調(diào)性檢查

Let consistent=true

For Diin D

Let consistent=false

break

EndIf

EndFor

If (consistent==true)∥B′是協(xié)調(diào)的

Let B=B′

Let redundant=true

EndIf

EndWhile

EndWhile

Return B

算法1的第一階段是逐次獲取具有最大辨識能力的覆蓋并用該覆蓋對原可辨識集簇進行消解來獲取協(xié)調(diào)集。具體過程為：首先從可辨識集簇L提取辨識能力最大的覆蓋C并加入到協(xié)調(diào)集變量B中，然后用該覆蓋C對L進行一次消解操作得到新的可辨識集簇V，接著再從V提取辨識能力最大的覆蓋并進行下一次消解操作，依次類推，直到可辨識集簇為空。最終得到B即為協(xié)調(diào)集。

算法1的第二階段是從協(xié)調(diào)集B中去除冗余覆蓋。 主要的策略是反復(fù)檢查協(xié)調(diào)集B是否存在某個覆蓋去除后仍能保持協(xié)調(diào)性，直到無法找到為止，最后返回的協(xié)調(diào)集即為約簡集。

從算法1可知該算法可終止，并由定理3和定理4可知，由算法1得到的結(jié)果必定包含所有核心覆蓋，同時該覆蓋集是去除了冗余覆蓋的一個約簡，結(jié)論由定理5給出。

定理5給定決策覆蓋信息系統(tǒng)(U,A,D)，采用算法1進行計算，則算法能夠結(jié)束，且返回的結(jié)果B?A是(U,A,D)的一個約簡覆蓋集。

以下給出算法1的時間復(fù)雜度和空間復(fù)雜度分析，設(shè)|U|和|A|分別為論域和覆蓋簇的規(guī)模大小。

第一階段：計算可辨識集簇L的時間復(fù)雜度為O(|U|2·|A|)，可辨識集簇L的空間復(fù)雜度為O(|U|2·|A|)。因為可辨識集簇在消解過程中的規(guī)模是逐漸變小的，考慮最壞可能性為覆蓋在L中平均分布的情況下，計算辨識能力最大覆蓋的平均時間復(fù)雜度為O(|U|2·|A|)，空間復(fù)雜度為O(|U|2·|A|)。可辨識集簇L的一次消解計算的平均時間復(fù)雜度為O(|U|2·|A|，)，平均空間復(fù)雜度為O(|U|2·|A|)。算法的循環(huán)總數(shù)至多為O(|A|)。綜合第一階段時間復(fù)雜度為O(|U|2·|A|2)，空間復(fù)雜度為O(|U|2·|A|)。

第二階段：完成去除冗余計算最多去除|A|個，去除一個冗余覆蓋最多需要|A|次協(xié)調(diào)性檢查，綜合時間復(fù)雜度為O(|U|·|A|2)，空間復(fù)雜度為O(|U|2·|A|)。兩個階段綜合計算復(fù)雜度：時間復(fù)雜度為O(|U|2·|A|2)，空間復(fù)雜度為O(|U|2·|A|)。

由上述計算復(fù)雜度的分析可知，采用“提取-消解”迭代逐次得到最大辨識能力的覆蓋算法是高效的。

4 相關(guān)實驗及結(jié)果

為了驗證算法在實際決策信息系統(tǒng)進行約簡的有效性，選取由UCI(university of California Irvine)所提供的5組數(shù)據(jù)集(如表1所示)進行約簡實驗，通過對照約簡前后的分類準(zhǔn)確性來驗證算法的有效性，并與相關(guān)研究[6]的約簡結(jié)果進行對比。數(shù)據(jù)集約簡前后的CART (classification and regression tree)、SVM(support vector machines)和3NN(3-nearest neighbor algorithm)分類實驗采用Python環(huán)境下的scikit-learn庫所提供的函數(shù)。

表1 實驗使用的UCI數(shù)據(jù)集Table 1 UCI datasets used in experiment

如表1所示的UCI數(shù)據(jù)集可視為一個決策信息系統(tǒng)(U,A,F,d)，A是屬性集，d是決策屬性。F={fa:U→Va}，其中fa表示對象集U在屬性a的值域Va上的取值映射，即對象x∈U在屬性a∈A上的值可表示為fa(x)。采用文獻[14]的方法將決策信息系統(tǒng)(U,A,F,d)轉(zhuǎn)化為覆蓋決策信息系統(tǒng)(U,A′,D)，即在任意屬性a∈A上構(gòu)造一個相應(yīng)的覆蓋C∈A′，在決策屬性d上構(gòu)造一個覆蓋D。簡要敘述如下。

第1步，構(gòu)造U上對象之間在任意屬性a∈A上的鄰域關(guān)系Ra={(x,y)|x,y∈U, |fa(x)-fa(y)|≤δa}。δa是屬性a的鄰域半徑，它的選取是根據(jù)文獻[4, 6]給出的方法δa=std(a)·δ，其中：std(a)是屬性a的標(biāo)準(zhǔn)差；δ是修正參數(shù)，取0.8～1.3可得比較好的約簡結(jié)果。

第2步，根據(jù)每一個屬性a的鄰域關(guān)系Ra構(gòu)造一個覆蓋Ca={Ra(x)|x∈U}。決策覆蓋D也按照類似的方法由決策屬性d得到，但不同的是還需要考慮具體數(shù)據(jù)集的決策屬性值之間的相容性，如果不相容則決策覆蓋D由決策屬性d直接得到一個劃分。

表2、表3所示的是上述數(shù)據(jù)集所對應(yīng)的決策信息系統(tǒng)進行約簡實驗的結(jié)果，其中NRS所在行的數(shù)據(jù)是基于鄰域粗糙集(neighborhood rough set，NRS)的約簡結(jié)果[6]，CRS(covering rough set)所在行的數(shù)據(jù)是由本文算法得到的約簡結(jié)果。

表2給出了來自鄰域粗糙集約簡和本文算法得到的約簡結(jié)果。表3給出了數(shù)據(jù)集未進行約簡前的CART、SVM和3NN分類準(zhǔn)確率，以及來自鄰域粗糙集約簡[6]和本文算法的約簡屬性集(如表3所示)所分別構(gòu)造的約簡數(shù)據(jù)集進行相應(yīng)分類實驗的準(zhǔn)確率。

從表2和表3可知，運用本文算法對數(shù)據(jù)集進行計算可得到較高的約簡率(最大達87.1%)，約簡后數(shù)據(jù)集的分類準(zhǔn)確率與約簡前相比有一定的提高；同時本算法與鄰域粗糙集約簡[6]所提供的約簡結(jié)果相比也有一定的優(yōu)越性。表明本文基于可辨識集消解策略的覆蓋決策信息系統(tǒng)的約簡算法能夠較好地去除原數(shù)據(jù)集中的冗余屬性。

表2 數(shù)據(jù)集約簡后的屬性集Table 2 Selected attributes with different reduction algorithms

表3 數(shù)據(jù)集約簡前后分類結(jié)果對比Table 3 Comparison of the classification accuracies of reduced data

注：約簡后的分類結(jié)果中加粗數(shù)據(jù)為本文約簡算法的結(jié)果，未加粗數(shù)據(jù)為NRS方法的結(jié)果。

5 總結(jié)

通過分析覆蓋決策系統(tǒng)中的協(xié)調(diào)覆蓋集與對象的可辨識集之間的關(guān)系，本文給出了覆蓋相對于可辨識集簇的辨識重要度和辨識影響度所構(gòu)成的覆蓋辨識能力，以及覆蓋對可辨識集簇進行消解的概念和性質(zhì)。提出了從覆蓋決策系統(tǒng)的可辨識集簇中提取最大辨識能力的覆蓋，然后用該覆蓋對原可辨識集簇進行消解的逐次迭代計算，直至可辨識集簇完全消解來得到協(xié)調(diào)覆蓋集的算法。

本文算法對可辨識集簇進行逐次地“提取-消解”的迭代計算是很高效的。未來可針對動態(tài)信息系統(tǒng)中的增量可辨識集[29]和可壓縮的可辨識集[30]運用本算法思想進行高效屬性約簡的探索工作。