張 政 胡 沛

(南陽理工學(xué)院軟件學(xué)院 南陽 473000)

?

基于決策等價性的決策表屬性集分解研究*

張 政 胡 沛

(南陽理工學(xué)院軟件學(xué)院 南陽 473000)

決策表屬性集分解是處理決策大型決策表數(shù)據(jù)復(fù)雜性,提高數(shù)據(jù)分析的一種有效手段,已得到深入研究。但在屬性集分解過程中,有可能出現(xiàn)決策規(guī)則的泛化,從而導(dǎo)致從原決策表與從子決策表得到的規(guī)則不一致性。論文深入研究了決策表屬性集分解的等價性問題,從保持決策表等價性和提高子表分類質(zhì)量的角度,提出了基于決策等價的決策表屬性集分解方法,并與現(xiàn)有的屬性集分解方法做了比較。

決策表; 屬性集; 分解; 等價性

Class Number TP18

1 引言

傳統(tǒng)的數(shù)據(jù)挖掘和知識歸納方法在決策表分析和處理中得到了較好的應(yīng)用,但是隨著計(jì)算機(jī)和數(shù)據(jù)采集技術(shù)的進(jìn)步,許多大型決策表包含了大量的屬性和對象,如何從這些堆積如山的數(shù)據(jù)中挖掘有用的信息,已成為當(dāng)今數(shù)據(jù)挖掘領(lǐng)域的熱點(diǎn)[1]。

決策表分解是解決大型決策表數(shù)據(jù)海量性和復(fù)雜性問題的一種有效手段。其思想是將一個大型決策表分解為若干規(guī)模較小且易于處理的子表,在子表中進(jìn)行規(guī)則獲取,可以減少每次處理的數(shù)據(jù)量,避免直接在復(fù)雜系統(tǒng)中建模的困難和缺陷,提高數(shù)據(jù)分析的效率和質(zhì)量[2]。

本文提出了基于決策等價性的決策表屬性集分解方法。首先根據(jù)決策表屬性集分解的等價性,提出了決策等價性判定標(biāo)準(zhǔn),然后從決策等價和提高決策分類質(zhì)量的標(biāo)準(zhǔn)出發(fā),提出了一種新的條件屬性選擇量度,按照屬性選擇量度指導(dǎo)子決策表的屬性選取,將決策表分解為幾個決策等價的子決策表。

2 粗糙集理論基本概念

粗糙集理論是波蘭數(shù)學(xué)家Z.Pawlak于1982年提出的一種處理含糊和不確定性問題的新型數(shù)學(xué)工具,已經(jīng)在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域中得到廣泛應(yīng)用,決策表信息系統(tǒng)是粗糙集理論的主要研究對象[3]。

定義2 在決策表信息系統(tǒng)S=〈U,R,V,f〉中,對于B?R,則B在U上的不可分辨關(guān)系定義為

(1)

顯然IND(B)是一個等價關(guān)系,它的所有等價類的集合記為U|IND(B),簡記為U|B。

定義3 給定決策表信息系統(tǒng)S=〈U,R,V,f〉,對于每個子集X?U和不可分辨關(guān)系B,X的下近似集和上近似集可以分別定義為

B-(X)=∪{Yi|(Yi∈U|IND(B)∧Yi?X)}

(2)

B-(X)=∪{Yi|(Yi∈U|IND(B)∧Yi∩X≠φ)}

(3)

定義4 設(shè)U為一個論域,P、Q為U上的兩個等價關(guān)系簇,Q的P正域POSP(Q)定義為

(4)

相對正域POSP(Q)是論域U的所有那些使用分類U|P所表達(dá)的知識中能夠正確地分類到U|Q的等價類之中的對象的集合。

(5)

定義6F是屬性集D導(dǎo)出的分類,C是條件屬性集合,D=syggg00是決策屬性集合,且A?C則對于任意屬性a∈C-A的重要性SGA(a,A,D)為

SGA(a,A,D)=rA∪{a}(F)-rA(F)

(6)

3 等價的決策表屬性集分解

決策表屬性集分解是從給定原始屬性集中按照一定的標(biāo)準(zhǔn)選取屬性結(jié)成一組,然后按照一定的算法來識別定義在屬性組上的中間概念層次,從而到達(dá)降維、增強(qiáng)模型可理解性的目的。這一方法要求在保持模型的分類能力的前提下,簡化計(jì)算并增強(qiáng)模型的可理解性。

