決策樹算法梳理

1.資訊論基礎

熵：熵是表示随機變量不确定性的度量

（解釋：說白了就是事物内部的混亂程度，比如雜貨市場裡面什麼都有那肯定混亂，專賣店裡面隻賣一個牌子的那就穩定多了）

公式：

聯合熵

聯合熵就是度量一個聯合分布的随機系統的不确定度。

條件熵

條件熵H(Y|X)表示在已知随機變量X的條件下随機變量Y的不确定性。

資訊增益

表示特征X使得類Y的不确定性減少的程度。（分類後的專一性，希望分類後的結果是同類在一起）

其中 I 為不純度的度量，關于 N 的計算是劃分後的個數權重。

I 為熵（Entropy）的時候，Delta 為資訊增益。

基尼不存度

基尼不存度是指來自集合的某種結果随機應用于集合中某一資料的預期誤差。（如果集合中所有結果屬于同一類，則誤差為0）

2.決策樹的不同分類算法的原理及應用場景

ID3算法

ID3算法的核心是在決策樹各個節點上應用資訊增益準則選擇特征，遞歸地建構決策樹。具體方法是：從根節點開始，對節點計算所有可能的特征的資訊增益，選擇資訊增益最大的特征作為節點的特征，由該特征的不同取值建立子節點；再對子節點遞歸的調用以上方法，建構決策樹；直到所有特征的資訊增益均很小或沒有特征可以選擇為止。最後得到一個決策樹。ID3相當于用極大似然進行機率模型得選擇。

C4.5

C4.5算法與ID3算法相似，C4.5算法對ID3算法進行了改進。C4.5在生成得過程中，用資訊增益比來選擇特征。

CART分類樹

CART是在給定輸入随機變量X條件下輸出随機變量Y的條件機率分布的學習反發法，CART假設決策樹是二叉樹，内部節點特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價于遞歸地二分每個特征，将輸入空間即特征空間劃分為有限個單元，并在這些單元上确定預測的機率分布，也就是在輸入給定的條件下輸出的條件機率分布。

3.回歸樹模型

回歸是為了處理預測值是連續分布的情景，其傳回值應該是一個具體預測值。回歸樹的葉子是一個個具體的值，從預測值連續這個意義上嚴格來說，回歸樹不能稱之為“回歸算法”。因為回歸樹傳回的是“一團”資料的均值，而不是具體的、連續的預測值（即訓練資料的标簽值雖然是連續的，但回歸樹的預測值卻隻能是離散的）。是以回歸樹其實也可以算為“分類”算法，其适用場景要具備“物以類聚”的特點，即特征值的組合會使标簽屬于某一個“群落”，群落之間會有相對鮮明的“鴻溝”。

4.決策樹防止過拟合手段

分析分類回歸樹的遞歸建樹過程，不難發現它實質上存在着一個資料過度拟合問題。在決策樹構造時，由于訓練資料中的噪音或孤立點，許多分枝反映的是訓練資料中的異常，使用這樣的判定樹對類别未知的資料進行分類，分類的準确性不高。是以試圖檢測和減去這樣的分支，檢測和減去這些分支的過程被稱為樹剪枝。樹剪枝方法用于處理過分适應資料問題。

5.模型評估

自助法（bootstrap）：

訓練集是對于原資料集的有放回抽樣，如果原始資料集N，可以證明，大小為N的自助樣本大約包含原資料63.2%的記錄。當N充分大的時候，1-（1-1/N）^(N) 機率逼近 1-e^(-1)=0.632。抽樣 b 次，産生 b 個bootstrap樣本，則，總準确率為（accs為包含所有樣本計算的準确率。

準确度的區間估計：

将分類問題看做二項分布，則有：

令 X 為模型正确分類，p 為準确率，X 服從均值 Np、方差 Np（1-p）的二項分布。acc=X/N為均值 p，方差 p（1-p）/N 的二項分布。acc 的置信區間：

