余建軍,張瓊之

(華南理工大學 工商管理學院,廣州 510640)

引言

ID3算法是著名的決策樹,它是以信息論為基礎的一項從上而下的貪心算法,基于熵的計算從根節(jié)點處的所有實例訓練集合開始構造決策樹.它通過概率的相關運算來分析對象的屬性值,從而畫出像一棵倒立的樹形結構圖來形象生動地解說實例,以助于分析決策者做出預測決策.ID3算法規(guī)則簡單,容易讓人理解,其算法與最基礎的決策樹算法[1]保持一致,一般用來解決離散值一類的問題,構造的樹尤為形象地說明結果,一目了然,得到了眾多學者的喜愛.

目前,ID3算法是眾多決策樹構造算法中應用得最為廣泛的一種,如在醫(yī)學、教學、公司業(yè)績上的應用等.孫道[2]把工廠所關注的特征變量對象返回的期望值傳遞給ID3算法中遞歸過程,構造出決策樹模型,提高算法在其他應用中的移植性.以上的學者是把決策樹ID3算法運用到實際實例中去,但并沒有進行改進及優(yōu)化算法,ID3算法自身所帶的局限性還是存在的,還是有不少問題值得研究的.ID3算法進行局部分析,每次只選擇一個屬性分析,從而產生大量規(guī)則以致效率會下降,并且只能做到局部最優(yōu);它優(yōu)先考慮屬性值數目最多的屬性,但問題是屬性值多不一定是最優(yōu)的測試屬性;它構造的決策樹是單變量決策樹,而忽略了屬性之間可能存在的相互依賴的關系;它的計算方法比較復雜,由于是關于對數log 的運算,所以運算量非常大;它對信息系統(tǒng)的數據沒有進行簡化,存在冗余的信息,當系統(tǒng)大量信息時會變得復雜,構造決策樹所需的時間也會增多.

由于ID3算法只能處理離散屬性值,Quinlan 又投入決策樹算法的研究當中去,于1993年提出了以ID3為基礎核心的C4.5算法,它不僅能處理離散屬性值,還能處理連續(xù)屬性值,并且繼承了ID3算法的所有優(yōu)點.接著,Breman 等人提出了構造一顆二叉樹的分類與回歸樹算——CART算法,它具有非常強大的統(tǒng)計解析能力,處理數據后得到一顆二叉樹,簡潔且易懂.此外,IBM 的研究人員提出了SLIQ算法,具有很好的伸縮性.后來,很多學者致力于研究多決策樹綜合技術,探索出各種多決策樹的分類方法,例如Schapire R 提出的Boosting、Breiman 提出的Bagging、Random Forest 分類方法等.再后來,決策樹的增量算法出現了,有增量ID3、ID5R 等[3].

黃愛輝等人利用數學上等價無窮小的性質提出一種新的改進的ID3算法[4].楊霖等人提出了基于粗糙集、粒計算和分類矩陣的ID3 改進算法[5].作者引入修正參數來改進ID3算法傾向于多值屬性選取的問題[6,7].也有學者利用模糊規(guī)則提出了兩種ID3 改進算法[8,9].李建等人[10]在ID3 的基礎上引入屬性重要度值用以計算新的信息熵,并在信息增益計算中加入關聯度函數比,提出了AFIV-ID3算法,克服了ID3 多值偏向的缺點.大部分學者都是針對ID3 取值較多的屬性和只能處理離散型數據這兩個缺陷進行改進及其優(yōu)化算法的,少有學者利用粗糙集中的屬性約簡去刪除系統(tǒng)中多余的信息.

