機(jī)器學(xué)習(xí)筆記-決策樹跟分類規(guī)則

決策樹(Decision Tree)

決策樹學(xué)習(xí)，建立一顆樹結(jié)構(gòu)的模型。此模型由一系列邏輯決策構(gòu)成。在此結(jié)構(gòu)中決策點(diǎn)代表某個(gè)屬性上的決策，分支表示決策選擇項(xiàng)，樹的葉子節(jié)點(diǎn)是一系列聯(lián)合決策的結(jié)論。

決策樹通過分而治之（Divide and conquer）方式-遞歸劃分（recurisive partitioning）來建立。在這個(gè)建立過程中，我們從代表所有數(shù)據(jù)的根節(jié)點(diǎn)出發(fā)，選擇通向目標(biāo)分類的特性把樣本拆分成不同的組,如此直至觸及停止標(biāo)準(zhǔn)。有幾類停止標(biāo)準(zhǔn), 節(jié)點(diǎn)上的所有或幾乎所有的樣本都是屬于同一類;沒有特征能對樣本進(jìn)行繼續(xù)分類了;樹已經(jīng)觸及預(yù)定義的大小限制.

建立決策樹面對的第一個(gè)挑戰(zhàn)就是從哪個(gè)特征著手進(jìn)行切分。如果我們切分出來的分段數(shù)據(jù)僅包含一類數(shù)據(jù)，那我們說這個(gè)“一致”（Pure）的。 

我們用熵來度量一個(gè)集合的無序程度。度量無序程度還可以用基尼不純度（Gini impurity）。這里我先學(xué)習(xí)了熵。

             c 

    Entropy(S) = Σ  -Pi log2(Pi)

             i=1

熵計(jì)算公式中各個(gè)部分的意義如下。在一個(gè)分段S上有c個(gè)類層次。Pi是第i個(gè)類層次的占比。

  有了一致性衡量的熵，我們就可以來解決如何拆分樣本。這里就得說到信息增益（Information Gain）

    InfoGain(F) = Entropy(S1) - Entropy(S2)

信息增益就是樣本拆分前后的熵的差值。拆分后的熵的計(jì)算公式如下：

                   n 

    Entropy(S) = Σ  wi Entropy(Pi)

              i=1

這個(gè)就是拆分后各部分的熵Entropy(Pi)如這一部分在總樣本中所占比的乘積的總和。

信息增益越高表明分拆越有效。

決策樹算法：

a. C5.0

  在C5.0里我們用熵（entropy）來衡量一致性。熵為0則表示樣本是完全同質(zhì)的。熵值越高則表示越無序。 

當(dāng)樹膨脹到一定大小后會導(dǎo)致決策過于特殊化, 得出的模型過擬合?？朔爽F(xiàn)象的做法有pre-pruning跟post-pruning。 pre-pruning就是當(dāng)決策點(diǎn)達(dá)到某個(gè)量時(shí)或者決策節(jié)點(diǎn)中只包含少量樣本是就停止樹的構(gòu)建。pre-pruning無法預(yù)知會不會遺漏掉某些細(xì)微的但是有相當(dāng)重要的模式。

pre-pruning之外的另一個(gè)方法就是post-pruning。當(dāng)樹構(gòu)建的相當(dāng)大后，我們用某些基于誤碼率的修剪標(biāo)準(zhǔn)來修建樹。這個(gè)方式通常比pre-pruning更有效。

在post-pruning的過程有連個(gè)可能的處理，一個(gè)是子樹提升（subtree raising）,還有一個(gè)是子樹置換（subtree replacement）

C5.0很容易通過調(diào)整訓(xùn)練選項(xiàng)來在過擬合跟欠擬合間達(dá)成平衡。

C5.0比C4.5增加了自適應(yīng)增強(qiáng)（adaptive boosting）.前一個(gè)分類器分錯(cuò)的樣本會被用來訓(xùn)練下一個(gè)分類器。AdaBoost方法對于噪聲數(shù)據(jù)和異常數(shù)據(jù)很敏感。但在一些問題中，AdaBoost方法相對于大多數(shù)其它學(xué)習(xí)算法而言，不會很容易出現(xiàn)過擬合現(xiàn)象。AdaBoost方法中使用的分類器可能很弱（比如出現(xiàn)很大錯(cuò)誤率），但只要它的分類效果比隨機(jī)好一點(diǎn)（比如兩類問題分類錯(cuò)誤率略小于0.5），就能夠改善最終得到的模型。而錯(cuò)誤率高于隨機(jī)分類器的弱分類器也是有用的，因?yàn)樵谧罱K得到的多個(gè)分類器的線性組合中，可以給它們賦予負(fù)系數(shù)，同樣也能提升分類效果。

除了自適應(yīng)增強(qiáng)，C5.0還可以提供一個(gè)成本矩陣（cost matrix）來修正模型。

http://sjchen.im.nuu.edu.tw/MachineLearning/final/CLS_DT.pdf

分類規(guī)則（classification rule）

分類規(guī)則表示的是if-else形式的知識,規(guī)則由先導(dǎo)（antecedent）跟后繼（consequence）構(gòu)成一個(gè)假設(shè)。

One rule算法

RIPPER算法（Repeated Incremental Pruning to Produce Error Reduction）

發(fā)展

修剪

優(yōu)化

從決策樹到規(guī)則