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