姜春茂，劉安鵬

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

1 引言

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

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

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

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

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

(1)

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

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

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

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

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

(2)

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

進(jìn)而可以得到樣本x的δ鄰域?yàn)椋?/p>

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

(3)

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

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

(4)

(5)

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

(6)

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

(7)

(8)

其中，上標(biāo)C表示補(bǔ)集。

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

3 屬性約簡(jiǎn)

3.1 度量準(zhǔn)則

根據(jù)應(yīng)用場(chǎng)景的不同，屬性約簡(jiǎn)有多種度量準(zhǔn)則，常用的度量準(zhǔn)則包括近似質(zhì)量[13,14]和條件熵[15-18]等。本文以近似質(zhì)量來(lái)構(gòu)造約簡(jiǎn)求解的約束條件。下面給出近似質(zhì)量的定義。

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

(9)

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

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

本文計(jì)算約簡(jiǎn)時(shí)采用的是基于適應(yīng)度函數(shù)的搜索方法，基于近似質(zhì)量的屬性重要性評(píng)價(jià)如下：

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

屬性重要性的評(píng)價(jià)建立在樣本?；幕A(chǔ)上。樣本粒化是通過條件屬性提供的信息構(gòu)造鄰域關(guān)系，得到論域上粒化結(jié)果的過程。根據(jù)信息?；Y(jié)果可以計(jì)算某一度量值，進(jìn)一步當(dāng)某個(gè)屬性加入到屬性集合中，相應(yīng)度量值的變化可以用來(lái)評(píng)估屬性的重要度。由此，屬性重要度如式(10)所示：

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

(10)

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

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

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

算法1基于鄰域粗糙集的前向貪心數(shù)值屬性約簡(jiǎn)算法

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

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

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

步驟2B←?；

步驟3 Do

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

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

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

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

步驟4返回B。

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

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

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

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

(11)

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

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

(12)

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

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

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

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

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

步驟2B←?；

步驟3 Do

T←?；

Forp= 1：q

(1)?ai?AT-B，計(jì)算屬性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中出現(xiàn)頻次最多的屬性b，B=B∪ ；

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

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

步驟4返回B。

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

4 基于三支決策的屬性約簡(jiǎn)加速方法

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

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

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

定義7給定第i層侯選屬性集Pi(X),?Xj?BNDi-1,Sig(Pi(Xj))表示屬性Xj的重要度，則第i層的正域、邊界域和負(fù)域劃分規(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 屬性約簡(jiǎn)加速算法

將加速方法應(yīng)用到前向貪心數(shù)值屬性約簡(jiǎn)算法中，具體步驟如算法3所示：

算法3基于三支決策的屬性約簡(jiǎn)加速算法

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

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

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

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

步驟3 Do

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

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

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

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

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

步驟4返回B。

算法3的時(shí)間復(fù)雜度為O(|U|2·(|AT|+|BND1|+…+|BNDm-1|)),其中|U|為論域中樣本數(shù)目，|BNDi|為中間域?qū)傩詳?shù)目。相比于算法1，算法3在迭代時(shí)將無(wú)關(guān)屬性排除，避免了這些屬性在約簡(jiǎn)過程中進(jìn)行無(wú)效計(jì)算，因而對(duì)約簡(jiǎn)效率的提高有幫助。

4.2 集成屬性約簡(jiǎn)加速算法

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

算法4基于三支決策的集成屬性約簡(jiǎn)加速算法

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

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

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

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

步驟3 Do

T←?；

Forp= 1：q

(1)?ai?AT-B-NEG，計(jì)算屬性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中出現(xiàn)頻次最多的屬性b放入正域(POS)，將重要度為0的屬性放入負(fù)域(NEG)，其余屬性放入邊界域(BND)；

(4)B=B∪；

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

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

步驟4返回B。

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

5 實(shí)驗(yàn)與結(jié)果分析

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

Table 1 Description of data sets表1 數(shù)據(jù)集描述

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

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

5.1 約簡(jiǎn)時(shí)間消耗對(duì)比

實(shí)驗(yàn)過程中記錄了2種算法在近似質(zhì)量度量指標(biāo)上約簡(jiǎn)求解的時(shí)間消耗，詳細(xì)的比較結(jié)果如表2所示。

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

由于篇幅有限，表2中數(shù)據(jù)集名稱采用與表1中相同的ID號(hào)替代。通過實(shí)驗(yàn)發(fā)現(xiàn)，結(jié)合了三支決策思想的新算法，無(wú)論是在全局環(huán)境下還是在集成環(huán)境下，均能夠有效降低約簡(jiǎn)的時(shí)間消耗。這是因?yàn)榧铀偎惴ㄍㄟ^減少侯選屬性的數(shù)量，降低了約簡(jiǎn)的計(jì)算時(shí)間。值得注意的是，在集成環(huán)境下每剔除一個(gè)冗余屬性，會(huì)同步減少所有決策類別下約簡(jiǎn)的計(jì)算量，所以同一數(shù)據(jù)集在集成環(huán)境下應(yīng)用三支加速約簡(jiǎn)方法，加速效果會(huì)更加明顯。

5.2 約簡(jiǎn)結(jié)果的分類精度對(duì)比

圖2和圖3分別展示了在以近似質(zhì)量為度量準(zhǔn)則前提下，采用了加速方法的算法3和算法4與傳統(tǒng)屬性約簡(jiǎn)算法1和算法2在NEC分類器[11]和SVM分類器[21]上的分類精度對(duì)比。實(shí)驗(yàn)結(jié)果表明，在大部分半徑下，算法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)算法與新算法的分類精度對(duì)比

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

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

通過對(duì)比NEC和SVM分類器上約簡(jiǎn)結(jié)果的分類精度發(fā)現(xiàn)，新算法相比于傳統(tǒng)算法擁有更好的分類性能。同時(shí)，新算法的時(shí)間消耗更低，說明基于三支決策的屬性約簡(jiǎn)加速方法在保證分類器分類性能的前提下，有效降低了約簡(jiǎn)的時(shí)間消耗。這是因?yàn)樾滤惴ㄔ诿看窝h(huán)選擇屬性時(shí)，僅判斷劃入邊界域的侯選屬性，減少了對(duì)無(wú)關(guān)屬性的計(jì)算，因而在保證分類性能的同時(shí)能帶來(lái)更好的時(shí)間性能。

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

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

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

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