【文章內(nèi)容簡介】 th” AND student = “ yes” THEN Class=“ Y” 海南師范大學(xué)本科畢業(yè)論文 8 IF age=“ old” AND creditrating=“ fair” THEN Class=“ Y” IF age=“ old” AND creditrating=“ excellent” THEN Class=“ N” 例子二： 這里我們通過考察?？谀承?學(xué)生的學(xué)習狀況為例 ,來展示 ID3 算法的實際流程。此例假定要按某校學(xué)生學(xué)習成績好壞這個概念對一個集合進行分類 ,該集合中用來描述學(xué)生的屬性有性格、 父母教育程度 和性別。性格的取 值為外向、內(nèi)向。 父母教育程度取值為 良好 、中等和 差。性別的取值為男 生 、 女生 。例子集中共有 12 名學(xué)生 ,如表 2所示。在類別一欄 ,將正例即“學(xué)習成績好”的學(xué)生用“ 好 ” 標出 ,反例即“學(xué)生成績差”的學(xué)生用“ 差 ”標出。 表 2 某學(xué)校 學(xué)生 的例子集 性格 父母教育程度 性別 類別 內(nèi)向 外向 外向 內(nèi)向 外向 內(nèi)向 外向 外向 外向 內(nèi)向 內(nèi)向 內(nèi)向 良 良 中 差 中 良 差 差 良 中 中 差 女生 男生 女生 女生 男生 男生 女生 男生 女生 女生 男生 男生 好 好 差 差 好 好 好 差 好 差 差 差 這些例子一開始全部包含在根結(jié)點中 ,為了找出當前的最佳劃分屬性 ,先須根據(jù) 信息論中的 公式計算訓(xùn)練 實 例集 Es的熵值。則根節(jié)點的熵值為 : 6 6 6 6( ) l o g 2 l o g 21 2 6 6 1 2 6 6E n tr o p y E s ? ? ??? = 1 下面分別計算例子集中各個屬性的信息贏取值。對屬性“性格”來說 ,分外向和內(nèi)向兩個分支。當 v =“外向”時 ,有 4 名“外向”小學(xué)生是“學(xué)習成績好”的 ,有 2 名“外向”小學(xué)生是“學(xué)習成績差”的。因此 , 4 4 2 2( ) l o g 2 l o g 2 0 . 9 1 8 36 2 4 6 2 4sE n tr o p y E ? ? ? ???性 格 , 外 向 當 v =“內(nèi)向”時 ,有 2 名“內(nèi)向”小學(xué)生是“學(xué) 習成績好”的 ,有 4 名“內(nèi)向”小學(xué)生是“學(xué)海南師范大學(xué)本科畢業(yè)論文 9 習成績差”的。因此 , 4 4 2 2( ) l o g 2 l o g 2 0 . 9 1 8 36 2 4 6 2 4sE n tr o p y E ? ? ? ???性 格 , 內(nèi) 向 所以根據(jù)“性格”屬性來進行例子集分類的信息贏取值為 : Gain(Es,性格 )=Entropy(Es)Entropy(Esv,格 )= 111 ( * 0 .9 1 8 3 + * 0 .9 1 8 3 ) = 0 .0 8 1 722 同理 ,對“ 父母教育程度 ”來說 :Gain(Es, 父母教育程度 )= 。 對“性別”來說 :Gain( Es,性別 ) = 0 。 因為 Gain ( Es ,性別 ) Gain ( Es ,性格 ) Gain ( Es , 父母教育程度 ) 可以看出以“ 父母教育程度 ”這個屬性進行例子集分類的信息贏取值最大 ,于是“ 父母教育程度 ”就被選為用于劃分的屬性 ,得到如下圖所示的決策樹。 父 母 教 育 程 度良差中內(nèi) 向 ， 良 ， 女 生 ： 好外 向 ， 良 ， 男 生 ： 好內(nèi) 向 ， 良 ， 男 生 ： 好外 向 ， 良 ， 女 生 ： 好內(nèi) 向 ， 中 ， 女 生 ： 差外 向 ， 中 ， 男 生 ： 好內(nèi) 向 ， 中 ， 男 生 ： 差外 向 ， 中 ， 女 生 ： 差內(nèi) 向 ， 差 ， 女 生 ： 差外 向 ， 差 ， 女 生 ： 好內(nèi) 向 ， 差 ， 男 生 ： 差外 向 ， 差 ， 男 生 ： 差 按“ 父母教育程度 ”劃分后的決策樹 現(xiàn)在必須根據(jù)所提供的信息進一步分析“ 父母教育程度 ”為“中”或“差”的小學(xué)生的“學(xué)習成績好壞” ,因此必須對“中”和“差”兩個分支的實例組成的例子集 (共 8個例子 ) 重復(fù)上述計算過程。這里簡化計算過程 ,算出 :Gain(Es,性格 )= 和 Gain(Es,性別 ) =。 因為 Gain ( Es ,性別 ) Gain ( Es ,性格 ) ,所以用屬性“性格”作第二步劃分 ,于是得到如下圖所示的決策樹。 父 母 教 育 程 度良差中內(nèi) 向 ， 良 ， 女 生 ： 好外 向 ， 良 ， 男 生 ： 好內(nèi) 向 ， 良 ， 男 生 ： 好外 向 ， 良 ， 女 生 ： 好內(nèi) 向 ， 中 ， 女 生 ： 差內(nèi) 向 ， 中 ， 男 生 ： 差內(nèi) 向 ， 差 ， 女 生 ： 差內(nèi) 向 ， 差 ， 男 生 ： 差性 格內(nèi) 向外 向外 向 ， 中 ， 男 生 ： 好外 向 ， 中 ， 女 生 ： 差性 格內(nèi) 向外 向外 向 ， 差 ， 女 生 ： 好外 向 ， 差 ， 男 生 ： 差 海南師范大學(xué)本科畢業(yè)論文 10 按“性格”作第二次劃分后的決策樹 現(xiàn)在只有“ 父母教育程度 ”為“中”和“差”的“外向”小學(xué)生還沒有明確類別 ,它們要用屬性“性別”來進一步劃分。最終得到的決策樹如下圖所示。 父 母 教 育 程 度良差中內(nèi) 向 ， 良 ， 女 生 ： 好外 向 ， 良 ， 男 生 ： 好內(nèi) 向 ， 良 ， 男 生 ： 好外 向 ， 良 ， 女 生 ： 好內(nèi) 向 ， 中 ， 女 生 ： 差內(nèi) 向 ， 中 ， 男 生 ： 差內(nèi) 向 ， 差 ， 女 生 ： 差內(nèi) 向 ， 差 ， 男 生 ： 差性 格內(nèi) 向外 向{ 外 向 ， 中 ， 女 生 ： 差 }性 格內(nèi) 向外 向{ 外 向 ， 差 ， 男 生 ： 差 }性 別女 生男 生{ 外 向 ， 中 ， 男 生 ： 好 }{ 外 向 ， 差 ， 女 生 ： 好 }性 別男 生女 生 最終得到的決策樹 IF 父母教 育程度 =“良” THEN 學(xué)習成績 =“好” IF 父母教育程度 =“中” AND 性格 =“內(nèi)向” THEN學(xué)習成績 =“差” IF 父母教育程度 =“差” AND 性格 =“內(nèi)向” THEN學(xué)習成績 =“差” IF 父母教育程度 =“中” AND 性格 =“外向” AND 性別 =“女生” THEN學(xué)習成績 =“差” IF 父母教育程度 =“中” AND 性格 =“外向” AND 性別 =“男生” THEN學(xué)習成績 =“好” IF 父母教育程度 =“差” AND 性格 =“外向” AND 性別 =“女生” THEN學(xué)習成績 =“好” IF 父母教育程度 =“差” AND 性格 =“外向” AND 性別 =“男生” THEN學(xué)習成績 =“差” 但是 不能保證 ID3算法對任何問題總能做出最佳選擇 ,只能說它在一般情況下能夠找出最優(yōu)決策樹。 這是 ID3算法的最大缺點。 算法的優(yōu)缺點 這里對 ID3算法作一些總結(jié) :ID3通過不 斷的循環(huán)處理 ,逐步求精決策樹 ,直到找到一個完全正確的決策樹。 ID3算法構(gòu)造的決策樹是從頂向下歸納形成了一組類似 IF ?THEN的規(guī)則。其最原始的程序只是用來區(qū)分象棋中的走步 ,所以區(qū)分的類別只有兩種 T或 F ,其屬性值也是一些離散有限的值 ,而今 ID3算法已發(fā)展到允許多于兩個類別 ,而其屬性值可以是整數(shù)或?qū)崝?shù)。下面歸納總結(jié)出 ID3算法的優(yōu)缺點如下 : 優(yōu)點 :搜索空間是完全的假設(shè)空間 ,目標函數(shù)必在搜索空間中 ,不存在無解的危險 。全盤使用訓(xùn)海南師范大學(xué)本科畢業(yè)論文 11 練數(shù)據(jù) ,而不是像候選剪除算法一個一個地考慮訓(xùn)練例。這樣做的優(yōu)點是可以利用全部訓(xùn)練例的 統(tǒng)計性質(zhì)進行決策 ,從而抵抗噪音。 缺點 :搜索中只維持一個解 ,不能像候選剪除算法那樣返回所有可能的與練例集一致的假設(shè) ,并優(yōu)化地查詢新例以獲得收斂于目標函數(shù)的解 。其搜索無回溯它可能收斂于局部最優(yōu)解而丟失全局最優(yōu)解 ,因為一個一個地考慮訓(xùn)練例 ,不容易象剪除算法那樣使用新例步進式地改進決策樹。 算法的發(fā)展 ID3算法在實際應(yīng)用中解決了許多問題 ,對于非增量式學(xué)習任務(wù) , ID3算法常常是建立決策樹的很好的選擇。但對于增量式學(xué)習任務(wù)來說 ,由于 ID3不能增量地接受訓(xùn)練例 ,這就使得每增加一次實例都必須拋 棄原有決策樹 ,重新構(gòu)造新的決策樹 ,造成了極大的開銷。于是 ID3 算法被 Quinlan[1]自己擴充為 ,。在 ,每個結(jié)點都保存了可用于計算 E值的屬性的信息 ,這些信息由屬性的每個取值所對應(yīng)的正例、反例計數(shù)組成。根據(jù)放在結(jié)點的信息 ,就可以判斷出哪個屬性的訓(xùn)練例集 Es值最小 ,從而確定當前用哪一個屬性來進行劃分。 :基于訓(xùn)練例自身的性能估計。當然訓(xùn)練例進行估計很可能產(chǎn)生偏向于規(guī)則的結(jié)果 ,為了克服這一點 ,。它采用的具體方法是 :計算規(guī)則對其使用的各個訓(xùn)練例分類的精度 a ,然后計算這個精度的二項分布的標準差 s ,最后對給定信任度 (95 %)， 取下界 ()為該規(guī)則的性能度量 pa； 在有大量數(shù)據(jù)的情況下 ,s接近于 0,pa接近于 a ； 隨著數(shù)據(jù)量的減少 ,pa與 a的差別將會增大。 A 的各種取值賦以概率 ,具有未知屬性 A 值的實例 x 按概率值分為大小不等的碎片 ,沿相應(yīng)屬性 A 值的分支向樹的下方分布 ,實例的碎片將用于計算信息贏取。這個實例碎片在學(xué)習后 ,還可以用 來對屬性值不全的新實例進行分類。 下面就 。 算法簡介 ID3的基礎(chǔ)上改進而成的， 它繼承了 ID3的全部優(yōu)點， 更好地修正了 ID3的剪枝算法并對高分支屬性、數(shù)值型屬性和含空值屬性地整理有了系統(tǒng)地描述。 例如 “窗口”( Windows ) 的概念 ,先從所有的事例中選取一部分用做構(gòu)造決策樹 ,再利用剩余的事例測試決策樹并對它進行調(diào)整。 ,它還能對屬性的取值集合進行等價類劃分 ,劃分在同一類的屬性值在屬性 值判斷時將走到同一分支上。再加上 ,實現(xiàn)高效 ,結(jié)果可靠 ,使 。但是 CN 如下 不足 之處 : 海南師范大學(xué)本科畢業(yè)論文 12 第一 , ,在構(gòu)造樹的內(nèi)部結(jié)點的時候是局部最優(yōu)的搜索方式。所以它所得到的最終結(jié)果盡管有很高的準確性 ,仍然 得 不到全局最優(yōu)的結(jié)果。 第二 ,在 ,而對樹的深度 ,結(jié)點的個數(shù)等不進行考慮 ,而樹平均深度直接對應(yīng)著決策樹的預(yù)測速度 ,樹的結(jié)點個數(shù)則代表樹的規(guī)模。 第三 ,一邊構(gòu)造決策樹 ,一邊進行評 價 ,決策樹構(gòu)造出來之后 ,很難再調(diào)整樹的結(jié)構(gòu)和內(nèi)容 ,決策樹性能的改善十分困難。 第四 , ,沒有一種使用啟發(fā)搜索的機制 ,分組時的效率較低。 GA(Geic Algorithm) 遺傳算法是一種通用搜索算法。它通過模擬自然界進化的過程來演化出解決問題的較優(yōu)方法。它把一些解決方案用一定的方式來表示 ,放在一起稱為群體 (population) 。每一個方案的優(yōu)劣程度即為適應(yīng)性 (fit2ness),根據(jù)自然界進化的“優(yōu)勝劣汰”的原則 ,逐步產(chǎn)生出它們的后代 ,使后 代具有更強的適應(yīng)性。這樣不斷演化下去 ,就能得到更優(yōu)的解決方案。它具有思想簡明、健壯性好等特點。在工農(nóng)業(yè)、經(jīng)濟政治、科研方面應(yīng)用極為廣泛。在計算機科學(xué)領(lǐng)域中的機器學(xué)習領(lǐng)域更是大有用武之地。 群體搜索策略和個體之間的信息交換是遺傳算法的兩大特點 ,主要表現(xiàn)在全局最優(yōu)性和潛在的并行性。 ,那么是不是能用遺傳算法的思想能夠得到解決呢 ,回答是肯定的。雖然遺傳算法的進發(fā)結(jié)果并不能保證得到理論意義上的最佳的決策樹 ,但是它提供了一種試探的過程。由于適者生存的特點 ,使得適應(yīng)性較優(yōu)的 決策樹能盡量保留 ,又由于它提供了對決策樹的調(diào)整和重新組合的機制 ,使得有更優(yōu)適應(yīng)性的決策樹在進發(fā)過程中出現(xiàn)。那么如何應(yīng)用遺傳算法 ,如何基于決策樹的結(jié)構(gòu)和性質(zhì)定義遺傳算子呢 ? 遺傳算子主要有三種 :復(fù)制 (reproduction) 、重組 (crossover) 、算子和變異 (mutation) 算子。一般的算子都是對特征串進行操作的。針對決策樹的結(jié)構(gòu)和特性 ,我們定義遺傳算子 :首先定義適應(yīng)函數(shù) (fitness function) 。遺傳算法是一個探索過程 ,它對樹的評價是在樹完全作成以后進行的 ,可以將樹的深度、結(jié)點數(shù) 等因素都考慮在內(nèi)。 復(fù)制算子的定義與常用的復(fù)制算子的定義一致。重組算子的定義就要用到?jīng)Q策樹結(jié)構(gòu)特點。我們有以下幾種重組方式 : (1) 用后代結(jié)點代替祖先結(jié)點 ,類似于書的剪枝操作。 (2) 同一棵樹的兩個結(jié)點互相交換。 (3) 兩個樹之間結(jié)點交換 ,這里所說的結(jié)點交換就是交換以這些結(jié)點為根的子樹。 變異是產(chǎn)生全局最優(yōu)的重要原因 ,盡管大多數(shù)的變異不能產(chǎn)生良好的效果