注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

柳州文铮

CANTOR SET&ART

 
 
 

日志

 
 

关联规则的学习Association rule learning  

2013-03-05 11:59:50|  分类: 股票数学模型对冲 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

File:FrequentItems.png

关联规则的学习Association rule learning

数据挖掘 , 关联规则发现有趣的大型数据库中的变量之间的关系, 学习是一种流行和研究方法。 它的目的是确定在数据库中发现使用不同的措施对有趣的强关联规则。 [1]基于强规则的概念,拉克什Agrawal等[2]提出的关联规则发现产品在大型交易记录的数据之间的规律通过销售点 (POS)系统,在超市销售。 例如,规则 \ {\ mathrm {洋葱,土豆} \} \ RIGHTARROW \ {\ mathrm {汉堡} \} 在一家超市的销售数据表明,如果一个客户购买洋葱和土豆一起,他或她很可能也买汉堡肉。 这些信息可以作为决策的基础,例如,促销定价产品置入营销活动,如。 在上面的例子中,从市场购物篮分析的关联规则,今天,在许多应用领域,包括Web使用挖掘 , 入侵检测 , 连续生产生物信息学 。 相对于序列挖掘 ,关联规则的学习通常不考虑项目内的交易或跨事务的顺序。

定义

示例数据库有4个项目和5个交易
交易ID 牛奶 面包 黄油 啤酒
1 1 1 0 0
2 0 0 1 0
3 0 0 0 1
4 1 1 1 0
5 0 1 0 0

Agrawal等人的原始定义。 [2]的关联规则挖掘问题的定义是:让 我= \ {I_1,I_2,\ ldots,i_n \} 是一组 ? 二进制属性的项目 。 让 D = \ {T_1,T_2,\ ldots,t_m \} 称为数据库的一组交易。 每笔交易 ? 有一个唯一的事务ID和包含的项目中的一个子集 我 。 被定义为规则的形式的含义 X \ RIGHTARROW? 哪里 X,Y \ subseteq我 和 X \帽Y = \ emptyset 。 该套项目(以下简称项目集 ) X 和 ? 被称为先行 (左手侧或左)和随之而来的 (右手侧或RHS)的规则。

要说明的概念,我们用一个小例子从超市域。 的一组项是 I = \ {\ mathrm {牛奶,面包,黄油,啤酒} \} 和一个小的数据库,其中包含的项目(1个代码的存在和没有在一个事务中的资料的0)到右侧的表中所示。 一个例子规则的超市 \ {\ mathrm {黄油,面包} \} \ RIGHTARROW \ {\ mathrm {牛奶} \} 这意味着,如果酱和面包都买了,客户也买牛奶。

注意:这个例子是非常小的。 规则在实际应用中,需要一个支持几百交易,才可以被认为有统计学显着性,并且数据集通常包含数千或数以百万计的交易。


编辑 ]有用的概念

要选择有趣的规则,从所有可能的规则的集合,约束的各种措施的意义和利息都可以使用。 最有名的约束是最低阈值的支持和信任。


