數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘7(完整版)
【正文】 個(gè)類分布描述，即該葉結(jié)點(diǎn)屬于某類的概率。 ?其缺點(diǎn)是： ?在構(gòu)造樹的過程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。 從決策樹抽取規(guī)則 在 ，從決策樹抽取規(guī)則需要兩個(gè)步驟：獲得簡(jiǎn)單規(guī)則、精簡(jiǎn)規(guī)則屬性。若停止擴(kuò)展，則相當(dāng)于剪去該結(jié)點(diǎn)以下的分枝。 ?雖然本質(zhì)上屬性的取值是連續(xù)的，但對(duì)于有限的采樣數(shù)據(jù)它是離散的， ?如果有 N條樣本，那么我們有 N1種離散化的方法： =vj的分到左子樹， vj的分到右子樹。 是在 ID3基礎(chǔ)上發(fā)展起來的決策樹生成算法，由 1993年提出。 （ 4） ID3對(duì)噪聲較為敏感。用 4761個(gè)關(guān)于苯的質(zhì)譜例子作了試驗(yàn)。 天 氣 1,2,8,9,11 4,5,6,10,14 晴 雨 多云 P ⒌ 遞歸建樹 分別對(duì) F1和 F3子集利用 ID3算法，在每個(gè)子集中對(duì)各特征（仍為四個(gè)特征）求互信息 . （ 1） F1中的天氣全取晴值，則 H（ U） =H（ U|V），有 I（ U|V） =0，在余下三個(gè)特征中求出濕度互信息最大，以它為該分枝的根結(jié)點(diǎn)，再向下分枝。 Quinlan的 ID3算法能得出結(jié)點(diǎn)最少的決策樹。 ? 表 。 ? 決策樹能準(zhǔn)確地識(shí)別所有樣本的類別，也能有效地識(shí)別新樣本的類別。 它代表接收到符號(hào)集 V后獲得的關(guān)于 U的信息量 。 7． 互信息 (1)后驗(yàn)熵 當(dāng)信宿沒有接收到輸出符號(hào) V時(shí) ， 已知輸入符號(hào) U的概率分布為 P（ U） ， 而當(dāng)接收到輸出符號(hào) V=Vj 后 ， 輸入符號(hào)的概率分布發(fā)生了變化 ,變成后驗(yàn)概率分布 P（ U|Vj） 。 （ 4） 信息熵 :自信息的數(shù)學(xué)期望 。 ｜ S｜表示例子總數(shù) 。 ?一般情況下，干擾總會(huì)對(duì)信源發(fā)出的信息造成某種破壞，使信宿收到的信息不完全。第 7章 信息論方法 ? 信息論原理 ? 決策樹方法 ? 信息論原理 信息論是 （通信）過程問題而建立的理論，也稱為統(tǒng)計(jì)通信理論。先驗(yàn)不確定性不能全部被消除，只能部分地消除。 （ 2） S中有 U1， U2兩類 。 即信源輸出后 ，每個(gè)消息所提供的信息量 ， 也反映了信源輸出前的平均不確定性 。 其后驗(yàn)熵為： 后驗(yàn)熵是接收到單個(gè)輸出符號(hào) Vj后關(guān)于信息源 U的不確定性 (信息度量 )。 可見 ， 熵 （ H（ U） 、 H（ U|V）） 只是平均不確定性的描述 。 ID3方法基本思想 ? 最有影響的決策樹方法首推 ID3。由 ID3算法得出一棵正確分類訓(xùn)練集中每個(gè)實(shí)體的決策樹，見下圖。 二、 ID3算法 （一）主算法 ⒈ 從訓(xùn)練集中隨機(jī)選擇一個(gè)既含正例又含反例的子集（稱為 窗口 ）； ⒉ 用“建樹算法”對(duì)當(dāng)前窗口形成一棵決策樹； ⒊ 對(duì)訓(xùn)練集（窗口除外）中例子用所得決策樹進(jìn)行類別判定，找出錯(cuò)判的例子； ⒋ 若存在錯(cuò)判的例子，把它們插入窗口，轉(zhuǎn) 2，否則結(jié)束。濕度取高的例子全為 N類，該分枝標(biāo)記 N。其中正例 2361個(gè)，反例 2400個(gè)，每個(gè)例子由 500個(gè)特征描述，每個(gè)特征取值數(shù)目為 6，得到一棵 1514個(gè)結(jié)點(diǎn)的決策樹。關(guān)于什么是噪聲，Quinlan的定義是訓(xùn)練例子中的錯(cuò)誤就是噪聲。 ID3在應(yīng)用中存在的不足，主要體現(xiàn)在以下幾個(gè)方面： （ 1） 用信息增益率來選擇屬性，它克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足； （ 2） 在樹構(gòu)造過程中或者構(gòu)造完成之后，進(jìn)行剪枝； （ 3） 能夠完成對(duì)連續(xù)屬性的離散化處理； （ 4） 能夠?qū)τ诓煌暾麛?shù)據(jù)的處理，例如未知的屬性 值； （ 5） ，并最終可以 形成產(chǎn)生式規(guī)則。計(jì)算這 N1種情況下最大的信息增益率。 （ 2）對(duì)于生成好的樹剪去某些結(jié)點(diǎn)和分枝。 對(duì)于生成好的決策樹，我們可以直接從獲得規(guī)則。例如，從下面的決策樹中我們可以得到規(guī)則： F=0 J = 0: Class0 J = 1 K = 0: Class0 K = 1: Class1 F = 1 G = 1: Class1 G = 0 J = 0: Class0 J = 1 K = 0: Class0 K = 1: Class1 決 策 樹： 規(guī)則： IF F=1, G=0, J=1, K=1 THEN class1 ?： ?產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。 剪枝之后的決策樹的葉結(jié)點(diǎn)不再只包含一類實(shí)例。 ?有辦法可以減少計(jì)算量。 用信息增益率來選擇屬性 ?一般來說率就是用來取平衡用的 ， 就像方差 。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1