機器學(xué)習(xí)算法總結(jié)-決策樹-文庫吧資料
2025-06-23 03:55本頁面
【正文】 間和所給任務(wù)的困難度（取決于例子個數(shù)，用來描述對象的屬性數(shù)，所學(xué)習(xí)概念的復(fù)雜度即決策樹的節(jié)點數(shù)等）僅成線性增長關(guān)系。歸納推理產(chǎn)生的結(jié)果不是以往討論的那種合取表達(dá)式，而是一棵決策樹（也稱判別樹，并可轉(zhuǎn)而表示為決策規(guī)則的一個集合），用它可正確地區(qū)分所有給定例子的類屬?！ D3的輸入是描述各種已知類別實例的列表。：若我們先根據(jù)非類別屬性X的值將T分成集合T1,T2…Tn，則確定T中一個元素類的信息量可通過確定Ti的加權(quán)平均值來得到，即Info(Ti)的加權(quán)平均值為：：信息增益度是兩個信息量之間的差值，其中一個信息量是需確定T的一個元素的信息量，另一個信息量是在已得到的屬性X的值后需確定的T一個元素的信息量，信息增益度公式為：ID3算法計算每個屬性的信息增益，并選取具有最高增益的屬性作為給定集合的測試屬性。以下是一些信息論的基本概念：：若存在n個相同概率的消息，則每個消息的概率p是1/n，一個消息傳遞的信息量為：若有n個消息，其給定概率分布為，則由該分布傳遞的信息量稱為P的熵，記為。ID3算法是由Quinlan首先提出的。反過來，當(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é)果的不確定性減少最多。上面說的是概念性的理解，如果用數(shù)學(xué)公式對應(yīng)起來理解，為什么會出現(xiàn)這樣的情況？已知B的情況，A的概率有沒有變化？當(dāng)A，B獨立，說明 沒有變化，當(dāng)AB不獨立的時候，即兩者存在某種相關(guān)性質(zhì)，換句話說就是B確定的前提下，A的概率分布與在總體上看不一樣。下雪的概率冬天amp。 return entropy。//全部是正實例或者負(fù)實例 //具體計算熵 根據(jù)[+count[0],count[1]],log2為底通過換底公式換成自然數(shù)底數(shù) double sum = count[0] + count[1]。 } } done_flag = true。!remain_state[i][j].pare(value)) || ifparent){//ifparen記錄是否算父節(jié)點 if(!remain_state[i][MAXLEN 1].pare(yes)){ count[0]++。i++){if((!ifparentamp。 if(!attribute_row[j].pare(attribute)){for(i=1。 j MAXLEN。 bool done_flag = false。舉例來說，假設(shè)S是一個關(guān)于布爾概念的有14個樣例的集合，它包括9個正例和5個反例（我們采用記號[9+，5]來概括這樣的數(shù)據(jù)樣例），那么S相對于這個布爾樣例的熵為：注意，如果S的所有成員屬于同一類，例如，如果所有的成員是正的，那么p就是0，于是； 另外S的正反樣例數(shù)量相等，；S的正反樣例數(shù)量不等，熵介于0，1之間，如下圖所示：//根據(jù)具體屬性和值來計算熵 double ComputeEntropy(vector vector string remain_state, string attribute, string value,bool ifparent){ vectorint count (2,0)。因此有這樣兩個條件熵的表達(dá)式：這是指特征X被固定為值xi時的條件熵，這是指特征X被固定時的條件熵，注意與上式在意義上的區(qū)別。但是問題接踵而至，例如一個特征X，它可能的取值有n多種，當(dāng)計算條件熵而需要把它固定的時候，要把它固定在哪一個值上呢？答案是每一種可能都要固定一下，計算n個值，然后取均值才是條件熵。我們計算分類系統(tǒng)不包含特征t的時候，就使用情況（2）來代替，就是計算當(dāng)一個特征t不能變化時，系統(tǒng)的信息量是多少。問題是當(dāng)系統(tǒng)不包含t時，信息量如何計算？我們換個角度想問題，把系統(tǒng)要做的事情想象成這樣：說教室里有很多座位，學(xué)生們每次上課進(jìn)來的時候可以隨便坐，因而變化是很大的（無數(shù)種可能的座次情況）；但是現(xiàn)在有一個座位，看黑板很清楚，聽老師講也很清楚，于是校長的小舅子的姐姐的女兒托關(guān)系（真輾轉(zhuǎn)?。?，把這個座位定下來了，每次只能給她坐，別人不行，此時情況怎樣？對于座次的可能情況來說，我們很容易看出以下兩種情況是等價的：（1）教室里沒有這個座位；（2）教室里雖然有這個座位，但其他人不能坐（因為反正它也不能參與到變化中來，它是不變的）。此時分類系統(tǒng)的熵就可以表示為：信息增益是針對一個一個的特征而言的，就是看一個特征t，系統(tǒng)有它和沒它的時候信息量各是多少，兩者的差值就是這個特征給系統(tǒng)帶來的信息量，即增益。說有這么一個變量X，它可能的取值有n多種，分別是，每一種取到的概率分別是，那么X的熵就定義為：意思就是一個變量可能的變化越多（反而跟變量具體的取值沒有任何關(guān)系，只和值的種類多少以及發(fā)生概率有關(guān)），它攜帶的信息量就越大（因此我一直覺得我們的政策法規(guī)信息量非常大，因為它變化很多，基本朝令夕改，笑）。在信息增益中，重要性的衡量標(biāo)準(zhǔn)就是看特征能夠為分類系統(tǒng)帶來多少信息，帶來的信息越多，該特征越重要。在1951年由Solomon Kullback 和Richard Leibler首先提出作為兩個分布的直接增益（directed divergence）。就比如信息增益不是對稱的，從P到Q的信息增益通常不等于從Q到P的信息增益。Q代表一種理論，模型，描述或者對P的近似。信息增益描述了當(dāng)使用Q進(jìn)行編碼時，再使用P進(jìn)行編碼的差異。 信息增益信息增益（Kullback–Leibler divergence）又稱information divergence，information gain，relative entropy 或者KLIC。(3) 停止準(zhǔn)則( Stopping Criterion )停止準(zhǔn)則是與評價函數(shù)相關(guān)的，一般是一個閾值，當(dāng)評價函數(shù)值達(dá)到這個閾值后就可停止搜索。搜索特征子集的過程有
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1