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 retList
def 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形式的關聯規則來理解數據。下一節會就此展開討論。