于宏濤, 賈宇波

(浙江理工大學 信息學院, 杭州 310018)

決策樹算法在數(shù)據(jù)挖掘領域占有非常重要的地位.當前主要的決策樹算法[1]包括ID3算法、C4.5算法、CART算法、SLIQ算法、SPRINT算法、PUBLIC算法等. C4.5算法[2]是1993年由Quinlan提出的, 其因直觀高效等優(yōu)點在醫(yī)療、金融、教育、互聯(lián)網(wǎng)等多個領域得到廣泛應用. 徐鵬等[3]利用C4.5算法對網(wǎng)絡流量進行了分類; 羅森林等[4]將C4.5算法引入到糖尿病的數(shù)據(jù)處理中, 建立了有效的預測糖尿病的規(guī)則; 周琦[5]采用C4.5算法對學生成績進行分析, 對學生高考成績進行了預測; 呂曉丹[6]利用C4.5算法為商業(yè)銀行建立了企業(yè)信用評價模型. 該算法的基本思想是首先將整個數(shù)據(jù)集做為根節(jié)點, 用各個屬性的信息增益率作為度量屬性重要程度的標準, 選擇信息增益率最大的屬性作為分裂屬性將根節(jié)點劃分成若干個子節(jié)點,并在各個子節(jié)點上重復進行分裂操作生成一棵完整的決策樹.

C4.5算法克服了ID3算法偏向于選擇屬性值較多的屬性的缺點, 新增了對連續(xù)屬性的處理方法. 但是該算法生成的決策樹分類精度不高, 樹的規(guī)模較大. 造成上述問題的原因為: 1) C4.5算法在選擇連續(xù)屬性的分裂點時只考慮單個屬性與類別屬性的關系, 割裂了各個屬性之間的聯(lián)系, 這就造成了信息損失, 導致最終的決策樹分類精度下降. 2) 在一個信息系統(tǒng)中, 并不是所有屬性都是同等重要的, 有些屬性與分類無關, 這些冗余屬性的存在, 使生成的決策樹規(guī)模較大, 分支增多.當前有許多學者對C4.5算法進行了優(yōu)化, 劉佳等[7]基于Fayyad和Irani的證明, 對C4.5算法的連續(xù)屬性離散化等方面進行了改進, 提高了算法效率和分類準確率; 曹燕等[8]提出了一種粗糙集理論與C4.5算法相結合的算法RSC4.5, 降低了分類結果的復雜度; 黃秀霞等[9]將泰勒公式引入到信息增益的計算公式內(nèi), 提高了決策樹的構建效率.

本文提出了一種基于粗糙集理論與CAIM準則的C4.5改進算法. 本算法在連續(xù)屬性的處理上采用了一種基于CAIM準則的多屬性關聯(lián)的離散化算法, 使得在連續(xù)屬性離散化過程中造成的信息損失降低, 提高了決策樹的分類精度; 運用一種基于粗糙集理論的屬性約簡算法去除了決策表中與分類無關的條件屬性,使得生成決策樹的規(guī)模減小.

1 基于CAIM準則的離散化方法

C4.5算法的一個優(yōu)點是支持對連續(xù)型數(shù)據(jù)的處理, 其處理方式為對首先每個連續(xù)屬性選取足夠多的候選斷點, 再分別計算每個候選斷點的信息增益, 選取信息增益最大的斷點作為最終斷點. 但是C4.5算法的斷點選擇過程中只考慮了單個連續(xù)屬性與決策屬性之間的關系, 這中處理方式造成了較多的信息損失, 使得構建的決策樹分類精度降低. 楊萍等[10]提出了一種基于CAIM準則的數(shù)據(jù)離散化方法, 該算法根據(jù)決策表中決策屬性與多個條件屬性之間的聯(lián)系構造離散化框架, 使得離散化后的條件屬性與決策屬性的關聯(lián)程度達到最大. 利用這種離散化方法可以降低連續(xù)屬性離散化過程中的信息損失, 有效提高C4.5算法的分類精度.

1.1 CAIM準則

Kurgan和Cios在2004年提出了CAIM準則[11],它是類別和屬性值之間的關聯(lián)程度的一種度量. 下面對CAIM準則進行簡單的介紹.

給定一個決策表S, 條件屬性集為C, C中包含w個連續(xù)屬性, 決策屬性為syggg00. 決策表S共包含n個元素, 決策屬性d將所有元素劃分為k個類別. 對C中任意一個連續(xù)屬性c, 可以確定一個離散化框架, 將c的值域劃分為m個離散區(qū)間為屬性c值域中的最小值, cm為最大值,對于任意的有 ci＞ci–1.

