数据挖掘十大经典算法教材

数据挖掘十大经典算法石峰国际权威的学术组织theIEEEInternationalConferenceonDataMining(ICDM)2006年12月评选出了数据挖掘领域的十大经典算法数据挖掘大致萌芽于上世纪70年代，例如，在先期探索基础上，1978年，RossJ.Quinlan提出判定树方法ID3，后来发展为成为C4.5算法。十几年前，数据挖掘学科进入了“而立”之年，向“不惑”推进，那时节，研究对象天天拓广，研究团队日益繁荣，老人要评功，新人要成长。有人顺天应时，提出动议：回顾成败、论功行赏、反思问题、展望未来。此议一呼，举“界”百应。

经过一段时间酝酿，以ICDM2006为依托，广发英雄牒，邀请ACMKDD发明奖得主和IEEEICDM研究贡献奖得主，作为数据挖掘十大算法提名委员会专家，得到积极响应。

严密的三阶段评选程序：组织者提出了三阶段评选程序：

(1)提名阶段:给出被提名算法名称,作简短评价,提出代表性人物；

(2)验证阶段：验证软件效率，查被引用频次，要求在2006.10月底，在GoogleScholar上至少查出被引用50次以上。这里选用GoogleScholar，而不是SCI，EI，是因为在当时，数据库和数据挖掘界的几个顶级会议（SIGMOD，VLDB，ICDE，ICDM等）以其水平和难度，堪称数据库界的奥林匹克或世界级锦标赛，但却被SCI和EI遗忘。

另类的二八规律提名和验证两阶段共推选出18个算法，并按验证指标排序。自然，其中8个在后来投票中未进入Top10，不妨称为提名奖得主，在高手如云的激烈竞争中，提名奖也是难得的荣誉。

巧得很，18个算法在后来的投票阶段中，只有两名从10名后升进10名前：即第11名K-Means和第13名AdaBoost，占20%；而原Top10中的80%在在前10中站稳了脚跟，不知这算不算另类的二八规律，即临近投票前的再努力，包括解释、演示和其他活动可能有20%的作用。

8个提名奖下面列出获提名奖的算法名次、名称及首发文章。值得注意的是，华裔学者韩家炜在出现了三次，裴健出现了两次。清单如下：

#8.FP-Tree:Han,J（韩家炜）.,Pei,J.（裴健）,andYin,Y.2000.Miningfrequentpatternswithoutcandidategeneration.InSIGMOD‘00.LinkMining。挖掘关联规则的快速算法；

#10.HITS:Kleinberg,J.M.1998.Authoritativesourcesinahyperlinkedenvironment.InProceedingsoftheNinthAnnualACM-SIAMSymposiumonDiscreteAlgorithms,1998.网页超链诱导主题搜索；

#12.BIRCHZhang,T.,Ramakrishnan,R.,andLivny,M.1996.BIRCH:anefficientdataclusteringmethodforverylargedatabases.InSIGMOD‘96.聚类算法；

#14.GSP:Srikant,R.andAgrawal,R.1996.MiningSequentialPatterns:GeneralizationsandPerformanceImprovements.InProceedingsofthe5thInternationalConferenceonExtendingDatabaseTechnology,1996.时间序列模式挖掘；

#15.PrefixSpan:J.Pei（裴健）,J.Han（韩家炜）,B.Mortazavi-Asl,H.Pinto,Q.Chen,U.DayalandM-C.Hsu.PrefixSpan:MiningSequentialPatternsEfficientlybyPrefix-ProjectedPatternGrowth.InICDE‘01.时间序列模式挖掘；

#16.CBA:Liu,B.,Hsu,W.andMa,Y.M.Integratingclassificationandassociationrulemining.KDD-98.??RoughSets，分类算法；

#17.Findingreduct:Zdzislaw

Pawlak,RoughSets:TheoreticalAspectsofReasoningaboutData,KluwerAcademicPublishers,Norwell,MA,1992，粗糙集理论；

#18.gSpan:Yan,X.andHan,J（韩家炜）.2002.gSpan:Graph-BasedSubstructurePattern，图数据挖掘；

(3)投票阶段：为客保证广泛的代表性和公正性，投票委员会在提名委员会基础上做了扩大，增加了KDD-06,ICDM'06,SDM'06三个国际会议的程序委员会委员。投票前，由推选的第三方专家介绍算法及其学术影响（被引用情况等），研究应用现状以及前景，充分酝酿基础上，投票产生了Top10.

