劉軍

(南京工業(yè)大學(xué)電子與信息工程學(xué)院，江蘇南京 210009)

當前，決策表建樹算法大多是針對相容表的，為解決決策表的屬性數(shù)量有限等不確定性問題，學(xué)者引入了非相容表。非相容表決策樹構(gòu)建算法需要解決2個主要問題，即如何將非相容表等價為相容表和如何對這類等價表構(gòu)建決策樹。在非相容表等價為相容表方面，秦川等［1］對相容表的Skowron可辨識矩陣的定義進行改進，使其對非相容表也能進行屬性約簡;葉東毅［2］用粗糙集的P近似精度γp(U，D)進行判別。上述學(xué)者的思路皆以屬性性質(zhì)判別相容關(guān)系為前提，這種全表的列向(屬性)約簡算法不僅要判定相容性，而且需要進行屬性約簡，因此運算量比較大。為此，筆者采用行向(記錄)的邏輯關(guān)系判定相容關(guān)系，并將非相容行經(jīng)過變量替代后等價于相容行，最終得到等價相容表。在如何構(gòu)建決策樹方面，基于信息熵的決策樹算法往往存在子樹重復(fù)的情況，降低了判定樹的使用效果［3］。近年來基于粗糙集的決策樹構(gòu)建是研究的熱點［3-4］，屬性約簡是粗糙集理論的核心［4］。由于屬性約簡的結(jié)果直接影響決策樹構(gòu)建的質(zhì)量，所以往往希望求得最小約簡集，然而要計算出最小約簡集是一個NP難題［5］。目前常用的屬性約簡算法是基于分辨矩陣的方法［6］和基于正區(qū)域的方法［7］，其中心思想都是利用粗糙集的屬性約簡技術(shù)來預(yù)先去除與構(gòu)建決策樹無關(guān)的屬性(屬性約簡)［8］，但這些方法的屬性約簡計算復(fù)雜度高，為解決此問題，筆者擬采用不進行屬性約簡而直接構(gòu)建決策樹的方式，即以粗糙集分辨關(guān)系［9］和粒計算［10］為理論基礎(chǔ)，給出一種針對非相容或相容表構(gòu)建決策樹的通用算法。該算法僅以條件屬性集A中單一屬性Ai對決策屬性集D的分辨關(guān)系為前提，將分辨能力較強、擊中數(shù)量最大且可盡快分出葉結(jié)點的屬性作為劃分屬性，以此遞進劃分逐級完成決策樹的構(gòu)建，將相同行的數(shù)量(擊中數(shù)量)作為屬性優(yōu)選的一個重要參數(shù)，這樣能保證生成的決策樹上層多為擊中量大的葉結(jié)點且可盡量減少樹的結(jié)點深度。本算法具有以下特點:

a.運用多值邏輯關(guān)系式證明單一條件下得出多種不同結(jié)論的不相容問題，可以將多結(jié)論以一個邏輯變量替代，將其等價為單一條件單一結(jié)論的相容問題進行處理。

b.針對替代性相容表的類型多變問題，提出一種基于粗糙集分辨關(guān)系的決策樹生成算法。該算法不以常規(guī)的屬性約簡求核屬性方法為出發(fā)點，而是以單一屬性Ai對D的分辨關(guān)系為前提確定優(yōu)選屬性:Ai按其取值劃分為若干部分(屬性粒)，并將屬性粒作為一個局部參數(shù);該屬性粒對應(yīng)于D的決策屬性粒數(shù)量(類別數(shù)量)作為一個全局參數(shù);將表中相同行的數(shù)量作為屬性粒的輔助參數(shù)，由這3個參數(shù)確定該屬性粒的優(yōu)劣。Ai中各屬性粒的累加和即為Ai的優(yōu)劣度，最優(yōu)者即為劃分屬性。

c.從實際出發(fā)，將決策表中相同行(包括邏輯變量替代后的相同行)作為一類輔助參數(shù)參與屬性粒的擇優(yōu)。相同行越多表示這類情況出現(xiàn)的概率越大，則應(yīng)該增加該行的權(quán)重。

1 決策樹構(gòu)建理論和算法

1.1 理論

