基于決策樹(shù)的數(shù)據(jù)挖掘-汽車評(píng)價(jià)分類的算法設(shè)計(jì)與實(shí)現(xiàn)

1、基于決策樹(shù)的數(shù)據(jù)挖掘汽車評(píng)價(jià)分類的算法設(shè)計(jì)與實(shí)現(xiàn)1 決策樹(shù)技術(shù)面臨的挑戰(zhàn)及目前研究方向隨著數(shù)據(jù)挖掘技術(shù)的興起， 作為擬人決策主要方法之一， 近年來(lái)決策樹(shù)又重新引起了人 們的興趣，并得到更廣泛的應(yīng)用。目前決策樹(shù)技術(shù)的主要研究方向有以下幾點(diǎn)：1.1 決策樹(shù)技術(shù)與其他技術(shù)的結(jié)合如何將決策樹(shù)技術(shù)和其他新興的技術(shù)相結(jié)合以便取長(zhǎng)補(bǔ)短一直是決策樹(shù)技術(shù)研究的熱 點(diǎn)，近幾年來(lái)國(guó)際上發(fā)表的有關(guān)決策樹(shù)的文章也大多集中在這個(gè)方面的研究。 近年關(guān)于決策 樹(shù)和其他技術(shù)的研究主要包括：1.1.1 決策樹(shù)技術(shù)和神經(jīng)網(wǎng)絡(luò)技術(shù)相結(jié)合 12 。人工神經(jīng)網(wǎng)絡(luò)的多層結(jié)構(gòu)使它具有對(duì)任意輸入輸出進(jìn)行映射的功能。同樣， 決策樹(shù)也具有產(chǎn)生 維

2、空間下任意復(fù)雜的決策邊界的功能。因此，可以將決策樹(shù)重新構(gòu)造成一個(gè)多層的 神經(jīng)網(wǎng)絡(luò)。 這種由決策樹(shù)轉(zhuǎn)化而成的神經(jīng)網(wǎng)絡(luò)具有加快神經(jīng)網(wǎng)絡(luò)訓(xùn)練速度等優(yōu)點(diǎn)。 另外一類 方法正好相反， 它研究的是由神經(jīng)網(wǎng)絡(luò)中得到所需要的決策樹(shù)。 這類方法解決了由神經(jīng)網(wǎng)絡(luò) 得到的知識(shí)難于被人們理解的缺點(diǎn)。1.1.2 決策樹(shù)技術(shù)和模糊集合原理的結(jié)合決策樹(shù)技術(shù)雖然有許多優(yōu)點(diǎn)，但也存在著不穩(wěn)定的缺點(diǎn)，即決策樹(shù)帶來(lái)了較大的變動(dòng)。 模糊集合的融通性使人們利用模糊邏輯來(lái)解決決策樹(shù)的這一缺點(diǎn)并取得了不錯(cuò)的效果。最 近，C.OIaru提出了一種新的模糊決策樹(shù)方法-軟決策樹(shù)。軟決策樹(shù)綜合決策樹(shù)的生成和修剪來(lái)決定其本身的結(jié)構(gòu)，并利用重修( R

3、efitting )和磨合( Backfitting )來(lái)提高樹(shù)的歸納能 力。 軟決策樹(shù)比一般決策 樹(shù)的正確率要高。 此外， M. Dong 等人 提出的 基于前瞻 (Look-Ahead )的模糊決策樹(shù)也能夠在得到較好的歸納特性的前提下產(chǎn)生較小體積的決策 樹(shù)4。1.1.3 決策樹(shù)技術(shù)和進(jìn)化算法，遺傳算法及遺傳編程的結(jié)合 56789 ?；谶M(jìn)化算法的決策樹(shù)系統(tǒng)具有較好的抗噪聲能力， 同時(shí)進(jìn)化算法很容易在并行計(jì)算機(jī) 上運(yùn)行， 因此可以期待基于進(jìn)化算法的決策樹(shù)的運(yùn)算能力有較大的提高。此外， 由于進(jìn)化算法為隨機(jī)算法， 它可以在任何時(shí)候?qū)ν粩?shù)據(jù)集合產(chǎn)生不同的決策樹(shù)，通過(guò)利用投票 (Vote)的方法可

