趣味数据挖掘系列11：十大算法展辉煌历史，十大问题引锦绣前程

摘要：这篇突出资料性，先说三十年的十大算法，看数据挖掘的史上辉煌，再叙七年前提出的十大问题，证数据挖掘专家不是砖家；

迟到的续集与个性化活动之不确定性 上篇博文（趣味数据挖之十）末尾许下一愿--介绍数据挖掘十大算法。在博友们友好的催促之下，现在才姗姗来迟，歉疚有加。凡人写博是十分个性化的业余活动（非平凡人物可能会雇佣团队写博）；在科技的春种秋收季节，人们总会遇到若干突然冒出来的任务，而在次要活动中，最先停下来为正事让时间的，就是读博写博。 言归正传，这篇突出资料性，先说三十年的十大算法，看数据挖掘的史上辉煌，再叙七年前提出的十大问题，证数据挖掘专家不是砖家；下一篇用实例解释的数据挖掘哲学思想，作一个有趣味的系列小结。 数据挖掘在而立之年论功行赏：评选十大算法 数据挖掘大致萌芽于上世纪70年代，例如，在先期探索基础上，1978年，Ross J. Quinlan提出判定树方法ID3，后来发展为成为 C4.5 算法，参见（趣味数据挖掘之六 ）。几年前，数据挖掘学科进入了“而立”之年，向“不惑”推进， 那时节，研究对象天天拓广，研究团队日益繁荣，老人要评功，新人要成长。有人顺天应时，提出动议：回顾成败、论功行赏、反思问题、展望未来。此议一呼，举“界”百应。

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

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

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

(2)验证阶段：验证软件效率，查被引用频次，要求在2006.10月底，在Google Scholar上至少查出被引用50次以上。这里选用Google Scholar，而不是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.（裴健）, and Yin, Y. 2000. Mining frequent patterns without candidate generation. In SIGMOD 00. Link Mining。挖掘关联规则的快速算法； #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. 网页超链诱导主题搜索； #12. BIRCH Zhang, T., Ramakrishnan, R., and Livny, M. 1996. BIRCH: an efficient data clustering method for very large databases. In SIGMOD 96.聚类算法； #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.时间序列模式挖掘； #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 ，粗糙集理论； #18. gSpan: Yan, X. and Han, J（韩家炜）. 2002. gSpan: Graph-Based Substructure Pattern，图数据挖掘；

(3) 投票阶段：为保证广泛的代表性和公正性，投票委员会在提名委员会基础上做了扩大，增加了 KDD-06, ICDM 06, SDM 06 三个国际会议的程序委员会委员。投票前，由推选的第三方专家介绍算法及其学术影响（被引用情况等），研究应用现状以及前景，充分酝酿基础上，投票产生了Top 10. 数据挖掘 Top 10 十大算法按得票数排序如下： #1: C4.5 (61 票), （判定树或决策树，分类算法 ，参见趣味数据挖掘之六；） #2: K-Means (60票),（K-平均聚类算法，参见趣味数据挖掘之八）； #3: SVM (58票),（分类算法）（支持向量机，分类算法）； #4: Apriori (52票), （关联规则挖掘算法，参见趣味数据挖掘之三）； #5: EM (48票),（期望最大化算法，聚类与参数估计）； #6: PageRank (46票), （著名的google页面评价算法）； #7: AdaBoost (45票), （积弱为强的分类算法）； #7: kNN (45票),（以近邻为楷模的分类方法）； #7: Naive Bayes (45票),（基于对象原生态分布的分类算法，比较忠实于数据的原汁原味，不需或少需先验知识）； #10: CART (34票), （二分递归分割的的判定树分类方法）；

其中研究分类的6个，聚类的2个，关联的一个，网页排序（本质上是分类）的一个。似有“分类独大”的现象，可见分类问题被研究得较彻底，问题的油水似被榨干，如果在分类方面还有遗留问题，可能是比较难啃的骨头问题，要等待不怕困难的、有缘的年轻人去发现、去创新了。

数据挖掘向何处去--- 7年前的10大问题. 为表达远见卓识，专家们常自问自答这样的问题：本领域向何处去？下一代关键技术是什么？本领域未来十年的研究什么？ 试玉要烧三日满，辨才须待七年期；是真知灼见的专家还是忽悠人的“砖家”？七年之后看。 在数据挖掘的顶级国际会议ICDM 2005上，一批专家提出了10个挑战性问题，如今刚满七年，让我们来看看这十大挑战性问题，看看今天的研究状态： 问题1 数据挖掘的统一理论。十年前，专家看到当时的数据挖掘中急用先研的短期行为较多，为单个问题研究技术，无统一的理论 ，目光不远大, 至今，比较完整的数据挖掘的同一理论还在探索中； 问题2 规模伸缩性、高维和高速问题。十年前的数据挖掘技术，在维度增加，数据规模增大时，所需资源（时间、空间和CPU）指数级地增加，在数据流分析、网络攻防、传感器网络应用中成为瓶颈；如今问题仍然在； 问题3 时间序列的高效率处理+ 高效分类聚类和预测,如今，在短长期预报,高精度处理方面问题仍然存在； 问题4 复杂数据总挖掘复杂知识，如图数据挖掘等表现突出，如今，在亚复杂系统干预规则的挖掘中也有需求； 问题5 网络挖掘，社会网络，邮件，网页，网络反恐，海量数据挖掘等；问题仍然存在； 问题6 分布式挖掘和多代理挖掘，如大型网络游戏，网络军事对抗等，需求日益增加； 问题7 生物数据挖掘 艾滋病疫苗相关、DNA相关的数据挖掘，方兴未艾； 问题8 数据挖掘自身的方法论研究， 尚待突破； 问题9 数据挖掘与信息安全和隐私保护；成为目前关注热点； 问题10. 特色数据的挖掘：包括高价值数据（如重症监护室数据），偏斜数据（抽样偏斜失真），不平衡数据（有用的只占很小比例）。  专家毕竟是专家 如今，七年过去了，人们欣慰地看到，专家不是砖家，他们提出的问题指导着这些年的研究方向。七年中出现了若干新事物，引出了若干新问题， 如物联网相关的数据挖掘， 云计算相关的数据挖掘，但上述十大问题还在被研究被解决，推动着数据挖掘的理论、系统和应用。 继承、发展和创新 今天我们复习数据挖掘十大算法，知道什么是好成果，是为了继承；复习十大问题，知道未来将在何处出好成果，是为了发展； 创新始终是研究的核心，什么是创新？创新就是于无中生有；什么是掀起潮流？掀起潮流就是于学术沉闷中兴风作浪；在学术的激流中能掀起一个小小的漩涡，也比总是跟潮更有劲，更有前途。