决策树分类算法

概念讲解

分类与聚类

在具体讲解分类和聚类算法之前，我们先了解一下什么是分类，什么是聚类，以及它们常用的算法有哪些。

1. Classification(分类)，对于一个classifier，通常需要你告诉它这个东西被分为某某类这样一些例子，理想情况下，一个classifier会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类的能力，这种提供数据训练的过程一般叫做“Supervised Learning（监督学习）”。

2. Clustering（聚类），简单的说就是把相似的东西分到一组，聚类的时候，我们不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起。因此一个聚类算法通常只需要知道如何计算相似度就可以开始工作了，因此clustering通常不需要使用训练数据进行学习，这种叫做“Unsupervised Learning（无监督学习）”

• 分类：简单地说，就是根据文本的特征或属性，划分到已有的类别中。也就是说，这些类别是已知的，通过对已知分类的数据进行训练和学习，找到这些不同类的特征，再对未分类的数据进行分类。常用算法：决策树、朴素贝叶斯，支持向量机，神经网络，k-最近邻，模糊分类

• 聚类：简单地说，就是你压根不知道数据会分为几类，通过聚类分析将数据或者说用户聚合成几个群体，那就是聚类了。聚类不需要对数据进行训练和学习，一个聚类算法只要知道如何计算相似度就可以工作了。

### 什么是决策树
所谓决策树，就是一种树，一种依托于策略抉择而建立的树。

机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。

从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。

来理论的太过抽象，下面举一个浅显易懂的例子：

套用俗语，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

  女儿：多大年纪了？
  母亲：26。
  女儿：长的帅不帅？
  母亲：挺帅的。
  女儿：收入高不？
  母亲：不算很高，中等情况。
  女儿：是公务员不？
  母亲：是，在税务局上班呢。
  女儿：那好，我去见见。

这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑：

决策树是一种十分常用的分类方法，需要监管学习，监管学习就是给出一堆样本，每个样本都有一组属性和一个分类结果，也就是分类结果已知，那么通过学习这些样本得到一个决策树，这个决策树能够对新的数据给出正确的分类。

相关算法

决策树学习之ID3算法

从信息论知识中我们知道期望信息越小，信息增益越大，从而纯度越高。ID3的算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益（后面会讲解什么是信息增益）最大的属性进行分裂

所以ID3的算法思想便是：

1. 自顶向下的贪婪搜索遍历可能的决策树空间构造决策树(此方法是ID3算法和C4.5算法的基础)；
2. 从“哪一个属性将在树的根节点被测试”开始；
3. 使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试（如何定义或者评判一个属性是分类能力最好的呢？这便是下文将要介绍的信息增益 or 信息增益率，这里要说的是信息增益和信息增益率是不同的,ID3基于信息增益来选择最好的属性，而接下来介绍的C4.5则是基于增益率来进行选择，这也是它进步的地方）。
4. 然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是说，样例的该属性值对应的分支）之下。
5. 重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。

这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑以前的选择。

实例讲解分析

回归决策树的基本知识，构建一个决策树主要有以下三个重要问题：

1. 数据是怎么分裂的
2. 如何选择分类的属性
3. 什么时候停止分裂

从上述三个问题和ID3算法思想出发， 以一个实际例子对ID3算法进行讲解。

问题描述：我们统计了14天的气象数据(指标包括outlook，temperature，humidity，windy)，并已知这些天气是否打球(play)。如果给出新一天的气象指标据:sunny,cool,high,TRUE，判断一下会不会去打球。

table 1

outlook	temperature	humidity	windy	play
sunny	hot	high	FALSE	no
sunny	hot	high	TRUE	no
overcast	hot	high	FALSE	yes
rainy	mild	high	FALSE	yes
rainy	cool	normal	FALSE	yes
rainy	cool	normal	TRUE	no
overcast	cool	normal	TRUE	yes
sunny	mild	high	FALSE	no
sunny	cool	normal	FALSE	yes
rainy	mild	normal	FALSE	yes
sunny	mild	normal	TRUE	yes
overcast	mild	high	TRUE	yes
overcast	hot	normal	FALSE	yes
rainy	mild	high	TRUE	no

现在我们用ID3算法来讲解：

预备知识讲解：

1. 信息熵

2. 信息增益

---

##### 决策树决策
决策树的形式类似于“如果天气怎么样，去玩；否则，怎么着怎么着”的树形分叉。那么问题是用哪个属性（即变量，如天气、温度、湿度和风力）最适合充当这颗树的根节点，在它上面没有其他节点，其他的属性都是它的后续节点。 那么借用上面所述的能够衡量一个属性区分以上数据样本的能力的“信息增益”（Information Gain）理论。 如果一个属性的信息增益量越大，这个属性作为一棵树的根节点就能使这棵树更简洁，比如说一棵树可以这么读成，如果风力弱，就去玩；风力强，再按天气、温度等分情况讨论，此时用风力作为这棵树的根节点就很有价值。如果说，风力弱，再又天气晴朗，就去玩；如果风力强，再又怎么怎么分情况讨论，这棵树相比就不够简洁了。 用熵来计算信息增益，如上图例子：

