设为首页收藏本站
开启辅助访问 切换到宽版

科学网

 找回密码
  注册
科学网 › 标签 › 关联规则

tag 标签: 关联规则

相关帖子

 版块 作者 回复/查看 最后发表

没有相关内容

相关日志

3月笔记
zh0406 2016-3-31 21:24
关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联，并以规则的形式表达出来。一个样本称为“事务”，每个事务由多个属性来确定，属性即为项，多个项组成的集合称为“项集”，其实每个事务就是一个项集。关联规则的表示为 X ⇒Y s,c X和Y是项集，X称为规则前项，Y称为规则后项，支持度s是数据库中包含X ∪Y的事务占全部事务的百分比：support( X ⇒Y )=P（ X ∪Y ）；置信度c是包含 X ∪Y的事务数与包含X的事务数的比值：confidence（ X ⇒Y ）=P（Y ∣X ）。 在关联规则的可视化图形中，应该体现五个参数：规则的前件、规则的后件、两者的关系、规则的支持度和规则的置信度。 关联规则处理的变量可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理。 关联规则挖掘过程主要包含两个阶段： 第一阶段先从数据集中找出所有的频繁项集，他们的支持度均大于等于最小支持度阈值min_sup； 第二阶段由这些频繁项集产生关联规则，计算它们的置信度，然后保留那些置信度大于等于最小置信度阈值min_conf的关联规则。 关联规则的应用： 最有名的是啤酒与尿布的故事；可以类推到购买其他商品的关联规则的挖掘； 应用于金融行业，可以预测银行客户的需求，便于营销； 应用于电子商务站点，解决其交叉销售问题； 可以设置用户购买商品的推荐，以及客户感兴趣的信息推送等； 在学校招生中的应用，对招生工作进行评估以及对学生专业选择进行指导建议等；在学生成绩中的应用，找出学生各科考试成绩之间的关系，对教师提出相关学科的侧重要求等； 在课堂评价中的应用，可以客观和有效的对教师的教学情况进行评价； 在股票分析中的应用，有利于投资者了解各种股票的走势及股票之间的关系，进一步分析上市公司的政策和方法，从而作出正确的投资决策等； 在电信运营商中的应用，挖掘用户的行为特征和需求，间接的反映市场动态的有用信息，用以指导运营商的业务运营和辅助业务提供商的决策制定等； 在行业供应链风险管理中的应用，考察期信用风险传染在不同行业供应链中呈现的显著性差异； 在医疗数据挖掘中的应用，考察某种病症与其他健康指标间的关联规则，可以进行疾病诊断、治疗、预测等诸多方面的研究； 在主要经济指标中的应用，可以是政府对高技术产业未来发展趋势的掌握，使政府部门制定产业规划、投资决策、优化产业结构等；
5 次阅读|0 个评论
关联规则综述
yewenjing 2014-1-2 09:32
铁治欣,陈奇,俞瑞钊. 关联规则采掘综述 . 计算机应用研究,2000,(1) 主要研究方向 算法 多循环方式的采掘算法 Agrawal: AIS,Apriori,AprioriTid,AprioriHybird; Park: DHP; Savasere: PARTITION; Toivonen: Sampling 增量式更新算法 IUA,PIUA 并行发现算法 Agrawal: CD,CaD，DD; Chueng: DMA,FDM 采掘一般或多层关联规则 Han: ML_T2L1,ML_T1LA,ML_TML1,ML_T2LA R.Srikant: Cumulate,Stratify,Estimate,Estmerge 采掘多值属性关联规则 多值属性又可分为数量属性和类别属性 采掘基于约束的关联规则 MUltipleJoins,Reorder,Direct 其他方向 发现关联规则的语言，采掘长模式和密集数据集，采掘相关性和因果关系，发现比例规则，发现日历和周期关联规则，采掘多维关联规则 刘君强 , 孙晓莹 , 潘云鹤 ,. 关联规则挖掘技术研究的新进展 . 计算机科学 ,2004,(1) 有关频集和关联规则挖掘的研究大致涉及三个方面： 1、经典频集挖掘的高性能算法研究，包括对Apriori的改进以及探索新的挖掘方法； 2、拓展频集的概念，提出相应的挖掘算法； 3、拓展关联规则概念及应用范围，包括规则的价值评估，新的关联规则类型 方向 算法 新进展 完全频集与关联规则 Apriori以及对Apriori的改进 TreeProjection,，FP-growth，伺机挖掘思想 闭合频集与无冗余关联规则 Pasquier：close，A-close 基于FP-growth的closet，Zaki：CHARM，Liu：OpportuneProject 最大频繁模式挖掘 Liu：Pincer-Search DepthProject（深度优先挖掘最大频繁模式），Burdick：MAFIA 多维多层关联规则及其他 多维，多层，基于约束，并行，关联规则与相关性，多支持度规则挖掘 颜雪松,蔡之华,蒋良孝,贺毅. 关联规则挖掘综述 . 计算机应用研究,2002,(11) BFS宽度优先搜索，所有（k-1）维项目集的支持度是在计算k维项目集支持度之前定义的。 DFS深度优先搜索，随着定义的树形结构下降的。
个人分类: 数据挖掘|2 次阅读|0 个评论
一篇 "它引" 上万的大牛论文 与 数据血统论-- 趣味数据挖掘之三
热度 21 tangchangjie 2011-12-1 08:18
一篇 "它引" 上万的大牛论文 与 数据血统论-- 趣味数据挖掘之三(唐常杰） 　 本文先通俗地介绍快速挖掘关联规则的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 = 2 m 所以，二项式展开后的m+1个系数的平均值为2 m /(m+1) ， 其分布称为二项分布，中学数学给出前几个是（1,1）（ 1,2,1） （1,3,3,1） （1,4,6,4,1），…大致规律是两头小,中间大,还可用杨辉三角形计算。 中间的系数远大于平均值 2 m /（m+1） . 所以说，组合数是大致随m的指数增长的。 于是，朴素挖掘方法耗时也随m的指数增长的，当m=10 5 ，(一个超市中的物品数量)，2 m /（m+1） 可是天文数字！ 为解决朴素挖掘方法中组合爆炸问题 ，R. Agrawal和 R.Srikant与1994年提出了Aprior算法。 　　 2 Aprior性质 与 数据血统论：高频集的子集一定是高频集 　　Aprior，形容词，发音 ， 其译意包括：演绎的、先天的、先验的、推测的、演绎的、事前的，等等。 　　笔者体会，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） 它有大规模实验验证 ，实验数据含10 5 个记录，这在当时已经是的“海量”了，当年用的计算机是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。 　　而论文 被引用11480 + 次，是特例中的特例，可能进入计算机科学论文被引用次数的高端了。 　　 　　 8 假如R.Agrawal在中国 目前，我国若干学校和科研单位单位并不承认国际会议论文。可能是因为制定科研成果认定政策的官员，多非计算机专业人士，他们只认SCI-EI，而不认这些顶级会议。（相关问题，或许另择机讨论）。 　　所以，如果R. Agrawal,和 R. Srikan在中国，如果他们鼓起勇气，用那篇开创性的论文 作为申请博士学位或作为提职称的主打材料，可能会像刀郎唱的，受到“冲动的惩罚”。 最近有了好消息，中国计算机学会（CCF）公布了一个“推荐国际学术会议”清单，其中包括数据库界的四个顶级会议：SIGMOD，VLDB，ICDE 和 SIGKDD，也许这个推荐清单还不足以说服有关官员，但抗争者至少有了一点批判的武器，不再是手无寸铁。 参考文献 R Agrawal, and R Srikant .”Fast Algorithms for Mining Association Rules in Large Databases”, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994. 点击这里下载 R Agrawal关于关联规则的开创性论文.pdf 相关博文 1 “被打”和“北大” 的关联 --- 趣味数据挖掘系列之 一 2 烤鸭、面饼和甜 面酱之朴素关联 --- 趣味数据挖掘系列之二 3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之 三 4 巧挖科学博客之均击量公式，兼谈干预规则 ---- 趣味数据挖掘之四 5 听妈妈讲 过去的故事，分房与分类 ----- 趣味数据挖掘之五 6 借水浒传故事，释决策树思路--- 趣味数据挖掘之六 7 宴会上的聚类 — 趣味数据挖掘之七 8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八 9 灯谜、外星殖民、愚公移山和进化计算 --- 趣味数据挖掘之九 10 达尔文、孟德尔与老愚公会盟：基因表达式编程--趣味数据挖之十 11 十大算法展辉煌，十大问题现锦绣---趣味数据挖掘之十一 12 数据挖掘中的趣味哲学 --- 趣味数据挖掘之十二 其它系列博文的入口 唐常杰博客主页 科学博客主页
个人分类: 科普札记|23928 次阅读|42 个评论
烤鸭、面饼和甜面酱之朴素关联 ---趣味数据挖掘之二
热度 21 tangchangjie 2011-11-22 15:07
烤鸭、面饼和甜面酱之朴素关联 ---趣味数据挖掘之二(唐常杰） 上文借有趣的实例介绍了关联规则的三度 （支持度、置信度，兴趣度）概念。为答博友，此文从原讲课PPT中，取一些素材，来解释关联规则的挖掘思路和应用方法。 1 通俗性与深入性的纠结 下笔（击键）之前，为通俗性和理论性的冲突，颇纠结了一番，通俗科普博文，是否需要完全避开公式和推导？查趣味数学小册子，其技巧是：趣例为载体，简喻作引导，推导明道理，前瞻性概述--“学，然后知不足”。 所以，此文仍有一些简单的推导，只需中学数学知识，但仍须静心思量。 2 来 自管理层的需求 设 想 某理想小型超市 , 采用 mini 版超市销售系统 , 管理了 6 种商品，记录了 5 个顾客的购物单（数据量如此之小，是为了简单地说明思想）。 流水号 所购物品清单 1 啤酒、薄饼、牛奶 2 烤鸭、薄饼、面酱 3 啤酒、烤鸭、薄饼、面酱 4 面酱，鸡蛋 5 烤鸭、面酱 经理不满足常识性的定性描述，想知道商品间关联，例如，顾客买了面酱就会买烤鸭吗？ 要求挖掘出支持度 不小于 2/5 （即至少同时被买两次）的商品间的关联。 下面先介绍朴素而费时的笨方法，后介绍聪明一些的方法。 记录总数记为 N ， N=5; 商品总数记为 M ， M=6 。 这里的数值 2/5 称为 支持度阈值 t ，支持度 不小于 2/5 的商品组成的集合称为高频集。 3朴素方法 3.1 模仿选举计票方法统计单项高频集 。把上面的 5 条记录视为 5 张选票，模仿 “唱票 - 计票 - 写正字”的方法，逐条唱票 - 计票，得票不少于两票的商品如下： 单项统计 支持度 { 啤酒 } 2/5 { 烤鸭 } 3/5 { 面饼 } 3/5 { 面酱 } 4/5 解释 ∶ (1) 单项统计中看出 60% 的顾客买了烤鸭、 60% 的顾客买了面饼、 80% 的顾客买了面酱。 (2) 如果所购物品清单中间有 N 条记录（这里 N=5 ），这里扫描工作量与 N 称正比，用行话，称为计算复杂度是 Order （ N ），或简单记录为 O(N)，统计百分比在 传统的统计中常见到。 3.2 模仿选举计票方法统计双项高频集 商品总数记为 M ， M=6, M 个对象的两两组合数目为 T=M* （ M-1 ） /2 ，这里 T=15 , （与 M 2 变化趋势大致相同 ），这一次选举对象是 T 种组合的每一个“商品对”，逐条 唱票 - 计票，得票超过两票的“同购商品对”如下 双项统计 支持度 { 啤酒，面饼 } 2/5 { 烤鸭，面饼 } 2/5 { 烤鸭，面酱 } 3/5 { 面饼，面酱 } 2/5 从双项统计中看出， 5 个顾客中，有 60% 的顾客买了烤鸭和面酱。传统的统计较少作这种组合统计工作。 3.3 模仿选举计票方法统计三项高频集 ， 类似地，得到高频的 同购 三项集 只有一项： 三项统计 支持度 { 烤鸭，面饼，面酱 } 2/5 这说明2/5= 40% 的顾客同时买了烤鸭、面饼和面酱。 4 从高频集导出关联规则 R1 ：烤鸭 -- 面饼、面酱。支持度 40% ，置信度为 66.6% 解释 ：买 烤鸭 的顾客占 3/5 ，买了烤鸭又同时买了{ 面饼，面酱} 顾客 占 2/5 ，说明在买烤鸭的人当中又 买了{面饼、面酱}的占{ (2/5) / (3/5) }=66.6% 。按朴素的，但不一定总是正确的看法，把买烤鸭视为原因，右边的买{ 面饼、面酱} 的视为结果，现有数据表明，这种因果关系有 66.6% 的正确性（不是想当然拍脑袋得出的神仙数字）。 且慢宣称找到了发财诀窍，因为对 3.3节 的结果还有另外两种演绎，（推理方法如上）： R2 ：面饼 -- 烤鸭、面酱 ， 支持度 40% ，置信度为 66.6% R3 ：面酱 -- 面饼、烤鸭 ， 支持度 40% ，置信度为 50% 而这些规则的 运用之妙成乎于人， 例如∶ 用 R1 ，将烤鸭降价以促销面饼、面酱，很可能会破产（一等置信度，导致了破产）； 用 R2 将面饼降价，以促销烤鸭，可能会发财； （一等置信度，导致了发财）； 用 R3 ，引不起顾客的热情。 可见，真理（知识）藏在数据中，还要人去去伪存真。 5 关联规则不是因果关系 设有关联规则： R4 ： X-- Y s= ？ c= ？ 它并不说明 X 是 Y 的原因，因为立刻可以写出有同样支持度的反方向规则，（置信度可能不同）， R5 ： Y-- X s= ？ c= ？ R4 仅提示，当 X 发生时， Y 发生的置信度为 C ，如果置信度 C=0.5 时，则相当于掷硬币算命，不可靠， 当 C 比较大时，例如 0.7 以上，就值得进一步考察，如果 X 包含多个项： X=A 1 A 2 ….. A n ，检查其中是否有多余的项，此法可用于排除过敏原，或研究饮食习惯对某种疾病的影响等场合。 我们曾经发表过一种 排除因果关系 的方法，考察 X 发生自然波动或者人工扰动时，如果 Y 的波动表现混沌，则可排除因果关联，反之，则可进一步调查研究：例如啤酒和纸尿布的故事中，通过属于管理范畴的调查，发现“ 婴儿之父下班为孩子买尿布时顺手买回自己爱喝的啤酒”，使得挖掘出来的规则可理解、可相信。 6 朴素方法太笨，数据量稍大就不可行。 朴素方法关键就是“组合被选举对象 -- 唱票 -- 计票”， 容易理解，容易实现，在小规模数据上是可用的，例如，想挖掘一个民间药方中的较重要成分，如果一共 10 项，每项有 10 个可能剂量，容易实现程序，现在的 PC 机已经比较快了，能计算这样的小规模问题。 但是，量变引起质变， 当数据变得很大，此法就从可行变为不可行了 考察 挖掘关联规则实际过程，易见过程分两大步： (a) 筛出高频集 。 给定支持度阈值 t , 模仿选举的“唱票 - 计票”把频率高于 t 的 单项集，双项集， …,K 项集 找出来（如第 3 节），这一步至少扫描数据库K遍，而且，多项集之组合数量很大，比较费时间。 (b) 计算置信度 ，比较简单，左边的支持度做分母，两边合起来的的支持度做分子（如第 3 节）。 在第一步中，当商品总数 T 比较大，例如实际大超市中，例如 T10 5 , 欲考察 K 项商品之间关联，当 K 比较大，例如 K10 时，涉及到组合爆炸，也许，用高档计算机也需要若干天，若干月，用行话描述，朴素方法的 Scalability不好，有人把scalability译为 规模伸缩性 或者简称 伸缩性 。 有聪明一点的方法吗？有。 下文中将看到，发表聪明方法的学者一举成名，而那篇论文创造了 被引用次数 的奇迹 ，下文将作简介这一成果，同时，分析超高被引用论文的特征。 相关博文 1 “被打”和“北大” 的关联 --- 趣味数据挖掘系列之 一 2 烤鸭、面饼和甜 面酱之朴素关联 --- 趣味数据挖掘系列之二 3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之 三 4 巧挖科学博客之均击量公式，兼谈干预规则 ---- 趣味数据挖掘之四 5 听妈妈讲 过去的故事，分房与分类 ----- 趣味数据挖掘之五 6 借水浒传故事，释决策树思路--- 趣味数据挖掘之六 7 宴会上的聚类 — 趣味数据挖掘之七 8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八 9 灯谜、外星殖民、愚公移山和进化计算 --- 趣味数据挖掘之九 10 达尔文、孟德尔与老愚公会盟：基因表达式编程--趣味数据挖之十 11 十大算法展辉煌，十大问题现锦绣---趣味数据挖掘之十一 12 数据挖掘中的趣味哲学 --- 趣味数据挖掘之十二 假日聚会，戏说云物人海 -- 漫谈大数据 其它系列博文的入口 唐常杰博客主页 科学博客主页
个人分类: 科普札记|16193 次阅读|46 个评论
“被打”和“北大” 的关联--- 趣味数据挖掘系列之一
热度 35 tangchangjie 2011-11-16 15:05
　　 “被打”和“北大” 的关联--- 趣味数据挖掘系列之一(唐常杰） 小时候喜欢读趣味数理化，所以久有一个小心愿，写一组趣味数据挖掘的科普博文。要把数据挖掘的一些概念讲得通俗有趣，需要好的例子，正搜寻中，一个有趣的、适合解释关联规则的例子就冒出来了。 　　科学网上三位博主周涛、吕喆、程智在博文（ 文1 , 　 文2, 　 文3) 　中 对“狼爸打子成才，把三个子女送进了北大”的事情做了定性分析。 　　本文借此例来说明数据挖掘中关联规则中支持度、置信度和兴趣度概念，顺便对此事做个定量分析， 同时也作为趣味数据挖掘系列博文的开篇。 　　 这个关联规则 可写成下列形式： 　　 R1： 被打 -- 北大， 支持度 s=?, 置信度 c=? 或 反过来 R2: 北大 -- 被打， 支持度 s=?, 置信度 c=? （观察因果的角度与R1有所不同） 下面将其计算支持度、置信度的上限，为简单，采用了一些略有放大的粗略假定和估计。 　　 　　 1 支持度 （support） 全国每年高考人数大约1000万人（2008 ：1050万，2009:1020万，2010: 957万）；把“狼爸”的三个孩子算成同一年进北大（支持度放大三倍），假定同年进北大、且都有“被打”的经历有3K名（支持度大约放大3K倍） 　　于是，全国考生中 “被打”且 “进北大” 的支持度s 为： 　　　　　支持度 s = 3K/10 7 =3K*10 -7 狼爸的故事表明，这里k ≥ 1, 据常识估计K10 ( 如果轻率放大K，北大学生会提出抗议，幸好，这里只是反面的假定 ），于是： 　　　　　支持度 s 3*10 -6 （支持度没有因果方向， 对R1和R2都适用） 对这样的概率比较小的事件，成熟彩民也会只当做娱乐，实在不值得媒体大惊小怪。 　　 2 计算“ 北大--被打”的置信度 (confidence) 2.1 在北京大学内计算 规则R1“被打-- 北大” 的 置信度计算稍有点难， 留到2.2小节解析。 我们先计算 R2：“北大--被打”的置信度，它也同样能说明某种关联，北大本科生 14000人（大约），平均每年收学生3500人，设其中挨过家长打的有3K人（1 ≤ k10），没有挨打的不少于3470人，则： 北大--被打， 置信度为 3K/3500 0.86% 北大--不被打， 置信度为 3470/3500 99.14% 可见，“被打”和“北大”的关联 很小，不足为信，当不得真。 　　 2.2 计算“被打 --北大”的置信度 (confidence)： 　　如上面假设，假定 同年全国被打的N名，其中进入北大的3K名（如上估计，0 ≤k10 ）则 R1: 被打--北大， 置信度 = 3k/N , 如果N很大，k0,置信度就比较小（不敢轻易估计N的具体数值,但不希望N大，那是教育的悲剧）， 如果N不太大，K0,置信度就比较大。 如果某年，k=0，不管N是多大， 那一年“被打--北大”的置信度 为0. 　　 　　 2.3 在该家庭范围内计算，兼议规则的兴趣度 ： “狼爸”有四个孩子（不知为什么能够超生），估计四个都挨过打，三个上了北大 被打-- 北大， 支持度 0.75， 置信度 0.75。 （1） 这条规则一旦走出其家门， 就不成立了。所以，准确表达为： （该家，被打） -- 北大， 支持度 0.75， 置信度 0.75。 （2） 为了说明其无意义，我们还可以挖掘出一条千真万确的关联规则： （该家子女，每天吃饭） -- 北大， 支持度 0.75， 置信度 0.75。 （3） 如果把“每天吃饭”改为任意的保健品，关联规则也成立，比“打”更具有有诱惑力，说不定还有经济效益。 这条无意义的关联规则，说明需引入关联规则的兴趣度，此概念稍复杂，只简介其大致思想。 当关联规则左边是多个项，如上面的（3）式，可以用减项法测试每个项的贡献，这类似过敏疾病患者判断过敏源，左边甚至可以减少到空集。在（3）式中， （a)把“每天吃饭”去掉， 不减少支持度和置信度，说明此项冗余； (b)如把“该家子女”去掉，则相当于在全国的大数据集上挖掘， 支持度和置信度立刻大减，说明这个项是至关重要的。 如果一个关联规则中，每一个项都是重要的，这个关联规则基本上是有意义的。 3 错误的挖掘结论 这里有几个估计，(1) 所谓的“打”，实际上是高高举起，轻轻放下，是严格的指代词，还不是那种打得皮开肉绽的打（那样会打掉尊严和信心，就悲剧了）；(2)老大比较懂事；（3）老大对老二老三的影响远胜于老爸打的效果。“狼爸”在挖掘关联规则时候，忽略了这一因素，“父假长子（女）之威”，用数据挖掘的行话，犯了“No interesteness” 的错误（这是一个稍复杂的概念），得出了错误的挖掘结论。 4 一个支持度和置信度都很高的关联规则 在输入文本的纠错技术中，常关注词与词的发声关联，或谐音关联，“被打”和“北大”的普通话发音都是“beida”,用拼音输入法时候，二者容易混淆，又例如， 本博文在输入最后一节小标题“辨才需待七年期”时，曾把 “辨才”输入为“辩才“（谢谢22楼的朋友的指正）， 纠错软件会把近音词按近似度排序列出。因为在语音近似的意义上： 被打-- 北大，支持度 100%， 置信度 100% 于是，在用拼音方法输入“被打”之后，作输入纠错检查时，软件列出候选词中的Top 1 就是“北大”，或许可以作为中学生被打后的一种安慰。 这一技术在处理网络文本，微博挖掘时也很有用，如规范 “悲剧 Vs 杯具”，“p2p Vs. P-to-P,”U Vs. YOU“,以及许多网络同声缩略语等等。 5 曾经言必称啤酒尿布 过去讲关联规则时候，常常用啤酒尿布的故事，有三个要点： (a)表象分析：说，沃尔玛通过抽象的销售数据挖掘，发现啤酒和尿布常被男性顾客们同时购买，在挖掘出来的若干条形如 （ X i --Y i ， s=? c=? ) 的规则中，这一条支持度和置信度都比较高； (b)内在联系 （这不属于数据挖掘,而属于管理）调查发现，婴儿之父下班为孩子买尿布时顺手买回自己爱喝的啤酒； (c )促销措施 （属于促销手段）,把啤酒和尿布放在同一个货架 ，或进一步地，把啤酒降价，把尿布涨价，吸引婴儿之父的消费。 现在人们认为,这只是一个故事，或许，“狼爸”的例子更贴近，更容易消除对概念的误解。 6 猜自然之谜时，数据挖掘虽属无奈之举，却很有效 。 在人们没有掌握行星运动规律之前，人们从历史观测数据去找规律，找匹配。第谷是一位实验天文学家，历经40年观察，积累了关于行星运动的大量数据。 　　开普勒在第谷的四十年数据上，用手工作数据挖掘，挖掘了十年，发现了行星运动三大定律。 Candida Ferreira采用基因表达式编程（GEP）方法，用10个 个体， 进化50代，只需要少得多的数据，几秒钟就可完成（参见文献 ,P253-257 )。有了这个定律，如今计算某个行星的位置，就不再需要数据挖掘，而直接用公式了。所以数据挖掘是在不知道规律时，而要猜自然之谜时的无奈之举。 如今，未破解的自然之谜还很多，数据挖掘虽属无奈之举，却很有效，挖掘出正确的表达形式（公式，定律等）后，再设法用理论或模型 来作动力学的或构造性的解释。 上面的分析表明，数据挖掘能从能从一些平常熟视无睹的事实中，挖掘出令人惊奇的结果。所以，有些国家把数据挖掘专业看作是敏感专业，出国学数据挖掘的学生去办留学签证时，常常被Check ,复查,偶尔也听说过被拒签。 7 辨才需待七年期 。 “狼爸”的三个子女进了北大，还不能就说是成功了，今后还要作科研，找工作，也许还要读研，写论文…, 等待他们的竞争还多，要等将来工作上出成果了，才算成功。 有道是：试玉要烧三日满，辨才需待七年期。希望他们在七年或者十年之后能真正成才，那时的成才，与现在的“打”，实在是没有什么关联了。 博友已提出问题， 问方法，关联规则怎么挖掘 ？问应用，怎么使用关联规则？且等下篇分解。 参考文献 Candida Ferreira,Gene Expression Programming ,Mathematical Modeling by an Artificial Intelligence, Second, revised and extended edition,P253-257 ,Springer,2006 ,ISSN print edition: 1860-949X, ISSN electronic edition: 1860-9503 ,Library of Congress Control Number: 2006921791. 相关博文 1 “被打”和“北大” 的关联 --- 趣味数据挖掘系列之 一 2 烤鸭、面饼和甜 面酱之朴素关联 --- 趣味数据挖掘系列之二 3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之 三 4 巧挖科学博客之均击量公式，兼谈干预规则 ---- 趣味数据挖掘之四 5 听妈妈讲 过去的故事，分房与分类 ----- 趣味数据挖掘之五 6 借水浒传故事，释决策树思路--- 趣味数据挖掘之六 7 宴会上的聚类 — 趣味数据挖掘之七 8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八 9 灯谜、外星殖民、愚公移山和进化计算 --- 趣味数据挖掘之九 10 达尔文、孟德尔与老愚公会盟：基因表达式编程--趣味数据挖之十 11 十大算法展辉煌，十大问题现锦绣---趣味数据挖掘之十一 12 数据挖掘中的趣味哲学 --- 趣味数据挖掘之十二 假日聚会，戏说云物人海 -- 漫谈大数据 六度分隔的扩展应用--穿越几次见欧拉（科普+科幻） 其它系列博文的入口 唐常杰博客主页 科学博客主页
个人分类: 科普札记|26790 次阅读|86 个评论
关联规则兴趣度评价
热度 1 郭崇慧 2011-6-10 16:25
关联规则兴趣度评价
随着数据收集和存储技术的不断发展，各行各业积累了大量的数据。为了从这些数据中获取有用的知识，数据挖掘技术越来越多地被数据分析人员所使用。关联规则挖掘作为数据挖掘领域的一项关键技术，目前在许多领域得到了广泛的应用 。关联规则算法可以产生大量的规则。但是由于资源的有限性，只能有部分规则可能被决策者选择出来使用 ，因此关联规则的兴趣度评价对于关联规则挖掘技术的实际应用具有重要意义。 关联规则的兴趣度可以通过兴趣度度量来评价。目前存在的兴趣度度量主要包括客观的度量和主观的度量 。客观的度量主要考虑数据的统计显著性，如关联规则挖掘中用到的支持度、置信度和提升度。主观的度量综合考虑原始数据和用户的领域知识。文 提出将用户的领域知识作为约束集成到关联规则挖掘系统中，获得用户感兴趣的规则。文 认为在挖掘的过程中，用户应该和关联规则挖掘系统进行交互，来判断规则是否感兴趣。文 和文 基于效用理论，提出了加权支持度和置信度来衡量关联规则兴趣度。 对于许多关联规则挖掘的特定应用领域，用户所感兴趣的挖掘结果可能涉及到多个方面。如在购物篮分析中，用户除了关注规则的统计显著性指标之外，可能对规则可以带来的销售利润也很关心。也就是说，对关联规则的评价应当是一个多属性决策问题。文 将PROMETHEE方法应用于关联规则评价，获得用户感兴趣的模式；文 同时考虑了客观的兴趣度度量和用户的主观偏好，将AHP-ELECTRE II方法用于关联规则排序，实现了关联规则挖掘同决策分析的集成。文 和 分别使用两个不同的数据包络分析(DEA)模型，对同一关联规则集进行了评价。 从文 和 的评价结果对比来看，对于同一关联规则集使用不同评价方法得出的评价结果存在一定程度的差异，当用户同时面临多种评价结果时，便会产生困惑，不利于决策。由于每种评价方法得出的结果都是对评价对象客观状态某个视角的反映，因此有必要综合考虑多种评价方法的评价信息，对评价结果进行集成，以得到更好的评价结果 。但如何选取合适的评价指标并建立关联规则评价指标体系，如何将现代综合评价方法与决策方法应用于关联规则评价 ，并对单一方法得到的评价结果进行综合集成，都是需要进一步研究的问题。 参考文献 Tan P N, Steinbach M, Kumar V. Introduction to data mining . Pearson Addison-Wesley, 2005. Choi D H, Ahn B S, Kim SH. Prioritization of association rules in data mining: Multiple criteria decision approach . Expert Systems with Application, 2005, 29(4): 867-878. Geng L, Hamilton H J. Interestingness measures for data mining: a survey . ACM Computing Surveys, 2006, 38(3): 1-32. Padmanabhan B, Tuzhilin A. A belief-driven method for discovering unexpected patterns . Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining.1998: 94–100. Sahar S. Interestingness via what is not interesting . Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining.1999: 332-336. Lu S F, Hu H P, Li F. Mining weighted association rules . Intelligent Data Analysis, 2001, 5(3): 211-225. Shen Y D, Zhang Z, Yang Q. Objective-Oriented utility-based association mining . Proceedings of the 2002 IEEE International Conference on Data Mining.2002: 426–433. 陈中祥, 吴相林, 岳超源. 基于PROMETHEE的模式兴趣度评估方法研究 . 系统工程与电子技术, 2003, 25(9): 1090-1093. Chen MC. Ranking discovered rules from data mining with multiple criteria by data envelopment analysis . Expert Systems with Application, 2007, 33(4): 1110-1106. Toloo M, Sohrabi B, Nalchigar S. A new method for ranking discovered rules from data mining by DEA . Expert Systems with Application, 2009, 36(4): 8503-8508. 郭崇慧, 张震. 基于组合评价方法的关联规则兴趣度评价 . 情报学报, 2011, 30(4):353-360. 郭亚军, 易平涛. 一种基于整体差异的客观组合评价法 . 中国管理科学, 2006,14(3):60-64. 岳超源. 决策理论与方法 . 北京: 科学出版社, 2003.
个人分类: 科研笔记|10516 次阅读|2 个评论
更多...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-6-16 19:27

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部