基于決策分類的決策表分解方法研究
2009-01-01 00:00:00王加陽胡沛
計算機應用研究 2009年1期
（中南大學 信息科學與工程學院， 長沙 410083）
摘 要：針對當前基于屬性重要性的決策表屬性集分解方法存在的不足，提出了一種新型的基于決策分類的決策表屬性集分解方法。分析了近似分類質(zhì)量和屬性重要性與決策分類之間的關系，利用粗糙集理論，從提高子決策表中決策分類正確性的角度出發(fā)考慮條件屬性與決策屬性之間的關系，提出了決策表分解的條件屬性選擇量度并對決策表實施屬性集分解。
關鍵詞：決策表； 分解； 粗糙集理論
中圖分類號：TP18 文獻標志碼：A
文章編號：10013695(2009)01010803
Research on decomposition of decision table based on decision making
WANG Jiayang， HU Pei
(College of Information Science Engineering， Central South University， Changsha 410083， China)
Abstract:There are some defects in the attribute set decomposition of decision table based on the attribute significance. The paper introduced a novel feature decomposition of decision table approach based on decision making. It analyzed the differences between the quality of approximation and the attribute significance to decision making. With the rough set theory， the relationships of condition attributes and decision attributes were considered increasing the attribute classification rate in the decision table， and a new attribute selection criterion was proposed. Then decision table was decomposed with the attribute selection criterion.
Key words：decision table; decomposition; rough set theory
隨著計算機和數(shù)據(jù)采集技術的進步，數(shù)據(jù)的積累無論是在數(shù)據(jù)對象個數(shù)上還是在數(shù)據(jù)維度上都以無法估算的速度迅速增長。數(shù)據(jù)量的不斷增大給現(xiàn)有的數(shù)據(jù)分析和處理技術提出了挑戰(zhàn)，許多實際的決策表包含了大量的對象和屬性，如何從這些堆積如山的數(shù)據(jù)中挖掘有用的信息已成為當今數(shù)據(jù)挖掘領域的熱點[1 ]。決策表分解是解決大型決策表數(shù)據(jù)海量性和復雜性問題的一種有效手段。其思想是將一個大型決策表分解為若干規(guī)模較小且易于處理的子表，在子表中進行規(guī)則獲取，可以減少每次處理的數(shù)據(jù)量，避免直接在復雜系統(tǒng)中建模的困難和缺陷，提高數(shù)據(jù)分析的效率和質(zhì)量[2 ]。
本文提出了一種基于決策分類的決策表分解方法。首先從條件屬性與決策屬性之間的關系出發(fā)，分析了近似分類質(zhì)量和屬性重要性與決策分類的關系，根據(jù)提高子決策表條件屬性正確分類能力的標準提出了一種新的條件屬性選擇量度，按照屬性選擇量度指導子決策表的屬性選取，將決策表分解為幾個子決策表。
1 粗糙集理論基本概念
粗糙集理論是波蘭數(shù)學家Z.Pawlak于1982年提出的一種處理含糊和不確定性問題的新型數(shù)學工具，已經(jīng)在機器學習、數(shù)據(jù)挖掘等領域中得到廣泛應用，決策表信息系統(tǒng)是粗糙集理論的主要研究對象[3]。
定義1 一個決策表信息系統(tǒng)S=〈U，R，V，f〉。其中：U是非空有限集合，即為論域；R=C∪D，C和D分別稱為條件屬性集和決策屬性集，D≠是非空有限集合；V=∪r∈RVr是屬性值的集合，Vr表示屬性r∈R的值域；f:U×A→V是一個信息函數(shù)，它指定U中每一個對象x的屬性值。
定義2 在決策表信息系統(tǒng)S=〈U，R，V，f〉中，對于BR，則B在U上的不可分辨關系定義為
IND(B)={(x1，x2)∈U×U｜b(x1)=b(x2)
b∈B}=Ib∈BIND(b)(1)
顯然IND(B)是一個等價關系，它的所有等價類的集合記為U｜IND(B)，簡記為U|B。
定義3 給定決策表信息系統(tǒng)S=〈U，R，V，f〉，對于每個子集XU和不可分辨關系B，X的下近似集和上近似集可以分別定義為
B_(X)=∪{Yi｜(Yi∈U｜IND(B)∧YiX)}(2)
B-(X)=∪{Yi｜(Yi∈U｜IND(B)∧Yi I X≠）}(3)
定義4 設U為一個論域，P、Q為U上的兩個等價關系簇，Q的P正域POSp(Q)定義為
POSp(Q)=∪X∈U/QP_(X)(4)
相對正域POSp(Q)是論域U的所有那些使用分類U｜P所表達的知識中能夠正確地分類到U｜Q的等價類之中的對象的集合。
定義5 設集合族F={X1，X2，…，Xn}（U=∪ni=1Xi ）是論域U上定義的知識，B是一個屬性子集，定義B對F近似分類質(zhì)量 rB(F)為
rB(F)=∑ni=1｜B_(Xi)｜/U｜(5)
定義6 F是屬性集D導出的分類，C是條件屬性集合，D＝g0gggggg是決策屬性集合，且AC則對于任意屬性a∈C-A的重要性SGA(a，A，D)為
SGA(a，A，D)= rA∪{a}(F)- rA(F)(6)
2 決策表分解
現(xiàn)實應用中，決策表的復雜性主要來自于屬性數(shù)量的增長。隨著屬性集的不斷擴大，為了建立有效的分類模型，避免出現(xiàn)過度擬合現(xiàn)象，訓練集中所需的對象數(shù)需呈指數(shù)級增長，針對決策表的復雜性首先考慮對屬性集的處理，力求減小屬性集的規(guī)模。
屬性集分解方法是從給定原始屬性集中按照一定的標準選取屬性結成一組，然后按照一定的算法來識別定義在屬性組上的中間概念層次，從而達到降維、增強模型可理解性的目的。這一方法要求在保持模型的分類能力的前提下，簡化計算并增強模型的可理解性。文獻[4，5]提出了基于屬性重要性的決策表屬性集分解方法，優(yōu)先選擇那些屬性重要性較大的條件屬性對決策分類；對于不能正確分類的對象，屬性重要性小的條件屬性可以對決策分類起輔助作用。由于屬性重要性反映的是去掉某條件屬性后對決策分類能力的影響，文獻[4，5]提到的決策表分解方法可能會導致屬性重要性較大的條件屬性所形成的子決策表對決策屬性具有較差的正域分類能力，不利于知識獲取。本文根據(jù)近似分類質(zhì)量和屬性重要性與決策分類的關系，從提高子決策表條件屬性分類能力出發(fā)提出了一種新的決策表分解屬性選擇量度，使其能夠有效地提高子決策表的決策分類質(zhì)量。
2.1 決策表條件屬性與決策屬性之間的關系研究
近似分類質(zhì)量和屬性重要性作為粗糙集理論中描述條件屬性與決策屬性之間關系的兩個重要概念，它們從不同的角度刻畫了條件屬性與決策屬性的關系。近似分類質(zhì)量只關注條件屬性對決策屬性正區(qū)域的變化情況；值越大表明該屬性集對決策屬性的正域分類能力越強。而屬性重要性側(cè)重反映在屬性集中增加條件屬性對近似分類質(zhì)量的影響，值越大說明去掉該屬性后引起的決策正域變化越大，即能正確分類到?jīng)Q策屬性劃分的等價類中的元素越少，該屬性對決策屬性越重要。
設B={x}為非空單屬性集，決策表中的條件屬性可能會出現(xiàn)B的近似分類質(zhì)量較大，而屬性x重要性卻很低的情況；也可能會出現(xiàn)屬性x重要性很高而B的近似分類質(zhì)量較小的情況。如表1所示，條件屬性集{a}和{b}具有最大的近似分類質(zhì)量，屬性a，b卻具有最小的屬性重要性；條件屬性c雖具有最大的屬性重要性，條件屬性集{c}卻具有最小的近似分類質(zhì)量。
2.2 決策表分解條件屬性的選擇研究
為了提高子決策表條件屬性對論域的正確分類能力，子表中的條件屬性進行選取時需從近似分類質(zhì)量和屬性重要性兩方面考慮。
1)子決策表中的對象能被盡可能多地正確分類
選取到子表中的第一個條件屬性b要有對決策屬性較強的正域分類能力。如果從屬性重要性的角度選取條件屬性，可能會出現(xiàn)由屬性重要性較大的條件屬性所形成的子表對決策屬性具有較差的正域分類能力。條件屬性b應從近似分類質(zhì)量考慮，單條件屬性集{b}需有最大的近似分類質(zhì)量 rB(F)；如果有多個單條件屬性集的近似分類質(zhì)量同為最大，從它們所包含的單條件屬性與決策屬性的重要性考慮，優(yōu)先選擇具有較大屬性重要性的。
如果一個決策表中每個條件屬性都不能對決策進行正確分類，即 rCi(F)＝0(Ci∈C）；如表2中所示的類似情況，應考慮使用條件屬性組合求其與決策屬性的近似分類質(zhì)量。具體方法為首先兩兩屬性組合，找出近似分類質(zhì)量值最大的組合；如果近似分類質(zhì)量仍為0，應使用三個屬性組合，依此類推。
2)子決策表的條件屬性對決策正域的劃分能很好地互補
選取到子表中的其他條件屬性能對決策分類起到很好的輔助作用。如果從近似分類質(zhì)量的角度選取條件屬性，雖可以保證條件屬性對論域有較強的正確分類能力，但可能會出現(xiàn)子表中的條件屬性對決策屬性的正域劃分有大量相交子集的情況，即子表中的各條件屬性的屬性重要性均較低，其余的條件屬性不能對現(xiàn)有的決策分類起到很好的輔助作用。選取到子表中的條件屬性a應滿足加入該屬性后子表的條件屬性對決策正域分類有較大增加，即相對于當前條件屬性集A，a屬性需有較大的屬性重要性SGA(a，A，D)。如果有多個屬性的屬性重要性同為最大，則從它們的分類能力考慮，優(yōu)先選擇具有較大正域分類能力的條件屬性。
定義7 F是屬性集D導出的分類，C是條件屬性集合，D＝g0gggggg是決策屬性集合，則對于任意屬性集AC的重要性SGA(A，C，D)=rc(F)-rc-A(F)。
如果條件屬性的屬性重要性均為0，如表3所示的類似情況，屬性b、c、e相對于{a}的屬性重要性均為0，此時應考慮使用條件屬性組合求屬性集的重要性。具體方法為首先兩兩屬性組合，找出屬性集重要性值最大的組合；如果屬性集重要性仍為0，應使用三個屬性組合，依此類推。
2.3 基于決策分類的決策表分解算法描述
對于含有多個決策屬性的決策屬性集D，可以將其轉(zhuǎn)換為單一的決策屬性，本文只考慮決策屬性集包含一個決策屬性d的情況，即D=g0gggggg，S=〈U，C∪D，V，f〉。
算法1 DDBDM
輸入：大型決策表S=〈U，C∪D，V，f〉。其中U為論域，C，D分別為條件屬性集和決策屬性集。
輸出：一系列符合要求的子表。
a）設置每個子表所允許的最大條件屬性集個數(shù)為n′（n′由用戶實際需要設置或由專家結合問題的先驗知識確定）。
b)設決策屬性D的等價類F=U｜D={D1，D2，…，Dm}，用式（5）計算C中各單屬性集的近似分類質(zhì)量，取滿足MAX( rB(F) )的屬性x。如果值為0，使用屬性組合求值最大的 rB(F)屬性集x，j=0，Rj=，k＝0。
c)將x加入集Rj中，k++。若C=，跳到g)執(zhí)行；若C≠，判斷是否滿足k≤n′，如果滿足的話，重復執(zhí)行d)；如果不滿足，執(zhí)行b)。
d)用式（6）計算C中各屬性的屬性重要性，取滿足MAX(SGA(a，Rj，D))的條件屬性y。如果值為0，使用屬性組合求值最大的SGA(a，A，D)屬性集y；將y加入Rj。
e)C=C-Rj，生成決策表Sj=〈U，Rj，V，f〉和T′j=〈U，C，V，f〉。其中：Sj為新生成的子決策表；T′j為中間決策表；++j。
f)對中間決策表T′j重復b)~e)。
g)輸出各子表Si （0≤i≤j）。
3 基于決策分類的決策表分解實例
如表4所示的決策表，C={a，b，c，e，f，g}是條件屬性集合，D=g0gggggg是決策屬性集合。下面利用本文所提到的基于決策分類的決策表分解方法對決策表4進行屬性集分解。
a)定義子表中所允許的最大條件屬性個數(shù)n′=3。
b)計算各單條件屬性集的近似分類質(zhì)量：
r{a}(F)=0.5r{b}(F)=0.4r{c}(F)=0.3
r{e}(F)=0.3r{f}(F)=0.1r{g}(F)=0
c){a}的近似分類質(zhì)量最大，選a進入子決策表1(表5)，求此時基于屬性集{a}的屬性重要性：
SGA(b，{a}，D)=0 SGA(c，{a}，D)=0.3
SGA(e，{a}，D)=0.1 SGA(f，{a}，D)=0.2
SGA(g，{a}，D)=0.3
d)屬性c、g相對于{a}的屬性重要性最大，選c進入子決策表1，求此時基于屬性集{a，c}的屬性重要性：
SGA(b，{a，c}，D)=0SGA(e，{a，c}，D)=0
SGA(f，{a，c}，D)=0.2SGA(g，{a，c}，D)=0.2
e)屬性f、g相對屬性{a，c}的屬性重要性最大，選f進入子決策表1；
f)同理，屬性b、e、g選入子決策表2（表6），分解結束。
4 結束語
從決策表中快速有效地提取規(guī)則是決策表分解的主要目的。基于決策分類的決策表方法從決策分類和知識發(fā)現(xiàn)的角度考慮條件屬性與決策屬性之間的關系，從屬性重要性和近似分類質(zhì)量兩個角度對決策表進行分解，能使子決策表中被正確分類的對象盡可能多，提高了決策分類質(zhì)量，有利于發(fā)現(xiàn)知識之間的隱含關系。本方法結構簡單，能夠很好地解決大型決策表的分解問題。
參考文獻：
［1］PAWLAK Z. Theorize with data using rough sets[C]//Proc of the 26th Annual International Computer Software and Applications Conference. Los Alamitos:IEEE Press， 2002:11251128.
[2]王加陽，劉柳明，羅安.大型決策表分解方法研究[J]. 計算機科學，2007，34(8)：211214.
[3]PAWLAK Z．Rough sets[J]．International Journal of Computer and Information Sciences，1982，11(5)：341356.
[4]樊群，趙衛(wèi)東，達慶利.一種基于粗集的實例分解歸納學習方法[J]. 管理工程學報，2001，15(2)：7981.
[5]趙衛(wèi)東，李旗號. 復雜決策表的特征提取方法研究[J]. 小型微型計算機系統(tǒng)，2002，10(23)：12411244.
