決策樹演算法實例
A. 決策樹法的計算題
依據y坐標將六個點劃分為兩個子類，水平線上面的兩個點是同一個分類，但是水平線之下的四個點是不純凈的。
對這四個點進行再次分類，以x左邊分類，通過兩層分類，現了對樣本點的完全分類。
決策樹是一種具有樹狀結構的分類和預測工具，其中每個內部節點表示對一個屬性的測試，每個分支表示測試的結果，每個葉節點(終端節點)持有一個類標簽。
(1)決策樹演算法實例擴展閱讀
決策樹演算法的關鍵
1、分裂屬性的選擇
即選擇哪個自變數作為樹叉，也就是在n個自變數中，優先選擇哪個自變數進行分叉。
2、樹剪枝
即在構建樹叉時，由於數據中的雜訊和離群點，許多分支反映的是訓練數據中的異常，而樹剪枝則是處理這種過分擬合的數據問題，常用的剪枝方法為先剪枝和後剪枝。
B. 決策樹的演算法
C4.5演算法繼承了ID3演算法的優點，並在以下幾方面對ID3演算法進行了改進：
1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；
2) 在樹構造過程中進行剪枝；
3) 能夠完成對連續屬性的離散化處理；
4) 能夠對不完整數據進行處理。
C4.5演算法有如下優點：產生的分類規則易於理解，准確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致演算法的低效。此外，C4.5隻適合於能夠駐留於內存的數據集，當訓練集大得無法在內存容納時程序無法運行。
具體演算法步驟如下；
1創建節點N
2如果訓練集為空，在返回節點N標記為Failure
3如果訓練集中的所有記錄都屬於同一個類別，則以該類別標記節點N
4如果候選屬性為空，則返回N作為葉節點，標記為訓練集中最普通的類；
5for each 候選屬性 attribute_list
6if 候選屬性是連續的then
7對該屬性進行離散化
8選擇候選屬性attribute_list中具有最高信息增益率的屬性D
9標記節點N為屬性D
10for each 屬性D的一致值d
11由節點N長出一個條件為D=d的分支
12設s是訓練集中D=d的訓練樣本的集合
13if s為空
14加上一個樹葉，標記為訓練集中最普通的類
15else加上一個有C4.5（R - {D},C，s）返回的點 背景：
分類與回歸樹(CART——Classification And Regression Tree)) 是一種非常有趣並且十分有效的非參數分類和回歸方法。它通過構建二叉樹達到預測目的。
分類與回歸樹CART 模型最早由Breiman 等人提出，已經在統計領域和數據挖掘技術中普遍使用。它採用與傳統統計學完全不同的方式構建預測准則，它是以二叉樹的形式給出，易於理解、使用和解釋。由CART 模型構建的預測樹在很多情況下比常用的統計方法構建的代數學預測准則更加准確，且數據越復雜、變數越多，演算法的優越性就越顯著。模型的關鍵是預測准則的構建，准確的。
定義：
分類和回歸首先利用已知的多變數數據構建預測准則, 進而根據其它變數值對一個變數進行預測。在分類中, 人們往往先對某一客體進行各種測量, 然後利用一定的分類准則確定該客體歸屬那一類。例如, 給定某一化石的鑒定特徵, 預測該化石屬那一科、那一屬, 甚至那一種。另外一個例子是, 已知某一地區的地質和物化探信息, 預測該區是否有礦。回歸則與分類不同, 它被用來預測客體的某一數值, 而不是客體的歸類。例如, 給定某一地區的礦產資源特徵, 預測該區的資源量。
C. 用偽代碼撰寫C4.5決策樹分類演算法或者樸素貝葉斯演算法，任意舉一簡單例子說明你寫的演算法的執行流程
vbvbvbvbvbvvbbvvbvbvb
D. 決策樹案例
咨詢記錄 · 回答於2021-10-24
E. 決策樹演算法原理是什麼
決策樹構造的輸入是一組帶有類別標記的例子，構造的結果是一棵二叉樹或多叉樹。二叉樹的 內部節點(非 葉子節點)一般表示為一個邏輯判斷，如形式為a=aj的邏輯判斷，其中a是屬性，aj是該屬性的所有取值：樹的邊是邏輯判斷的分支結果。
多叉樹(ID3)的內部結點是屬性，邊是該屬性的所有取值，有幾個 屬性值就有幾條邊。樹的葉子節點都是類別標記。
由於數據表示不當、有雜訊或者由於決策樹生成時產生重復的子樹等原因，都會造成產生的決策樹過大。
因此，簡化決策樹是一個不可缺少的環節。尋找一棵最優決策樹，主要應解決以下3個最優化問題：①生成最少數目的葉子節點；②生成的每個葉子節點的深度最小；③生成的決策樹葉子節點最少且每個葉子節點的深度最小。
(5)決策樹演算法實例擴展閱讀：
決策樹演算法的優點如下：
（1）分類精度高；
（2）生成的模式簡單；
（3）對雜訊數據有很好的健壯性。
因而是目前應用最為廣泛的歸納推理演算法之一，在 數據挖掘中受到研究者的廣泛關注。
F. 畢業設計題目是（選用決策樹演算法的數據挖掘實例分析與設計）
應用遺傳演算法和決策樹演算法在數據挖掘中的比較
賈修一 MG0533024
(南京大學 計算機科學與技術系, 江蘇省南京市 210093)
A Comparision between the Genetic Algorithms and Decision Tree For Data
Mining
Abstract: This chapter introces the application with the genetic algorithms and ID3 for the data mining, choose
the better algorithm to classifier the given data sets through.the comparision between the two algorithms. And
analyzing the results of the experiment as well as reasons.
Key words: genetic algrithms; data ming; decision Tree
摘 要: 對訓練數據分別採用遺傳演算法和決策樹演算法進行數據挖掘,通過比較兩者實驗得出的結果,來選
擇更適合本數據集的演算法進行分類,並分析實驗結果及原因.
關鍵詞: 遺傳演算法;數據挖掘;決策樹演算法
1. 數據的描述
數據屬性有139351維,每個屬性的取值為0或1,分類標識只有兩類:A和I.數據的維數太高,在數
據預處理階段最好做屬性的約簡,進行降維的處理.
(1)數據維數太高,易造成一定的維數災難,使得分類挖掘時間過長.
(2)數據龐大,肯定有些噪音數據.
2.演算法的設計
為了提高最後分類的精確度,特設計了兩種方法進行比較,從中選出一種精確度高的方法.第一種是根
據數據的特點,每個屬性只取值0和1,所以進行屬性約簡的時候採用遺傳演算法.遺傳演算法的優點是可以對
大規模的數據進行一定的屬性約簡.
2.1 遺傳演算法描述:
(1) 遺傳演算法的步驟是編碼,選擇,交叉,變異.通過模仿自然界中的遺傳進化原理,來對數據進行
處理.而遺傳演算法的好壞取決於適應度函數的選擇,進化的次數,和交叉變異的合理性和概率性等,所以要
想設計一個合適的遺傳演算法必須經過大量的實驗.
(2) 就訓練數據而言,對每一維屬性的取值,在類標識一定的條件下,取1和取0的概率之間有個絕
對值差α1,α2,該差越大,說明該屬性的重要程度越高.同時還要考慮對同一維屬性,不論最終類標識是
什麼,取值都相同的話,則該屬性可以被認為是無效的屬性,對最後的分類沒有影響,所以適應度函數取對
每一維屬性的α1,α2的熵,熵越大,則屬性的重要程度就越低.
(3) 編碼階段,就把每一位屬性做為一個長度為139351的染色體的一個基因,1表示選擇該屬性,0
表示不選擇該屬性.隨機初始化8個種群,按照適應度函數的定義,從中選取4個適應度函數最小的染色體
做為父代.
(4) 將選出的父代進行交叉操作,因為是降維操作,所以交叉就是取兩個染色體之間隔位進行AND(與)
操作,變異就是按照一定的概率,在139351維上隨機的100位進行非操作,即:0變為1,1變為0.依次又
產生4個後代,結合原來的4個父代組成新的8個初始種群.進化50次.
然後利用貝葉斯方法進行分類.得到的是一個弱的學習器h,然後利用AdaBoost方法進行強化學習分類器.
2.2 AdaBoost演算法描述:
(1) 給定訓練集(x1,y1),(x2,y2),…,(xm,ym)m個.
(2) yi∈{-1,+1},實例xi∈X的正確標識.
(3) for t=1,…,T
2
{
構造{1,…,m}上的分布Dt,找出弱分類器 ht:X->{-1,+1},
同時在Dt產生很小的錯誤εt:
εt=PrDt[ht(xi)≠yi]
}
(4)構造 Dt,D1(i)=1/m
Dt+1(i)= Dt/Zt*exp(-αt*yi*ht(xi))//(注:yi和ht(xi)只能取值於{-1,+1})
其中Zt是歸一化因子(使Dt+1為分布)
αt=1/2*㏑((1-εt)/ εt)>0
(5)輸出最終分類器:Hfinal(x)=sign(∑αt*ht(x)).
第二種方法就是直接使用決策樹方法(ID3演算法)進行分類.求出每一維屬性的的信息增益,建立一棵
決策樹,利用決策樹來進行分類.
2.3 決策樹演算法(ID3)
(1)創建節點N;
(2)if samples都在同一個類C then
{
返回N作為葉結點,以類C標識;
}
(3)if attribut_list為空 then
{
返回N作為葉結點,標記為samples中最普通的類;
}
(4) 選擇attribute_list中具有最高信息增益的屬性test_attribute;標記節點N為test_attribute;
(5) for each test_attribute中的已知值a
由節點N長出一個條件為test_attribute=a的分枝;
(6) 設s是samples中test_attribute=a的樣本的集合;
(7) if s為空 then
加上一個樹葉,標記weisamples中最普通的類;
else
加上一個由ID3(s,attribute_list-test_attribute)返回的節點;
3. 實驗分析
就第一種方法:通過實驗,在進化次數上選取50次,使得維數約簡到1500維左右時得到的分類效果最
好,但由於種群是隨機產生的,所以在未進行boosting強化時正確率在60～85%之間,不是很穩定,但是符
合弱分類器的要求,即只要正確率超過50%就行,在進行boosting後,正確率能超過80%,但可能是數據進
行約簡的不好或進行迭代的次數選取不太合適,正確率卻沒有ID3的高.就本數據集而言,由於最終標識只
有2個,所以比較適合使用遺傳演算法和Adaboost進行訓練.正確率不高主要問題應該在:
(1)遺傳演算法的適應度函數沒有選好,不同的編碼方式對應不同的適應度函數取法,就本例而言,二進
制編碼方式應該是可以的,就是在對適應度函數取的時候沒有一個合適的數據表示,只好利用了熵的概念,
但在實際意義上感覺效果並不是很好.屬性約簡後正確率不高,這應該是最主要的原因.
(2)交叉變異的方式或許有問題,但是不是主要問題,只要適應度函數選好,也就是選擇操作正確的話,
這兩步操作對最終結果應該影響不大.
(3)進化次數的改進,通過實驗,考慮最後的正確率和運行時間,發現在進化50次和約簡到1500維時
賈修一:應用遺傳演算法和決策樹演算法在數據挖掘中的比較3
效果最好.但隨著適應度函數的不同,進化次數也不同.從理論上說,進化次數越多,效果也應該越好,最
終達到一個最優解,但同時要避免得到局部最優解,就需要對傳統的遺傳演算法進行改進,避免早熟問題.在
此就不討論.
(4)利用貝葉斯分類得到的弱學習器,在格式上並不和Adaboost完全適應,所以在應用的時候效果不
是很好,這也取決於迭代的次數和訓練樣集的選取.
就決策樹方法,對這么多維的屬性在某種意義上說並不合適,但就對本實驗給定的訓練樣例集而言,通
過建樹,只要6個結點就可以,而且正確率超過90%,所以,根據不同的數據集採用不同的方法得到的正確
率是不一樣的.所以在某種程度上說,奧卡姆剃刀原理是正確的.
由於時間有限,沒有對第一種方法進行一定的改進和進行其他方法的實驗,故最終採用ID3演算法進行分
類,採用前100個數據進行訓練,後10個進行測試,錯誤的只有1個.採用前80個數據進行訓練,後30
個進行測試的時候只有2個分類錯誤.正確率自測還是可以的.
4. 總結和感謝
通過本次實驗,最大的收獲就是採用了兩種不同的方法進行了實驗比較,雖然自己原先設計的演算法沒有
得到期望中的效果,並最終採用了其他的演算法,但是通過實驗,我對遺傳演算法和AdaBoost強化弱學習器方法
等有了更深的了解,也明白對不同的數據,是沒有一種萬能通用的解法的.以後會繼續改進自己的演算法,爭
取取得好的效果.最後感謝老師能提供這次實驗的數據.
G. 決策樹演算法的典型演算法
決策樹的典型演算法有ID3，C4.5，CART等。
國際權威的學術組織，數據挖掘國際會議ICDM （the IEEE International Conference on Data Mining）在2006年12月評選出了數據挖掘領域的十大經典演算法中，C4.5演算法排名第一。C4.5演算法是機器學習演算法中的一種分類決策樹演算法,其核心演算法是ID3演算法。C4.5演算法產生的分類規則易於理解，准確率較高。不過在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，在實際應用中因而會導致演算法的低效。
決策樹演算法的優點如下：
（1）分類精度高；
（2）生成的模式簡單；
（3）對雜訊數據有很好的健壯性。
因而是目前應用最為廣泛的歸納推理演算法之一，在數據挖掘中受到研究者的廣泛關注。
H. 目前比較流行的決策樹演算法有哪些
ID3演算法，最簡單的決策樹
c4.5 是最經典的決策樹演算法，選擇信息差異率最大的作為分割屬性。
CART演算法，適合用於回歸
I. 數據挖掘中決策樹演算法
決策樹演算法有很多種，比喻有ID3（利用信息增益來選擇決策變數），C4.5（利用信息增益率來選擇決策變數），CART，chain以及quest等，不同的決策樹適用情況也不一樣，有機會可以多多交流。。
J. 常見決策樹分類演算法都有哪些
在機器學習中，有一個體系叫做決策樹，決策樹能夠解決很多問題。在決策樹中，也有很多需要我們去學習的演算法，要知道，在決策樹中，每一個演算法都是實用的演算法，所以了解決策樹中的演算法對我們是有很大的幫助的。在這篇文章中我們就給大家介紹一下關於決策樹分類的演算法，希望能夠幫助大家更好地去理解決策樹。
1.C4.5演算法
C4.5演算法就是基於ID3演算法的改進，這種演算法主要包括的內容就是使用信息增益率替換了信息增益下降度作為屬性選擇的標准；在決策樹構造的同時進行剪枝操作；避免了樹的過度擬合情況；可以對不完整屬性和連續型數據進行處理；使用k交叉驗證降低了計算復雜度；針對數據構成形式，提升了演算法的普適性等內容，這種演算法是一個十分使用的演算法。
2.CLS演算法
CLS演算法就是最原始的決策樹分類演算法，基本流程是，從一棵空數出發，不斷的從決策表選取屬性加入數的生長過程中，直到決策樹可以滿足分類要求為止。CLS演算法存在的主要問題是在新增屬性選取時有很大的隨機性。
3.ID3演算法
ID3演算法就是對CLS演算法的最大改進是摒棄了屬性選擇的隨機性，利用信息熵的下降速度作為屬性選擇的度量。ID3是一種基於信息熵的決策樹分類學習演算法，以信息增益和信息熵，作為對象分類的衡量標准。ID3演算法結構簡單、學習能力強、分類速度快適合大規模數據分類。但同時由於信息增益的不穩定性，容易傾向於眾數屬性導致過度擬合，演算法抗干擾能力差。
3.1.ID3演算法的優缺點
ID3演算法的優點就是方法簡單、計算量小、理論清晰、學習能力較強、比較適用於處理規模較大的學習問題。缺點就是傾向於選擇那些屬性取值比較多的屬性，在實際的應用中往往取值比較多的屬性對分類沒有太大價值、不能對連續屬性進行處理、對雜訊數據比較敏感、需計算每一個屬性的信息增益值、計算代價較高。
3.2.ID3演算法的核心思想
根據樣本子集屬性取值的信息增益值的大小來選擇決策屬性，並根據該屬性的不同取值生成決策樹的分支，再對子集進行遞歸調用該方法，當所有子集的數據都只包含於同一個類別時結束。最後，根據生成的決策樹模型，對新的、未知類別的數據對象進行分類。
在這篇文章中我們給大家介紹了決策樹分類演算法的具體內容，包括有很多種演算法。從中我們不難發現決策樹的演算法都是經過不不斷的改造趨於成熟的。所以說，機器學習的發展在某種程度上就是由於這些演算法的進步而來的。