6.sklearn參數詳解，Python繪制決策樹*

DecisionTreeRegressor(criterion=“mse”, splitter=“best”, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0., max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0., min_impurity_split=None, presort=False)

1.criterion:string, optional (default=“mse”) 它指定了切分品質的評價準則。預設為’mse’(mean squared error)。

2.splitter:string, optional (default=“best”) 它指定了在每個節點切分的政策。有兩種切分策咯： (1).splitter=‘best’:表示選擇最優的切分特征和切分點。 (2).splitter=‘random’:表示随機切分。

3.max_depth:int or None, optional (default=None) 指定樹的最大深度。如果為None，則表示樹的深度不限，直到 每個葉子都是純淨的，即葉節點中所有樣本都屬于同一個類别， 或者葉子節點中包含小于min_samples_split個樣本。

4.min_samples_split:int, float, optional (default=2) 整數或者浮點數，預設為2。它指定了分裂一個内部節點(非葉子節點) 需要的最小樣本數。如果為浮點數(0到1之間)，最少樣本分割數為ceil(min_samples_split * n_samples)

5.min_samples_leaf:int, float, optional (default=1) 整數或者浮點數，預設為1。它指定了每個葉子節點包含的最少樣本數。 如果為浮點數(0到1之間)，每個葉子節點包含的最少樣本數為ceil(min_samples_leaf * n_samples)

6.min_weight_fraction_leaf:float, optional (default=0.) 它指定了葉子節點中樣本的最小權重系數。預設情況下樣本有相同的權重。

7.max_feature:int, float, string or None, optional (default=None) 可以是整數，浮點數，字元串或者None。預設為None。 (1).如果是整數，則每次節點分裂隻考慮max_feature個特征。 (2).如果是浮點數(0到1之間)，則每次分裂節點的時候隻考慮int(max_features * n_features)個特征。 (3).如果是字元串’auto’,max_features=n_features。 (4).如果是字元串’sqrt’,max_features=sqrt(n_features)。(5).如果是字元串’log2’,max_features=log2(n_features)。 (6).如果是None，max_feature=n_feature。

8.random_state:int, RandomState instance or None, optional (default=None) (1).如果為整數，則它指定了随機數生成器的種子。(2).如果為RandomState執行個體，則指定了随機數生成器。(3).如果為None，則使用預設的随機數生成器。9.max_leaf_nodes:int or None, optional (default=None) (1).如果為None，則葉子節點數量不限。(2).如果不為None，則max_depth被忽略。10.min_impurity_decrease:float, optional (default=0.) 如果節點的分裂導緻不純度的減少(分裂後樣本比分裂前更加純淨)大于或等min_impurity_decrease，則分裂該節點。個人了解這個參數應該是針對分類問題時才有意義。這裡的不純度應該是指基尼指數。回歸生成樹采用的是平方誤差最小化政策。分類生成樹采用的是基尼指數最小化政策。權重不純度的減少量計算公式為：min_impurity_decrease=N_t / N * (impurity - N_t_R / N_t * right_impurity - N_t_L / N_t * left_impurity) 其中N是樣本的總數，N_t是目前節點的樣本數，N_t_L是分裂後左子節點的樣本數， N_t_R是分裂後右子節點的樣本數。impurity指目前節點的基尼指數，right_impurity指分裂後右子節點的基尼指數。left_impurity指分裂後左子節點的基尼指數。

11.min_impurity_split:float 樹生長過程中早停止的門檻值。如果目前節點的不純度高于門檻值，節點将分裂，否則它是葉子節點。這個參數已經被棄用。用min_impurity_decrease代替了min_impurity_split。

12.presort： bool, optional (default=False) 指定是否需要提前排序資料進而加速尋找最優切分的過程。設定為True時，對于大資料集會減慢總體的訓練過程；但是對于一個小資料集或者設定了最大深度的情況下，會加速訓練過程。