決策規(guī)則樹方法

7.3

決策規(guī)則樹方法7.3.1IBLE方法的基本思想1、IBLE方法的特點IBLE方法是利用信息論中信道容量的概念作為對實體中選擇重要特征的度量。信道容量不依賴于正、反例的比例，依賴于訓練集中正、反例特征取值的選擇量。ID3方法每次選一個特征作為決策樹的結點.IBLE方法建立的決策規(guī)則樹中每個結點是由多個特征所組成。2、多元信道轉(zhuǎn)化為二元信道在各特征取多值的情況下，用互信息和信道容量作為特征選擇量，都會出現(xiàn)傾向于某取值的例子數(shù)較多的特征，這種傾向不都合理。解決辦法：對特征進行分解，化為二值特征。天氣晴多云雨天氣—晴天氣—多云天氣—雨yesnononoyesnononoyes

對氣溫等都可以做類似工作，這樣在選擇特征時就不會出現(xiàn)偏向問題。3、決策規(guī)則樹

規(guī)則1規(guī)則2規(guī)則nu1

u1

u1u2

u2

u2IBLE算法的一般決策規(guī)則樹規(guī)則1規(guī)則12規(guī)則13規(guī)則21規(guī)則11規(guī)則1規(guī)則n規(guī)則n1規(guī)則n2u1u1u1u1u1u1u2u2u2u2u2u2IBLE算法的復雜決策規(guī)則樹4、決策規(guī)則樹結點（1）規(guī)則表示形式?jīng)Q策規(guī)則樹中非葉結點均為規(guī)則。規(guī)則表示為：特征：A1，A2，...，.Am權值：W1，W2，...，.Wm標準值：V1，V2，...，.Vm閾值：Sp，Sn該規(guī)則可形式描述為：（1）sum:=0；（2）對i:=1到m作：若（Ai）=Vi，則sum:=sum+Wi；（3）若sum<=Sn，則該例為N類；（4）若sum>=Sp，則該例為P類；（5）若Sn<sum<Sp，則該例暫不能判，轉(zhuǎn)下一條規(guī)則判別。其中sum表示權和，（Ai）表示特征Ai的取值。（2）舉例設問題空間中例子有10個特征（屬性），特征編號從1到10。每個特性取值為{no,yes}，用{0,1}表示，規(guī)則是由重要特征組成的，對每個特征求出權值以表示其重要程度，刪除不重要特征得規(guī)則如下：特征：13467權值：1009010550040標準值：10110閾值：220，100現(xiàn)有三個測試例子：例子1：（1，0，0，0，1，0，0，1，1，1）例子2：（0，1，0，0，1，0，0，0，1，0）例子3：（0，1，0，0，1，0，1，0，1，1）特征12345678910權值1009010550040標準值10110權和例子一1000100111230例子二0100100010130例子三010010101190閾值：Sp=220，Sn=100例子1的權和sum=230，有sum>220，判定例子1屬于u1類。例子2的權和sum=130，有100<sum<220，認為例子2不能判，轉(zhuǎn)下一條規(guī)則判別。例子3有權和sum=90，有sum<100，判例子3的類別為u2類。規(guī)則中:

A1，A2，...，Am為組成規(guī)則的特征

W1，W2，...，Wm為對應的權值

