三支決策視角下的屬性約簡加速方法*

姜春茂，劉安鵬

(哈爾濱師范大學計算機科學與信息工程學院，黑龍江 哈爾濱 150025)

1 引言

三支決策[1 - 3]是在決策粗糙集理論[4]基礎上提出的一種三分而治思想，其核心是將論域分為3個子集，分別對3個子集采取不同的策略來處理不確定性決策。為了提高知識約簡的提取速率,Yao[5]利用漸進式粒度計算思想進一步提出了序貫三支決策。屬性約簡[6-8]作為粗糙集理論[9]的核心研究內容，常常受到眾多學者關注，其核心是在給定度量準則的前提下刪除冗余屬性的過程。在實際應用中，研究者往往對特殊決策類中的數據格外關注。在此基礎上，Chen等[10]提出了集成屬性約簡的概念。集成屬性約簡雖然平衡了各決策類的需求，但同時也增加了計算約簡的時間消耗。為了提高屬性約簡的計算效率，本文借助序貫三支決策思想提出了一種加速方法。新方法每次向約簡集合中添加屬性的同時排除部分無關屬性來提高約簡計算效率，以降低時間消耗。

2 基礎知識

在粗糙集理論中，一個決策系統(tǒng)可表示為一個二元組DS=〈U,AT∪D〉，其中，U是所有對象的集合，稱為論域；AT是條件屬性的集合；D為決策屬性集合且AT∩D=?。

定義1給定一個決策系統(tǒng)DS，當D的取值都為離散型時，論域上的劃分如下所示：

U/IND(D)={X1,X2,…,Xq}

(1)

其中，對于?Xp∈U/IND(D),Xp表示第p個決策類。IND(D)={(x,y)∈U×U:?ai∈AT,ai(x)=ai(y)},ai(x)表示樣本x在屬性ai上的取值。

另外，[x]D表示與x屬于同一個決策類的樣本集合。

傳統(tǒng)粗糙集模型僅適用于處理離散型數據，不適合處理實際應用中的連續(xù)型或混合型數據。Hu等[11]提出了鄰域粗糙集模型，該模型有效解決了傳統(tǒng)模型在數據離散化后信息的丟失問題。具體方法是通過條件屬性提供的信息計算樣本間的距離，通過距離構造樣本的鄰域關系，最終借助鄰域關系來處理復雜型數據。

定義2[12]給定一個決策系統(tǒng)DS,給定鄰域半徑δ，鄰域關系可定義為：

N= {(x,y)∈U×U:rA(x,y)≤δ}

(2)

其中，?x,y∈U,rA(x,y)表示樣本x與y之間的距離，本文采用歐氏距離來計算；A為屬性集合。

進而可以得到樣本x的δ鄰域為：

δA(x)= {y|rA(x,y)≤δ}

(3)

其中，δ為鄰域半徑，且δ>0。

定義3給定一個決策系統(tǒng)DS,U/IND(D)={X1,X2,…,Xq},?Xp∈U/IND(D),Xp關于屬性集合A的下近似集和上近似集可定義如下：

(4)

(5)

基于下近似集和上近似集的概念可將論域劃分成3部分，即：正域POS(X)、邊界域BND(X)和負域NEG(X)，形成基于粗糙集的三支決策[12]，其定義如下所示：

(6)

{x∈U|(δA(x)?Xp)∧(δA(x)?)}

(7)

(8)

其中，上標C表示補集。

可見，正域中的對象表示確定屬于決策類Xp的樣本，負域中的對象表示確定不屬決策類Xp的樣本，而邊界域中的對象表示不確定屬于決策類Xp的樣本，相對應地可以分別給予接受、拒絕和不承諾(延遲決策)的語義解釋。

3 屬性約簡

3.1 度量準則

根據應用場景的不同，屬性約簡有多種度量準則，常用的度量準則包括近似質量[13,14]和條件熵[15-18]等。本文以近似質量來構造約簡求解的約束條件。下面給出近似質量的定義。

定義4給定一個決策系統(tǒng)DS,U/IND(D)={X1,X2,…,Xq},?B?AT,D關于B的近似質量定義為：

(9)

其中,|X|表示集合X的基數。

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

本文計算約簡時采用的是基于適應度函數的搜索方法，基于近似質量的屬性重要性評價如下：

