学习笔记之——决策树

决策树（Decision Tree）应该算是机器学习（Machine Learning）中最简单的分类模型之一，而且由于决策树逻辑规则清晰，它的可解释性比较强。在实务中，决策树通常是分类学习模型的第一选择。

决策树有三种算法，分别为ID3、C4.5和CART（Classification and Regreesion Tree），区别主要在于节点分裂时基于的标准不同。ID3的分裂标准是让分裂前后数据集的信息熵（Entropy）差异，即信息增益最大化。信息熵的概念来源于信息论，由数学家香农（Shannon）提出，用来刻画系统的不确定性。系统的熵值越大，则系统不确定性越大。C4.5是ID3的升级版，刻画标准由信息增益改成信息增益率，来修正ID3通常倾向于选择特征取值较多的特征进行分类的问题。

现在机器学习中流行的决策树算法是CART。由名字可以看出，CART既可以用来做回归，也可以用来做分类。我们这里只讨论用CART来学习分类器。实际上，CART的回归功能也是可以用来分类的，在集成学习（Ensemble Learning）中GBDT（Gradient Boosting Decision Tree）模型正是用回归的CART作为基学习器，这个原理类似逻辑回归（Logistic Regression）。CART决策树是一个二叉树，比较直观易解释，它的分裂标准是使分裂前后基尼系数（Gini Index）差值最大。基尼系数跟信息熵的性质基本相似，也是刻画系统不确定性和纯度的量。

CART决策树生成流程大致如下：

1、计算训练数据集的基尼系数；

2、计算每个属性分裂后训练数据集的基尼系数，选择差异最大的分裂特征和分裂值；

3、重复上述过程，直到达到停止标准，比如叶子节点包含样本不得低于某个设定值等等。

看这个树的生成流程，应该就能看出决策树为什么受欢迎了。跟其他分类算法比，决策树实现过程非常简单，没有什么特别的假设或者复杂的运算。

在Matlab用UCI中的红酒数据集Wine（http://archive.ics.uci.edu/ml/datasets/wine）来试试CART决策树。Wine数据集是意大利同一地区三类不同的红酒，共有178个观测，13个关于红酒的特征（Alcohol,Malic acid,Ash,Alcalinity of ash,Magnesium,Total phenols,Flavanoids,Nonflavanoidphenols,Proanthocyanins,Colorintensity,Hue,OD280/OD315 of diluted wines,Proline，我也不知道怎么翻译，懂红酒的朋友应该知道），以及13个特征相对应的红酒分类（1类、2类和3类）。现在要做的就是，从这个历史数据集，找出将红酒分类的规则。这样，当新产出一只红酒，根据这只红酒的13个特征取值，就可以根据规则判断出这只红酒属于1类酒、2类酒还是3类酒。

初步得到的CART决策树如下（做了一个简单的限制，每个父节点包含样本数不小于10），可以看到，得到的决策树还是比较简单的，分类规则也是非常清晰的。同时，可以看到13个特征并没有全部用到，而是很自然地选择出了相对重要的特征进行分类。

CART决策树模型有个比较突出的问题，就是很容易过拟合（Over fitting）。所谓过拟合就是模型太听话了，照单全收训练集的信息，包括噪音，对训练集拟合地很好，甚至好过头了。这会导致训练出来的模型用来对新数据进行分类预测时，效果却不是很好，即泛化能力比较弱。这也契合过犹不及的思想，太好了就会被发好人卡。具体到CART决策树，就需要对生成的决策树进行剪枝，一是使模型变得更为简单，二是提高模型的泛化能力。

CART决策树剪枝用的CCP方法（Cost-Complexity Pruning）。CCP大致的思想是计算剪去某段子树时，在错误率和复杂度之间做一个平衡，从中找到综合影响最小的一段子树剪去，照此规则依次剪下去，直至只剩根节点，这就形成了一列供选择剪枝的树。接着，可以用交叉验证（cross-validation）方法，在这一列树中找到最优的树，这里用k-fold交叉验证。最优树的选择一般有两个标准，一是使交叉误差最小，二是1-SE（1-standard error）原则，即选择在最小交叉误差的1个标准误范围内的树。根据我个人的使用经验，我的建议是最好放宽一点，使用1-SE原则。据此，可以计算出最佳子树bestlevel为2，最优CART决策树具体如下：

至此，可用得到最优决策树分类器对红酒进行分类。

La Fin.