【趣味】数据挖掘(3)—Apriori算法-论文引用与数据血统论

本文先通俗地介绍快速挖掘关联规则的Apriori算法,然后介绍发表这一算法的论文(它被引用了11480+次),最后关注此文的实际影响 与 传统影响因子的差距。

有言在先,趣味数据挖掘和趣味数学一样,有些段落比较细致,此文虽只要中学数学知识,但须静心把它当回事,或许要在草稿上写画,才读得顺畅。 1 朴素挖掘方法中的组合数呈指数增长 上文中,关联规则朴素挖掘法的主要脉络是 “组合对象--选举-唱票-计票”。人们说组合对象数量很大,究竟大到什么程度?   从m个对象中选k个对象的组合数记为C(m,k), 中学数学中, C(m,k)=m!/k!(m-k)!, 下面简单估计它的增大趋势: C(m,k) 是二项式(1+x)m 展开后第k+1项系数,令x=1,容易得出    ∑C(m,k)= (1+1)m= 2m 所以,二项式展开后的m+1个系数的平均值为2m /(m+1) , 其分布称为二项分布,中学数学给出前几个是(1,1)( 1,2,1) (1,3,3,1) (1,4,6,4,1),…大致规律是两头小,中间大,还可用杨辉三角形计算。 中间的系数远大于平均值 2m /(m+1) . 所以说,组合数是大致随m的指数增长的。 于是,朴素挖掘方法耗时也随m的指数增长的,当m=105,(一个超市中的物品数量),2m /(m+1) 可是天文数字! 为解决朴素挖掘方法中组合爆炸问题,R. Agrawal和 R.Srikant与1994年提出了Aprior算法。

