1基本定義

決策樹演算法是一種逼近離散函數值的方法。它是一種典型的分類方法,首先對數據進行處理,利用歸納演算法生成可讀的規則和決策樹,然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。

2典型演算法

決策樹的典型演算法有ID3,C4.5,CART等;
決策樹演算法的優點如下:
(1)分類精度高;
(2)生成的模式簡單;
(3)對雜訊數據有很好的健壯性。
因而是目前應用最為廣泛的歸納推理演算法之一,在數據挖掘中受到研究者的廣泛關注。

3基本思想

決策樹方法最早產生於上世紀60年代,到70年代末。由J Ross Quinlan提出了ID3演算法,此演算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5演算法在ID3演算法的基礎上進行了改進,對於預測變數的缺值處理、剪枝技術、派生規則等方面作了較大改進,既適合於分類問題,又適合於回歸問題。
決策樹演算法構造決策樹來發現數據中蘊涵的分類規則.如何構造精度高、規模小的決策樹是決策樹演算法的核心內容。決策樹構造可以分兩步進行。第一步,決策樹的生成:由訓練樣本集生成決策樹的過程。一般情況下,訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的,用於數據分析處理的數據集。第二步,決策樹的剪技:決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程,主要是用新的樣本數扼集(稱為測試數據集)中的數據校驗決策樹生成過程中產生的初步規則,將那些影響預衡準確性的分枝剪除。
1)樹以代表訓練樣本的單個結點開始。
2)如果樣本都在同一個類.則該結點成為樹葉,並用該類標記。
3)否則,演算法選擇最有分類能力的屬性作為決策樹的當前結點.
4)根據當前決策結點屬性取值的不同,將訓練樣本數據集tlI分為若干子集,每個取值形成一個分枝,有幾個取值形成幾個分枝。勻針對上一步得到的一個子集,重複進行先前步驟,遞4'I形成每個劃分樣本上的決策樹。一旦一個屬性出現在一個結點上,就不必在該結點的任何後代考慮它。
5)遞歸劃分步驟僅當下列條件之一成立時停止:
①給定結點的所有樣本屬於同一類。
②沒有剩餘屬性可以用來進一步劃分樣本.在這種情況下.使用多數表決,將給定的結點轉換成樹葉,並以樣本中元組個數最多的類別作為類別標記,同時也可以存放該結點樣木的類別分佈,
③如果某一分枝tc,七砰如恤卜a*沒有樣本,則以樣本的多數類創建一個樹葉。

4構造方法

決策樹構造的輸入是一組帶有類別標記的例子,構造的結果是一棵二叉樹或多叉樹。二叉樹的內部節點(非葉子節點)一般表示為一個邏輯判斷,如形式為a=aj的邏輯判斷,其中a是屬性,aj是該屬性的所有取值:樹的邊是邏輯判斷的分支結果。多叉樹(ID3)的內部結點是屬性,邊是該屬性的所有取值,有幾個屬性值就有幾條邊。樹的葉子節點都是類別標記。
由於數據表示不當、有雜訊或者由於決策樹生成時產生重複的子樹等原因,都會造成產生的決策樹過大。因此,簡化決策樹是一個不可缺少的環節。尋找一棵最優決策樹,主要應解決以下3個最優化問題:①生成最少數目的葉子節點;②生成的每個葉子節點的深度最小;③生成的決策樹葉子節點最少且每個葉子節點的深度最小。
上一篇[常規思維]    下一篇 [關聯規則]

相關評論

同義詞:暫無同義詞