決策樹算法是一種逼近離散函數值的方法，是一種典型的分類方法。
決策樹算法構造決策樹來發現數據中蘊涵的分類規則。如何構造精度高，規模小的決策樹是決策樹算法的核心內容。一般情況下分兩步進行，
1.決策樹的生成。
2.決策樹的剪枝。（對上一個階段生成的決策樹進行檢驗，校正和修下的過程，方法：使用測試數據集校驗1中生成的決策樹，將那些影響準確性的分枝剪除）
典型算法
ID3算法，此算法目的在于減少樹的深度。但是忽略了葉子數目的研究。
C4.5算法，在ID3算法的基礎上進行了改進，對于預測變量的缺值處理，剪枝技術，派生規則等方面做了較大的改進，既適合于分類問題，又適合于回歸問題。總結：產生的分類規則易于理解，準確率較高。不過在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，在實際應用中會導致算法低效。
決策樹算法的優點如下：
1.分類精度高；
2.生成的模式簡單；
3.對噪聲數據有很好的健壯性。
以上為概念總結。
——————————————————————————————————————————————————————————
-信息增益
在劃分數據集之前后信息發生的變化稱之為信息增益，計算每個特征值劃分數據集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。
計算方法（香農熵）
熵定義為信息的期望值。計算公式如下：
符號xi的信息定義為l(xi)=-log2p(xi)，其中p(xi)是選擇該分類的概率。（各分類在總實例中得比例）
所有類別所有可能值包含的信息期望值H=-∑ni=1p(xi)log2p(xi),其中n分類的數目。
-劃分數據集
對每個特征劃分數據集的結果計算一次信息熵，然后判斷按照哪個特征劃分數據集是最好的劃分方式。
增益=元數據的熵-按特征量劃分的熵 -->增益越大 劃分越優
-遞歸構建決策樹
工作原理如下：
1.得到原始數據集
2.基于好的屬性劃分數據集
3.特征值多于兩個的情況下。可能存在大于兩個分支的數據集劃分。第一次劃分后，數據被向下傳遞到樹分支的下一個節點，在這個節點上再次劃分數據。
遞歸的結束條件：1.遍歷完所有劃分數據集的屬性 2 每個分支下得所有實例都具有相同的分類。
后續：改進算法的總結和代碼整理
|
