面向特定類的三支概率屬性約簡算法

彭莉莎,錢文彬,2,王映龍

1(江西農業大學 計算機與信息工程學院,南昌 330045)2(江西農業大學 軟件學院,南昌 330045) E-mail:qianwenbin1027@126.com

1 引 言

與許多經典二支分類模型相比,Yao教授提出的三支決策[1,2]更符合人們在信息不足的情況下解決問題的“三思而后行”的思維方式.三支決策將整體劃分成三個部分,從粗粒度到細粒度、從宏觀到微觀對整體進行分析和處理,通過這種“三劃分”思想處理模糊信息數據,可有效提高決策質量,降低錯誤決策風險,因此,三支決策已成為當前粒計算與知識發現領域中一個重要的研究方向,并在理論模型和應用領域獲得廣泛研究.理論模型方面包括序貫三支決策[3]、三支聚類[4]、三支區間集[5]和三支模糊集[6,7]等.應用領域包括垃圾郵件過濾[8]、惡意軟件分析[9]、人臉識別[10]、和推薦系統[11]等.

在知識發現和粒計算領域中,對高維數據進行屬性約簡可以提高分類算法的效率和分類性能,且能降低分類過程中的測試代價和誤分類代價,因此,屬性約簡在近些年得到了廣泛關注和研究.然而,在經典粗糙集模型的屬性約簡中,不確定性度量呈現的單調性在三支決策的屬性約簡中不再成立,于是研究學者們相繼提出三支屬性約簡,這些三支約簡方法主要分為三支宏觀屬性約簡和三支微觀屬性約簡.三支宏觀屬性約簡適用于決策類是相互關聯的決策系統,即獲取所有決策類下的三支屬性約簡.例如,Chen等人為鄰域系統構建基于條件熵的三支決策約簡算法[12];Li等人提出鄰域決策粗糙集的正域相關和最小代價屬性約簡[13];Zhang等人在基于依賴度的定性屬性約簡的基礎上提出了基于相對依賴度的三支定量屬性約簡,并探討了二者之間的聯系與區別[14].Gao等人基于最大包含程度提出最大決策熵,并驗證了其單調性,在決策粗糙集模型上構建了基于三支最大決策熵的啟發式屬性約簡算法[15].微觀屬性約簡適用于決策類是相互獨立的決策系統,即對單個決策類(簡稱特定類)進行三支約簡,每個特定類的約簡子集互不相同.Ma等人從代數論的角度構建了關于經典粗糙集和概率粗糙集的特定類三支屬性約簡,并分析了二者在一致決策系統和不一致決策系統下的約簡結果[16].Zhang等人從代數論和信息論的角度研究了三層粒度結構中的中層結構的Algebra,Likelihood、Prior和Posterior特定類的屬性約簡算法,并討論了四種算法下的約簡子集的大小關系和基于一致性與不一致性的轉換關系[17].

Yao和Zhang詳細討論了三支宏觀屬性約簡與三支微觀約簡的關系,提到所有決策類的約簡子集并不能有效地等同于某個特定類的約簡子集,且考慮到約簡代價等原因,有時可能只需獲取某個特定類的約簡子集,這樣不僅可以減少約簡代價,也能使該特定類的約簡子集更精確.例如,在醫療系統中,首先,對初步診斷患有X病的患者進行正域、負域或邊界域劃分,然后求解這三個域的屬性(檢測項目)約簡結果,就可得知只需檢測哪些項目便可判斷出這些疑似X類患者一定、不一定或一定不患X病,這在一定程度上可減少檢測費用和提高診斷質量.然而,現有針對三支微觀約簡的研究相對較少,但也逐漸受到關注和探討[18].為了進一步研究面向特定類的三支屬性約簡,本文在上述研究基礎上,構建了基于相對依賴度和基于信息熵的特定類三支概率屬性約簡算法,并通過醫療診斷的實例詳細分析了算法的有效性和可解釋性.

2 基本知識

