西瓜書習題試答-第08章-集成學習

試答系列：「西瓜書」-周志華《機器學習》習題試答
系列目錄
[第01章：緒論]
[第02章：模型評估與選擇]
[第03章：線性模型]
[第04章：決策樹]
[第05章：神經網絡]
[第06章：支持向量機]
第07章：貝葉斯分類器
第08章：集成學習
第09章：聚類
第10章：降維與度量學習
第11章：特徵選擇與稀疏學習
第12章：計算學習理論(暫缺)
第13章：半監督學習
第14章：機率圖模型
(後續章節更新中...)html

8.1 假設拋硬幣正面爲上的機率爲p，反面朝上的機率爲1-p。令H(n)表明拋n次硬幣所得正面朝上的次數，則最多k次正面朝上的機率爲

對δ>0,k=(p-δ)n，有Hoeffding不等式python

試推導出式(8.3).
證實：(8.3)表達了集成錯誤率，當不超過半數預測正確時，集成分類器預測錯誤，所以集成錯誤率爲：web

注意，上式中第一行中的H(x)是集成分類器預測函數，第二行的H(T)是題目中所述的硬幣朝上次數的函數。與題目中的(8.43)、(8.44)式對比，進行變量代換：n=T，p=1-ε，k=[T/2]，那麼δ=1-ε-[T/2]/T。其中[T/2]/T≤1/2,因此δ≥1/2-ε，因而有面試

得證。算法

8.2 對於0/1損失函數來講，指數損失函數並不是僅有的一致替代函數。考慮式(8.5)，試證實：任意損失函數 \(L(-f(x)H(x))\)，若對於H(x)在區間[-∞,δ] (δ>0)上單調遞減，則是0/1損失函數的一致替代函數。

證實：這道題表述大概存在筆誤，應該是「…，若對於f(x)H(x)在區間…」纔對。好比，對於Adaboost中採用的指數損失函數，\(L(-f(x)H(x))=exp(-f(x)H(x))\)，當f(x)=1時，損失函數=exp(-H(x))是對於H(x)在[-∞，+∞]上的單調減函數，可是當f(x)=-1時，損失函數=exp(H(x))是H(x)的增函數，與題目描述不符。
對於任意損失函數，若對於f(x)H(x)在區間[-∞,δ] (δ>0)上單調遞減，函數曲線當形以下圖：

\(L(-u)\)函數的特色是：在[-∞,δ]區間是單調遞減函數(不管其凹凸性如何)，在[δ,+∞]區間，能夠是任意形狀曲線，不管其單調性如何。從上圖中能夠看出，對該損失函數進行最小化時，所對應的橫座標位置u*老是在δ右側，也就是f(x*)H(x*)≥δ>0，這說明H(x)與f(x)同正負號。所以sign(H(x*))=f(x*)，其結果與最小化0/1損失函數結果一致，是一致替代函數。編程

8.3 從網上下載或本身編程實現AdaBoost，以不剪枝決策樹爲基學習器，在西瓜數據集3.0α上訓練一個AdaBoost集成，並與圖8.4進行比較。

答：網絡

1. AdaBoost算法總結

• 西瓜書中的推導大概過程

\(\alpha_t=argmin_\alpha l_{exp}(\alpha_t h_t| D_t)=\frac{1}{2}\ln(\frac{1-\epsilon_t}{\epsilon_t})\)，其中\(\epsilon_t=P_{x\sim D_t}(f(x)\neq h_t(x))\)；
\(h_t (x)=argmin_h l_{exp}(H_{t-1}+h|D)\dots=argmin_h E_{x\sim D_t}[Ⅱ(f(x)\neq h(x))]\)，其中將\(H_{t-1}\)的影響包含在\(D_t\)中，\(D_t(x)\)是關於x的分佈，\(D_t(x)∝D(x)e^{-f(x)H_{t-1}(x)}\)，Dt存在遞推關係\(D_{t+1}=D_t e^{-f(x)\alpha_t h_t(x)}/Z_t\)。app

然而，看完教材上的上述推導，內心充滿了疑問：dom

1. 爲何求\(α_t\)是經過最小化\(l_{exp}(α_th_t|D_t)\)來求得？
2. 爲何經過最小化\(l_{exp}(H_{t-1}+h_t|D)\)來求取\(h_t\)時，\(h_t\)前面沒有係數\(α_t\)，後面推導\(D_{t+1}\)和\(D_t\)的遞推關係時，怎麼就忽然要加上係數\(α_t\)了？

• 其餘推導方法
  此前看過吳恩達的CS229課程，其補充材料中有介紹Boosting算法的內容，一樣是對AdaBoost算法的推導，容易理解的多，現將其總結至此：
  (爲了與西瓜書中的表達符號一致，對原文進行了必定的改寫)

在計算到第t步時，當前已經獲得的模型爲\(H_{t-1}\)，接下來的學習器對當前模型\(H_{t-1}\)預測錯誤的樣本進行重點關注，定義新的樣本權重分佈：機器學習

\[D_t(x)=D(x)e^{-f(x)H_{t-1}(x)}/E_{x\sim D}[e^{-f(x)H_{t-1}(x)}] \]

