博文
十大算法展辉煌历史，十大问题引锦绣前程---趣味数据挖掘之十一
精选
|||
十大算法展现辉煌历史，十大问题引领锦绣前程---趣味数据挖掘之十一(唐常杰）
迟到的续集与个性化活动之不确定性 上篇博文（趣味数据挖之十）末尾许下一愿--介绍数据挖掘十大算法。在博友们友好的催促之下，现在才姗姗来迟，歉疚有加。凡人写博是十分个性化的业余活动（非平凡人物可能会雇佣团队写博）；在科技的春种秋收季节，人们总会遇到若干突然冒出来的任务，而在次要活动中，最先停下来为正事让时间的，就是读博写博。
言归正传，这篇突出资料性，先说三十年的十大算法，看数据挖掘的史上辉煌，再叙七年前提出的十大问题，证数据挖掘专家不是砖家；下一篇用实例解释的数据挖掘哲学思想，作一个有趣味的系列小结。
言归正传，这篇突出资料性，先说三十年的十大算法，看数据挖掘的史上辉煌，再叙七年前提出的十大问题，证数据挖掘专家不是砖家；下一篇用实例解释的数据挖掘哲学思想，作一个有趣味的系列小结。
数据挖掘在而立之年论功行赏：评选十大算法 数据挖掘大致萌芽于上世纪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. 网页超链诱导主题搜索；
严密的三阶段评选程序： 组织者提出了三阶段评选程序：
(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票),（期望最大化算法，聚类与参数估计）；
#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票), （二分递归分割的的判定树分类方法）；
#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. 特色数据的挖掘：包括高价值数据（如重症监护室数据），偏斜数据（抽样偏斜失真），不平衡数据（有用的只占很小比例）。
试玉要烧三日满，辨才须待七年期；是真知灼见的专家还是忽悠人的“砖家”？七年之后看。
在数据挖掘的顶级国际会议ICDM 2005上，一批专家提出了10个挑战性问题，如今刚满七年，让我们来看看这十大挑战性问题，看看今天的研究状态：
问题1 数据挖掘的统一理论。十年前，专家看到当时的数据挖掘中急用先研的短期行为较多，为单个问题研究技术，无统一的理论 ，目光不远大, 至今，比较完整的数据挖掘的同一理论还在探索中；
问题2 规模伸缩性、高维和高速问题。十年前的数据挖掘技术，在维度增加，数据规模增大时，所需资源（时间、空间和CPU）指数级地增加，在数据流分析、网络攻防、传感器网络应用中成为瓶颈；如今问题仍然在；
问题3 时间序列的高效率处理+ 高效分类聚类和预测,如今，在短长期预报,高精度处理方面问题仍然存在；
问题4 复杂数据总挖掘复杂知识，如图数据挖掘等表现突出，如今，在亚复杂系统干预规则的挖掘中也有需求；
问题5 网络挖掘，社会网络，邮件，网页，网络反恐，海量数据挖掘等；问题仍然存在；
问题6 分布式挖掘和多代理挖掘，如大型网络游戏，网络军事对抗等，需求日益增加；
问题7 生物数据挖掘 艾滋病疫苗相关、DNA相关的数据挖掘，方兴未艾；
问题8 数据挖掘自身的方法论研究， 尚待突破；
问题9 数据挖掘与信息安全和隐私保护；成为目前关注热点；
问题10. 特色数据的挖掘：包括高价值数据（如重症监护室数据），偏斜数据（抽样偏斜失真），不平衡数据（有用的只占很小比例）。
专家毕竟是专家 如今，七年过去了，人们欣慰地看到，专家不是砖家，他们提出的问题指导着这些年的研究方向。七年中出现了若干新事物，引出了若干新问题， 如物联网相关的数据挖掘， 云计算相关的数据挖掘，但上述十大问题还在被研究被解决，推动着数据挖掘的理论、系统和应用。
继承、发展和创新 今天我们复习数据挖掘十大算法，知道什么是好成果，是为了继承；复习十大问题，知道未来将在何处出好成果，是为了发展；
创新始终是研究的核心，什么是创新？创新就是于无中生有；什么是掀起潮流？掀起潮流就是于学术沉闷中兴风作浪；在学术的激流中能掀起一个小小的漩涡，也比总是跟潮更有劲，更有前途。
(下篇博文 拟通过实例，在哲学层次上比较数据挖掘和专家系统，为此系列做一个小结) 相关博文
3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之三
4 巧挖科学博客之均击量公式，兼谈干预规则----趣味数据挖掘之四
5 听妈妈讲 过去的故事，分房与分类-----趣味数据挖掘之五
8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八
9 灯谜、外星殖民、愚公移山和进化计算---趣味数据挖掘之九
10 达尔文、孟德尔与老愚公会盟：基因表达式编程--趣味数据挖之十
11 十大算法展现辉煌，十大问题引领锦绣---趣味数据挖掘之十一
假日聚会，戏说云物人海 --漫谈大数据
https://blog.sciencenet.cn/blog-287179-547898.html
上一篇：达尔文、孟德尔与老愚公的会盟：基因表达式编程--趣味数据挖之十
下一篇：沿着江山起起伏伏温柔的曲线---清明看花
76 李学宽 钟炳 江贺 彭思龙 金小伟 陈安 李宇斌 余昕 王铮 荣元华 黄晓磊 柳海涛 杨正瓴 武夷山 汤奔阳 谢鑫 龚文引 化柏林 单博炜 刘钢 郭崇慧 马磊 晏燕华 毛宁 元云芬 章迅来 郭桅 赵继慧 陈应泉 侯德鑫 苏德辰 陈儒军 边一 熊伟 周春雷 李天成 刘全慧 李本先 张钧波 占礼葵 黄顺谋 马绍忠 曹建军 赵星 曹聪 蒋继平 杨晓慧 刘洋 李欣海 白图格吉扎布 庄世宇 陈斌 章成志 井然哲 杨秀海 支丽平 魏玉保 高维明 李征 徐建良 许洪光 邓昌义 yunmu yewen lihx1798 vldb zdlh yangwencao crossludo wangguofengw chenwendu89 zhousiweiz fishman936 wavelet05 dulizhi95 xqhuang
