数据挖掘之关联规则

2016-10-31 本文已影响0人 Mancha

关联规则

关联规则是数据挖掘研究里的重要内容，目的是为了找出不同东西之间的相关性。下面来介绍关联规则中一些重要的定义。

下面借用一个引例来介绍关联规则。

某超市的事务数据库

D是一个事务数据库，其中每一个事务T由一些项目构成，并且都有一个唯一的标识（TID）。如上图所示，每一个TID对应一条事务Ti，每一个事务Ti中的物品称为项目，项目的集合就称为项目集，而含有K个项目的项目集称为K-项目集。

项目集X的支持度是指在事务数据库D中包含项目集X的事务占整个事务的比例，记为sup(X)，可以看作是项目集X在总事务中出现的频率。一般定义为sup(X)=X出现的次数/事务总数T。
引例中X={bread, milk}出现在T1，T2，T5，T9和T10中，所以支持度为0.5。

最小支持度是项集的最小支持阈值，记为min_sup，代表了用户关心的关联规则的最低重要性。支持度不小于min_sup的称为频繁项目集，长度为K的频繁集称为K-频繁集。如果设定sup_min为0.3，引例中{bread, milk}的支持度是0.5，所以是2-频繁集。

可信度是指在事务数据库D中，同时含项目集X和Y的事务与含项目集X的事务的比，即sup(XUY)/sup(X)，看作是项目集X出现，使项目集Y也出现，这一件事情在总事务中出现的频率。

关联规则可形式化为X⇒Y，它的含义是XUY的支持度sup(XUY)大于用户指定的最小支持度min_sup，且可信度conf大于用户指定的最小可信度min_conf。关联规则挖掘就是在事务数据库D中找出满足用户指定的最小支持度min_sup和最小可信度min_conf的所有关联规则。

Apriori算法是一种以概率为基础的关联规则算法，它是一种迭代算法，从少到多，从简单到复杂寻找极大频繁集的算法。

1.Apriori特性
如果一个拥有K个项目的项目集I不满足最小支持度，根据定义，项目集I不是一个频繁集，如果往I中加入任意一个新的项目得到一个拥有K+1个项目的项目集I'，则I'必定也不是频繁集。

2.算法过程

制定最小支持度及最小置信度
Apriori算法使用了候选项集的概念，首先扫描数据库产生候选项目集，如果候选项目集的支持度不小于最小支持度，则该候选项目集为频繁项目集
从数据库中读入所有事务数据，得到出候选1项集C1及相应的支持度数据，通过将每个1项集的支持度与最小支持度比较，得出频繁项集合L1，然后将这些频繁1项集两两进行连接，产生候选2项集合C2。
然后再次扫描数据库得到候选2项集合C2的支持度，将2项集的支持度与最小支持度比较，确定频繁2项集。类似地，利用这些频繁2项集L2产生候选3项集和确定频繁3项集，以此类推。
反复扫描数据库，与最小支持度比较，产生更高项的频繁项集合，再结合产生下一级候选项集，直到不再产生出新的候选项集为止。