決策樹歸納法

歸納式學(xué)習(xí)法決策樹歸納法01簡介DTI算法步驟DTI算法原理目錄0302基本信息決策樹歸納法(DTI)，又稱“決策圖”，是歸納式學(xué)習(xí)法中最簡單的一支。它是將決策過程各個階段之間的邏輯結(jié)構(gòu)繪成一張箭線圖，再根據(jù)決策樹進(jìn)行分析計算，從而得出所需決策方案的方法。DTI常用于數(shù)據(jù)挖掘。簡介簡介決策樹歸納法根據(jù)數(shù)據(jù)的值，把數(shù)據(jù)分層組織成樹型結(jié)構(gòu)，即用樹形結(jié)構(gòu)來表示決策集合，這些決策集合通過對數(shù)據(jù)集的分類產(chǎn)生規(guī)則。在決策樹中每一個分支代表一個子類，樹的每一層代表一個概念。

決策樹歸納法一般以方框和圓圈為結(jié)點，并由直線連接而成的一種像樹枝形狀的結(jié)構(gòu)。方框結(jié)點叫做決策點，由決策點引出若干條樹枝(直線)。每條樹枝代表一個方案，故叫方案枝。在每個方案枝的末端畫上一個圓圈就是圓圈結(jié)點，圓圈結(jié)點叫做機(jī)會點。由機(jī)會點引出若干條樹枝(直線)，每條樹枝為概率枝。在概率枝的末端列出不同狀態(tài)下的收益值或損失值。

DTI常用于分析構(gòu)建模型的可行性與可信度，相應(yīng)地根據(jù)觀察推出其邏輯表達(dá)式及結(jié)構(gòu)，通過其簡單清晰的邏輯推理和分割信息值，能夠快捷地對大數(shù)據(jù)集進(jìn)行高效的數(shù)據(jù)劃分。但針對連續(xù)型數(shù)據(jù)和多類別集合，劃分效率就會隨復(fù)雜度的升高而降低。

DTI算法原理DTI算法原理決策樹歸納法(GTI)是一組規(guī)則集合，使用遞歸的方式將訓(xùn)練樣本集(TS)劃分成更小的子集合(Sub-TS)，直到每一個子集合擁有獨有的所屬類別標(biāo)簽。DTI算法通常采用信息論(IT)作為屬性選擇方法，根節(jié)點TS的選擇是基于訓(xùn)一算出的所具有最高信息增益的屬性。給定一個N維訓(xùn)練樣本集T={}，表示樣本實例屬于類別的先驗概率，可根據(jù)下式得出對給定的樣本實例進(jìn)行分類所需要的期望信息Info(T)。相應(yīng)地，訓(xùn)練樣本集T根據(jù)屬性A={}迭代地被劃分成N個不同的子集合{}，其中為樣本集合T中屬性A=時的樣本子集合。可根據(jù)權(quán)重值計算出屬性A劃分T的期望信息，從而根據(jù)原始信息要求Info(T)和新的信息要求的偏移量計算得出信息增益InfoGain(A)。根據(jù)樣本集T中的屬性值，逐一地計算出每個屬勝值對T進(jìn)行劃分的信息增益，從中選擇出具有最高信息增益的屬性。作為最佳屬性來劃分子集合，遞歸整個過程直到所有集合都被正確歸類。

DTI算法步驟示例偽程序解釋算法偽程序示例DTI算法步驟算法偽程序示例程序名：DTIsamples代表以離散值屬性表示的訓(xùn)練樣本，attribute_list指候選屬性集合。(1)建立一節(jié)點N；(2)若samples含相同分類c，則：(3)返回N表示含c類的葉節(jié)點；(4)若attribute_list為空集合則：(5)返回N含samples中最大類的葉節(jié)點；(6)選test_attribute，即attribute_list中含最大信息增益的屬性；(7)將節(jié)點N標(biāo)記為testattribute；(8)對testattribute的每一已知值分割樣本；(9)由節(jié)點N產(chǎn)生一分支表示testattribute=；示例偽程序解釋樹由一單一節(jié)點表示訓(xùn)練樣本開始(步驟1)，若樣本含相同類，則節(jié)點為葉且注標(biāo)為此類(步驟2、3)；否則，算法使用系統(tǒng)亂度導(dǎo)向稱為信息增益法為經(jīng)驗法則，以選出最能將樣本分成兩類的屬性(步驟6)。該屬性變成該節(jié)點的“測試”或“決策”屬性(步驟7)。算法的各屬性均被分類，每一測試屬性的已知值建立一分支，樣本依此被分割(步驟8-10)。算法以遞歸式形成樣本中每一分割而成決策樹。節(jié)點產(chǎn)生一屬性后，則不需考慮該節(jié)點的子孫(步驟13)。當(dāng)滿足下列條件時停止遞歸：(a)樣本的任一已知節(jié)點皆屬于某一固定類(步驟2、3)或(b)樣本中沒有其它屬性可供進(jìn)一步分割(步驟4)，此時，引用勝者攘括(步驟5)，將該節(jié)點轉(zhuǎn)換成葉節(jié)點且標(biāo)記為勝者的類別，否則儲存該節(jié)點的類分布。(c)分支test_attribute=(步驟11)無樣本。此時，葉依據(jù)樣本中主要類別建立(步驟12)。樹中每一節(jié)點所選的測試屬性均以信息增益加以衡量，這種衡量稱為屬性選擇度量或度量一完善的分割。含最高信息增益