V1，V2，...，Vm為對應特征取正例的標準值測試例子在該特征處取值與標準值相同，則sum（權和）加上對應權值，否則不加。Sp，Sn是判是、判非、不能判的閾值。測試例子的權和為sum:Sum>=Sp時判為是類（u1類）Sum<=Sn時判為非類（u2類）Sn<sum<Sp時認為不能判7.3.2IBLE算法IBLE算法由四部分組成： (1)預處理 (2)建規(guī)則算法 (3)建決策樹算法 (4)類別判定算法預處理：將例子集的特征取多值，變?yōu)槎鄠€特征分別取{0,1}。建規(guī)則算法：求各特征Ak的信道容量Ck，對于一個特征有分特征時，取最大C值的分特征代表該特征。權值的計算公式：Wk=[Ck×1000]（Wk取整）利用最大后驗準則定義該特征Ak的譯碼函數(shù)F(1)、F(0)。利用譯碼函數(shù)按正例（u1）輸入，計算特征Ak的標準值{0,1}。選取前m個信道容量較大的特征構造規(guī)則。計算所有的正、反比例的權和數(shù)，從它們的分布規(guī)律中得Sp、Sn閾值。建決策樹算法RW1W2W3(|PEP|≠0)∨(|NEP|≠0)(|PEM|≠0)∨(|NEM|≠0)(|PEN|≠0)∨(|NEN|≠0)PENE建規(guī)則算法規(guī)則NE′PE′PEPPENPEMNEPNENNEMIBLE建決策樹算法圖類別判定算法在得到一棵決策樹后，對一未知實體E進行分類：（1）置根結點位當前結點；（2）用當前結點中的規(guī)則對E進行判定；（3）輸出判別結果，結束。IBLE方法實例7.3.2.1配隱形眼鏡問題（1）患者配隱形眼鏡的類別患者是否應配隱形眼鏡有三類：

@1：患者應配隱形眼鏡

@2：患者應配軟隱形眼鏡

@3：患者不適合配隱形眼鏡（2）患者眼鏡診斷信息(屬性)

a：患者的年紀: (1)年輕(2)前老光眼(3)老光眼b：患者的眼睛診斷結果 (1)近視(2)遠視c：是否散光

(1)是：(2)否

d：患者的淚腺

(1)不發(fā)達；(2)正常表7.2配隱形眼鏡患者實例序號屬性取值診斷值序號屬性取值診斷值abcd@abcd@11111313221132111221422122

3

112131522213

411221162222351211317311136121221831123

7

122131931213

8122212031221

9211132132113

10211222232122

11212132332213

12212212432223利用IBLE算法得出的各類決策規(guī)則樹和邏輯公式（1）@1類的決策規(guī)則樹

規(guī)則1a=1b=1c=2d=20.210.0480.2820.282s1=0.5639

≤s1

>s1

非@1類@1類

等價規(guī)則為：c=2∧d=2∧a=1→@1 c=2∧d=2∧b=1→@1（2）@2類的決策規(guī)則樹

規(guī)則2 a=1,2b=1c=2d=2 0.0390.0080.3020.302 s1=0.6042

≤s1

>s1

非@2類@2類

等價規(guī)則為：c=1∧d=2∧b=2→@2 c=1∧d=2∧a=1→@2c=1∧d=2∧a=2→@2（3）@3類的決策規(guī)則樹

規(guī)則3 a=3b=2c=2d=1 0.01860.0040.0040.428 s1=0.004s2=0.0265 ≤s1

≥s2

s1<sum<s2

非@3類@3類

規(guī)則4

a=2b=1c=10.220.01440.0144s1=0.0144≤s1

>s1非@3類@3類邏輯公式推導為：上層結點的邏輯公式： d=1→@3 a=3∧b=2∧c=2→@3上層不能判斷邏輯公式有：

（b=2∧c=2)∨

(a=3)∨ (a=3∧b=2)∨ (a=3∧c=2)→繼續(xù)判別下層結點的邏輯公式：

b=1∧c=1→@3

a=2→@3合并后下層結點的邏輯公式：

a=3∧b=1∧c=1→@3

a=2∧b=2∧c=2→@3苯等八類化合物的分類問題類正例認對認錯正確百分比反例認對認錯正確百分比總正確百分比RQRT60TJ類一類二類三類四類五1022050552419515345524175160000093.1377568100100100100100155100509999999999999991368448997997999999999191622200087.774849699.899.810010010090.43979.58299.999.9100100100對八類化合物，IBLE的平均預測正確率為93.967%

IBLE與ID3的比較類IBLE/%ID3/%RT60TJ類二81.77976.78698.33472.20370.64389.322預測正確率IBLE比ID3高出近10個百