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

原文发布于微信公众号 - 悦思悦读(yuesiyuedu)

原文发表时间:2016-02-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏梦里茶室

TensorFlow 深度学习笔记 TensorFlow实现与优化深度神经网络

全连接神经网络 辅助阅读:TensorFlow中文社区教程 - 英文官方教程 代码见:full_connect.py Linear Model 加载lesso...

214100
来自专栏Gaussic

使用TensorFlow训练循环神经网络语言模型

读了将近一个下午的TensorFlow Recurrent Neural Network教程,翻看其在PTB上的实现,感觉晦涩难懂,因此参考了部分代码,自己写了...

27330
来自专栏素质云笔记

k-means+python︱scikit-learn中的KMeans聚类实现( + MiniBatchKMeans)

之前一直用R,现在开始学python之后就来尝试用Python来实现Kmeans。 之前用R来实现kmeans的博客:笔记︱多种常见聚类模型以及分群质...

3.2K90
来自专栏Python数据科学

一款非常棒的特征选择工具:feature-selector

本篇主要介绍一个基础的特征选择工具feature-selector,feature-selector是由Feature Labs的一名数据科学家williamk...

30140
来自专栏DHUtoBUAA

编程求取直线一般式表达式,两直线交点

背景介绍   最近在水面无人艇(USV)模拟仿真中,用到了一些点和线的关系求解,本文主要讲述一下两点确认直线,点到直线距离,两条直线的交点等问题的解决方法,并给...

51970
来自专栏企鹅号快讯

使用RNN预测股票价格系列一

正文共11490个字,16张图,预计阅读时间:29分钟。 01 概述 我们将解释如何建立一个有LSTM单元的RNN模型来预测S&P500指数的价格。 数据集可以...

27590
来自专栏机器之心

Capsule官方代码开源之后,机器之心做了份核心代码解读

430120
来自专栏AI研习社

如何使用注意力模型生成图像描述?

我们的目标是用一句话来描述图片, 比如「一个冲浪者正在冲浪」。 本教程中用到了基于注意力的模型,它使我们很直观地看到当文字生成时模型会关注哪些部分。

22120
来自专栏AI研习社

一文教你如何用神经网络识别验证码!

AI 研习社按:本文作者 Slyne_D,原载于作者个人博客,雷锋网 AI 研习社已获授权。文中相关链接详见文末“阅读原文”。 这是去年博主心血来潮实现的一个小...

30730
来自专栏云霄雨霁

算法设计策略----回溯法和分枝限界法

25000

扫码关注云+社区

领取腾讯云代金券