4、以得到理想的分類器。 因?yàn)榭傮w分類器比單個(gè)分類器的錯(cuò)誤率低， 所以基于進(jìn)化算 法的決策樹(shù)在減小錯(cuò)誤率方面也有優(yōu)勢(shì)。 同樣，將決策樹(shù)運(yùn)用于進(jìn)化計(jì)算也能夠提高進(jìn)化算 法的性能。 例如， 利用決策樹(shù)為進(jìn)化算法播種具有較好質(zhì)量的初始種群能提高進(jìn)化算法的搜 索能力并縮短運(yùn)行時(shí)間。將遺傳算法用于分類和概念學(xué)習(xí)任務(wù)比較常見(jiàn)， 但真正將它作為一種發(fā)展決策樹(shù)的實(shí)用 工具的研究還比較少。 A. PapageIis 等將遺傳算法直接用于產(chǎn)生決策樹(shù)。與一般遺傳算法 采用二進(jìn)制串的形式不同， 他們采用了二進(jìn)制樹(shù)結(jié)構(gòu)來(lái)進(jìn)行問(wèn)題表示。 當(dāng)無(wú)關(guān)屬性或比較強(qiáng) 的條件相關(guān)屬性存在時(shí)，遺傳算法比其他的貪婪啟發(fā)方式( Greedy

5、Heuristics )具有優(yōu)勢(shì)。 D. R. CarvaIho 提出了一個(gè)混合決策樹(shù)和遺傳算法的算法， 一定程度地解決了低訓(xùn)練數(shù)據(jù)易 于產(chǎn)生錯(cuò)誤的規(guī)則的缺點(diǎn)。 需要注意的是， 遺傳算法和決策樹(shù)結(jié)合的缺點(diǎn)是計(jì)算量較大。 將 遺傳編程用于決策樹(shù)可以改進(jìn)標(biāo)準(zhǔn)貪婪決策樹(shù)歸納算法的一些局限性。遺傳編程種群中的每個(gè)個(gè)體都可以是一個(gè)決策樹(shù)。 遺傳編程中使用的函數(shù)是決策樹(shù)的特性以及遺傳編程中的終結(jié) 集(Terminal Set )。利用遺傳編程構(gòu)造決策樹(shù)可以取得比較好的效果，特別是發(fā)現(xiàn)小數(shù)據(jù) 量下的最優(yōu)決策樹(shù)。1.1.4 決策樹(shù)技術(shù)和多智能體的結(jié)合 將決策樹(shù)用于多智能體控制并不多見(jiàn)。 但正由于多智能體系統(tǒng)的

6、復(fù)雜性， 而機(jī)器學(xué)習(xí)有 潛力提供一個(gè)魯棒性較強(qiáng)的機(jī)制來(lái)有效協(xié)調(diào)各智能體間的行為，因此對(duì)多智能體結(jié)合機(jī)器學(xué)習(xí)是一個(gè)很有前途的方向。近幾年P(guān). Stone 和 M. Veloso 發(fā)表了一些這方面的文章10 1112 。他們提出了基于決策樹(shù) C4.5 算法中置信度( Confidence Factor )下的多智能體 控制，并將此應(yīng)用于機(jī)器人足球控制。1.2 尋找新的構(gòu)造決策樹(shù)的方法自從 Quinlan 提出 ID3 和 C4.5 方法后，有不少專家提出了其他構(gòu)造決策樹(shù)的方法， 如由 Brieman 等人提出的 CART 方法和由 Kass 提出的 CHAID 方法。最近， M. Ankerst

