数据挖掘的关联规则挖掘

关联规则挖掘中的几个概念

先看一个简单的例子，假如有下面数据集，每一组数据ti表示不同的顾客一次在商场购买的商品的集合：t1: 牛肉、鸡肉、牛奶t2: 牛肉、奶酪t3: 奶酪、靴子t4: 牛肉、鸡肉、奶酪t5: 牛肉、鸡肉、衣服、奶酪、牛奶t6: 鸡肉、衣服、牛奶t7: 鸡肉、牛奶、衣服假如有一条规则：牛肉—>鸡肉，那么同时购买牛肉和鸡肉的顾客比例是3/7，而购买牛肉的顾客当中也购买了鸡肉的顾客比例是3/4。这两个比例参数是很重要的衡量指标，它们在关联规则中称作支持度support和置信度confidence。对于规则：牛肉—>鸡肉，它的支持度为3/7，表示在所有顾客当中有3/7同时购买牛肉和鸡肉，其反应了同时购买牛肉和鸡肉的顾客在所有顾客当中的覆盖范围；它的置信度为3/4，表示在买了牛肉的顾客当中有3/4的人买了鸡肉，其反应了可预测的程度，即顾客买了牛肉的话有多大可能性买鸡肉。其实可以从统计学和集合的角度去看这个问题， 假如看作是概率问题，则可以把“顾客买了牛肉之后又多大可能性买鸡肉”看作是条件概率事件，而从集合的角度去看，可以看下面这幅图：

上面这副图可以很好地描述这个问题，s表示所有的顾客，而a表示买了牛肉的顾客，b表示买了鸡肉的顾客，c表示既买了牛肉又买了鸡肉的顾客。在数据挖掘中，例如上述例子中的所有商品集合i=牛肉，鸡肉，牛奶，奶酪，靴子，衣服称作项目集合，每位顾客一次购买的商品集合ti称为一个事务，所有的事务t=t1,t2,....t7称作事务集合，并且满足ti是i的真子集。一条关联规则是形如下面的蕴含式：x—>y，x，y满足：x，y是i的真子集，并且x和y的交集为空集其中x称为前件，y称为后件。其中(x,y).count表示t中同时包含x和y的事务的个数，x.count表示t中包含x的事务的个数。关联规则挖掘则是从事务集合中挖掘出满足支持度和置信度最低阈值要求的所有关联规则，这样的关联规则也称强关联规则。对于支持度和置信度，我们需要正确地去看待这两个衡量指标。一条规则的支持度表示这条规则的可能性大小，如果一个规则的支持度很小，则表明它在事务集合中覆盖范围很小，很有可能是偶然发生的；如果置信度很低，则表明很难根据x推出y。根据条件概率公式p(y|x)=p(x,y)/p(x)，即p(x,y)=p(y|x)*p(x)p(y|x)代表着置信度，p(x,y)代表着支持度，所以对于任何一条关联规则置信度总是大于等于支持度的。并且当支持度很高时，此时的置信度肯定很高，它所表达的意义就不是那么有用了。这里要注意的是支持度和置信度只是两个参考值而已，并不是绝对的，也就是说假如一条关联规则的支持度和置信度很高时，不代表这个规则之间就一定存在某种关联。举个最简单的例子，假如x和y是最近的两个比较热门的商品，大家去商场都要买，比如某款手机和某款衣服，都是最新款的，深受大家的喜爱，那么这条关联规则的支持度和置信度都很高，但是它们之间没有必然的联系。然而当置信度很高时，支持度仍然具有参考价值，因为当p(y|x)很高时，可能p(x)很低，此时p(x,y)也许会很低。

关联规则挖掘的原理和过程

