-
決策樹算法
鎖定
決策樹算法是一種逼近離散函數值的方法。它是一種典型的分類方法,首先對數據進行處理,利用歸納算法生成可讀的規則和決策樹,然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。
決策樹方法最早產生於上世紀60年代,到70年代末。由J Ross Quinlan提出了ID3算法,此算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5算法在ID3算法的基礎上進行了改進,對於預測變量的缺值處理、剪枝技術、派生規則等方面作了較大改進,既適合於分類問題,又適合於迴歸問題。
決策樹算法構造決策樹來發現數據中藴涵的分類規則.如何構造精度高、規模小的決策樹是決策樹算法的核心內容。決策樹構造可以分兩步進行。第一步,決策樹的生成:由訓練樣本集生成決策樹的過程。一般情況下,訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的,用於數據分析處理的數據集。第二步,決策樹的剪枝:決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程,主要是用新的樣本數據集(稱為測試數據集)中的數據校驗決策樹生成過程中產生的初步規則,將那些影響預衡準確性的分枝剪除。
- 中文名
- 決策樹算法
- 釋 義
- 一種典型的分類方法
- 典型算法
- ID3,C4.5,CART
- 基本思想
- 樹以代表訓練樣本的單個結點開始
決策樹算法簡介
決策樹(decision tree)是一種基本的分類與迴歸方法。決策樹模型呈樹形結構,在分類問題中,表示基於特徵對實例進行分類的過程。它可以認為是if-then規則的集合,也可以認為是定義在特徵空間與類空間上的條件概率分佈。
其主要優點是模型具有可讀性,分類速度快。學習時,利用訓練數據,根據損失函數最小化的原則建立決策樹模型。預測時,對新的數據,利用決策樹模型進行分類。
決策樹算法決策樹學習
目標:根據給定的訓練數據集構建一個決策樹模型,使它能夠對實例進行正確的分類。決策樹學習本質上是從訓練數據集中歸納出一組分類規則。能對訓練數據進行正確分類的決策樹可能有多個,可能沒有。在選擇決策樹時,應選擇一個與訓練數據矛盾較小的決策樹,同時具有很好的泛化能力;而且選擇的條件概率模型應該不僅對訓練數據有很好的擬合,而且對未知數據有很好的預測。
[1]
損失函數:通常是正則化的極大似然函數
策略:是以損失函數為目標函數的最小化
決策樹學習的算法通常是一個遞歸地選擇最優特徵,並根據該特徵對訓練數據進行分割,使得對各個子數據集有一個最好的分類的過程。包含特徵選擇、決策樹的生成和決策樹的剪枝過程。
目的:將樹變得更簡單,從而使它具有更好的泛化能力。
步驟:去掉過於細分的葉結點,使其回退到父結點,甚至更高的結點,然後將父結點或更高的結點改為新的葉結點。
決策樹的生成對應模型的局部選擇,決策樹的剪枝對應於模型的全局選擇。決策樹的生成只考慮局部最優,決策樹的剪枝則考慮全局最優。
特徵選擇:
如果特徵數量很多,在決策樹學習開始時對特徵進行選擇,只留下對訓練數據有足夠分類能力的特徵。(例如把名字不作為一個特徵進行選擇)
決策樹算法典型算法
國際權威的學術組織,數據挖掘國際會議ICDM (the IEEE International Conference on Data Mining)在2006年12月評選出了數據挖掘領域的十大經典算法中,C4.5算法排名第一。C4.5算法是機器學習算法中的一種分類決策樹算法,其核心算法是ID3算法。C4.5算法產生的分類規則易於理解,準確率較高。不過在構造樹的過程中,需要對數據集進行多次的順序掃描和排序,在實際應用中因而會導致算法的低效。
[2]
決策樹算法的優點如下:
(1)分類精度高;
(2)生成的模式簡單;
(3)對噪聲數據有很好的健壯性。
決策樹算法基本思想
1)樹以代表訓練樣本的單個結點開始。
2)如果樣本都在同一個類.則該結點成為樹葉,並用該類標記。
3)否則,算法選擇最有分類能力的屬性作為決策樹的當前結點.
4)根據當前決策結點屬性取值的不同,將訓練樣本數據集tlI分為若干子集,每個取值形成一個分枝,有幾個取值形成幾個分枝。勻針對上一步得到的一個子集,重複進行先前步驟,遞4'I形成每個劃分樣本上的決策樹。一旦一個屬性出現在一個結點上,就不必在該結點的任何後代考慮它。
5)遞歸劃分步驟僅當下列條件之一成立時停止:
①給定結點的所有樣本屬於同一類。
②沒有剩餘屬性可以用來進一步劃分樣本.在這種情況下.使用多數表決,將給定的結點轉換成樹葉,並以樣本中元組個數最多的類別作為類別標記,同時也可以存放該結點樣本的類別分佈,
決策樹算法構造方法
決策樹構造的輸入是一組帶有類別標記的例子,構造的結果是一棵二叉樹或多叉樹。二叉樹的內部節點(非葉子節點)一般表示為一個邏輯判斷,如形式為a=aj的邏輯判斷,其中a是屬性,aj是該屬性的所有取值:樹的邊是邏輯判斷的分支結果。多叉樹(ID3)的內部結點是屬性,邊是該屬性的所有取值,有幾個屬性值就有幾條邊。樹的葉子節點都是類別標記。
[3]
由於數據表示不當、有噪聲或者由於決策樹生成時產生重複的子樹等原因,都會造成產生的決策樹過大。因此,簡化決策樹是一個不可缺少的環節。尋找一棵最優決策樹,主要應解決以下3個最優化問題:①生成最少數目的葉子節點;②生成的每個葉子節點的深度最小;③生成的決策樹葉子節點最少且每個葉子節點的深度最小。
決策樹算法分類與迴歸樹模型
同樣由特徵選擇、樹的生成及剪枝組成,既可以用於分類也可以用於迴歸。
CART算法由以下兩步組成
(1)決策樹生成:基於訓練數據集生成決策樹,生成的決策樹要儘量大;