标签

2015年2月11日星期三

关于决策树的更多——C4.5

在写前面关于AI作业的决策树笔记的时候接触了CART及C4.5两个决策树算法的名称,最近在《数据挖掘》这本教材上看到了它们的介绍。今年的ICM D题也让我更多地了解了数据挖掘中分类(Classification)和聚类(Clustering)的知识,虽然我们队最后没用上决策树的算法
数据挖掘中的分类和聚类的区别可以大体概括为有监督(Superised)学习和无监督(Unsuperised)学习的区别。虽然它们都是对数据进行划分(partition)的算法,但分类在学习阶段(也就是接受训练集训练)的时候,其数据库是包含了类标号(class label)的,用以指定某一条数据记录属于哪一个分类,而聚类的数据是不包括类标号的。好比前篇中的例子,用于训练判断党派的模型的原始数据中,包含了每一个议员的实际所属党,我们根据这些来得到我们要的模型。但若过原始数据中并不包括每个议员的党派,而只是他们在各个议题上的取态,我们要根据这些数据来为他们分类,这就是个聚类问题。说到这里的确有打算试一下在数据集上试一下聚类。【题外话,最近看美剧《新闻编辑室》,对美国的党派之争有了点兴趣】
前篇已经写过决策树算法的总体算法,不同的决策树算法实际是对总体思路的不断改进,因此不再冗述通用的过程。

信息增益率
ID3,C4.5和CART使用的均是贪心,不回溯的方法。C4.5作为ID3之后继,在选择属性的时候使用的度量标准是信息的增益率而非信息增益。其定义如下:

代表的是数据集D根据属性A进行划分后的“分裂信息(Split Information)”,与ID3的信息增益不同的是,它考虑该输出的元组数相对D中元组总数的比例。
为什么需要引入这个?细心的人会发现,基于信息增益的选择时,我们会倾向于选择那些具有大量可能值的属性,比如说数据库中每条记录有其唯一的ID,若数据集中包含着ID这一属性,根据ID划分,我们能得到N(N为数据记录数)个分支,其中分出来的每个子节点只包含该ID对应的那条记录,数据集大小为1,其信息纯度为最高。根据公式,有:
id这一属性的增益值是最大的可能值。之所以根据id划分的Remainder值会为0,是因为根据id划分出来的每个数据集都有最高的集中度(纯度),但实际上这样的划分显然很无意义。增益率中对增益的归一便能解决这一问题。GainRate计算的便是属性A的信息增益和分裂信息量的比。

悲观剪枝
What's more difference? C4.5的另一大不同是其剪枝方式。
之前作业中引入的减少过拟合的剪枝方法,若数据的增益小于某个阈值视为划分停止,取其大多数值结束划分,这其实是一种前剪枝(Prepruning)。后剪枝(Postpruning)则是在整棵原始树构建出来后,在根据算法砍去其冗余枝,而不是在构建时根据算法避免冗余枝产生。
C4.5的悲观剪枝(Pessimistic Pruning)利用对一棵子树的错误率评估来判断要不要把该子树砍除。因为原始错误率是用训练集的测试结果,既然树是训练集训练出的,其错误率往往很小,因此估算时使用了悲观的方法。
设子树有S个叶子节点(决策节点),划分到这一子树的有N个测试集样例,其中错误的例子共有E个,则其乐观错误率为。根据概率论中用正态分布拟合二项分布,p的置信区间为,我们的悲观错误率便是这一区间的上界,的取值可以是0.25。
当计算得剪枝后的错误率比剪枝前低的时候,我们就用子树的叶子节点中的多数值替换整棵子树。

连续值属性
如何划分那些连续值的属性,如果将数据集中的连续值属性看作是离散值,那也将是一场灾难,因为有多少个值就会划出多少个分支。很自然我们会想到,如果要划分连续值A,其决策过程应该是这样的:
也就是我们选择一个分裂点去对连续值进行二元划分。C4.5对连续属性的处理正是基于此。假设某节点的数据集中,连续属性A的所有取值排序后为, 任意相邻的一对值的中点均有可能成为分裂点。v个值将有v-1个划分方案。 我们对于每个划分方案,计算其Remainder,则Remainder最小的是我们需要的分裂方案(还是那句,因为这样分裂两边的集中度最高)。按照分裂点分成两个区间后,连续值的问题便成为了二值问题,我们便可将这个二值化后的属性与其他属性进行比较,从而确定要拿来划分的属性。

最后一句话,这篇东西应该加“机器学习”标签还是“数据挖掘”。。。。=-=

没有评论 :

发表评论