基本思想
決策樹方法最早産生于上世紀60年代，到70年代末。由J Ross Quinlan提出了ID3算法，此算法的目的在于減少樹的深度。但是忽略了葉子數目的研究。C4.5算法在ID3算法的基礎上進行了改進，對于預測變量的缺值處理、剪枝技術、派生規則等方面作了較大改進，既适合于分類問題，又适合于回歸問題。
決策樹算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹算法的核心内容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有曆史的、有一定綜合程度的，用于數據分析處理的數據集。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數扼集（稱為測試數據集）中的數據校驗決策樹生成過程中産生的初步規則，将那些影響預衡準确性的分枝剪除。
1、樹以代表訓練樣本的單個結點開始。
2、如果樣本都在同一個類．則該結點成為樹葉，并用該類标記。
3、否則，算法選擇最有分類能力的屬性作為決策樹的當前結點．
4、根據當前決策結點屬性取值的不同，将訓練樣本數據集tlI分為若幹子集，每個取值形成一個分枝，有幾個取值形成幾個分枝。勻針對上一步得到的一個子集，重複進行先前步驟，遞4'I形成每個劃分樣本上的決策樹。一旦一個屬性出現在一個結點上，就不必在該結點的任何後代考慮它。
5、遞歸劃分步驟僅當下列條件之一成立時停止：
①給定結點的所有樣本屬于同一類。
②沒有剩餘屬性可以用來進一步劃分樣本．在這種情況下．使用多數表決，将給定的結點轉換成樹葉，并以樣本中元組個數最多的類别作為類别标記，同時也可以存放該結點樣木的類别分布，
③如果某一分枝tc，沒有滿足該分支中已有分類的樣本，則以樣本的多數類創建一個樹葉。
典型算法
決策樹的典型算法有ID3，C4.5，CART等。
國際權威的學術組織，數據挖掘國際會議ICDM（the IEEE International Conference on Data Mining）在2006年12月評選出了數據挖掘領域的十大經典算法中，C4.5算法排名第一。C4.5算法是機器學習算法中的一種分類決策樹算法,其核心算法是ID3算法。C4.5算法産生的分類規則易于理解，準确率較高。不過在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，在實際應用中因而會導緻算法的低效。
決策樹算法的優點如下：
（1）分類精度高；
（2）生成的模式簡單；
（3）對噪聲數據有很好的健壯性。
因而是目前應用最為廣泛的歸納推理算法之一，在數據挖掘中受到研究者的廣泛關注。
構造方法
構造決策樹的關鍵步驟是分裂屬性。所謂分裂屬性就是在某個節點處按照某一特征屬性的不同劃分構造不同的分支，其目标是讓各個分裂子集盡可能地“純”。盡可能“純”就是盡量讓一個分裂子集中待分類項屬于同一類别。分裂屬性分為三種不同的情況：
1、屬性是離散值且不要求生成二叉決策樹。此時用屬性的每一個劃分作為一個分支。
2、屬性是離散值且要求生成二叉決策樹。此時使用屬性劃分的一個子集進行測試，按照“屬于此子集”和“不屬于此子集”分成兩個分支。
3、屬性是連續值。此時确定一個值作為分裂點split_point，按照>split_point和<=split_point生成兩個分支。
構造決策樹的關鍵性内容是進行屬性選擇度量，屬性選擇度量是一種選擇分裂準則，是将給定的類标記的訓練集合的數據劃分D“最好”地分成個體類的啟發式方法，它決定了拓撲結構及分裂點split_point的選擇。
屬性選擇度量算法有很多，一般使用自頂向下遞歸分治法，并采用不回溯的貪心策略。
分類與回歸樹模型：
同樣由特征選擇、樹的生成及剪枝組成，既可以用于分類也可以用于回歸。
CART算法由以下兩步組成
（1）決策樹生成：基于訓練數據集生成決策樹，生成的決策樹要盡量大；
（2）決策樹剪枝：用驗證數據集對己生成的樹進行剪枝并選擇最優子樹，這時用損失函數最小作為剪枝的标準。
