小白自學(xué)路上的備忘記錄。。。

參考：
決策樹(分類樹、回歸樹)
決策樹:這個博客的圖真好看，通俗易懂。哈哈
決策樹詳解

引言

決策樹（Decision Tree）是一種有監(jiān)督學(xué)習(xí)算法，常用于分類和回歸。本文僅討論分類問題。

決策樹.png

一、決策樹模型

決策樹模型是運用于分類以及回歸的一種樹結(jié)構(gòu)。決策樹由節(jié)點和有向邊組成，一般一棵決策樹包含一個根節(jié)點、若干內(nèi)部節(jié)點和若干葉節(jié)點。決策樹的決策過程需要從決策樹的根節(jié)點開始，待測數(shù)據(jù)與決策樹中的特征節(jié)點進行比較，并按照比較結(jié)果選擇選擇下一比較分支，直到葉子節(jié)點作為最終的決策結(jié)果。

• 內(nèi)部節(jié)點：對應(yīng)于一個屬性測試 。每個內(nèi)部節(jié)點為一個判斷條件，并且包含數(shù)據(jù)集中滿足從根節(jié)點到該節(jié)點所有條件的數(shù)據(jù)的集合。根據(jù)內(nèi)部結(jié)點的判斷條件測試結(jié)果，內(nèi)部節(jié)點對應(yīng)的數(shù)據(jù)的集合別分到兩個或多個子節(jié)點中
• 葉節(jié)點：葉節(jié)點為最終的類別，被包含在該葉節(jié)點的數(shù)據(jù)屬于該類別 ，即對應(yīng)于決策結(jié)果
• 根節(jié)點包：包含數(shù)據(jù)集中的所有數(shù)據(jù)的集合
• 每個節(jié)點包括的樣本集合根據(jù)屬性測試的結(jié)果被劃分到子節(jié)點中；
• 根節(jié)點到每個葉節(jié)點的路徑對應(yīng)對應(yīng)了一個判定測試路徑；

簡而言之，決策樹是一個利用樹的模型進行決策的多分類模型

二、決策樹學(xué)習(xí)

1.特征選擇

為了找到最優(yōu)的劃分特征，我們需要先了解一些信息論的知識：

• 純度
• 信息熵(information entropy)
• 信息增益(information gain)
• 信息增益率(information gain ratio)
• 基尼指數(shù)(Gini index)

純度：
你可以把決策樹的構(gòu)造過程理解成為尋找純凈劃分的過程。數(shù)學(xué)上，我們可以用純度來表示，純度換一種方式來解釋就是讓目標(biāo)變量的分歧最小

信息熵：表示信息的不確定度
在信息論中，隨機離散事件出現(xiàn)的概率存在著不確定性。為了衡量這種信息的不確定性，信息學(xué)之父香農(nóng)引入了信息熵的概念.
當(dāng)不確定性越大時，它所包含的信息量也就越大，信息熵也就越高。
信息熵越大，純度越低。當(dāng)集合中的所有樣本均勻混合時，信息熵最大，純度最低

信息熵.png

經(jīng)典的 “不純度”的指標(biāo)有三種，分別是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指數(shù)（Cart 算法）
信息增益：
信息增益指的就是劃分可以帶來純度的提高，信息熵的下降。它的計算公式，是父親節(jié)點的信息熵減去所有子節(jié)點的信息熵。
信息增益率
信息增益率 = 信息增益 / 屬性熵
基尼指數(shù)
基尼指數(shù)（基尼不純度）：表示在樣本集合中一個隨機選中的樣本被分錯的概率。
即 基尼指數(shù)（基尼不純度）= 樣本被選中的概率 * 樣本被分錯的概率
基尼系數(shù)的性質(zhì)與信息熵一樣：度量隨機變量的不確定度的大??；
G 越大，數(shù)據(jù)的不確定性越高；
G 越小，數(shù)據(jù)的不確定性越低；
G = 0，數(shù)據(jù)集中的所有樣本都是同一類別
詳細參考：機器學(xué)習(xí)——基尼指數(shù)

2.決策樹生成

決策樹生成.png

2.1 ID3

ID3 算法是建立在奧卡姆剃刀（用較少的東西，同樣可以做好事情）的基礎(chǔ)上：越是小型的決策樹越優(yōu)于大的決策樹
ID3算法的核心是在決策樹各個節(jié)點上根據(jù)信息增益來選擇進行劃分的特征，然后遞歸地構(gòu)建決策樹。算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間。