給定一個決策系統DS=(U,C∪D,{va|a∈C},{Ia|a∈C});其中U={x1,x2,…,xm}表示有限非空對象全集,n-維特征空間C={a1,a2,…,an}表示有限非空條件屬性全集,D表示決策屬性,va表示a∈C的屬性值,Ia|U→va表示一個信息函數,Ia(x)表示對象x在屬性a上的值域.關于屬性子集B?C的等價關系可表示為IND(B)?{x,y∈U|?a∈C[Ia(x)=Ia(y)]},x基于B的等價類[x]B可表示為[x]B={y∈U|xBy}.

2.1 基于概率粗糙集的三支決策

三支決策模型的主要思想是三分而治,即將論域劃分成3個域—正域、負域和邊界域,并針對這三個域采取有效策略[19].

在三支決策粗糙集中,{λPP,λBP,λNP}和{λPN,λBN,λNN}分別表示當對象x屬于對象集X和不屬于X時,將x劃分到X的正域、邊界域和負域的風險損失值.然后,根據期望風險最小化的貝葉斯(Bayes)決策準則計算得出三支決策規則:

定義1[1].給定決策系統DS=(U,C∪D),α和β為損失風險損失值計算而來的三支決策閾值,屬性子集B?C,?X?U,P(X|[x]B)表示[x]B屬于X的條件概率,則對于X構造如下基于概率粗糙集表示的三支決策:

POS(X|B)={x∈U|α≤P(X|[x]B)≤1}

BND(X|B)={x∈U|β

NEG(X|B)={x∈U|0≤P(X|[x]B)≤β}

通過三支決策將對象劃分到了X的正域POS(X|B)、負域NEG(X|B)和邊界域BND(X|B)中.

2.2 基于代數觀點的特定類的三支屬性約簡

在啟發式屬性約簡算法中,約簡子集應同時滿足組合充分條件和獨立必要條件,為了便于闡述,在下文中用S和N分別表示這兩個條件.S條件用于選擇與屬性全集具有同等分類能力的屬性子集,即約簡子集;N條件可去除約簡子集中可能存在的少量冗余屬性,以確保最終的約簡子集盡量最小.

文獻[16]提出了關于經典粗糙集模型和關于概率粗糙集模型的特定類三支屬性約簡方法.關于概率粗糙集模型下的基于代數包含關系的特定類的三支屬性約簡定義如下:

定義2[16].給定決策系統DS=(U,C∪D)和一對閾值α和β,若R為C關于特定類Dj∈U/D的三支定性約簡子集,則其應該滿足以下條件:

(SPOS):POSα,β(Dj|R)?POSα,β(Dj|C)

(NPOS):?(R′?R)[POSα,β(Dj|R′)POSα,β(Dj|R)]

(SBND):BNDα,β(Dj|R)?BNDα,β(Dj|C)

(NBND):?(R′?R)[BNDα,β(Dj|R′)BNDα,β(Dj|R)]

(SNEG):NEGα,β(Dj|R)?NEGα,β(Dj|C)

(NNEG):?(R′?R)[NEGα,β(Dj|R′)NEGα,β(Dj|R)]

特定類的核屬性可通過依賴度表示為:CORE(Dj)=rα,β(Dj|(C-a))

同理,屬性a∈C-R的重要度可表示為:SIG(a,R)=rα,β(R)-rα,β(R-a).

該文獻雖未給出具體的屬性約簡算法,但詳細研究了代數觀點下的特定類三支屬性約簡模型.

2.3 基于信息論的特定類屬性約簡

文獻[17]從信息論的角度,提出了關于經典粗糙集模型的特定類的三種正域屬性約簡方法(Likelihood、Prior和Posterior),其核心概念如定義3中1)-3)所示.

定義3.[17]給定決策系統DS=(U,C∪D),若R為C關于特定類Dj∈U/D的三支約簡子集,則其應該滿足以下條件:

1)Likelihood-特定類屬性約簡-Rlklhd(Dj)

(Sklhd):H(Dj|R)=H(Dj|C)

(Nklhd):?(R′?R)[H(Dj|R′)>H(Dj|R)]

2)Prior-特定類屬性約簡-Rprior(Dj)

(Sprior):H(R)=H(C)