該權重分佈反映了對預測錯誤樣本的重點關注，由於，若是預測正確，\(e^{-f(x)H_{t-1}(x)}<1\),若是預測錯誤，\(e^{-f(x)H_{t-1}(x)}>1\)。
\(h_t(x)\)的肯定：在新的樣本權重下進行學習訓練。
\(α_t\)的肯定：

\[\begin{aligned} \alpha_t &=argmin_{\alpha}l_{exp}(H_t |D)\\ &=argmin_{\alpha}E_{x\sim D}[e^{-f(x)H_{t-1}(x)}\cdot e^{-f(x)\alpha_t h_t(x)}]\\ &=argmin_{\alpha}E_{x\sim D_t}[e^{-f(x)\alpha_t h_t(x)}]\\ &=argmin_{\alpha}(1-\epsilon_t)e^{-\alpha_t}+\epsilon_t e^{\alpha_t}\\ &=\frac{1}{2}ln(\frac{1-\epsilon_t}{\epsilon_t}) \end{aligned}\]

接着證實了 算法的收斂性，注意到\(D_t\)的歸一化係數\(Z_t=E_{x\sim D}[e^{-f(x)H_{t-1}(x)}]=l_{exp}(H_{t-1}|D)\)，所以有：

\[\begin{aligned} l_{exp}(H_t |D)&=E_{x\sim D}[e^{-f(x)H_{t-1}(x)}\cdot e^{-f(x)\alpha_t h_t(x)}]\\ &=E_{x\sim D}[Z_t \cdot D_t(x)\cdot e^{-f(x)\alpha_t h_t(x)}]\\ &=l_{exp}(H_{t-1} |D)\cdot E_{x\sim D_t}[e^{-f(x)\alpha_t h_t(x)}]\\ &=l_{exp}(H_{t-1} |D)\cdot 2\sqrt{\epsilon_t(1-\epsilon_t)} \end{aligned}\]

設每一個弱分類器的偏差知足\(\epsilon_t \leq \frac{1}{2}-\gamma\)，則有：

\[\begin{aligned} l_{exp}(H_t |D)&=l_{exp}(H_{t-1} |D)\cdot 2\sqrt{\epsilon_t(1-\epsilon_t)}\\ &\leq l_{exp}(H_{t-1} |D)\cdot \sqrt{1-4\gamma^2} \end{aligned}\]

所以有：

\[l_{exp}(H_t |D)\leq l_{exp}(H_0|D)(1-4\gamma^2)^{t/2}=(1-4\gamma^2)^{t/2} \]

其中\(l_{exp}(H_0|D)=Z_0 =1\)，通過有限步T之後，必然有\(l_{exp}(H_T|D)< \frac{1}{m}\)，此時全部樣本都被正確分類，對應的最大步數\(T_{max}=-2\ln m/ln(1-4γ^2)≤\ln m/2γ^2\).
至於爲何\(l_{exp}(H_T|D)< \frac{1}{m}\)時，全部樣本都正確分類？由於\(l_{exp}(H_T|D)\geq l_{1/0}(H_T|D)=\epsilon\)，當\(l_{exp}(H_T|D)< \frac{1}{m}\)時，\(\epsilon=\frac{誤分數}{m}<\frac{1}{m}\)，誤分樣本數<1，意味着全部樣本都被正確分類。

• 討論
  如今能夠回頭來解答前面存在的疑問了：

1. 爲何求\(α_t\)是經過最小化\(l_{exp}(α_th_t|D_t)\)來求得？
   最小化\(l_{exp}(α_th_t|D_t)\)實際上等價於最小化\(l_{exp}(H_{t-1}+α_th_t|D)\)，然後者正是咱們最終的優化目標，如此便好理解了。
2. 爲何經過最小化\(l_{exp}(H_{t-1}+h_t|D)\)來求取\(h_t\)時，\(h_t\)前面沒有係數\(α_t\)，後面推導\(D_{t+1}\)和\(D_t\)的遞推關係時，怎麼就忽然要加上係數\(α_t\)了？
   西瓜書上最小化\(l_{exp}(H_{t-1}+h_t|D)\)來求取\(h_t\)不太好理解，\(D_t\)是化簡前式過程當中析出的一部分，是個析出量。而CS229課程中的證實過程則直觀易於理解，\(D_t\)反映了當前步驟對以前預測錯誤的樣本進行重點關注的權重從新分配，是個直接定義量.
   
   另外，注意到，在上述證實算法收斂性的過程當中，假設每一個弱分類器的預測錯誤率優於隨機分類器：\(\epsilon_t \leq \frac{1}{2}-\gamma\)，從而獲得的結論\(l_{exp}(H_t |D)\leq l_{exp}(H_{t-1} |D)\sqrt{1-4\gamma^2}\)，接着有後面算法必然收斂的結論。其實，若是分類器不好，\(\epsilon_t >\frac{1}{2}+\gamma\)，也能夠獲得相同的結果。再者，即使分類器\(h_t(x)\)的錯誤率比隨機分類器還差:\(\epsilon_t >\frac{1}{2}\)，由此獲得的\(α_t<0\)，那麼\(α_t h_t(x)=|α_t|·[-h_t(x)]\)，這至關於自動將\(h_t(x)\)進行了翻轉糾正。
   
   所以，教材中提到的\(\epsilon_t <\frac{1}{2}\)的限制，徹底不必，真正關鍵的在於 錯誤率要遠離1/2，更靠近0或者1均可以。 假如某次迭代時\(\epsilon_t =\frac{1}{2}\)，則\(α_t=0\)，\(l_{exp}(H_t |D)=l_{exp}(H_{t-1} |D)\)，不會再產生新的學習器，損失函數再也不變化，Boosting算法陷入停滯，沒法再進行下去。