設(shè)S=(U，A，D，V，F(xiàn))［9］是一決策表，其中，U={x1，x2，…，xn}是論域，A為條件屬性集，D為決策屬性集，V為屬性值集合，F(xiàn)是U×(A∪D)→V的映射。根據(jù)Lukasiewicz的多值邏輯定義［11］，S是多值邏輯的真值表，S中的每一行都是多值邏輯的一個最小項，由最小項的相容與不相容關(guān)系可以確定如何將不相容關(guān)系替代為相容關(guān)系。

定理1 設(shè)多值邏輯不相容最小項mi=p，mj=q和mk=r。最小項mi，mj可相容的充要條件是mk=r (其中i，j和k是最小項下標，p，q和r為邏輯函數(shù)值，mi=mj=mk，p≠q，r=p+q)。

證明 由mi∨mj=p∨q(因mi=mj=mk，p≠q)→mk=p∨q。

由獨立命題邏輯運算［12］得概率公式:

因p和q是獨立事件，且r=p+q，因此r也是一個獨立事件，則

式mk=r成立，得證。

定理1說明任何不相容的決策表，將其不相容的多個最小項經(jīng)獨立替代后可以轉(zhuǎn)換為一個獨立最小項，使原決策表相容，從而使不相容表構(gòu)建決策樹轉(zhuǎn)換為相容表構(gòu)建決策樹。構(gòu)建決策樹完成后將先前替代的獨立事件r(葉結(jié)點)逆替代為p和q(葉結(jié)點)即可。

當前，決策樹構(gòu)建方法首先需要對S進行屬性約簡［13］。由于S的情況各異(尤其是經(jīng)替代后的S)，往往會出現(xiàn)從極端緊密(每個屬性都是核屬性)至極端松散(有多個核集)的各種情況。極端緊密不需要屬性約簡，而極端松散則會出現(xiàn)多個可選擇的屬性約簡集，其他情況介于二者之間，所以需要一種可處理各類S的統(tǒng)一算法。

定義1［10］在S中，令A(yù)i∈A，v∈V，(Ai，v)或Aiv為S上的原子公式，m(Aiv)表示U上所有滿足f(Ai)=v的個體集合，其中m(*)為意義函數(shù)符，則稱二元對(Ai，m(Aiv))為S上的基本粒。

根據(jù)定義1，基本粒(Ai，m(Aiv))主體是原子公式(Ai，v)，即(Ai，v)表示屬性Ai取值為v時u∈U的行集，所以在本文中(Ai，v)稱為S的屬性粒，而(D，di)稱為S的決策屬性粒，其中di∈D。屬性粒是屬性的最小可劃分單位，以其作為分辨關(guān)系的基本單位可以準確地確定屬性的分辨強度。

定義2 設(shè)屬性Ai∈A，v∈Ai。Ai的屬性同值量定義為是屬性Ai取值為v時所對應(yīng)S的行數(shù)，YAiv是獨立參數(shù)。

定義3 將S的完全相同行只用一行表示，同時新增一列屬性n記錄該相同行的個數(shù)，稱n為屬性同值量系數(shù)。

在設(shè)有n的S中，YAiv和n配合使用，即(Ai，v)所涉及n之累加和記為NAiv。對S中未設(shè)n列的情況，則默認n=1。

例如:實例分析中表3中未設(shè)n列，屬性a中有2種取值1和2，其對應(yīng)Yav分別是:Ya1=6;Ya2=15;表1中設(shè)有n列，屬性e中有2種取值0和1，其對應(yīng)Nev分別是:Ne0=10+30=40;Ne1=10+40+90+60=200。

例如:表1中，屬性e的2種取值0和1，其對應(yīng)XAiv分別是

1.2 算法

每個屬性Ai由若干(Ai，v)組成，所以可以先確定Ai中每個(Ai，v)的分辨能力，Ai中各(Ai，v)分辨能力的累加和即為Ai的分辨能力。求出A中每個Ai的分辨能力后，再從中選出分辨能力最強者作為劃分屬性，以此由上而下構(gòu)建決策樹。

