數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘7-wenkub
2023-03-28 12:39:47 本頁(yè)面
【正文】 ?這種情形就稱為信宿對(duì)于信源狀態(tài)具有不確定性。第 7章 信息論方法 ? 信息論原理 ? 決策樹(shù)方法 ? 信息論原理 信息論是 （通信）過(guò)程問(wèn)題而建立的理論，也稱為統(tǒng)計(jì)通信理論。而且這種不確定性是存在于通信之前的。先驗(yàn)不確定性不能全部被消除，只能部分地消除。 ? 如果后驗(yàn)不確定性等于零，這就表示信宿收到了全部信息。 （ 2） S中有 U1， U2兩類 。 （ 2） 消息（符號(hào)） Ui（ i=1， 2， ...， q）的發(fā)生概率 P（ Ui）組成信源數(shù)學(xué)模型（樣本空間或概率空間） （ ） ＝ [ ] （ 3） 自信息 :消息 Ui發(fā)出后所含有的信息量 。 即信源輸出后 ，每個(gè)消息所提供的信息量 ， 也反映了信源輸出前的平均不確定性 。 （ 2） 如果 n種可能的發(fā)生都有相同的概率 ， 即所有的 Ui有 P（ Ui） =1/n， H（ U） 達(dá)到最大值 log n，系統(tǒng)的不確定性最大 。 其后驗(yàn)熵為： 后驗(yàn)熵是接收到單個(gè)輸出符號(hào) Vj后關(guān)于信息源 U的不確定性 (信息度量 )。 說(shuō)明接收到符號(hào)集 V的所有符號(hào)后 ， 關(guān)于輸入符號(hào) U的平均不確定性減少了 。 可見(jiàn) ， 熵 （ H（ U） 、 H（ U|V）） 只是平均不確定性的描述 。樹(shù)的中間結(jié)點(diǎn)是該結(jié)點(diǎn)為根的子樹(shù)所包含的樣本子集中信息量最大的屬性。 ID3方法基本思想 ? 最有影響的決策樹(shù)方法首推 ID3。 一、 ID3基本思想 例如：關(guān)于氣候的類型，特征為 : 天氣 取值為： 晴，多云，雨 氣溫 取值為： 冷 ，適中，熱 濕度 取值為： 高 ，正常 風(fēng) 取值為： 有風(fēng)， 無(wú)風(fēng) ? 每個(gè)實(shí)體在世界中屬于不同的類別，為簡(jiǎn)單起見(jiàn)，假定僅有兩個(gè)類別，分別為 P， N。由 ID3算法得出一棵正確分類訓(xùn)練集中每個(gè)實(shí)體的決策樹(shù)，見(jiàn)下圖。 ?現(xiàn)用來(lái)判一個(gè)具體例子， 某天早晨氣候描述為 : 天氣 ：多云 氣溫 ：冷 濕度 ：正常 風(fēng) ：無(wú)風(fēng) 它屬于哪類氣候呢 ? ?從圖中可判別該實(shí)體的類別為 P類。 二、 ID3算法 （一）主算法 ⒈ 從訓(xùn)練集中隨機(jī)選擇一個(gè)既含正例又含反例的子集（稱為 窗口 ）； ⒉ 用“建樹(shù)算法”對(duì)當(dāng)前窗口形成一棵決策樹(shù)； ⒊ 對(duì)訓(xùn)練集（窗口除外）中例子用所得決策樹(shù)進(jìn)行類別判定，找出錯(cuò)判的例子； ⒋ 若存在錯(cuò)判的例子，把它們插入窗口，轉(zhuǎn) 2，否則結(jié)束。 ? 主算法中每迭代循環(huán)一次，生成的決策樹(shù)將會(huì)不相同。濕度取高的例子全為 N類，該分枝標(biāo)記 N。取無(wú)風(fēng)時(shí)全為 P類，該分枝標(biāo)記 P。其中正例 2361個(gè)，反例 2400個(gè)，每個(gè)例子由 500個(gè)特征描述，每個(gè)特征取值數(shù)目為 6，得到一棵 1514個(gè)結(jié)點(diǎn)的決策樹(shù)。一般情況不能保證相同，這樣計(jì)算訓(xùn)練集的互信息就有偏差。關(guān)于什么是噪聲，Quinlan的定義是訓(xùn)練例子中的錯(cuò)誤就是噪聲。這對(duì)漸近學(xué)習(xí)（即訓(xùn)練例子不斷增加）是不方便的。 ID3在應(yīng)用中存在的不足，主要體現(xiàn)在以下幾個(gè)方面： （ 1） 用信息增益率來(lái)選擇屬性，它克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足； （ 2） 在樹(shù)構(gòu)造過(guò)程中或者構(gòu)造完成之后，進(jìn)行剪枝； （ 3） 能夠完成對(duì)連續(xù)屬性的離散化處理； （ 4） 能夠?qū)τ诓煌暾麛?shù)據(jù)的處理，例如未知的屬性 值； （ 5） ，并最終可以 形成產(chǎn)生式規(guī)則。 ?如果僅僅算差值那么兩個(gè)差距就很大了 ， 如果使用速度增加率 (加速度 ， 即都是為 1m/s^2)來(lái)衡量 ， 2個(gè)人就是一樣的加速度 。計(jì)算這 N1種情況下最大的信息增益率。 決策樹(shù)剪枝 由于噪聲和隨機(jī)因素的影響，決策樹(shù)一般會(huì)很復(fù)雜。 （ 2）對(duì)于生成好的樹(shù)剪去某些結(jié)點(diǎn)和分枝。 (2)基于誤差的剪枝 決策樹(shù)的剪枝通常是用葉結(jié)點(diǎn)替代一個(gè)或者多個(gè)子樹(shù)，然后選擇出現(xiàn)概率最高的類作為該結(jié)點(diǎn)的類別。 對(duì)于生成好的決策樹(shù)，我們可以直接從獲得規(guī)則。 ?此外， 集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。例如，從下面的決策樹(shù)中我們可以得到規(guī)則： F=0 J = 0: Class0 J = 1 K = 0: Class0 K = 1: Class
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1