根據(jù)一個確定的離散化框架、決策屬性變量和連續(xù)屬性c的離散區(qū)間, 可以確定一個二維矩陣, 如表1所示. 其中表示決策屬性d的k個取值,eir表示在決策表中決策屬性取值為di且連續(xù)屬性c的取值在(cr–1, cr]中的元素個數(shù). Ndi表示決策屬性取值為di的元素個數(shù), Ncr表示屬性c的取值在區(qū)間(cr–1,cr]的元素個數(shù).

表1 離散化二維矩陣

由一個離散化二維矩陣可得CAIM準則的如下定義:

{eir}max表示當i變化時eir的最大值, 如果{eir}max=則稱決策屬性取值為dh的元素構成的集合為區(qū)間(cr–1, cr]中的主導類. 主導類中包含的元素個數(shù)越多, CAIM的值就越大, 類別與離散區(qū)間的關聯(lián)程度就越大.

1.2 一種基于CAIM準則的離散化算法

離散化算法的根本目的是求取一個斷點集合, 將連續(xù)屬性劃分為多個區(qū)間. 在最理想的情況下, 可以選取出k–1個斷點(k為決策屬性取值個數(shù)), 斷點劃分出的k個區(qū)間中的元素全部屬于同一個類別, 此時CAIM達到理論上的最大值CAIM=n/k, k–1個斷點為最佳劃分斷點集合. 在實際問題中CAIM的值隨著斷點的增加而增加, 達到局部最大后開始下降, 此時為使決策屬性與待離散的條件屬性關聯(lián)程度達到最大, 必須要選擇足夠多的斷點, 使劃分出的離散區(qū)間中所有元素都屬于同一個類別. 如果只考慮離散區(qū)間中的主導類則會造成信息損失, 使離散結果的質量下降.

前面論述的都是單個連續(xù)條件屬性與決策屬性之間的關聯(lián), 實際上僅僅依靠單個屬性是不能區(qū)分元素的, 因此應該考慮到?jīng)Q策屬性與所有屬性之間的關聯(lián)關系, 從而降低信息損失, 提高分類的精度. 從多個屬性的角度考慮連續(xù)屬性的離散化, 實質上就是尋找一個最小的斷點集合, 這些斷點可以將整個決策表劃分成一個個的超立方體, 并使得每個超立方體中的元素都屬于同一個類別. 在考慮多個屬性與決策屬性關聯(lián)的離散化算法時如果只追求由斷點集劃分出的超立方體空間中的元素都屬于同一個類別, 則會使斷點個數(shù)太多, 離散效果不好. 因此我們需要在斷點個數(shù)與超立方體空間中元素純度之間尋找一個平衡, 使離散化結果達到我們想要的效果. 由前面的討論我們知道在最理想的情況下每個連續(xù)屬性的斷點個數(shù)為k–1個, 將每個連續(xù)屬性劃分為k個離散區(qū)間, 在此我們將k設為離散化區(qū)間的期望個數(shù). 在每個離散化區(qū)間中, 設定一個最小閾值, 使得每個區(qū)間中主導類的個數(shù)不小于最小閾值, 給出一個常量則有{eir}max＞R*Ncr, r=1, 2,…, k. 此時有最小的CAIM期望值為:

設CAIMpmax為局部最大值, 則每增加一個斷點CAIM的下降幅度不超過(CAIMpmax–CAIMexp)/(k–1)時, 可以得到預期的離散化結果.

算法1. 基于CAIM準則的多屬性關聯(lián)離散化算法1) 設i=1, DS={U}, 離散化結果斷點集合CutPoint=.2) 設DStemp=, r=1. 對DS中的一個元素Ur, Ur內(nèi)共包含kr個類別.

3) 取一個連續(xù)屬性 ci, 將 ci的值域按照升序排列得:, 取兩個相鄰屬性值的平均數(shù)構成集合. B為候選斷點集. 初始化離散化框架為, 歷史CAIM最大值CAIMpmax=0, 屬性ci的斷點集合Point=.4) 設j=1, CAIM的最小期望值為CAIMexp=|Ur|R2/kr.5) 遍歷B中的斷點加入離散化框架LS中計算CAIM值, 取使CAIM值最大的點, 記CAIM最大值為CAIMh. 6) 如果第5步中CAIMh滿足 或, 則令CAIMpmax=CAIMh. 將第4步選擇的斷點加入離散化框架LS和斷點集合Point中, 并在B中刪除該斷點.另j=j+1, 如果j＜kr則轉到第5步.7) 假設離散化框架LS將Ur劃分成多個小集合, 設Ux是其中一個,如果Ux中的元素不都屬于同一類別則另.8) 令 DS=DStemp, r=r+1, 如果, 則轉至第 3 步.9) 此時Point為屬性ci的斷點集合, 令, i=i+1,如果i＜l, 轉至第2步, 否則算法結束, CutPoint為各個連續(xù)屬性的斷點集合.