決定(Ai，v)分辨能力的關(guān)鍵參數(shù)是NAiv和XAiv。從1.1節(jié)分析可知，(Ai，v)的NAiv值越大且XAiv值越小，則其分辨能力越強。所以依據(jù)NAiv和XAiv可以推導(dǎo)出判別(Ai，v)分辨能力強弱的一般式:若XAiv=1，則經(jīng)1次結(jié)點劃分，NAiv即可分辨出di∈D中的NAiv行，即NAiv/XAiv=NAiv/1，得1個葉結(jié)點;若XAiv=2，1次結(jié)點劃分后，要在之后的2個分區(qū)內(nèi)完成對di∈D的分辨，至少要經(jīng)2次結(jié)點劃分，NAiv才可2次分辨完di∈D的NAiv行，即NAiv/XAiv=NAiv/2，得2個葉結(jié)點;若XAiv=3，1次結(jié)點劃分后，要在之后的3個分區(qū)內(nèi)對di∈D進行分辨，至少需要經(jīng)過3次結(jié)點劃分，NAiv才可3次分辨出di∈D的NAiv行，即NAiv/XAiv=NAiv/3，得3個葉結(jié)點……依此類推，可以得到(Ai，v)對di∈D的分辨度的一般式:UAiv=NAiv/XAiv，屬性Ai對D的分辨度算式:

而UAi(i=1，2，…，n)中最大者為劃分屬性:M=max(UAi)(i=1，2，…，n)。

在當前表S中，用M進行劃分生成1個枝結(jié)點且得若干子表，再對各子表求其各自的M，直到當前子表中M中只有1種di∈D值，則生成1個葉結(jié)點，這是一個逐級擇優(yōu)劃分的遞歸算法:

2 實例分析與比較

2.1 實例分析

文獻［14］中表1是一個非相容決策表，將非相容行中的D=1∨0用2替代，同時增加表示表中相同行數(shù)量的列n，見表1。

首層劃分屬性M的選擇:

表1 非相容表替代后的決策數(shù)據(jù)Table 1 Decision data after substitution in incompatible table

同理，Ub≈107，Uc=80，Ud≈113，Ue≈107，Uf=120。

由M=max(UAi)→Uf=120 (Ai=a，b，c，d，e，f)。

經(jīng)M劃分后，在f=0(U=Z1，Z2，Z3)的子表中:Ua=10/1+50/1=60，Ub=50，Uc=30，Ud=60，Ue=35，Ua和Ud都是M(等價)?？扇芜x一個再次劃分后得到葉結(jié)點。在f=1(U=Z4，Z56，Z78)的子表中:Ua=120/2 +60/1=120，Ub=90，Uc=90，Ud=90，Ue=180。Ue是M，選其劃分后得葉結(jié)點。決策樹(以磁盤管理格式)表示如下:

當(f=1)∧(e=1)時，D=0有47%可能;而D=1有53%可能。這很好地解決了非相容表構(gòu)建決策樹的一個難題。從屬性約簡角度，屬性重要程度的順序為f，e，a或d。對照文獻［14］基于正域約簡集{a，e，f}，{b，e，f}及{d，e，f}和基于分布約簡集{a，e，f}可以看出，算法的屬性擇優(yōu)是準確的。

文獻［15］表1中U=4與U=8等價，U=1與U=5，11，20等價，U=2與U=15等價，而U=12與U= 3，6，14，19非相容，將D=1∨0用2替代，同時增加表示表中相同行數(shù)量的列n，得表2。

首層劃分屬性M的選擇:

表2 替代后的決策數(shù)據(jù)Table 2 Decision data after substitution

同理，Uc2=12.0，Uc3=10.0，Uc4= 8.0，Uc5≈7.7。

由M=max(UAi)→Uc2=12.0 (Ai= c1，c2，c3，c4，c5)。

經(jīng)M劃分，在c2=0(U=u1，u4，u10，u13)子表中直接得c2=0→D=0;在c2=1(U=u2，u7，u9，u12，u16，u17， u18)子表中得c4=1→D=1，對c4=0繼續(xù)劃分后最終得決策樹:

屬性的重要程度順序是c2(Uc2=10.0)，c3(Uc3≈8.3)，c1(Uc1=12.0)，c4(Uc4=8.0)和c5(Uc5≈7.7)。而文獻［15］所述的順序為c1(Uc1=0.1)，c3(Uc3=0.05)，c4(Uc4=0.05)，c2(Uc2=0)和c5(Uc5=0)，若按文獻［15］的結(jié)果應(yīng)首選c1作為M，則得4層樹(圖略):第1層1結(jié)點0樹葉、第2層2結(jié)點3樹葉、第3層1結(jié)點1樹葉、第4層1結(jié)點2樹葉。文獻［15］的結(jié)果與本例樹相比較差(其樹葉多在下層)。由此可知，屬性約簡是側(cè)重哪個屬性最不可少(判定核屬性)，而本文所構(gòu)建決策樹算法則側(cè)重哪個屬性最能盡快生成樹葉且逐漸包括各核屬性。