7、等提出了基于多維可視化下的交互式的決策樹(shù)構(gòu)造 13。此方法在決策樹(shù)構(gòu)造階段加入了專 家知識(shí)， 這樣便于用戶更深地理解產(chǎn)生決策樹(shù)的數(shù)據(jù)及最終產(chǎn)生的決策樹(shù)。同時(shí)此方法也顯著地減小了決策樹(shù)的大小。在 M. Ankerst 等提出的方法中，他們主要用兩類進(jìn)化算法替代 了傳統(tǒng)的貪婪搜索算法以實(shí)現(xiàn)數(shù)值屬性的任意分割。1.3 尋找更好的簡(jiǎn)化決策樹(shù)的方法簡(jiǎn)化決策樹(shù)的研究工作主要有兩個(gè)方面， 一是對(duì)比各種不同的簡(jiǎn)化決策樹(shù)方法， 分析它 們各自的特性、 優(yōu)點(diǎn)和缺點(diǎn)。 另外一個(gè)就是尋找更好的與傳統(tǒng)方法不同的簡(jiǎn)化決策樹(shù)的方法， 這一直是決策樹(shù)技術(shù)研究的一個(gè)熱點(diǎn)。 近年來(lái)， 針對(duì)不同的應(yīng)用領(lǐng)域并且隨著其他新技術(shù)的 加入

8、，陸續(xù)有這方面的文章發(fā)表。例如， D. Founrnier 等提出的一種新的修剪決策樹(shù)的方法 -DI 修剪法 14。此方法針對(duì)數(shù)據(jù)不確定的情況，利用特性索引(Quality Index )來(lái)權(quán)衡處理決策樹(shù)深度和節(jié)點(diǎn)雜質(zhì)。 DI- 修剪法將保持那些雖不能減小錯(cuò)誤率但能指出一些特殊性質(zhì)的 群體的子樹(shù)。 D. Founrnier 等認(rèn)為這對(duì)于研究不確定數(shù)據(jù)是非常關(guān)鍵的。1.4 研究產(chǎn)生決策樹(shù)的訓(xùn)練和檢驗(yàn)數(shù)據(jù)的大小及特性與決策樹(shù)特性之間的關(guān)系與上述簡(jiǎn)化決策樹(shù)不同， 這類研究著眼于產(chǎn)生決策樹(shù)的數(shù)據(jù)。 訓(xùn)練數(shù)據(jù)的增加經(jīng)常造成 決策樹(shù)大小的線性增加， 而這種增加并沒(méi)有都帶來(lái)決策樹(shù)準(zhǔn)確性的提高。一些專家認(rèn)為，

9、 在產(chǎn)生決策樹(shù)前盡量減少數(shù)據(jù)量比在決策樹(shù)產(chǎn)生后再簡(jiǎn)化決策樹(shù)更加有效。實(shí)際上， 這就是經(jīng)常提起的數(shù)據(jù)預(yù)處理技術(shù)( Data Preprocessing )，與決策樹(shù)修剪技術(shù)( Pruning )相對(duì)應(yīng)， 也稱它為數(shù)據(jù)減少技術(shù) ( Data Reduction Techniques )。近幾年，有關(guān)這方面的研究取得 了一些進(jìn)展 151617 。1.5 不確定環(huán)境下決策樹(shù)研究不確定環(huán)境下的決策研究一直是一個(gè)熱點(diǎn)，決策樹(shù)技術(shù)就是其中一個(gè)重要的方法之一。前面介紹的決策樹(shù)技術(shù)與模糊集合原理的結(jié)合就是一個(gè)不錯(cuò)的選擇。此外，Z. Eloudi 等人提出了一種基于置信度函數(shù)的決策樹(shù) 18。此算法利用置信度函數(shù)原

10、理來(lái)代表分類問(wèn)題中的 參數(shù)不確定性，在不確定環(huán)境下決策樹(shù)構(gòu)造和不確定環(huán)境下的分類均取得了比較好的效果。 目前正在進(jìn)行決策樹(shù)與專家系統(tǒng)相結(jié)合的研究，以便在不確定環(huán)境下更好地決策。1.6 決策樹(shù)技術(shù)中時(shí)間復(fù)雜度與準(zhǔn)確性之間的矛盾決策樹(shù)技術(shù)與神經(jīng)網(wǎng)絡(luò)技術(shù)相比所具有的最大優(yōu)點(diǎn)就是訓(xùn)練決策樹(shù)的時(shí)間遠(yuǎn)遠(yuǎn)低于訓(xùn) 練神經(jīng)網(wǎng)絡(luò)的時(shí)間。 決策樹(shù)技術(shù)中如何處理時(shí)間復(fù)雜度和分類準(zhǔn)確性之間的矛盾是一個(gè)令人 感興趣的問(wèn)題。到底如何取舍需要具體問(wèn)題具體分析。例如，0.Taner 等人提出的全變量決策樹(shù) ( 0mnivariate Decision Tree ) 19。在分類正確性方面超過(guò)了其他決策樹(shù)方法，卻付 出了需要更多

