模式識別——決策樹算法-預(yù)覽頁
【正文】 then 加一個樹葉到節(jié)點 N，標(biāo)記為 D 中的多數(shù)類； else 加一個由 Generate_decision_tree（ Dj， attribute_list）返回的節(jié)點到節(jié)點 N； end for 返回 N； 上述算法基本策略中，用到三個參數(shù) D、 attribute_list和 Attribute_selection_method調(diào)用該算法。如果我們要根據(jù)分裂準(zhǔn)則的輸出將 D劃分成較小的劃分，理想地，每個劃分是“純”的，即，落在給定劃分的所有元組都屬于相同的類。設(shè)節(jié)點 N代表或存放 劃分 D的元組。 對于 D中的元組分類所需的期望信息由下式給出： 21( ) lo g ( )miiiIn fo D p p??? ? （ 1） 其中， pi是 D中任意元組屬于類 Ci的概率，并用 |Ci,D|/|D|估計。 Info(D)又稱 D的熵。理想地，我們希望該劃分產(chǎn)生元組的準(zhǔn)確分類，即，每個劃分都是純的。 信息增益定義為原來的信息需求（即僅基于類比例）與新的需求（即對 A劃分之后得到的）之間的差。 三 ID3 算法 java 實現(xiàn) 1 實例 假定某推銷員根據(jù)經(jīng)驗得知，學(xué)生是否會由家長接送，與學(xué)生的年齡、性別和家庭收入關(guān)系最大。有經(jīng)驗的同事告訴她，應(yīng)該先把年齡和收入情況分成幾個等級。 對于表中數(shù)據(jù)，在不考慮任何特征時， 16 人中有 4 人需要家長接送， 12 人不需要家長接送，計算出此時的熵不純度為 ))1612(l og1612)164(l og164(Inf o(D ) 22 ???? 其中， Info(D)表示總共 16 個樣本中 4 個為一類， 12 個為另一類時的熵不純度?？偟撵夭患兌仁沁@兩組樣本上計算的不純度按照樣本比例的加權(quán)求和，即 (D )1610Info(D )166(D )Info A ??? 這 樣，采用年齡作為根節(jié)點后，在下一級的熵不純度比上一級減少的量是 ( D )I n f oI n f o ( D )G a i n ( A ) A ?? 稱作不純度減少量，或信息增益（ information gain）。結(jié)果發(fā)現(xiàn)，對于男性組，采用年齡特征后不純度減少最大，為 ；對于女性組，則是采用月收入作為特征后不純度減少最多，為 。 模式識別 —— 決策樹算法 第 7 頁 共 14 頁 2 算法的 JAVA 實現(xiàn) import JAVA包 。 // 原始數(shù)據(jù) int decatt。 public ID3() { xmldoc = ()。 (new File( D:\\newProject\\weka371\\weka371\\weka371\\data\\))。 i ()。 i ()。 return。 Pattern pattern = (patternString)。 ArrayListString al = new ArrayListString()。 String[] row = (,)。 } catch (IOException e1) { ()。 } decatt = n。 int sum = 0。 sum += arr[i]。 } public boolean infoPure(ArrayListInteger subset) { String value = ((0))[decatt]。 // equals表示對象內(nèi)容相同， ==表示兩個對象指向的是同一片內(nèi)存 if (!(next)) return false。 int[][] info = new int[(index).size()][]。 模式識別 —— 決策樹算法 第 11 頁 共 14 頁 int[] count = new int[(index).size()]。 String nodevalue = (n)[index]。 int decind = (decatt).indexOf(decvalue)。 i++) { entropy += getEntropy(info[i]) * count[i] / sum。 IteratorElement iter = ()。 return。 i ()。 minEntropy = entropy。 for (String val : attvalues) { (nodeName).addAttribute(value, val)。 i++) { if (((i))[minIndex].equals(val)) { ((i))。 FileWriter fw = new FileWriter(file)。 ()。 2 弊端 以上介紹的基本算法對于樹的每一層，需要掃描一遍 D中的元組。 。研究表明這種方法存在一個弊端：算法往往偏向于選擇取值較多的屬性，因為加權(quán)和的方法使得實例集的分模式識別 —— 決策樹算法 第 14 頁 共 14 頁 類趨向于拋棄小數(shù)據(jù)量的數(shù)據(jù)元組，然而取值較多的屬性卻不總是最優(yōu)的屬性，即按照使熵值最小和信息增益最大的原 則被 ID3算法列為應(yīng)該首先選取的屬性在現(xiàn)實情況中卻并不那么重要，也就是說對這些屬性進(jìn)行測試不會提供太多的信息。 利用用戶興趣度把（ 2）修改為： 1||( ) ( ) ( )||v jAjjDIn fo D In fo DD ??? ? ?? 六、 附錄 —— 核心算法的主要源代 碼 模式識別 —— 決策樹算法 第 15 頁 共 14 頁 模式識別 —— 決策樹算法 第 16 頁 共 14 頁 模式識別 —— 決策樹算法 第 17 頁 共 14 頁 參考文獻(xiàn) [1] 張學(xué)工 . 模式識別 . 第 三 版 . 北京： 清華大學(xué) 出版社， 20228. [2] ID3 決策樹 eWl2mx7aXG2z_BIgPL1m513MXrZIwpZEXlio5KnGrzH00DE_XSRGwRyeoB1EK
公司管理相關(guān)推薦
鄂ICP備17016276號-1