⽂本分类算法之决策树.ID3实现
⽂本分类，字⾯意思来说就是对⽂本进⾏分类。其实就是这样，⽂本分类是根据⽂本所具有的⼀些特征和属性来将其判别为事先确定的⼏个类别的过程。常⽤的分类⽅法有朴素贝叶斯⽅法，K近邻⽅法（KNN），⽀持向量机（SVM），决策树⽅法，神经⽹络⽅法等等。本⽂主要来介绍决策树的⼀种实现。
决策树是通过⽂本的⼀些属性来建⽴的⼀个模型。决策树采⽤⾃顶向下的⽅式，树中的每个结点都代表⼀个属性，该结点的每棵⼦树都代表这个属性的⼀个确定取值，叶结点上放着决策值。⽤决策树对⽬标属性进⾏判断时，将从树根出发，沿着已知的属性进⼊⼦树，知道找到叶结点，也就得到的预测结果。所以从跟结点到每⼀个叶结点的路径都是⼀条决策规则。
引⽤他⼈博⽂（①）中的⼀个例⼦：
通俗来说，决策树分类的思想类似于找对象。现想象⼀个⼥孩的母亲要给这个⼥孩介绍男朋友，于是有了下⾯的对话：
⼥⼉：多⼤年纪了？
母亲：26。
moodle⼥⼉：长的帅不帅？
母亲：挺帅的。
⼥⼉：收⼊⾼不？
母亲：不算很⾼，中等情况。
⼥⼉：是公务员不？conroe
母亲：是，在税务局上班呢。
⼥⼉：那好，我去见见。
这个⼥孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收⼊和是否公务员对将男⼈分为两个类别：见和不见。假设这个⼥孩对男⼈的要求是：30岁以下、长相中等以上并且是⾼收⼊者或中等以上收⼊的公务员，那么这个可以⽤下图表⽰⼥孩的决策逻辑（声明：此决策树纯属为了写⽂章⽽YY的产物，没有任何根据，也不代表任何⼥孩的择偶倾向，请各位⼥同胞莫质问我^_^）：
香港大学研究生申请
上图完整表达了这个⼥孩决定是否见⼀个约会对象的策略，其中绿⾊节点表⽰判断条件，橙⾊节点表⽰决策结果，箭头表⽰在⼀个判断条件在不同情况下的决策路径，图中红⾊箭头表⽰了上⾯例⼦中⼥孩的决策过程。
camp david>不要介意的英文这幅图基本可以算是⼀颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收⼊⾼中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。
dowell决策树⽅法的起源是概念学习系统CLS，然后发展到ID3⽅法，最后⼜演化为能处理连续属性的C5.0.有名的决策树⽅法还有CART和Assistant。这⾥我的实现⽅法是ID3。
ID3算法的思想是采⽤贪⼼的策略选取分类能⼒最好的⼀个属性来，然后对于这个最佳属性的每⼀个取值产⽣⼀个分⽀，对于每⼀个分⽀都将有属于它的训练样例，重复前边的过程来完成建树。
ID3算法的伪代码实现如下（摘⾃《机器学习》，）：
ID3(Examples, Target_attribute, Attributes)
Examples即训练样例集。Target_attribute是这棵树要预测的⽬标属性。Attributes是除⽬标属性外供学习到得决策树测试的属性列表。
返回⼀棵能正确分类给定Examples的决策树
创建树的Root节点
如果Examples 都为正，那么返回label = 的单节点树Root
如果Examples 都为反，那么返回label = - 的单节点树Root
如果Attributes为空，那么返回单节点树Root, label=Examples中最普遍的Target_attributes值
否则开始
A <- Attributes中分类Examples能⼒最好的属性
Root的决策属性 <- A
对于A的每个可能值vi
在Root下加⼀个新的分⽀对应测试A = vi
令Examples vi为Examples中满⾜A属性值为vi的⼦集
如果Examples vi为空
savvy翻译在这个新分⽀下加⼀个叶⼦结点，结点的label=Examples中最普遍的Target_attribute值
否则在这个新分⽀下加⼀个⼦树ID3(Examples vi, Target_attribute, Attributes - {A})
结束
返回Root
看起来这个算法还是很简单的，但是还有⼀个问题，如何选择分类能⼒最好的⼀个属性，这也是ID3算法要解决的核⼼问题。ID3算法使⽤统计学来实现的。
⽤⼀个例⼦来说明分类能⼒最好的属性是如何产⽣的。
现在有⼀组数据，数据中包括天⽓情况和某事是否去打⽹球的情况，如下。
upperoutlook temperature humidity windy play
sunny hot high weak no
sunny hot high strong no
overcast hot high weak yes
rainy mild high weak yes
rainy cool normal weak yes
rainy cool normal strong no
男生秋装搭配
overcast cool normal strong yes
sunny mild high weak no
sunny cool normal weak yes
rainy mild normal weak yes
sunny mild normal strong yes
overcast mild high strong yes
overcast hot normal weak yes
no
rainy mild high strong
现在先来介绍⼀下熵，熵是信息论中⼴泛使⽤的⼀个度量标准，它是来衡量⼀个随机变量出现的数学期望，刻画了任意样例集的纯度。给定包含关于某个⽬标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为：
⽐如上述数据的计算式为：
Entropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940
已经有了熵作为衡量训练样例集合纯度的标准，现在可以定义属性分类训练数据的效⼒的度量标准。这个标准被称为信息增益。简单的说，⼀个属性的信息增益就是由于使⽤这个属性分割样例⽽导致的期望熵降低(或者说，样本按照某属性划分时造成熵减少的期望)。更精确地讲，⼀个属性A相对样例集合S的信息增益Gain(S,A)被定义为：
其中 Values(A)是属性A所有可能值的集合，是S中属性A的值为v的⼦集。换句话来讲，Gain(S,A)是由于给定属性A的值⽽得到的关于⽬标函数值的信息。当对S的⼀个任意成员的⽬标值编码时，Gain(S,A)的值是在知道属性A的值后可以节省的⼆进制位数。
公里的英文为什么是⼆进制，很简单，计算机中的数据就是以⼆进制的形式存储的，信息量为n的数据就可以⽤lo
g2 (n) 位的⼆进制数来表⽰。
以上述信息中的wind属性为例，可以得到它的信息增益：
ID3算法基本上就已经介绍完了，对于上述数据我写了⼀个实现，由于⽔平有限，可能有些地⽅还有错误或不⾜，如果有⼈
发现，请留⾔，谢谢。
由于在这⾥贴代码效果不是很好，所以我放在的别的⽹站上，链接:
