面向局部多約束的屬性約簡方法研究*

董 杰，王 遜+，張文冬，王平心，楊習(xí)貝

1.江蘇科技大學(xué) 計算機學(xué)院，江蘇 鎮(zhèn)江 212003

2.江蘇科技大學(xué) 理學(xué)院，江蘇 鎮(zhèn)江 212003

1 引言

作為一種刻畫不確定與不精確問題的數(shù)學(xué)工具，粗糙集理論與方法[1]近年來在機器學(xué)習(xí)、人工智能等領(lǐng)域得到了廣泛的應(yīng)用。除了粗糙集模型的構(gòu)建以外，屬性約簡[2-5]是粗糙集理論中公認的一個核心研究問題。所謂屬性約簡，一般來說可以理解為從所有屬性中找出一些滿足給定約束條件的屬性子集。這些約束條件大多是建立在由粗糙集模型與方法所得到的一些度量（如近似質(zhì)量[6]、條件熵[7]、決策錯誤率[8]等）基礎(chǔ)上的，具體的約束可以是找到一些屬性子集能夠保持這些度量或在給定的閾值范圍內(nèi)達到預(yù)期的度量標準。

例如，將近似質(zhì)量作為約簡約束條件中的度量，利用啟發(fā)式算法可以求得一個使得近似質(zhì)量滿足給定約束的最小屬性子集。然而值得注意的是，這一約簡僅僅能夠使得近似質(zhì)量滿足約束條件，但并不表示這個約簡能夠滿足其他諸如條件熵度量下的約束條件。這主要是因為利用單一度量指標所構(gòu)建的約束條件其指向明確，同時粗糙集理論中的不同度量指標之間可能并不存在必然的一致性。除此之外，僅僅考慮近似質(zhì)量約束的約簡策略并不一定適用，這主要是因為近似質(zhì)量的約束雖然能夠得到滿足，但每一個決策類所對應(yīng)的下近似集的變化情況是不一樣的。例如對于約束條件為達到原始近似質(zhì)量95%的情形來說，這是一種典型的近似約簡[9]，雖然經(jīng)過約簡后所得到的近似質(zhì)量可以達到預(yù)期的目標，但是并不一定能夠保證每一個決策類的下近似集都能夠達到與原始下近似集相似度等于或高于95%這一目標。

為解決上述問題，在文獻[10-11]工作的基礎(chǔ)上，選取近似質(zhì)量和條件熵這兩種度量準則構(gòu)建約束條件，并從局部的視角出發(fā)，定義了局部多約束的屬性約簡，進而設(shè)計了求解這一約簡的啟發(fā)式算法。值得注意的是，經(jīng)典Pawlak粗糙集模型是建立在等價關(guān)系基礎(chǔ)上的，僅能用于處理離散型數(shù)據(jù)，而對于現(xiàn)實中廣泛存在的連續(xù)型數(shù)據(jù)卻束手無策。因此，Hu等人[12]提出了鄰域粗糙集方法，該方法不僅可以用于直接處理連續(xù)型數(shù)據(jù)，而且由于鄰域半徑的存在，依據(jù)不同大小的半徑，可以自然地形成一個多粒度結(jié)構(gòu)框架，極大地拓展了粗糙集理論的應(yīng)用范疇[13-17]。本文將借助這一模型來實現(xiàn)新的屬性約簡方法。

本文主要內(nèi)容安排如下：第2章簡要介紹鄰域粗糙集的基本知識；第3章在傳統(tǒng)屬性約簡的基礎(chǔ)上，構(gòu)建了局部多約束屬性約簡策略；第4章進行實驗對比分析；第5章總結(jié)全文。

2 基礎(chǔ)知識

在粗糙集理論中，研究對象為一個決策系統(tǒng)DS=＜U,AT∪D＞,U是所有樣本構(gòu)成的集合，即論域；AT是所有條件屬性的集合；D是決策屬性的集合且AT∩D=?。U/IND(D)={X1,X2,…,XN}表示根據(jù)決策屬性D所誘導(dǎo)出的論域上的劃分。

定義1給定一個決策系統(tǒng)DS,?x∈U,?δ∈[0,1],r(x,y)為歐氏距離函數(shù)，則點集δ(x)={y|r(x,y)≤δ,y∈U}表示x的δ鄰域，δ稱為鄰域半徑。

給定論域U={x1,x2,…,xn}，假設(shè)M=(rij)n×n為論域上的相似度矩陣，rij表示樣本xi與xj之間的歐氏距離。為了解決因半徑過小而產(chǎn)生空鄰域的問題[18]，可以采用鄰域區(qū)間的表示方法。給定半徑δ,?xi∈U,xi的鄰域區(qū)間為：

