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

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

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

1 引言

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

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

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

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

2 基礎(chǔ)知識(shí)

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

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

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

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

對(duì)于任一決策類(lèi)Xi∈U/IND(D)：

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

定義3[21]給定一個(gè)決策系統(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，那些確定屬于某一決策類(lèi)別的樣本占總體樣本的比例。

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

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

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

3 屬性約簡(jiǎn)

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

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

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

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

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

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

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

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

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

輸出：一個(gè)約簡(jiǎn)red。

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

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

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

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

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

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

步驟4輸出red。

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

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

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

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

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

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

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

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

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

輸出：一個(gè)針對(duì)第i類(lèi)標(biāo)記的約簡(jiǎn)red。

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

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

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

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

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

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

步驟4輸出red。

3.3 局部多約束屬性約簡(jiǎn)

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

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

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

（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詳細(xì)介紹了求解局部多約束屬性約簡(jiǎn)的算法。

算法3局部多約束屬性約簡(jiǎn)算法

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

輸出：屬性約簡(jiǎn)red。

步驟 1red←?,γ(red,Xi)=-∞,H(Xi|red)=∞，計(jì)算γ(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，計(jì)算γ(red∪{ai},Xi),H(Xi|red∪{ai})。

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

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

步驟6輸出red。

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

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

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

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

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

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

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

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

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

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

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

（2）利用局部多約束準(zhǔn)則約簡(jiǎn)可以有效地降低條件熵，因此滿(mǎn)足條件熵約簡(jiǎn)的約束條件。

5 結(jié)束語(yǔ)

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

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

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

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

Fig.2 Comparisons among conditional entropies with 3 different reductions圖2 3種不同約簡(jiǎn)下條件熵對(duì)比