(Nprior):?(R′?R)[H(R′)

3)Posterior-特定類屬性約簡-Rpstrr(Dj)

(Spstrr):H(R|Dj)=H(C|Dj)

(Npstrr):?(R′?R)[H(R′|Dj)

其中,令B?C,Ci∈U/IND(B),則?Dj∈U/D,其三支權重熵如下定義:

[Hklhd(Dj|P)≥Hklhd(Dj|Q)]∧[Hprior(P)≤Hprior(Q)]∧[Hpstrr(P|Dj)≤Hpstrr(Q|Dj)]

該文獻面向經典粗糙集的三支決策模型,從信息論觀點研究了特定類的三種正域屬性約簡算法.而本文則是面向概率粗糙集的三支決策模型,構建基于信息熵的特定類的正域、負域和邊界域屬性約簡算法.

3 面向特定類的三支概率屬性約簡

3.1 代數觀點下的特定類三支概率屬性約簡

在文獻[14]和文獻[16]的基礎上,從代數觀點構建基于相對依賴度的特定類的正域、負域和邊界域屬性約簡算法.

定義4.給定決策系統DS=(U,C∪D)和一對參數α和β,rrelative代表相對依賴度,若R為C關于特定類Dj∈U/D的三支定量約簡子集,則其應該滿足以下條件:

(SPOS):rrelative(Dj|R)≥α

(NPOS):?(R′?R)[Rrelative(Dj|R′)<α]

(SBND):rrelative(Dj|R)∈(β,α)

(NBND):?(R′?R)[rrelative(Dj|R′)?(β,α)]

SNEG:rrelative(Dj|R)≤β

(NNG):?(R′?R)[rrelative(Dj|R′)

令*=POS∨BND∨NEG.則在Dj的正域約簡、邊界域約簡和負域約簡過程中:

?a∈(C-R),其屬性的重要度為:SIG(a,R)=rrelative(R∪{a})-rrelative(R).將作為啟發式屬性約簡算法中的啟發因子.

雖然該方法也是從代數觀點下進行屬性約簡,但2.2小節中提到的是一種基于包含關系的定性屬性約簡方式,而本小節中構建的是一種基于概率的定量屬性約簡方式.通過分析可知,當設置(β,α)=(0,1)時,后者可轉化成前者.因此,從理論上講,本小節提出的基于相對依賴度的特定類三支概率屬性約簡方法的可擴展性相對更強.

為此,以決策系統的相對核CORE為起點,以外部屬性的重要性SIG為啟發式信息,面向特定類構建基于相對依賴度的三支概率啟發式屬性約簡算法(RRSC-TWDAR),如算法1所示.

算法1.一種面向特定類的基于相對依賴度的三支概率屬性約簡算法RRSC-TWDAR(下面以“面向特定類下的正域的三支概率屬性約簡算法”為例)

輸入:決策系統DS=(U,C∪D)和參數α和β

Step 3.whilerrelative(Dj|R)<αdo

Step 4.end while //跳出while循環

ifrrelative(Dj|R-{r})≥αthen

R=R-{r};

end if;

Step 6.end for //跳出for循環

3.2 基于信息論的特定類三支概率屬性約簡

為了進一步探討面向特定類的三支屬性約簡,我們基于概率粗糙集的三支決策模型,給出了基于信息熵的特定類的正域、邊界域和負域的屬性約簡模型和算法.

定義5.給定決策系統DS={U,C∪D}和一對閾值α和β,特定類Dj∈U/D,屬性子集B?C,P(Dj|[x]B)表示等價類[x]B屬于Dj的條件概率,則關于特定類Dj構造如下基于概率粗糙集表示的三支決策:

POS(Dj|B)={x∈U|α≤P(Dj|[x]B)≤1}

BND(Dj|B)={x∈U|β

NEG(Dj|B)={x∈U|0≤P(Dj|[x]B)≤β}

令*=POS∨BND∨NEG.則關于特定類Dj基于信息熵的正域、邊界域和負域的約簡中:

算法2.一種面向特定類的基于信息熵的三支概率屬性約簡算法(ITSC-TWDAR)

輸入:決策系統DS=(U,C∪D)

R=R∪{a0};

Step 4.end while

R=R-{r};

end if;

Step 6.end for

算法2與算法1相比,除了啟發因子不一樣,整體設計思路也是以核屬性為約簡子集的起點,依據S條件,依次添加最重要的屬性至約簡子集中,直至達到與屬性全集具有相同的劃分能力后跳出循環,最后,依據N條件,剔除粗糙約簡子集中的冗余屬性,直至最終獲取到一個盡量最優的約簡結果.

算法2的最佳運行時間有兩種:

4 實例分析

算法1和算法2基于概率三支決策模型,簡述了基于相對依賴度和信息熵的特定類的三支屬性約簡過程,為了進一步說明這兩種算法的有效性和可解釋性,下面以表1為例進行分析和說明,并詳細給出算法1和算法2對一致決策系統和不一致決策系統的計算過程.

某醫院診斷系統,如表1所示,xI代表病人,aI代表病癥,D為診斷結果.算法的有效性為:根據初步診斷結果分為三類病人,將患有“Φ”病的一類病人D1={x1,x2,x3}作為特定類,對其進行三支概率屬性約簡.算法的可解釋性為:D1的約簡子集即為醫生診斷病人是否患“Φ”病時需要檢查的部分病癥.即:檢查RPOS(D1)可知,POS(D1)中的病人患有“Φ”病、檢查RBND(D1)可知BND(D1)的病人可能患有“Φ”病;檢查RNEG(D1)可知NEG(D1)中的病人不患“Φ”病.

表1 某醫院診斷系統
Table 1 A hospital diagnostic system

一致表不一致表Ua1a2a3DUa1a2a3Dx1010Φx1100Φx2010Φx2011Φx3011Φx3001Φx4001Ψx4011Ψx5001Ψx5001Ψx6101Ψx6021Ψx7100Ωx7010Ψx8100Ω/////x9110Ω/////

設置閾值α=0.8;β=0.2,根據定義1可知,基于概率粗糙集的三支決策計算D1的正域、負域和邊界域,計算結果如表2,表中D1中的對象用粗體表示.

根據算法1和算法2,在實際應用或對大數據進行降維處理時,無需計算每個屬性子集下的相對依賴度和信息熵,但為了更詳細直觀地根據相對依賴度和信息熵來分析兩個算法的計算步驟,我們將所有計算結果置于表3中.

表2D1在各屬性子集下的正域、負域和邊界域
Table 2 Positive,negative,and boundary regions ofD1under each attribute subset

屬性子集 一致表不一致表BPOS(D1)BND(D1)NEG(D1)POS(D1)BND(D1)NEG(D1){a1,a2,a3}{x1,x2},{x3}?{x4,x5},{x6},{x7,x8},{x9){x1}{x2,x4},{x3,x5}{x6},{x7}{a2,a3}{x3}{x1,x2,x9}{x4,x5,x6},{x7,x8}{x1}{x2,x4},{x3,x5}{x6},{x7}{a1,a3}{x1,x2}{x3,x4,x5}{?x6},{x7,x8,x9}{x1}{x2,x3,x4,x5,x6}{x7}{a1,a2}{x1,x2,x3}?{x4,x5},{x6,x7,x8},{x9}{x1}{x2,x4,x7},{x3,x5}{x6}{a1}?{x1,x2,x3,x4,x5}{x6,x7,x8,x9}{x1}{x2,x3,x4,x5,x6,x7}?{a2}?{x1,x2,x3,x9}{x4,x5,x6,x7,x8}?{x1,x3,x5},{x2,x4,x7}{x6}{a3}?{x1,x2,x7,x8,x9}{x3,x4,x5,x6}?{x1,x7},{x2,x3,x4,x5,x6}?

下面將根據算法1和算法2,以表1左側中的一致表為例,詳細計算代數觀點和信息論觀點下的特定類D1的正域、邊界域和負域約簡過程和結果,以下算法中的步驟與第3節中算法1和算法2一一對應..

算法1.

1.正域約簡:

第1步.計算特定類D1的正域約簡中的核屬性.

rrelative(D1|C-{a1})=0.333<α=0.8;

rrelative(D1|C-{a2})=0.667<α=0.8;

rrelative(D1|C-{a3})=1>α=0.8;

第2步.將第1步計算而來的核屬性賦值給R,并將R作為正域約簡的起點.

第3步.不斷添加重要的屬性到R中,直至獲取到與屬性全集具有相同劃分劃分能力的約簡子集.

第4步.因為Rrelative(D1|R)=Rrelative(D1|{a1,a2})=1>α所以跳出while循環,此時R={a1,a2}.

第5、6步.剔除R中的冗余屬性.

第8步.輸出D1的最終的正域約簡子集:

上述屬性約簡結果的語義解釋:醫生只需要檢查{a1,a2}兩項病癥便可診斷出{a1,a2}下的POS(D1)中的{x1,x2,x3}患有Φ病,既能減少檢查費,又能減少病人的檢查時間和檢查疼痛等代價.

表3 各屬性子集關于D1的相對依賴度和信息熵
Table 3 Relative dependence and information entropy ofD1under each attribute subset

屬性子集 一致表不一致表BrrelativeHPOSITHBNDITHNEGITrrelativeHPOSITHBNDITHNEGIT{a1,a2,a3}1.0000.2510.0000.5021.0000.1210.1570.212{a2,a3}0.3330.1060.1590.3041.0000.1210.1570.212{a1,a3}0.6670.1450.1590.2651.0000.1210.1420.106{a1,a2}1.0000.1590.0000.4101.0000.1210.3040.106{a1}0.0000.0000.1420.1571.0000.1210.1420.000{a2}0.0000.0000.1570.1420.0000.0000.3180.106{a3}0.0000.0000.1420.1570.0000.0000.2870.000

2.邊界域約簡:

第1步.計算特定類D1的邊界域約簡中的核屬性.

rrelative(D1|C-{a1})=0.333∈(β,α);

rrelative(D1|C-{a2})=0.667∈(β,α);

rrelative(D1|C-{a3})=1?(β,α);

第2步.將核屬性賦值給R,作為邊界域約簡的起點.

第3步.獲取D1初步的邊界域約簡子集.

因為rrelative(D1|R)=rrelative(D1|{a3})=0?(β,α),且SIG(a1,R,D1)=0.667>SIG(a2,R,D1)=0.333,所以選出C中除a3外最重要的屬性(a0=a1)并入R中,即R=a3∪a1={a1,a3},此時rrelative(D1|{a1,a3})=0.6667∈(β,α),

第4步.結束while循環.

第5步.剔除冗余屬性.

rrelative(D1|{a1,a3}-{a1})=rrelative(D1|{a1,a3}-{a3})=0?(β,α).

第6步.結束for循環.

第8步.輸出D1的最終的邊界域約簡子集.

上述屬性約簡結果的語義解釋:如果醫生檢查{a1,a3},便可診斷出{a1,a3}下的BND(D1)中的x3、x4和x5可能患有Φ病.假設檢查a2的費用遠高于檢查a3的費用,若病人x3經濟條件受限又想知道自己是否可能患有Φ病的時候,則可選擇這種診斷方案.

3.負域約簡:

第1步.計算特定類D1的負域約簡中的核屬性.

rrelative(D1|C-{a1})=0.3333>β=0.2;

rrelative(D1|C-{a2})=0.6667>β=0.2;

rrelative(D1|C-{a3})=1>β=0.2;

因為負域約簡算法不同于正域約簡算法1，此時省略第3步和第4步.

第5步.依次剔除最重要的屬性,直至rrelative(D1|R)<β.

此時rrelative(D1|R)=rrelative(D1|C)>β∧|R|>1,進入while循環,依次剔除最重要的屬性,因為SIG(a1,R,D1)=0.667>SIG(a2,R,D1)=0.333>SIG(a3,R,D1)=0,所以a0={a1},即R=C-a1={a2,a3},此時,rrelative(D1|{a2,a3})=0.333>β,因此繼續剔除重要屬性,因為SIG(a2,R,D1)=SIG(a3,R,D1)=0,按順序選擇a0={a2},即R={a2,a3}-{a2}={a3},此時rrelative(D1|{a3})=0<β.

第6步.跳出for循環.

上述屬性約簡結果的語義解釋:如果醫生只檢查a3,便可診斷出基于a3劃分的NEG(D1)中的{x3,x4,x5,x6}不患Φ病.

同理,可基于相對依賴度獲取不一致表中D1的三支概率約簡子集,計算結果如表4所示.

算法2.

1.正域約簡:

第1步.基于信息熵計算D1的正域約簡的核屬性.

第2步.將核屬性賦值給R.

第3步.獲取與C具有相同的正域劃分能力的屬性子集R.

上述屬性約簡結果的語義解釋:通過基于信息熵的屬性約簡方式進行醫療診斷,醫生必須同時檢查{a1,a2,a3}這三種病癥,才能確診POS(D1)中的{x1,x2,x3}都患Φ病.對比分析可知,通過相對依賴度的屬性約簡方式進行醫療診斷時,醫生只檢查{a1,a2}也能{x1,x2,x3}都患Φ病.雖然后者比前者的診斷成本更高,但診斷結果沒前者精準.

2.邊界域約簡:

第1步.計算D1的邊界域約簡的核屬性.

第3步.依次選取最重要的屬性存入R中,直至R劃分邊界域的信息熵高于C劃分邊界域的信息熵.

上述屬性約簡結果的語義解釋:醫生通過檢查a3可診斷出BND(D1)中的{x1,x2,x7,x8,x9}可能患Φ病.

3.負域約簡:

第1步.計算D1的負域約簡的核屬性.

第3步.獲取與C具有相同的負域劃分能力的屬性子集R.

上述屬性約簡結果的語義解釋:醫生必須檢查{a1,a2,a3}這三個項目,才能確診NEG(D1)的{x4,…,x9}不患Φ病,同時也能推斷出{x1,x2,x3}一定或可能患Φ病.

同理,基于信息熵計算不一致表中D1的三支概率約簡子集,計算結果如表4所示.

表4 特定類三支概率屬性約簡結果
Table 4 Three-way probabilistic attribute reduction results on class-specific

各域約簡子集一致表不一致表RPOS(D1)RPOSrelative(D1){a1,a2}{a1}RPOSIT(D1){a1,a2,a3}{a1}RBND(D1)RBNDrelative(D1){a1,a3}NULLRBNDIT(D1){a3}{a2}RNEG(D1)RNEGrelative(D1){a3}{a2}RNEGIT(D1){a1,a2,a3}{a2,a3}

通過表4中的基于相對依賴度和基于信息熵的特定類的三支概率屬性約簡結果可知:不一致表下的約簡子集要小于一致表下的約簡子集;基于相對依賴度求解的約簡子集要小于基于信息熵求解的約簡子集,但前者有時可能較難獲取不一致表的邊界域約簡,且其約簡子集下的分類準確率一定程度上低于后者.綜上分析,兩種算法都有各自的優缺點,因此,在實際應用中,應根據決策系統的數據特征、可承受的約簡代價范圍和所期待的分類準確率等實際情況選擇最合理的約簡方式.

本文提出了代數觀點下的基于相對依賴度和信息論觀點下的基于信息熵的三支概率屬性約簡方法,并對不同決策系統中的特定類的正域、邊界域和負域的進行了有效地屬性約簡,為人們在現實生活選擇不同的決策方式提供了依據,也一定程度上減少了人們的決策代價.

5 總 結

針對決策系統中的特定類,本文從代數和信息論視角,分別構建了基于相對依賴度和基于信息熵的正域、負域和邊界域約簡模型,并給出了對應的啟發式的屬性約簡算法.通過醫療診斷的實例詳細分析了兩種算法在一致決策系統和不一致決策系統上的約簡過程,并給出了有效的約簡結果,進一步驗證了算法的可行性和可解釋性.在下一步研究計劃中,將研究基于信息論中的條件熵和其他熵對特定類的三支概率屬性約簡方法,并通過實驗分析算法的約簡效率和分類精度,同時對比已有的相關算法.