(泉州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院信息系，福建 泉州 362000)

·計算機軟件理論、技術(shù)與應(yīng)用·

基于決策類劃分的新型多變量決策樹算法

黃俊南

(泉州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院信息系，福建 泉州 362000)

基于不可分辨關(guān)系、復(fù)合運算、集合運算和邏輯運算等集合論概念，構(gòu)造一種新型的多變量決策樹算法。該算法包括5個步驟：依據(jù)決策屬性值劃分出決策類；利用決策類之間條件屬性集相交判斷二義性條件屬性值；利用決策類各條件屬性值域的不同判斷獨立決策條件屬性值；利用決策類自身條件屬性集進行復(fù)合運算，獲得多變量決策方法；使用或運算符(∨)連接各個部分的決策規(guī)則以取得完整的決策規(guī)則。以決策樹典型訓(xùn)練集(氣象信息系統(tǒng))為例進行驗證，其結(jié)果表明，該算法行之有效。通過時間復(fù)雜度的分析結(jié)果表明，該算法較之粗糙集算法更優(yōu)，而且不亞于ID3算法。

單變量決策樹；多變量決策樹；決策表；集合運算；邏輯運算

決策樹是用于模擬人們對于某種決策而進行的一系列判斷過程的樹形圖。其分類方式近年來被廣泛作為商業(yè)領(lǐng)域、科學(xué)研究等相關(guān)決策問題的解決方案。

決策樹的構(gòu)造算法有很多種運算方式，典型代表是Quinlan提出來的ID3算法[1]。此后他又提出了ID3的優(yōu)化算法即C4.5算法[2]。此類算法是基于單變量構(gòu)造的決策樹(只檢驗單個屬性)，這一限制使得對很多復(fù)雜概念的表達變得困難或無法表達[3]；因此，人們提出了多變量歸納學(xué)習(xí)系統(tǒng)。粗糙集多變量算法是將粗糙集中的相對核作為初試測試屬性集合，采用粗糙集中的知識代替ID3的信息熵作為選擇擴展屬性的度量，在一些情況下，它能獲得比ID3算法更簡潔的決策樹[4]。其典型代表有苗奪謙等[3]提出的基于粗糙集的多變量決策樹的構(gòu)造方法、吳強等[5]提出的基于非線性擬合方程的多變量決策樹算法等。本文采用一個新的視角進行多變量決策樹的構(gòu)造，其主要目的是降低決策樹構(gòu)造過程的數(shù)據(jù)運算量及其復(fù)雜度，并提出較為易懂的運算過程。

1 主流決策樹算法建樹及簡化的邏輯規(guī)則

目前，主流的決策樹算法的代表是單變量算法ID3和多變量粗糙集算法[6-16]。本文利用表1的數(shù)據(jù)集[1]作為訓(xùn)練集。

表1 一個關(guān)于氣象信息系統(tǒng)表(訓(xùn)練集)

對表1數(shù)據(jù)分別根據(jù)ID3算法和粗糙集多變量粗糙集算法進行遞歸建樹，得到的決策樹如圖1(a)和(b)所示。

對圖1的2種構(gòu)建過程使用“if-then”規(guī)則進行分類記錄并簡化，均可得如下邏輯規(guī)則：

If (outlook=”sunny” and humidity=”high”)or (outlook=”rain” and windy=”true”)

Then class=”N”; --class為N的邏輯規(guī)則

If (outlook=”sunny” and humidity=”normal”)or (outlook=”rain” and windy=”false”)or outlook=”overcast”

Then class=”P”;--class為Y的邏輯規(guī)則

(a) ID3單變量決策樹

(b)粗糙集多變量決策樹

2 決策類劃分的多變量決策樹算法構(gòu)造過程

2.1決策表定義

一個決策表可以形式化定義[6]為：S=，其中U={u1,u2,…,un}是所感興趣對象的有限集合，C∪D是屬性的有限集，C為條件屬性集，D為決策屬性集，并且C∩D=?，V為屬性集C∪D的值域，f:U×(C∪D)→V為一個信息函數(shù)，表示任一對象的屬性在V上的取值，即f(x,r)∈Vr，它指定了U中每個對象x的屬性值。決策表S=中的依賴關(guān)系C→kD決定了一套if…then…形式的規(guī)則集。從邏輯觀點出發(fā)，決策規(guī)則將形如a=v(a為屬性名，v為屬性值)的基本公式是利用連接詞語“與” “或”和“蘊含”連接起來所建立的蘊含式。蘊含式前件表示條件，后件表示決策[7]。