参与评比的18种算法，它们在数据挖掘领域都产生了极为深远的影响。在学习数据挖掘时，可以以这18种算法为主线，如果能把每一种算法都弄懂，整个数据挖掘领域就掌握得差不多了。Classification#1.C4.5Quinlan,J.R.1993.C4.5:ProgramsforMachineLearning.MorganKaufmannPublishersInc.#2.CARTL.Breiman,J.Friedman,R.Olshen,andC.Stone.ClassificationandRegressionTrees.Wadsworth,Belmont,CA,1984.#3.KNearestNeighbours(kNN)Hastie,T.andTibshirani,R.1996.DiscriminantAdaptiveNearestNeighborClassification.IEEETrans.PatternAnal.Mach.Intell.(TPAMI).18,6(Jun.1996),607-616.#4.NaiveBayesHand,D.J.,Yu,K.,2001.Idiot'sBayes:NotSoStupidAfterAll?Internat.Statist.Rev.69,385-398.StatisticalLearning#5.SVM

Vapnik,V.N.1995.TheNatureofStatisticalLearningTheory.Springer-VerlagNewYork,Inc.

#6.EMMcLachlan,G.andPeel,D.(2000).FiniteMixtureModels.J.Wiley,NewYork.AssociationAnalysis#7.Apriori

Rakesh

AgrawalandRamakrishnan

Srikant.FastAlgorithmsforMiningAssociationRules.InProc.ofthe20thInt‘lConferenceonVeryLargeDatabases(VLDB’94),Santiago,Chile,September1994..sg/agrawal94fast.html#8.FP-TreeHan,J.,Pei,J.,andYin,Y.2000.Miningfrequentpatternswithoutcandidategeneration.InProceedingsofthe2000ACMSIGMODinternationalConferenceonManagementofData(Dallas,Texas,UnitedStates,May15-18,2000).SIGMOD'00.ACMPress,NewYork,NY,1-12.DOI=/10.1145/342009.335372LinkMining#9.PageRank

Brin,S.andPage,L.1998.Theanatomyofalarge-scalehypertextualWebsearchengine.InProceedingsoftheSeventhinternationalConferenceonWorldWideWeb(WWW-7)(Brisbane,Australia).P.H.EnslowandA.Ellis,Eds.#10.HITSKleinberg,J.M.1998.Authoritativesourcesinahyperlinkedenvironment.InProceedingsoftheNinthAnnualACM-SIAMSymposiumonDiscreteAlgorithms(SanFrancisco,California,UnitedStates,January25-27,1998).SymposiumonDiscreteAlgorithms.SocietyforIndustrialandAppliedMathematics,Philadelphia,PA,668-677.Clustering#11.K-Means

MacQueen,J.B.,Somemethodsforclassificationandanalysisofmultivariateobservations,inProc.5thBerkeleySymp.MathematicalStatisticsandProbability,1967,pp.281-297.#12.BIRCHZhang,T.,Ramakrishnan,R.,andLivny,M.1996.BIRCH:anefficientdataclusteringmethodforverylargedatabases.InProceedingsofthe1996ACMSIGMODinternationalConferenceonManagementofData(Montreal,Quebec,Canada,June04-06,1996).J.Widom,Ed.SIGMOD'96.ACMPress,NewYork,NY,103-114.BaggingandBoosting#13.AdaBoostFreund,Y.andSchapire,R.E.1997.Adecision-theoreticgeneralizationofon-linelearningandanapplicationtoboosting.J.Comput.Syst.Sci.55,1(Aug.1997),119-139.DOI=/10.1006/jcss.1997.1504SequentialPatterns#14.GSP

Srikant,R.andAgrawal,R.1996.MiningSequentialPatterns:GeneralizationsandPerformanceImprovements.InProceedingsofthe5thinternationalConferenceonExtendingDatabaseTechnology:AdvancesinDatabaseTechnology(March25-29,1996).P.M.Apers,M.Bouzeghoub,andG.Gardarin,Eds.LectureNotesInComputerScience,vol.1057.Springer-Verlag,London,3-17.#15.PrefixSpanJ.Pei,J.Han,B.Mortazavi-Asl,H.Pinto,Q.Chen,U.DayalandM-C.Hsu.PrefixSpan:MiningSequentialPatternsEfficientlybyPrefix-ProjectedPatternGrowth.InProceedingsofthe17thinternationalConferenceonDataEngineering(April02-06,2001).ICDE'01.IEEEComputerSociety,Washington,DCIntegratedMining#16.CBALiu,B.,Hsu,W.andMa,Y.M.Integratingclassificationandassociationrulemining.KDD-98,1998,pp.80-86..sg/liu98integrating.htmlRoughSets#17.Findingreduct

