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

張 政 胡 沛

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

?

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

張 政 胡 沛

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

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

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

Class Number TP18

1 引言

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

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

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

2 粗糙集理論基本概念

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

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

(1)

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

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

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

(2)

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

(3)

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

(4)

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

(5)

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

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

(6)

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

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

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

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

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

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

為了提高子決策表的決策分類質量,子表條件屬性的選取從屬性重要性和近似分類質量考慮,子表條件屬性的選取需滿足以下條件：

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

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

3.3 屬性集分解等價性判定

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

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

3.4 算法描述

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

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

算法1.DDBDE

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

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

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

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

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

4 改進的決策表屬性集分解

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

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

4.1 子決策表條件屬性的選擇

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

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

4.2 屬性集分解等價性判定

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

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

4.3 算法描述

算法2.ADDBDE

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

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

Step3. 將x并入集Rj中,k++。若C=Φ,跳到Step7執行。若C≠Φ,判斷是否滿足k≤n,如果滿足的話,執行Step4；如果不滿足,執行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中增加相應分類信息C′,且rC′(R)=1,C′?Rj,|C′|的值應最小,將C′并入C中。

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

4.4 屬性集分解方法的比較

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

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)。

證明 因為|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從分類質量、決策等價性、時間復雜度等方面對上述幾種決策表屬性集分解方法進行比較。

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

5 基于決策分類的決策表分解實例

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

表2 決策表1

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

表3 子決策表1

表4 子決策表2

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

表5 子決策表3

表6 子決策表4

6 結語

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

[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].計算機科學，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] 樊群，趙衛東，達慶利.一種基于粗集的實例分解歸納學習方法[J].管理工程學報，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] 楊善林，劉業政，李亞飛.基于Rough Sets理論的證據獲取與合成方法[J].管理科學學報，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] 劉業政.基于粗糙集數據分析的智能決策支持系統研究[D].合肥：合肥工業大學，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].計算機應用研究，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日

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

TP18

10.3969/j.issn.1672-9722.2016.11.026