模式識(shí)別——決策樹(shù)算法-資料下載頁(yè)
2025-12-30 09:24本頁(yè)面
【正文】 istInteger selatt) { Element ele = null。 @SuppressWarnings(unchecked) ListElement list = (// + name)。 IteratorElement iter = ()。 while (()) { ele = ()。 if ((value).equals(value)) break。 } if (infoPure(subset)) { (((0))[decatt])。 return。 模式識(shí)別 —— 決策樹(shù)算法 第 12 頁(yè) 共 14 頁(yè) } int minIndex = 1。 double minEntropy = 。 for (int i = 0。 i ()。 i++) { if (i == decatt) continue。 double entropy = calNodeEntropy(subset, (i))。 if (entropy minEntropy) { minIndex = (i)。 minEntropy = entropy。 } } String nodeName = (minIndex)。 (new Integer(minIndex))。 ArrayListString attvalues = (minIndex)。 for (String val : attvalues) { (nodeName).addAttribute(value, val)。 ArrayListInteger al = new ArrayListInteger()。 for (int i = 0。 i ()。 i++) { if (((i))[minIndex].equals(val)) { ((i))。 } } buildDT(nodeName, val, al, selatt)。 } } // 把 xml寫(xiě)入文件 public void writeXML(String filename) { try { File file = new File(filename)。 模式識(shí)別 —— 決策樹(shù)算法 第 13 頁(yè) 共 14 頁(yè) if (!()) ()。 FileWriter fw = new FileWriter(file)。 OutputFormat format = ()。 // 美化格式 XMLWriter output = new XMLWriter(fw, format)。 (xmldoc)。 ()。 } catch (IOException e) { (())。 } } } 四 ID3 算法性能分析 1 優(yōu)勢(shì) 搜索空間是完全的假設(shè)空間，目標(biāo)函數(shù)必在搜索空間中，不存在無(wú)解的危險(xiǎn) ；全盤(pán)使用訓(xùn)練數(shù)據(jù)，而不是像候選剪除算法一個(gè)一個(gè)地考慮訓(xùn)練例。這樣做的優(yōu)點(diǎn)是，可以利用全部訓(xùn)練例的統(tǒng)計(jì)性質(zhì)進(jìn)行決策，從而抵抗噪音。 2 弊端 以上介紹的基本算法對(duì)于樹(shù)的每一層，需要掃描一遍 D中的元組。在處理大型數(shù)據(jù)庫(kù)時(shí)，這可能導(dǎo)致很長(zhǎng)的訓(xùn)練時(shí)間和內(nèi)存的不足。 對(duì)于非增量式學(xué)習(xí)任務(wù)， ID3算法常常是建立決策樹(shù)的很好的選擇。但對(duì)于增量式學(xué)習(xí)任務(wù)來(lái)說(shuō)，由于 ID3不能增量地接受訓(xùn)練例，這就使得每增加一次實(shí)例都必須拋棄原有決策樹(shù)，重新構(gòu)造新的決策樹(shù)，造成了極大的開(kāi)銷(xiāo)。 。 搜索中只維持一個(gè)解，不 能像候選剪除算法那樣返回所有可能的與訓(xùn)練例集一致的假設(shè)，并優(yōu)化地查詢(xún)新例以獲得收斂于目標(biāo)函數(shù)的解；其搜索無(wú)回溯。它可能收斂于局部最優(yōu)解而丟失全局最優(yōu)解，因?yàn)橐粋€(gè)一個(gè)地考慮訓(xùn)練例，不容易像剪除算法那樣使用新例步進(jìn)式地改進(jìn)決策樹(shù)。 五 ID3 算法改進(jìn) 傳統(tǒng)的 ID3算法選擇屬件 A作為測(cè)試屬性的原則是使得其信息增益最大。研究表明這種方法存在一個(gè)弊端：算法往往偏向于選擇取值較多的屬性，因?yàn)榧訖?quán)和的方法使得實(shí)例集的分模式識(shí)別 —— 決策樹(shù)算法 第 14 頁(yè) 共 14 頁(yè) 類(lèi)趨向于拋棄小數(shù)據(jù)量的數(shù)據(jù)元組，然而取值較多的屬性卻不總是最優(yōu)的屬性，即按照使熵值最小和信息增益最大的原 則被 ID3算法列為應(yīng)該首先選取的屬性在現(xiàn)實(shí)情況中卻并不那么重要，也就是說(shuō)對(duì)這些屬性進(jìn)行測(cè)試不會(huì)提供太多的信息。 針 |對(duì) ID3算法偏向于選擇取值較多但實(shí)際中并不總是最優(yōu)的屬件作為測(cè)試屬件的缺點(diǎn)，這里引人用戶(hù)興趣度：給定 0≤ ? ≤ 1， ? 稱(chēng)為用戶(hù)對(duì)不確定知識(shí)的興趣度，其太小由決策者根據(jù)先驗(yàn)知識(shí)或領(lǐng)域知識(shí)來(lái)確定。它是個(gè)模糊的概念，通常指關(guān)于某一事務(wù)的先驗(yàn)知識(shí)，包括領(lǐng)域知識(shí)和專(zhuān)家建議，具體到?jīng)Q策樹(shù)學(xué)習(xí)中則是指在決策樹(shù) 訓(xùn)練過(guò)程中除了用于生成和修改決策樹(shù)的實(shí)例集之外的所有影響決策樹(shù)規(guī)則生成和選擇的因素。 改進(jìn)的 ID3算法是針對(duì)規(guī)則生成方法即屬性選擇標(biāo)準(zhǔn)算法進(jìn)行了改進(jìn)，通過(guò)對(duì)式 (2)中加權(quán)和增加用戶(hù)興趣度，加強(qiáng)了屬性的標(biāo)注，降低了非重要屬性的標(biāo)注，把加權(quán)和轉(zhuǎn)換為加權(quán)和加用戶(hù)興趣度，使生成決策樹(shù)時(shí)數(shù)量少的數(shù)據(jù)元組不會(huì)被淹沒(méi)，最終使決策樹(shù)減少了對(duì)取值較多的屬性的依賴(lài)性，從而盡可能地減少大數(shù)據(jù)掩蓋小數(shù)據(jù)的現(xiàn)象發(fā)生。 利用用戶(hù)興趣度把（ 2）修改為： 1||( ) ( ) ( )||v jAjjDIn fo D In fo DD ??? ? ?? 六、 附錄 —— 核心算法的主要源代 碼 模式識(shí)別 —— 決策樹(shù)算法 第 15 頁(yè) 共 14 頁(yè) 模式識(shí)別 —— 決策樹(shù)算法 第 16 頁(yè) 共 14 頁(yè) 模式識(shí)別 —— 決策樹(shù)算法 第 17 頁(yè) 共 14 頁(yè) 參考文獻(xiàn) [1] 張學(xué)工 . 模式識(shí)別 . 第 三 版 . 北京： 清華大學(xué) 出版社， 20228. [2] ID3 決策樹(shù) eWl2mx7aXG2z_BIgPL1m513MXrZIwpZEXlio5KnGrzH00DE_XSRGwRyeoB1EK
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1