一、概述

　　決策樹（decision tree）的一個重要任務是為了數據中所蘊含的知識信息，因此決策樹可以使用不熟悉的數據集合，并從中提取出一系列規則，在這些機器根據數據創建規則時，就是機器學習的過程。

二、決策樹的構造

　　決策樹：

　　　　優點：計算復雜度不高， 輸出結果易于理解， 對中間值的缺失不敏感， 可以處理不相關特征數據。

　　　　缺點： 可能會產生過度匹配問題。

　　適用數據類型：數值型和標稱型

　　在構造決策樹時， 我們需要解決的第一個問題就是， 當前數據集上哪個特征在劃分數據分類時起決定性作用。 為了找到決定性的特征， 劃分出最好的結果， 我們必須評估每個特征。 完成測試之后， 原始數據集就被劃分為幾個數據子集。?這些數據子集會分布在第一個決策點的所有分支上；
　　決策樹的一般流程
　　　　1. 收集數據： 可以使用任何方法。
　　　　2. 準備數據： 樹構造算法只適用于標稱型數據， 因此數值型數據必須離散化。
　　　　3. 分析數據： 可以使用任何方法， 構造樹完成之后， 我們應該檢查圖形是否符合預期。
　　　　4. 訓練算法： 構造樹的數據結構。
　　　　5. 測試算法： 使用經驗樹計算錯誤率。
　　　　6. 使用算法： 此步驟可以適用于任何監督學習算法， 而使用決策樹可以更好地理解數據的內在含義。

　　涉及的算法：

　　　　二分法：一些決策樹算法采用二分法劃分數據，

　　　　ID3：?而我們將適用ID3算法劃分數據集?， ID3算法更多信息了解

　　　　C4.5： ID3的一個改進， 比ID3準確率高且快， 可以處理連續值和有缺失值的feature

　　　　CRAT： 使用基尼指數的劃分準則，通過在每個步驟最大限度降低不純潔度， CART能夠處理孤立點以及對空缺值的處理；

　信息增益：

　　劃分數據集的大原則是： 將無序的數據變得更加有序。 我們可以使用多 種方法劃分數據集， 但是每種方法都有各自的優缺點。 組織雜亂無章數據的一種方法就是使用信息論度量信息， 信息論是量化處理信息的分支 科學。 我們可以在劃分數據前后使用信息論量化度量信息的內容。
　　在劃分數據集之前之后信息發生的變化稱為信息增益， 知道如何計算信 息增益， 我們就可以計算每個特征值劃分數據集獲得的信息增益， 獲得 信息增益最高的特征就是最好的選擇。
　熵：
　　為了計算熵（entropy）， 我們需要計算所有類別所有可能值包含的信息期望值， 通過下面的公式得到：
　　

　　符號xi 的信息定義為：

　　其中p(xi)是選擇該分類的概率

　　熵的單位是bit， 用來衡量信息的多少；從計算熵的公式來看：

　　　　變量的不確定性越大， 熵就越大；

　　計算完信息熵后，我們便可以得到數據集的無序程度。我們將對每個特征劃分數據集的結果計算一次信息熵，然后判斷哪個特征劃分數據集是最好的劃分方式（根據信息熵判斷，信息熵越小，說明劃分效果越好）

　　

三、ID3算法

　　選擇屬性判斷節點；

　　信息獲取量（Information Gain）： Gain（A）= Info（D） - Infor_A(D) , 通過A來作為節點分類獲取了多少信息；　　

總結

以上是生活随笔為你收集整理的ML之监督学习算法之分类算法一 ——— 决策树算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。