频繁集挖掘（Apriori算法）与关联规则生成

一、背景

在网上购物时，系统会主动推荐一些商品，赠送一些优惠券，并且这些推荐的商品和赠送的优惠券往往都能直抵我们的需求，诱导我们消费。这背后主要使用使用了关联分析技术，通过分析哪些商品经常一起购买，可以帮助商家了解用户的购买行为。从大规模数据中挖掘对象之间的隐含关系被称为关联分析（associate analysis）或者关联规则学习（associate rule learning），其可以揭示数据中隐藏的关联模式，帮助人们进行市场运作，决策支持等。

关联规则最早是为了进行购物篮分析（Market Basket Analysis）而提出的，例如：在超市销售数据中发现了规则{onionspo,potatoes}⇒{burger}，可能指示如果一个顾客同时购买了 onions 和 potatoes，那么他很可能也会购买 burger，这些信息可以用于指导市场活动，比如商品定价，商品摆放位置。

一组购物篮事务的例子

关联规则的例子：{Diaper} -> {Beer}, {Milk, Bread} -> {Eggs, Coke}, {Beer, Bread} -> {Milk}

二、概念定义

2.1 频繁项集（Frequent Itemset）

项集（Itemset）：一个或多个项（item）的集合。例如：{Milk, Bread, Diaper}

k-项集（k-itemset）：一个含有k个项的项集

支持数（Support count）σ：项集出现的次数。例如：σ({Milk, Bread, Diaper}) = 2

支持度（Support）：包含项集的事务数与总事务数的比值。例如：s({Milk, Bread, Diaper}) = 2/5

频繁项集：项集的支持度大于等于一个阈值

2.2 关联规则（Association Rule）

关联规则：一种X -> Y的表达，其中X和Y都是项集。例如：{Milk, Diaper} -> {Beer}

两个评估指标：

支持度（Support, s）：同时包含X, Y的事务数与总事务数的比值
置信度（Confidence, c）：衡量Y中的项在包含X的事务中出现的频率

评估指标的例子

关联规则生成的任务：给定一组事务T，关联规则生成需要找到满足以下条件的规则：

支持度 >= minsup阈值
置信度 >= minconf阈值

三、算法步骤

3.1 频繁集挖掘（Apriori算法）

k = 1
首先找出所有的 1-项集
从所有的 1-项集中，通过计算 support, 找出频繁的 1-项集
如果频繁的 k-项集不为空， repeat：
    用 f_(k-1) * f_(k-1)的方法，生成候选的 k+1 项集
    通过计算 support，找出频繁的 k+1 项集
    k = k+1
返回频繁集集合 f 与对应的支持度集合 support_total

在生成候选项集的时候，有一种优化方法：如果两个有序k-1项集的前k-2项是相同的，那么把他们合并生成新的k项集

k候选集生成的优化

3.2 关联规则生成

对 f 中的每一个频繁集：
    对 f 中的每一个子集：
        首先判断是否包含无法生成关联规则的子集：
            是，则跳过，进入下一次循环
        求出频繁集与该子集的差集
            计算 conf： support(频繁集) / support(差集)
            if conf > min_conf：
                存储【差集 --> 子集】的关联规则
            else:
                加入无法生成关联规则的子集列表
返回关联规则列表 rules

最后编辑于：2019.04.18 21:06:12