定義5給定一個決策系統(tǒng)DS,?B?AT，B是DS中的一個關于近似質量的約簡當且僅當γ(B,D)≥γ(AT,D)且?B′?B,γ(B′,D)<γ(B,D)。

屬性重要性的評價建立在樣本粒化的基礎上。樣本?；峭ㄟ^條件屬性提供的信息構造鄰域關系，得到論域上?；Y果的過程。根據信息?；Y果可以計算某一度量值，進一步當某個屬性加入到屬性集合中，相應度量值的變化可以用來評估屬性的重要度。由此，屬性重要度如式(10)所示：

Sigγ(ai,B,D)=γ(B∪{ai},D)-γ(B,D)

(10)

其中ai∈AT。在屬性約簡中，常用的搜索策略包括添加屬性、刪除屬性以及先添加后刪除屬性策略。本文采用添加式策略計算約簡，即從空集開始逐個加入重要度最大的屬性，直至滿足約束條件為止。

3.2 傳統(tǒng)添加式屬性約簡算法

胡清華等[12]提出了基于鄰域粗糙集的前向貪心數值屬性約簡算法，該算法將屬性重要性作為評價指標，通過貪心策略將當前重要度最大的屬性添加至約簡集合。該算法的具體描述如算法1所示。

算法1基于鄰域粗糙集的前向貪心數值屬性約簡算法

輸入：決策系統(tǒng)DS=〈U,AT∪D〉,半徑δ。

輸出：一個γ約簡B。

步驟1計算γ(AT,D)；

步驟2B←?；

步驟3 Do

(1)?ai?AT-B,計算屬性ai的重要度Sigγ(ai,B,D)；

(2)選出一個重要度最大的屬性b,令B=B∪；

(3)計算γ(B,D)；

Untilγ(B,D)≥γ(AT,D)；

步驟4返回B。

算法1的時間復雜度為O(|U|2·|AT|2),其中，|U|為論域中樣本數目，|AT|為條件屬性數目。該算法把所有決策類別作為一個整體計算，來選出重要度最大的屬性，進而得到約簡結果。該算法的好處是能夠根據決策屬性進行有效約簡，但計算無法細化到具體的決策類別中。在實際應用中，研究者往往更加關注那些影響特定決策類別的屬性，因而發(fā)展出集成屬性約簡的研究。

3.3 傳統(tǒng)集成屬性約簡算法

首先給出集成環(huán)境下的局部近似質量的定義。

定義6[19]給定一個決策系統(tǒng)DS,U/IND(D)={X1,X2,…,Xq},?B?AT,Xp關于B的局部近似質量表示如下：

(11)

結合式(9)和式(10)可以推導出集成環(huán)境下單個決策類Xp的局部屬性重要度為:

Sigγ(ai,B,Xp)=γ(B∪{ai},Xp)-γ(B,Xp)

(12)

通過局部屬性重要度分別求解各個決策類下重要度最大的屬性，將得到的結果進行綜合后得到侯選屬性。集成屬性約簡算法[19]如算法2所示。

算法2傳統(tǒng)集成添加式約簡求解算法

輸入：決策系統(tǒng)DS=〈U,AT∪D〉，半徑δ。

輸出：一個γ約簡B。

步驟1計算γ(AT,D)；

步驟2B←?；

步驟3 Do

T←?；

Forp= 1：q

(1)?ai?AT-B，計算屬性ai的重要度Sigγ(ai,B,Xp)；

(2)選擇aj，滿足Sigγ(aj,B,Xp)= max{Sigγ(ai,B,Xp);?ai?AT-B}；

(3)令T=T∪{aj}；

EndFor

選擇T中出現頻次最多的屬性b，B=B∪ ；

(4)計算γ(B,D)；

Untilγ(B,D)≥γ(AT,D)；

步驟4返回B。

算法2的時間復雜度為O(q·|U|2·|AT|2),其中q為決策類的數目，|U|為論域中樣本數目，|AT|為條件屬性數目，T為所有決策類下選出的重要度最大的屬性集。該算法的優(yōu)勢在于平衡了各個決策屬性的需求，不足之處在于該算法在迭代過程中增加了計算量，導致求解約簡的時間消耗增加。

4 基于三支決策的屬性約簡加速方法

