非參數(shù)方法——決策樹實(shí)現(xiàn)的判別式

介紹
第一部分 參數(shù)方法——類密度模型參數(shù)估計(jì)
第二部分 監(jiān)督學(xué)習(xí)——分類（基于似然的方法）
第三部分 監(jiān)督學(xué)習(xí)——分類（基于判別式的方法）（參數(shù)方法——判別式參數(shù)估計(jì)）
第四部分 監(jiān)督學(xué)習(xí)——回歸
第五部分 監(jiān)督學(xué)習(xí)——關(guān)聯(lián)規(guī)則
第六部分 維度規(guī)約（特征的提取和組合）
第七部分 半?yún)?shù)方法
第八部分 非監(jiān)督學(xué)習(xí)——聚類
第九部分 非參數(shù)方法——密度估計(jì)
第十部分 非參數(shù)方法——決策樹實(shí)現(xiàn)的判別式
第十一部分 多層感知器——非參數(shù)估計(jì)器
第十二部分 局部模型
第十三部分 支持向量機(jī)與核機(jī)器
第十四部分 隱馬爾科夫模型
第十五部分 參數(shù)的貝葉斯估計(jì)
第十六部分 集成學(xué)習(xí)——組合多學(xué)習(xí)器
第十七部分 增強(qiáng)學(xué)習(xí)
第十八部分 機(jī)器學(xué)習(xí)實(shí)驗(yàn)
第十九部分 特征工程與數(shù)據(jù)預(yù)處理

通過參數(shù)方法，半?yún)?shù)方法，非參數(shù)方法估計(jì)先驗(yàn)密度\hat P(C_i)和類似然\hat p(\mathbf{x}|C_i)。然后通過計(jì)算后驗(yàn)，并定義判別式函數(shù)，來進(jìn)行判斷。
這樣的方法都是基于對似然或后驗(yàn)概率的估計(jì)的。繞過這些，直接估計(jì)判別式函數(shù)，而不是通過后驗(yàn)來定義判別式，則為基于判別式的方法。

決策樹

決策樹是一種實(shí)現(xiàn)分治策略的層次數(shù)據(jù)結(jié)構(gòu)。是一種有效的非參數(shù)方法，可用于分類和回歸。

對于參數(shù)估計(jì)，我們定義整個輸入空間上的模型，使用所有訓(xùn)練數(shù)據(jù)來學(xué)習(xí)模型的參數(shù)。
對于非參數(shù)方法，在估計(jì)密度時，把輸入空間劃分成由距離度量定義的 局部區(qū)域。對每個輸入x，使用x周邊區(qū)域內(nèi)的訓(xùn)練數(shù)據(jù)來估計(jì)對應(yīng)的局部模型。

決策樹是一種用于監(jiān)督學(xué)習(xí)的層次模型，其局部區(qū)域通過少數(shù)幾部遞歸分裂確定。決策樹由內(nèi)部決策節(jié)點(diǎn)和終端樹葉組成，每個決策節(jié)點(diǎn)對輸入進(jìn)行一個測試，來確定輸出分支。這個決策過程從根節(jié)點(diǎn)開始，不斷遞歸，直到到達(dá)一個樹葉節(jié)點(diǎn)。

決策樹也是一種非參數(shù)方法，但不像“非參數(shù)方法——密度估計(jì)”一節(jié)，它不對類密度假定任何參數(shù)形式。并且不會預(yù)先確定樹結(jié)構(gòu)（就像預(yù)先確定密度模型）。而是隨著學(xué)習(xí)，不斷生長樹，添加節(jié)點(diǎn)和樹葉分支。

每個決策節(jié)點(diǎn)m上的f_m(x)都定義一個d為輸入空間上的判別式，將空間劃分為較小的區(qū)域。f_m(x)是一個簡單函數(shù)，決策樹去學(xué)習(xí)一個復(fù)雜函數(shù)時，就是將復(fù)雜函數(shù)分解成一系列簡單的決策。