的支持 \ mathrm {增刊}(X) 一个套装 X 被定义为包含项集的数据集合中的交易的比例。 在示例数据库中,项集 \ {\ mathrm {牛奶,面包,黄油} \} 有一个支撑 1/5 = 0.2 因为它发生的所有交易的20%(1 5笔交易)。
定义规则的信心 \ mathrm {配置}(X \ RIGHTARROW?)= \ mathrm {增刊}(X \杯子?)/ \ mathrm {增刊}(X) 。 例如,规则 \ {\ mathrm {牛奶,面包} \} \ RIGHTARROW \ {\ mathrm {黄油} \} 有信心 0.2/0.4 = 0.5 在数据库中,这意味着50%的牛奶和面包的交易规则是正确的(50%的顾客买了牛奶和面包,黄油以及购买)。 阅读时要小心的表达:在这里,增刊(X∪Y)是指发生的交易, 其中 X 和Y都出现 “ 支持 ”,而不是“ 对发生的交易中出现X或Y的支持 ”,所产生的一种解释,因为集工会是相当于逻辑分离 。 参数 \ mathrm {增刊}() 是一组前提条件,从而变得更加严格,因为它的增长(而不是更具包容性的)。
的概率的估计值可以被解释为置信 P(Y | X) ,发现该规则的RHS交易的可能性的情况下,这些交易还包含了LHS。 [3]
电梯的规则被定义为 \ mathrm {电梯}(X \ RIGHTARROW?)= \压裂{\ mathrm {增刊}(X \杯Y)} {\ mathrm {增刊}(X)\时间\ mathrm {增刊}(Y)} 或比所观察到的支持预期的,如果X和Y是独立的 。 该规则 \ {\ mathrm {牛奶,面包} \} \ RIGHTARROW \ {\ mathrm {黄油} \} 设有电梯 \压裂{0.2} {0.4 \倍0.4 = 1.25 。
被定义为规则的信念 , \ mathrm {换}(X \ RIGHTARROW?)= \压裂{1  -  \ mathrm {增刊}(Y)} {1  -  \ mathrm {配置}(X \ RIGHTARROW Y)} 。 该规则 \ {\ mathrm {牛奶,面包} \} \ RIGHTARROW \ {\ mathrm {黄油} \} 有一个信念, \压裂{1  -  0.4} {1  -  0.5} = 1.2 ,并且可以理解为预期频率的比率是X发生无Y(即是说,的频率,该规则作出不正确的预测),如果X和Y是独立的,除以所观察到的频率不正确的预测。 在这个例子中,定罪值为1.2的规则 \ {\ mathrm {牛奶,面包} \} \ RIGHTARROW \ {\ mathrm {黄油} \} 20%以上的经常是不正确的(1.2倍多),如果X和Y之间的关联是纯粹偶然的机会。
编辑 ]过程


频繁项集晶格,其中的颜色的方块表示多少事务包含的项目的组合。 请注意,较低水平的格子可以包含至多他们父母的资料的最小数目,例如,{交流}至多只能有 MIN(A,C) 项目。 这就是所谓的向下封闭性 [2]。

关联规则,通常需要以满足用户指定的最小支持和用户指定的最小值在同一时间的信心。 关联规则的产生通常是分成两个独立的步骤:


首先,最小支持在数据库中找出所有的频繁项集 。
其次,这些频繁项集和最小置信度约束的形式规则。

而第二个步骤是简单的,第一步需要更多的关注。

在数据库中查找所有的频繁项集是困难的,因为它涉及到搜索所有可能的项集(产品组合)。 可能的项目集的一组发电机组超过 我 并有大小 2 ^ n-1个 (不包括不是一个有效的项集是空集)。 虽然呈指数增长中的项目数的幂的大小 ? 在 我 ,高效的搜索,可以使用向下封闭性的支持[2] [4] (也称为反单调性 [5] ),保证频繁项集,它的所有子集是频繁的,从而为一个罕见的套装,它的所有超集也必须是罕见的。 利用这个属性,高效的算法(例如,Apriori算法[6]和怡亨[7] ),可以找到所有的频繁项集。


编辑 ]历史

关联规则的概念通俗化,特别是由于Agrawal等1993年的文章。 人,已经收购了6000多引用根据谷歌学术搜索,截至2008年3月,因此,在数据挖掘领域被引用最多的论文之一[2] 。 但是,它是可能的,什么是现在所谓的“关联规则”是出现在1966年的一篇论文中,由彼得·哈耶克等人开发的一个通用的数据挖掘方法对古哈[8] [9]


编辑 ]对有趣的替代措施

下一步,信心也对有趣的规则的其他措施提出了建议。 一些流行的措施是:


所有的信心[10]
集体的力量[11]
信念[12]
充分利用[13]
提起(原名利息) [14]

这些措施的定义可以在这里找到。 以上几种措施和Tan等人[15]寻找技术,可以模拟用户(使用此模型为兴趣性措施)是一个活跃的研究趋势的名义下的“主观趣味性”


编辑 ]统计上可靠协会

有一个限制,发现协会的标准方法是通过搜索大量的数字可能存在的关联看,似乎是相关联的项目的集合,发现了许多虚假的协会有一个大的风险。 这些项目,合作与意外的发生频率在数据的集合,但只这样做的机会。 例如,假设我们考虑10,000项的集合和寻找含有两个项目中的左手侧和1资料中的右手侧的规则。 还有约1万亿的规则。 如果我们将一个独立的统计检验显着性水平为0.05,这意味着只有5%的机会接受一个规则,如果不存在关联关系。 如果我们假设有没有关联,不过,我们应该期望找到50,000,000,000规则。 可靠的统计协会发现[16] [17]控制这方面的风险,在大多数情况下,发现任何可疑的协会用户指定的显着性水平降低风险。