2.2 結(jié)果比較

在解決了決策表非相容問題的前提下，可以直接對各類相容表構(gòu)建決策樹，因算法采用單屬性與決策屬性的邏輯關(guān)系進行決策樹構(gòu)建，所以算法簡潔、有效。文獻［16］中表1經(jīng)屬性(值)替代后如表3所示。

表3 屬性(值)替代后的汽車數(shù)據(jù)Table 3 Car data after substitution

首層劃分屬性M的選擇:

同理，Ub=7，Uc≈10.3，Ud=7，Ue≈8.7，Uf≈8.8，Ug≈7.7，Uh≈7.8，Ui=13。

M=max(UAi)→Ui=13(Ai=a，b，c，d，e，f，g，h，i)。

經(jīng)M劃分后，本層得2個樹葉，而在i=2的子表中繼續(xù)劃分后最終得決策樹:

與文獻［16］中圖1相比，同樣是4層樹，本算法至第2層已分辨出13行，而文獻［16］中圖1只分辨出9行。

若按文獻［16］改進算法將表1視為只有一個屬性i(質(zhì)量)和一個決策屬性s(里程)的非相容表進行構(gòu)建決策樹，按1.2節(jié)算法可得決策樹:

與文獻［16］中圖4相比，同樣是1層樹，但其判定準確性(每項都有準確判定)高于文獻［16］中的圖4 (以λ=0.72，即全部判定可信度只有0.72的概率)。

對文獻［17］中表2，首層劃分屬性M的選擇:

同理，Ua2=14，Ua3≈12.3，Ua4=14。

由M=max(UAi)→Ua2=14(Ai=a1，a2，a3，a4)。

經(jīng)M=a2劃分后最終得決策樹:

與文獻［17］中圖2相比，同樣是3層樹且最底層均為4葉結(jié)點，但本算法首層分辨出6行，而文獻［17］的圖2只分辨出4行。

3 結(jié) 論

a.從理論上證明非相容最小項集可經(jīng)邏輯代換為等價的可相容最小項集，使非相容表轉(zhuǎn)換為相容表。

b.針對相容表的特點，提出了一種基于屬性粒分辨關(guān)系的構(gòu)建決策樹算法。針對各類決策表，以條件屬性集A中各屬性粒對D的分辨關(guān)系為基礎(chǔ)，不需屬性約簡直接確定劃分屬性M。

c.所提算法簡潔易理解，時間和空間復(fù)雜度較小。

d.所提算法采用一級判定法確定M。由于決策樹的多解性，若一級判定仍有多個等價的M時，可采用多級判定法確定M。

［1］秦川，陳海軍，施化吉，等.不相容決策表的屬性約簡算法［J］.計算機工程與應(yīng)用，2008，44(24):162-164.(QIN Chuan，CHEN Haijun，SHI Huaji，et al.Attribute reduction algorithm for inconsistent decision tables［J］.Computer Engineering and Applications，2008，44(24):162-164.(in Chinese))

［2］葉東毅.不相容決策表分解的若干性質(zhì)［J］.小型微型計算機系統(tǒng)，2006，27(4):695-697.(YE Dongyi.Some properties of decomposition of inconsistent decision tables［J］.Journal of Chinese Computer Systems，2006，27(4):695-697.(in Chinese))

［3］HUANG Longjun，ZHOU Caiying.A new method for constructing decision tree based on rough set theory［C］//Proceeding of International Conference on Granular Computing.Washington:IEEE，2007:241-244.

［4］BAI J S，F(xiàn)AN B，XUE J Y.Knowledge representation and acquisition approach based on decision tree［C］//2003 IEEE International Conference on Natural Language Processing and Knowledge Engineering.Washington:IEEE，2003:533-538.