2 Aprior性质 与 数据血统论:高频集的子集一定是高频集 Aprior,形容词,发音 ['ei prai 'o rai], 其译意包括:演绎的、先天的、先验的、推测的、演绎的、事前的,等等。   笔者体会,Aprior算法命名是采用“先天的”这一层意思(曾与R.Agrawal同登黄山,但兴奋中忘了问这个问题)。 Aprior性质说:高频集的子集一定是高频集,这相当于“龙生龙、凤生凤”,注意,它并未断言“老鼠生儿打地洞”,所以,属于半血统论。   社会生活中,血统论带来不公平,22个世纪前,大泽乡起义的带头人陈胜,代表老百姓的发出了一声呐喊:“王侯将相宁有种乎?”,它穿越时空、而今还振聋发聩(典出《史记·陈涉世家》)。   数据空间中的血统论带来了数据的不公平,正好可用于数据剪枝,尽早排除哪些不必要扫描的对象,从而提高计算速度。   这个数据血统论 有下列两层意思: 2.1,从高频集看其子集   用乒乓球竞赛作比喻,设在10次竞赛中有5次以上夺冠的选手的称为高频选手,(相当于支持度阈值=5/10); Aprior性质说:如果双打组合 {A, B} 是高频的,则其子集{A}和{B}都是高频的。   为什么?因已知A, B联手5次夺冠,A还可能和其他选手联手或单打而夺冠,所以A的夺冠总次数不低于5。 Aprior性质对任意k项集都成立,双打只说了k=2的特例;人们都承认它,有公理体系之洁癖的数学美爱好者,也可在一番定义之后去证明它。 2.2 Aprior构造性命题:(k+1)项的高频集一定可以用其两个k项的高频子集 连接而成   例如,上篇博文中 k=3时, {烤鸭,面饼,面酱} 是高频集,用 JOIN 表示数据库中的连接运算,则这个三项集可用两个双项(高频)集 连接而成,如下所示: {烤鸭,面饼} JOIN {面饼,面酱} == {烤鸭,面饼,面酱} 要点是,两个记录中的“面饼”作粘连项,用数据库的行话,是两个只有一行的表(关系)做等值连接。   一般地描述,(k+1)项的高频集有(k+1)个k项子集(且都是高频的),容易找到其中的两个,使他们有K-1项相同,连接即可。 3 迅速排除非高频集的法宝  上述Aprior构造性命题的逆否命题是“不能用两个k项高频集连接而成的k+1项集,一定不是高频集”,使得我们能用构造性命题把高频候选集 迭代地、循序渐进地、一个不漏地 构造出来,因为凡是构造不出来,都要排除,不必操心。  这是我们迅速排除非高频集、缩小候选空间的法宝。大致思路的估计如下:   摸着石头过河 试探地确定支持度阈值。 假定超市有10万种商品,想找出同时被购买得比较多的K项集合,K=1,2,..,10。什么是“比较多”?怎样选择支持度阈值T? T=0.01; 满足此阈值的项多,挖掘系统计算很长时间才算完,可能经济意义小; T=0.95 ,可能太大,类似于元宵节大部分家庭买汤圆,平时满足此阈值的商品少,甚至为空集;挖掘系统很快(几秒钟-几分钟)就算完了。  选T=20%,即有20%的顾客都买的货物,(这类商品真实存在,例如食品、餐巾纸,卫生纸等等)。比较中庸,有意义,中等时间消耗。 4 Aprior原理作迅速剪枝  下面,为了找到量的感觉,将用常识与合理假定,给出一些具体的数据。 4.1 先找出高频单项集 设 挖掘系统扫描数据库得知,支持度不小于20% 单项集 只有 100项。 这一次从10万项中剪掉了99.9%。 4.2 只有高频单项集 才有资格 组合成高频双项集的候选集(根据构造性命题) 这个消息太好了,按照Aprior原理,不需扫描 10万种商品,而只需考虑100项商品组成的双项集,他们一共有100(100-1)/2 =4950项,如果采用朴素的笨方法,从10万项产生双项集,会有10^5 *10^5-1)/2 > 10^9项! 这一次剪掉的不少于99.9999999% 当然,没被剪枝的,还需要扫描一次流水账,核实其高频性 设 4950个双项集中,支持度不小于20%的只有 10项,(双项高频集比单项集要难一些,因为项与项需要“缘分”才能被同时购买),则4940项及其超集都被剪掉了,这一次又剪掉4940/4950=99.7% 4.3 只有高频双项集 才有资格连接成 高频三项集的候选集 10个双项集,彼此连接,产生的三项候选集超集不会超过10*9/2=45项,还不太多,核实其高频性也比较容易了。 以此类推…. 总的思想,(a)知道了某项不是高频集,就把它排出;(b)因为它的血统不够高贵,其超集合的血统一定不高贵,也被排除;(c)在理想参数下,每次可能排除绝大部分。 这就是我们用来剪枝,加快的法宝。 5 一举成名的高被引用论文之特征 Aprior算法是IBM Almaden研究中心的 R. Agrawal和 R. Srikant在1994年提出的,发表在数据库界的顶级国际会议VLDB 94上,在Google 上一搜即得,有兴趣者不妨实查一下,它被引用了11480+ 次,也可在本文附件中下载。   这是顶级科学家在顶级国际会议上的一个方向的开创性论文,因为紧凑,原始文献比教科书中相关章节稍难读,更不像科普博文这样浅显。笔者在教学中,常推荐给新入门者,因为它有下列特色: (1) 它于无中添有,高频数据的先天性质(Aprio性质)天天摆在光天化日下,被普通人熟视无睹、擦肩而过,人群中,有一个人-- R. Agrawal,就像王菲在《传奇》中唱的,多看了它几眼,捅破了这层窗户纸,在人类知识上无中添有(这就是创新),窗户纸有个特点,未破之前,百思不得其解,捅破之后,一目了然,大众认可; (2) 它也兴风作浪— 独特的算法,并不复杂,掀起了一阵关联规则研究的潮流。 (3) 它像破冰船,破开了关联规则研究方向的拦路坚冰;它像推土机,推开了露天煤矿的表土,又不独贪(矿场太大,也无法独贪),留给后来者的,不是榨干了油水的骨头,所以才有大批后来者跟踪、改进,引出了后来的成百上千篇的改进型论文,才有上万次的引用。 (4) 它很完整,有背景,有模型,有形式化描述,有理论、有算法,这也是数据挖掘界学术论文的标准写法,初学者可在这里学思想、学写法,学实验; (5) 它有大规模实验验证,实验数据含105个记录,这在当时已经是的“海量”了,当年用的计算机是IBM RS6000,主频 33M,也许在1994年是不错的设备,今天看来,并不高贵。在大规模的数据集上测试算法的规模伸缩性,是如今数据挖掘论文攀登顶级会议的必要条件。 6 十大算法的Top4 在2006年,国际数据挖掘界推选十大数据挖掘算法,经过严密的程序,几个国际会议程序委员会( KDD-06, ICDM '06, SDM '06 ,ACM KDD Innovation Award and IEEE,ICDM )的提名 ---投票---辩论,最后Aprilori 算法名列十大算法的第四名。(关于十大算法,另择机讨论)。 7 不公平的影响因子

