首页 > 代码库 > 【数据挖掘技术】关联规则（Apriori算法）
【数据挖掘技术】关联规则（Apriori算法）
一、关联规则中的频繁模式
关联规则（Association Rule）是在数据库和数据挖掘领域中被发明并被广泛研究的一种重要模型，关联规则数据挖掘的主要目的是找出：
【频繁模式】：Frequent Pattern，即多次重复出现的模式和并发关系（Cooccurrence Relationships），即同时出现的关系，频繁和并发关系也称为关联（Association）.
二、应用关联规则的经典案例：沃尔玛超市中“啤酒和尿不湿”的经典营销案例
购物篮分析（Basket Analysis）:通过分析顾客购物篮中商品之间的关联，可以挖掘顾客的购物习惯，从而帮助零售商可以更好地制定有针对性的营销策略。
以下列举一个最简单也最经典的关联规则的例子：婴儿尿不湿—>啤酒[支持度=10%,置信度=70%]
这个规则表明，在所有顾客中，有10%的顾客同时购买了婴儿尿不湿和啤酒，而在所有购买了婴儿尿不湿的顾客中，占70%的人同时还购买了啤酒。发现这个关联规则后，超市零售商决定把婴儿尿不湿和啤酒摆在一起进行销售，结果明显提高了销售额，这就是发生在沃尔玛超市中“啤酒和尿不湿”的经典营销案例。
三、支持度（Support）和置信度（Confidence）
事实上，支持度和置信度是衡量关联规则强度的两个重要指标，他们分别反映着所发现规则有用性和确定性。
【支持度】 规则X->Y的支持度：事物全集中包含X U Y的事物百分比。Support（A B）= P（A B） 支持度主要衡量规则的有用性，如果支持度太小，则说明相应规则只是偶发事件，在商业实践中，偶发事件很可能没有商业价值。【置信度】 规则X->Y的置信度：既包括X又包括Y的事物占所有包含了X的事物数量的百分比。Confidence（A B）= P（B|A） 置信度主要衡量规则的确定性（可预测性），如果置信度太低，那么从X就很难可靠的推断出Y来，置信度太低的规则在实践应用中也没有太大用途。
四、Apriori算法
【基本概念】1 【资料库（Transaction Database）】：存储着二维结构的记录集（D)；2 【所有项集（Items）】：所有项目的集合(I)；3 【记录 （Transaction ）】：在资料库里的一笔记录(T,T属于D);4 【项集（Itemset）】：同时出现的项的集合。定义为：k-itemset（k项集），k-itemset ? T。除非特别说明，否则下文出现的k均表示项数；5 【候选 集（Candidate itemset）】：通过向下合并得出的项集。定义为C[k]；6 【强规则】：经过关联规则分析后，针对某些人推销（根据某规则）比盲目推销（一般来说是整个数据）的比率，这个比率越高越好；7 【剪枝步】只有当子集都是频繁集的候选集才是频繁集，这个筛选的过程就是剪枝步；
Apriori算法是众多的关联规则数据挖掘算法中最著名的算法，其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。
该算法具体分为以下两步进行：
- 生成所有的频繁项目集。一个频繁项目集（Frequent Itemset）是一个支持度高于最小支持度阀值（min-sup）的项目集。
- 从频繁项目集中生成所有的可信关联规则。这里可信关联规则是指置信度大于最小置信度阀值（min-conf）的规则。
然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递归的方法。
【Apriori算法】
Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。 step1: 通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1;
step2: 利用L1找频繁2项集的集合L2;
step3: L2找L3，
...
stepn: 如此下去，直到不能再找到任何频繁k项集。
最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。其中，Apriori算法具有这样一条性质：任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)< 最小支持度阈值，当有元素A添加到I中时，结果项集（A∩I）不可能比I出现次数更多。因此A∩I也不是频繁的。
然而，可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。
五、关联规则算法的用途
关联规则算法不但在数值型数据集的分析中有很大用途，而且在纯文本文档和网页文件中，也有重要作用。比如发现单词间的并发关系以及Web的使用模式等，这些都是Web数据挖掘、搜索及推荐的基础。