2.2新型決策樹算法描述

算法首先依據(jù)決策屬性值劃分出各自獨立的決策類，利用決策類之間條件屬性集相交判斷并排除掉二義性，然后利用決策類各條件屬性值域的不同判斷并排除獨立決策條件屬性值，接著利用復(fù)合運算對自身條件屬性集進行運算獲得多變量決策規(guī)則，最后使用或運算符對運算后的單獨決策規(guī)則和多變量決策規(guī)則進行連接以獲取完整的決策規(guī)則。其相關(guān)算法描述如下：針對決策表形式化定義S=，其中C是條件屬性集，D是決策屬性集。假設(shè)C={c1,c2,…,cn}，c1～cn表示各條件屬性。算法包含5個步驟。

步驟1:根據(jù)決策屬性劃分論域。使用不可分辨關(guān)系[7]對決策表U進行決策類劃分，令集合Vd表示決策屬性d的值域，設(shè)Vd={d(1),d(2),…,d(p)}表示決策值，值域個數(shù)為p，則決策屬性d將論域U劃分成{Ud(1),Ud(2),…,Ud(p)}。

步驟2:排除二義性[8]條件屬性。如果一個文法存在某個句子對應(yīng)2棵不同的語法樹，則說明這個文法是二義的。二義性條件屬性體現(xiàn)為相同的條件屬性值能推導(dǎo)出不同的決策屬性值，當(dāng)決策類存在這種條件屬性，決策分析將無法準確推導(dǎo)。對全部決策類分析并排除。

1)判斷。假設(shè)存在2個決策類Ud(x1),Ud(x2)?U，其中1≤x1,x2≤p，且x1≠x2，這2個決策類的條件屬性集分別是Cd(x1),Cd(x2)?C。設(shè)2個屬性集相交后集合為Cd(x12)=Cd(x1)∩Cd(x2)，當(dāng)Cd(x12)≠?，則說明這2個決策類存在二義性條件屬性值，使得Cd(x12)→Dd(x1)和Cd(x12)→Dd(x2)成立，且Dd(x1)≠Dd(x2)。

步驟3:分析并取得獨立決策條件屬性。當(dāng)決策類中某些條件屬性值不屬于其他決策類時，則稱此類屬性值為獨立決策條件屬性值(簡稱獨值)，可直接引作決策規(guī)則。

1)判斷獨值。重設(shè)Ud(j)為排除二義性條件屬性值后的決策類。用ci(d(j))表示c1(d(j))～cn(d(j))條件屬性，1≤i≤n。設(shè)決策類Ud(j)的條件屬性ci對對象u存在值f(u,ci)=z，且該值不屬于任何其他決策類，則稱z為Ud(j)在條件屬性ci上的獨立決策條件屬性值。用Vci(d(j))表示決策類Ud(j)條件屬性ci的值域，Vci表示論域U條件屬性ci的值域，則獨立決策條件屬性值滿足：

如果ci={z:z∈Vci(d(j),z?(Vci-Vci(d(j)))}，則f:Ud(j)×{ci:ci=z}∪Dd(j)→Vd(j)成立。——①

2)判斷獨值集。當(dāng)決策類Ud(j)條件屬性ci存在多個獨值時，用集合Zi(d(j))={z1,z2,…,zq}表示，其中z1～zq表示條件屬性ci的各個獨立條件決策屬性值，設(shè)為zk∈Vci(d(j))，1≤k≤q；因此，公式①可轉(zhuǎn)變?yōu)楣舰冢?/p>