決策表屬性集分解減少了每次處理的數(shù)據(jù)量,使得適合普通決策表的算法也能適用于復(fù)雜的大型決策表,各子表之間可以進(jìn)行并行計(jì)算,減小時間復(fù)雜度,提高數(shù)據(jù)分析的效率。目前決策表屬性集分解方法主要有：基于函數(shù)的分解方法[4],基于屬性核的分解方法[5]和基于屬性聚類的分解方法[6]；這些屬性集分解方法雖得到了較好的應(yīng)用,但由于沒考慮到分解前后決策等價性的問題,致使得到的決策存在規(guī)則泛化的可能。本文以分解前后決策等價為標(biāo)準(zhǔn),從提高子決策表?xiàng)l件屬性分類能力出發(fā)提出了新的決策表分解屬性集方法,使其能保持分解前后決策等價性。對于含有多個決策屬性的決策屬性集D,可以將其轉(zhuǎn)換為單一的決策屬性[7],本文中只考慮決策屬性集只包含一個決策屬性d的情況,即D=syggg00,S=〈U,C∪D,V,f〉。

3.1 決策表屬性集分解的等價性

決策表分解的決策等價性是指通過原決策表歸納所得到的決策結(jié)果與分解后綜合各子表局部規(guī)則得到的決策結(jié)果相同[8～9]。屬性集分解過程中,由于子決策表屬性個數(shù)減少,僅由部分條件屬性推導(dǎo)的規(guī)則可能出現(xiàn)泛化,增大了分類決策的不確定性。

3.2 決策表分解條件屬性的選擇

為了提高子決策表的決策分類質(zhì)量,子表?xiàng)l件屬性的選取從屬性重要性和近似分類質(zhì)量考慮,子表?xiàng)l件屬性的選取需滿足以下條件：

1) 選入子表的第一個條件屬性b需要對論域有最大的正域分類能力,即單條件屬性集需有最大的近似分類質(zhì)量rB(F)；

2) 選入子表的其它條件屬性需對決策分類起很好的輔助作用,即相對于當(dāng)前子表中的條件屬性集A,要有最大的屬性重要性SGA(a,A,D)。

3.3 屬性集分解等價性判定

首先考慮將原決策表S分解為兩個子決策表S1和S2的情況,它們對應(yīng)的條件屬性子集分別為C1和C2。如果對于?u∈U,δC(u)=δC1(u)∩δC2(u),則該分解是一次等價的屬性集分解；如果有δC(u)?δC1(u)∩δC2(u),則該分解不是等價的屬性集分解,需要在表S2中增加相應(yīng)的分類信息,具體方法為：

找出決策規(guī)則信息丟失對象R,即論域中所有δC(u)?δC1(u)∩δC2(u)的對象,在表S2增加相應(yīng)分類條件屬性集C′,且C′與R的關(guān)聯(lián)度為1；為了保證C′個數(shù)盡可能少,應(yīng)從單屬性考慮,如果單屬性集與R的關(guān)聯(lián)度不為1,則考慮使用屬性組合。S分解為多個子表的等價性判定與分解為2個子表的方法類似。

3.4 算法描述

輸入：大型決策表S=〈U,C∪D,V,f〉；其中U為論域,C,D分別為條件屬性集和決策屬性集。

輸出：一系列符合要求的子表。

算法1.DDBDE

Step1. 設(shè)置每個子表所允許的最大條件屬性集個數(shù)為n′(n′由用戶實(shí)際需要設(shè)置或由專家結(jié)合問題的先驗(yàn)知識確定)。

Step2. 設(shè)決策屬性D的等價類：F=U|D={D1,D2,…,Dm},用式(5)計(jì)算C中各單屬性集的近似分類質(zhì)量,取滿足：MAX(rB(F))的屬性x；j=0,Rj=Φ,k=0。

Step3. 將x并入集Rj中,k++。若C=Φ,跳到Step7執(zhí)行。若C≠Φ,判斷是否滿足k≤n,如果滿足的話,執(zhí)行Step4；如果不滿足,執(zhí)行Step2。

Step4. 用式(6)求出C中各屬性的屬性重要性,取滿足MAX(SGA(a,Rj,D))的條件屬性y,將y加入Rj,C=C-Rj。

Step8. 輸出各子表Si(0≤i≤j)。

4 改進(jìn)的決策表屬性集分解

為了保證屬性集分解的等價性,算法DDBDE需要在每次分解完成后要判斷從子表得到的決策屬性交集與原決策表的決策值是否相等,需要大量的運(yùn)算,不利于提高算法的效率。

rB(Xi)=|B_(Xi)|/|U|

4.1 子決策表?xiàng)l件屬性的選擇

1) 選入子表的第一個條件屬性b需要對論域有最大的正域分類能力,即單條件屬性集需有最大的近似分類質(zhì)量rB(F)；

