今天心情大好，看到了讲述决策树的好文，学习分享一下。。。

==========分割============================================

决策树（decision tree）——以实例为基础的归纳学习算法，采用自定向下的递归方式从一组无次序无规则的元组中推理出分类规则。对于给定的元组，通过在决策树的内部节点进行对应属性值的比较来确定该节点后面的分支，直到遇到叶子节点就可以判定该元组属于哪个分类。从跟到叶子的一条路径就对应于一条合取规则。

》》理解决策树的思想不算太难，大家都懂的，但是根据一组已经标记类别的元组建立决策树就是很多方法的啦。。。比较出名的ID3，C4.5啦

===========再分割============================================

1.ID3算法

思想：在决策树各级节点上根据“信息增益（Information gain）”作为属性选择的标准，即使用使用“信息增益”来衡量一个属性区分数据样本的能力，信息增益量越大，说明这个属性作为一棵树的根节点能使得这棵树更简洁。
具体做法：检测数据样本的所有属性，选择信息增益最大的属性作为该决策树的结点，再由该属性的不同取值建立分支，然后再使用该方法递归的对各个分支建立决策书节点的分支，直到所有属性都对应决策树的一个内部节点为止。决策树建立起来以来就可以对新的数据样本进行分类。

2.C4.5算法
C4.5算法是继承ID3并在其基础上改进的算法，它使用的是“信息增益率”作为属性选择的标准，这一点克服了“信息增益”选择属性时偏向选择取值多的属性的不足；同时在决策树的构造过程中使用了“剪枝”方法。C4.5可以对连续属性进行离散化处理。

==========再再分割=================================================

“信息熵”通俗的讲是指信息的混乱程度，熵值越大，表示信息越混乱，而对于要进行分类或聚类的数据样本，我们当然希望信息熵越小越好，这样就表明相似的数据样本距离近，而相异的数据样本距离远。

注：对于信息熵的概念，是针对数据样本的某一个衡量标准来讲的，也就是说，针对数据样本的某个属性的信息熵是指以该属性来划分数据样本的信息混乱程度。

这里使用一个例子来具体说明“信息熵”和“信息增益”的计算，希望能更好的理解。。。

E.g 某数据样本包含的属性：wind，humidity，outlook，temperature，和play，其中play是需要检查的属性，其值有yes和no。简单说也就是在给定的天气，温度，湿度和风力情况下，判断是否出去玩的问题啦！

1.现给定14条做了标记的数据样本，其中正例yes有9条，反例no有5条。该样本的熵记为Entropy（S），则有Entropy(S)=-(9/14)*log(9/4)-(5/14)*log(5/14)=0.940

其中log表示以2为底的对数。

2.分别计算以wind, humidity, outlook, temperature作为根节点时的信息增益。

对于wind，其取值为weak或者strong，其中，取weak的记录中play有6个正例，2个反例；取strong的记录中有3个正例，3个反例，则有

Entropy(weak)=-(6/8)*log(6/8)=0.811

Entropy(strong)=-(2/8)*log(2/8)=1.0

wind的信息增益为：

Gain(wind)=Entropy(S)-(8/14)*Entropy(weak)-(6/8)*Entropy(strong)=0.048

同理，Gain(humidity)=0.151，Gain(outlook)=0.247，Gain(temperature)=0.029

根据前面说的选择“信息增益”最大的属性作为根节点，因此该决策树的根节点为outlook，再根据outlook的取值建立决策树的分支，递归使用该方法直到所有的属性都已经成为决策树的节点。

==========分了再分===================================================

心情好的时候学习总是觉得内容很有意思。。。加油加油咯数据挖掘分类之决策树

ITPub博客

数据挖掘分类之决策树