如果Zi(d(j))={z1,z2,…,zq}，且ci={zk:zk∈Zi(d(j)),Zi(d(j)?Vci(d(j)),Zi(d(j))?(Vci-Vci(d(j)))}，則f:Ud(j)×{ci:ci=zk}∪Dd(j)→Vd(j)?！?/p>

步驟4:復(fù)合運算構(gòu)建的新型多變量決策樹算法。完成前3步后的決策類Cd(j)x信息表為Sd(j)=，Ud(j)={u1(d(j)),u2(d(j)),…,un(d(j))}，Cd(j)={c1(d(j)),c2(d(j)),…,cn(d(j))}，|VDd(j)|=1，各分區(qū)決策類決策屬性值唯一，且信息函數(shù)f:Ud(j)×(Cd(j)∪Dd(j))→VDd(j)成立。如論域包含對象m個，Ud(j)對應(yīng)決策表如表2所示。

表2 決策表——論域Ud(j)

1)對象分量相交。取表2條件屬性集Cd(j)，并用a11～amn表示1～m行(對象)在1～n列(條件屬性)的值，下面分別用x和y表示行和列下標。條件屬性集為

設(shè)tx∈Cd(j)，tx表示第x個對象的條件屬性集，tx[ci]則表示對象tx在屬性ci的一個分量，ci(d(j))={a1i,a2i,…,ami}，1≤i≤n。

2)刪除無效對象。對集合Cd(j)x中的每個對象所包含的屬性值進行計數(shù)，當(dāng)計數(shù)值小于等于1時，說明該對象的條件屬性集無法進行有效決策，從集合Cd(j)x中刪除此類對象。

3)判斷最優(yōu)對象近似度。當(dāng)集合Cd(j)x所包含的有效元素個數(shù)越多，則由對象tx條件屬性集所產(chǎn)生多變量決策的可能性越高。構(gòu)建函數(shù)MAX(findnonull(Cd(j)x))用于求取Cd(j)x中有效元素個數(shù)的屬性集。

4)保留最優(yōu)循環(huán)后的多變量決策集合。當(dāng)Cd(j)1～Cd(j)m中存在多個最大有效元素值相同時，保留這些集合并依次對其執(zhí)行步驟4的1)～ 3)，直至每個集合最后只剩下單個對象(每循環(huán)執(zhí)行1次，產(chǎn)生的新集合所包含的對象個數(shù)減1)。

運算結(jié)果可能會保留下多個擁有單個對象的集合，對每個集合執(zhí)行步驟4的5)～ 7)。

對Cd(j)l元素個數(shù)進行計數(shù)，并根據(jù)不同情況進行處理。

(1)|Cd(j)l|≤1。集合中有效的條件屬性值小于等于1時，說明這個集合無法滿足多變量決策要求。回溯到求取當(dāng)前集合的上一集合，回溯后的集合至少包含2條以上的對象條件屬性值有效，且每個對象至少包含2個非空分量。將每個對象的條件屬性值作為最終集合進行約簡，并執(zhí)步驟4的6)。

(2)|Cd(j)l|≥2。集合中有效元素個數(shù)滿足多變量決策要求，并執(zhí)行步驟4的6)。

8)循環(huán)多變量運算。對論域Ud(j)循環(huán)執(zhí)行步驟4的1)～ 7)直至所有對象完成多變量決策運算，每循環(huán)1次至少能獲取1條多變量決策邏輯表達式。

9)推導(dǎo)出完整的邏輯表達式。當(dāng)決策類Ud(j)完成多變量決策運算后可能產(chǎn)生n′個邏輯表達式，分別用condd(j)[1]～condd(j)[n′]表示。設(shè)condd(j)為決策類Ud(j)推導(dǎo)后的完整多變量邏輯表達式，則condd(j)=condd(j)[1]∨condd(j)[2]…∨condd(j)[n′]，且使condd(j)→d=VDd(j)成立。

10)判斷最優(yōu)邏輯表達式。當(dāng)執(zhí)行步驟4的5)時，如存在多個最優(yōu)近似度相同集合，由此可能推導(dǎo)出多個有效邏輯表達式，分別用cond1(d(j))～condm′(d(j))表示。設(shè)condy′(d(j))表示cond1(d(j))～condm′(d(j))中的第y′個邏輯表達式，1≤y′≤m′。設(shè)函數(shù)findv(∨,condy′(d(j)))，用于查找condy′(d(j))中所包含的或運算符(∨)的個數(shù)，當(dāng)該函數(shù)取值越低時，表示condy′(d(j))邏輯表達式的復(fù)雜度越低。保留最小復(fù)雜度的邏輯表達式作為最優(yōu)邏輯表達式。