具體方法：

• 1.從根節(jié)點開始，初始化特征集合和數(shù)據(jù)集合
• 2.計算數(shù)據(jù)集合信息熵和所有特征的條件熵，選擇信息增益最大的特征作為當(dāng)前決策節(jié)點；
• 3.由該特征的不同取值建立子節(jié)點；更新數(shù)據(jù)集合和特征集合（刪除上一步使用的特征，并按照特征值來劃分不同分支的數(shù)據(jù)集合）；
• 4.重復(fù) 2，3 兩步，若子集值包含單一特征，則為分支葉子節(jié)點，即到所有特征的信息增益都很小或者沒有特征可以選擇為止，得到最終的決策樹

ID3的局限：

• 沒有剪枝，容易過擬合；
• 采用信息增益作為選擇最優(yōu)劃分特征的標(biāo)準(zhǔn)，然而信息增益會偏向那些取值較多的特征，類似“編號”的特征其信息增益接近于 1(這也是C4.5采用信息增益率的原因)；
• 只能用于處理離散分布的特征；
• 沒有考慮缺失值

2.2 C4.5

C4.5與ID3相似，但大的特點是克服了 ID3 對特征數(shù)目的偏重這一缺點，引入信息增益率來作為分類標(biāo)準(zhǔn)。

C4.5的實現(xiàn)基于ID3的改進：

• 用信息增益率來選擇劃分特征，克服了用信息增益選擇的不足
• 在構(gòu)造樹的過程中進行剪枝（引入悲觀剪枝策略進行后剪枝）；
• 將連續(xù)特征離散化，假設(shè) n 個樣本的連續(xù)特征 A 有 m 個取值，C4.5 將其排序并取相鄰兩樣本值的平均數(shù)共 m-1 個劃分點，分別計算以該劃分點作為二元分類點時的信息增益，并選擇信息增益最大的點作為該連續(xù)特征的二元離散分類點；
• 缺失值進行處理
  1.在特征值缺失的情況下進行劃分特征的選擇？（即如何計算特征的信息增益率）答：對于具有缺失值特征，用沒有缺失的樣本子集所占比重來折算；
  2.選定該劃分特征，對于缺失該特征值的樣本如何處理？（即到底把這個樣本劃分到哪個結(jié)點里）答：樣本同時劃分到所有子節(jié)點，不過要調(diào)整樣本的權(quán)重值，其實也就是以不同概率劃分到不同節(jié)點中。

信息增益率對可取值較少的特征有所偏好（分母越小，整體越大），因此 C4.5 并不是直接用增益率最大的特征進行劃分，而是使用一個啟發(fā)式方法：先從候選劃分特征中找到信息增益高于平均值的特征，再從中選擇增益率最高的。

C4.5的局限：

• 剪枝策略可以再優(yōu)化；
• C4.5 用的是多叉樹，用二叉樹效率更高；
• C4.5 只能用于分類；
• C4.5 使用的熵模型擁有大量耗時的對數(shù)運算，連續(xù)值還有排序運算；
• C4.5 在構(gòu)造樹的過程中，對數(shù)值屬性值需要按照其大小進行排序，從中選擇一個分割點，所以只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時，程序無法運行。

2.3 CART

ID3 和 C4.5 生成的決策樹分支、規(guī)模都比較大，CART 算法的二分法可以簡化決策樹的規(guī)模，提高生成決策樹的效率。
CART(classificationandregressiontree),分類回歸樹算法，既可用于分類也可用于回歸，在這一部分我們先主要將其分類樹的生成。區(qū)別于ID3和C4.5,CART假設(shè)決策樹是二叉樹，內(nèi)部節(jié)點特征的取值為“是”和“否”，左分支為取值為“是”的分支，右分支為取值為”否“的分支。這樣的決策樹等價于遞歸地二分每個特征，將輸入空間(即特征空間)劃分為有限個單元。
CART的分類樹用基尼指數(shù)來選擇最優(yōu)特征的最優(yōu)劃分點，具體過程如下