从上面的分析可知，关联规则挖掘是从事务集合中挖掘出这样的关联规则：它的支持度和置信度大于最低阈值minsup,minconf，这个阈值是由用户指定的。我们称像f这样的集合称为频繁项目集，假如f中的元素个数为k，我们称这样的频繁项目集为k-频繁项目集，它是项目集合i的子集。所以关联规则挖掘可以大致分为两步：1从事务集合中找出频繁项目集；2从频繁项目集合中生成满足最低置信度的关联规则。 最出名的关联规则挖掘算法是apriori算法，它主要利用了向下封闭属性：如果一个项集是频繁项目集，那么它的非空子集必定是频繁项目集。它先生成1-频繁项目集，再利用1-频繁项目集生成2-频繁项目集。。。然后根据2-频繁项目集生成3-频繁项目集。。。依次类推，直至生成所有的频繁项目集，然后从频繁项目集中找出符合条件的关联规则。下面来讨论一下频繁项目集的生成过程，它的原理是根据k-频繁项目集生成k+1-频繁项目集。因此首先要做的是找出1-频繁项目集，这个很容易得到，只要循环扫描一次事务集合统计出项目集合中每个元素的支持度，然后根据设定的支持度阈值进行筛选，即可得到1-频繁项目集。下面证明一下为何可以通过k-频繁项目集生成k+1-频繁项目集：假设某个项目集s=s1，s2...，sn是频繁项目集，那么它的n-1非空子集s1，s2，...sn-1，s1，s2，...sn-2，sn...s2，s3，...sn必定都是频繁项目集，通过观察，任何一个含有n个元素的集合a=a1，a2，...an，它的n-1非空子集必行包含两项a1，a2，...an-2，an-1和 a1，a2，...an-2，an，对比这两个子集可以发现，它们的前n-2项是相同的，它们的并集就是集合a。对于2-频繁项目集，它的所有1非空子集也必定是频繁项目集，那么根据上面的性质，对于2-频繁项目集中的任一个，在1-频繁项目集中必定存在2个集合的并集与它相同。因此在所有的1-频繁项目集中找出只有最后一项不同的集合，将其合并，即可得到所有的包含2个元素的项目集，得到的这些包含2个元素的项目集不一定都是频繁项目集，所以需要进行剪枝。剪枝的办法是看它的所有1非空子集是否在1-频繁项目集中，如果存在1非空子集不在1-频繁项目集中，则将该2项目集剔除。经过该步骤之后，剩下的则全是频繁项目集，即2-频繁项目集。依次类推，可以生成3-频繁项目集。。直至生成所有的频繁项目集。得到频繁项目集之后，则需要从频繁项目集中找出符合条件的关联规则。最简单的办法是：遍历所有的频繁项目集，然后从每个项目集中依次取1、2、...k个元素作为后件，该项目集中的其他元素作为前件，计算该规则的置信度进行筛选即可。这样的穷举效率显然很低。即给定一个频繁项目集f，如果一条强关联规则的后件为β，那么以β的非空子集为后件的关联规则都是强关联规则。所以可以先生成所有的1-后件后件只有一项强关联规则，然后再生成2-后件强关联规则，依次类推，直至生成所有的强关联规则。下面举例说明apiori算法的具体流程： 假如有项目集合i=1，2，3，4，5，有事务集t：1,2,31,2,41,3,41,2,3,51,3,52,4,51,2,3,4设定minsup=3/7，misconf=5/7。首先：生成频繁项目集：1-频繁项目集：1，2，3，4，5生成2-频繁项目集：根据1-频繁项目集生成所有的包含2个元素的项目集：任意取两个只有最后一个元素不同的1-频繁项目集，求其并集，由于每个1-频繁项目集元素只有一个，所以生成的项目集如下：1，2，1，3，1，4，1，52，3，2，4，2，53，4，3，54，5计算它们的支持度，发现只有1，2，1，3，1，4，2，3，2，4，2，5的支持度满足要求，因此求得2-频繁项目集：1，2，1，3，1，4，2，3，2，4生成3-频繁项目集：因为1，2，1，3，1，4除了最后一个元素以外都相同，所以求1，2，1，3的并集得到1，2，3， 1，2和1，4的并集得到1，2，4，1，3和1，4的并集得到1，3，4。但是由于1，3，4的子集3，4不在2-频繁项目集中，所以需要把1，3，4剔除掉。然后再来计算1，2，3和1，2，4的支持度，发现1，2，3的支持度为3/7 ，1，2，4的支持度为2/7，所以需要把1，2，4剔除。同理可以对2，3，2，4求并集得到2，3，4 ，但是2，3，4的支持度不满足要求，所以需要剔除掉。因此得到3-频繁项目集：1，2，3。到此频繁项目集生成过程结束。注意生成频繁项目集的时候，频繁项目集中的元素个数最大值为事务集中事务中含有的最大元素个数，即若事务集中事务包含的最大元素个数为k，那么最多能生成k-频繁项目集，这个原因很简单，因为事务集合中的所有事务都不包含k+1个元素，所以不可能存在k+1-频繁项目集。在生成过程中，若得到的频繁项目集个数小于2，生成过程也可以结束了。现在需要生成强关联规则：这里只说明3-频繁项目集生成关联规则的过程：对于集合1，2，3先生成1-后件的关联规则：1，2—>3， 置信度=3/41，3—>2，置信度=3/52，3—>1 置信度=3/31，3—>2的置信度不满足要求，所以剔除掉。因此得到1后件的集合1，3，然后再以1，3作为后件 2—>1，3 置信度=3/5不满足要求，所以对于3-频繁项目集生成的强关联规则为：1，2—>3和2，3—>1。

