浅谈Python实现Apriori算法介绍

导读：

随着大数据概念的火热，啤酒与尿布的故事广为人知。我们如何发现买啤酒的人往往也会买尿布这一规律？数据挖掘中的用于挖掘频繁项集和关联规则的Apriori算法可以告诉我们。本文首先对Apriori算法进行简介，而后进一步介绍相关的基本概念，之后详细的介绍Apriori算法的具体策略和步骤，最后给出Python实现代码。

1.Apriori算法简介

Apriori算法是经典的挖掘频繁项集和关联规则的数据挖掘算法。A priori在拉丁语中指"来自以前"。当定义问题时，通常会使用先验知识或者假设，这被称作"一个先验"（a priori）。Apriori算法的名字正是基于这样的事实：算法使用频繁项集性质的先验性质，即频繁项集的所有非空子集也一定是频繁的。Apriori算法使用一种称为逐层搜索的迭代方法，其中k项集用于探索(k+1)项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1。然后，使用L1找出频繁2项集的集合L2，使用L2找出L3，如此下去，直到不能再找到频繁k项集。每找出一个Lk需要一次数据库的完整扫描。Apriori算法使用频繁项集的先验性质来压缩搜索空间。

2. 基本概念

项与项集：设itemset={item1, item_2, …, item_m}是所有项的集合，其中，item_k(k=1,2,…,m)成为项。项的集合称为项集（itemset），包含k个项的项集称为k项集(k-itemset)。 事务与事务集：一个事务T是一个项集，它是itemset的一个子集，每个事务均与一个唯一标识符Tid相联系。不同的事务一起组成了事务集D，它构成了关联规则发现的事务数据库。 关联规则：关联规则是形如A=>B的蕴涵式，其中A、B均为itemset的子集且均不为空集，而A交B为空。 支持度(support)：关联规则的支持度定义如下：

其中表示事务包含集合A和B的并（即包含A和B中的每个项）的概率。注意与P(A or B)区别，后者表示事务包含A或B的概率。

置信度(confidence)：关联规则的置信度定义如下：

项集的出现频度(support count)：包含项集的事务数，简称为项集的频度、支持度计数或计数。

频繁项集(frequent itemset)：如果项集I的相对支持度满足事先定义好的最小支持度阈值（即I的出现频度大于相应的最小出现频度（支持度计数）阈值），则I是频繁项集。

强关联规则：满足最小支持度和最小置信度的关联规则，即待挖掘的关联规则。

3. 实现步骤

一般而言，关联规则的挖掘是一个两步的过程：