VLDB顶级国际会议,一年只有几十篇论文的空间,进入VLDB似乎比进入奥运会还要难,但会议论文既不上EI,也不上SCI。ISI不计算其影响因子,或ISI影响因子为0。  根据DBLP和Google的论文统计,从1994-2003年,SIGMOD文章平均被引用70次,VLDB文章平均被引用50次。简单抽样表明,引用高峰在前两年,各占10年中引用数的20%以上,如果这个抽样有一般性,则 实际 影响因子可能不小于 10 ,甚至不小于14。  而论文[1]被引用11480+ 次,是特例中的特例,可能进入计算机科学论文被引用次数的高端了。 8 假如R.Agrawal在中国

目前,我国若干学校和科研单位单位并不承认国际会议论文。可能是因为制定科研成果认定政策的官员,多非计算机专业人士,他们只认SCI-EI,而不认这些顶级会议。(相关问题,或许另择机讨论)。   所以,如果R. Agrawal,和 R. Srikan在中国,如果他们鼓起勇气,用那篇开创性的论文[1]作为申请博士学位或作为提职称的主打材料,可能会像刀郎唱的,受到“冲动的惩罚”。 最近有了好消息,中国计算机学会(CCF)公布了一个“推荐国际学术会议”清单,其中包括数据库界的四个顶级会议:SIGMOD,VLDB,ICDE 和 SIGKDD,也许这个推荐清单还不足以说服有关官员,但抗争者至少有了一点批判的武器,不再是手无寸铁。

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2014-07-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

解读Etsy如何利用热力学帮你找到适合“极客”的东西

Etsy的用户喜爱这个市集,货品丰富且数量繁多。不过对于那些自己也不清楚要找什么的用户来说,东西太多太杂反而更让人困扰。7月份,我们更新了UI界面,将搜索的热门...

1808
来自专栏Python中文社区

摩根纽约总部量化女神手把手教你学Python机器学习与量化交易

“量化投资”是指投资者使用数理分析、计算机编程技术、金融工程建模等方式,通过对样本数据进行集中比对处理,找到数据之间的关系,制定量化策略,并使用编写的软件程序来...

1000
来自专栏AI研习社

入门必读的机器学习名词解释,你都懂了吗?

train? valid? or test? 机器学习最明显的一个特点是需要大量的数据。特别对监督学习来说,就是需要大量的带标签数据(labeled dat...

3324
来自专栏大数据文摘

用神经网络续写《权力的游戏》,这个脑洞有点大(附完整小说下载)

1214
来自专栏SIGAI学习与实践平台

理解计算 从根号2到AlphaGo 第3季神经网络的数学模型

1910年,英国哲学家伯特兰·罗素(Bertrand Russell )和其老师怀特海(Alfred North Whitehead)合著的《数学原理》一书问世...

1345
来自专栏AI科技评论

干货 | 不能更通俗易懂的机器学习名词解释

train? valid? or test? 机器学习最明显的一个特点是需要大量的数据。特别对监督学习来说,就是需要大量的带标签数据(labeled dat...

3337
来自专栏大数据挖掘DT机器学习

自己动手写推荐系统

在下面介绍的做推荐系统的流程中,我只是想给大家介绍个普通的推荐系统该怎么做,所以很多地方都有偷懒,还请大家见谅。而且由于我不是做的在线的推荐系统,而是属于隔天...

3428
来自专栏数说工作室

训练集是题库,测试集就是高考!| 不能更简单通俗的机器学习名词解释

1. train? valid? or test? 机器学习最明显的一个特点是需要大量的数据。特别对监督学习来说,就是需要大量的带标签数据(labeled da...

3928
来自专栏量子位

德国AI“算个球”:西班牙是冠军,只要别让德国进八强(严谨推理)

可能是由于人类(包括球王)预测不靠谱,前几届世界杯预测战况和冠军的任务,常常交给动物完成。

792
来自专栏大数据挖掘DT机器学习

【趣味】数据挖掘(6)——借水浒传故事,释决策树思路

决策树 (又称判定树,Decision Tree)是硕、博士生数据挖掘课程要点和难点,教学实践表明,这一章需要数学基础知识多,难得有趣。明知是难点,偏向难...

3305

扫描关注云+社区