2. 編程計算

題目上說「以不剪枝決策樹爲基學習器」，沒明白什麼意思，好像有問題。AdaBoost的基學習器一般是弱學習器，而不剪枝決策樹第一步即可實現零偏差分類，對應的\(α_1=∞\)，下一步的分佈\(D_2=0\)，算法沒法再進行下去。既然要與圖8.4進行比較，下面的解答採用與之相同的決策樹樁做爲基學習器。
詳細編程代碼附後。
說明一點，根據前面討論，對於每一個決策樹樁，我統一約定左分支取值爲1，右分支取值爲-1，即使當前\(h_t(x)\)的效果較差，\(\epsilon_t>1/2\)，流程也會經過\(α_t<0\)的方式自動將其糾正過來。

3. 運行結果討論

首先，嘗試在生成決策樹樁時，以信息增益最大化來肯定劃分屬性和劃分點，結果失敗，過程當中會致使\(ε_t=1/2\)，Boosting算法沒法再進行下去。
因而，改用最小化偏差來進行劃分選擇：\(min E_{x\sim D_t}[Ⅱ(f(x)\neq h_t(x))]\)。計算結果以下：

在t=7時即達到零錯誤率(此處的錯誤率是指總的預測函數\(H_t(x)\)在原數據集D上的錯誤率，注意與\(\epsilon_t\)區分)。
正如前面的分析(「其餘推導方法」中對收斂性的證實)，\(l_{exp}≥l_{0/1}=錯誤率ε\)，\(l_{exp}\)是\(l_{0/1}\)的上界，當\(l_{exp}<1/m\)時，必有\(l_{0/1}<1/m\)，必有\(l_{0/1}=0\)。

上圖中採用與教材8.4中相同的表示方法：紅粗線和黑細線分別表示集成和基學習器的分類邊界。這裏獲得的分類邊界與教材8.4有所不一樣。

另外，根據前面的討論，只要\(\epsilon_t\)不等於1/2，都能保證\(l_{exp}\)收斂並在有限步迭代後達到零錯誤率。所以，我嘗試了用隨機方法產生\(h_t(x)\)，按理說仍然可以保證算法收斂，某次實驗結果以下：


正如預期，儘管每一個\(h_t\)是隨機產生的，卻可以確保算法收斂，只不過收斂速度較慢。損失函數\(l_{exp}\)老是單調降低的，錯誤率在t=29歸零以後儘管有反彈，但總能穩定歸零。

那麼，在Adaboost算法中，當\(\epsilon_t\)=1/2時，能夠沒必要break，能夠從新隨機產生一個\(\epsilon_t\)≠1/2 的基學習器來避免程序早停。
再次嘗試經過信息增益最大化來進行劃分，可是引入一個機制：當\(\epsilon_t\)=1/2時，從新隨機產生一個弱學習器。某次實驗結果以下：

8.4 Gradient Boosting [Friedman,2001]是一種經常使用的Boosting算法，試析其與AdaBoost的異同。

答：