步驟5:決策表完整的決策規(guī)則。對各分區(qū)決策類完成上述步驟1～4，設(shè)Ud(1)～Ud(p)的獨立決策條件屬性邏輯表達式為indecondd(1)～indecondd(p)。indecondd(j)表示決策類Ud(j)的獨立決策條件屬性邏輯表達式，當(dāng)indecondd(j)=?時，Ud(j)不存在獨立條件屬性決策值。論域U獨立決策條件屬性邏輯表達式為indecond，則indecond=indecondd(1)→Vd(1)∨indecondd(2)→Vd(2)∨…∨indecondd(p)→Vd(p)。

設(shè)Ud(1)～Ud(p)的多變量決策邏輯表達式為condd(1)～condd(p)，論域U的多變量邏輯表達式為cond，則cond=condd(1)→Vd(1)∨condd(2)→Vd(2)∨…∨condd(p)→Vd(p)。

合并2部分決策規(guī)則取得完整的決策：cond∨indecond。

3 基于決策類劃分新型多變量算法實例分析

通過對多個決策樹進行算法實例分析，發(fā)現(xiàn)本算法是有效的，現(xiàn)以決策樹典型訓(xùn)練集——氣象信息系統(tǒng)表(表1)為實例進行證明。各步驟運算情況如下。

步驟1:根據(jù)決策屬性劃分論域。對訓(xùn)練集根據(jù)決策值進行不可分辨關(guān)系劃分。因決策屬性值域VD={N,P}，將論域U根據(jù)決策屬性值劃分為2個等價決策類。U/ID={{1,2,6,8,14},{3,4,5,7,9,10,11,12,13}}，這2個決策類分別用UN和UP表示。

步驟2:二義性條件屬性判斷。CN={a1N,a2N,a3N,a4N}，CP={a1P,a2P,a3P,a4P}。因CN∩CP=?，所以論域U不存在二義性條件屬性。

步驟3：獨立決策條件屬性值的判斷和處理方式。求出CN和CP各條件屬性值域。將CN與CP相對應(yīng)條件屬性值域進行比較，可見Va1P-Va1N={overcast}。說明a1=overcast→D=P為決策類UP的獨立決策條件屬性值。將判斷為a1=overcast的獨立條件屬性值相關(guān)的對象從決策類UP中刪除。

步驟4：獲取多變量邏輯表達式。取UN和UP中的條件屬性集分別進行分量相交。

由UN推導(dǎo)出的多變量邏輯表達式的最后結(jié)果為(a1=0∧a3=0)∨(a1=1∧a4=1)→D=N。

由UP推導(dǎo)出的多變量邏輯表達式的最后結(jié)果為(a1=1∧a4=0)∨(a1=0∧a3=1)→D=P。

步驟5：決策表U完整的邏輯表達式。

綜上所述，將UN和UP取得的多變量決策規(guī)則轉(zhuǎn)換為邏輯表達式，分別為：(outlook=sunny humidity=high) (outlook=rain windy=true)→(class=N)和(outlook=rain windy=false) (outlook = sunny humidity=normal)→(class=P)。

獨立決策邏輯表達式為(a1=overcast)→(D=P)，即(outlook=overcast)→(class=p)。

將上述邏輯表達式組合為完整的決策表達式，可得氣候集的決策表達式為 ((outlook=sunny humidity=high) (outlook= rain windy=true)→(class=N)) (outlook=rain windy=false) (outlook=sunny humidity=normal)→(class=P)) (outlook=overcast)→(class=P)。將其轉(zhuǎn)換為邏輯語句：

If (outlook=”sunny” and humidity=”high”)or (outlook=”rain” and windy=”true”)Then class=”N”;

If (outlook=”sunny” and humidity=”normal”)or (outlook=”rain” and windy=”false”)or outlook=”overcast” then class=”P”;

由此可見，獲得的結(jié)果與ID3和粗糙集多變量運算結(jié)果無二，證明新決策樹構(gòu)建方法成立。

4 算法復(fù)雜度分析與比較

設(shè)訓(xùn)練集中有n行記錄，m個條件屬性，決策值域個數(shù)為p，則ID3算法的信息熵的時間復(fù)雜度為O(n2log2n)。粗糙集的核心步驟是計算等價類，它的時間復(fù)雜度為O(m×n2)[5]。

