|
媒介
大二的时辰，一个先生为了勾起我们对数据发掘的乐趣，总是问我们这个题目：你们知道超市为什么要把啤酒跟尿布放在一路吗？可是从来没汇报我们谜底。此刻，许多人都听过这个题目，认为很泛泛，可是当时的我真认为挺神奇的。直到其后，相识了关联法则发掘，进修了关联法则发掘的代表性算法Apriori，才终于知道了谜底。关联法则发掘，就是找出那些常常同时呈现的事物，好比啤酒和尿布。接下来，我们进入正题。
根基常识
关联法则发掘通过情势化的说话表述如下：
设荟萃
I=i1,i2,...,im
是一个项目（Item）荟萃,
T=t1,t2,...,tn
是一个事宜（Transaction）荟萃，个中，每个事物
ti
是一个项目荟萃，并满意
ti?I
，项目就是相同媒介中所说的啤酒和尿布的对象，事宜就是同时呈现的几个项目标荟萃。
一个关联法则是一个如下情势的蕴涵相关：
X→Y，个中，X?I,Y?I且X?Y=?
X(或Y)是一个项目标荟萃，称为项集(Itemset),X称为前件，Y称为后件。
假如项集X是事物
ti∈T
的一个子集,则称
ti
包括X,或称X包围
ti
。X在T中的支持计数（暗示位
X.count
）是T中包括X的事物的数量。
对付关联法则
X→Y
，有
支持度=(X?Y).countn,个中，n是事物数量
置信度=(X?Y).countX.count
支持度用于权衡一条法则呈现得有多频仍，只有呈现得足够频仍的法则对我们才有效，好比
啤酒→尿布
。置信度用于权衡以前件推出后件的可行度，相同于概率
P(Y|X)
。值得留意的是，只要一条法则的支持度到达用户要求的最小支持度(minsup)时，我们才去思量这条法则以前件到后件的置信度。
关联法则发掘的方针就是，找失事物荟萃T中全部满意支持度和置信度别离高于用户指定的最小支持度和最小置信度(minconf)的法则。Apriori算法帮我们实现这个方针。
Apriori算法
Apriori算法分为两步：
(1)天生全部频仍项目集：一个频仍项目集(Frequent Itemset)是一个支持度高于minsup的项集。
(2)从频仍项目齐集天生全部可信关联法则：一个可信关联法则(Confident Association Rule)是置信度大于minconf的法则。
一个包括k个项目标项集称为k-项集,一个包括k个项目标频仍项目集成为k-频仍项目集。
向下关闭属性：频仍项目集的任何非空子集也是频仍项目集。这个属性很重要，可是很好领略：包括频仍项目集的非空子集的事宜数量大于便是包括频仍项目集自己的事宜数量。
接下来详细先容Apriori算法的两步。
频仍项目天生
Apriori算法假定I中的项目都回收字典序分列。在算法中涉及的每个项集也都假定始终保持这个次序。
算法伪代码如下：
个中，
Ck
是候选k-频仍项目集荟萃，
Fk
是频仍项目集荟萃，
?kFk
指全部频仍项目集荟萃的并集。个中，
candidate?gen(Fk?1)
的伪代码如下：
candidate?gen(Fk)
中必要声名的处所是由
Fk?1
天生
Ck
的方法：两个(k-1)-频仍项目集的前k-2个元素都是一样，只有最后一个元素差异，两个频仍项目集的并集构成一个候选k-频仍项目集。为什么这是可行的？由向下关闭属性可知，假如一个k-项目集是频仍项目集，那么它的恣意(k-1)项目子集一定也是频仍项目集，也就是说，它的只有最后一个元素差异的两个(k-1)-频仍项目集一定在
F(k?1)?频仍项目集
中，于是，通过这种方法天生的候选k-频仍项目集包括了全部的k-频仍项目。为什么要选这两个荟萃呢?可以看到，这样选，轻易使得项集保持有序。
关联法则天生
从频仍项目集f中抽取全部关联法则，必要找出f的全部非空子集，然后以使得前件不为空的非空子集作为后件，天生一条关联法则。我们要从这些关联法则找到这样的关联法则：
(f?a)→a，满意置信度=f.count(f?a).count≥minconf
可以看出，当以a为后件时，假如法则满意最小置信度，那么以a的任何非空子集为后件的法则也一定满意最小置信度，由于分母变小了。这也是向下关闭属性。
天生关联法则算法的伪代码如下：
参考资料： 《Web数据发掘》第2版，Bing Liu 著， 俞勇 译
（编辑：湖南网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