• 1.從根節(jié)點開始，對節(jié)點計算現(xiàn)有特征的基尼指數(shù)，對每一個特征，例如A，再對其每個可能的取值如a,根據(jù)樣本點對A=a的結(jié)果的”是“與”否“劃分為兩個部分，利用Gini(D,A=a)進行計算；
• 2.在所有可能的特征A以及該特征所有的可能取值a中，選擇基尼指數(shù)最小的特征及其對應(yīng)的取值作為最優(yōu)特征和最優(yōu)切分點。然后根據(jù)最優(yōu)特征和最優(yōu)切分點，將本節(jié)點的數(shù)據(jù)集二分，生成兩個子節(jié)點
• 3.對兩個字節(jié)點遞歸地調(diào)用上述步驟，直至節(jié)點中的樣本個數(shù)小于閾值，或者樣本集的基尼指數(shù)小于閾值，或者沒有更多特征后停止；
• 4.生成CART分類樹；

3.決策樹剪枝

剪枝就是給決策樹瘦身，這一步想實現(xiàn)的目標(biāo)就是，不需要太多的判斷，同樣可以得到不錯的結(jié)果。之所以這么做，是為了防止“過擬合”（Overfitting）現(xiàn)象的發(fā)生。
過擬合：指的是模型的訓(xùn)練結(jié)果“太好了”，以至于在實際應(yīng)用的過程中，會存在“死板”的情況，導(dǎo)致分類錯誤。
欠擬合：指的是模型的訓(xùn)練結(jié)果不理想.
剪枝的方法：

• 預(yù)剪枝：在決策樹構(gòu)造時就進行剪枝。方法是，在構(gòu)造的過程中對節(jié)點進行評估，如果對某個節(jié)點進行劃分，在驗證集中不能帶來準(zhǔn)確性的提升，那么對這個節(jié)點進行劃分就沒有意義，這時就會把當(dāng)前節(jié)點作為葉節(jié)點，不對其進行劃分。那么怎么測量泛化精度，就是留出一部分訓(xùn)練數(shù)據(jù)當(dāng)做測試集，每次劃分前比較劃分前后的測試集預(yù)測精度。
  • 優(yōu)點：降低了過擬合風(fēng)險，降低了訓(xùn)練所需的時間。
  • 缺點：預(yù)剪枝是一種貪心操作，可能有些劃分暫時無法提升精度，但是后續(xù)劃分可以提升精度。故產(chǎn)生了欠擬合的風(fēng)險。
• 后剪枝：在生成決策樹之后再進行剪枝。通常會從決策樹的葉節(jié)點開始，逐層向上對每個節(jié)點進行評估。如果剪掉這個節(jié)點子樹，與保留該節(jié)點子樹在分類準(zhǔn)確性上差別不大，或者剪掉該節(jié)點子樹，能在驗證集中帶來準(zhǔn)確性的提升，那么就可以把該節(jié)點子樹進行剪枝。方法是：用這個節(jié)點子樹的葉子節(jié)點來替代該節(jié)點，類標(biāo)記為這個節(jié)點子樹中最頻繁的那個類。
  • 優(yōu)先：降低過擬合風(fēng)險，降低欠擬合風(fēng)險，決策樹效果提升比預(yù)剪枝強
  • 缺點：時間開銷大得多

ID3、C4.5、CART對比

參考：【機器學(xué)習(xí)】決策樹（上）——ID3、C4.5、CART（非常詳細）

• 劃分標(biāo)準(zhǔn)的差異：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺點，偏向于特征值小的特征，CART 使用基尼指數(shù)克服 C4.5 需要求 log 的巨大計算量，偏向于特征值較多的特征。
• 使用場景的差異：ID3 和 C4.5 都只能用于分類問題，CART 可以用于分類和回歸問題；ID3 和 C4.5 是多叉樹，速度較慢，CART 是二叉樹，計算速度很快；
• 樣本數(shù)據(jù)的差異：ID3 只能處理離散數(shù)據(jù)且缺失值敏感，C4.5 和 CART 可以處理連續(xù)性數(shù)據(jù)且有多種方式處理缺失值；從樣本量考慮的話，小樣本建議 C4.5、大樣本建議 CART。C4.5 處理過程中需對數(shù)據(jù)集進行多次掃描排序，處理成本耗時較高，而 CART 本身是一種大樣本的統(tǒng)計方法，小樣本處理下泛化誤差較大 ；
• 樣本特征的差異：ID3 和 C4.5 層級之間只使用一次特征，CART 可多次重復(fù)使用特征；
• 剪枝策略的差異：ID3 沒有剪枝策略，C4.5 是通過悲觀剪枝策略來修正樹的準(zhǔn)確性，而 CART 是通過代價復(fù)雜度剪枝。

更多模型不斷更新中。。。。