不同的決策樹對f_m(\centerdot)假設(shè)不同的模型，不同的模型確定了判別式的形狀和區(qū)域的形狀。每一個樹葉節(jié)點(diǎn)有一個輸出，對于分類來說，輸出就是標(biāo)號，而對回歸而言輸出則為數(shù)值。


單變量樹

在單變量輸入時，每個內(nèi)部節(jié)點(diǎn)中的測試只使用實(shí)例維度屬性中的其中一維，作為輸入。
通過訓(xùn)練數(shù)據(jù)構(gòu)建樹的過程叫做樹歸納。但對于給定訓(xùn)練集，存在不止一個對其無錯編碼的樹，我們希望找到的是其中的最小樹。樹的大小用樹中的節(jié)點(diǎn)數(shù)和決策節(jié)點(diǎn)的復(fù)雜性度量。尋找最小樹是NP完全問題，因此我們必須使用給予啟發(fā)式的局部搜索過程。

分類樹

在用于分類的決策樹中，劃分的優(yōu)劣由不純度來度量。一個劃分是純的，如果對于所有分支，劃分后選擇相同分支的實(shí)例都屬于相同的類。對于節(jié)點(diǎn)m，令N_m為到達(dá)節(jié)點(diǎn)m的訓(xùn)練實(shí)例集。對于根節(jié)點(diǎn)，N_m=N。其中N_m^i個屬于C_i類，\sum_iN_m^i=N_m。

如果一個實(shí)例到達(dá)m節(jié)點(diǎn)，那么它說與C_i類的概率估計(jì)為\hat P(C_i|x,m)=p_m^i=\frac{N_m^i}{N_m}。

如果m節(jié)點(diǎn)是純的，那么對于所有i，有p_m^i為0或1。這時，不再需要進(jìn)一步劃分，并可以添加一個葉子節(jié)點(diǎn)，用p_m^i=1的類 i 進(jìn)行標(biāo)號。


  • 不純度度量

    常用熵來度量不純度：\mathbf{I}_m=-\sum_{i=1}^Kp_m^i\log_2p_m^i
    其中0\log0\equiv0。在信息論中，熵是對一個實(shí)例的類代碼進(jìn)行編碼所需要的最少位數(shù)。

    當(dāng)然熵并非唯一的度量，對于兩類問題，其中p^1\equiv p，p^2=1-p，函數(shù)\phi (p,1-p)是非負(fù)函數(shù)，它可以用來度量不純度，如果它滿足以下條件：
    （1）對于任意p\in[0,1]，\phi(1/2,1/2)\geq\phi(p,1-p)。
    （2）\phi(0,1)=\phi(1,0)=0
    （3）當(dāng)p在[0,1/2]上時，\phi(p,1-p)是遞增的，而p在[1/2,1]上時，遞減。
    函數(shù)\phi(p,1-p)包含以下幾個例子：

    • 熵\phi(p,1-p)=-p\log_2p-(1-p)\log_2(1-p)
    • Gini指數(shù)\phi(p,1-p)=2p(1-p)
    • 誤分類誤差\phi(p,1-p)=1-\max (p,1-p)

    對于K>2的情況，可類似地推廣。上面三個度量之間并無顯著差異。


如果m節(jié)點(diǎn)是不純的，則應(yīng)當(dāng)劃分實(shí)例來降低不純度。在所有可能的劃分中，我們選擇最小化劃分后不純度的劃分。

在節(jié)點(diǎn)m，經(jīng)節(jié)點(diǎn)的決策函數(shù)f_m(x)，N_m中的N_{mj}被劃分到 j 分支。（如常見的，對離散屬性有n個輸出分支；對數(shù)值屬性有2個輸出分支）自然地有\sum_{j=1}^KN_{mj}=N_m。

考慮輸入為離散屬性，在 j 分支中，有N_{mj}^i個屬于類C_i，\sum_{i=1}^KN_{mj}^i=N_{mj}。

于是對于節(jié)點(diǎn)m，決策函數(shù)返回輸出 j，而實(shí)例屬于類C_i的概率估計(jì)為：

\hat P(C_i|x,m,j)\equiv p_{mj}^i=\frac{N_{mj}^i}{N_{mj}}