11、訓(xùn)練時(shí)間的代價(jià)。 隨著微處理器速度越來(lái)越快、 價(jià)錢越來(lái)越便宜， 以及并行計(jì) 算的運(yùn)用，使人們?cè)谧鰶Q定時(shí)擁有比以前更大的自由。1.7 決策樹(shù)技術(shù)的軟件實(shí)現(xiàn)將決策樹(shù)技術(shù)軟件化一直是決策樹(shù)技術(shù)的方向之一。目前市場(chǎng)上的大多數(shù)據(jù)挖掘軟件如SAS等都包含有決策樹(shù)技術(shù)部分。如何開(kāi)發(fā)出功能更加強(qiáng)大、使用更加方便、界面更加友 好的軟件以實(shí)現(xiàn)決策樹(shù)技術(shù)，一直是大家努力的方向。以上這些決策樹(shù)的研究并不是孤立的，它們經(jīng)常相互聯(lián)系、相互結(jié)合。2決策樹(shù)算法實(shí)例在汽車評(píng)價(jià)分類的數(shù)據(jù)庫(kù)中給汽車定義了6個(gè)屬性：（1）購(gòu)買價(jià)格buying，該屬性取值有 4種，分別為vhigh、high、med和low（2）保養(yǎng)維護(hù)費(fèi)用 main

12、t，該屬性取值有 4種，分別為vhigh、high、med和low（3）車門數(shù)量doors，該屬性取值有 4種，分別為2、3、4和5more（4）載人數(shù)量persons，該屬性取值有 3種，分別為2、4和more（5）行李箱容量lug_boot，該屬性取值有 3種，分別為small、med和big（6）安全性safety，該屬性取值有 4種，分別為low、med和high本文采用了完整涵蓋 6個(gè)屬性所有1728（4*4*4*3*3*4 ）種取值組合的數(shù)據(jù)庫(kù)，根據(jù)每 輛汽車各個(gè)屬性的取值組合，消費(fèi)者對(duì)汽車給出4種評(píng)價(jià)，分別為unacc、acc、good和vgood。數(shù)據(jù)庫(kù)來(lái)源：http:/arc

13、/ml/datasets/Car+Evaluation2.1 CLS算法邏輯與實(shí)現(xiàn)用CLS算法生成決策樹(shù)首先要確定6個(gè)屬性的先后順序，即決策樹(shù)每層需要對(duì)哪種屬性進(jìn)行取值分類和判斷。如下圖所示，程序使用者在運(yùn)行算法之前可以在下拉列表中選擇決 策樹(shù)前2層的屬性，其余 4種屬性將按照數(shù)據(jù)庫(kù)中從左至右的默認(rèn)順序依次作為決策樹(shù)之 后4層的屬性。Ch 000 thv first attributm：| pmr.en寸”And th second attribute: safely下圖即為選擇persons和safety作為前2層屬性時(shí)6個(gè)屬性的排列順序：Attribute/

14、Resutt NamepersonssafetybuyingmaintdoorsIug b0atColumn No.572346Count of Values334443Values2lowvhighvhigh2small4medhighhigh3medmorehighmedmed4biglowlow5more附錄1的代碼為生成決策樹(shù)的主要過(guò)程，首先將所有汽車按照第1層屬性的取值進(jìn)行分類，例如按上圖順序按 persons分為3類（2、4和more ）。然后依次進(jìn)行判斷每類汽車 的消費(fèi)者評(píng)價(jià)是否一致，若一致則在該類下生成葉子結(jié)點(diǎn)，例如persons取值為2的汽車均被評(píng)價(jià)為unacc，于是生成如下

