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

摘要：論述了決策表屬性集分解的概念和必要性，對分解中的決策等價性問題進行分析，提出了決策表論域上的弱等價條件和部分等價條件，并針對弱等價性判斷標準的局限性，進一步提出了決策表樣本集取值空間上的強等價條件，使得決策等價性的判斷標準更為完備。

關(guān)鍵詞：決策表；分解；等價性；屬性集

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2007)08－0067－03



傳統(tǒng)的數(shù)據(jù)挖掘和知識歸納方法在決策表分析和處理中得到了較好的應用，但是隨著數(shù)據(jù)規(guī)模的不斷擴大，許多大型決策表含有大量的屬性和對象，結(jié)構(gòu)復雜，給數(shù)據(jù)分析和處理帶來不少困難，計算復雜度上升，規(guī)則質(zhì)量和分類精度下降。

屬性數(shù)量的龐大是造成大型決策表分析困難的主要原因之一，從屬性集的角度對決策表進行分解是一種有效的數(shù)據(jù)轉(zhuǎn)換方法。通過屬性集的分解得到的子決策表規(guī)模較小且更易于處理，可以減少每次處理的數(shù)據(jù)量，提高數(shù)據(jù)分析的效率和質(zhì)量。分解前后決策分類的等價性是影響決策表分解質(zhì)量的關(guān)鍵因素，在分解過程中要力求保證決策等價、信息無損，因此有必要建立分解前后決策等價性的判斷標準。

1決策表屬性集分解

決策表是一種將條件屬性和決策屬性區(qū)分開來的知識表示系統(tǒng)，由對象集、條件屬性集和決策屬性集組成，是信息系統(tǒng)的一種特殊情況，為數(shù)據(jù)集中的規(guī)則推導和知識發(fā)現(xiàn)提供基礎(chǔ)。它可以表示為一個四元組：T=(U，R，V，f)。其中：論域U是對象的集合，R=C∪D是屬性集合，子集C和子集D分別是條件屬性集與決策屬性集，V=∪a∈RVa是屬性值的集合，Va表示屬性a的值域，f: U×A→V是指定U中對象的屬性值的函數(shù)。

數(shù)據(jù)量的不斷增大使得許多現(xiàn)有的數(shù)據(jù)分析方法受到限制，在實際應用中表現(xiàn)為計算復雜度上升，而規(guī)則質(zhì)量和分類精度降低。決策表數(shù)據(jù)分析中的主要困難之一來自于屬性數(shù)量的增長，隨著屬性集的不斷擴大，為了建立有效的分類模型，訓練集中所需的對象數(shù)呈指數(shù)級增長，歸納算法的搜索空間也隨之擴大，增大了在決策表中進行盲目的知識發(fā)現(xiàn)、得到無用分類規(guī)則的可能性。另外，根據(jù)最短描述長度原理(minimum description length principle，MDLP)[1]，分類規(guī)則前件中屬性過多將影響規(guī)則質(zhì)量，不利于新對象的分類，而屬性較少的分類模型更易于理解，適合于用戶驅(qū)動的數(shù)據(jù)挖掘過程。針對決策表的復雜性，首先考慮對屬性集的處理，力求減小屬性集的規(guī)模。

目前，對多屬性決策表大多采用屬性約簡方法[2]，在保持分類決策不變的前提下刪除決策表中的冗余屬性，從而減小屬性集的規(guī)模，其中一些算法取得了較好的效果。但屬性約簡技術(shù)仍存在以下弊端：某些決策表中必要的條件屬性很多，經(jīng)過約簡后的屬性集可能仍然龐大；約簡算法的結(jié)果依賴于訓練集中對象的數(shù)量，若對象較少，約簡的質(zhì)量將受到影響；另外，某些約簡算法對于大型決策表效率較低，計算復雜度高。

針對決策表屬性集的復雜性和屬性約簡等技術(shù)存在的問題，對決策表進行屬性集分解是一種較好的處理方法[3]。其基本思想是將決策表的條件屬性集分解為若干子集，它們分別與決策屬性構(gòu)成一個決策子表，所有條件屬性子集構(gòu)成原條件屬性集的一個覆蓋。對于決策表T=(U，C∪g0gggggg，V，f)，T的一次屬性集分解將產(chǎn)生N個子表的集合，每個子表表示為Ti=(U，Ci∪g0gggggg，V， f)，i∈{1，…，N}。其中：CiC，且∪i∈{1，…，N}Ci=C。

分解完成后，對原決策表的分析處理，轉(zhuǎn)換為在各子表上分別進行局部規(guī)則歸納和推導，然后將它們綜合起來的過程。對于不同的決策子表，可以使用相同的歸納學習方法，也可以使用不同的方法，分別得到各子表對應的子規(guī)則庫，子規(guī)則庫在學習或分類過程中融合，為新對象的分類提供支持。

