决策树分类实验
一 实验目的
- 了解决策树算法的原理，学会特征选择，分枝过程
- 了解决策树算法的实现过程，能比较多种不同决策树
- 学会使用Python语言建立决策树分类模型
二 实验原理
决策树学习是一种逼近离散值目标函数的方法。通过将一组数据中学习的函数表示为决策树，从而将大量数据有目的的分类，从而找到潜在有价值的信息。决策树分类通常分为两步---生成树和剪枝；
树的生成：自上而下的递归分治法
剪枝：减去那些可能增大错误预测率的分支
决策树的方法起源于概念学习系统CLS（Concept Learning System）, 然后发展最具有代表性的ID3（以信息熵作为目标评价函数）算法，最后又演化为C4.5, C5.0,可以处理连续属性。
决策树的结构
以下面一个简单的用于是否买电脑预测的决策树为例子，树中的内部节点表示某个属性，节点引出的分支表示此属性的所有可能的值，叶子节点表示最终的判断结果也就是类型。
借助可视化工具例如Graphviz，matplotlib的注解等等都可以讲我们创建的决策树模型可视化并直接被人理解，这是贝叶斯神经网络等算法没有的特性。
决策树算法
决策树算法主要是指决策树进行创建中进行树分裂(划分数据集)的时候选取最优特征的算法，他的主要目的就是要选取一个特征能够将分开的数据集尽量的规整，也就是尽可能的纯. 最大的原则就是: 将无序的数据变得更加有序！这里总结以下三个常用的方法：
- 信息增益（imformation gain）
- 增益比率（gain ratio）
- 基尼不纯度（Gini impurity）
信息增益
信息论中告诉我们某个事件的信息量为这个事件发生的概率的负对数。
信息熵就是平均而言一个事件发生得到的信息量大小，也就是信息量的期望值.
我们将一组数据集进行划分后，数据的信息熵会发生改变，我们可以通过使用信息熵的计算公式分别计算被划分的子数据集的信息熵并计算他们的平均值(期望值)来作为分割后的数据集的信息熵。新的信息熵的相比未划分数据的信息熵的减小值便是信息增益了.假设我们将数据集D划分成k份D1,D2,…,Dk，则划分后的信息熵为:
信息增益便是两个信息熵的差值
增益比率
增益比率是信息增益方法的一种扩展，是为了克服信息增益带来的弱泛化的缺陷。因为按照信息增益选择，总是会倾向于选择分支多的属性，这样会是的每个子集的信息熵最小。例如给每个数据添加一个第一无二的id值特征，则按照这个id值进行分类是获得信息增益最大的，这样每个子集中的信息熵都为0，但是这样的分类便没有任何意义，没有任何泛化能力，类似过拟合。
因此我们可以通过引入一个分裂信息来找到一个更合适的衡量数据划分的标准，即增益比率。
分裂信息的公式表示为:
可见如果数据分的越多，分裂信息的值就会越大。这时候把分裂信息的值放到分母上便会中和信息增益带来的弊端。
基尼不纯度
基尼不纯度的定义: 
其中m表示数据集D中类别的个数, pi表示某种类型出现的概率。可见当只有一种类型的时候基尼不纯度的值为0，此时不纯度最低。
针对划分成k个子数据集的数据集的基尼不纯度可以通过如下式子计算:
由此我们可以根据不纯度的变化来选取最有的树分裂属性
树分裂
有了选取最佳分裂属性的算法，下面我们就需要根据选择的属性来将树进一步的分裂。所谓树分裂只不过是根据选择的属性将数据集划分，然后在总划分出来的数据集中再次调用选取属性的方法选取子数据集的中属性。实现的最好方式就是递归了.
树分裂的终止条件有两个：
一个是遍历完所有的属性 可以看到，在进行树分裂的时候，我们的数据集中的数据向量的长度是不断缩短的，当缩短到0时，说明数据集已经将所有的属性用尽，便也分裂不下去了, 这时我们选取最终子数据集中的众数作为最终的分类结果放到叶子节点上.
另一个是新划分的数据集中只有一个类型。 若某个节点所指向的数据集都是同一种类型，那自然没有必要在分裂下去了即使属性还没有遍历完.
三 实验步骤
DecisionTreeClassifier是能够对数据集执行多类分类的类。与其他分类器一样，DecisionTreeClassifier需要输入两部分，一部分为特征集合，还有标签集合。先给出简单的训练过程如下：
>>> from sklearn import tree
>>> X = [[0, 0], [1, 1]]
>>> Y = [0, 1]
>>> clf = tree.DecisionTreeClassifier()
>>> clf = clf.fit(X, Y)
在训练了模型之后，我们可以用来做预测：
>>> clf.predict([[2., 2.]])
array([1])
或者，可以预测每个类的概率，这是决策树的叶子节点中相同类的训练样本的分数：
>>> clf.predict_proba([[2., 2.]])
array([[ 0., 1.]])
DecisionTreeClassifier能够二分类（标签为[-1,1]）和多分类（其中标签为[0，...，K-1]）。
使用Iris数据集，我们可以构造一个树，如下所示：
>>> from sklearn.datasets import load_iris
>>> from sklearn import tree
>>> iris = load_iris()
>>> clf = tree.DecisionTreeClassifier()
>>> clf = clf.fit(iris.data, iris.target)
经过培训，我们可以使用export_graphviz以Graphviz格式导出树。 如果您使用conda包管理器，则可以安装graphviz二进制文件和python包，conda能帮助我们使用一个简单的命令安装python-graphviz
conda install python-graphviz
或者，可以从graphviz项目主页下载graphviz的二进制文件，并从pypi withpip安装graphviz安装Python包装器。
以下是在整个iris数据集上训练的上述树的graphviz导出示例; 结果保存在输出iris.pdf中：
>>> import graphviz
>>> dot_data = tree.export_graphviz(clf, out_file=None)
>>> graph = graphviz.Source(dot_data)
>>> graph.render("iris")
>>> dot_data = tree.export_graphviz(clf, out_file=None,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True, rounded=True,
special_characters=True)
>>> graph = graphviz.Source(dot_data)
>>> graph
我们可以得到以下的图片输出：
模型训练好之后，我们可以在测试集上预测分类结果：
>>> clf.predict(iris.data[:1, :])
array([0])
我们也可以直接预测概率：
>>> clf.predict_proba(iris.data[:1, :])
array([[ 1., 0., 0.]])