2) 選入子表的其它條件屬性需對決策分類起很好的輔助作用,即相對于當(dāng)前子表中的條件屬性集A,要有最大的屬性重要性SGA(a,A,D)。

4.2 屬性集分解等價性判定

首先考慮將原決策表S分解為兩個子決策表S1和S2的情況,它們對應(yīng)的條件屬性子集分別為C1和C2。如果POSC1(D)∪POSC2(D)=U,則該分解是一次等價的屬性集分解；如果POSC1(D)∪POSC2(D)?U,表明本次分解可能不是等價的,導(dǎo)致決策正域分類信息丟失,對子表S2應(yīng)增加相關(guān)的決策正域分類信息。具體方法如下：

找出決策正域分類信息丟失對象R=U-(POSC1(D)∪POSC2(D)),在表S2增加相應(yīng)決策正域分類條件屬性集C′,使rC′(R)=1,且C′?C1；為了保證C′個數(shù)盡可能少,應(yīng)從單屬性考慮,如果單屬性集不能對R正確分類,則考慮使用屬性組合。S分解為多個子表的等價性判定與分解為2個子表的方法類似。

4.3 算法描述

算法2.ADDBDE

Step1. 設(shè)置每個子表所允許的最大條件屬性集個數(shù)為n′(n′由用戶實(shí)際需要設(shè)置或由專家結(jié)合問題的先驗(yàn)知識確定)。

Step2. 設(shè)決策屬性D的等價類：F=U|D={D1,D2,…,Dm},用式(5)計(jì)算C中各單屬性集的近似分類質(zhì)量,取滿足：MAX(rB(F))的屬性x；j=0,Rj=Φ,k=0。

Step3. 將x并入集Rj中,k++。若C=Φ,跳到Step7執(zhí)行。若C≠Φ,判斷是否滿足k≤n,如果滿足的話,執(zhí)行Step4；如果不滿足,執(zhí)行Step2。

Step4. 用式(6)求出C中各屬性的屬性重要性,取滿足MAX(SGA(a,Rj,D))的條件屬性y,將y加入Rj,C=C-Rj。

Step6.R=U-(POSRj(D)∪POSC-Rj(D)),如果R=Φ,表明此次分解為等價的屬性集分解,如果R≠Φ,表明此次分解有決策正域分類信息丟失,需要在C中增加相應(yīng)分類信息C′,且rC′(R)=1,C′?Rj,|C′|的值應(yīng)最小,將C′并入C中。

Step8. 輸出各子表Si(0≤i≤j)。

4.4 屬性集分解方法的比較

滿足算法ADDBDE的決策等價判定必滿足算法DDBDE的等價判定,故ADDBDE可以看作是DDBDE的特例,滿足ADDBDE的等價分解必滿足DDBDE,因此ADDBDE中的冗余條件屬性個數(shù)大于或等于DDBDE中的冗余條件屬性數(shù)；但ADDBDE只需計(jì)算各子表的正域分類情況,無需推導(dǎo)相應(yīng)的決策規(guī)則,比DDBDE具有較小的時間復(fù)雜度和空間復(fù)雜度。

SGA(a,A,Xi)=rA∪{a}(Xi)-rA(Xi)。

定理2 決策表S=〈U,C,D,V,f〉,如果POSC′(D)∪POSC-C′(D)=U,則rC′(F)≥SGA(C′,C,D)。

證明 因?yàn)閨POSC′(D)∪POSC-C′(D)|=|POSC′(D)|+|POSC-C′(D)|-|POSC′(D)|∩|POSC-C′(D)|=|U|。

即rC′(F)-(|POSC′(D)|∩|POSC-C′(D)|)/|U|=SGA(C′,C,D)

故rC′(F)≥SGA(C′,C,D)。

證畢。

推論1 如果rC′(F)

表1從分類質(zhì)量、決策等價性、時間復(fù)雜度等方面對上述幾種決策表屬性集分解方法進(jìn)行比較。

表1 決策表屬性集分解方法的比較

5 基于決策分類的決策表分解實(shí)例

如表1所示的決策表,C={a,b,c,e,f,g}是條件屬性集合,D=syggg00是決策屬性集合。下面利用本文所提到的基于決策等價的決策表屬性集分解方法對決策表2進(jìn)行屬性集分解。

表2 決策表1

用算法DDBDE可以將其分解成表3和表4。

表3 子決策表1

表4 子決策表2

用算法ADDBDE可以將其分解成表5和表6。

表5 子決策表3

表6 子決策表4

6 結(jié)語