決策表的屬性集分解減少了每次處理的數(shù)據(jù)量，使得適合普通決策表的算法也能適用于復雜的大型決策表，各子表之間可以進行并行計算，減小時間復雜度，提高數(shù)據(jù)分析的效率。通過分解還能增強數(shù)據(jù)挖掘過程的可理解性和透明度，發(fā)現(xiàn)屬性之間隱含的關(guān)系，采用小樣本數(shù)據(jù)建模的方式提高規(guī)則質(zhì)量和分類精度。

在基于決策表屬性集分解的學習和分類過程中，數(shù)據(jù)分析的效率和質(zhì)量與分解方法密切相關(guān)。目前出現(xiàn)的一些屬性集分解方法，如文獻[4]提出的根據(jù)屬性類型的分解方法、文獻[5]提出的基于函數(shù)分解的方法、文獻[6]提出的屬性集分解及貝葉斯合成方法等，在原理和特性上存在差異，在實際應用中須根據(jù)給定問題的具體情況和數(shù)據(jù)本身的特點，選擇合適的分解方法提高計算效率和分類質(zhì)量。



2分解的決策等價性判斷

對大型決策表進行分解的目的是在規(guī)模相對較小的子決策表中建立模型獲取知識，通過局部的規(guī)則推導降低數(shù)據(jù)分析過程的復雜度。當對新對象進行分類時，綜合局部知識得到?jīng)Q策結(jié)果，其中的關(guān)鍵是各子表得到的規(guī)則庫能相互協(xié)作[7]，即綜合不同的子規(guī)則庫對同一對象進行分類時，得到的決策結(jié)果不會與原決策值產(chǎn)生矛盾。

分解的決策等價性是指通過原決策表歸納所得的決策結(jié)果與分解后綜合各子表局部規(guī)則得到的決策結(jié)果相同。屬性集分解過程中，由于子決策表屬性個數(shù)減少，僅由部分條件屬性推導的規(guī)則可能出現(xiàn)泛化，增大了分類決策的不確定性。決策表的屬性集分解方法應保證分解前后的決策等價和信息無損，避免決策表分解對分類結(jié)果帶來的不確定性。

3強等價判斷標準

分解的弱等價條件僅保證了決策表論域中所有對象分解前后的決策等價性，而上述強等價條件在決策表樣本集的取值空間下進行判斷，不僅保證了原決策表中所有對象分解前后決策等價，而且考慮了不包含于原決策表中，但是能夠由決策子表局部分類的對象，更加嚴格地限定了分解過程中決策等價性的條件。強等價條件比弱等價條件更為全面、完備，進一步避免了使用子表決策帶來的不確定性。

4結(jié)束語

屬性集的分解是處理大型決策表復雜特性，提高數(shù)據(jù)分析效率和質(zhì)量的有效手段，分解前后決策的等價性是影響決策表分解質(zhì)量的關(guān)鍵因素，在分解過程中要力求保證決策等價。通過定義局部決策函數(shù)，提出了基于決策表論域的弱等價條件和部分等價條件，針對弱等價性判斷標準的局限性，進一步提出了決策表樣本集取值空間上的強等價條件，從更加嚴格的層次保證了分解過程中的決策等價性。通過決策等價條件對決策表屬性集分解進行考察，可判斷分解前后決策分類是否一致，減小子表決策存在的不確定性，避免分解帶來的信息損失和分類結(jié)果的矛盾。

參考文獻：

［1］ZUPAN B，BOHANEC M，DEMSAR J，et al.Learning by discovering concept hierarchies[J].Artificial Intelligence，1999，109(12):211－242.

[2]STARZYK J，NELSON D E，STURTZ K.Reduct generation in information systems[J].Bulletin of International Rough Set Society，1998，3:19－22.

[3]ROKACH L，MAIMON O.Theory and applications of attribute decomposition[C]//Proc of the 2001 IEEE International Conference on Data Mining.Washington:[s.n.]，2001:473－480.

[4]KUSIAK A.Decomposition in data mining: an industrial case study[J].IEEE Transactions on Electronics Packaging Manufactu￣ring，2000，23(4):345－353.

[5]ZUPAN B，BOHANEC M，BRATKO I，et al.A dataset decomposition approach to data mining and machine discovery[C]//Proc of the 3rd International Conference on Knowledge Discovery and Data Mining. Irvine:[s.n.]，1997:299－303.

[6]MAIMON O，ROKACH L.Improving supervised learning by feature decomposition[C]//Proc of the 2nd International Symposium on Foundations of Information and Knowledge Systems. Salzau Castle:[s.n.]，2002:178196.

[7]KUSIAK A.Decomposition in data mining: a medical case study[C]//Proc of the SPIE Conference on Data Mining and Knowledge Discovery. Orlando:[s.n.]， 2001:267－277.

[8]WALCZAK B，MASSART D L.Rough sets theory[J].Chemometrics and Intelligent Laboratory System，1999，47(1):116.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”