于天佑等人[11]研究表明在選定的特定類的數量相對全部決策類的數量較少時,約簡的結果可能會更短,約簡的效率也會有不同程度的提升.鄔陽陽等人[12]當前研究中拓展粗糙集模型在約簡理論完善、大數據處理、特殊數據處理等3 個方面的問題依然存在.尹繼亮[13]利用區(qū)間值、正域,并引入局部約簡的概念,設計了基于差別矩陣的局部約簡算法.粗糙集屬性約簡算法是一種數據預處理的有效方法,但指標多的時候,使用區(qū)間值與正域求解是非常困難,運行起來效率低下,因此屬性約簡的應用研究相對較少.少有學者應用分辨函數去求解屬性約簡,更少學者想到要把ID3中計算熵公式中的復雜對數進行化簡.本文將介紹ID3 的基本原理,針對ID3 信息系統(tǒng)存在冗余知識與計算方法復雜這兩點缺點進行改進,提出了基于粗糙集屬性約簡的簡化ID3算法,重點在于改進算法的實例分析、實驗仿真和結果分析比較.

1 ID3算法的基本理論

決策樹算法這個說法最早出現于上世紀60年代,到了1979年,澳大利亞學者Quinlan 提出了迭代兩分器算法(Iterative Dichotomizer3),故簡稱ID3算法.決策樹是數據挖掘分類算法中的一個重要分支,是一種歸納學習的貪心算法,屬于有監(jiān)督學習法.它主要是以實例為基礎,通過概率的相關運算來分析對象的屬性值,從而畫出像一棵倒立的樹形結構圖來形象生動地解說實例,以助于分析決策者做出預測決策.下面簡述一下ID3 的基本理論.

對于一組實例訓練樣本集合U,共有n 個樣本集合;分類屬性集合為C,有c 個不同的類;決策屬性集合為D,將實例訓練集合分為d 個不同的類Di(i=1,2,···,d),每個類的個數為ni(i=1,2,···,n),則 Di類在集合U 中出現的概率為 Pi=ni/n,則計算集合U 劃分d 個類的信息熵為Ci(i=1,2,···,c).

假設分類屬性集合C 的屬性值集合為Values(C)，CCi是集合U 中屬性C 的值為Ci的樣本子集,該子集實例個數為t,屬于 Di類的個數有ti(i=1,2,···,t),子集Ci在屬性集合C 出現的概率為Pti=ti/t,則屬性集合C 劃分為c 個類的信息熵為:

定義1.選擇分類屬性C 后的實例訓練樣本集合U 的信息熵為:

即在選擇分類屬性集合C 后的信息熵為其每一個子集Ci的 信息熵的加權和,權值為子集CCi中值的個數占集合U 的個數的比例.

定義2.屬性C 相對實例訓練樣本集合U 的信息增益為:

信息增益指的是因知道屬性C 后而導致集合U 的信息熵下降,Gain(U,C)越小,說明H(U)下降得越快,H(U,C)所含的信息量就越大,屬性C 就難以從眾多的分類屬性中分類出來.所以,ID3算法才選擇信息增益最高的屬性作為測試屬性.

2 基于粗糙集屬性約簡的簡化ID3算法

2.1 屬性約簡

定義3.設 D ?C,如果D 是獨立的,且IND(D)=IND(C),那稱D 是等價關系族C 的一個約簡(Reduct).

一個信息系統(tǒng)里面含有很多知識信息,有些知識很可能是重復的或是沒有必要,也就是說這些知識對該信息系統(tǒng)是冗余的,把多余的知識刪掉后剩下的知識就是知識約簡.即知識約簡還是與原來的信息系統(tǒng)保持有同樣的分類能力的,只不過是把一些沒必要的知識刪去而已,從而使得分類時更加簡便、精確.

定理1[14].設X ?C,

1)如果? x ∈RED(X),那:

2)如果? x ∈X-RED(X),則:

從上面的命題可以看出,知識約簡中每一個元對約簡中的其余元都是必不可少,而約簡外的其他元對于約簡中的任何一元都是不必要,即是可以刪去.

定義4.設C 和D 為論域U 上的等價關系,D 的C 正域記作 P OSC(D),定義為:

其中,X ∈U/D.

顯然,相對約簡是兩個屬性之間的關系.POSC(D)解釋了知識 U/C 的信息正確歸類到屬性D 的等價類中的準確性.

定義5.設C 和D 為論域U 上的等價關系族,R ∈P,如果:

