Top 10 algorithms in data mining

Abstract

This paper presents the top 10 data mining algorithms identified by the IEEE International Conference on Data Mining (ICDM) in December 2006: C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. These top 10 algorithms are among the most influential data mining algorithms in the research community. With each algorithm, we provide a description of the algorithm, discuss the impact of the algorithm, and review current and further research on the algorithm. These 10 algorithms cover classification, clustering, statistical learning, association analysis, and link mining, which are all among the most important topics in data mining research and development.

0 Introduction

In an effort to identify some of the most influential algorithms that have been widely used in the data mining community, the IEEE International Conference on Data Mining (ICDM, http://www.cs.uvm.edu/~icdm/) identified the top 10 algorithms in data mining for presentation at ICDM rsquo;06 in Hong Kong.

As the first step in the identification process, in September 2006 we invited the ACM KDD Innovation Award and IEEE ICDM Research Contributions Award winners to each nominate up to 10 best-known algorithms in data mining. All except one in this distinguished set of award winners responded to our invitation. We asked each nomination to provide the following information: (a) the algorithm name, (b) a brief justification, and (c) a representative publication reference. We also advised that each nominated algorithm should have been widely cited and used by other researchers in the field, and the nominations from each nominator as a group should have a reasonable representation of the different areas in data mining.

After the nominations in Step 1, we verifified each nomination for its citations on Google Scholar in late October 2006, and removed those nominations that did not have at least 50 citations. All remaining (18) nominations were then organized in 10 topics: association analysis, classifification, clustering, statistical learning, bagging and boosting, sequential patterns, integrated mining, rough sets, link mining, and graph mining. For some of these 18 algorithms such as k-means, the representative publication was not necessarily the original paper that introduced the algorithm, but a recent paper that highlights the importance of the technique. These representative publications are available at the ICDM website.

In the third step of the identification process, we had a wider involvement of the research community. We invited the Program Committee members of KDD-06 (the 2006 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining), ICDM rsquo;06 (the2006 IEEE International Conference on Data Mining), and SDM rsquo;06 (the 2006 SIAM International Conference on Data Mining), as well as the ACM KDD Innovation Award and IEEEICDM Research Contributions Award winners to each vote for up to 10 well-known algorithms from the 18-algorithm candidate list. The voting results of this step were presented at the ICDM rsquo;06 panel on Top 10 Algorithms in Data Mining.

At the ICDM rsquo;06 panel of December 21, 2006, we also took an open vote with all 145 attendees on the top 10 algorithms from the above 18-algorithm candidate list, and the top 10 algorithms from this open vote were the same as the voting results from the above third step. The 3-hour panel was organized as the last session of the ICDM rsquo;06 conference, in parallel with 7 paper presentation sessions of the Web Intelligence (WI rsquo;06) and Intelligent Agent Technology (IAT rsquo;06) conferences at the same location, and attracting 145 participants to this panel clearly showed that the panel was a great success.

1 C4.5 and beyond

1.1 Introduction

Systems that construct classifiers are one of the commonly used tools in data mining. Such systems take as input a collection of cases, each belonging to one of a small number of classes and described by its values for a fixed set of attributes, and output a classifier that can accurately predict the class to which a new case belongs.

These notes describe C4.5 [64], a descendant of CLS [41] and ID3 [62]. Like CLS and ID3, C4.5 generates classifiers expressed as decision trees, but it can also construct classififiers in more comprehensible ruleset form. We will outline the algorithms employed in C4.5, highlight some changes in its successor See5/C5.0, and conclude with a couple of open research issues.

1.2 Decision trees

Given a set S of cases, C4.5 first grows an initial tree using the divide-and-conquer algorithm as follows:

bull; If all the cases in S belong to the same class or S is small, the tree is a leaf labeled with the most frequent class in S.

bull; Otherwise, choose a test based on a single attribute with two or more outcomes. Make this test the root of the tree with one branch for each outcome of the test, partition S into corresponding subsets S1, S2, hellip; according to the outcome for each case, and apply the same procedure recursively to each subset.

There are usually many tests that could be chosen in this last step. C4.5 uses two heuristic criteria to rank possible tests: information gain, which minimizes the total entropy of the subsets {Si} (but is heavily biased towards tests with numerous outcomes), and the default gain ratio that divides information gain by the information provided by the test outcomes.

Attributes can be either numeric or nominal and this determines the format of the test outcomes. For a numeric attribute A they are {A≦h, A gt; h} where the threshold h is found by sorting S on the values of A and choosing the split between successive values that maximizes the criterion above. An attribute A with discrete values has by default one outcome for each value, but an option allows the values to be grouped into two o

剩余内容已隐藏，支付完成后下载完整资料

数据挖掘的十大算法

摘要

本文介绍了2006年12月IEEE国际数据挖掘大会(ICDM)评选出的十大数据挖掘算法:C4.5、k-Means、SVM、Apriori、EM、PageRank、AdaBoost、kNN、Naive Bayes和CART。这10种算法都是研究界最具影响力的数据挖掘算法。对每个算法进行了描述，讨论了算法的影响，并对当前和未来的研究进行了回顾。这10种算法涵盖了分类、聚类、统计学习、关联分析和链接挖掘，这些都是数据挖掘研究和开发中最重要的主题。

0引入

为了确定一些已经广泛应用于数据挖掘社区且最具影响力的算法,在ICDM 06年的香港IEEE数据挖掘国际会议(ICDM http://www.cs.uvm.edu/ ~ ICDM /)确定了十大算法在数据挖掘。

作为识别过程的第一步，2006年9月，我们邀请了ACM KDD创新奖和IEEE ICDM研究贡献奖的获奖者，分别提名10个最知名的数据挖掘算法。除了一位杰出的获奖者外，所有人都响应了我们的邀请。我们要求每个提名者提供以下信息:(a)算法名称，(b)简要论证，和(c)代表性出版物参考。我们还建议，每个提名的算法应该被该领域的其他研究人员广泛引用和使用，每个提名者作为一个组的提名应该合理地代表数据挖掘的不同领域。

在第一步的提名之后，我们在2006年10月底核实了每一个提名在谷歌Scholar上的引用情况，并删除了那些被引用不超过50次的提名。剩下的18个提名被分为10个主题:关联分析、分类、聚类、统计学习、套袋和助推、顺序模式、综合挖掘、粗糙集、链接挖掘和图挖掘。对于这18种算法中的一些算法，如k-means，代表性的出版物不一定是介绍该算法的原始论文，而是强调该技术重要性的最近的一篇论文。这些具有代表性的出版物可在国际发展研究中心网站上查阅。

在鉴定过程的第三步，我们有更广泛的研究团体参与。我们邀请了KDD-06(2006年ACM SIGKDD知识发现和数据挖掘国际会议)、ICDM 06(2006年IEEE数据挖掘国际会议)和SDM 06(2006年SIAM数据挖掘国际会议)的项目委员会成员，以及ACM KDD创新奖和IEEEICDM研究贡献奖获奖者，从18个算法候选名单中每人投票选出10个知名算法。这一步骤的投票结果在ICDM的06年度“数据挖掘的10大算法”专题讨论会上展示。

ICDM的06小组2006年12月21日,我们也采取了与所有145名与会者开放投票十大算法从上面18-algorithm候选人名单,和十大算法从这个开放投票投票结果一样从上面的第三步。3小时小组组织最后会话ICDM的06年会上,与7报告会议的网络智能(WI 06年)和智能代理技术(IAT 06)会议在同一位置,吸引了145名参与者,这显然面板显示面板是一个伟大的成功。

1 C4.5

1.1介绍

构造分类器的系统是数据挖掘中常用的工具之一。这类系统以案例的集合作为输入，每个案例属于少数类中的一个，并由其对一组固定属性的值进行描述，然后输出一个分类器，该分类器可以准确地预测一个新案例属于哪个类。

这些注释描述了C4.5 [64]， CLS[41]和ID3[62]的后代。与CLS和ID3一样，C4.5生成表示为决策树的分类器，但它也可以以更容易理解的规则集形式构造分类器。我们将概述C4.5中使用的算法，强调其继承者See5/C5.0中的一些变化，并以几个开放的研究问题结束。

1.2决策树

给定一组情况S, C4.5首先使用分治算法生成初始树，如下所示:

bull;如果S中的所有情况都属于同一类，或者S很小，那么树就是S中最常见的类标记的叶子。

bull;否则，选择一个基于两个或多个结果的单一属性的测试。将这个测试作为树的根，测试的每个结果都有一个分支，将S划分为相应的子集S1, S2，hellip;根据每个案例的结果，并对每个子集递归应用相同的过程。

在这最后一步通常有许多测试可以选择。C4.5使用两个启发式标准对可能的测试进行排序:信息增益，它最小化子集{Si}的总熵(但严重偏向于有许多结果的测试)，以及默认的增益比，即信息增益与测试结果提供的信息之间的比值。

属性可以是数字的，也可以是名义的，这决定了测试结果的格式。对于数字属性a，它们是{a≦h, a gt; h}，其中阈值h是通过对a的值进行S排序，并在满足上述条件的连续值之间选择拆分得到的。具有离散值的属性A默认为每个值提供一个结果，但有一个选项允许将这些值分组为两个或多个子集，每个子集有一个结果。

然后对初始树进行剪枝，以避免过拟合。修剪算法是基于对一组N种情况下的错误率的悲观估计，其中E不属于最常见的一类。C4.5不是用E/N来确定在N次试验中观察到E个事件时二项式概率的上限，而是使用用户指定的置信值，其默认值为0.25。

修剪从叶片一直进行到根部。在N种情况下，误差为E的叶片上估计误差为上述悲观错误率的N倍。对于一个子树，C4.5将分支的估计误差相加，并将其与被叶子替换的子树的估计误差进行比较;如果后者不高于前者，则对子树进行剪枝。类似地，C4.5检查估计的错误，如果子树被它的一个分支取代，当这显得有利时，树就会相应地修改。修剪过程通过树一次就完成了。

C4.5的树构造算法与CART[9]有几个不同之处，例如:

bull;CART中的测试总是二进制的，但C4.5允许两种或更多结果。

bull;CART使用基尼指数(Gini diversity index)对测试进行排名，而C4.5使用基于信息的标准。

使用成本-复杂性模型的CART修剪树，其参数由交叉验证估计;C4.5使用从二项式置信限导出的单遍算法。

bull;这个简短的讨论没有提到当一个案例的某些值未知时会发生什么。CART查找在被测试属性具有未知值时近似于结果的替代测试，但C4.5在结果之间按概率分配情况。

1.3规则集分类器

复杂的决策树可能很难理解，例如，因为关于一个类的信息通常分布在整个树中。C4.5引入了另一种形式，由“如果a、B、C和hellip;hellip;”然后是类X”，每个类的规则都被组合在一起。通过找到案例满足条件的第一条规则，对案例进行分类;如果不满足任何规则，则将case赋值给一个默认类。

C4.5规则集由初始的(未修剪的)决策树形成。从树的根到叶子的每条路径都成为一个原型规则，它的条件是沿着路径的结果，它的类是叶子的标签。然后，通过确定依次丢弃每个条件的效果来简化该规则。删除一个条件可能会增加规则涵盖的案例数N，也可能增加不属于规则指定类别的案例数E，并可能降低如上所确定的悲观错误率。使用爬山算法来降低条件，直到找到最低的悲观错误率。

要完成这个过程，需要依次为每个类选择简化规则的子集。这些类子集被排序以最小化训练案例上的错误，并选择一个默认类。最终规则集的规则通常比修剪后的决策树的叶子的数量少得多。

C4.5规则集的主要缺点是它们所需的CPU时间和内存。在一项实验中，从一个大型数据集中抽取了1万到10万例病例的样本。对于决策树，从10 k移动到100K将PC上的CPU时间从1.4 s增加到61 s，增加了44倍。然而，规则集所需的时间从32秒增加到9715秒，增加了300倍。

1.4 See5 / C5.0

C4.5在1997年被商用系统See5/C5.0(简称C5.0)取代。这些变化包括新功能和大大提高的效率，包括:

提升[24]的一个变体，它构建了一个分类器的集合，然后投票给出一个最终的分类。提高预测精度通常会带来显著提高。

bull;新的数据类型(例如，日期)，“不适用”的值，可变错误分类成本，以及预过滤属性的机制。

bull;无序规则集——当一个案例被分类时，所有适用的规则都被找到并投票。

这提高了规则集的可解释性和它们的预测准确性。

bull;极大地提高了决策树和(特别是)规则集的可伸缩性。可伸缩性通过多线程增强;C5.0可以利用具有多个cpu和/或核心的计算机。

更多详情请访问http://rulequest.com/see5-comparison.html。

1.5研究的问题

我们经常听到同事表达这样的观点:决策树是一个“已解决的问题”。“我们不同意这个主张，并将以几个开放的研究问题来结束。

稳定的树。众所周知，在构建树的情况下，树的错误率(重代错误率)远低于不可见情况下的错误率(预测错误率)。例如，在一个已知的包含20,000个案例的字母识别数据集上，C4.5的替换错误率为4%，而遗漏(20,000倍)交叉验证的错误率为11.7%。正如本文所演示的，从20,000中省略一个案例通常会影响所构建的树!

现在假设我们可以开发一个非平凡树构造算法，它几乎不会因为遗漏任何一种情况而受到影响。对于这种稳定树，重代错误率应该近似于留一交叉验证错误率，表明树的大小是“正确的”。

分解复杂的树。集成分类器，无论是通过增强、套袋、权重随机化或其他技术生成，通常提供改进的预测精度。现在，给定少量的决策树，有可能生成一棵完全等同于投票的(非常复杂的)树，但我们能反过来吗?也就是说，一个复杂的树可以被分解成一个小的简单树的集合，当它们一起投票时，会给出与复杂树相同的结果吗?这样的分解对于生成可理解的决策树有很大的帮助。

C4.5致谢

关于C4.5的研究由澳大利亚研究委员会资助多年。

C4.5可以免费用于研究和教学，源代码可以从http://rulequest.com/Personal/c4.5r8.tar.gz下载。

2 k-means算法

2.1算法

k-means算法是一种简单的迭代方法，用于将给定数据集划分为用户指定数量的聚类，k。该算法已被多个不同学科的研究人员发现，最著名的是Lloyd (1957, 1982) [53]， Forgey (1965)， Friedman and Rubin(1967)，和McQueen(1967)。[43]中给出了k-means的详细历史以及几种变体的描述。Gray和Neuhoff[34]为在爬山算法的大背景下放置的k均值提供了一个很好的历史背景。

该算法作用于D维向量集，D = {xi | i = 1，hellip;N}，其中xiisin;Kd 表示第i个数据点。算法通过在k个点中选取k个点来初始化d 作为初始k的簇代表或“质心”。选择这些初始种子的技术包括从数据集中随机抽样，将它们设置为聚类数据的一个小子集的解决方案，或扰动数据的全局平均值k次。然后算法在两步之间迭代，直到收敛:

步骤1:数据分配。每个数据点被分配到它最近的质心，并任意断开连接。这将导致对数据进行分区。

第二步:重新安置“中心”。每个集群代表被重新定位到所有分配给它的数据点的中心(平均值)。如果数据点带有概率度量(权重)，那么将迁移到数据分区的期望(加权平均值)。

当赋值(因此cj 值)不再改变。算法执行过程如图1所示。注意，每次迭代需要N times; k次比较，这决定了一次迭代的时间复杂度。收敛所需的迭代次数是不同的，可能与N有关，但作为第一次切割，该算法在数据集大小上可以认为是线性的。

一个需要解决的问题是如何在分配步骤中量化“最接近的”。亲密度的默认度量是欧几里得距离，在这种情况下，我们可以很容易地表明，非负代价函数会随着赋值或重定位步骤的变化而减小，因此在有限次迭代中保证收敛。k-均值在非凸代价上的贪婪下降性质也意味着收敛只到局部最优，而且该算法通常对初始质心位置非常敏感。图21 说明了对于相同的数据集，对于三个初始质心的不同选择，得到的结果不如图1所示。局部极小问题可以通过对不同的初始质心进行多次运行或对收敛解进行有限的局部搜索来解决。

2.2局限

除了对初始化很敏感之外，k-means算法还存在其他几个问题。首先，观察k-means是由具有相同、各向同性协方差矩阵的混合k高斯拟合数据的一种极限情况(Sigma; = sigma;2I)，当对混合分量的数据点进行软分配时，将每个数据点单独分配给最有可能的分量。因此，当数据没有被合理分离的球形球很好地描述时，例如，如果数据中有非covex形状的簇，它就会动摇。这个问题可以通过在聚类之前将数据重新调整到“whiten”，或者使用更适合数据集的不同距离度量来缓解。例如，信息理论聚类使用KL-divergence来测量代表两个离散概率分布的两个数据点之间的距离。最近的研究表明，如果一个人在分配步骤中，通过选择一个非常大的发散类(称为Bregman发散)中的任何一个成员来测量距离，而不做其他改变，k-means的基本属性，包括保证收敛，线性分离边界和可伸缩性，被保留[3]。只要使用适当的散度，这个结果使k-means对更大的数据集有效。

K-means可以与另一种算法配对来描述非凸聚类。第一种方法是使用k-means将数据聚集到大量组中。然后，这些组使用单一链接层次聚类聚集成更大的集群，这种集群可以检测复杂的形状。这种方法还使解决方案对初始化不那么敏感，而且由于分层方法提供了多个分辨率的结果，因此也不需要预先指定k。

随着k的增加，最优解决方案的成本降低，直到当集群的数量等于不同数据点的数量时，它达到0。这使它更加困难(a)直接比较不同数量的集群解决方案和(b)的最佳值k。如果事先不知道所需的k,一个通常会运行k - means不同的k值,然后使用一个合适的标

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[588820]，资料为PDF文档或Word文档，PDF文档可免费转换为Word