而劃分后的總不純度為：

\mathbf{I}_m^{\prime}=-\sum_{j=1}^n\frac{N_{mj}}{N_m}\sum_{i=1}^Kp_{mj}^i\log_2p_{mj}^i。

對于輸入為數(shù)值屬性，決策函數(shù)通過閾值將輸入空間一分為二。在N_m個數(shù)據(jù)點(diǎn)之間，存在N_m-1個可能的\omega_{m0}作為閾值（N_m個點(diǎn)中每兩個點(diǎn)的中值點(diǎn)）。最佳的劃分點(diǎn)總是存在于屬于不同的兩個相鄰點(diǎn)之間。這樣，在構(gòu)建數(shù)值屬性的決策樹時，檢查每個中值點(diǎn)，選擇有最大純度的作為閾值。這一步迭代在離散屬性下是沒有的。

構(gòu)建決策樹的基本思想，就是對于所有的不純分支，迭代地、并行地構(gòu)建新的分支，選擇具有最小熵的劃分位置，直到所有的分支都是純的。從而實(shí)現(xiàn)分類和回歸的目的。

一個問題是，這種劃分偏向于選擇許多樹葉分支。因?yàn)檫@樣會使總不純度很小。例如選取訓(xùn)練樣本的編號作為屬性，那么就會形成每個分支都只有一個實(shí)例，不純度均為0的決策樹。這顯然不合理。許多分支節(jié)點(diǎn)過于復(fù)雜，背離了決策樹把類判別式劃分成簡單決策的思想。

類似的，當(dāng)輸入實(shí)例存在噪聲時，構(gòu)建樹直到它是最純的，就會產(chǎn)生一棵非常大，并且過擬合的樹。

需要通過加罰來均衡不純度下降和分支數(shù)量這兩個屬性。設(shè)置某個閾值\theta_p，我們不需要p_{mj}^i為0或1，只需要接近0或1就可以。


回歸樹