就稱R 為C 中D 可省的,反之就稱R 為C 中D 不可省[3]的.如果C 中任意一個關系R 都是不可省的,就稱是D 獨立的,也就是說C 是相對于D 獨立的.

定義6.設S ?C,稱S 為C 的約簡,當且僅當S 是C 的D 獨立子族,且:

即稱之為相對約簡.

定理2.C 的D 核等于C 的所有D 約簡的交:

定義7.令T=(U,A,V,f)為一個信息系統(tǒng),U 中元素的個數記為| U|=n,|A|=m,T 的分辨矩陣M 定義為一個n 階對稱矩陣[3],其i 行j 列處的元素可定義為:

其中,f 稱為分辨函數,使得mij可以區(qū)分屬性.

對于每一個a ∈A,指定布爾變量 a[2],將T 的f 函數定義為一個m 元布爾函數:

其中,∧ 為合取,∨ 為析取.可以看出,分辨函數f 的析取范式中的每一個合取式對應一個約簡,約簡的交集即為核.

2.2 化簡算法

下面簡化的公式是基于本章中的式(1),假設論域U 中的訓練樣本集只有兩類,即決策屬性集合D 中只有兩種類別,稱為正例與反例,設其占的個數分別為P 與N,分類屬性集合C 中對應的正例與反例的個數分別為 pi,ni,則公式可以寫成:

由對數換底公式:logab=logcb/logca,其中a,b,c為大于0 且不等于1 的常數.

故:

又由數學分析中的泰勒公式[15],有:

得ln(1-x)=-x-x2/2-x3/3+···+(-1)xn/n.

當x 趨于0 時,l n(1-x)≈-x-x2/2.

所以:

因為5 /(N+P)ln2為常數,故信息熵簡化公式可寫為:

3 實例分析

本文中的例子摘自李雄飛等著者編寫的第二版《數據挖掘與知識發(fā)現》,詳情見參考文獻[3].下面以表1 為例,運用ID3算法構造決策樹.該表中一共有14 個樣本,樣本構成的集合為U,分類屬性一共有4 種,決策屬性只有1 種,且PlayTennis 有兩個不同的值{yes,no},也就是有兩個不同類D1,D2.

表1 PlayTennis 的訓練樣本集[3]

為了便于計算,把表1 轉化為 PlayTennis 訓練集數值化數據,如表2.

表2 PlayTennis 訓練集數值化數據

第1 步.由決策表2 PlayTennis 訓練集數值化數據,可得:

故該決策表是一致決策表,即集合D 依賴于集合C.

第2 步.畫出決策表的分辨矩,見表3

第3 步.通過分辨函數求出屬性的約簡.

由畫出決策表的分辨矩,見表3,得分辨函數為:

因此,決策表的核為:OWT ∩OWH=OW

即說明Outlook 與Wind 這個屬性在做決策分類時是必不可少,該系統(tǒng)的分類屬性只需要Outlook、Wind、Temperature 或者Outlook、Wind、Humidity 這3 個就可以進行歸類.

第4 步.選擇Outlook、Wind、Temperature 這3 個屬性進行決策,用信息熵簡化公式g 計算.

Outlook:go=2?3/(2+3)+4?0/(4+0)+3?2/(3+2)=6/5同 理,可求得:gw=27/8 ,gT=37/12.

顯然,Outlook 的信息熵最小,故取其作為根節(jié)點,畫出部分樹如圖1.

第5 步.在屬性Outlook 的條件下繼續(xù)計算分類屬性的信息熵,選擇最小者作為節(jié)點.

同理,當Outlook 取值為Sunny 時,有:

Wind:gSunnyW=7/6.

Temperature:gSunnyT=1/2.

故在樹的左邊第二節(jié)點選擇屬性Temperature.

表3 決策表2 的分辨矩陣

圖1 部分決策樹

以此類推,直到當前節(jié)點的訓練樣本實例是屬于同一類時就可以結束計算了,得出一棵決策樹如圖2.

圖2 決策樹1

如果在第三步中選擇Outlook、Wind、Humidity這3 個屬性的話,得到決策樹結果跟用傳統(tǒng)ID3算法構造的一樣,如圖3.