1. Gradient Boosting算法簡介
   算法描述以下圖所示(參考原論文，以及這篇博文)
   
   下面試將Gradient Boosting算法改寫成與本教材一致的表達方式：

   算法：Gradient Boosting

   1. \(h_0(x)=argmin_\alpha E_{x\sim D}[L(f(x),\alpha)]\)
   2. for t=1,2,...,T do：
   3. \(\,\,\,\,\,\,\,\,\tilde{y_i}=-[\frac{\partial L(f(x_i),H(x_i))}{\partial H(x_i)}]_{H(x)=H_{t-1}(x)}, i=1\sim m\)
   4. \(\,\,\,\,\,\,\,\,h_t(x)=argmin_{\beta,h}E_{x\sim D}[(\tilde{y}-\beta h(x))^2]\)
   5. \(\,\,\,\,\,\,\,\,\alpha_t=argmin_\alpha E_{x\sim D}[L(y,H_{t-1}(x)+\alpha h_t(x))]\)
   6. \(\,\,\,\,\,\,\,\,H_t(x)=H_{t-1}(x)+\alpha_t h_t(x)\)
   7. end for

   討論
   Gradient Boosting算法第3行便是求取目標函數L關於預測函數H的負梯度。好比，\(L=(y-H)^2\)，則有\(\partial L/\partial H=2(H-y)\)。
   此前，在對率迴歸和神經網絡的訓練中咱們瞭解過梯度降低法，不過，那裏是求取目標函數L關於參數θ的梯度。預測函數H(x;θ)的模型自己的形式不變，好比對率迴歸中，它固定是線性函數，在神經網絡中，各層神經元數目固定，而參數θ則可任意變化。咱們的任務是在θ的參數空間中搜索最佳參數。
   然而在這裏，咱們把H當作能夠任意變化的函數，L是關於H這個函數的函數(泛函)。若是H真的能夠任意變化，咱們直接令H(x)=y不就行了。也有可能H(x)=y未必使L達到最小，此時能夠經過最小化\(L(y,H_{t-1}+h)\)來求取\(h_t\)。
   然而，一般H不能任意變化，具體在boosting算法中，H被限定爲多個弱學習器相加的形式。那麼在第t步肯定\(h_t\)時，Gradient Boosting算法即是以這個負梯度做爲啓發方向，使\(h_t\)應該儘量地接近於該方向。
   Gradient Boosting算法適用於多種形式的損失函數。若是L取與AdaBoost中同樣的指數損失函數，而且f(x)={1,-1}，咱們能夠試着推導一下，結果應如是：

   算法：exp-boost

   1. \(h_0(x)=sign(m_+-m_-)\)
   2. for t=1,2,...,T do：
   3. \(\,\,\,\,\,\,\,\,\tilde{y_i}=f(x_i)exp[-f(x_i)H_{t-1}(x_i)], i=1\sim m\)
   4. \(\,\,\,\,\,\,\,\,h_t(x)=argmin_{\beta,h}E_{x\sim D}[(\tilde{y}-\beta h(x))^2]=\cdots=argmin_hE_{x\sim D_t}[Ⅱ(f(x)\neq h(x))]\)
   5. \(\,\,\,\,\,\,\,\,\alpha_t=argmin_\alpha E_{x\sim D}[L(y,H_{t-1}(x)+\alpha h_t(x))]=\cdots=\frac{1}{2}ln\frac{1-\epsilon_t}{\epsilon_t}\)
   6. \(\,\,\,\,\,\,\,\,H_t(x)=H_{t-1}(x)+\alpha_t h_t(x)\)
   7. end for

   可見，此時Gradient Boosting算法除了多了一個\(h_0(x)\)，相應的初始分佈D1有所不一樣，在t=1,2…,T迭代步驟中，\(h_t\)和\(\alpha_t\)的計算方法與AdaBoost算法徹底相同。

2. 比較Gradient Boosting和AdaBoost算法
   相同點：
   預測函數H(x)一樣是「加性模型」，亦即基學習器的線性組合；
   第t步產生\(h_t\)和\(\alpha_t\)時，都保持前面的\(H_{t-1}(x)\)不變；
   \(\alpha_t\)的計算都是經過在既定\(h_t(x)\)的狀況下來最小化目標函數；
   AdaBoost算法能夠當作是在指數損失函數和y={1,-1}狀況下的Gradient Boosting算法特例；
   不一樣點：
   求取\(h_t\)的思路不一樣(儘管在指數損失函數和y={1,-1}狀況下結果同樣)，在AdaBoost中，根據當前\(H_{t-1}(x)\)的預測效果來從新調整各個樣本的權重，提升錯誤樣本的權重，基於此來訓練\(h_t(x)\)。而在Gradient Boosting中，經過尋找與負梯度方向最接近的函數\(h_t(x)=argmin_h|\nabla_HL-βh(x)|^2\)。
   Gradient Boosting算法適用範圍更廣，函數取值能夠連續取值、離散取值(不限於y={1,-1})，損失函數能夠是平方差，絕對誤差，Huber，logistic型。而AdaBoost算法只能用於二分類的狀況。

8.5 試編程實現Bagging，以決策樹樁爲基學習器，在西瓜數據集3.0α上訓練一個Bagging集成，並與圖8.6進行比較。

答：詳細編程代碼附後。
以樁決策樹爲基學習器，下圖是某一次的計算結果：


可見，訓練偏差最低爲0.17，最少有3個樣本被誤分。與圖8.6比較，分類效果較差，哪裏出了問題？
網上查閱相關介紹，好比這篇博文。
瞭解到：Boosting算法的基學習器一般是弱學習器，特色是誤差較大，經過Boosting算法能夠逐步提高，較低誤差；而Bagging的基學習器一般是強學習器，好比，全決策樹和神經網絡，特色是誤差較小，可是容易過擬合，方差較大，經過多個基學習器的平均來減少方差，防止過擬合。
這裏採用的基學習器是決策樹樁，自己誤差較大，Bagging集成只有下降方差的效果，對於誤差並沒有改善，因此集成後的訓練偏差仍然很低。因而，咱們將基學習器改成全決策樹，下圖是某次計算結果：


可見，前4個集成後便已經實現了零訓練偏差。

8.6 試析Bagging一般爲什麼難以提高樸素貝葉斯分類器的性能。

答：參考上題8.5的一些結論，樸素貝葉斯分類器自己的特色是誤差較大，算是弱學習

8.7 試析隨機森林爲什麼比決策樹Bagging集成的訓練速度更快。