2 基于粗糙集理論的屬性約簡

2.1 粗糙集理論

1982年Pawlak提出了粗糙集理論[12], 它是一種新的處理不確定、不精確和含糊信息的數(shù)據(jù)分析理論.下面對本文用到的粗糙集理論相關概念進行簡單介紹.

定義2. 設P和Q分別是決策表S的屬性子集,則P, Q分別將論域U構成一個劃分X=U/IND(P)和Y=U/IND(Q)記將X和Y在論域U上的概率分布表示為:

其中card(E)表示集合E中的元素個數(shù). 記p(Yj|Xi)為Yj對Xi的條件概率, 計算公式如下:

定義3. 對于給定的屬性子集P和他的概率分布,稱H(P)為P的信息熵, 計算公式如下:

定義4. 對于給定的屬性子集P和Q以及它們的概率分布和條件概率分布, 稱H(Q|P)為Q相對于P的條件熵, 計算公式如下:

定義5: 給定屬性子集P、Q以及他們的信息熵和條件熵, 稱H(Q)-H(Q|P)為P與Q的互信息, 記為I(P;Q).

定義6[13]. 對于決策表S, 條件屬性集為C, 決策屬性集為D, 取p∈C, 如果條件熵H(D|C)=H(D|(C-{p})),則稱屬性p在C中是D-不必要的; 如果條件熵H(D|C)＜H(D|(C-{p})), 則稱屬性p在C中是D-必要的.如果C中所有屬性都是D-必要的, 則稱C是相對于決策D獨立的. C中所有D-必要的屬性組成的集合稱為C的相對于決策D的核, 記為CORED(C).

定義7. 對于決策表S, 條件屬性集為C, 決策屬性集為D, 設如果滿足都有則稱B是C的一個相對決策D-約簡, 記為是所有約簡組成的集合.

2.2 屬性約簡算法

屬性約簡是運用粗糙集理論處理的主要問題之一.屬性約簡的根本目的是在保證決策表分類能力不變的前提下刪除條件屬性中的冗余屬性. 當前有很多有效的屬性約簡算法, 如基于屬性重要度的約簡算法[14]、基于信息熵的約簡算法[15]、基于互信息的屬性約簡算法等[16]. 本文將采用基于互信息的屬性約簡算法對決策表進行屬性約簡, 其約簡算法步驟如算法2.

算法2. 基于互信息的屬性約簡算法1) 計算決策表中條件屬性C和決策屬性D的互信息I(C;D)=H(D)–H(D|C).2) 計算C相對于D的核屬性集合CORED(C), 另B=CORED(C).

3) 計算B與決策屬性D的互信息I(B;D)=H(D)–H(D|B), 如果I(B;D)=I(C|D)則轉到第5步.4) 取任意的條件屬性ci,, 計算互信息,求得使I(ci, D|B)最大的屬性cm, 令, 轉到第3步.5) 輸出B, B即為決策表的屬性約簡.

3 基于粗糙集理論與CAIM的C4.5算法

3.1 C4.5算法

C4.5算法是一種在ID3算法基礎上改進的決策樹生成算法, 它采用信息增益率作為節(jié)點選擇衡量標準,在ID3算法的基礎上增加了對連續(xù)屬性的處理和剪枝方法. C4.5算法整體上分為3步: 1) 如果決策表中有連續(xù)屬性, 對連續(xù)屬性進行離散化處理. 2) 以信息增益率做為分裂節(jié)點的選擇標準, 遞歸構建決策樹. 3) 對構建的決策樹采用悲觀剪枝方法[17]進行剪枝處理. 下面首先介紹信息增益率的相關概念, 再對C4.5算法的步驟進行簡單說明.

定義8. 給定一個決策表S, 決策屬性將整個決策表劃分為m個樣本子集表示決策表中一個元素分布在Si中的概率, S的信息熵定義為:

定義2. 給定決策表S, 條件屬性c將決策表劃分為k個不同樣本子集則按屬性c劃分S的信息增益定義如下:

定義3. 信息增益率定義如下:

C4.5算法的具體步驟如算法3.

算法3. C4.5算法1) 如果決策表中有連續(xù)屬性, 則首先對決策表的連續(xù)屬性變量進行離散化處理. 設連續(xù)屬性有n個取值, 處理過程為首先對連續(xù)屬性取值進行從小到大排序, 再選擇相鄰值的平均值作為分割點將連續(xù)屬性劃分為n個小區(qū)間.