15、圖所示的葉子結(jié)點(diǎn)：若該類汽車的消費(fèi)者評(píng)價(jià)不一致，則進(jìn)入決策樹(shù)第2層的生成過(guò)程，將該類汽車按照第2層屬性的取值繼續(xù)細(xì)分，例如 persons取值為4的汽車沒(méi)有一致的消費(fèi)者評(píng)價(jià)，于是 按safety繼續(xù)細(xì)分為3類（low、med和high ）依次進(jìn)行判斷，如下圖所示：persons4safetylowmedhigh根據(jù)這種方法層層推進(jìn)，最終即可生成完整的決策樹(shù)，而每層的生成方法和邏輯與附錄 1的代碼相似，因此不一一敘述。2.2 ID3算法邏輯與實(shí)現(xiàn)用ID3算法生成決策樹(shù)不需要事先確定 6個(gè)屬性的先后順序，而是由附錄 3的代碼在 生成新結(jié)點(diǎn)是計(jì)算每種屬性的信息熵并選擇這個(gè)結(jié)點(diǎn)的屬性，選擇結(jié)點(diǎn)屬性之后

16、和CLS算法一樣進(jìn)行該屬性不同取值的分類和判斷。附錄2的代碼為生成決策樹(shù)的主要過(guò)程，首先計(jì)算各屬性的信息熵并選擇第1層的屬性，例如在汽車評(píng)價(jià)案例中經(jīng)過(guò)計(jì)算選擇safety為第1層屬性，如下圖所示：然后按safety分為3類（low、med和high），依次進(jìn)行判斷每類汽車的消費(fèi)者評(píng)價(jià)是否一致，若一致則在該類下生成葉子結(jié)點(diǎn)，例如safety取值為low的汽車均被評(píng)價(jià)為 unacc，于是生成如下圖所示的葉子結(jié)點(diǎn)：若該類汽車的消費(fèi)者評(píng)價(jià)不一致，則進(jìn)入決策樹(shù)第2層的生成過(guò)程，按該類汽車計(jì)算各屬性的信息熵并選擇結(jié)點(diǎn)屬性，根據(jù)不同取值繼續(xù)細(xì)分并判斷，例如safety取值為med的汽車沒(méi)有一致的消費(fèi)者評(píng)價(jià)，

17、于是計(jì)算并選取persons作為結(jié)點(diǎn)屬性，繼續(xù)細(xì)分為3類（2、4和more ）依次進(jìn)行判斷，如下圖所示：safelymedpersons24more根據(jù)這種方法層層推進(jìn)，最終即可生成完整的決策樹(shù)，而每層的生成方法和邏輯與附錄 1的代碼相似，因此不一一敘述。與CLS算法規(guī)定了每層的結(jié)點(diǎn)屬性不同，在 ID3算法中對(duì)每個(gè)新的結(jié)點(diǎn)都需要計(jì)算各 屬性的信息熵來(lái)選擇屬性，所以某個(gè)結(jié)點(diǎn)按屬性的取值分類后， 下一層的幾個(gè)結(jié)點(diǎn)未必采用 相同的屬性，例如下圖中第 4層的4個(gè)結(jié)點(diǎn)并沒(méi)有選擇同樣的屬性。safetymedpersons4buyingvhighmaimhigh lug bt>otmedmaintl

18、owrnaint2.3 CLS算法與ID3算法效果比較CLS算法的效果根據(jù)屬性順序的不同會(huì)有很大的差異，下表即為根據(jù)不同屬性順序生 成決策樹(shù)的葉子結(jié)點(diǎn)數(shù)：屬性順序葉子結(jié)點(diǎn)數(shù)safety Tpersons t buying t maintT doors t lug boot469persons t safety t buying t maintT doors t lug boot469buying t maint t doors t persons t lug boot t safety965lug boot t maintT buying t doorsT persons t safety10