于分類樹相比，只需要將適用于分類的不純度度量，換成適用于回歸的不純度度量。
對節(jié)點(diǎn)m，記X_m是訓(xùn)練集X中到達(dá)m點(diǎn)的子集。定義
b_m(\mathbf{x})=\begin{equation}\left\{ \begin{array}{} 1, & if\ \mathbf{x} \in X_m\\ 0, & else \end{array} \right. \end{equation}
和其他回歸方法一樣，在回歸樹中，劃分的好壞可以用估計(jì)值的均方誤差度量。令g_m為節(jié)點(diǎn)m中的估計(jì)值。
E_m=\frac1{N_m}\sum_t(r^t-g_m)^2b_m(\mathbf{x}^t)
其中N_m=|X_m|=\sum_tb_m(\mathbf{x}^t)。
各節(jié)點(diǎn)中，用節(jié)點(diǎn)中訓(xùn)練實(shí)例的輸出的均值作為估計(jì)值：g_m=\frac {\sum_tb_m(\mathbf{x}^t)r^t} {\sum_tb_m(\mathbf x^t)}

如果一個節(jié)點(diǎn)上的誤差E_m<\theta_r是可以接受的。那么久創(chuàng)建一個樹葉節(jié)點(diǎn)，輸出g_m，不再進(jìn)一步分裂。
如果誤差不能接受，則需要對到達(dá)節(jié)點(diǎn)m的數(shù)據(jù)進(jìn)一步劃分，使分裂后的各分支的誤差和最小。
令X_{mj}為X_m的被劃為到 j 分支的子集。定義
b_{mj}=\left\{ \begin{array}{} 1, & if\ \mathbf{x} \in X_{mj} \\ 0, & else \end{array} \right.
g_{mj}是節(jié)點(diǎn)m的分支 j 上的估計(jì)值。則劃分后的誤差為
E_m^{\prime}=\frac{1}{N_m}\sum_j\sum_t(r^t-g_{mj})^2b_{mj}(\mathbf{x}^t)
和分類樹一樣，我們尋找最小化誤差的分割閾值。

除了均方誤差，還可使用最大可能誤差來度量劃分的好壞
E_m=\max_j\max_t|r^t-g_{mj}|b_{mj}(\mathbf{x}^t)
這樣可以保證任何實(shí)例的誤差都小于給定閾值。

可接受的誤差閾值 是復(fù)雜度參數(shù)。閾值越小，生成的樹越大并且過擬合的風(fēng)險(xiǎn)越大；閾值越大，欠擬合或說過光滑的可能性越大。

類似于非參數(shù)密度估計(jì)的回歸問題中，移動均值與移動直線的方法。在決策樹中，也可以不適用樹葉上的均值來作為估計(jì)輸出，而是在葉子上做線性回歸來擬合樹葉上的實(shí)例：
g_m(\mathbf{x})=\mathbf{\omega}_m^T\mathbf{x}+\omega_{m0}
這使得每個樹葉上的輸入x，根據(jù)線性回歸函數(shù)有不同的輸出。但這需要額外的開銷來進(jìn)行線性回歸。


剪枝

通常，到達(dá)一個節(jié)點(diǎn)的訓(xùn)練實(shí)例數(shù)小于整個訓(xùn)練集的某個百分比，則無論該節(jié)點(diǎn)純度（誤差）如何，都不在進(jìn)一步進(jìn)行劃分。
其基本思想是，基于過少實(shí)例的決策樹（將該節(jié)點(diǎn)看做根節(jié)點(diǎn)，進(jìn)一步劃分相當(dāng)于構(gòu)建新的樹）導(dǎo)致較大的方差，從而導(dǎo)致較大的泛化誤差。這種在構(gòu)建樹時提前停止構(gòu)建的做法叫做先剪枝。

相對地，另一種可能的方法是后剪枝，實(shí)踐中的效果比先剪枝更好。
前面所介紹的樹的構(gòu)建過程，都是貪心的。每一步做出最小化不純度的選擇，永不回溯修改。但后剪枝方法不同，它試圖找出并剪掉不必要的子樹。
在后剪枝中，先從訓(xùn)練數(shù)據(jù)集中抽取一部分作為剪枝集。使用去掉剪枝集后的訓(xùn)練集，讓樹增長到所有樹葉都是純的，具有零誤差。對于得到的樹的每一個子樹，用一個被該子樹覆蓋的訓(xùn)練實(shí)例標(biāo)記的樹葉節(jié)點(diǎn)替換它。如果該樹葉在剪枝集上的性能不比該子樹差，則剪掉子樹，因?yàn)樗沁^擬合的，該子樹的附加復(fù)雜性是不必要的。否則保留子樹。


用決策樹提取特征及規(guī)則

決策樹能夠 提取特征。單變量樹只是用必要的變量，并在樹構(gòu)建之后某些特征可能根本沒有使用。所以可以使用決策樹提取特征，將構(gòu)建得的決策樹所使用的特征作為其他學(xué)習(xí)方法的輸入。
決策樹具有較好的可解釋性。因?yàn)闆Q策樹節(jié)點(diǎn)中的條件簡單，易于理解。從樹根到樹葉的每條路徑都是條件判斷的合取。這些路徑構(gòu)成 IF-THEN 的規(guī)則集。

當(dāng)然，在訓(xùn)練決策樹前，根據(jù)業(yè)務(wù)先驗(yàn)知識，選取對訓(xùn)練數(shù)據(jù)具有分類能力的特征作為輸入特征，也是很有比較的。這相當(dāng)于為決策樹訓(xùn)練做特征提取。


多變量樹

在單變量樹中，對節(jié)點(diǎn)進(jìn)行劃分時只是用一個輸入維。而在多變量樹種，每個決策節(jié)點(diǎn)都可以使用所有的輸入維，這種情況更普遍。
當(dāng)輸入是數(shù)值屬性時，節(jié)點(diǎn)的線性決策函數(shù)為f_m(\mathbf{x})=\omega_m^T \mathbf{x}+\omega_{m0}。其定義了輸入空間中的超平面，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑上的一步一步劃分，最終葉子節(jié)點(diǎn)定義輸入空間上的多面體。
在節(jié)點(diǎn)上使用非線性多變量決策函數(shù)，可以更加靈活。如使用二次多項(xiàng)式f_m(\mathbf{x})=\mathbf{x}^TW_m\mathbf{x}+\boldsymbol{\omega}_m^T \mathbf{x}+\omega_{m0}