從決策表中快速有效地提取規(guī)則是決策表分解的主要目的。分解前后決策分類的等價性是影響決策表分解質(zhì)量的關(guān)鍵因素,在分解過程中要力求保證決策等價和信息無損,避免決策表分解對分類結(jié)果帶來的不確定性。本文提出了兩種基于決策等價的屬性集分解方法,分解的每次過程都保證了分解的等價性,使決策表分解前后從原表與從子表得到的規(guī)則一致；并從分類質(zhì)量、決策等價性和時間復(fù)雜度等方面與傳統(tǒng)的屬性集分解方法做了比較。

[1] Z.Pawlak. Theorize with Data using Rough Sets[C]. Proceedings of the 26th Annual International Computer Software and Applications Conference.IEEE， 2002.

[2] 王加陽, 劉柳明, 羅安. 大型決策表分解方法研究[J].計(jì)算機(jī)科學(xué)，2007，34(8)：211-214. WANG Jiayang, LIU Liuming, LUO An. Research on Decomposition of Large Decision Table[J]. Computer Science，2007，34(8)：211-214.

[3] Z.Pawlad.Rough Sets[J].International Journal of Computer and Information Sciences，1982，11：341-356

[4] B. Zupan, M. Bohanec, I. Bratko, et al. A Dataset Decomposition Approach to Data Mining and Machine Discovery[C]//D. Heckerman eds. Proc. of the Third International Conference on Knowledge Discovery and Data Mining. Irvine, CA: AAAI Press,1997:299-303

[5] 樊群，趙衛(wèi)東，達(dá)慶利.一種基于粗集的實(shí)例分解歸納學(xué)習(xí)方法[J].管理工程學(xué)報(bào)，2001，15(2)：79-81. FAN Qun，ZHAO Weidong，DA Qingli. A Decision Table Decomposition Induction Learning Method Based on Rough Set[J]. Journal of Industrial Engineering and Engineering Management，2001,15(2)：79-81.

[6] 楊善林，劉業(yè)政，李亞飛.基于Rough Sets理論的證據(jù)獲取與合成方法[J].管理科學(xué)學(xué)報(bào)，2005，8(5)：69-75. YANG Shanlin，LIU Yezheng，LI Yafei. Research on Rough Sets-based Evidence Acquirement and Combination of DST[J].Journal of Management Sciences，2005,8(5)：69-75.

[7] 劉業(yè)政.基于粗糙集數(shù)據(jù)分析的智能決策支持系統(tǒng)研究[D].合肥：合肥工業(yè)大學(xué)，2003:23-24. LIU Yezheng. Research on Rough Set Data Analysis Based Intelligent Decision Support Systems[D]. Hefei：HeFei University of Technology，2003:23-24.

[8] Kusiak. A. Decomposition in Data Mining: A Medical Case Study[C]. In: B.V.Dasarathy, eds. Proceedings of the SPIE Conference on Data Mining and Knowledge Discovery: Theory, Tools, and TechnologyⅢ. Orlando,2001:267-27.

[9] 劉柳明，王加陽，羅安.決策表屬性集分解的等價性研究[J].計(jì)算機(jī)應(yīng)用研究，2007，24(8)：67-69. LIU Liuming，WANG Jiayang，LUO An. Research on Equivalence of Attribute Set Decomposition to Decision Table[J]. Application Research of Computers，2007,24(8)：67-69.

[10] Hadjimichael M.,Wong S.K.M.,Ziarko W. Rough Sets:Probabilistic versus Deterministic[J]. International Journal of Man-Machine Studies,1988,29(29):81-95.

[11] Ziarko W. Analysis of uncertain information in the framework of variable precision rough sets[J]. Foundations of Computing and Decision Science 1993,18(3/4):381-396.

Attribute Set Decomposition of Decision Table Based on Decision Making Equivalence

ZHANG Zheng HU Pei

(College of Software, Nanyang Institute of Technology, Nanyang 473000)

Attribute set decomposition of decision table as a useful method deals with data complexities of the large decision tables and improves data analysis. It had in-depth studied by many scholars. But it may appears decision rules generalization during the attribute set decomposition, so it may led differences of the rules from the original decision table and the child decision tables. The paper went deep into the equivalence of attribute set decomposition, and proposed novel attribute set decomposition approaches from keeping the equivalence of decision table and improving the classification rate in the child decision tables and compared the methods with existing methods of attribute set decomposition.

decision table, attribute set, decomposition, equivalence

2016年5月16日,

2016年6月30日

張政,男,碩士，講師，研究方向：數(shù)據(jù)挖掘、粗糙集理論及應(yīng)用、云計(jì)算與大數(shù)據(jù)。胡沛,男, 碩士,講師，研究方向：嵌入式、數(shù)據(jù)挖掘、粗糙集理論及應(yīng)用。

TP18

10.3969/j.issn.1672-9722.2016.11.026