Zdzislaw

Pawlak,RoughSets:TheoreticalAspectsofReasoningaboutData,KluwerAcademicPublishers,Norwell,MA,1992GraphMining#18.gSpanYan,X.andHan,J.2002.gSpan:Graph-BasedSubstructurePatternMining.InProceedingsofthe2002IEEEInternationalConferenceonDataMining(ICDM'02)(December09-12,2002).IEEEComputerSociety,Washington,DC.最终当选的十大经典算法

C4.5,k-Means,SVM,Apriori,EM,PageRank,

AdaBoost,kNN,NaiveBayes,CART.数据挖掘Top10十大算法按得票数排序如下：

#1:C4.5(61票),

#2:K-Means(60票),

#3:SVM(58票),（分类算法

#4:Apriori(52票),

#5:EM(48票),（期望最大化算法，聚类与参数估计）；

#6:PageRank(46票),（谷歌选页的著名算法）；

#7:AdaBoost(45票),（积弱为强的分类算法）；

#7:kNN(45票),（以邻为楷模的分类方法）；

#7:NaiveBayes(45票),（分类算法）；

#10:CART(34票),（二分递归分割的的决策树方法）；

C4.5

C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；

2)在树构造过程中进行剪枝；

3)能够完成对连续属性的离散化处理；

4)能够对不完整数据进行处理。C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。Thek-meansalgorithm

k-meansalgorithm（K-Means算法）是一个聚类算法，把n的对象根据他们的属性分为k个分割，k<n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。Supportvectormachines

支持向量机，英文为SupportVectorMachine，（SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.CBurges的《模式识别--支持向量机指南》。TheApriorialgorithm

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。最大期望(EM)算法

在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏（Latent）变量,最大期望经常用在机器学习和计算机视觉的数据集聚（DataClustering）领域。PageRank

PageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里·佩奇（LarryPage）。因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。AdaBoost

Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。kNN:k-nearestneighborclassification

K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。NaiveBayes

在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(DecisionTreeModel)和朴素贝叶斯模型（NaiveBayesianModel，NBC）。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。CART:分类与回归树

CART,ClassificationandRegressionTrees。在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝。数据挖掘向何处去6年前的10大问题.

为表达远见卓识，专家们常自问自答这样的问题：本领域向何处去？下一代关键技术是什么？本领域未来十年的研究什么？

在数据挖掘的顶级国际会议ICDM2005上，一批专家提出了10个挑战性问题，如今刚满七年，让我们来看看这十大挑战性问题，看看今天的研究状态：

问题1

数据挖掘的统一理论。十年前，专家看到当时的数据挖掘中急用先研的短期行为较多，为单个问题研究技术，无统一的理论，目光不远大,至今，比较完整的数据挖掘的同一理论还在探索中；

问题2

规模伸缩性、高维和高速问题。十年前的数据挖掘技术，在维度增加，数据规模增大时，所需资源（时间、空间和CPU）指数级地增加，在数据流分析、网络攻防、传感器网络应用中成为瓶颈；如今问题仍然在；

问题3

时间序列的高效率处理+高效分类聚类和预测,如今，在短长期预报,高精度处理方面问题仍然存在；

问题4

复杂数据总挖掘复杂知识，如图数据挖掘等表现突出，如今，在亚复杂系统干预规则的挖掘中也有需求；

问题5

网络挖掘，社会网络，邮件，网页，网络反恐，海量数据挖掘等；问题仍然存在；

问题6

分布式挖掘和多代理挖掘，如大型网络游戏，网络军事对抗等，需求日益增加；

问题7

生物数据挖掘艾滋病疫苗相关、DNA相关的数据挖掘，方兴未艾；

问题8

数据挖掘自身的方法论研究，尚待突破；

问题9

数据挖掘与信息安全和隐私保护；成为目前关注热点；

问题10.特色数据的挖掘：包括高价值数据（如重症监护室数据），偏斜数据（抽样偏斜失真），不平衡数据（有用的只占很小比例）。如今，七年过去了，人们欣慰地看到，专家不是砖家，他们提出的问题指导着这些年的研究方向。七年中出现了若干新事物，引出了若干新问题，如物联网相关的数据挖掘，云计算相关的数据挖掘，但上述十大问题还在被研究被解决，推动着数据挖掘的理论、系统和应用。PageRank&Hits石峰Outline背景介绍PageRankHitsPageRank

