11.1节提到，关联分析的目标包括两项：发现频繁项集和发现关联规则。首先需要找到频繁项集，然后才能获得关联规则。本节将只关注于发现频繁项集。
Apriori算法是发现频繁项集的一种方法。Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表。接着扫描交易记录来查看哪些项集满足最小支持度要求，那些不满足最小支持度的集合会被去掉。然后，对剩下来的集合进行组合以生成包含两个元素的项集。接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。
11.3.1 生成候选项集
在使用Python来对整个程序编码之前，需要创建一些辅助函数。下面会创建一个用于构建初始集合的函数，也会创建一个通过扫描数据集以寻找交易记录子集的函数。数据集扫描的伪代码大致如下：
对数据集中的每条交易记录tran 对每个候选项集can： 检查一下can是否是tran的子集： 如果是，则增加can的计数值 对每个候选项集： 如果其支持度不低于最小值，则保留该项集返回所有频繁项集列表
下面看一下实际的运行效果，建立一个apriori.py文件并加入下列代码。
程序清单11-1 Apriori算法中的辅助函数
def loadDataSet: return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]def createC1(dataSet): C1 = for transaction in dataSet: for item in transaction: if not [item] in C1: C1.append([item]) C1.sort #❶ 对C1中每个项构建一个不变集合 return map(frozenset, C1)def scanD(D, Ck, minSupport): ssCnt = {} for tid in D: for can in Ck: if can.issubset(tid): if not ssCnt.has_key(can): ssCnt[can]=1 else: ssCnt[can] += 1 numItems = float(len(D)) retList = supportData = {} for key in ssCnt: #❷ 计算所有项集的支持度 support = ssCnt[key]/numItems if support >= minSupport: retList.insert(0,key) supportData[key] = support return retList, supportData 上述程序包含三个函数。第一个函数loadDataSet创建了一个用于测试的简单数据集，另外两个函数分别是createC1和scanD。
不言自名，函数createC1将构建集合C1。C1是大小为1的所有候选项集的集合。Apriori算法首先构建集合C1，然后扫描数据集来判断这些只有一个元素的项集是否满足最小支持度的要求。那些满足最低要求的项集构成集合L1。而L1中的元素相互组合构成C2，C2再进一步过滤变为L2。到这里，我想读者应该明白了该算法的主要思路。
因此算法需要一个函数createC1来构建第一个候选项集的列表C1。由于算法一开始是从输入数据中提取候选项集列表，所以这里需要一个特殊的函数来处理，而后续的项集列表则是按一定的格式存放的。这里使用的格式就是Python中的frozenset类型。frozenset是指被“冰冻”的集合，就是说它们是不可改变的，即用户不能修改它们。这里必须要使用frozenset而不是set类型，因为之后必须要将这些集合作为字典键值使用，使用frozenset可以实现这一点，而set却做不到。
首先创建一个空列表C1，它用来存储所有不重复的项值。接下来遍历数据集中的所有交易记录。对每一条记录，遍历记录中的每一个项。如果某个物品项没有在C1中出现，则将其添加到C1中。这里并不是简单地添加每个物品项，而是添加只包含该物品项的一个列表1。这样做的目的是为每个物品项构建一个集合。因为在Apriori算法的后续处理中，需要做集合操作。Python不能创建只有一个整数的集合，因此这里实现时必须是一个列表（有兴趣的读者可以试一下）。这就是我们使用一个由单物品列表组成的大列表的原因。最后，对大列表进行排序并将其中的每个单元素列表映射到frozenset，最后返回frozenset的列表❶。
1. 也就是说，C1是一个集合的集合，如{{0},{1},{2},…}，每次添加的都是单个项构成的集合{0}、{1}、{2}…。——译者注
程序清单11-1中的第二个函数是scanD，它有三个参数，分别是数据集、候选项集列表Ck以及感兴趣项集的最小支持度minSupport。该函数用于从C1生成L1。另外，该函数会返回一个包含支持度值的字典以备后用。 scanD函数首先创建一个空字典ssCnt，然后遍历数据集中的所有交易记录以及C1中的所有候选集。如果C1中的集合是记录的一部分，那么增加字典中对应的计数值。这里字典的键就是集合。当扫描完数据集中的所有项以及所有候选集时，就需要计算支持度。不满足最小支持度要求的集合不会输出。函数也会先构建一个空列表，该列表包含满足最小支持度要求的集合。下一个循环遍历字典中的每个元素并且计算支持度❷。如果支持度满足最小支持度要求，则将字典元素添加到retList中。可以使用语句retList.insert(0,key)在列表的首部插入任意新的集合。当然也不一定非要在首部插入，这只是为了让列表看起来有组织。函数最后返回最频繁项集的支持度supportData，该值会在下一节中使用。
下面看看实际的运行效果。保存apriori.py之后，在Python提示符下输入：
>>> import apriori 然后导入数据集：
>>> dataSet=apriori.loadDataSet>>> dataSet [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]] 之后构建第一个候选项集集合C1：
>>> C1=apriori.createC1(dataSet)>>> C1[frozenset([1]), frozenset([2]), frozenset([3]), frozenset([4]), frozenset([5])] 可以看到，C1包含了每个frozenset中的单个物品项。下面构建集合表示的数据集D。
>>> D=map(set,dataSet) >>> D[set([1, 3, 4]), set([2, 3, 5]), set([1, 2, 3, 5]), set([2, 5])] 有了集合形式的数据，就可以去掉那些不满足最小支持度的项集。对上面这个例子，我们使用0.5作为最小支持度水平：
>>> L1,suppData0=apriori.scanD(D, C1, 0.5)>>> L1[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])] 上述4个项集构成了L1列表，该列表中的每个单物品项集至少出现在50%以上的记录中。由于物品4并没有达到最小支持度，所以没有包含在L1中。通过去掉这件物品，减少了查找两物品项集的工作量。
11.3.2 组织完整的Apriori算法
整个Apriori算法的伪代码如下：
当集合中项的个数大于0时 构建一个k个项组成的候选项集的列表 检查数据以确认每个项集都是频繁的 保留频繁项集并构建k+1项组成的候选项集的列表
既然可以过滤集合，那么就能够构建完整的Apriori算法了。打开apriori.py文件加入如下程序清单中的代码。
程序清单11-2 Apriori算法
def aprioriGen(Lk, k): #creates Ck retList = lenLk = len(Lk) for i in range(lenLk): for j in range(i+1, lenLk): #❶（以下三行）前k-2个项相同时，将两个集合合并 L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2] L1.sort; L2.sort if L1==L2: retList.append(Lk[i] | Lk[j]) return retListdef apriori(dataSet, minSupport = 0.5): C1 = createC1(dataSet) D = map(set, dataSet) L1, supportData = scanD(D, C1, minSupport) L = [L1] k = 2 while (len(L[k-2]) > 0): Ck = aprioriGen(L[k-2], k) #❷ 扫描数据集，从Ck得到Lk Lk, supK = scanD(D, Ck, minSupport) supportData.update(supK) L.append(Lk) k += 1 return L, supportData 程序清单11-2包含两个函数aprioriGen与apriori。其中主函数是apriori，它会调用aprioriGen来创建候选项集Ck。
函数aprioriGen的输入参数为频繁项集列表Lk与项集元素个数k，输出为Ck。举例来说，该函数以{0}、{1}、{2}作为输入，会生成{0,1}、{0,2}以及{1,2}。要完成这一点，首先创建一个空列表，然后计算Lk中的元素数目。接下来，比较Lk中的每一个元素与其他元素，这可以通过两个for循环来实现。紧接着，取列表中的两个集合进行比较。如果这两个集合的前面k-2个元素都相等，那么就将这两个集合合成一个大小为k的集合❶。这里使用集合的并操作来完成，在Python中对应操作符|。
上面的k-2有点让人疑惑。接下来再进一步讨论细节。当利用{0}、{1}、 {2}构建{0,1}、{0,2}、 {1,2}时，这实际上是将单个项组合到一块。现在如果想利用{0,1}、 {0,2}、 {1,2}来创建三元素项集，应该怎么做？如果将每两个集合合并，就会得到{0, 1, 2}、 {0, 1, 2}、 {0, 1, 2}。也就是说，同样的结果集合会重复3次。接下来需要扫描三元素项集列表来得到非重复结果，我们要做的是确保遍历列表的次数最少。现在，如果比较集合{0,1}、 {0,2}、 {1,2}的第1个元素并只对第1个元素相同的集合求并操作，又会得到什么结果？{0, 1, 2}，而且只有一次操作！这样就不需要遍历列表来寻找非重复值。
上面所有的操作都被封装在apriori函数中。给该函数传递一个数据集以及一个支持度，函数会生成候选项集的列表，这通过首先创建C1然后读入数据集将其转化为D（集合列表）来完成。程序中使用map函数将set映射到dataSet列表中的每一项。接下来，使用程序清单11-1中的scanD函数来创建L1，并将L1放入列表L中。L会包含L1、L2、L3…。现在有了L1，后面会继续找L2，L3…，这可以通过while循环来完成，它创建包含更大项集的更大列表，直到下一个大的项集为空。如果这听起来让人有点困惑的话，那么等一下你会看到它的工作流程。首先使用aprioriGen来创建Ck，然后使用scanD基于Ck来创建Lk。Ck是一个候选项集列表，然后scanD会遍历Ck，丢掉不满足最小支持度要求的项集❷。Lk列表被添加到L，同时增加k的值，重复上述过程。最后，当Lk为空时，程序返回L并退出。
下面看看上述程序的执行效果。保存apriori.py文件后，输入如下命令：
>>> reload(apriori)<module /'apriori/' from /'apriori.pyc/'> 上面的命令创建了6个不重复的两元素集合，下面看一下Apriori算法：
>>> L,suppData=apriori.apriori(dataSet)>>> L[[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])],[frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])],[frozenset([2, 3, 5])], ] L包含满足最小支持度为0.5的频繁项集列表，下面看一下具体值：
>>> L[0][frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])]>>> L[1][frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]),frozenset([3, 5])]>>> L[2][frozenset([2, 3, 5])]>>> L[3] 每个项集都是在函数apriori中调用函数aprioriGen来生成的。下面看一下aprioriGen函数的工作流程：
>>> apriori.aprioriGen(L[0], 2)[frozenset([1, 3]), frozenset([1, 2]), frozenset([1, 5]),frozenset([2, 3]), frozenset([3, 5]), frozenset([2, 5])] 这里的6个集合是候选项集Ck中的元素。其中4个集合在L[1]中，剩下2个集合被函数scanD过滤掉。
下面再尝试一下70%的支持度：
>>> L,suppData=apriori.apriori(dataSet,minSupport=0.7)>>> L[[frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([2, 5])], ] 变量suppData是一个字典，它包含我们项集的支持度值。现在暂时不考虑这些值，不过下一节会用到这些值。
现在可以知道哪些项出现在70%以上的记录中，还可以基于这些信息得到一些结论。我们可以像许多程序一样利用数据得到一些结论，或者可以生成if-then形式的关联规则来理解数据。下一节会就此展开讨论。