為了縮短集成環(huán)境下屬性約簡的時間，本文提出了一種基于三支決策的屬性約簡加速方法。該方法的核心在于結合了序貫三支決策思想，在選擇屬性的同時排除部分無關屬性，在迭代過程中減少侯選屬性的數量，以達到降低時間消耗的目的。首先給出m層序貫三支決策S3WD(Sequential Three-Way Decisions)的構造過程如圖1所示。

Figure 1 Construction process of sequential three-way decisions圖1 序貫三支決策的構造過程

通過將BND(延遲決策域)中的候選屬性迭代三分，最終轉化為二支決策從而得到約簡集合B，此時B=POS1∪POS2∪…∪POSm，m的取值與數據中冗余屬性(NEG域中對象)和終止條件相關，且當約簡的終止條件固定后，數據中冗余屬性越多，所需的m值越小。

定義7給定第i層侯選屬性集Pi(X),?Xj?BNDi-1,Sig(Pi(Xj))表示屬性Xj的重要度，則第i層的正域、邊界域和負域劃分規(guī)則如下所示：

(13)

BNDi(X)={x∈U|0<

(14)

(15)

其中，1≤i≤m，Sigmax(Pi(X))為第i層重要度最大的屬性。Sig(Pi(Xj|[x]BNDi-1))為第i層的候選屬性Xj的屬性重要度。

4.1 屬性約簡加速算法

將加速方法應用到前向貪心數值屬性約簡算法中，具體步驟如算法3所示：

算法3基于三支決策的屬性約簡加速算法

輸入：決策系統(tǒng)DS=〈U,AT∪D〉，半徑δ。

輸出：一個γ約簡B。

步驟1計算γ(AT,D)；

步驟2B←?;POS←?;BND←AT;NEG←?;

步驟3 Do

(1)?ai?AT-B-NEG，計算屬性ai的重要度Sigγ(ai,B,D)；

(2)將重要度最大的屬性aj放入正域(POS)，將重要度為0的屬性放入負域(NEG)，其余屬性放入邊界域(BND)；

(3)令B=B∪{ai}；

(4)計算γ(B,D)；

Untilγ(B,D)≥γ(AT,D)；

步驟4返回B。

算法3的時間復雜度為O(|U|2·(|AT|+|BND1|+…+|BNDm-1|)),其中|U|為論域中樣本數目，|BNDi|為中間域屬性數目。相比于算法1，算法3在迭代時將無關屬性排除，避免了這些屬性在約簡過程中進行無效計算，因而對約簡效率的提高有幫助。

4.2 集成屬性約簡加速算法

在集成環(huán)境下該加速方法同樣適用，具體步驟如算法4所示：

算法4基于三支決策的集成屬性約簡加速算法

輸入：決策系統(tǒng)DS=〈U,AT∪D〉，半徑δ。

輸出：一個γ約簡B。

步驟1計算γ(AT,D)；

步驟2B←?;POS←?;BND←AT;NEG←?;

步驟3 Do

T←?；

Forp= 1：q

(1)?ai?AT-B-NEG，計算屬性ai的重要度Sigγ(ai,B,Xp)；

(2)選擇aj,滿足Sigγ(aj,B,Xp)=max{Sigγ(ai,B,Xp):?ai?AT-B}；

(3)令T=T∪{aj}；

EndFor

選擇T中出現頻次最多的屬性b放入正域(POS)，將重要度為0的屬性放入負域(NEG)，其余屬性放入邊界域(BND)；

(4)B=B∪；

(5)計算γ(B,D)；

Untilγ(B,D)≥γ(AT,D)；

步驟4返回B。

算法4的時間復雜度為O(q·|U|2·(|AT|+|BND1|+…+|BNDm-1|)),其中q為決策類的數目，|U|為論域中樣本數目，|BNDi|為中間域屬性數目，T為所有決策類下選出的重要度最大的屬性集。加入三支決策加速方法后，算法4相比于算法2在約簡的計算過程中降低了計算量。

5 實驗與結果分析

為了驗證所提加速方法的有效性，本文從UCI數據集中選取了8組數據進行實驗，對應用了加速方法的算法(新算法)與傳統(tǒng)算法在分類精度和時間消耗上的差異進行了比較。數據集的描述如表1所示。實驗環(huán)境為PC機，雙核1.00 GHz CPU,4 GB內存，Windows 10操作系統(tǒng)，Matlab R2016b 實驗平臺。

Table 1 Description of data sets表1 數據集描述

實驗采用了5折交叉驗證[20]的方法，選取10個不同的半徑，分別為0.02,0.04,…,0.2。5折交叉驗證的具體過程是將實驗數據中的樣本平均分成5份，即U1,U2,…,U5。第1次使用U2∪U3∪…∪U5作為訓練集求得約簡B1，使用U1作為測試集并利用B1中的屬性計算分類精度；第2次使用U1∪U3∪…∪U5作為訓練集求得約簡B2，使用U2作為測試集并利用B2中的屬性計算分類精度；依次類推，第5次使用U1∪U2∪…∪U4作為訓練集求得約簡B5,使用U5作為測試集并利用B5中的屬性計算分類精度。

本組實驗以近似質量為約簡的度量準則，用鄰域分類器NEC(NEighborhood Classifier)[11]和SVM分類器[21]對測試集中的樣本進行分類。實驗在全局環(huán)境和集成環(huán)境下分別進行，將傳統(tǒng)算法與新算法進行對比分析。分別計算并比較了算法1～算法4的時間消耗及分類精度。

5.1 約簡時間消耗對比

實驗過程中記錄了2種算法在近似質量度量指標上約簡求解的時間消耗，詳細的比較結果如表2所示。

Table 2 Comparison of reduction time consumption between traditional and accelerated algorithms表2 傳統(tǒng)算法與加速算法的約簡時間消耗對比

由于篇幅有限，表2中數據集名稱采用與表1中相同的ID號替代。通過實驗發(fā)現，結合了三支決策思想的新算法，無論是在全局環(huán)境下還是在集成環(huán)境下，均能夠有效降低約簡的時間消耗。這是因為加速算法通過減少侯選屬性的數量，降低了約簡的計算時間。值得注意的是，在集成環(huán)境下每剔除一個冗余屬性，會同步減少所有決策類別下約簡的計算量，所以同一數據集在集成環(huán)境下應用三支加速約簡方法，加速效果會更加明顯。

5.2 約簡結果的分類精度對比

圖2和圖3分別展示了在以近似質量為度量準則前提下，采用了加速方法的算法3和算法4與傳統(tǒng)屬性約簡算法1和算法2在NEC分類器[11]和SVM分類器[21]上的分類精度對比。實驗結果表明，在大部分半徑下，算法3和算法4得到的分類精度優(yōu)于算法1和算法2的，可以說明采用加速方法后的新算法具有不弱于傳統(tǒng)算法的分類精度。

Figure 2 Comparison of classification accuracy between traditional algorithms and new algorithms in global environment圖2 全局環(huán)境下傳統(tǒng)算法與新算法的分類精度對比

Figure 3 Comparison of classification accuracy between traditional algorithms and new algorithms in ensemble environment圖3 集成環(huán)境下傳統(tǒng)算法與新算法的分類精度對比

5.3 實驗分析

通過對比NEC和SVM分類器上約簡結果的分類精度發(fā)現，新算法相比于傳統(tǒng)算法擁有更好的分類性能。同時，新算法的時間消耗更低，說明基于三支決策的屬性約簡加速方法在保證分類器分類性能的前提下，有效降低了約簡的時間消耗。這是因為新算法在每次循環(huán)選擇屬性時，僅判斷劃入邊界域的侯選屬性，減少了對無關屬性的計算，因而在保證分類性能的同時能帶來更好的時間性能。

6 結束語

為了降低屬性約簡的時間消耗，本文將三支決策思想引入到約簡的求解過程中，以提高約簡計算的時間效率。通過實驗對比分析可以得出，本文方法在保障分類器分類性能前提下能夠有效提升求解約簡的時間性能。在這一工作的基礎上，本文將就以下問題展開進一步探討：

(1)本文中僅使用鄰域粗糙集模型，下一步將考慮使用其它粗糙集模型，如模糊粗糙集、決策粗糙集等。

(2)新算法在剔除屬性的過程中僅考慮重要度為0的屬性，下一步可設置屬性重要度的動態(tài)閾值，以提高約簡的求解效率，并結合分類精度的代價損失進行研究。