编辑 ]算法

随着时间的推移产生关联规则的算法,提出了许多。

一些著名的算法是Apriori算法 ,怡亨和FP-增长,但他们只是做了一半的工作,因为他们是频繁项集挖掘算法。 需要做的另一个步骤后在数据库中发现频繁项集产生规则。


编辑 ]Apriori算法
主要文章: Apriori算法

Apriori算法是最知名的挖掘关联规则的算法[6] 。 它采用了广度优先搜索策略来计算项目集的支持,并使用一个的候选生成功能,利用向下封闭性支持。


编辑 ]怡亨算法

怡亨[7]是一种深度优先搜索算法,使用交集。


编辑 ]FP-growth算法

FP代表频繁模式。

在第一个阶段,该算法计算发生(属性 - 值对)数据集,并将其存储到“头表的。 在第二个阶段,它建立FP-树结构由插入的实例。 在每个实例中的资料进行排序中的数据集,从而使它们的频率的降序排列的树可以被快速处理。 在每个实例中不符合最低保额门槛的项目将被丢弃。 ,如果许多情况下,分享最频繁的项,FP-树提供高压缩比接近树的根。

这个压缩版的主数据集的递归处理变大项集,而不是直接产生候选项目,并测试他们对整个数据库。 增长开始从底部的头表(最长的分支机构),找到所有匹配给定条件的情况下。创建新的树,与计数投射对应于设定的条件的属性的实例是从原来的树,每个节点得到它的儿童计数的总和。 递归增长时,没有个别项目的属性条件满足最小支持度阈值,并继续处理原来的FP-树的剩余头项目。

递归过程一旦完成,所有大项集,最低保额已发现关联规则的创建开始。

[18]


编辑 ]古哈程序ASSOC

古哈是探索性数据分析,具有一定的理论基础,在观察结石的一般方法[19] 。

的的ASSOC过程[20]是一个古哈矿山广义关联规则快速的位串操作的方法。 用这种方法开采关联规则都比较一般比输出的先验,例如“项目”,可以同时连接与结合背离和规则的前项和后之间的关系不仅限于设置最小支持度和信心,在的先验:支持的感兴趣措施的任意组合都可以使用。


编辑 ]OPUS搜索

OPUS是一个有效的规则发现算法[21] ,相反,大多数替代品,并不需要反单调是单调或限制,如最低支持。,最初用来寻找规则的固定随之而来的[21] [22]后来一直延续到随之而来的任何项目规则。 [23] OPUS搜索是流行的巨著协会发现系统中的核心技术。


编辑 ]绝杀

有关关联规则挖掘是一个著名的故事“啤酒和尿布”的故事。 一名自称是超市购物行为的调查,发现客户(大概是年轻男性)买尿布的人往往也买啤酒。 这个故事成为流行的一个例子,如何从日常的数据可能会发现意想不到的关联规则。 的故事有多少是真实的,有不同的意见。 [24]丹尼尔·鲍尔斯说: [24]


 

1992年,托马斯布利肖克的零售咨询集团在Teradata的经理,和他的同事准备了一个120万约25 OSCO药店的市场购物篮分析。 数据库查询,以确定亲缘关系。 分析“也发现,下午5点至7:00之间,消费者购买啤酒和尿布”。 有组织及严重罪行管理人员没有利用的啤酒和尿布关系的更紧密的货架上,移动产品。


编辑 ]其他类型的关联规则挖掘

对比组的学习是联想式学习的一种形式。 对比度设置的学习者使用不同的规则,在他们对面的子集分配有意义的。 [25]

加权课堂学习是另一种形式的联想学习,重者可被分配给类给一个特定的数据挖掘结果的消费者关注的问题焦点。

高阶模式发现技术,方便捕捉的高的顺序(polythetic)模式固有的复杂的现实世界的数据或事件的关联。 [26]

K-最优模式发现提供了另一种关联规则的学习,要求每个图案中经常出现的数据的标准方法。