vsHitsPageRank&Hits在研究中的应用背景介绍Web上超链接结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大的提高检索结果的质量。SergeyBrin和LawrencePage在1998年提出了PageRank算法，同年J.Kleinberg提出了HITS算法LawrencePage,SergeyBrin,RajeevMotwani,TerryWinograd,'ThePageRankCitationRanking:BringingOrdertotheWeb',1998,

http://www-/~backrub/pageranksub.ps

为了更高效地计算PageRank,以下是改良以后的一篇论文。TaherH.Haveliwala,‘EfficientComputationofPageRank’,StanfordTechnicalReport,1999,

:8090/pub/1999-31PageRank(TM)是美国Google公司的登记注册商标。Google查询过程Google查询的全过程通常不超过半秒时间，但在这短短的时间内需要完成多个步骤，然后才能将搜索结果交付给搜索信息的用户。

PageRank?HITS?PageRank算法PageRank算法1

其中：PR(A):页面A的网页级别,

PR(Ti)：页面Ti的网页级别，页面Ti链向页面A，

C(Ti)：页面Ti链出的链接数量，

d：阻尼系数，取值在0－1之间PageRank算法2

其中N是互联网上所有网页的数量PR(A)=(1-d)+d(PR(T1)/C(T1)+...+PR(Tn)/C(Tn))PR(A)=(1-d)/N+d(PR(T1)/C(T1)+...+PR(Tn)/C(Tn))这个算法不以站点排序，页面网页级别由一个个独立的页面决定PageRank

的核心思想

PageRank

是基于「从许多优质的网页链接过来的网页，必定还是优质网页」的回归关系，来判定所有网页的重要性。反向链接数

(单纯的意义上的受欢迎度指标)反向链接是否来自推荐度高的页面(有根据的受欢迎指标)反向链接源页面的链接数(被选中的几率指标)因此，如果从类似于Yahoo!那样的PageRank

非常高的站点被链接的话，仅此网页的PageRank

也会一下子上升；相反地，无论有多少反向链接数，如果全都是从那些没有多大意义的页面链接过来的话，PageRank

也不会轻易上升。ComputingPageRank

-initializevectoroverwebpagesloop:-newrankssumofnormalizedback-linkranks (特征值与特征向量) -computenormalizingfactor

-addescapeterm

-controlparameterwhile-stopwhenconverged矩阵表示aij＝1if(从页面i向页面j「有」链接的情况)aij＝0if(从页面i向页面j「没有」链接的情况)当黑点呈横向排列时，表示这个页面有很多正向链接(即向外导出的链接)；反之，当黑店呈纵向排列时，表示这个页面有很多反向链接。PageRank

的矩阵是把这个邻接矩阵转置后(行和列互换)，为了将各列(column)矢量的总和变成1(全概率),PageRank实例链接源ID 链接目标ID1 2,3,4,5,72 13 1,24 2,3,55 1,3,4,66 1,57 5PageRank实例A=[ 0,1,1,1,1,0,1; 1,0,0,0,0,0,0; 1,1,0,0,0,0,0; 0,1,1,0,1,0,0; 1,0,1,1,0,1,0; 1,0,0,0,1,0,0; 0,0,0,0,1,0,0;]1,2,3,4,5,6,71,2,3,4,5,6,7PageRank实例M:将A转置后将各个数值除以各自的非零元素的总数M=[ 0, 1, 1/2, 0, 1/4, 1/2, 0; 1/5, 0, 1/2, 1/3, 0, 0, 0; 1/5, 0, 0, 1/3, 1/4, 0, 0; 1/5, 0, 0, 0, 1/4, 0, 0; 1/5, 0, 0, 1/3, 0, 1/2, 1; 0, 0, 0, 0, 1/4, 0, 0; 1/5, 0, 0, 0, 0, 0, 0;]PageRank实例流入量＝(ID=2发出的Rank)+(ID=3发出的Rank)+(ID=5发出的Rank)+(ID=6发出的Rank)=0.166+0.141/2+0.179/4+0.045/2=0.30375为什么要提出HITS算法？PageRank算法中对于向外链接的权值贡献是平均的，也就是不考虑不同链接的重要性。而WEB的链接具有以下特征：

1.有些链接具有注释性，也有些链接是起导航或广告作用。有注释性的链接才用于权威判断。

2.基于商业或竞争因素考虑，很少有WEB网页指向其竞争领域的权威网页。

3.权威网页很少具有显式的描述，比如Google主页不会