數據挖掘之決策樹分類

1. 理論知識

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

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

   信息增益存在的問題時:總是傾向于選擇包含多取值的參數，因為參數的取值越多，其分割后的子節點純度可能越高。為了避免這個問題，我們引入了增益比例(Gain Ratio)的選擇指標，其定義如下圖所示。

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

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

   上面介紹的是基于熵概念的參數選擇規則，另一種流行的規則稱為基尼指數（Gini Index），其定義如下圖?；嵯禂翟诠濣c類別分布均勻時取最大值1-1/n，在只包含一個類別時取最小值0. 所以與熵類似，也是一個描述不純度的指標。

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

過度擬合問題(Overfitting)

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

Scalable決策樹分類算法

   這里介紹兩個算法，一個是RainForest，其主要的貢獻是引入了一個稱為AVC的數據結構，其示意圖如下。主要的作用是加速參數選擇過程的計算。

   另一個算法稱為BOAT，其采用了稱為bootstrap的統計技術對數據集進行分割，在分割的子數據集上分別構造決策樹，再基于這些決策樹構造一個新的決策樹，文章證明這棵新樹與基于全局數據集構造的決策樹非常相近。這種方法的主要優勢在于支持增量更新。