定義2[19-20]給定一個決策系統(tǒng)DS,U/IND(D)={X1,X2,…,XN},?B?AT,D關(guān)于B的下近似和上近似定義為：

對于任一決策類Xi∈U/IND(D)：

決策類的下近似集是表示確定屬于該決策類的樣本的合集，借助下近似集，可以得到如下所示近似質(zhì)量的定義。

定義3[21]給定一個決策系統(tǒng)DS,U/IND(D)={X1,X2,…,XN},?B?AT,D關(guān)于B的近似質(zhì)量定義如下：

其中，|X|表示集合X的基數(shù)。

顯然 0≤γ(B,D)≤1成立。γ(B,D)表示根據(jù)條件屬性B，那些確定屬于某一決策類別的樣本占總體樣本的比例。

除了近似質(zhì)量之外，條件熵也是粗糙集理論中一種常用的用于刻畫不確定性的度量方法，以下定義4中給出了鄰域條件熵的形式化描述。

定義4給定一個決策系統(tǒng)DS，論域U={x1,x2,…,xn},?B?AT,D關(guān)于B的條件熵定義如下：

其中，[xi]D是指決策系統(tǒng)中包含樣本xi的決策類。

3 屬性約簡

3.1 傳統(tǒng)近似質(zhì)量約簡

屬性約簡是粗糙集理論研究中的重要內(nèi)容，它是依據(jù)某種度量準則設(shè)置一約束條件，使得刪除決策系統(tǒng)中的冗余屬性后能夠滿足這一約束。

值得注意的是，由于文中使用式（1）所示的鄰域區(qū)間計算鄰域，因此鄰域粗糙集的近似質(zhì)量并不一定隨著屬性的增加而呈單調(diào)增加變化。當考慮將近似質(zhì)量作為度量準則時，約簡中的約束條件可以設(shè)置為“利用約簡所求得的近似質(zhì)量不低于利用原始屬性集合所求得的近似質(zhì)量”，如定義5所示。

定義5給定一個決策系統(tǒng)DS,?B?AT,B被稱為一個近似質(zhì)量約簡當且僅當γ(B,D)≥γ(AT,D)且?B′?B,γ(B′,D)＜γ(AT,D)。

決策系統(tǒng)中的一個近似質(zhì)量約簡是一個能夠保持鄰域粗糙集的近似質(zhì)量不降低的最小屬性子集。根據(jù)定義5所示的約簡定義，可以進一步使用如下所示的重要度進行約簡的求解。

給定一個決策系統(tǒng)DS,?B?AT且對于任意的a∈AT-B, 如果γ(B∪{a},D)=γ(B,D)，那么就表明屬性a對于近似質(zhì)量的提升沒有任何貢獻，a是冗余的；如果γ(B∪{a},D)＞γ(B,D)，那么就表示加入屬性a后可以提高近似質(zhì)量。因此，屬性重要度定義為：

根據(jù)上述屬性重要度，可以構(gòu)建一個啟發(fā)式屬性約簡算法。該算法以空集為起點，每次計算全部剩余屬性的屬性重要度，從中選擇屬性重要度值最大的屬性加入約簡集合中，直到利用當前約簡集合中的屬性所求得的近似質(zhì)量滿足約簡中的約束條件。

算法1近似質(zhì)量約簡

輸入：鄰域決策系統(tǒng)DS=＜U,AT∪D＞，鄰域半徑參數(shù)δ。

輸出：一個約簡red。

步驟1red←?,γ(red,D)=-∞，計算γ(AT,D)。

步驟2若γ(red,D)≥γ(AT,D)，則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟3。

步驟3（1）?ai∈AT-red，計算Sig(ai,red,D)；

（2）選擇aj，滿足Sig(aj,red,D)=max{Sig(ai,red,D):?ai∈AT-red}；

（3）令red=red∪{aj}；

（4）計算γ(red,D)，返回步驟2。

步驟4輸出red。

3.2 局部近似質(zhì)量約簡

算法1在迭代過程中，求解屬性重要度是依據(jù)全體樣本所得到的近似質(zhì)量差異，如式（9）。但這種重要度計算方法僅考慮的是決策系統(tǒng)中由所有決策類所生成下近似而得到的近似質(zhì)量，忽略了每一個決策類別的下近似集在約簡前后的變化程度。

