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