Apriori 算法的作用
Apriori 算法的核心思想是計算頻繁項集出現的機率（即支援度）和頻繁項集内部的關聯規則（即置信度）。
支援度
什麼是支援度
如圖：如果訂單總數為N，包含某個組合的訂單為M，那麼M組合出現的支援度（機率）為M/N.。
Note
我們這裡認為樣本資料和我們現實世界的真實情況是同分布的。
如何計算支援度
在數學上我們如何找出某一項集的出現機率呢？
我們先列出所有的一項集，然後計算每一項集在在總資料中出現的機率，再計算它們所有的組合産生的機率，如果資料有成千上萬，這個計算量是非常大的，這種情況下，在數學上合理的邏輯在計算機上并不可行，那麼Apriori算法的思路是什麼呢。
支援度的核心思想
如果AB的組合頻繁出現，是頻繁項集，那麼子集A、B必然頻繁出現；
反過來，如果A、B中有一項不是頻繁項集，那麼AB集合必然不是頻繁項集。
我們利用機率論的思想來解決這個問題，根據Apriori算法的思路：如果AB組合頻繁出現，那麼A、B自身必然頻繁出現，反過來，如果A、B不是頻繁出現的，那AB組合也就不是頻繁出現的。是以說Apriori算法提出逐層組合計算思路。
首先列出是以的一項集，計算每一項的支援度，剔除支援度過低的資料項，如圖，也就是後兩項，然後将前四項組成二項集，再計算每一個種組合的支援度，剔除支援度低的項集，支援度的濾值可以根據實際情況自行設定。然後再組合成三項集、四項集，依次類推，直到n項集為空為止，也就是某個次元的頻繁項集不存在，為空集。
那我需要推到什麼時候呢，資料量這麼大，這就提到了一個概念，門檻值threshold，對這個推薦算法來說，我是不是推到四五層就足夠了，我疊代到15層，這有15層的組合是不是就足夠滿足我的需求了呢。我設定這樣一個門檻值。或這說我支援度達到一個什麼程度，我也可以設定一個門檻值。機率達到什麼程度的門檻值。滿足這個條件的時候我自然而然的停止，而不是一直計算到為空集為止。這樣就能大大提高算法的執行效率也能滿足我們的需求。這個和傳統咱們計算出所有排列組合的情況是完全不一樣的。
這樣最後得到的結果項集裡面的所有所有可能組合就是頻繁項集，這樣的項集可能有多個。
比如我們得到最終的頻繁項集結果：
[‘I1, I2, I3’, ‘I1, I2, I5’]
比如對于:I1，I2，I3 這個頻繁集，我們可以得到它的子集:{I1}, {I2}, {I3}, {I1， I2}, {I1，I3}, {I2，I3}。
那麼，如何得到項集内部的規則，也就是關聯關系呢。這就涉及另一個概念：置信度。
置信度
釋義：A出現的時候，B出現的機率。
這裡面還有一個問題是，A和B的關聯關系，比如，買C++ Primer Plus，可能會買 C Primer Plus，因為他要研究一下底層的東西，可是買C Primer Plus的人不會買 C++ Primer Plus，他做底層開發，隻看底層就夠了，也可能我們需要向他彙編一類的書籍。是以，A、B存在因果關系，A是B出現的原因，B卻不是A出現的原因，對于這這關系的計算稱之為置信度，置信度是找出組合内部的關聯關系，支援度是找出在一起出現的頻繁項集。這種項集内部的因果關系我們稱之為關聯規則。
如果A是B出現的原因，我們判斷支援度強弱的方法是用A和B并集{support（A|B）的并集指的是A集合和B集合的出現的概}的支援度除以A的支援度。這樣我們就可以推斷A出現的情況下，B出現的機率。
如果A出現的時候B經常出現，那麼A導緻B的機率就非常高。如圖
A導緻B出現稱為置信度。
舉個例子
我們有ABCD組合，可以拆成下面為四種組合，我們依次從右邊拿出一個放到左邊，這樣每種組合又能派生出三種組合， 這種情況下，依次類推，直到左邊有三項右邊有一項為止，這樣我們就可以生成所有合理的關聯規則組合，在這個基礎上，我們再計算所有關聯規則的置信度confidence，剔除置信度小于某個門檻值threshold的關聯規則，這就是關聯分析。
是以Apriori算法是找出頻繁項集和分析組合内部的因果關系（關聯分析）的算法。最後，我們會設定一個門檻值，不可能計算到空集位置，這種情況太少見了，推到10 - 15個的項集組合的時候可能就足夠了，這種情況下可能會限定一個threshold，避免很多無意義的計算，實際項目當中可能有幾百萬的項目，以現在的計算能力計算出所有的組合是不可能的嗎，所有希望用足夠少的時間計算出滿足我們需求的結果。所有需要設定threshold，或者設定n，推導到多少次，這個思想其實非常重要，大家要注意，在機器學習當中，這個是機器學習的慣有思維和處理方式，很多時候我們傳統的數學模型需要把所有的結果計算出來才能進行下一步推導。 機器學習呢，是逐層計算、逐層推導，它需要一個總體的計算或者說一個結果。 這是機器學習非常重要的一個思想。Apriori算法的核心思想是通過疊代推導每一次産生新項集的方式得到滿足需求的結果。這也是機器學習非常關鍵的核心思想，講其它算法的時候，機器學習都是按照這個思想走下去的，公式不一樣，疊代方法類似。
接下來我們看一下Apriori算法的代碼實作。
Apriori 算法實作
目錄結構
首先，看一下資料我們的資料集
apriorData.txt
每一行是一個書籍的訂單。
C++ Primer Plus C Primer Plus
C Primer Plus C和指針 C陷阱與缺陷 C程式設計語言
C++ Primer Plus C和指針 C陷阱與缺陷 C++程式設計語言
C Primer Plus C++ Primer Plus C和指針 C陷阱與缺陷
C Primer Plus C++ Primer Plus C和指針 C++程式設計語言
接下來看一下Apriori的核心算法實作代碼
apriori.py
"""Apriori算法實作"""
# TODO：補充實作關聯規則提取
// transactions:原始資料，supportThreshold：支援度的門檻值
def apriori(transactions, supportThreshold):
"""Apriori實作"""
# 将每一個事務轉換成集合，提高檢索效率
transactionSets = [set(transaction) for transaction in transactions]
# 生成1項集
itemSets = createItemSets(transactions)
# 計算1項集支援度并篩選符合要求的項集，将支援度過低的剔除
filteredItemSets, supports = filterBySupport(transactionSets,
itemSets, supportThreshold)
# 儲存符合要求的1項集
itemSetsList = [filteredItemSets]
# 如果前一次篩選的項集為空則停止循環，這裡為空， 并不是計算到為空集為止，
# 剛剛我們設定了threshold，我們會在達到這個門檻值的時候終止疊代。
# 将n項集組成n+1項集（上一次的計算結果組成新的項集不斷疊代）
while len(filteredItemSets) > :
# 将k-1項集合并生成k項集
itemSets = combineItemSets(itemSets)
# 篩選符合要求的k項集
filteredItemSets, newSupports = filterBySupport(
transactionSets, itemSets, supportThreshold)
# 儲存新項集的支援度
supports.update(newSupports)
# 儲存符合要求的k項集
itemSetsList.append(filteredItemSets)
return itemSetsList, supports
def createItemSets(transactions):
"""根據事務建立1項集"""
itemSets = []
# 周遊所有事務
for transaction in transactions:
# 周遊事務中項目并構造項集
for item in transaction:
itemSet = [item]
if itemSet not in itemSets:
itemSets.append(itemSet)
# 排序并傳回每一個項集的frozenset
# frozenset是不可變集合，可以作為字典的key
itemSets.sort()
return [frozenset(itemSet) for itemSet in itemSets]
def filterBySupport(transactions, itemSets, threshold):
"""計算項集支援度，并根據支援度門檻值篩選滿足要求的項集"""
itemSetCounts = {}
# 周遊所有事務
for transaction in transactions:
# 周遊項集并計算項集在事務中的出現次數
for itemSet in itemSets:
# 判斷一個集合的所有元素是否都包含于另一個集合
if itemSet.issubset(transaction):
# 如果項集沒有出現過則傳回0
itemSetCount = itemSetCounts.get(itemSet, )
itemSetCounts[itemSet] = itemSetCount +
filteredItems = []
supports = {}
transactionCount = len(transactions)
# 周遊所有的項集計數
for itemSet, itemSetCount in itemSetCounts.items():
# 計算支援度
support = itemSetCount / transactionCount
# 根據門檻值篩選項集
if support >= threshold:
filteredItems.append(itemSet)
# 儲存支援度
supports[itemSet] = support
return filteredItems, supports
def combineItemSets(itemSets):
"""将k-1項集合并成k項集"""
newItemSets = []
itemSetsCount = len(itemSets)
# 周遊提取兩個項集
for itemSet1Index in range(itemSetsCount):
for itemSet2Index in range(itemSet1Index + , itemSetsCount):
itemSet1 = itemSets[itemSet1Index]
itemSet2 = itemSets[itemSet2Index]
# 分别計算兩個項集的差集
diff1 = itemSet1 - itemSet2
diff2 = itemSet2 - itemSet1
# 如果兩個項集各有一個項目不同，其他項目相同則組合成一個新項集
if len(diff1) == and len(diff2) == :
newItemSet = itemSet1 | itemSet2
if newItemSet not in newItemSets:
newItemSets.append(newItemSet)
return newItemSets
注意
這裡面隻實作了支援度的計算，置信度有個公式A與B的并集的支援度除以A的支援度。其實關聯規則的核心思想和周遊方式， 跟支援度（支援度的公式m/n）的計算幾乎一樣，公式不一樣，疊代方式類似，大家可以自己參考實作一下。
有了算法之後，我們看一下如果調用算法實作Apriori的計算。
建立：
apriorisample.py
from common.io.tsv import TsvDataSetReader
from algorithm.apriori import apriori
dataReader = TsvDataSetReader()
transactions = dataReader.loadDataSet('aprioriData.txt')
itemSetsList, supports = apriori(transactions, supportThreshold=)
print(transactions)
/*
Prints:
[['C++ Primer Plus', 'C Primer Plus'],
['C Primer Plus', 'C和指針', 'C陷阱與缺陷', 'C程式設計語言'],
['C Primer Plus', 'C++ Primer Plus', 'C和指針', 'C陷阱與缺陷'],
['C Primer Plus', 'C++ Primer Plus', 'C和指針', 'C++程式設計語言']]
*/
print(itemSetsList)
/*
Prints:
[[frozenset({'C Primer Plus'}),
frozenset({'C++ Primer Plus'}),
frozenset({'C陷阱與缺陷'})],
[frozenset({'C++ Primer Plus', 'C Primer Plus'}),
frozenset({'C Primer Plus', 'C和指針'}),
frozenset({'C++ Primer Plus', 'C和指針'})],
[]]
*/
print(supports)
/*
Prints:
{frozenset({'C Primer Plus'}): ,
frozenset({'C++ Primer Plus'}): ,
frozenset({'C和指針'}): ,
frozenset({'C陷阱與缺陷'}): ,
frozenset({'C++程式設計語言'}): ,
frozenset({'C和指針', 'C Primer Plus'}): ,
frozenset({'C陷阱與缺陷', 'C Primer Plus'}): ,
frozenset({'C和指針', 'C陷阱與缺陷'}): ,
frozenset({'C++程式設計語言', 'C++ Primer Plus'}): ,
frozenset({'C和指針', 'C++ Primer Plus'}): ,
frozenset({'C陷阱與缺陷', 'C++ Primer Plus'}): ,
frozenset({'C++程式設計語言', 'C陷阱與缺陷'}): ,
frozenset({'C++程式設計語言', 'C Primer Plus'}): ,
frozenset({'C和指針', 'C Primer Plus', 'C陷阱與缺陷'}): ,
frozenset({'C程式設計語言', 'C和指針', 'C陷阱與缺陷'}): ,
frozenset({'C++程式設計語言', 'C陷阱與缺陷', 'C++ Primer Plus'}): ,
frozenset({'C++程式設計語言', 'C和指針', 'C陷阱與缺陷'}): ,
frozenset({'C陷阱與缺陷', 'C Primer Plus', 'C++ Primer Plus'}): ,
frozenset({'C++程式設計語言', 'C Primer Plus', 'C++ Primer Plus'}): ,
frozenset({'C++程式設計語言', 'C和指針', 'C Primer Plus'}): }
*/