決策樹的復(fù)雜性

實(shí)際上，對于任何分類方法，都是從假設(shè)類中選取一個假設(shè)來近似一個實(shí)際判別式。如果使用單變量輸入，那么判別式近似于分段的，平行于軸的超平面。而是用多變量輸入，線性組合就是任意的超平面，非線性組合可以得到曲面。
決策樹的超參數(shù)包括節(jié)點(diǎn)的決策函數(shù)的復(fù)雜度、決策節(jié)點(diǎn)的分支數(shù)。分支數(shù)決定了決策節(jié)點(diǎn)的決策判別式的個數(shù)。具有兩個分支的決策節(jié)點(diǎn)將輸入空間一分為二，而具有n個分支的決策節(jié)點(diǎn)將輸入空間劃分為n個部分。
這樣，樹的大小與節(jié)點(diǎn)復(fù)雜度和分支數(shù)之間存在相關(guān)性。使用簡單節(jié)點(diǎn)和較小分支數(shù)的時候可以得到一顆更大的樹，這樣的樹可解釋性更好。
更復(fù)雜的節(jié)點(diǎn)需要更多的數(shù)據(jù)來訓(xùn)練，隨著沿樹向下，數(shù)據(jù)越來越少，更容易出現(xiàn)過擬合。同時，節(jié)點(diǎn)復(fù)雜的樹比較小，也就失去了通過樹將問題簡化為一系列小問題的初衷。

實(shí)際上，可以在靠近樹根的地方使用較復(fù)雜的節(jié)點(diǎn)，而隨著樹的向下，數(shù)據(jù)越來越少，問題越來越簡單，再采用相對簡單的節(jié)點(diǎn)。

此外，前面所討論的決策節(jié)點(diǎn)都是“硬”的，依賴于決策函數(shù)，每次去一個確定的分支。在“軟”決策樹中，每次經(jīng)過決策節(jié)點(diǎn)，按計(jì)算后的概率取各分支上結(jié)果的加權(quán)。


決策森林

決策森林是一系列決策樹的voting或系綜，屬于集成學(xué)習(xí)方法。其訓(xùn)練的是多棵決策樹，每一棵決策樹在訓(xùn)練集的隨機(jī)子集上訓(xùn)練，并最終組合各個決策樹的結(jié)果，這就是隨機(jī)森林方法的思想。其總體的準(zhǔn)確率可以顯著提高。集成學(xué)習(xí)的介紹見《集成學(xué)習(xí)——組合多學(xué)習(xí)器》


作為非參數(shù)方法的決策樹

不同于基于實(shí)例的密度估計(jì)，決策樹
1.每個樹葉對應(yīng)于一個“箱”，但決策樹的箱不固定寬度，或k個近鄰實(shí)例。
2.決策樹中“箱”的劃分不根據(jù)輸入空間的相似度，而是通過熵或均方誤差，來決定是否進(jìn)一步拆箱。
3.由于采用樹結(jié)構(gòu)，只需要通過少量比較就可以找到每個實(shí)例所屬的箱。不需基于實(shí)例方法一樣，需要每次一一計(jì)算相似度。
4.決策樹一旦構(gòu)造完成，就不需要存儲訓(xùn)練實(shí)例，而只需要存儲樹結(jié)構(gòu)、決策節(jié)點(diǎn)參數(shù)和樹葉節(jié)點(diǎn)的輸出?？臻g復(fù)雜度更小。而基于實(shí)例的密度估計(jì)，每次重新輸入一個x，都需要基于訓(xùn)練數(shù)據(jù)重新計(jì)算輸出。

決策樹就是一種基于判別式的方法，繞開了類密度估計(jì)，直接估計(jì)判別式。關(guān)于一些基本的決策樹算法可見《決策樹基本要點(diǎn)及方法對比》

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容