然而在實際應(yīng)用中，一些特殊的決策類往往會使得研究者更為關(guān)注。例如，為了得到更簡潔的規(guī)則，可以從局部的視角出發(fā)，針對每一個決策類別進行約簡[5,22]。鑒于此，以下給出局部近似質(zhì)量的公式，用以量化地反映每一個決策類下近似集的大小，并在此基礎(chǔ)上，進一步定義了基于局部近似質(zhì)量的屬性約簡。

定義6給定一個決策系統(tǒng)DS,U/IND(D)={X1,X2,…,XN},?B?AT,?Xi∈U/IND(D)，類別Xi關(guān)于B的局部近似質(zhì)量定義表示為：

定義7給定一個決策系統(tǒng)DS,?B?AT,?Xi∈U/IND(D)，B被稱為一個局部近似質(zhì)量約簡當且僅當γ(B,Xi)≥γ(AT,Xi)且 ?B′?B,γ(B′,Xi)＜γ(AT,Xi)。

式（10）描述的是在決策系統(tǒng)中第i類樣本的近似質(zhì)量，這是一種基于類別標記的局部近似質(zhì)量。利用這一概念，可以構(gòu)建第i個類別標記下的屬性重要度公式形如：

求解局部近似質(zhì)量約簡的具體步驟如算法2所示。

算法2局部近似質(zhì)量約簡

輸入：鄰域決策系統(tǒng)DS=＜U,AT∪D＞，決策類Xi且Xi∈U/IND(D)，鄰域半徑參數(shù)δ。

輸出：一個針對第i類標記的約簡red。

步驟1red←?,γ(red,Xi)=-∞，計算γ(AT,Xi)。

步驟2若γ(red,Xi)≥γ(AT,Xi)，則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟3。

步驟3（1）?ai∈AT-red，計算Sig(ai,red,Xi)；

（2）選擇aj，滿足Sig(aj,red,Xi)=max{Sig(ai,red,Xi):?ai∈AT-red}；

（3）令red=red∪{aj}；

（4）計算γ(red,Xi)，返回步驟2。

步驟4輸出red。

3.3 局部多約束屬性約簡

算法2是選取單一度量準則作為求取約簡的方法，但這一方法并不能保證所求得的約簡能夠同時滿足兩個或兩個以上的約束條件。為解決這一問題，可以進一步地引入多個度量準則，文中以下再將局部條件熵作為約簡的約束條件，使得約簡在局部視角下滿足多方面約束的條件。

定義8給定一個決策系統(tǒng)DS，論域U={x1,x2,…,xn},?B?AT,D關(guān)于Xi的局部條件熵定義如下：

定義9給定一個決策系統(tǒng)DS，?B?AT,?Xi∈U/IND(D),B被稱為一個局部多約束屬性約簡當且僅當：

（1）γ(B,Xi)≥γ(AT,Xi)且H(D|Xi)≤H(D|B)；

（2）?B′?B,γ(B′,Xi)＜γ(AT,Xi)或H(D|Xi)＜H(D|B′)。

算法3詳細介紹了求解局部多約束屬性約簡的算法。

算法3局部多約束屬性約簡算法

輸入：鄰域決策系統(tǒng)DS=＜U,AT∪D＞。

輸出：屬性約簡red。

步驟 1red←?,γ(red,Xi)=-∞,H(Xi|red)=∞，計算γ(AT,Xi),H(Xi|AT)。

步驟2若γ(red,Xi)≥γ(AT,Xi)且H(Xi|red)≤H(Xi|AT)，轉(zhuǎn)步驟6，否則轉(zhuǎn)步驟3。

步驟3?ai∈AT-red，計算γ(red∪{ai},Xi),H(Xi|red∪{ai})。

步驟4若aj滿足γ(red∪{aj},Xi)=max{γ(red∪{ai},Xi):?ai∈AT-red};ak滿足H(Xi|red∪{ak})=min{H(Xi|red∪{ai}):?ai∈AT-red}。

步驟5選取am滿足m=min(j,k)，令red=red∪{am}，計算γ(red,Xi)和H(Xi|red)，返回步驟2。

步驟6輸出red。

在算法3的步驟5中，若所求得的aj=ak，則步驟5中的am=aj=ak，而若aj≠ak，則說明利用近似質(zhì)量度量指標與條件熵度量指標所得到的屬性有沖突，此時選取位置最靠前的屬性加入到約簡的屬性集合中去。然后返回步驟2，判斷屬性集合是否同時滿足近似質(zhì)量和條件熵兩個約束條件。若滿足則輸出red，否則算法繼續(xù)。

4 實驗分析