答：在選擇劃分屬性時，隨機森林只需考察隨機選取的幾個屬性，而決策樹Bagging則要考察全部屬性，所以訓練速度更快。

8.8 MultiBoosting算法[Webb,2000]將AdaBoost做爲Bagging的基學習器，Iterative Bagging算法[Breiman,2001b]則將Bagging做爲AdaBoost的基學習器。試比較兩者的優缺點。（暫缺）

答：

8.9 試設計一種可視的多樣性度量，對習題8.3和習題8.5中獲得的集成進行評估，並與κ-偏差圖比較。（暫缺）

答：

8.10 試設計一種能提高k近鄰分類器性能的集成學習算法。（暫缺）

答：

附：習題代碼

8.3(python)

# -*- coding: utf-8 -*-
"""
Created on Wed Mar 11 09:50:11 2020

@author: MS
"""

import numpy as np
import matplotlib.pyplot as plt

#設置出圖顯示中文
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus'] = False

def Adaboost(X,Y,T,rule='MaxInfoGain',show=False):
    # 以決策樹樁爲基學習器的Adaboost算法
    # 輸入:
    #     X:特徵，m×n維向量
    #     Y：標記,m×1維向量
    #     T：訓練次數
    #     rule:決策樹樁屬性劃分規則，能夠是：
    #          'MaxInfoGain'，'MinError','Random'
    #     show:是否計算並顯示迭代過程當中的損失函數和錯誤率
    # 輸出:
    #     H:學習結果，T×3維向量，每行對應一個基學習器，
    #       第一列表示αt,第二列表示決策樹樁的分類特徵，第三列表示劃分點
    
    m,n=X.shape        #樣本數和特徵數
    D=np.ones(m)/m     #初始樣本分佈
    H=np.zeros([T,3])  #初始化學習結果爲全零矩陣 
    #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    #這部分用於計算迭代過程當中的損失函數和錯誤率的變化
    #無關緊要
    H_pre=np.zeros(m)  #H對各個樣本的預測結果
    L=[]               #存儲每次迭代後的損失函數
    erro=[]            #存儲每次迭代後的錯誤率
    #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    for t in range(T):
        if rule=='MaxInfoGain':
            ht=decision_sdumps_MaxInfoGain(X,Y,D)
        elif rule=='MinError':
            ht=decision_sdumps_MinError(X,Y,D)
        else:  #rule=='Random'或者其餘未知取值時，隨機產生
            ht=decision_sdumps_Random(X,Y,D)
        ht_pre=(X[:,ht[0]]<=ht[1])*2-1   #左分支爲1，右分支爲-1
        et=sum((ht_pre!=Y)*D)
        while abs(et-0.5)<1E-3:
            # 若et=1/2，從新隨機生成
            ht=decision_sdumps_Random(X,Y,D)
            ht_pre=(X[:,ht[0]]<=ht[1])*2-1
            et=sum((ht_pre!=Y)*D)
        alphat=0.5*np.log((1-et)/et)
        H[t,:]=[alphat]+ht
        #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        #這部分用於計算迭代過程當中的損失函數和錯誤率的變化
        #無關緊要
        if show:
            H_pre+=alphat*ht_pre
            L.append(np.mean(np.exp(-Y*H_pre)))
            erro.append(np.mean(np.sign(H_pre)!=Y))
        #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        D*=np.exp(-alphat*Y*ht_pre)
        D=D/D.sum()
    #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    #這部分用於顯示迭代過程當中的損失函數和錯誤率的變化
    #無關緊要
    if show:
        try:
            plt.title('t=%d時錯誤率歸0'%(np.where(np.array(erro)==0)[0][0]+1))
        except:
            plt.title('錯誤率還沒有達到0')
        plt.plot(range(1,len(L)+1),L,'o-',markersize=2,label='損失函數的變化')
        plt.plot(range(1,len(L)+1),erro,'o-',markersize=2,label='錯誤率的變化')
        plt.plot([1,len(L)+1],[1/m,1/m],'k',linewidth=1,label='1/m 線')
        plt.xlabel('基學習器個數')
        plt.ylabel('指數損失函數/錯誤率')
        plt.legend()
        plt.show()
    #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    return H

def decision_sdumps_MinError(X,Y,D):
    # 基學習器---決策樹樁
    # 以最小化錯誤率來選擇劃分屬性和劃分點    
    m,n=X.shape        #樣本數和特徵數
    results=[]         #存儲各個特徵下的最佳劃分點和錯誤率
    for i in range(n): #遍歷各個候選特徵
        x=X[:,i]               #樣本在該特徵下的取值
        x_sorted=np.unique(x)  #該特徵下的可能取值並排序
        ts=(x_sorted[1:]+x_sorted[:-1])/2   #候選劃分點
        Errors=[]              #存儲各個劃分點下的|錯誤率-0.5|的值
        for t in ts:
            Ypre=(x<=t)*2-1
            Errors.append(abs(sum(D[Ypre!=Y])-0.5))
        Bestindex=np.argmax(Errors)   #距離0.5最遠的錯誤率的索引號
        results.append([ts[Bestindex],Errors[Bestindex]])
    
    results=np.array(results)
    divide_feature=np.argmax(results[:,1])         #劃分特徵
    h=[divide_feature,results[divide_feature,0]]   #劃分特徵和劃分點
    return h

