Apriori算法

http://blog.csdn.net/lizhengnanhua/article/details/9061755

一、Apriori算法简介：  Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。 Apriori（先验的，推测的）算法应用广泛，可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定。

二、挖掘步骤：

1.依据支持度找出所有频繁项集（频度）

2.依据置信度产生关联规则（强度）

三、基本概念

对于A->B

①支持度：P(A ∩ B)，既有A又有B的概率

②置信度：

P(B|A)，在A发生的事件中同时发生B的概率 p(AB)/P(A)     例如购物篮分析：牛奶 ⇒ 面包

例子：[支持度：3%，置信度：40%]

支持度3%：意味着3%顾客同时购买牛奶和面包

置信度40%：意味着购买牛奶的顾客40%也购买面包

③如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。

④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则

四、实现步骤

    Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法，“K-1项集”用于搜索“K项集”。

首先，找出频繁“1项集”的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。

核心思想是：连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某

个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。

简单的讲，1、发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集   重复步骤（1）~（5）直到不能发现更大的频集

2、产生关联规则，过程为:根据前面提到的置信度的定义，关联规则的产生如下：

（1）对于每个频繁项集L，产生L的所有非空子集；

（2）对于L的每个非空子集S，如果

                P（L）/P（S）≧min_conf

则输出规则“SàL-S”

注：L-S表示在项集L中除去S子集的项集

 

算法：Apriori
输入：D - 事务数据库；min_sup - 最小支持度计数阈值
输出：L - D中的频繁项集
方法：
     L1=find_frequent_1-itemsets(D); // 找出所有频繁1项集
     For(k=2;Lk-1!=null;k++){
        Ck=apriori_gen(Lk-1); // 产生候选，并剪枝
        For each 事务t in D{ // 扫描D进行候选计数
            Ct =subset(Ck,t); // 得到t的子集
            For each 候选c 属于 Ct
                         c.count++;
        }
        Lk={c属于Ck | c.count>=min_sup}
}
Return L=所有的频繁集；
 
Procedure apriori_gen(Lk-1:frequent(k-1)-itemsets)
      For each项集l1属于Lk-1
              For each项集 l2属于Lk-1
                       If((l1[1]=l2[1])&&( l1[2]=l2[2])&&……..
&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])) then{
                   c=l1连接l2 //连接步：产生候选
                   if has_infrequent_subset(c,Lk-1) then
                       delete c; //剪枝步：删除非频繁候选
                   else add c to Ck;
                  }
          Return Ck;
 
     Procedure has_infrequent_sub(c:candidate k-itemset; Lk-1:frequent(k-1)-itemsets)
        For each(k-1)-subset s of c
            If s不属于Lk-1 then
               Return true;
        Return false;