下面對新算法5個步驟的時間復(fù)雜度進行分析。

步驟1采用不可分辨關(guān)系依據(jù)決策屬性值對訓(xùn)練集進行劃分，其時間復(fù)雜度為O(n)。

步驟2利用決策類之間條件屬性集相交是否為空判斷訓(xùn)練集是否存在二義性數(shù)據(jù)，其時間復(fù)雜度為O(p2)。

步驟3利用決策類之間的各條件屬性值域的不同，判斷是否存在獨立決策條件屬性值，并獲取獨立決策規(guī)則，其時間復(fù)雜度為O(m/p)。

步驟4利用一個復(fù)合運算方式構(gòu)造出一種新型的多變量決策方法，能快速獲取各決策類的多變量邏輯表達式，并依此推導(dǎo)決策規(guī)則，其時間復(fù)雜度為O(m×n2/p)。

步驟5使用或運算符(V)將各個獨立決策規(guī)則和多變量決策規(guī)則進行連接，其時間復(fù)雜度為O(p)。

本算法的核心部分為第4步驟，取其時間復(fù)雜度與ID3算法和粗糙集算法對比。這3種算法對比的關(guān)鍵要素集中在n、m和p這3個參數(shù)。在其中1個參數(shù)變動，另2個參數(shù)保持不變的情況下進行分析，如表3—5所示，取得的實驗分析結(jié)果如圖2—4所示。

表3 僅記錄增長

在條件屬性個數(shù)和決策值域不變而記錄增長的情況下進行分析的結(jié)果如圖2所示?？芍?，當(dāng)記錄數(shù)增長時，3種算法的運算次數(shù)均是增長的，但新算法的增長速度最慢。

圖2 僅記錄增長算法分析圖

表4 僅決策值域個數(shù)增長

實驗次數(shù)m(條件屬性個數(shù))n(記錄數(shù))P(決策值域個數(shù))第1次1010005第2次10100010第3次10100020第4次10100030

在條件屬性和記錄數(shù)不變而決策值域個數(shù)增長的情況下進行分析的結(jié)果如圖3所示?？芍?，當(dāng)決策值域個數(shù)增長時，ID3和粗糙集這2種算法的運算次數(shù)是持衡且相同的(這2種算法的運算次數(shù)彼此覆蓋)，新算法的運算速度卻是降低的。

圖3 僅決策值域個數(shù)增長算法分析圖

表5 僅條件屬性個數(shù)增長

實驗次數(shù)m(條件屬性個數(shù))n(記錄數(shù))P(決策值域個數(shù))第1次51005第2次101005第3次201005第4次301005第5次401005

在記錄數(shù)和決策值域個數(shù)不變而條件屬性個數(shù)增長的情況下的分析結(jié)果如圖4所示?？芍?dāng)條件屬性個數(shù)增長時，ID3運算次數(shù)不變，而粗糙集和新算法的運算次數(shù)是增長的，但新算法的增長幅度遠低于粗糙集。

圖4 僅條件屬性個數(shù)增長算法分析圖

綜上所述：新算法在m、n和p這3個參數(shù)分別增長的情況下，其運算速度均遠遠優(yōu)于粗糙集算法；當(dāng)條件屬性個數(shù)增長且達到一定臨界值時，其運算速度會超過ID3算法。

5 結(jié)論

本文提出了一種新型的多變量決策樹構(gòu)造算法，該算法有5個步驟：1)采用不可分辨關(guān)系依據(jù)決策屬性值對訓(xùn)練集進行劃分，能有效減少后續(xù)算法涉及的數(shù)據(jù)量及其復(fù)雜度；2)利用決策類之間條件屬性集相交是否為空判斷訓(xùn)練集是否存在二義性數(shù)據(jù)；3)利用決策類之間的各條件屬性值域的不同，判斷是否存在獨立決策條件屬性值，并獲取獨立決策規(guī)則；4)利用一個復(fù)合運算方式構(gòu)造出一種新型的多變量決策方法，從而快速獲取各決策類的多變量邏輯表達式，并依此推導(dǎo)決策規(guī)則；5)使用或運算符(∨)將各個獨立決策規(guī)則和多變量決策規(guī)則進行連接，獲取完整的決策規(guī)則。通過模擬證明該算法有效，并在時間復(fù)雜度方面優(yōu)于粗糙集，當(dāng)訓(xùn)練集記錄處于增長狀況時更優(yōu)于ID3算法。