為了驗證局部多約束屬性約簡的有效性，從UCI數(shù)據(jù)集中選擇了6組數(shù)據(jù)，數(shù)據(jù)的基本描述如表1所列。實驗環(huán)境為PC機，雙核2.60 GHz CPU，8 GB內(nèi)存，Windows 10操作系統(tǒng)，Matlab R2016a實驗平臺。

實驗采用了5折交叉驗證[23]的方法并且選取了10個不同的半徑δ，值分別為0.03，0.06，…，0.3。5折交叉驗證的具體過程是將實驗數(shù)據(jù)中的樣本平均分成5份，即U1,U2,…,U5，第一次使用U2∪U3∪…∪U5作為訓(xùn)練集求得約簡red1，使用U1作為測試集并在其中利用red1求得近似質(zhì)量與條件熵；第二次使用U1∪U3∪…∪U5作為訓(xùn)練集求得約簡red2，使用U2作為測試集并在其中利用red2求得近似質(zhì)量與條件熵；依次類推，第五次使用U1∪U2∪…∪U4作為訓(xùn)練集求得約簡red5，使用U5作為測試集并在其中利用red5求得近似質(zhì)量與條件熵。

本組實驗選取了全局近似質(zhì)量、局部近似質(zhì)量以及局部多約束準則作為約簡的度量標準[24-25]，在上述6組數(shù)據(jù)集上分別比較了基于這3種約簡的近似質(zhì)量與條件熵。實驗結(jié)果如圖1、圖2所示。

觀察圖1可以發(fā)現(xiàn)，在10個半徑下，針對每個決策類，利用3種約簡在測試集上所求得的近似質(zhì)量值相差并不大。因此不難得出如下結(jié)論：

（1）利用局部近似質(zhì)量約簡可以保證決策類的每個類別的近似質(zhì)量能夠滿足屬性約簡準則。

（2）利用局部多約束約簡依然可以滿足全局近似質(zhì)量約簡與局部近似質(zhì)量約簡的約束條件。

（3）利用全局近似質(zhì)量約簡所得到的局部近似質(zhì)量值并不一定占據(jù)優(yōu)勢，例如在“Seeds”數(shù)據(jù)集中，半徑為0.15時，對于決策類X2來說，利用全局近似質(zhì)量約簡所得到X2的局部近似質(zhì)量值為0.7，而利用X2的局部近似質(zhì)量約簡所得到的局部近似質(zhì)量值為0.8。

根據(jù)圖2，在10個半徑下，利用全局近似質(zhì)量約簡所求得的條件熵往往低于利用局部近似質(zhì)量約簡所求得的條件熵，而利用局部多約束約簡所求得的條件熵相較于利用全局近似質(zhì)量所求得的條件熵來說，值更低。因此可以得出如下結(jié)論：

（1）局部近似質(zhì)量約簡不能有效地降低條件熵，因此不滿足條件熵約簡的約束條件。例如在“Wine”數(shù)據(jù)集中，對于決策類X2來說，利用局部近似質(zhì)量約簡所得到X2的局部條件熵明顯要高于利用X2的全局近似質(zhì)量約簡和局部多約束約簡所得到的局部條件熵。

（2）利用局部多約束準則約簡可以有效地降低條件熵，因此滿足條件熵約簡的約束條件。

5 結(jié)束語

利用鄰域粗糙集求解約簡時，傳統(tǒng)的近似質(zhì)量約簡是在考慮所有決策類的前提下進行，忽視了具體某種決策類別下近似質(zhì)量的變化情形。并且基于單一準則的屬性約簡的結(jié)果雖然能夠滿足約束條件，但是不能保證其仍然滿足其他度量準則下的約束條件。鑒于此，從局部視角出發(fā)，將局部近似質(zhì)量與局部條件熵作為約簡的多約束準則，利用啟發(fā)式算法求解多約束約簡。實驗結(jié)果表明，該方法不僅可以保證決策類的近似質(zhì)量滿足約束條件，而且能夠顯著地降低條件熵，即仍然能夠滿足條件熵這一度量準則下的約束條件。

Table 1 Data sets description表1 數(shù)據(jù)集描述

Fig.1 Comparisons among approximate qualities with 3 different reductions圖1 3種不同約簡下近似質(zhì)量對比

在此基礎(chǔ)上，下一步將討論由不同決策類生成的局部多約束約簡之間的結(jié)構(gòu)關(guān)系，同時為減少約簡時間消耗尋求更高效的約簡算法。

Fig.2 Comparisons among conditional entropies with 3 different reductions圖2 3種不同約簡下條件熵對比