数据挖掘10大算法

Sunstone Zhang 编译 数据挖掘者 http://idmer.blog.sohu.com 数据挖掘10大算法 Top 10 Algorithms in Data Mining ICDM 2006 Panel 12/21/2006, Coordinators: Xindong Wu and Vipin Kumar 注：ICDM的全称是IEEE International Conference on DataMining Page 2 大纲 1. 1. 三步鉴定 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 三步鉴定流程 2. 182. 18种通过审核的候选算法种通过审核的候选算法 33.. 算法陈述算法陈述 44.. 数据挖掘数据挖掘1100大算法：一览大算法：一览 55.. 开放式讨论开放式讨论 Page 3 大纲 1. 1. 三步鉴定流程三步鉴定流程 2. 182. 18种通过审核的候选算法种通过审核的候选算法 33.. 算法陈述算法陈述 44.. 数据挖掘数据挖掘1100大算法：一览大算法：一览 55.. 开放式讨论开放式讨论 Page 4 三步鉴定流程 1. 提名 (Nominations) 使用以下三个步骤来选出数据挖掘的10大算法 § 在2006年9月召开的ICDM会议上，我们邀请了ACM KDD创新大奖(Innovation Award)和 IEEE ICDM研究贡献奖(Research Contributions Award)的获奖者们来参与数据挖掘10大算 法的选举，每人提名10种他认为最重要的算法 § 除一人未参与外，其他获奖者均给出了算法的提名 § 每个提名中均需同时给出以下信息： - (a) 算法名称 - (b) 提名理由摘要 - (c) 算法的代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 性论文 § 每个提名算法都应该被相关领域的研究者们广泛引用和使用，每位提名者给出的同类算法应 该是数据挖掘重要应用领域的代表 Page 5 三步鉴定流程 2. 审核 (Verification) 使用以下三个步骤来选出数据挖掘的10大算法 § 在2006年10月，我们通过Google Scholar对每个提名算法的引用情况进行了审核，从候选名 单中删除了低于50篇论文引用的算法 § 最终剩下18种提名算法通过了审核，它们分属10类数据挖掘主 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 3. 投票 (Voting) § 我们邀请了更多的专业人士来从这些候选算法中投票选出10大算法，他们包括 - (a) KDD-06、ICDM ‘06和SDM ’06的程序委员会成员 (Program Committee members) - (b) ACM KDD创新大奖和IEEE ICDM研究贡献奖的获奖者们 § 根据票数排名筛选出10大算法 (如果票数相同，则按字母顺序进行排名) Page 6 大纲 1. 1. 三步鉴定流程三步鉴定流程 2. 182. 18种通过审核的候选算法种通过审核的候选算法 33.. 算法陈述算法陈述 44.. 数据挖掘数据挖掘1100大算法：一览大算法：一览 55.. 开放式讨论开放式讨论 Page 7 18种通过审核的候选算法 § 分类 (Classification) - 1. C4.5: Quinlan, J. R. 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc. - 2. CART: L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984. - 3. K Nearest Neighbours (kNN): Hastie, T. and Tibshirani, R. 1996. Discriminant Adaptive Nearest Neighbor Classification. IEEE Trans. Pattern Anal. Mach. Intell. (TPAMI). 18, 6 (Jun. 1996), 607-616. - 4. Naive Bayes Hand, D.J., Yu, K., 2001. Idiot's Bayes: Not So Stupid After All? Internat. Statist. Rev. 69, 385-398. § 统计学习 (Statistical Learning) - 5. SVM: Vapnik, V. N. 1995. The Nature of Statistical Learning Theory. Springer-Verlag New York, Inc. - 6. EM: McLachlan, G. and Peel, D. (2000). Finite Mixture Models. J. Wiley, New York. § 关联分析 (Association Analysis) - 7. Apriori: Rakesh Agrawal and Ramakrishnan Srikant. Fast Algorithms for Mining Association Rules. In VLDB '94. - 8. FP-Tree: Han, J., Pei, J., and Yin, Y. 2000. Mining frequent patterns without candidate generation. In SIGMOD '00. C4.5 CART Naïve Bayes kNN SVM EM Apriori FP-Tree Page 8 18种通过审核的候选算法 § 链接挖掘 (Link Mining) - 9. PageRank: Brin, S. and Page, L. 1998. The anatomy of a large-scale hypertextual Web search engine. In WWW-7, 1998. - 10. HITS: Kleinberg, J. M. 1998. Authoritative sources in a hyperlinked environment. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998. § 聚类 (Clustering) - 11. K-Means: MacQueen, J. B., Some methods for classification and analysis of multivariate observations, in Proc. 5th Berkeley Symp. Mathematical Statistics and Probability, 1967. - 12. BIRCH Zhang, T., Ramakrishnan, R., and Livny, M. 1996. BIRCH: an efficient data clustering method for very large databases. In SIGMOD '96. § 袋装与推进 (Bagging and Boosting) - 13. AdaBoost: Freund, Y. and Schapire, R. E. 1997. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci. 55, 1 (Aug. 1997), 119-139. PageRank HITS K-Means BIRCH AdaBoost Page 9 18种通过审核的候选算法 § 序列模式 (Sequential Patterns) - 14. GSP: Srikant, R. and Agrawal, R. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements. In Proceedings of the 5th International Conference on Extending Database Technology, 1996. - 15. PrefixSpan: J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal and M-C. Hsu. PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth. In ICDE '01. § 集成挖掘 (Integrated Mining) - 16. CBA: Liu, B., Hsu, W. and Ma, Y. M. Integrating classification and association rule mining. KDD-98. § 粗糙集 (Rough Sets) - 17. Finding reduct: Zdzislaw Pawlak, Rough Sets: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Norwell, MA, 1992 § 图挖掘 (Graph Mining) - 18. gSpan: Yan, X. and Han, J. 2002. gSpan: Graph-Based Substructure Pattern Mining. In ICDM '02. GSP PrefixSpan CBA gSpan Finding reduct Page 10 大纲 1. 1. 三步鉴定流程三步鉴定流程 2. 182. 18种通过审核的候选算法种通过审核的候选算法 33.. 算法陈述算法陈述 44.. 数据挖掘数据挖掘1100大算法：一览大算法：一览 55.. 开放式讨论开放式讨论 Page 11 算法陈述 § 每种算法的陈述包括以下内容： - a) 算法的概要描述 - b) 算法的应用 - c) 该算法目前和未来的研究方向 § 每位陈述人会介绍自己 - 对该算法有深入的研究 - 尽量使用算法原作者的幻灯片，可以适当修改 - 提出自己对该算法的观点和意见 Page 12 大纲 1. 1. 三步鉴定流程三步鉴定流程 2. 182. 18种通过审核的候选算法种通过审核的候选算法 33.. 算法陈述算法陈述 44.. 数据挖掘数据挖掘1100大算法：一览大算法：一览 55.. 开放式讨论开放式讨论 Page 13 数据挖掘十大算法：一览表 分类 分类 分类 集装与推进 链接挖掘 统计学习 关联分析 统计学习 聚类 分类 挖掘主题 L.Breiman Hand, D.J Hastie, T Freund, Y. Brin, S. McLachlan, G Rakesh Agrawal Vapnik, V.N MacQueen, J.B Quinlan, J.R 作者 1984 2001 1996 1997 1998 2000 1994 1995 1967 1993 发表时间 Dan Steinberg34CART10 Qiang Yang45Naïve Bayes9 Vipin Kumar45kNN8 Zhi-Hua Zhou45AdaBoost7 Christos Faloutsos46PageRank6 Joydeep Ghosh48EM5 Christos Faloutsos52Apriori4 Qiang Yang58SVM3 Joydeep Ghosh60K-Means2 Hiroshi Motoda61C4.51 讲解人得票数算法排名 Page 14 大纲 1. 1. 三步鉴定流程三步鉴定流程 2. 182. 18种通过审核的候选算法种通过审核的候选算法 33.. 算法陈述算法陈述 44.. 数据挖掘数据挖掘1100大算法：一览大算法：一览 55.. 开放式讨论开放式讨论 Page 15 开放式讨论 § 由算法的原作者和陈述人来编写调查表 § 如何更好地使用这10大算法？ § 是否需要为这10大算法专门编写一本书？ - IDMer注：该书已出版，参见右图封面。书名为 《The Top Ten Algorithms in Data Mining》， 编著者为XinDong Wu和Vipin Kumar § 针对这10大算法的任何问题展开讨论 Page 16 ICDM 2006会议的算法投票结果 § 共有145人参加了ICDM 2006 Panel (会议的专题讨论)，并对18种候选算 法进行投票 § 开放式投票选出的前3大算法 (Top 3 Algorithms) - C4.5: 52票 - SVM: 50票 - Apriori: 33票 § 10大算法 - ICDM 2006 Panel与会者选出了前10大算法，结果和前面的“数据挖掘10大算法” 相同。 Page 17 THE END Page 18 数据挖掘10大算法(思维导图) Page 19 数据挖掘10大算法(思维导图)－C4.5