def decision_sdumps_MaxInfoGain(X,Y,D):
    # 基學習器---決策樹樁
    # 以信息增益最大來選擇劃分屬性和劃分點    
    m,n=X.shape        #樣本數和特徵數
    results=[]         #存儲各個特徵下的最佳劃分點和信息增益
    for i in range(n): #遍歷各個候選特徵
        x=X[:,i]               #樣本在該特徵下的取值
        x_sorted=np.unique(x)  #該特徵下的可能取值並排序
        ts=(x_sorted[1:]+x_sorted[:-1])/2   #候選劃分點
        Gains=[]               #存儲各個劃分點下的信息增益
        for t in ts:
            Gain=0
            Y_left,D_left=Y[x<=t],D[x<=t]    #左分支樣本的標記和分佈
            Dl=sum(D_left)                   #左分支總分佈數
            p1=sum(D_left[Y_left==1])/Dl     #左分支正樣本分佈比例
            p0=sum(D_left[Y_left==-1])/Dl    #左分支負樣本分佈比例
            Gain+=Dl*(np.log2(p1**p1)+np.log2(p0**p0))
            
            Y_right,D_right=Y[x>t],D[x>t]    #右分支樣本的標記和分佈
            Dr=sum(D_right)                  #右分支總分佈數
            p1=sum(D_right[Y_right==1])/Dr   #右分支正樣本分佈比例
            p0=sum(D_right[Y_right==-1])/Dr  #右分支負樣本分佈比例
            Gain+=Dr*(np.log2(p1**p1)+np.log2(p0**p0))
            
            Gains.append(Gain)
            
        results.append([ts[np.argmax(Gains)],max(Gains)])
    
    results=np.array(results)
    divide_feature=np.argmax(results[:,1])               #劃分特徵
    h=[divide_feature,results[divide_feature,0]]         #劃分特徵和劃分點
    return h

def decision_sdumps_Random(X,Y,D):
    # 基學習器---決策樹樁
    # 隨機選擇劃分屬性和劃分點    
    m,n=X.shape          #樣本數和特徵數
    bestfeature=np.random.randint(2)
    x=X[:,bestfeature]   #樣本在該特徵下的取值
    x_sorted=np.sort(x)  #特徵取值排序
    ts=(x_sorted[1:]+x_sorted[:-1])/2   #候選劃分點
    bestt=ts[np.random.randint(len(ts))]
    h=[bestfeature,bestt]
    return h

def predict(H,X1,X2):
    # 預測結果
    # 僅X1和X2兩個特徵,X1和X2同維度
    pre=np.zeros(X1.shape)
    for h in H:
        alpha,feature,point=h
        pre+=alpha*(((X1*(feature==0)+X2*(feature==1))<=point)*2-1)
    return np.sign(pre)

##############################
#      主程序
##############################
#>>>>>西瓜數據集3.0α
X=np.array([[0.697,0.46],[0.774,0.376],[0.634,0.264],[0.608,0.318],[0.556,0.215],
   [0.403,0.237],[0.481,0.149],[0.437,0.211],[0.666,0.091],[0.243,0.267],
   [0.245,0.057],[0.343,0.099],[0.639,0.161],[0.657,0.198],[0.36,0.37],
   [0.593,0.042],[0.719,0.103]])
Y=np.array([1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1])

#>>>>>運行Adaboost
T=50
H=Adaboost(X,Y,T,rule='MaxInfoGain',show=True)
# rule:決策樹樁屬性劃分規則，能夠取值：'MaxInfoGain'，'MinError','Random'

#>>>>>觀察結果
x1min,x1max=X[:,0].min(),X[:,0].max()
x2min,x2max=X[:,1].min(),X[:,1].max()
x1=np.linspace(x1min-(x1max-x1min)*0.2,x1max+(x1max-x1min)*0.2,100)
x2=np.linspace(x2min-(x2max-x2min)*0.2,x2max+(x2max-x2min)*0.2,100)
X1,X2=np.meshgrid(x1,x2)

for t in [3,5,11,30,40,50]:
    plt.title('前%d個基學習器'%t)
    plt.xlabel('密度')
    plt.ylabel('含糖量')
    # 畫樣本數據點
    plt.scatter(X[Y==1,0],X[Y==1,1],marker='+',c='r',s=100,label='好瓜')
    plt.scatter(X[Y==-1,0],X[Y==-1,1],marker='_',c='k',s=100,label='壞瓜')
    plt.legend()
    # 畫基學習器劃分邊界
    for i in range(t):
        feature,point=H[i,1:]
        if feature==0:
            plt.plot([point,point],[x2min,x2max],'k',linewidth=1)
        else:
            plt.plot([x1min,x1max],[point,point],'k',linewidth=1)
    # 畫集成學習器劃分邊界
    Ypre=predict(H[:t],X1,X2)
    plt.contour(X1,X2,Ypre,colors='r',linewidths=5,levels=[0])
    plt.show()