［5］王國胤，于洪，楊大春.基于條件信息熵的決策表約簡［J］.計算機學(xué)報，2002，25(7):759-766.(WANG Guoyin，YU Hong，YANG Dachun.Decision table reduction based on conditional information entropy［J］.Chinese Journal of Computers，2002，25 (7):759-766.(in Chinese))

［6］WANG Xiangyang，YANG Jie，JENSEN Richard，et al.Feature selection based on rough sets and particle swarm optimization［J］. Pattern Recognition Letters，2007，28(4):459-471.

［7］JENSEN R，SHEN Q.Finding rough set reducts with ant colony optimization［C］//Proceedings of the 2003 UK Workshop on Computational Intelligence.Berlin:Springer，2003:15-22.

［8］WANG GuoYin，ZHAO Jun，AN Jiujiang，et al.Theoretical study on attribute reduction of rough set theory:in algebra view and information view［C］//Third International Conference on Cognitive Informatics.Washington:IEEE，2004:148-155.

［9］李永華，蔣蕓，王小菊.一種基于rough集的屬性約簡的改進算法［J］.計算機應(yīng)用，2008，28(8):200-202.(LI Yonghua，JIANG Yun，WANG Xiaoju.An improved algorithm for attribute reduction based on rough sets［J］.Journal of Computer Applications，2008，28(8):200-202.(in Chinese))

［10］徐久成，史進玲，成萬里.粒計算中決策規(guī)則的提?。跩］.計算機工程與應(yīng)用，2009，45(25):132-134.(XU Jiucheng，SHI Jinling，CHENG Wanli.Algorithm for decision rules extraction based on granular computing［J］.Computer Engineering and Applications，2009，45(25):132-134.(in Chinese))

［11］劉全，伏玉琛，孫吉貴，等.一種基于集合符號的自動推理擴展方法［J］.計算機研究與發(fā)展，2007，44(8):1317-1323. (LIU Quan，F(xiàn)U Yuchen，SUN Jigui，et al.An automated reasoning expanded method based on set signs［J］.Journal of Computer Research and Development，2007，44(8):1317-1323.(in Chinese))

［12］劉宏嵐，高慶獅，楊炳儒.多值邏輯中的命題相關(guān)性與邏輯運算研究［J］.北京科技大學(xué)學(xué)報，2007，12(增刊2):177-182. (LIU Honglan，GAO Qingshi，YANG Bingru.Proposition relativity and logic calculation in many-valued logic［J］.Journal of University of Science and Technology Bering，2007，12(Sup2):177-182.(in Chinese))

［13］王名揚，胡清華，于達仁.基于粗糙集約簡的決策林構(gòu)建方法［J］.計算機工程，2009，35(15):193-197.(WANG Mingyang，HU Qinghua，YU Daren.Construction method of decision forests based on rough set reduction［J］.Computer Engineering，2009，35(15):193-197.(in Chinese))

［14］朱承學(xué)，陳志剛.不相容信息系統(tǒng)的屬性約簡研究［J］.中南林業(yè)科技大學(xué)學(xué)報，2010，30(6):189-192.(ZHU Chengxue，CHEN Zhigang.Research of attributes reduction in inconsistent system［J］.Journal of Central South University of Forestry＆Technology，2010，30(6):189-192.(in Chinese))

［15］王靜，葉茂，劉啟和，等.布爾決策表的屬性約簡新方法:應(yīng)用于欺詐識別［J］.計算機工程與應(yīng)用，2011，47(12):126-129. (WANG Jing，YE Mao，LIU Qihe，et al.New attribute reduction algorithm of Boolean decision table:application on fraud detection［J］.Computer Engineering and Applications，2011，47(12):126-129.(in Chinese))

［16］高靜，徐章艷，宋威，等.一種新的基于粗糙集模型的決策樹算法算機工程［J］.計算機工程，2008，34(3):9-11.(GAO Jing，XU Zhangyan，SONG Wei，et al.New decision tree algorithm based on rough set model［J］.Computer Engineering，2008，34 (3):9-11.(in Chinese))

［17］周軍，林慶.基于粒度商的決策樹構(gòu)造算法［J］.計算機工程與設(shè)計，2009，30(16):3826-3829.(ZHOU Jun，LIN Qing. Quotient GD based algorithm for design decision tree［J］.Computer Engineering and Design，2009，30(16):3826-3829.(in Chinese))