2) 計算每個屬性的信息增益率. 對于連續(xù)屬性, 分別計算以候選分割點進行劃分的信息增益率, 選擇信息增益率最大的候選分割點作為該連續(xù)屬性的最終分割點. 比較各個屬性的信息增益率, 選擇信息增益率最大的屬性作為分裂節(jié)點.3) 分裂節(jié)點的每個屬性取值都對應一個子集, 再對子集遞歸執(zhí)行第2步, 直到劃分的每個子集中的元素都屬于同一類別, 生成決策樹.4) 對第3步生成的決策樹采用悲觀剪枝方法進行剪枝處理.

3.2 改進的C4.5算法

通過對4.5算法的分析, 發(fā)現(xiàn)以下問題導致C4.5算法生成的決策樹分類精度不高, 樹的規(guī)模較大.1) C4.5算法對連續(xù)屬性的處理只考慮了單一連續(xù)屬性與決策屬性的關聯(lián)關系, 在離散化過程中會造成較多的信息損失, 導致分類精度降低. 2) 決策表中可能存在與分類無關的冗余屬性, 使得決策樹構建過程中生成樹的規(guī)模過大.

為解決上述問題, 本文提出了一種基于CAIM準則和粗糙集理論的C4.5優(yōu)化算法. 其基本思想是首先判斷決策表中是否有連續(xù)屬性, 如果有則采用基于CAIM準則的數(shù)據(jù)離散化方法對連續(xù)屬性進行離散化處理. 再利用基于粗糙集理論的屬性約簡算法對決策表進行屬性約簡, 最后計算每個屬性的信息增益率, 選擇分裂屬性遞歸構造決策樹. 此算法采用的離散化方法考慮了多個條件屬性與決策屬性的關聯(lián)關系, 避免了C4.5算法在連續(xù)屬性的處理過程中只考慮單一屬性與決策屬性關系所造成的信息損失, 可有效提高決策樹的分類精度. 改進的C4.5算法在構建決策樹之前增加了屬性約簡的步驟, 屬性約簡可以剔除與分類無關的條件屬性, 使生成的決策樹規(guī)模減小. 該算法具體步驟如算法4.

算法4. 基于CAIM準則與粗糙集理論的C4.5改進算法1) 如果決策表中有連續(xù)屬性, 運用于CAIM準則的離散化方法對連續(xù)屬性進行離散化處理, 否則轉至第2步.2) 運用基于粗糙集理論的屬性約簡算法對決策表進行屬性約簡, 去除冗余屬性.3) 計算每個屬性的信息增益率, 選擇信息增益率最大的屬性作為分裂節(jié)點.4) 分裂節(jié)點的屬性取值將決策表劃分為多個小決策表, 對每個小決策表遞歸執(zhí)行第3步, 直到劃分出的每個小決策表中的元素都屬于同一類別, 生成決策樹.5) 對第4步生成的決策樹采用悲觀剪枝方法進行剪枝處理.

4 實驗設計與分析

為驗證本文改進算法的有效性, 從UCI機器學習數(shù)據(jù)庫[18]中選取了3個有代表性的決策數(shù)據(jù)集: 虹膜植物集iris、葡萄酒識別數(shù)據(jù)集wine、皮馬印第安人糖尿病數(shù)據(jù)集pima進行實驗分析. 這3個數(shù)據(jù)集的詳細信息如表2所示.

表2 實驗數(shù)據(jù)

取每個數(shù)據(jù)集的70%作為訓練樣本數(shù)據(jù), 30%為測試數(shù)據(jù). 將本文算法中離散化過程的參數(shù)R設為0.8與Weka中的J48(即C4.5)算法在分類準確率與生成決策樹節(jié)點個數(shù)兩個方面進行對比, 實驗結果如表3所示.

表3 實驗結果

從表3可以看出, 本文算法與C4.5算法相比iris數(shù)據(jù)集準確率提高了2.13%, 樹節(jié)點個數(shù)減少3個;pima數(shù)據(jù)集準確率提高了5.78%, 樹節(jié)點個數(shù)減少8個; wine數(shù)據(jù)集準確率提高了2.31%, 樹節(jié)點個數(shù)減少了2個. 從實驗結果中可以看出, 本文算法相較于C4.5算法在分類準確率和生成樹規(guī)模上都有一定程度的優(yōu)化, 證明本文算法切實有效可行. 通過本文算法生成的決策樹能夠更好的對新數(shù)據(jù)進行分類和預測.

5 結論

本文對基于CAIM準則的離散化方法、基于粗糙集理論的屬性約簡算法和C4.5算法進行了簡單介紹.通過對C4.5算法分類精度不高、生成決策樹規(guī)模較大的問題產(chǎn)生原因進行分析. 本文用基于CAIM準則的離散化方法代替C4.5算法中對連續(xù)屬性的處理方法, 在離散化的基礎上進行屬性約簡, 去除冗余屬性,降低了決策表的屬性維度, 最后生成決策樹. 實驗結果表明改進后的C4.5算法有更好的分類效果, 生成更為簡潔的決策樹.