8.5(python)

以決策樹樁爲基學習器

# -*- coding: utf-8 -*-
"""
Created on Wed Mar 11 09:50:11 2020

@author: MS
"""

import numpy as np
import matplotlib.pyplot as plt

#設置出圖顯示中文
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus'] = False

def decision_sdumps_MaxInfoGain(X,Y):
    # 基學習器---決策樹樁
    # 以信息增益最大來選擇劃分屬性和劃分點    
    m,n=X.shape        #樣本數和特徵數
    results=[]         #存儲各個特徵下的最佳劃分點,左分支取值，右分支取值，信息增益
    for i in range(n): #遍歷各個候選特徵
        x=X[:,i]                 #樣本在該特徵下的取值
        x_values=np.unique(x)    #當前特徵的全部取值
        ts=(x_values[1:]+x_values[:-1])/2   #候選劃分點
        Gains=[]             #存儲各個劃分點下的信息增益
        for t in ts:
            Gain=0
            Y_left=Y[x<=t]           #左分支樣本的標記
            Dl=len(Y_left)           #左分支樣本數
            p1=sum(Y_left==1)/Dl     #左分支正樣本比例
            p0=sum(Y_left==-1)/Dl    #左分支負樣本比例
            Gain+=Dl/m*(np.log2(p1**p1)+np.log2(p0**p0))
            
            Y_right=Y[x>t]          #右分支樣本的標記
            Dr=len(Y_right)         #右分支總樣本數
            p1=sum(Y_right==1)/Dr   #右分支正樣本比例
            p0=sum(Y_right==-1)/Dr  #右分支負樣本比例
            Gain+=Dr/m*(np.log2(p1**p1)+np.log2(p0**p0))
            
            Gains.append(Gain)
        best_t=ts[np.argmax(Gains)]  #當前特徵下的最佳劃分點
        best_gain=max(Gains)         #當前特徵下的最佳信息增益
        left_value=(sum(Y[x<=best_t])>=0)*2-1   #左分支取值(多數類的類別)
        right_value=(sum(Y[x>best_t])>=0)*2-1   #右分支取值(多數類的類別)
        results.append([best_t,left_value,right_value,best_gain])
    
    results=np.array(results)
    df=np.argmax(results[:,-1])       #df表示divide_feature，劃分特徵
    h=[df]+list(results[df,:3])       #劃分特徵,劃分點,左枝取值，右枝取值
    return h

def predict(H,X1,X2):
    # 預測結果
    # 僅X1和X2兩個特徵,X1和X2同維度
    pre=np.zeros(X1.shape)
    for h in H:
        df,t,lv,rv=h  #劃分特徵,劃分點,左枝取值，右枝取值
        X=X1 if df==0 else X2
        pre+=(X<=t)*lv+(X>t)*rv
    return np.sign(pre)



#>>>>>西瓜數據集3.0α
X=np.array([[0.697,0.46],[0.774,0.376],[0.634,0.264],[0.608,0.318],[0.556,0.215],
   [0.403,0.237],[0.481,0.149],[0.437,0.211],[0.666,0.091],[0.243,0.267],
   [0.245,0.057],[0.343,0.099],[0.639,0.161],[0.657,0.198],[0.36,0.37],
   [0.593,0.042],[0.719,0.103]])
Y=np.array([1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1])
m=len(Y)
#>>>>>Bagging
T=20
H=[]       #存儲各個決策樹樁，
           #每行爲四元素列表，分別表示劃分特徵,劃分點,左枝取值，右枝取值
H_pre=np.zeros(m)  #存儲每次迭代後H對於訓練集的預測結果
error=[]           #存儲每次迭代後H的訓練偏差
for t in range(T):
    boot_strap_sampling=np.random.randint(0,m,m)   #產生m個隨機數
    Xbs=X[boot_strap_sampling]                     #自助採樣
    Ybs=Y[boot_strap_sampling]                     #自助採樣
    h=decision_sdumps_MaxInfoGain(Xbs,Ybs)         #訓練基學習器
    H.append(h)                                    #存入基學習器
    #計算並存儲訓練偏差
    df,t,lv,rv=h                                   #基學習器參數
    Y_pre_h=(X[:,df]<=t)*lv+(X[:,df]>t)*rv         #基學習器預測結果
    H_pre+=Y_pre_h                                 #更新集成預測結果
    error.append(sum(((H_pre>=0)*2-1)!=Y)/m)       #當前集成預測的訓練偏差
H=np.array(H)

#>>>>>繪製訓練偏差變化曲線
plt.title('訓練偏差的變化')
plt.plot(range(1,T+1),error,'o-',markersize=2)
plt.xlabel('基學習器個數')
plt.ylabel('錯誤率')
plt.show()
#>>>>>觀察結果
x1min,x1max=X[:,0].min(),X[:,0].max()
x2min,x2max=X[:,1].min(),X[:,1].max()
x1=np.linspace(x1min-(x1max-x1min)*0.2,x1max+(x1max-x1min)*0.2,100)
x2=np.linspace(x2min-(x2max-x2min)*0.2,x2max+(x2max-x2min)*0.2,100)
X1,X2=np.meshgrid(x1,x2)

