【文章內(nèi)容簡介】 選剪除算法那樣返回所有可能的與練例集一致的假設(shè),并優(yōu)化地查詢新例以獲得收斂于目標函數(shù)的解。其搜索無回溯它可能收斂于局部最優(yōu)解而丟失全局最優(yōu)解,因為一個一個地考慮訓練例,不容易象剪除算法那樣使用新例步進式地改進決策樹。 算法的發(fā)展ID3算法在實際應用中解決了許多問題,對于非增量式學習任務(wù), ID3算法常常是建立決策樹的很好的選擇。但對于增量式學習任務(wù)來說,由于ID3不能增量地接受訓練例,這就使得每增加一次實例都必須拋棄原有決策樹,重新構(gòu)造新的決策樹,造成了極大的開銷。于是ID3 算法被Quinlan[1],。,每個結(jié)點都保存了可用于計算E值的屬性的信息,這些信息由屬性的每個取值所對應的正例、反例計數(shù)組成。根據(jù)放在結(jié)點的信息,就可以判斷出哪個屬性的訓練例集Es值最小,從而確定當前用哪一個屬性來進行劃分。:基于訓練例自身的性能估計。當然訓練例進行估計很可能產(chǎn)生偏向于規(guī)則的結(jié)果,為了克服這一點,。它采用的具體方法是:計算規(guī)則對其使用的各個訓練例分類的精度a ,然后計算這個精度的二項分布的標準差s ,最后對給定信任度(95 %)，取下界()為該規(guī)則的性能度量pa；在有大量數(shù)據(jù)的情況下,s接近于0,pa接近于a ；隨著數(shù)據(jù)量的減少,pa與a的差別將會增大。 的各種取值賦以概率,具有未知屬性A 值的實例x 按概率值分為大小不等的碎片,沿相應屬性A 值的分支向樹的下方分布,實例的碎片將用于計算信息贏取。這個實例碎片在學習后,還可以用來對屬性值不全的新實例進行分類。，它繼承了ID3的全部優(yōu)點，更好地修正了ID3的剪枝算法并對高分支屬性、數(shù)值型屬性和含空值屬性地整理有了系統(tǒng)地描述。“窗口”( Windows ) 的概念,先從所有的事例中選取一部分用做構(gòu)造決策樹,再利用剩余的事例測試決策樹并對它進行調(diào)整。,它還能對屬性的取值集合進行等價類劃分,劃分在同一類的屬性值在屬性值判斷時將走到同一分支上。,實現(xiàn)高效,結(jié)果可靠,。但是CN :第一, ,在構(gòu)造樹的內(nèi)部結(jié)點的時候是局部最優(yōu)的搜索方式。所以它所得到的最終結(jié)果盡管有很高的準確性,仍然得不到全局最優(yōu)的結(jié)果。第二,而對樹的深度,結(jié)點的個數(shù)等不進行考慮,而樹平均深度直接對應著決策樹的預測速度,樹的結(jié)點個數(shù)則代表樹的規(guī)模。第三,一邊構(gòu)造決策樹,一邊進行評價,決策樹構(gòu)造出來之后,很難再調(diào)整樹的結(jié)構(gòu)和內(nèi)容,決策樹性能的改善十分困難。第四, ,沒有一種使用啟發(fā)搜索的機制,分組時的效率較低。(Genetic Algorithm)遺傳算法是一種通用搜索算法。它通過模擬自然界進化的過程來演化出解決問題的較優(yōu)方法。它把一些解決方案用一定的方式來表示,放在一起稱為群體(population) 。每一個方案的優(yōu)劣程度即為適應性(fit2ness),根據(jù)自然界進化的“優(yōu)勝劣汰”的原則,逐步產(chǎn)生出它們的后代,使后代具有更強的適應性。這樣不斷演化下去,就能得到更優(yōu)的解決方案。它具有思想簡明、健壯性好等特點。在工農(nóng)業(yè)、經(jīng)濟政治、科研方面應用極為廣泛。在計算機科學領(lǐng)域中的機器學習領(lǐng)域更是大有用武之地。群體搜索策略和個體之間的信息交換是遺傳算法的兩大特點,主要表現(xiàn)在全局最優(yōu)性和潛在的并行性。,那么是不是能用遺傳算法的思想能夠得到解決呢,回答是肯定的。雖然遺傳算法的進發(fā)結(jié)果并不能保證得到理論意義上的最佳的決策樹,但是它提供了一種試探的過程。由于適者生存的特點,使得適應性較優(yōu)的決策樹能盡量保留,又由于它提供了對決策樹的調(diào)整和重新組合的機制,使得有更優(yōu)適應性的決策樹在進發(fā)過程中出現(xiàn)。那么如何應用遺傳算法,如何基于決策樹的結(jié)構(gòu)和性質(zhì)定義遺傳算子呢?遺傳算子主要有三種:復制(reproduction) 、重組(crossover) 、算子和變異(mutation) 算子。一般的算子都是對特征串進行操作的。針對決策樹的結(jié)構(gòu)和特性,我們定義遺傳算子:首先定義適應函數(shù)(fitness function) 。遺傳算法是一個探索過程,它對樹的評價是在樹完全作成以后進行的,可以將樹的深度、結(jié)點數(shù)等因素都考慮在內(nèi)。復制算子的定義與常用的復制算子的定義一致。重組算子的定義就要用到?jīng)Q策樹結(jié)構(gòu)特點。我們有以下幾種重組方式: (1) 用后代結(jié)點代替祖先結(jié)點,類似于書的剪枝操作。(2) 同一棵樹的兩個結(jié)點互相交換。(3) 兩個樹之間結(jié)點交換,這里所說的結(jié)點交換就是交換以這些結(jié)點為根的子樹。變異是產(chǎn)生全局最優(yōu)的重要原因,盡管大多數(shù)的變異不能產(chǎn)生良好的效果,對于決策樹,我們定義的變異算子是改變樹的結(jié)構(gòu)或者改變樹中結(jié)點內(nèi)的信息。針對內(nèi)部結(jié)點和葉節(jié)點,屬性值的分組與否這些不同情況,變異的處理是不一樣的。對于內(nèi)部結(jié)點內(nèi),變異操作可能產(chǎn)生下面的結(jié)果:(1) 改變結(jié)點上判斷的屬性。(2) 改變屬性值的分組情況。(3) 改變該結(jié)點下的子樹的分支情況,改變屬性值與分支子樹的對應。(4) 改變該結(jié)點的分支數(shù)。這樣經(jīng)過重組、變異算子運算得到的新的決策樹需要進行結(jié)構(gòu)上的完整性和一致性處理。調(diào)整變異結(jié)點及其子結(jié)點的樹結(jié)構(gòu)使之為一棵完整的正確的決策樹。去除從樹根到葉節(jié)點路徑上重復的屬性判斷等。決策樹的構(gòu)造分為以下幾步:(1) 第一代群體的產(chǎn)生；(2) 產(chǎn)生下一代；(3) 產(chǎn)生最優(yōu)決策樹。[1]以上討論了一些決策樹構(gòu)造算法，并且對這些算法的優(yōu)缺點進行了分析。下面，給出評價決策樹的一些標準。1．過學習在由決策樹學習的過程中，我們必須在一組假設(shè)中選擇一個，使得它與訓練實例集相匹配。我們已經(jīng)看到不可能在沒有任何偏置（bias）的情況下學習。如果預先字段所要學習的函數(shù)屬于整個假設(shè)空間中一個很小子集，那么即使在訓練實例不完整的情況下，我們也有可能從訓練實例集喪鐘學習有用的假設(shè)，來使得它能夠?qū)ξ粗膶嵗M行正確分類。即使如此，我們還是希望有一個大的訓練實例集。因為訓練實例集越大，關(guān)于分類的信息越多。在這種情況下，即使我們隨機地從與訓練實例集相一致的假設(shè)集中選擇一個，它也能對未知實例的分類進行預測。相反，即使在有偏置的情況下，如果訓練實例集與整個假設(shè)空間相比過小，仍有過多的與訓練實例相一致的假設(shè)供我們選擇，我們做出假設(shè)的泛化能力將很差。當有過多的假設(shè)與訓練實例集相一致的時候，則成為過學習。過學習是所有機器學習都要考慮的問題。過學習將導致我們所做出的假設(shè)泛化能力過差。所以，也可以如下定義過學習。假設(shè)h對所有的訓練實例分類的錯誤率為，對整個實例空間D分類的錯誤率為。如果存在另一個假設(shè)使得：并且 一般將成為重替換（resubstitution）錯誤率，在本書中將其簡記為r錯誤率。而在此一般將在測試集中的錯誤率成為錯誤。Cohen和Jensen提出了一個有用的理論來解釋為何會出現(xiàn)過學習的情況。他們提出，當一個算法過高估計增加樹的復雜性對于分類的正確性的貢獻，那么就會出現(xiàn)過學習現(xiàn)象。主要有三種原因使得算法過高估計這些貢獻：（1）檢測模型的數(shù)目：算法檢測模型數(shù)目與出現(xiàn)過學習的可能性是正相關(guān)的。（2）不同的正確性估計：小的訓練實例集更不可能代表數(shù)據(jù)的內(nèi)在分布，更有可能產(chǎn)生過學習的現(xiàn)象。而大一些的訓練實例集產(chǎn)生過學習問題的可能性更小。（3）選擇最優(yōu)樹：通過極大化某個特定評價函數(shù)來選擇最優(yōu)決策樹增加了過學習的可能性。Cohen和Jensen利用事后剪枝的方法驗證了他們的理論。2．有效性最為直接的估計一棵決策樹在測試實例集合上的性能的方法是，將它在測試實例集合上進行實際測試，這樣就可以選中在測試集合中表現(xiàn)最好的一棵決策樹。但是這種方法等價于在測試實例集中訓練決策樹，這在大多數(shù)情況下是不現(xiàn)實的。所以一般并不采用這種方法，而是采取用訓練實例集本身來估計訓練算法的有效性。一種最簡便的方法是用訓練實例集的一部分（例如3/4的訓練實例）對決策樹進行訓練，而用另外一部分（例如1/4的訓練實例）對決策樹檢測其有效性。但是，這樣做將會減小訓練實例空間，而增大過學習的可能性，所以這種方法也不可取。3．交叉有效性在此方法中，我們將訓練實例集T分為互不相交且大小相等的k個子集，...。對于任意子集，用T訓練決策樹，之后用對生成的決策樹進行測試，得到錯誤率，然后估計整個算法的錯誤率：e=可以看出隨著k的增加，所生成的樹的數(shù)目也隨之增加，算法的復雜度也會變大。4．余一有效性（leaveoneout validation）這種有效性的度量與交叉有效性類似，不同之處在于將每個的大小定為1。假設(shè)|T|=n，則錯誤率為：e=顯然，這種有效性測量算法的復雜度過高，但是它的準確程度也是最高的。5．決策樹的復雜程度決策樹的復雜程度也是度量決策樹學習效果的一個重要標準。對于給定的描述語言，如果決策樹是單變量（univariate）的，那么決策樹的復雜程度主要由樹的結(jié)點個數(shù)決定；如果是多變量（multivariare）的，則主要是由結(jié)點中屬性的總個數(shù)決定。傳統(tǒng)的決策樹算法主要是針對小數(shù)據(jù)集的,大都要求訓練集常駐內(nèi)存,這使得在處理數(shù)據(jù)挖掘任務(wù)時,傳統(tǒng)決策樹算法在可伸縮性、精度和效率方面受到了很大的限制。而在實際的數(shù)據(jù)挖掘應用中我們面臨的數(shù)據(jù)集往往是容量巨大的數(shù)據(jù)庫或者數(shù)據(jù)倉庫,在構(gòu)造決策樹時需要將龐大的數(shù)據(jù)在主存和緩存中不停的導入導出,使得運算效率大大降低。針對以上問題,許多學者提出了處理大型數(shù)據(jù)集的決策樹算法。其中主要在以下四個方面的應用：數(shù)據(jù)預處理；抽樣方法；數(shù)據(jù)的重構(gòu)；結(jié)合上述的遺傳算法等其他算法。目前決策樹技術(shù)的主要研究方向[8]有以下幾點:1 決策樹算法的并行性研究2 尋找新的構(gòu)造決策樹的方法3 尋找更好的簡化決策樹的方法4 研究產(chǎn)生決策樹的訓練和檢驗數(shù)據(jù)的大小及特性與決策樹特性之間的關(guān)系5 不確定環(huán)境下決策樹研究6 將決策樹用于多智能體控制并不多見7 決策樹時間復雜度與準確性之間的矛盾8 決策樹技術(shù)的軟件實現(xiàn)由以上討論可知：ID3算法存在種種缺陷，如：算法的計算時間是例子個數(shù)、特征個數(shù)、節(jié)點個數(shù)之積的線性函數(shù)。另外大量實驗證明,ID3算法在預測正確率和效果上是令人滿意的。用互信息作為特征選擇量,要求訓練例子集中的正、反例比例應與實際領(lǐng)域里正、反例比例相同。但在一般情況下不能保證相同,因而計算訓練集的互信息就有偏差。互信息的計算依賴于特征值數(shù)目較多的特征,這樣不太合理。另外ID3在建樹時,每個節(jié)點僅含一個特征,特征間的相關(guān)性強調(diào)不夠。下面針對ID3 算法的第二個不足之處,提出一些決策樹改進意見。[6]的特征選擇方法1．樣本均值 （1）表示第i類在第j維特征處的樣本均值。其中,Si表示第i類總的樣本數(shù), 表示第i類第k個樣本在第j維特征處的取值。2．樣本歸一化 樣本歸一化就是將屬性取值范圍投影到一個特定的范圍之內(nèi),以消除數(shù)值型屬性因大小不一而造成挖掘結(jié)