数据挖掘中的分类和聚类的区别可以大体概括为有监督(Superised)学习和无监督(Unsuperised)学习的区别。虽然它们都是对数据进行划分(partition)的算法,但分类在学习阶段(也就是接受训练集训练)的时候,其数据库是包含了类标号(class label)的,用以指定某一条数据记录属于哪一个分类,而聚类的数据是不包括类标号的。好比前篇中的例子,用于训练判断党派的模型的原始数据中,包含了每一个议员的实际所属党,我们根据这些来得到我们要的模型。但若过原始数据中并不包括每个议员的党派,而只是他们在各个议题上的取态,我们要根据这些数据来为他们分类,这就是个聚类问题。说到这里的确有打算试一下在数据集上试一下聚类。【题外话,最近看美剧《新闻编辑室》,对美国的党派之争有了点兴趣】
前篇已经写过决策树算法的总体算法,不同的决策树算法实际是对总体思路的不断改进,因此不再冗述通用的过程。
信息增益率
ID3,C4.5和CART使用的均是贪心,不回溯的方法。C4.5作为ID3之后继,在选择属性的时候使用的度量标准是信息的增益率而非信息增益。其定义如下:
为什么需要引入这个?细心的人会发现,基于信息增益的选择时,我们会倾向于选择那些具有大量可能值的属性,比如说数据库中每条记录有其唯一的ID,若数据集中包含着ID这一属性,根据ID划分,我们能得到N(N为数据记录数)个分支,其中分出来的每个子节点只包含该ID对应的那条记录,数据集大小为1,其信息纯度为最高。根据公式,有:
悲观剪枝
What's more difference? C4.5的另一大不同是其剪枝方式。
之前作业中引入的减少过拟合的剪枝方法,若数据的增益小于某个阈值视为划分停止,取其大多数值结束划分,这其实是一种前剪枝(Prepruning)。后剪枝(Postpruning)则是在整棵原始树构建出来后,在根据算法砍去其冗余枝,而不是在构建时根据算法避免冗余枝产生。
C4.5的悲观剪枝(Pessimistic Pruning)利用对一棵子树的错误率评估来判断要不要把该子树砍除。因为原始错误率是用训练集的测试结果,既然树是训练集训练出的,其错误率往往很小,因此估算时使用了悲观的方法。
设子树有S个叶子节点(决策节点),划分到这一子树的有N个测试集样例,其中错误的例子共有E个,则其乐观错误率为
当计算得剪枝后的错误率比剪枝前低的时候,我们就用子树的叶子节点中的多数值替换整棵子树。
连续值属性
如何划分那些连续值的属性,如果将数据集中的连续值属性看作是离散值,那也将是一场灾难,因为有多少个值就会划出多少个分支。很自然我们会想到,如果要划分连续值A,其决策过程应该是这样的:
也就是我们选择一个分裂点去对连续值进行二元划分。C4.5对连续属性的处理正是基于此。假设某节点的数据集中,连续属性A的所有取值排序后为
最后一句话,这篇东西应该加“机器学习”标签还是“数据挖掘”。。。。=-=
没有评论 :
发表评论