#include #include #include #include using namespace std;vector t; //保存初始输入的事务集 double minsup,minconf; //用户设定的最小支持度和置信度 map mp; //保存项目集中每个元素在事务集中出现的次数 vector< vector > f; //存放频繁项目集 vector<<"请输入事务集的个数:"<>n; getchar; cout<<"请输入事务集:"<>minsup>>minconf;vector split(string str,char ch) vector v; int i,j; i=0; whilei f; //存储1-频繁项目集 fori=0;i v=split(t,); //将输入的事务集进行切分，如输入1 2 3，切分得到"1","2","3" forj=0;j v1,vector v2 //判断v1和v2是否只有最后一项不同 int i,j; i=0; j=0; whilei<> v,vector f //判断v的所有k-1子集是否在f中 int i,j; bool flag=true; fori=0;i::iterator it=findf.begin,f.end,str; ifit==f.end flag=false; return flag;int calculatesupportcount(vector v) //计算支持度计数 int i,j; int count=0; fori=0;i t=split(t[i,); forj=0;j::iterator it=findt.begin,t.end,v[j; ifit==t.end break; ifj==v.size count++; return count; bool judgesupportvector<=mp.size;k++ iff.size< k //如果fk-1为空，则退出 break; else //根据fk-1生成ck候选项集 int i,j; vector c; vector f=f[k-1; fori=0;i v1=split(f[i,); forj=i+1;j v2=split(f[j,); ifjudgeitem(v1,v2) //如果v1和v2只有最后一项不同，则进行连接 vector tempvector=v1; tempvector.push_backv2[v2.size-1; sorttempvector.begin,tempvector.end; //对元素排序，方便判断是否进行连接 //剪枝的过程 //判断 v1的(k-1)的子集是否都在fk-1中以及是否满足最低支持度 ifjudgesubset(tempvector,f)judgesupport(tempvector) int p; string tempstr; forp=0;p removeitemfromset(vector v1,vector v2) //从v1中剔除v2 int i; vector result=v1; fori=0;i::iterator it= findresult.begin,result.end,v2[i; ifit!=result.end result.erase(it); return result;string getstr(vector v1,vector v2) //根据前件和后件得到规则 int i; string rstr; fori=0;i v=split(fs,); vector h; vector< vector > h; //存放所有的后件 int fcount=calculatesupportcount(v); //f的支持度计数 fori=0;i addh; fori=0;i v1=split(h[i,); forj=i+1;j v2=split(h[j,); ifjudgeitem(v1,v2) vector tempvector=v1; tempvector.push_backv2[v2.size-1; //得到后件集合 sorttempvector.begin,tempvector.end; vector filterv=removeitemfromset(v,tempvector); //得到前件集合 int acount=calculatesupportcount(filterv); //计算前件支持度计数 iffcount >= ceil(acount*minconf) //如果满足置信度要求 string rstr=getstr(filterv,tempvector); //根据前件和后件得到规则 string hstr; forint s=0;s f=f[k; fori=0;i<> f=f[k; fori=0;i<><>