19、75doors t lug boot t buying TmaintT persons t safety1102可以看到屬性順序?qū)τ谛Ч挠绊懯志薮?，通過(guò)改變順序葉子結(jié)點(diǎn)數(shù)的變化可能超過(guò)1倍。經(jīng)過(guò)多次測(cè)試，用CLS算法生成汽車評(píng)價(jià)決策樹(shù)的最少葉子結(jié)點(diǎn)數(shù)為469個(gè)，而ID3算法生成的決策樹(shù)只有296個(gè)葉子結(jié)點(diǎn)。由于ID3算法選取結(jié)點(diǎn)屬性的方法更加靈活、合理，從直觀上判斷會(huì)比 CLS算法效果更佳，所以這樣的結(jié)果差異也在情理之中。3總結(jié)本文實(shí)例是用 VBA語(yǔ)言編程，界面為 Excel 2003 （具體見(jiàn)電子版），語(yǔ)言和界面不夠 專業(yè)，所以實(shí)現(xiàn)速度也沒(méi)有達(dá)到最理想，最快的42 ''最

20、慢的4 '以上。進(jìn)一步工作會(huì)在編程語(yǔ)言上改進(jìn)，以實(shí)現(xiàn)最佳效果。附錄 附錄 1 CLS 算法生成決策樹(shù)的過(guò)程Private Function DECISIONTREE(LAYER_COUNT As Integer, ROW_COUNT As Integer)Dim LAYER_RANGE As Range, TREE_RANGE As Range, RANGE2 As Range, ROW2 As Integer, I As Integer, J As Integer, K As Integer, X As IntegerDim VALUE1 As String, COLUMN1 As

