机器学习第三篇——分类决策树
决策树是一类常见的机器学习方法，利用决策树来进行决策的过程很像人类在面临决策问题时的一种思考模式。举个生活中的例子，假如我们要判断一个没剖开的西瓜是不是好瓜，有经验的瓜农可能会首先看看西瓜的颜色，再看看西瓜的根蒂形状，如果还没得出结论，可能还会敲打西瓜，听听是什么声音。上述过程用决策树表示如下。
那么我们的问题来了，给你一份带分类标签的数据，你怎么训练出一棵决策树。再次回顾我们是怎样利用决策树进行判定的，在决策过程中每提出的一个问题其实都是对某个属性的测试，然后沿着测试结果的分支继续测试，直到走到最终的分类结果。在每一步的测试中，我们都想通过这个测试就能得到最终的分类结果，一个极端的例子，如果能通过判断西瓜色泽是青绿色就得出是好瓜的结论最好。
所以我们的目标是尽可能进行少的属性测试就能得到分类结果，换句话说就是每次测试都选择最优的属性测试，最优的含义就是通过这个测试能把数据集中的样本结果尽多的确定。
这样问题就清晰了，在构建决策树的过程中就是每次都选择一个最优的属性。那么我们通过什么办法来确定一个属性是最优属性呢，下面就引入信息增益的概念。
首先什么是信息，信息能否度量？香农在他的著作《通信的数学原理》提出一个名词“信息熵”。信息熵是用来消除事件不确定性所需的信息量的度量，我们可以这么理解，一个事件越不确定，我们就需要越多的信息来确定它，它的信息熵就越大。比如我说明天会是世界末日，这个事件是真的还是假的，很难确定，所以它的信息熵很大。
回到我们的数据集上，如果我们的数据集的类别种类很多，我们要确定一个样本到底属于哪个类别，需要的信息量就越大，就表明这份数据集的信息熵就越大。数据集的信息熵计算公式如下：
其中D是数据集，y|是类别个数，Pk是第k类样本所占的比率。
前面我们说了，我们每次都是选择最优的属性进行测试，也就是利用数据样本在属性上的取值不同将数据集分为D1，D2，...，Dv，v为属性上不同值的个数，我们希望划分后的数据集的信息熵是较小的，也就是希望原数据集和划分后的数据集的信息熵的差值较大。这就是信息增益的含义，信息增益计算公式如下：
基于信息增益构建决策树的算法被称为ID3算法。但我们仔细想想，会发现信息增益有一个偏好，就是每次都倾向于选择可取值数目较多的属性，因为通常利用可取值数目较多的属性划分数据集后得到的信息增益较大。
但有时选择这个属性会带来不好的影响。举个简单的例子，在一个数据集中，假设每个数据样本都有唯一的ID，如果利用这个ID进行判断，当然能一步得出结论，但这并不是我们想要的，因为ID没有任何的实际含义，它只是一个数据样本的唯一标识。
为了解决这个问题，C4.5算法就在ID3算法的基础上进行了改进，C4.5算法对一个属性的信息增益利用属性的可取值数目进行了惩罚。C4.5算法利用增益率来选择最优属性，增益率的计算公式如下：
一般来说，属性a的可取值数目越多，IV(a)的值就越大。增益率就可以理解为在信息增益的基础对属性的可取值数目进行了惩罚。值得注意的一点是：C4.5算法并不是直接选择增益率最大的那个属性，而是先在候选属性中找出那些信息增益大于平均值的属性，再从这些属性中选择增益率最大的属性。
最后还有一个指标可以用来选择最优属性，那就是基尼指数，CART（Classification And Regression Tree）决策树就是使用基尼指数来选择最优属性的。
可以想象，当我们从数据集中随机取两个样本，当这两个样本属于同一分类的概率越大，这个数据集的纯度越高，反之如果两个样本属于不同分类的概率越大，则数据集的纯度越低。基尼值就是表明随机取两个样本属于不同分类的概率，基尼值越大，数据集纯度越低。这和信息熵的作用类似。基尼值的计算公式如下：
其中K为数据集分类的个数，Pk为第一个分类所占的比率。
我们希望选择一个属性，经过这个属性的划分后，数据集的纯度高，也就是数据集的基尼值小。用属性a划分数据集后的基尼值计算公式如下：
到此为止我们知道了利用信息增益选择属性的ID3算法，利用增益率选择属性的C4.5算法，利用基尼指数选择属性的CART算法。下面我们来看下sklearn上的DecisionTreeClassifier是怎样实现决策树的。
一个简单的例子如下：
from sklearn.datasets import load_irisfrom sklearn import tree
iris = load_iris()
clf = tree.DecisionTreeClassifier()
clf = clf.fit(iris.data, iris.target)
DecisionTreeClassifier的相关参数说明：
Parameters:
criterion : string, optional (default=”gini”)
指定用哪种指标来选择最优划分属性。”gini”：基尼指数，“entropy”：信息增益。
splitter : string, optional (default=”best”)
当一个属性的值为连续时，指定如何划分数据集。"best"是求出最好的划分点进行划分，"random"是随机选择一个划分点进行划分。
选择建议：当样本很大时，选择"random"，因为样本很大时选择一个最佳划分点计算开销较大。
max_depth : int or None, optional (default=None)
设置树的最大深度。当为None时，就是不限制树的深度。在数据样本大的情况下建议设置树的深度为10-100，因为这可以有效的缓解过拟合问题。
min_samples_split : int, float, optional (default=2)
设置子树可以继续划分所需的最小样本数。当数据集较大时，可以适当加大这个值。
min_samples_leaf : int, float, optional (default=1)
设置叶子结点所需的最小样本数。如果当前的叶子结点样本数小于该值，则该叶子结点会和兄弟结点一起被剪枝。
max_features : int, float, string or None, optional (default=None)
设置选择最优属性时所参考的候选属性个数。当为None时，就是在所有属性中选择最优的，当为"auto"或"sqrt"时，候选属性个数为。
max_leaf_nodes : int or None, optional (default=None)
设置决策树叶子结点的最大个数。合适的值也可以缓解过拟合问题。
presort : bool, optional (default=False)
数据是否预排序。当数据集较少的时候，预排序可以使选择最佳划分点加快，但数据量大时反而不好。
Methods：
fit(X, y[, sample_weight, check_input, …])
利用数据样本X，训练决策树。
predict(X[, check_input])
预测样本X的分类。
predict_proba(X[, check_input])
返回每个数据样本属于每个分类的概率。
score(X, y[, sample_weight])
返回数据样本X的预测正确率。