for t in [3,5,11,15,20]:
    plt.title('前%d個基學習器'%t)
    plt.xlabel('密度')
    plt.ylabel('含糖量')
    #plt.contourf(X1,X2,Ypre)
    # 畫樣本數據點
    plt.scatter(X[Y==1,0],X[Y==1,1],marker='+',c='r',s=100,label='好瓜')
    plt.scatter(X[Y==-1,0],X[Y==-1,1],marker='_',c='k',s=100,label='壞瓜')
    plt.legend()
    # 畫基學習器劃分邊界
    for i in range(t):
        feature,point=H[i,:2]
        if feature==0:
            plt.plot([point,point],[x2min,x2max],'k',linewidth=1)
        else:
            plt.plot([x1min,x1max],[point,point],'k',linewidth=1)
    # 畫基集成效果的劃分邊界
    Ypre=predict(H[:t],X1,X2)
    plt.contour(X1,X2,Ypre,colors='r',linewidths=5,levels=[0])   
    plt.show()

以完整決策樹做爲基學習器

# -*- coding: utf-8 -*-
"""
Created on Tue Mar 17 13:16:42 2020

@author: MS

前面採用決策樹樁來進行Bagging集成，效果較差，
如今改用全決策樹full-tree來集成，觀察效果。
全決策樹算法再也不自編，直接採用sklearn工具。
"""


import numpy as np
import matplotlib.pyplot as plt
from sklearn import tree

#設置出圖顯示中文
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus'] = False

def predict(H,X1,X2):
    # 預測結果
    # 僅X1和X2兩個特徵,X1和X2同維度
    X=np.c_[X1.reshape(-1,1),X2.reshape(-1,1)]
    Y_pre=np.zeros(len(X))
    for h in H:
        Y_pre+=h.predict(X)
    Y_pre=2*(Y_pre>=0)-1
    Y_pre=Y_pre.reshape(X1.shape)
    return Y_pre



#>>>>>西瓜數據集3.0α
X=np.array([[0.697,0.46],[0.774,0.376],[0.634,0.264],[0.608,0.318],[0.556,0.215],
   [0.403,0.237],[0.481,0.149],[0.437,0.211],[0.666,0.091],[0.243,0.267],
   [0.245,0.057],[0.343,0.099],[0.639,0.161],[0.657,0.198],[0.36,0.37],
   [0.593,0.042],[0.719,0.103]])
Y=np.array([1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1])

#>>>>>Bagging
T=20
H=[]       #存儲各個決策樹樁，每行表示#劃分特徵,劃分點,左枝取值，右枝取值
m=len(Y)
H_pre=np.zeros(m)  #存儲每次迭代後H對於訓練集的預測結果
error=[]           #存儲每次迭代後H的訓練偏差
for t in range(T):
    boot_strap_sampling=np.random.randint(0,m,m)
    Xbs=X[boot_strap_sampling]
    Ybs=Y[boot_strap_sampling]
    h=tree.DecisionTreeClassifier().fit(Xbs,Ybs)
    H.append(h)
    # 計算並存儲當前步的訓練偏差
    H_pre+=h.predict(X)
    Y_pre=(H_pre>=0)*2-1
    error.append(sum(Y_pre!=Y)/m)
    

#>>>>>繪製訓練偏差變化曲線
plt.title('訓練偏差的變化')
plt.plot(range(1,T+1),error,'o-',markersize=2)
plt.xlabel('基學習器個數')
plt.ylabel('錯誤率')
plt.show()

#>>>>>觀察結果
x1min,x1max=X[:,0].min(),X[:,0].max()
x2min,x2max=X[:,1].min(),X[:,1].max()
x1=np.linspace(x1min-(x1max-x1min)*0.2,x1max+(x1max-x1min)*0.2,100)
x2=np.linspace(x2min-(x2max-x2min)*0.2,x2max+(x2max-x2min)*0.2,100)
X1,X2=np.meshgrid(x1,x2)

for t in [3,5,11]:
    plt.title('前%d個基學習器'%t)
    plt.xlabel('密度')
    plt.ylabel('含糖量')
    # 畫樣本數據點
    plt.scatter(X[Y==1,0],X[Y==1,1],marker='+',c='r',s=100,label='好瓜')
    plt.scatter(X[Y==-1,0],X[Y==-1,1],marker='_',c='k',s=100,label='壞瓜')
    plt.legend()
    # 畫基學習器劃分邊界
    for i in range(t):
        #因爲sklearn.tree類中將決策樹的結構參數封裝於內部，
        #不方便提取，這裏採用一個笨辦法：
        #用predict方法對區域內全部數據點(100×100)進行預測，
        #而後再用plt.contour的方法來找出劃分邊界
        Ypre=predict([H[i]],X1,X2)
        plt.contour(X1,X2,Ypre,colors='k',linewidths=1,levels=[0])
    # 畫集成學習器劃分邊界
    Ypre=predict(H[:t],X1,X2)
    plt.contour(X1,X2,Ypre,colors='r',linewidths=5,levels=[0])
    plt.show()