21、Integer, CLASS As String, CLASS_COLUMN As Integer, DECISION As String Set LAYER_RANGE = Range("K5")CLASS_COLUMN = LAYER_COUNT + 2Set TREE_RANGE = Range("K16")TREE_RANGE.Cells(1, 1) = LAYER_RANGE.Cells(1, 1)BORDER_THIN (TREE_RANGE.Cells(1, 1)COLUMN1 = LAYER_RANGE.Cells(2, 1)ROW2 =

22、 -1For I = 1 To LAYER_RANGE.Cells(3, 1)VALUE1 = LAYER_RANGE.Cells(3 + I, 1)K = 0For J = 2 To ROW_COUNTIf Cells(J, COLUMN1) = VALUE1 ThenCLASS = Cells(J, CLASS_COLUMN)K = J Exit ForEnd IfNextX = 1For J = K To ROW_COUNTIf Cells(J, COLUMN1) = VALUE1 And Not Cells(J, CLASS_COLUMN) = CLASS ThenX = 0 Exit

23、 ForEnd IfNextIf X = 1 ThenROW2 = ROW2 + 2TREE_RANGE.Cells(ROW2, 2) = VALUE1 TREE_RANGE.Cells(ROW2, 3) = CLASSCall BORDER_MEDIUM(TREE_RANGE.Cells(ROW2, 3)Call CONECTION(TREE_RANGE.Cells(1, 1), TREE_RANGE.Cells(ROW2, 3)ElseIf X = 0 ThenROW2 = ROW2 + 2TREE_RANGE.Cells(ROW2, 2) = VALUE1TREE_RANGE.Cells

24、(ROW2, 3) = LAYER_RANGE.Cells(1, 2)Call BORDER_THIN(TREE_RANGE.Cells(ROW2, 3)Call CONECTION(TREE_RANGE.Cells(1, 1), TREE_RANGE.Cells(ROW2, 3)Set RANGE2 = TREE_RANGE.Cells(ROW2, 3)ROW2 = ROW2 - 1 + LAYER2(RANGE2, VALUE1, LAYER_RANGE, CLASS_COLUMN, ROW_COUNT) End IfNextRange("K13") = (ROW2 +

25、 1) / 2End Function附錄 2 ID3 算法生成決策樹(shù)的過(guò)程Private Function DECISIONTREE(ROW_COUNT As Integer)AsAsDim LAYER_RANGE As Range, TREE_RANGE As Range, RANGE2 As Range, ROW2 As Integer, COLUMN1 Integer, ATTRIBUTE1 As Integer, ATTRIBUTE2 As Integer, VALUE1 As String, CLASS As String, CLASS_COLUMN IntegerDim I As

26、 Integer, J As Integer, K As Integer, L As Integer, N As Integer, M As IntegerSet LAYER_RANGE = Range("K5")Set TREE_RANGE = Range("K16")CLASS_COLUMN = 8M = LAYER_RANGE.Cells(3, 7)ATTRIBUTE1 = CHOOSE_ATTRIBUTE(7, CLASS_COLUMN, ROW_COUNT, M, LAYER_RANGE)LAYER_RANGE.Cells(8, ATTRIBU

27、TE1) = 1TREE_RANGE.Cells(1, 1) = LAYER_RANGE.Cells(1, ATTRIBUTE1)BORDER_THIN (TREE_RANGE.Cells(1, 1)COLUMN1 = LAYER_RANGE.Cells(2, ATTRIBUTE1)ROW2 = -1For I = 1 To LAYER_RANGE.Cells(3, ATTRIBUTE1)VALUE1 = LAYER_RANGE.Cells(3 + I, ATTRIBUTE1)K = 0For J = 2 To ROW_COUNTIf Cells(J, COLUMN1) = VALUE1 Th

28、enCLASS = Cells(J, CLASS_COLUMN)K = JREF.Cells(J, ATTRIBUTE1) = 1ElseREF.Cells(J, ATTRIBUTE1) = 0End IfNextX = 1For J = 2 To ROW_COUNTIf Cells(J, COLUMN1) = VALUE1 And Not Cells(J, CLASS_COLUMN) = CLASS ThenX = 0 Exit ForEnd IfNextIf X = 1 ThenROW2 = ROW2 + 2TREE_RANGE.Cells(ROW2, 2) = VALUE1TREE_RA

29、NGE.Cells(ROW2, 3) = CLASSCall BORDER_MEDIUM(TREE_RANGE.Cells(ROW2, 3)Call CONECTION(TREE_RANGE.Cells(1, 1), TREE_RANGE.Cells(ROW2, 3)ElseIf X = 0 ThenROW2 = ROW2 + 2TREE_RANGE.Cells(ROW2, 2) = VALUE1M,ATTRIBUTE2 = CHOOSE_ATTRIBUTE(ATTRIBUTE1, CLASS_COLUMN, ROW_COUNT, LAYER_RANGE)TREE_RANGE.Cells(RO

30、W2, 3) = LAYER_RANGE.Cells(1, ATTRIBUTE2)Call BORDER_THIN(TREE_RANGE.Cells(ROW2, 3)Call CONECTION(TREE_RANGE.Cells(1, 1), TREE_RANGE.Cells(ROW2, 3)Set RANGE2 = TREE_RANGE.Cells(ROW2, 3)ROW2 = ROW2 - 1 + LAYER2(RANGE2, ATTRIBUTE1, ATTRIBUTE2, LAYER_RANGE, CLASS_COLUMN, ROW_COUNT, M)End IfNextLAYER_RA

31、NGE.Cells(8, ATTRIBUTE1) = EmptyRange("K13") = (ROW2 + 1) / 2End Function附錄 3 ID3 算法計(jì)算信息熵和選擇結(jié)點(diǎn)屬性的過(guò)程Private Function ENTROPY_CALCULATION(ATT_NO As Integer, PREATT As Integer, CLASS_COLUMN As Integer, ROW_COUNT As Integer, M As Integer, LAYER_RANGE As Range) As DoubleDim ATT_C As Integer, PR

32、_ATT() As Double, COUNT_ATT As Integer, PR_CLA() As Double, COUNT_CLA As Integer, ENTROPY_CLA() As Double, TOTAL As Integer, RN As Integer, AN As Integer, CN As IntegerATT_C = LAYER_RANGE.Cells(3, ATT_NO)ENTROPY_CALCULATION = 0TOTAL = 0For RN = 2 To ROW_COUNTIf REF.Cells(RN, PREATT) = 1 ThenTOTAL =

33、TOTAL + 1End IfNextReDim PR_ATT(ATT_C) As DoubleFor AN = 1 To ATT_CCOUNT_ATT = 0ReDim Preserve ENTROPY_CLA(AN) As DoubleReDim PR_CLA(M) As DoubleENTROPY_CLA(AN) = 0For RN = 2 To ROW_COUNTIf REF.Cells(RN, PREATT) = 1 And Cells(RN, ATT_NO + 1) = LAYER_RANGE.Cells(3 + AN, ATT_NO) ThenCOUNT_ATT = COUNT_

34、ATT + 1 REF.Cells(RN, ATT_NO) = 1ElseREF.Cells(RN, ATT_NO) = 0End IfNextPR_ATT(AN) = COUNT_ATT / TOTALFor CN = 1 To MCOUNT_CLA = 0For RN = 2 To ROW_COUNTIf REF.Cells(RN, ATT_NO) = 1 And Cells(RN, CLASS_COLUMN) = LAYER_RANGE.Cells(3 + CN, 7)ThenCOUNT_CLA = COUNT_CLA + 1End IfNextPR_CLA(CN) = COUNT_CL

35、A / COUNT_ATTIf PR_CLA(CN) > 0 ThenENTROPY_CLA(AN) = ENTROPY_CLA(AN) - PR_CLA(CN) * Log(PR_CLA(CN) / Log(2)End IfNextENTROPY_CALCULATION = ENTROPY_CALCULATION + PR_ATT(AN) * ENTROPY_CLA(AN)NextEnd FunctionPrivate Function CHOOSE_ATTRIBUTE(PREATT As Integer, CLASS_COLUMN As Integer, ROW_COUNT As I

36、nteger,M As Integer, LAYER_RANGE As Range) As IntegerDim ENTROPY_ACC As Double, ENTROPY_TEMP As Double, ATT_NO As IntegerENTROPY_ACC = 2CHOOSE_ATTRIBUTE = 0For ATT_NO = 1 To 6If Not LAYER_RANGE(8, ATT_NO) = 1 ThenM,ENTROPY_TEMP = ENTROPY_CALCULATION(ATT_NO, PREATT, CLASS_COLUMN, ROW_COUNT, LAYER_RAN

37、GE)If ENTROPY_TEMP < ENTROPY_ACC ThenENTROPY_ACC = ENTROPY_TEMPCHOOSE_ATTRIBUTE = ATT_NOEnd IfEnd IfNextEnd Function參考文獻(xiàn)：1 Boz O. Extracting decision trees from trained neural net-worksC. Edmonton, Alberta, Canada: Proc of the English ACM SIGKDD International Conference on Knowledge Discovery and

38、 Data Mining, 2002.2 Sethi L. Entropy nets: from decision trees to neural net-worksJ. Proc of IEEE,1990,78 (10) :1605-1613.3 Olaru C, Wehenkel L. A complete fuzzy decision tree techniqueJ. Fuzzy Sets and Systems,2003,138(2) :221-254.4 Dong M, Kothari R. Look-ahead based fuzzy decision tree induction

39、 J. IEEE Transactions on Fuzzy Systems, 2002, 9 (3) :461-468.5 Cantu -Paz E, Kamath C. Inducing oblique decision trees with evolutionary AlgorithmsJ . IEEE Transactions on Evolutionary Computation, 2003, 7 (1) : 54-68.6 Papagelis A, Kalles D. Breeding decision trees using evolutionary techniquesC. U

40、SA: Proceedings of ICML ' 01U,SA, 2001.7 Papagelis A, Kalles D. GA tree: genetically evolved decision treesC . USA: Proceedings of ICTAIP00,2000.8 Tur G, Guvenir H A. Decision tree induction using genetic programming C. Ankara, Turkish: Proceedings of the Fifth Turkish Symposium on Artificial In

41、telligence and Neural Networks,1996.9 Eggermont J. Evolving fuzzy decision trees with genetic programming and clusteringC. Milan, Italy: Proceedings of the 4th European Conference on Genetic Programming,2001.10 Stone P, VeIoso M. Using decision tree confidence factors for muItiagent control C . Minnesota, USA: Proceedings of the 2nd International Conference on Autonomous Agents, 1998.11 Stone P, VeIoso M. M