WORD版数据挖掘十大经典算法.doc

数据挖掘经典算法国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.? C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；??? 2) 在树构造过程中进行剪枝；??? 3) 能够完成对连续属性的离散化处理；??? 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。决策树概述：?? 决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。一般的数据挖掘工具，允许选择分裂条件和修剪规则，以及控制参数（最小节点的大小，最大树的深度等等），来限制决策树的。决策树作为一棵树，树的根节点是整个数据集合空间，每个分节点是对一个单一变量的测试，该测试将数据集合空间分割成两个或更多块。每个叶节点是属于单一类别的记录。构造决策树的过程为：首先寻找初始分裂。整个训练集作为产生决策树的集合，训练集每个记录必须是已经分好类的。决定哪个属性域作为目前最好的分类指标。一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。建决策树，就是根据记录字段的不同取值建立树的分支，以及在每个分支子集中重复建立下层结点和分支。建决策树的关键在于建立分支时对记录字段不同取值的选择。选择不同的字段值，会使划分出来的记录子集不同，影响决策树生长的快慢以及决策树结构的好坏，从而导致找到的规则信息的优劣。可见，决策树算法的技术难点也就是选择一个好的分支取值。利用一个好的取值来产生分支，不但可以加快决策树的生长，而且最重要的是，产生的决策树结构好，可以找到较好的规则信息。相反，如果根据一个差的取值来产生分支，不但减慢决策树的生长速度，而且会使产生的决策树分支过细，结构性差，从而难以发现一些本来可以找到的有用的规则信息。 以下转自 祥子的BLOG /u/4d8d63030100096x#sort_1对分类树中的ID3和C4.5算法做了比较“实在”的介绍。 决策树的经典构造算法（一）——ID3 ID3算法是1986年由Quilan提出的，它是一个从上到下、分而治之的归纳过程。ID3算法的核心是：在决策树各级结点上选择属性时，通过计算信息增益来选择属性，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。 ??? 有关信息增益的定义以及具体的计算方法和实例，可以参考马瑜和王有刚的论文《ID3算法应用研究》的第1、2两节。 ??? ID3算法思想描述如下： (1) 初始化决策树T为只含一个树根(X,Q)，其中X是全体样本集，Q为全体属性集。 (2) if(T中所有叶节点(X’,Q’)都满足X属于同一类或Q’为空)then 算法停止； (3) else ??? {任取一个不具有(2)中所述状态的叶节点(X’,Q’)； (4)?for each Q’中的属性A do 计算信息增益gain(A,X’)； (5)?????选择具有最高信息增益的属性B作为节点(X’,Q’)的测试属性； (6)?for each B的取值bi do ????????{从该节点(X’, Q’)伸出分支，代表测试输出B=bi； ????????求得X中B值等于bi的子集Xi，并生成相应的叶节点(Xi’,Q’-{B})；} (7) 转(2)；} ??? ID3算法是决策树的一个经典的构造算法，在一段时期内曾是同类研究工作的比较对象，但通过近些年国内外学者的研究，ID3算法也暴露出一些问题，具体如下： ??? (1)信息增益的计算依赖于特征数目较多的特征，而属性取值最多的属