关联规则挖掘

关联规则挖掘黎都2004-12-21基本概念（1）数据，数据集项目，项目集事务t包含项目集X支持数，频繁项目集（频集）Support（X）=a(x)/|D|置信度基本概念（2）关联规则：若项目集X与Y交集为空，则X=>Y为关联规则，其中：Support(X=>Y)=Support(X并Y）Confidence（X=>Y）=Suppose(X并Y）/Suppose(X)关联规则的目的对于指定的minsupport和minconfidence使得support(X)>=minsupportConfidence(X）>=minconfidence则称关联规则X=>Y为强规则关联规则挖掘的就是挖掘出事务集D中的强规则关联规则挖掘关联规则挖掘分为两个子问题：1，根据最小支持度找出数据集D中的所有频集；2，根据频集和最小置信度产生关联规则；关联规则的发现算法发现算法解决的是关联规则挖掘的第一个问题关联规则分为布尔关联规则和多值规则多值关联规则都转化为布尔关联规则来解决，因此先介绍布尔关联规则算法Apriori，AprioriTid，AprioriHybridApriori算法Agrawal等人在1993年提出的AIS和SETM的基础上在1994年提出Apriori和AprioriTiApriori和AprioriTid算法利用前次过程中的数据项目集来生成新的候选数据项目集，减少了中间不必要的数据项目集的生成，提高了效率Apriori算法L1={大项目集1项目集}For(k=2;Lk-1

非空；k++)dobeginCk=apriori-gen(Lk-1);for所有事务tdobeginCt=subset(Ck,t)for所有候选c（属于Ct

）doc.count++;Apriori算法End

Lk

={c属于Ck|c.count>=minsupp}EndApriori算法得到的频集为Lk

的并集Apriori算法分析分为第一次遍历和第k次遍历第一次遍历计算每个项目的具体值，确定大项目集1项目集L1

第k次遍历利用前一次找到的大项集Lk-1

和Apriori-gen函数产生候选集Ck，然后扫描数据库，得到Ck

中候选的支持度，剔除了不合格的候选后Ck作为Lk

Apriori算法分析:Apriori-gen本质是合并项目集成为候选项目集算法：InsertintoCk

Selectp[1],p[2],……，p[k-1]，q[k-1]FromLk-1p，Lk-1qWherep[1]=q[1]，……，p[k-2]=q[k-2]p[k-1]<q[k-1]Apriori算法分析:Apriori-gen然后，对于Ck

中某集合c的任意子集，如果不存在于Lk-1，则删除c；例子：L3

为{123}{124}{135}{234}在合并后为C3:{{1234}{1345}}；因为{1345}中的{145}不存在，所以C3

中{1345}应该删除，故L4:{1234}Apirori算法分析：Subset候选项目集Ck

是存储在一个Hash树中的，并且要求项目集中的项目有序Subset函数寻找所有包含在某个事务中的候选，使用Hash查找实质：得到候选集Ck

中候选项c的支持度AprioriTid算法AprioriTid算法由Apriori算法改进优点：只和数据库做一次交互，无须频繁访问数据库将Apirori中的Ck

扩展，内容由{c}变为{TID，c}，TID用于唯一标识事务引入Bk

，使得Bk

对于事务的项目组织集合，而不是被动的等待Ck

来匹配ApioriTid算法举例：minsupp=2数据库：TID项目100134200235300123540025ApioriTid算法示例TID项目集100{1}{3}{4}200{2}{3}{5}300{1}{2}{3}{5}400{2}{5}项集支持度{1}2{2}3{3}

3{5}3ApioriTid算法示例TID项目集100{{13}}200{{23}{25}{35}}300{{12}{13}{15}{23}{25}{35}}400{{25}}项集支持度{13}2{23}2{25}

3{35}2ApioriTid算法示例TID项目集100空200{{235}}300{{235}}400空ApioriTid算法上面图中分别为Bk

和Lk，而Ck

和Apriori算法产生的一样，因此没有写出来可以看到Bk

由Bk-1

得到，无须由数据库取数据缺点：内存要求很大，事务过多的时候资源难以满足ApioriHybrid算法这种算法将Apriori算法和AprioriTid算法混合，利用各自优点弥补不足；利用的原理：随着候选集的元素扩充，所能匹配的事务将可能减少算法：先使用Apriori算法，当能匹配的事务减少到内存可以容纳的程度，使用ApiroriTid算法ApioriHybrid算法性能AprioriHybrid算法性能比Apriori和AprioriTid算法都要好经过算法统计平均，AprioriHybrid比Apriori效率高30%，比AprioriTid高60%但是应用上比两者都复杂，相对而言用Apriori可以得到更简单的应用多值属性关联刚才介绍的都是布尔属性关联，实际中多值属性应用也很多解决多值关联的办法在于把QARP转为BARP来解决解决要点：划分值域区间太宽，置信度将降低太窄，支持度将降低多值属性关联定义：挖掘多值关联规则问题就是在给定的交易集合D中产生所有满足最小支持度和最小置信度的多值关联规则的过程MAQA算法MAQA算法MAQA算法将QARP问题转为BARP问题。Step1：对于多值属性A，若取值范围为[L,R]，划分为若干区间。若为数量属性，应用聚类算法确定值的划分，若为类别属性，采用归纳进行划分。MAQA算法Step2：将划分后的属性区间映射为序对<A,k>，A属于布尔集Step3：从项目集中找出有价值的项，构成频集Step4：在频集中迭代的找到支持度合格的两个项，并加入频集项目集中Step5：应用频集产生关联规则Step6：确定有价值的关联规则作为输出MAQA算法第一步划分为关键，支持度和置信度证明对立矛盾的关系，合适划分是个重要的步骤。第二步和第五步都很直接，第五步计算最小置信度如：ABCD和AB都为频集，通过Conf=supp(ABCD)/supp(AB)判断是否超过最小置信度MAQA算法第三步为Apriori算法或者其改进算法第六步采用interest度量方法下面重点介绍第一步和第四步多值划分的聚类算法CP聚类算法CPFor每个属性值大于N的属性do计算每个属性对应的事务数目寻找局部最大点和最小点确定区间计算minL和maxL之间的事务数sumi如果满足合并条件则合并相邻区间得到k个区间S=sumi的和-max(sumi)–min(sumi)聚类算法CPS平均=S/（K-2）寻找所有大于c*S平均的sumi，并把结果存于PForP中每个区间jdoIfsumi/(minRi–MinLi)>S/(minR-minL)then保存区间j作为输