數(shù)據(jù)挖掘之決策樹分類

1. 理論知識(shí)

決策樹分類算法的一般流程如下：一開始，所有的實(shí)例均位于根節(jié)點(diǎn)，所有參數(shù)的取值均離散化；根據(jù)啟發(fā)規(guī)則選擇一個(gè)參數(shù)，根據(jù)參數(shù)取值的不同對(duì)實(shí)例集進(jìn)行分割；對(duì)分割后得到的節(jié)點(diǎn)進(jìn)行同樣的啟發(fā)式參數(shù)選擇分割過程，如此往復(fù)，直到(a)分割得到的實(shí)例集合屬于同一類；(b)參數(shù)用完，以子集中絕大多數(shù)的實(shí)例類別作為該葉節(jié)點(diǎn)的類別。

   基于熵的概念，我們可以得到參數(shù)選擇的第一個(gè)規(guī)則：信息增益(Info Gain).信息增益的定義是分裂前的節(jié)點(diǎn)熵減去分裂后子節(jié)點(diǎn)熵的加權(quán)和，即不純度的減少量，也就是純度的增加量。參數(shù)選擇的規(guī)則是：選擇使信息增益最大的參數(shù)分割該節(jié)點(diǎn)。信息增益計(jì)算的算例如下圖。

   信息增益存在的問題時(shí):總是傾向于選擇包含多取值的參數(shù)，因?yàn)閰?shù)的取值越多，其分割后的子節(jié)點(diǎn)純度可能越高。為了避免這個(gè)問題，我們引入了增益比例(Gain Ratio)的選擇指標(biāo)，其定義如下圖所示。

   增益比例存在的問題是：傾向于選擇分割不均勻的分裂方法，舉例而言，即一個(gè)拆分若分為兩個(gè)節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)特別多的實(shí)例，一個(gè)節(jié)點(diǎn)特別少的實(shí)例，那么這種拆分有利于被選擇。

   為了克服信息增益和增益比例各自的問題，標(biāo)準(zhǔn)的解決方案如下：首先利用信息增益概念，計(jì)算每一個(gè)參數(shù)分割的信息增益，獲得平均信息增益；選出信息增益大于平均值的所有參數(shù)集合，對(duì)該集合計(jì)算增益比例，選擇其中增益比例最大的參數(shù)進(jìn)行決策樹分裂。 

   上面介紹的是基于熵概念的參數(shù)選擇規(guī)則，另一種流行的規(guī)則稱為基尼指數(shù)（Gini Index），其定義如下圖?；嵯禂?shù)在節(jié)點(diǎn)類別分布均勻時(shí)取最大值1-1/n，在只包含一個(gè)類別時(shí)取最小值0. 所以與熵類似，也是一個(gè)描述不純度的指標(biāo)。

   基于基尼系數(shù)的規(guī)則是：選擇不純度減少量(Reduction in impurity)最大的參數(shù)。不純度減少量是分割前的Gini index減去分割后的Gini index?；嵯禂?shù)的特點(diǎn)與信息增益的特點(diǎn)類似。

過度擬合問題(Overfitting)

  過度擬合問題是對(duì)訓(xùn)練數(shù)據(jù)完全擬合的決策樹對(duì)新數(shù)據(jù)的預(yù)測能力較低。為了解決這個(gè)問題，有兩種解決方法。第一種方法是前剪枝(prepruning)，即事先設(shè)定一個(gè)分裂閾值，若分裂得到的信息增益不大于這個(gè)閾值，則停止分裂。第二種方法是后剪枝（postpruning），首先生成與訓(xùn)練集完全擬合的決策樹，然后自下而上地逐層剪枝，如果一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)被刪除后，決策樹的準(zhǔn)確度沒有降低，那么就將該節(jié)點(diǎn)設(shè)置為葉節(jié)點(diǎn)（基于的原則是Occam剪刀：具有相似效果的兩個(gè)模型選擇較簡單的那個(gè)）。

Scalable決策樹分類算法

   這里介紹兩個(gè)算法，一個(gè)是RainForest，其主要的貢獻(xiàn)是引入了一個(gè)稱為AVC的數(shù)據(jù)結(jié)構(gòu)，其示意圖如下。主要的作用是加速參數(shù)選擇過程的計(jì)算。

   另一個(gè)算法稱為BOAT，其采用了稱為bootstrap的統(tǒng)計(jì)技術(shù)對(duì)數(shù)據(jù)集進(jìn)行分割，在分割的子數(shù)據(jù)集上分別構(gòu)造決策樹，再基于這些決策樹構(gòu)造一個(gè)新的決策樹，文章證明這棵新樹與基于全局?jǐn)?shù)據(jù)集構(gòu)造的決策樹非常相近。這種方法的主要優(yōu)勢在于支持增量更新。