分而治之
此處重點放在分而治之的解題思路
問題1: 給定一個數組 [2,3,4,6]，你需要將這些數字相加，並返回結果。
使用循環很容易完成這種任務：
num = [2,3,4,6]def sum1(num): total = 0 for i in num: total += i return total
print(sum1(num))15問題2: 那我們如何使用 分而治之 策略呢？
Q1: 如果我問數組[2] or []數字相加的結果是多少？
A1: 2 or 0，因為只有1個元素時，累加肯定是其本身2；沒有元素時，肯定為0。因此，稱這種情況下為基線條件。可以理解為：計算最簡單的條件。
Q2：對於數組[2,3,4,6]求和是否可以看成：對數組[2]求和 + 對數組[3,4,6]求和？
A2：可以，在問題2中，所求取的數組長度更短了。換言之，這縮小了問題規模，這就是Divide。
綜合問題1和問題2，新的sum2函數工作原理如下：
如果列表為空，返回0
否則，計算第1個元素+剩餘元素列表總和
def sum2(num): if num == []: return 0 return num[0] + sum2(num[1:])print(sum2(num))15總結1：¶分而治之不是用於解決問題的算法，而是一種解決問題的思路。
首先要找到基線條件。
每次遞歸調用都必須離基線條件更進一步，即 縮小問題規模。
決策樹基本流程¶決策樹（Decision Tree）是一類常見的機器學習算法，其基本流程圖遵循簡單且直觀的 D&C策略。
下面以西瓜問題來展示決策樹基本流程：
西瓜屬性包含：[色澤, 根蒂, 敲聲]
我們可能首先看「它是什麼顏色的？」，如果是「青綠色」
「它的根蒂是什麼形態？」，如果是「蜷縮」
「它敲起來是什麼聲音？」，如果是「濁響」
結論：好瓜。
對照 D&C策略，我們發現下一次的問題總是基於屬性子集來問的。第一個問題包含3種屬性，第二個問題包含2種屬性，等等。
由此可見，決策樹是基於樹結構來進行決策的。這種決策方式恰是人類在面臨決策問題時一種很自然的處理機制。並且我們會很容易理解每個決策步驟的結果（有很好的解釋性）。
一般的，一顆決策樹：
包含一個根節點（包含所有屬性）
若干內部節點（跟節點屬性子集）
若干葉節點（最終決策結果：好瓜or壞瓜）
從根節點到葉節點的一條路徑，稱之為「一個決策序列」。
決策樹偽代碼¶三種情形¶當前節點包含的樣本全屬於同一類別，無需劃分（紅色框）。
當前屬性集為空，或是所有樣本在所有屬性上取值相同（x取值一樣），無法劃分（藍色框），根據少數服從多數投票（後驗分布）。
當前節點包含的樣本集合為空，不能劃分（綠色框），此時要回到上一節點，根據少數服從多數投票（先驗分布）。
註：由於決策樹是採用 分而治之策略，所以決策樹的生成是一個遞歸過程。
劃分選擇¶信息熵（information entropy）在上面綠色框內有一個紅色小框（第8行），如何選擇最優劃分屬性呢？
我們應該如何衡量一個劃分數據的犯錯大小呢？
從上面的圖片可以看出：當兩類東西數量相當時，我們不能用少數服從多數投票方法給出結果。
如何衡量一類東西數量相對整體的情況呢？
我們可以用頻率，根據統計學知識，我們知道一個東西頻率的極限就是概率。
但是如果單用概率，我們很難描述上述圖片。（從左到右依此為數據集1-數據集5）
第1個數據集，x類概率為4/4，紅點類為0/4
第2個數據集，x類概率為3/4，紅點類為1/4
第3個數據集，x類概率為2/4，紅點類為2/4
第4個數據集，x類概率為1/4，紅點類為3/4
第5個數據集，x類概率為0/4，紅點類為4/4
我們會發現，如果單純使用概率值，我們需要指定其值是對應那類數據。
但是如果我們只看類別情況，第1個數據集與第5個數據集有區別嗎？第2個數據集與第4個數據集有區別嗎？
雖然數據集1與數據集5、數據集2與數據集4，兩類數據佔比情況有所區別；但是所傳遞的信息量是一樣的
數據集1和數據集5都只有一類數據
數據集2和數據集4，都是有一類數據佔比3/4，有一類數據佔比1/4
所以為了描述上述圖片的區別，我們要採用信息量來描述。
在1948年，香農在 A Mathematical Theory of Communication 論文中首次對上述信息量做了定量描述：信息熵。
信息熵：是對一個信號源所發出的符號（x號和紅點）的不確定性的定量描述
公式為：𝐻(𝐴)=𝐸𝑛𝑡(𝐴)=−∑𝑝𝑖𝑙𝑜𝑔2𝑝𝑖H(A)=Ent(A)=−∑pilog2pi
註：A為一個信息源（可以看出上圖的一個數據集劃分），𝑝𝑖pi為某一類出現的概率。（關於為啥信息熵是這個表達式，不在此詳細討論，後續有專有視頻）
至此，我們現在有了一個可以描述信息量的工具——信息熵。在機器學習中，信息熵是度量樣本集合純度最常用的指標。
所以在機器學習中，我們提到信息熵，其實就是在描述一個數據集的純度。純度和信息量其實是一類概念，不同說法而已。
信息熵值越小，數據集A的純度越高
信息增益（information gain）¶Q1：什麼是增益（gain） A1：簡而言之，放大倍數。這也是gain單詞的含義，就是相對原有系統上的放大倍數。如果把人看成一個系統，我們使用顯微鏡就構成了一個新的系統（人+顯微鏡），這個新系統比舊系統的放大倍數更強大，所以我們才可以看微觀生物。
Q2：信息增益是什麼呢？A2：信息增益，準確來講是信息熵增益，當我們用新的屬性集（新系統）去描述一個數據集時，與原有描述該數據集的舊屬性集（舊系統）對比而，引起信息熵數值變大，就叫做信息增益。這種相對數值大小的改變可以用差值，也可以用比值等。
Q3：為何信息熵數值如何改變？A3：信息熵是根據類別來計算的。現在我們轉換計算方式，根據屬性來計算。1個屬性下可能會包含多個類別。如果此時，我們屬性看成新的類別，那麼原數據的類別數量減少，也就是說新計算方式下的純度提高了，有前面結論可知：信息熵值減小了。
信息增益：兩種計算方式下，信息熵數值的差值。
下面給出精確的數學表達
Tip：著名的ID3決策樹學習算法就是基於信息增益為準則來劃分屬性。
註：由於信息增益中的權重是基於樣本數量，所以信息增益準則對可取值數目較多的屬性有所偏好。
增益率（gain ratio）¶前面有提到過，信息熵數值大小相對改變可以用：差值 or 比值。
信息增益是基於差值而言的，增益率是基於比值。
由信息增益部分的內容可知，當我們選擇採用屬性集來從新計算數據集的信息熵時，這個時候可以把屬性集看成新的類別集。基於新的類別集，我們可以計算數據集新的信息熵（見下圖公式4.4）。
Tip：著名的C4.5算法就是基於增益率來選擇最優屬性劃分的。
註：回顧信息增益公式，概率越小的類別對信息增益值的貢獻越大（在[0,1]區間，log函數比y=x變化快）。因為公式4.3的分母是4.4，所以增益率對可取值數目比較少的屬性有所偏好。
因此，C4.5算法並不是直接選擇增益率最大的候選劃分屬性，而是使用了一個啟發式：先從候選劃分屬性中找出信息增益高於平均水平的屬性，再從 中選擇增益率最高的.
基尼係數（Gini index）¶在機器學習中，基尼係數與信息熵一樣用來衡量數據的純度（purity）。
三分類及多分類 多分類基尼係數公式如下：𝐺𝑖𝑛𝑖(𝑝𝑖)=∑𝑝𝑖(1−𝑝𝑖)=1−∑𝑝2𝑖
註：CART（Classification And Regression Tree）決策樹是使用基尼係數來選擇劃分屬性。tip：基尼係數越小，數據集的純度越高。
基尼指數類比前面增益率，把屬性當成新的類別，此時的基尼指數定義為： 𝐺𝑖𝑛𝑖𝑖𝑛𝑑𝑒𝑥(𝐷,𝑎)=∑𝑣=1𝑉|𝐷𝑣||𝐷|𝐺𝑖𝑛𝑖(𝐷𝑣)
基於鳶尾花決策樹算法實踐¶千呼萬喚始出來，終於到了python代碼演示環節了。
這次還是基於鳶尾花數據來做
from matplotlib import pyplot as pltfrom sklearn import datasetsfrom sklearn.tree import DecisionTreeClassifier from sklearn import treeimport numpy as np#加載數據iris = datasets.load_iris(as_frame=True)X = iris.datay = iris.target
#DataFrame個數，轉換列名df = iris.framedf.columns = ['sepal_l','sepal_w','petal_l','petal_w','target']df
#繪圖，花萼寬度 VS 花瓣長度fig = df[df.target==0].plot(kind='scatter',x='sepal_w',y='petal_l', marker='^', color='orange', label='Setosa')df[df.target==1].plot(kind='scatter',x='sepal_w',y='petal_l',color='blue', marker='x', label='versicolor',ax=fig)df[df.target==2].plot(kind='scatter',x='sepal_w',y='petal_l',color='red', marker='o', label='virginica', ax=fig)fig.set_xlabel("Sepal Width")fig.set_ylabel("Petal Length")fig.set_title("Sepal Width VS Petal Length")fig=plt.gcf()fig.set_size_inches(8,4)plt.show()
#決策樹模型學習clf1 = DecisionTreeClassifier(max_depth=3)X1 = X[['sepal width (cm)', 'petal length (cm)']]m1 = clf1.fit(X1, y)
#決策樹可視化fig = plt.figure(figsize=(25,20))_ = tree.plot_tree(clf1, feature_names=X1.columns, class_names=iris.target_names, filled=True)剪枝處理¶
當我們不對決策樹層數限制時，會出現過擬合情況；當我們層數選擇過小時，會出現欠擬合。
隨著決策樹層數的增加，一般情況下 基尼係數會越來越小趨近於0，當基尼係數過小的時候，就不需要再分了，防止過擬合，採取投票法給出結果分類。
前面兩種算法都是邊劃分邊剪枝，這稱為預剪枝（Pre-Pruning）
剪枝小結預剪枝一旦遇到基尼係數減小較少就不再往下細分，有可能導致後面可能出現的好的劃分被忽略掉了，從而造成模型的複雜度太低，最終發生欠擬合。這有點像一次考差就禁止該學生繼續深造，以後連考試的機會都沒有了。
後剪枝不會出現這樣的問題，所以在實際應用中，後剪枝是更常見的。其缺點是計算量較大。
參考資料