Apriori算法介绍（Python实现）

跟着大年夜数据概念的火热，啤酒与尿布的故事广为人知。我们若何发明买啤酒的人往往也会买尿布这一规律?数据发掘中的用于发掘频繁项集和接洽关系规矩的Apriori算法可以告诉我们。本文起首对Apriori算法进内话旧，而落后一步介绍相干的根本概念，之后具体的介绍Apriori算法的具体策略和步调，最后给出Python实现代码。

1.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)：接洽关系规矩的支撑度定义如下：

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

置信度(confidence)：接洽关系规矩的置信度定义如下：

频繁项集(frequent itemset)：如不雅项集I的相对支撑度知足事先定义好的最小支撑度阈值(即I的出现频度大年夜于响应的最小出现频度(支撑度计数)阈值)，则I是频繁项集。

强接洽关系规矩：知足最小支撑度和最小置信度的接洽关系规矩，即待发掘的接洽关系规矩。

3. 实现步调

一般而言，接洽关系规矩的发掘是一个两步的过程：

找出所有的频繁项集

由频繁项集产生强接洽关系规矩

3.1发掘频繁项集

3.1.1 相干定义

连接步调：频繁(k-1)项集Lk-1的自身连接产生候选k项集Ck

Apriori算法假定项集中的项按照字典序排序。如不雅Lk-1中某两个的元素(项集)itemset1和itemset2的前(k-2)个项是雷同的，则称itemset1和itemset2是可连接的。所以itemset1与itemset2连接产生的结不雅项集是{itemset1[1], itemset1[2], …, itemset1[k-1], itemset2[k-1]}。连接步调包含鄙人文代码中的create_Ck函数中。

剪枝策略

因为存在先验性质：任何非频繁的(k-1)项集都不是频繁k项集的子集。是以，如不雅一个候选k项集Ck的(k-1)项子集不在Lk-1中，则该候选也弗成能是频繁的，大年夜而可以大年夜Ck中删除，获灯揭捉?缩后的Ck。下文代码中的is_apriori函数用于断定是否知足先验性质，create_Ck函数中包含剪枝步调，即若不知足先验性质，剪枝。

删除策略

基于紧缩后的Ck，扫描所有事务，对Ck中的每个项进行计数，然后删除不知足最小支撑度的项，大年夜而获得频繁k项集。删除策略包含鄙人文代码中的generate_Lk_by_Ck函数中。

因为要应用字典(support_data)记录项集的支撑度，须要用项集作为key，而可变集合无法作为字典的key，是以在合适机会应将项集转为固定集合frozenset。

3.1.2 步调

每个项都是候选1项集的集合C1的成员。算法扫描所有的事务，获得每个项，生成C1(见下文代码中的create_C1函数)。然后对每个项进行计数。然后根据最小支撑度大年夜C1中删除不知足的项，大年夜而获得频繁1项集L1。
对L1的自身连接生成的集合履行剪枝策略产生候选2项集的集合C2，然后，扫描所有事务，对C2中每个项进行计数。同样的，根据最小支撑度大年夜C2中删除不知足的项，大年夜而获得频繁2项集L2。
对L2的自身连接生成的集合履行剪枝策略产生候选3项集的集合C3，然后，扫描所有事务，对C3每个项进行计数。同样的，根据最小支撑度大年夜C3中删除不知足的项，大年夜而获得频繁3项集L3。
以词攀类推，对Lk-1的自身连接生成的集合履行剪枝策略产生候选k项集Ck，然后，扫描所有事务，对Ck中的每个项进行计数。然后根据最小支撑度大年夜Ck中删除不知足的项，大年夜而获得频繁k项集。

3.2 由频繁项集产生接洽关系规矩

一旦找出了频繁项集，就可以直接由它们产生强接洽关系规矩。产生步调如下：