挖掘频繁序列的支持,找到序列中的时空数据。 [27]

广义关联规则的分层分类(概念层次)

量化关联规则分类和定量数据[28]

区间型数据的关联规则 ,例如分区岁到5岁的增量不等

的最大协会的规则

一连串的关联规则,时间数据,如第一次购买电脑,CD-ROM,然后一个摄像头。


编辑 ]参见
序列挖掘
生产系统
编辑 ]
^ Piatetsky夏皮罗,格里高利(1991), 发现,分析,并介绍强大的规则 ,在Piatetsky夏皮罗,格雷戈里和弗劳利,威廉J.主编。, 数据库中的知识发现 ,AAAI / MIT出版社,剑桥,MA 。
一个 B? ? ?: ? 阿格拉瓦尔,R.;,T.Imieliński;偶像,A.(1993)。 “挖掘关联规则在大型数据库”项目组之间进行的1993年ACM SIGMOD国际会议上的数据管理- SIGMOD 93。 第207 DOI : 10.1145/170035.170072 。 ISBN 0897915925 。 编辑
^ 希普,J.;Güntzer,U.; Nakhaeizadeh,G.(2000)。 “算法的关联规则挖掘---一个普通的调查和比较。”ACM SIGKDD探索快 ??讯 2:58。 DOI : 10.1145/360402.360421 。 编辑
谭,彭宁,迈克尔,斯坦贝奇;库马尔,VIPIN(2005年)。 “第6章。关联分析:基本概念和算法” 。 数据挖掘 。 Addison-Wesley出版 , ISBN 0-321-32136-7 。
沛,建汉,加味; Lakshmanan提供,LAKS VS 频繁项集挖掘可兑换的限制 ,在第17届国际会议上月2-6工程数据,2001年,海德堡,德国 ,2001年,页433-442
 b 阿格拉瓦尔,拉克什·;和Srikant的,莱玛克里斯南; 快速的在大型数据库中挖掘关联规则的算法 ,在虎门,豪尔赫B.;,萨默尔Jarke;和Zaniolo,卡罗;编辑, 第20届国际会议上非常大的数据库(VLDB),圣地亚哥,智利,1994年9月 ,页487-499
 b 崎,MJ(2000年)。 “可扩展算法的关联规则挖掘。IEEE知识和数据工程,12(3):372-390。 DOI 编辑 : 10.1109/69.846291 。