[1]Quinlan J R.Induction of Decision Trees[J].Machine Learning,1986(1):81-106.

[2]Quinlan J R.C4.5:Programs forMachine Learning[M].SanMateo.CA:Morgan Kauffman,1993.

[3]苗奪謙,王玨.基于粗糙集的多變量決策樹構(gòu)造方法[J].軟件學(xué)報,1997,8(6):425-431.

[4]沙惠新,葉東毅.基于知識粗糙集的多變量決策樹的構(gòu)建[J].福州大學(xué)學(xué)報：自然科學(xué)版，2004,32(2):138-141.

[5]吳強,李金龍,楊振宇.基于非線性擬合方程的多變量決策樹算法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報，2006,36(5):546-549.

[6]Pawlak Z W.Rough Sets[J].Internationl Journal of information and Computer Science,1982,11(5):314-356.

[7]安利平.基于粗集理論的多屬性決策分類[M].北京：科學(xué)出版社,2008:15-22.

[8]呂映芝,張素琴,蔣維杜.編譯原理[M].北京：清華大學(xué)出版社,1998:39.

[9]陳建凱,王熙照,高相輝.改進的基于排序熵的有序決策樹算法[J].模式識別與人工智能,2014,27(2):134-140.

[10]王鑫,王熙照,陳建凱.有序決策樹的比較研究[J].計算機科學(xué)與探索,2013,7(11):1018-1025.

[11]許行,梁吉業(yè),王寶麗.基于雙向有序互信息的單調(diào)分類決策樹算法[J].南京大學(xué)學(xué)報：自然科學(xué)版，2013,49(5):628-636.

[12]王萍,張曉丹,張磊.H.264/AVC中基于決策樹的P幀快速模式選擇[J].中國圖像圖形學(xué)報,2014,19(3):476-483.

[13]王之津,周鵬,韓正彪.基于決策樹算法的競爭對手識別模式研究[J].情報理論與實踐,2013,36(3):1-6.

[14]陳子春,黃小剛.基于模糊相容關(guān)系的集值決策表的相對約簡[J].西華大學(xué)學(xué)報：自然科學(xué)版,2012,31(4):31-36.

[15]彭宏,吳鐵峰,張東娜，等.粗糙模糊模型及其在入侵檢測中的應(yīng)用[J].西華大學(xué)學(xué)報：自然科學(xué)版,2005,24(3):1-3.

[16]謝小林.基于ID3算法的道路客運行業(yè)信用評級模型[J].西華大學(xué)學(xué)報：自然科學(xué)版，2007，26(1)：25-27.

(編校：饒莉)

ANewMultivariatetheDecisionTreeAlgorithmBasedontheDecisionClassification

HUANG Jun-nan

(QuanzhouVocationalCollegeofEconomicsandBusinessInformationDepartment,Quanzhou362000China)

A new multivariate decision tree algorithm is proposed based on the conceptions of indiscernibility relation, compound operations, set operations and logical operation in set theory. It consists of five steps. Firstly, decision is classed according to the decision attribute value. Secondly, the attribute value is worked out according to the set intersection of the decision classes condition attribute. Thirdly, the independent decision condition attribute values are obtained according to each condition attribute field of the decision classification. Fourthly, multivariable decision rules are find out with compound operations of the decision classe condition sets. Finally, the OR operation is used to connect every decision rule in order to produce a complete rule. Experiment results demonstrate that the algorithm is effective. The time complexity results demonstrate that this algorithm has better time performance than rough sets algorithms, and no less than ID3 algorithm indeed.

univariate decision tree; multivariable decision tree; decision table; set operation; logic operation

2014-11-15

福建省教育廳科技項目(JB13357)。

黃俊南(1977—)，男，講師，碩士，主要研究方向為數(shù)據(jù)庫、算法分析、系統(tǒng)分析。

TP301.6

：A

：1673-159X(2015)03-0006-07

10.3969/j.issn.1673-159X.2015.03.002