1. 计算分类系统的熵
类别是 “是否出去玩”。取值为yes的记录有9个，取值为no的有5个，即说这个样本里有9个正例，5个负例，记为S(9+,5-)，S是样本的意思(Sample)。那么P(c1) = 9/14, P(c2) = 5/14
这里熵记为Entropy(S),计算公式为：

Entropy(S)=−914∗log2914−514∗log2514$$Entropy(S)=-\frac{9}{14}\ast lo{g}_2\frac{9}{14}-\frac{5}{14}\ast lo{g}_2\frac{5}{14}$$

2. 分别以Wind、Humidity、Outlook和Temperature作为根节点，计算其信息增益
我们来计算Wind的信息增益:
当Wind固定为Weak时：记录有8条，其中正例6个，负例2个；同样，取值为Strong的记录6个，正例负例个3个。我们可以计算相应的熵为：

Entropy(Weak)=−68∗log268−28∗log228$$Entropy(Weak)=-\frac{6}{8}\ast lo{g}_2\frac{6}{8}-\frac{2}{8}\ast lo{g}_2\frac{2}{8}$$

Entropy(Strong)=−36∗log236−36∗log236$$Entropy(Strong)=-\frac{3}{6}\ast lo{g}_2\frac{3}{6}-\frac{3}{6}\ast lo{g}_2\frac{3}{6}$$

现在就可以计算出相应的信息增益了：

Gain(Wind)=Entropy(S)−814∗Entropy(Weak)−614∗Entropy(Strong)$$Gain(Wind)=Entropy(S)-\frac{8}{14}\ast Entropy(Weak)-\frac{6}{14}\ast Entropy(Strong)$$

=0.940−814∗0.811−614∗1.0=0.048$$=0.940-\frac{8}{14}\ast 0.811-\frac{6}{14}\ast 1.0=0.048$$

这个公式的奥秘在于，8/14是属性Wind取值为Weak的个数占总记录的比例，同样6/14是其取值为Strong的记录个数与总记录数之比。

同理，如果以Humidity作为根节点：
Entropy(High)=0.985$Entropy(High)=0.985$;\quad Entropy(Normal)=0.592$Entropy(Normal)=0.592$

Gain(Humidity)=0.940−714∗Entropy(High)−714∗Entropy(Normal)=0.151$$Gain(Humidity)=0.940-\frac{7}{14}\ast Entropy(High)-\frac{7}{14}\ast Entropy(Normal)=0.151$$

以Outlook作为根节点：
Entropy(Sunny)=0.971;Entropy(Overcast)=0.0;Entropy(Rain)=0.971$Entropy(Sunny)=0.971;Entropy(Overcast)=0.0;Entropy(Rain)=0.971$

Gain(Outlook)=0.940−514∗Entropy(Sunny)−414∗Entropy(Overcast)−514∗Entropy(Rain)=0.247$$Gain(Outlook)=0.940-\frac{5}{14}\ast Entropy(Sunny)-\frac{4}{14}\ast Entropy(Overcast)-\frac{5}{14}\ast Entropy(Rain)=0.247$$

以Temperature作为根节点：
Entropy(Cool)=0.811;Entropy(Hot)=1.0;Entropy(Mild)=0.918$Entropy(Cool)=0.811;Entropy(Hot)=1.0;Entropy(Mild)=0.918$

Gain(Temperature)=0.940−414∗Entropy(Cool)−414∗Entropy(Hot)−614∗Entropy(Mild)=0.029$$Gain(Temperature)=0.940-\frac{4}{14}\ast Entropy(Cool)-\frac{4}{14}\ast Entropy(Hot)-\frac{6}{14}\ast Entropy(Mild)=0.029$$

这样我们就得到了以上四个属性相应的信息增益值： Gain(Wind)=0.048；Gain(Humidity)=0.151；$Gain(Wind)=0.048；Gain(Humidity)=0.151；$
Gain(Outlook)=0.247；Gain(Temperature)=0.029$Gain(Outlook)=0.247；Gain(Temperature)=0.029$
最后按照信息增益最大的原则选Outlook为根节点。子节点重复上面的步骤。这颗树可以是这样的，它读起来就跟你认为的那样：


ID3优点是理论清晰、方法简单、学习能力较强，但也存在一些缺点：
（1）只能处理分类属性的数据，不能处理连续的数据；
（2）划分过程会由于子集规模过小而造成统计特征不充分而停止；
（3）ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是 倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。

C4.5算法讲解

这一个算法，就不讲解了，有一篇博客讲的特别好，推荐看一下。

C4.5算法讲解博客地址：

总结

因为最近要进行数据挖掘的课程考试，所以在复习（其实是预习…）时，进行总结。我是观看了几篇博客讲解后进行总结的，主要是为了记录我学到的，后面可以进行回头查阅，如能帮助到其他人，那再好不过了。

参考文献

1. 分类算法之决策树ID3详解
2. 决策树分类算法