^ 哈耶克,切赫,伊万·哈维尔; Chytil,Metoděj; 自动假设确定的古哈的方法 ,计算1(1966)293-308
^ 哈耶克,切赫Feglar,托马斯;劳赫,月和Coufal,大卫· 古哈法,数据预处理和挖掘 ,数据挖掘应用程序的数据库支持,施普林格,2004年, ISBN 978-3-540-22479-2
Omiecinski,爱德华·R.; 替代利率措施在数据库中矿业协会 ,IEEE知识与数据工程,15(1):57-69月/ 2003年2月
AGGARWAL,Charu C.和玉,菲利普S.; 项集产生一个新的框架 ,在PODS 98,研讨会数据库系统原理,西雅图,WA,USA,1998,页18-24
布林,谢尔盖·伟,拉杰夫;厄尔曼中,Jeffrey D.和楚苏尔,沙洛姆动态项集计数和蕴涵规则的市场购物篮数据 ,在SIGMOD 1997年,ACM SIGMOD数据管理国际会议(SIGMOD 1997) ,图森,亚利桑那州,美国,1997年5月 ,第255-264
^ Piatetsky夏皮罗,格雷戈里, 发现,分析,并介绍强大的规则 ,数据库中的知识发现,1991年,第229-248
布林,谢尔盖·伟,拉杰夫;厄尔曼中,Jeffrey D.和楚苏尔,沙洛姆动态项集计数和蕴涵规则的市场购物篮数据 ,在SIGMOD 1997年,ACM SIGMOD数据管理国际会议(SIGMOD 1997) ,图森,亚利桑那州,美国,1997年5月 ,第265-276
谭,彭宁;库马尔,VIPIN;和Srivastava,Jaideep, 选择正确的目标措施关联分析 ,信息系统,29(4):293-313,2004年
韦伯,杰弗里·I.(2007年); 发现显着的模式 ,机器学习68(1),荷兰:施普林格,第1-33 在线访问
Gionis,阿里斯蒂德 Mannila,海基 ;Mielik?inen,Taneli; Tsaparas,Panayiotis; 评估数据挖掘结果通过交换随机 ,ACM知识发现数据(TKDD),第1卷,第3期2007年12月号,第14
威滕,弗兰克,霍尔:数据挖掘实用机器学习的工具和技术,第3版
劳赫,则逻辑结石数据库中的知识发现 ,在诉讼的原则,数据挖掘和知识发现 ,施普林格,1997年第一届欧洲 ,页47-57
^ 哈耶克,切赫和Havránek,托马斯(1978)。 机械化假说形成的一般理论的数学基础 。 施普林格出版社。 ISBN 3-540-08738-9 。
^ 韦伯,杰弗里·I.(1995); 作品:一个高效的可容许算法无序的搜索 ,中国的人工智能研究,门洛帕克,CA:AAAI出版社,第431-465页 在线访问
巴亚尔,,小罗伯托J.;阿格拉瓦尔,拉克什; Gunopulos,迪米特里奥斯(2000年)。 “基于约束的规则挖掘在大,密集的数据库”。 数据挖掘和知识发现 4(2):217-240。 DOI :10.1023 / A:1009895914772 。
^ 韦伯,杰弗里·I.(2000); 协会的规则“,,拉古莱玛克里斯南的高效搜索和Stolfo,萨尔;主编。 第六届ACM SIGKDD国际会议上的知识发现和数据挖掘(KDD-2000),波士顿; ,MA,纽约,NY:美国计算机协会,页99-107 在线访问
一个 B? http://www.dssresources.com/newsletters/66.php
孟席斯,蒂姆和胡莹; 数据挖掘非常忙碌的人 ,IEEE计算机2003年10月,页18-25
黄,安德鲁KC王杨(1997)。 “高阶模式发现从离散值数据”。IEEE知识与数据工程(TKDE):877-893。
扎基·穆罕默德J.(2001年); SPADE:挖掘频繁序列的高效算法 ,机器学习杂志,42,页31-60
^ Salleb Aouissi,Ansaf;和Christel VRAIN,;和Nortet,西里尔(2007年)。 “QuantMiner:基于遗传算法的量化关联规则挖掘”。 国际联合人工智能会议(IJCAI):1035-1040。
编辑 ]外部链接
编辑 ]参考书目
Hahsler,迈克尔关联规则的注释书目
StatSoft推出的电子教材:关联规则
编辑 ]实现
SIPINA ,一个自由的,学术的数据挖掘sotware,其中包括关联规则学习的典范。
大数据,数据挖掘平台的普及DataRush ,包括关联规则挖掘
KXEN数据挖掘,商业软件
Silverlight的部件用Apriori算法的关联规则挖掘的现场演示
RapidMiner ,一个免费的Java数据挖掘软件套件(社区版:GNU)
橙色 ,一个免费的数据挖掘软件套件,模块orngAssoc
Ruby实现(AI4R)
arules , ?挖掘中的关联规则和频繁项集包
的C. Borgelt的实现Apriori和怡亨
频繁项集挖掘实现信息库(FIMI)
频繁模式挖掘的实现来自巴特戈索尔斯的
Weka中 , Java语言编写的数据挖掘任务的机器学习算法的集合
KNIME一个开源的流程导向的数据预处理和分析平台
扎基·穆罕默德·J.; 数据挖掘软件
巨著 ,系统可靠的统计协会发现
(古哈) Lisp的矿工 ,矿山广义关联规则(使用位串,而不是apriori算法)
Ferda Dataminer ,可扩展的可视化数据挖掘平台,实现了古哈程序ASSOC和数据挖掘功能multirelational
STATISTICA ,商业统计软件的关联规则模块
SPMF ,一个开源的数据挖掘平台,提供超过48个,集挖掘关联规则挖掘和序列模式挖掘算法。 包括一个简单的用户界面,并在GPL下发布Java源代码。
ARtool ,GPL的Java关联规则挖掘应用程序的图形用户界面,提供多种算法的实现,对发现的频繁模式和关联规则的提取(包括Apriori和FPgrowth)

  评论这张
 
阅读(202)| 评论(0)
推荐

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017