决策树告诉你Hello Kitty到底是人是猫

Hello Kitty，一只以无嘴造型40年来风靡全球的萌萌猫，在其40岁生日时，居然被其形象拥有者宣称：HelloKitty不是猫！

2014年八月，研究 Hello Kitty 多年的人类学家 Christine R. Yano 在写展品解说时，却被Hello Kitty 持有商三丽鸥纠正：Hello Kitty是一个卡通人物，她是一个小女孩，是一位朋友，但她『绝不』是一只猫。

粉了快半个世纪的世界萌猫，你说是人就是人啦？！就算是形象持有者，也没权利下这个定论啊!

谁有权认定Hello Kitty是人是猫呢？我们把裁决权交给世界上最公正无私的裁判—— 计算机。让机器来决定。

机器如何具备区分一个形象属于哪个物种的知识呢？让它学习呀！机器是可以学习的。我们用计算机编个程序，再输入一堆数据，等着这个程序运行一个算法来处理这些数据。最后，我们需要的结论就显示在屏幕上啦。就是这么简单！

那么来看看我们需要的数据和算法吧。

训练数据

如下图所示，左边一堆是一群小女孩，右边一堆是一群猫。

特征选取

我们提取七个特征，用来判断一个形象，是人是猫。这七个特征包括：有否蝴蝶结；是否穿衣服；是否高过5个苹果；是否有胡子；是否圆脸；是否有猫耳朵；是否两脚走路。

用一个表格来表现这七个特征则如下（第一列为Label，第二至八列为7个特征，每个特征只有两个取值，Yes或者No）：

Table-1

算法选取

算法，我们选用决策树。决策树（decision tree）是一个树结构（可以是二叉树或非二叉树），每个非叶节点表示一个特征属性，每个分支代表这个特征属性在某个取值，而每个叶节点存放一个类别。

使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。决策树的决策过程非常直观，容易被人理解。

选定算法后，首先我们要构造决策树。

构造决策树

决策树的构造过程是一个迭代的过程。每次迭代中，采用不同属性作为分裂点，来将元组划分成不同的类别。被用作分裂点的属性叫做分裂属性。

选择分裂属性的目标是让各个分裂子集尽可能地“纯”，即尽量让一个分裂子集中待分类项属于同一类别。

ID3算法

如何使得各个分裂子集“纯”，算法也有多种，此处，我们选择最直接也最简单的ID3算法。该算法的核心是：以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。

下面先定义几个要用到的概念:

i) D为用类别对训练元组进行的划分;

ii) D的熵（entropy）表示为：

其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。

熵的实际意义表示是D中元组的类标号所需要的平均信息量。

iii) 对训练元组按属性A进行D划分，则A对D划分的期望信息为：

iv）则按照属性A进行D划分的信息增益为期望信息量与熵（即平均信息量）的差值：

代入数据计算

1）根据上述概念，我们先来计算info（D）。因为总共只有两个类别：人和猫，因此m==2。

Info（D）= -p[Girl] log（p[Girl]） - p[Cat] log（p[Cat]）= - 9/17 * log（9/17） - 8/17 * log（8/17）= 0.69

2）然后我们再分别计算各个feature的Info[feature]（D）。

因为无论哪个feature，都只有两个属性值:Yes或者No，因此InfoA（D）公式中的v==2。

下面以Info[Has a bow](D)为例来示意其计算过程。

Info[Has a bow](D) = p[Yes] * (-p[Girl|Yes]* log(p[Girl|Yes]) – p[Cat|Yes] * log(p[Cat|Yes))+ p[No] * (-p[Girl|No] * log(p[Girl|No])– p[Cat|No] * log(p[Cat|No]))= 8/17 * (-4/8 * log(4/8) – 4/8 * log(4/8)) + 9/17* (- 5/9 * log(5/9) – 5/9 * log(5/9)) = 0.69

依次计算其他几项，得出如下结果：

Info[Wear Clothes](D) = 0.31

Info[Less than 5 apples tall](D) =0.60

Info[Has whiskers](D) = 0.36

Info[Has round face](D) = 0.61

Info[Has cat ears](D) = 0.18

Info[Walks on 2 feet](D) = 0.36

3）进一步计算，得出Gain(Has cat ears) 最大，因此”Has cat ears”是第一个分裂节点。

而从这一属性对应的类别也可以看出，所有属性值为No的都一定是Girl；属性值为Yes，可能是Girl也可能是Cat，那么第一次分裂，我们得出如下结果：

现在“Has cat ears”已经成为了分裂点，则下一步将其排除，用剩下的6个feature继续分裂成树：

Table-2

Table-2为第二次分裂所使用训练数据，相对于Table-1，“Has cat ears”列，和前7行对应“Has cat ears”为No的数据都已经被移除，剩下部分用于第二次分裂。

如此反复迭代，最后使得7个feature都成为分裂点。

需要注意的是，如果某个属性被选为当前轮的分裂点，但是它在现存数据中只有一个值，另一个值对应的记录为空，则这个时候针对不存在的属性值，将它标记为该属性在所有训练数据中所占比例最大的类型。

对本例而言，当我们将“Wear Clothes”作为分裂点时，会发现该属性只剩下了一个选项——Yes（如下Table-3所示）。此时怎么给“Wear Clothes”为No的分支做标记呢？

Table-3

这时就要看在Table-1中，“Wear Clothes”为No的记录中是Girl多还是Cat多。一目了然，在Table-1中这两种记录数量为0：6，因此“Wear Clothes”为No的分支直接标志成Cat。

根据上述方法，最终我们构建出了如下决策树：

决策树构建算法总结

DecisionTree induceTree(training_set, features) {

If(training_set中所有的输入项都被标记为同一个label){ return 一个标志位该label的叶子节点；

} else if(features为空) {

return 一个标记为默认label的叶子节点； // 默认标记为在所有training_set中所占比例最大的label

} else {

选取一个feature，F；

以F为根节点创建一棵树currentTree；

从Features中删除F；

foreach(value V of F) {

将training_set中feature F的取值为V的元素全部提取出来，组成partition_v；

branch_v= induceTree(partition_V, features);

将branch_v添加为根节点的子树，根节点到branch_v的路径为F的V值；

}

returncurrentTree；

}

}

决策树剪枝

如图中显示，最后两个分裂点“Has round face”和“Has a bow”存在并无意义——想想也是啊，无论人猫，都有可能是圆脸，也都可以戴蝴蝶结啊。所以我们对上面决策树进行剪枝。

剪枝是优化决策树的常用手段。剪枝方法大致可以分为两类：

I. 先剪枝（局部剪枝）——在构造过程中，当某个节点满足剪枝条件，则直接停止此分支的构造。

II. 后剪枝（全局剪枝）——先构造完成完整的决策树，再通过某些条件遍历树进行剪枝。

上面我们的决策树已经构造完成了，此时剪枝头就是后剪枝。修剪完成后，我们的决策树变成了下面这样：

用决策树对Hello Kitty进行分类

我们将Hello Kitty的属性带入Cat-Girl决策树，发现Hello Kitty：Has cat ears: Yes -> Work on 2 feed: Yes -> WearClothes: Yes -> Has whirskers: Yes -> Less than 5 apples: Yes -> Cat。

Bingo! Hello Kitty 是只猫！这是我们的ID3决策树告诉我们的！

ID3决策树实现源代码

ID3决策树Java实现代码和本文所使用数据文件位于：https://github.com/juliali/DecisionTreeSamples.git