决策树告诉你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