C4.5算法在信息检索结果分类中的应用.doc

C4.5算法在信息检索结果分类中的应用 　　摘要：决策树是归纳学习和数据挖掘的重要方法，该文对c4.5算法、决策树的构建和剪枝进行了介绍，然后将C4．5算法应用于信息检索结果分类中，实现了检索结果的分层分类处理。 　　关键词：信息检索；决策树；C4.5算法 　　中图分类号：TP301文献标识码：A文章编号：1009-3044(2011)09-2126-03 　　C4.5 Algorithm in the Classification of Search Results 　　HUANG Wei 　　(Changsha Aeronautical Vocational and Technical College, Changsha 410014, China) 　　Abstract: Decision tree inductive learning and data mining is an important method. In this paper, c4.5 algorithm, decision tree construction and pruning were introduced. Then C4.5 algorithm is applied to the results of classification in information retrieval, search results to achieve a hierarchical classification. 　　Key words: information retrieval; decision tree; c4.5 algorithm 　　企业信息检索系统所给出的检索结果，可能会包含比较多的记录。这些记录在用户进行浏览时，是以分页的方式呈现给用户的，每当用户完成一页信息的查看后，通过相关的操作，可以将显示引导到后继的新的一页或之前的某一页。信息结果的分页呈现，一方面是便于用户浏览信息的需要，同时也是检索系统分层实现检索的外在体现。检索结果计算从综合的角度来说，主要完成以下几个大的方面的内容：首先是对关键字有关的相关指标的统计分析；其次是检索结果的挖掘分类；最后是检索结果的分页处理。 　　分类是数据挖掘中的一个重要课题，近年来，数据分类技术已经被有效地，广泛地应用于科学实验，商业决策等领域，引起了学术界的关注。现有的决策树分类算法主要有CLS、ID3、C4．5、CART、SLIQ、SPRINT等，本文选取的c4．5算法是用于构造决策树的经典算法之一。 　　1 决策树及C4.5算法 　　1.1 决策树 　　所谓决策树(Decision Tree)是一种决策过程的图形，?Q策过程中由许多不同的行动方案和许多不同发生状况(或事件) 相交配合而成，形同树状分析，故称决策树。决策树对杂乱的数据进行数据挖掘时，决策树分类方法采用自顶向下的递归方式，把一组无序的数据整理成类似于流程图的树结构。其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个树叶结点代表类或类分布。所以，从决策树的根到叶结点的一条路径对应着一条合取规则。 　　基于决策树的分类算法的一个最大的优点就是它在学习过程中不需要使用者了解很多的背景知识。要构造决策树模型，首先将数据集划分为训练集和测试集。在训练集中，根据每个属性的增益率，构造出最初的决策树模型。决策树建立好后，为消除决策树对测试数据分类时产生的“过度拟合”问题，将其进行剪枝，得到决策树决策规则。利用决策树方法进行数据挖掘，一般的步骤为：数据预处理，数据挖掘操作，剪枝和应用。 　　数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来做预测。建立决策树的过程，即树的生长过程是不断的把数据进行切分的过程，每次切分对应一个问题，也对应着一个节点。对每个切分都要求分成的组之间的“差异”最大。 　　1.2 C4.5算法 　　C4.5算法是众多决策树算法中比较成熟、应用比较广泛的一个经典算法，非常适合数据的增量挖掘。 　　(1) C4.5算法扩展 　　C4.5提出了最初ID3算法的一些扩展： 　　① 建立决策树，通过评估增益或者增益率，能处理有未知属性值的训练集，对于一个属性仅仅考虑它被定义的那条的记录。增益率计算公式为： 　　 GainRatio(D,T)=Gain(D,T)/SplitInfo(D,T) (1) 　　在这里，SplitInfo(D,T)是基于类属性值D的T分裂产生的信息。因此SplitInfo(D,T)是I(|T1|/|T|,|T2|/|T|,…,|Tm|/|T|)。在这里（T1,T2,…,Tm）是D值诱导的T分割。 　　② 处理未知值的训练样本。C4.