基本定義
決策樹算法是一種逼近離散函式值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。
典型算法
決策樹的典型算法有ID3，C4.5，CART等。
國際權威的學術組織，數據挖掘國際會議ICDM （the IEEE International Conference on Data Mining）在2006年12月評選出了數據挖掘領域的十大經典算法中，C4.5算法排名第一。C4.5算法是機器學習算法中的一種分類決策樹算法,其核心算法是ID3算法。C4.5算法產生的分類規則易於理解，準確率較高。不過在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，在實際套用中因而會導致算法的低效。
決策樹算法的優點如下：
（1）分類精度高；
（2）生成的模式簡單；
（3）對噪聲數據有很好的健壯性。
因而是目前套用最為廣泛的歸納推理算法之一，在數據挖掘中受到研究者的廣泛關注。
基本思想
決策樹方法最早產生於上世紀60年代，到70年代末。由J Ross Quinlan提出了ID3算法，此算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5算法在ID3算法的基礎上進行了改進，對於預測變數的缺值處理、剪枝技術、派生規則等方面作了較大改進，既適合於分類問題，又適合於回歸問題。
決策樹算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用於數據分析處理的數據集。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數扼集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡準確性的分枝剪除。
1）樹以代表訓練樣本的單個結點開始。
2）如果樣本都在同一個類．則該結點成為樹葉，並用該類標記。
3）否則，算法選擇最有分類能力的屬性作為決策樹的當前結點．
4）根據當前決策結點屬性取值的不同，將訓練樣本數據集tlI分為若干子集，每個取值形成一個分枝，有幾個取值形成幾個分枝。勻針對上一步得到的一個子集，重複進行先前步驟，遞4'I形成每個劃分樣本上的決策樹。一旦一個屬性出現在一個結點上，就不必在該結點的任何後代考慮它。
5）遞歸劃分步驟僅當下列條件之一成立時停止：
①給定結點的所有樣本屬於同一類。
②沒有剩餘屬性可以用來進一步劃分樣本．在這種情況下．使用多數表決，將給定的結點轉換成樹葉，並以樣本中元組個數最多的類別作為類別標記，同時也可以存放該結點樣木的類別分布，
③如果某一分枝tc，七砰如恤卜a*沒有樣本，則以樣本的多數類創建一個樹葉。
構造方法
決策樹構造的輸入是一組帶有類別標記的例子，構造的結果是一棵二叉樹或多叉樹。二叉樹的內部節點(非葉子節點)一般表示為一個邏輯判斷，如形式為a=aj的邏輯判斷，其中a是屬性，aj是該屬性的所有取值：樹的邊是邏輯判斷的分支結果。多叉樹(ID3)的內部結點是屬性，邊是該屬性的所有取值，有幾個屬性值就有幾條邊。樹的葉子節點都是類別標記。
由於數據表示不當、有噪聲或者由於決策樹生成時產生重複的子樹等原因，都會造成產生的決策樹過大。因此，簡化決策樹是一個不可缺少的環節。尋找一棵最優決策樹，主要應解決以下3個最最佳化問題：①生成最少數目的葉子節點；②生成的每個葉子節點的深度最小；③生成的決策樹葉子節點最少且每個葉子節點的深度最小。