4 仿真實驗與結果分析

4.1 仿真實驗環(huán)境與實驗內容

本實驗涉及的設備、語言等具體環(huán)境如表4.

為了驗證改進算法的運行時間比ID3 的少,本文用C++語言編寫程序進行實驗,實驗數據主要來源于UCI Machine Learning Repository,選取了Balance Scale Data Set 庫,網址是:http://archive.ics.uci.edu/ml/datasets.html.

決策屬性為Class Name:Yes,No,分類屬性有4 種,如表5.

圖3 決策樹2

表4 實驗環(huán)境

表5 實驗內容的分類屬性與種類

這個數據集是為了模擬心理學實驗結果而產生.本文中選取的每個例子被分類為平衡秤尖端在右側或是在向左端,實驗中分別標記為Yes,No.屬性是左重量,左距離,右重量和右距離.

該實驗用C++編程的流程如圖4.

圖4 編程流程圖

4.2 實驗結果分析

4.2.1 算法的正確性與可行性

ID3算法用的信息熵公式:

其中,p1,p2分別指的是實例訓練集合中正例與反例所占的比例.

基于粗糙集方法的屬性約簡化簡算法用的信息熵公式為:

其中,pi,ni分別指的是實例訓練集合中正例與反例的個數.

由此可畫出式(14)與式(15)的函數圖像如圖5.

由圖5 可知,ID3算法與基于粗糙集屬性約簡的簡化ID3算法的熵的范圍都是 0 到1,但是改進的算法的熵的變化幅度比ID3 的大.基于粗糙集屬性約簡的簡化ID3算法運算復雜度要比ID3算法的要低得多,省去了log 對數的計算,并且保持了跟傳統(tǒng)ID3算法一樣的準確率.因此,改進的算法并沒有改變熵函數的性質,可見其的正確性與可行性,并且擴大了熵的變化幅度.

圖5 熵的函數圖像

4.2.2 算法的優(yōu)勢

通過實驗可知,基于粗糙集方法的屬性約簡化簡算法的計算時間比ID3 少,具體如表6.

從上述仿真實驗以及分析可以得出以下結論:

1)基于粗糙集方法的屬性約簡化簡算法的熵函數性質并沒有改變,繼承了ID3 的所有優(yōu)點;

2)基于粗糙集方法的屬性約簡化簡算法的計算時間比ID3 的少,這無疑是一個優(yōu)勢.

表6 實驗結果

5 結論

本文先通過文獻綜述總結了決策樹ID3 的歷史發(fā)展過程,概述了當前學者研究改進及優(yōu)化決策樹ID3算法的現狀和結論.本文通過實例分析與實驗驗證,基于粗糙集屬性約簡的簡化ID3算法的優(yōu)勢之一是刪掉了冗余的知識,是決策系統(tǒng)更加精煉簡潔,能快速找出關鍵的分類屬性;優(yōu)勢之二是保持了ID3 的一切優(yōu)點,與ID3 有同樣的準確率與精度;優(yōu)勢之三是選取測試屬性的計算公式中沒有復雜的對數函數,只有簡單的加法、乘法和除法,經實驗證明,運算時間比ID3 的要少.缺點是在求屬性約簡時,規(guī)模過大的話,用分辨函數求解的難度就會變大.

總的來看,本文處于研究階段并沒有把結論應用到社會生活實例中去,所以本文還是存在不足之處,還是有很多值得再去深入研究、探索的地方,未來的研究方向以下這兩點:1)本文提出的基于粗糙集的決策樹ID3算法相對ID3 來說確實是有優(yōu)勢,但在求屬性的約簡過于繁瑣,所以下一步的研究是尋求更加簡單的方式去求屬性的約簡,完善基于粗糙集方法的屬性約簡化簡決策樹算法.2)由于時間及其能力不足等等客觀條件的限制,本文沒有將改進的算法運用到更多的實際生活例子中去并用于預測,因此該論文得到發(fā)展的話,應該更重視研究把此算法改得更加合理性、科學性、可行性.