姓名：梁祥 学号：17021210935
【嵌牛导读】：决策树算法作为数据挖掘领域的十大算法之一，与k-means算法、EM算法等在实际应用中发挥着重要的作用。决策树算法利用已知或人为定义的标签（Flag），在具有一定样本规模的情况下，可以绘制出信息熵下降最快的树模型。利用训练得到的树，就可以利用先验知识判断目标对象属于哪个预定义的目标类。
【嵌牛鼻子】：决策树，ID3，信息熵，信息增益
【嵌牛提问】：如何量化定义随机事件所包含的信息量？在构建决策树时，如何使决策树的信息熵下降最快？
【嵌牛正文】：
关于决策树算法，不像之前的其他聚类算法那么枯燥，我们这次可以先讲小故事了~~~
一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
（此例纯属虚构，如有雷同，那这个例子一定也是从网上抄的）
决策树是一种典型的分类方法，功能强大且容易提取规则，利用归纳算法生成决策树，树中的每条路径代表一个规则，所以比较适合用于数据挖掘中的分类。这里呢，我们主要介绍ID3算法。该算法采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。
决策树算法最大的优点是，它可以自学习。在学习的过程中，不需要使用者了解过多的背景知识，只需要对训练实例进行较好的标注，就能够进行学习。显然，决策树学习算法属于有监督学习，它从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。
因此，建立决策树的关键在于当前状态下选择哪个属性作为分类依据。ID3算法的理论基础是信息论中的信息熵和信息增益度，在算法中以其为度量标准在树的内部各个节点处寻找一个属性，使该属性能最好地将训练集进行分类。
那么，如何度量自信息量的大小呢？
通过自信息量，也成为非平均自信息量，是用来消除不确定度的一种表达：
信息熵是从平均意义上表征信源的总体特征，可以表示信源的平均不确定度，对于特定信源（概率空间给定），其信源熵是一个确定的数值，不同的信源因统计特性不同，其熵也不同。
假定有n个互不相容的事件a1,a2,a3,......,an，令p（ai）表示时间ai发生的概率，则由该分布传递的信息量称为熵，记为式（1）
熵的实际意义表示是D中元组的类标号所需要的平均信息量。在每次分类迭代中，首先计算当前信息的全体信息熵，计算方法如上式所述。
在决策树分类中，假设S是训练样本集合，假定当前数据的类别标号属性具有n个不同的值a1，a2，a3，......，an。同时在样本集合中存在m个不同类C1，C2，......，Cm（身高、体重、学历等），同样在每个类Ci划分出的子集中，也可能存在不同的类别标号属性，其类别数目可以表示为：Si1，Si2，......，Sin。子集的熵同样可以利用经验熵公式计算得出。通过比较每个明确某个子集划分之后，信息熵的增加量，即信息增益，就可以将其确定为当前生长的决策树节点。
信息增益 = 全体信息熵 - 当前属性下的信息熵
根据贪婪算法，为了使下一步所需的信息量最小，要求每一次都选择其信息增益最大的属性作为决策树的新节点。
ID3决策树建立算法的步骤：
1）决定分类属性；
2） 对目前的数据表，建立一个节点N
3） 如果数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的类
4） 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别
5） 否则，根据平均信息期望值E或GAIN值选出一个最佳属性作为节点N的测试属性
6 ）节点属性选定后，对于该属性中的每个值：从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏
7）如果分支数据表非空，则运用以上算法从该节点建立子树。
决策树算法比较适合处理离散数值的属性，实际应用中属性是连续的或者离散的情况都比较常见。在应用连续属性值时，在一个树节点可以将该属性的值划分为几个合理的区间。然后信息增益的计算就可以采用和离散值处理一样的方法。原则上可以将该属性划分为任意数目的空间。
小结：ID3算法是一种经典的决策树学习算法，其基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变为最小的属性，以此构造一棵熵值下降最快的决策树。判断某个节点是否为叶子节点的原则是，在该节点上的所有数据属性一致，或者所有属性已经判断完毕。对于属性一致的情况，可以直接终止生成；而对于属性判断完毕的情况，如果当前节点的类别属性不一致，可以利用多数投票法对目标属性进行判断。
