機器學(xué)習(xí)算法總結(jié)-決策樹(編輯修改稿)
2025-07-14 03:55 本頁面
【文章內(nèi)容簡介】 e sum = count[0] + count[1]。 doubleentropy=count[0]/sum*log(count[0]/sum)/log() count[1]/sum*log(count[1]/sum)/log()。 return entropy。 }舉個例子：A事件是：季節(jié){春，夏，秋，冬}，B事件是：天氣{下雨，下雪，晴天，多云}；那就可以畫出一個二維表格，最直觀的是 夏天amp。下雪的概率冬天amp。下雪的概率；當(dāng)我知道天氣是下雪的時候，我就有很大的概率認(rèn)為季節(jié)是冬天；這說明：我知道了B事件的情況，對A的不確定性減少了；如果A，B是獨立的，比如，A事件是季節(jié){春，夏，秋，冬}，B事件是交通的情況{堵，不堵}，我知道B的情況，對A的不確定性并沒影響。上面說的是概念性的理解，如果用數(shù)學(xué)公式對應(yīng)起來理解，為什么會出現(xiàn)這樣的情況？已知B的情況，A的概率有沒有變化？當(dāng)A，B獨立，說明 沒有變化，當(dāng)AB不獨立的時候，即兩者存在某種相關(guān)性質(zhì)，換句話說就是B確定的前提下，A的概率分布與在總體上看不一樣。信息論中有熵，用來表示時間的不確定性，這個跟這個事件的可能值數(shù)目，還有取每個值的概率，比如有A事件{1,2,3,4}每個取值等概，那么熵為2；如果A{1,2}每個取值等概率，熵為1；當(dāng)取值數(shù)目一樣的時候A{1,2,3,4}，，那么這個熵小于2；這是為什么？因為在數(shù)據(jù)壓縮方面，對于小概率事件就要用長的編碼，大概率事件用短編碼，這樣最后平均每個事件的編碼就比較?。《鴮τ诘雀怕适录?，這種策略就沒法使用，就沒法實現(xiàn)數(shù)據(jù)的壓縮；熵說的就是這種下界。反過來，當(dāng)我們說一個事件熵很大，就意味著1這個事件的取值范圍很多2（或者）這個事件中每個取值的概率比較均勻以上兩者都代表著這個事件的不確定性很大，所以我們又說熵是一種不確定性的度量那么什么是條件熵呢，為什么小于等于呢？上面說了，知道了B，1：首先A的取值范圍會縮小，為什么？拿上面一個例子來說，我知道了天氣是下雪，那么幾乎可以說A的取值只能從{春天，冬天}里選擇；2：A中每個取值的概率分布會發(fā)生變化與的概率分布不同；數(shù)學(xué)證明；即已知B的結(jié)果，A的不確定性減少；要表述A這個事件的編碼數(shù)更少； 在決策樹中，我們關(guān)心的是H（結(jié)果|屬性）的關(guān)系，即已知某屬性，結(jié)果的不確定性還有多少；我們需要知道，哪個屬性能使得結(jié)果的不確定性減少最多。 決策樹的生成 ID3算法如果學(xué)習(xí)的任務(wù)是對一個大的例子集作分類概念的歸納定義，而這些例子又都是用一些無結(jié)構(gòu)的屬性值對來表示，則可以采用示例學(xué)習(xí)方法的一個變種──決策樹學(xué)習(xí)，其代表性的算法是昆蘭（，1986）提出的ID3。ID3算法是由Quinlan首先提出的。該算法是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標(biāo)準(zhǔn)，從而實現(xiàn)對數(shù)據(jù)的歸納分類。以下是一些信息論的基本概念：：若存在n個相同概率的消息，則每個消息的概率p是1/n，一個消息傳遞的信息量為：若有n個消息，其給定概率分布為，則由該分布傳遞的信息量稱為P的熵，記為。：若一個記錄集合T根據(jù)類別屬性的值被分成互相獨立的類C1C2..Ck，則識別T的一個元素所屬哪個類所需要的信息量為Info(T)=I(p)，其中P為C1C2…Ck的概率分布，即。：若我們先根據(jù)非類別屬性X的值將T分成集合T1,T2…Tn，則確定T中一個元素類的信息量可通過確定Ti的加權(quán)平均值來得到，即Info(Ti)的加權(quán)平均值為：：信息增益度是兩個信息量之間的差值，其中一個信息量是需確定T的一個元素的信息量，另一個信息量是在已得到的屬性X的值后需確定的T一個元素的信息量，信息增益度公式為：ID3算法計算每個屬性的信息增益，并選取具有最高增益的屬性作為給定集合的測試屬性。對被選取的測試屬性創(chuàng)建一個節(jié)點，并以該節(jié)點的屬性標(biāo)記，對該屬性的每個值創(chuàng)建一個分支據(jù)此劃分樣本。 ID3的輸入是描述各種已知類別實例的列表。例子由預(yù)先定義的屬性值對來表示。歸納推理產(chǎn)生的結(jié)果不是以往討論的那種合取表達(dá)式，而是一棵決策樹（也稱判別樹，并可轉(zhuǎn)而表示為決策規(guī)則的一個集合），用它可正確地區(qū)分所有給定例子的類屬?！ 渲械拿恳环侨~節(jié)點對應(yīng)一個需測試的屬性，每個分叉就是該屬性可能的取值；樹的葉節(jié)點則指示一個例子事物的類別。ID3的顯著優(yōu)點是歸納學(xué)習(xí)花費的時間和所給任務(wù)的困難度（取決于例子個數(shù)，用來描述對象的屬性數(shù)，所學(xué)習(xí)概念的復(fù)雜度即決策樹的節(jié)點數(shù)等）僅成線性增長關(guān)系。當(dāng)然，ID3只能處理用屬性值對表示的例子。在ID3中, 每一個例子用相同的一組屬性來表示，每一個屬性又有自身的屬性值集，如顏色屬性可取值是{紅、綠、蘭}等。構(gòu)造決策樹的目的是為了對事物作出正確的分類。決策樹形式的分類規(guī)則適用于任何的對象集Ｃ。如Ｃ是空的，那么它無需分類，對應(yīng)的決策樹也為空；如Ｃ中的對象是同一類的，那么決策樹就一個葉節(jié)點，即該類名；如果Ｃ集中的對象屬于二個不同的類別，那未我們可以選取一個對象的屬性，隨后按其可能值把Ｃ劃分成一些不相交的子集C1，C2，…，Cn，其中Ci是含有所選屬性的第ｉ個值的那些對象集。對每一個這樣的子集又可以用同樣的策略處理，最后的結(jié)果是一棵樹。ID3（Examples,Targetattrlbute,Attrlbutes）創(chuàng)建樹的root節(jié)點如果Examples都為正，返回label=+的單節(jié)點輸root如果Examples都為反，返回label=的單節(jié)點輸root如果Attrlbutes為空，那么返回單節(jié)點輸root，label=Examples中最普遍的Targetattributes值否則開始A Attributes中分類examples能力最好的屬性Root的決策屬性A對于A的每個可能值vi 在root下加一個新的分支對應(yīng)測試A=vi 令Examples為Examples中滿足A屬性值為vi的子集 如果Examples為空 在這個新分支下加一個葉子結(jié)點，節(jié)點的label=Examples中最普遍的Targetattributes值 否則在新分支下加一個子樹ID3 （Examples Targetattribute，Attributes{A}）結(jié)束返回root 下面給出一個關(guān)于人分類的例子（對象）集，并預(yù)先定義了指定的一組屬性及其可取值：高度{高，矮}，發(fā)色{黑色, 紅色，金色}和眼睛{蘭色，棕色}。這里，將人分為兩類，分別以＋、－來指示?！? 高度 發(fā)色 眼睛 類別 矮 黑色
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1