一批交易可以反覆出現某些組合,即使沒有任何一行事前被標成「模式」。首要問題是精確定義何謂反覆出現;其次,是找出每個符合條件的組合,而不必為所有可能項集作不必要計數。Apriori 用一個簡單的包含關係,把兩個問題連接起來。
關鍵是分清:證明某項集不可能頻繁,與量度其確切支持度,是不同工作。已剪枝提案可能完全不需掃描交易。反過來,通過剪枝的提案仍須計數:必要證據不等於頻繁性的證書。
計交易數,不計同一行內的重複出現
定義 2.1.1
(支持次數與支持度比例)
令 是有限項目全集,數據庫是帶索引的交易清單 ,其中 ,每個 。對項集 ,定義
次數記錄多少筆交易包含 的每個項目。最低支持次數為 時,滿足 的項集稱為頻繁項集。這裏挖掘非空項集,並使用正整數閾值。
每行對某項目的支持次數最多貢獻一次,即使原購物紀錄買了多件相同物品也一樣。兩行內容相同的獨立交易,卻仍計兩次。交易身分與項目數量回答不同問題。
使用四個抽象項目 及六筆合成教學交易。 這類簡寫代表項集 ,不是有次序的字串。
| 交易 | 項目 |
|---|---|
例如, 出現在 ,所以 、。 與 各包含其中一項,卻都沒有同時包含兩項。
證明哪些擴充可以排除
命題 2.1.2
(支持度具反單調性)
若 ,則 且 。因此,若 , 的任何超集都不頻繁;等價地,頻繁項集的每個子集都頻繁。
證明
(嵌套的交易索引集合)
若 ,每筆包含 的交易也包含 。因此, 所計算的交易索引集合,包含於 所計算的集合,得到
若 ,則對每個超集 都有 。取逆否命題,便得頻繁項集的每個子集都頻繁。
這就是 Apriori 使用的向下封閉性。論斷針對同一個固定數據庫及閾值。它沒有說頻繁子集會令較大項集也頻繁:較大集合增加了要求,符合條件的交易可能更少。
對某個 項提案,只需檢查其全部直接 項子集,是否在上一層頻繁族中。每個更小子集都包含於某個直接子集,再用向下封閉性便可涵蓋它們。只要一個直接子集缺席,就有足夠依據剪枝。
分清連接提案、可計數候選與頻繁結果
以 表示大小為 的頻繁項集。為免把剪枝步驟藏起來,以 表示剪枝前的連接提案, 表示保留以供計數的候選。有些描述在剪枝前也使用「候選」一詞;操作本身比命名慣例重要。
固定項目次序 。若 內兩個已排序項集的首 項相同、最後項不同,便把它們連接。接著,若提案某個直接子集不在 ,便剪去它。計算每個餘下候選的支持次數,達到 才保留於 。
例題 2.1.3
(完成 m = 2 的單項與雙項層)
單項及雙項的次數如下:
| 項集 | ||||
|---|---|---|---|---|
| 支持次數 |
| 項集 | ||||||
|---|---|---|---|---|---|---|
| 支持次數 |
全部單項都達標,所以 。把它們連接,產生六個雙項提案。每個提案的單項子集都頻繁,因此六個雙項都接受計數。只有 達到次數閾值,得到
留意 是已計數但未達閾值, 則已計數為零,兩者都不同於「未計數」。
例題 2.1.4
(第三層:計數一個提案、剪去兩個)
到了三項層,共同前綴連接是 、、。這個連接步驟不會產生 : 不在 ,沒有可與 配合的頻繁雙項。
| 連接提案 | 子集判斷 | 有否為自身作交易計數? | 結果 |
|---|---|---|---|
| 全部頻繁 | 有:只有 匹配,次數為 1 | 已計數,但不頻繁 | |
| 不在 | 沒有 | 以 剪枝 | |
| 不在 | 沒有 | 以 剪枝 |
因此 、、。不可能有更大頻繁項集,否則它會有頻繁三項子集。最後的非空頻繁項集,就是四個單項及 的四個成員。
表格同時記錄執行歷史與數學事實。已剪枝紀錄沒有透過自身掃描取得已量度支持次數,卻不表示真實支持度沒有定義:這裏由 得到的界,甚至直接推出 。要分清這種推論與「算法掃描了 」的聲稱。同樣地,格圖顯示全部可能項集,不表示每個都曾產生或計數。
反例模式
直接子集頻繁,是必要而非充分條件
在 時,三個雙項 都頻繁,但 次數只有 1。不同交易可以分別支持不同雙項,而沒有第二筆交易同時包含三項。因此,通過子集檢查只足以讓 接受計數,不能直接標為頻繁。
錯誤在於倒轉了推論。 頻繁會迫使其雙項頻繁;雙項頻繁卻不能迫使 頻繁。
下面的追蹤圖可按任何閾值 m 重播這六筆交易,並把三個判斷分開:連接提案、子集剪枝的證明,以及實際的支持度計數。
為何連接與剪枝不會遺漏頻繁項集
定理 2.1.5
(逐層 Apriori 恰好找出頻繁項集)
對每個 ,經共同前綴連接、直接子集剪枝及計數所得的集族 ,恰好就是所有頻繁 項集的集合。
證明
(以計數保證可靠性,按項集大小歸納證明完整性)
可靠性:只有已量度支持次數達到 的項集才進入 ,所以不會報告非頻繁項集。
完整性:單項層由直接計數得到,這是歸納起點。假設 包含每個頻繁 項集,並任取頻繁 。按向下封閉性,子集 及 都頻繁,因此均在 。它們共享所需前綴,連接就會產生 。 的其他直接子集也全部頻繁,所以剪枝不能移除 。計數再確認其支持度,把它放入 。因此,逐層程序會找出每個非空頻繁項集。
證明透視
每個要素各自保證甚麼
剪枝與計數的工作不同。在完整性的一半中,向下封閉性用了兩次:一次是把 的兩個特定 項子集放進 ,使共同前綴連接能產生 ;另一次是說明其他每個直接子集都在,使剪枝檢驗不會否決 。所選的兩個子集(分別去掉最後一項和倒數第二項)必定符合連接條件,所以只用共同前綴連接並不會損失任何項集。剪枝證明的是排除安全,並不證明留下的項集頻繁;這是計數的工作,它提供可靠性。完整性與支持度檢查一起確立正確性,單獨一項都不足夠。
頻繁項集與關聯規則是不同輸出
對非空、互不相交的項集 ,若 ,規則 的指標為
支持度以全部交易作分母,置信度則只用包含前件 的交易。若 ,提升度定義為
例題 2.1.6
( 的支持度、置信度與提升度)
對 ,支持度為 ,置信度為 ,提升度為 。反轉規則,支持度及提升度不變,置信度卻改為 。分母解釋了這種不對稱;頻繁的無序項集本身並沒有指定方向。
反例模式
較大置信度仍可低於後件的基準比例
規則 的置信度為 ,但全部交易中 出現於 。其提升度為 。在這份數據中,包含 的交易反而比整體數據庫更少出現 。只看表面較大的置信度,就會錯過這項比較。
這裏置信度是經驗條件比例,不是統計置信水平。這個比例及提升度,都不能確立因果機制或保證未來數據的表現。它們首先是用正確分母描述指定交易樣本的指標。
常見錯誤
(以為置信度隨前件單調)
不要沒有新證明,就把支持度的子集規則套到置信度。在這些交易中,;前件加入 後降至 ,加入 卻升至 1。條件比例可以向任何一方改變。
重現頻繁項集階段
這個小型 Python 實作以已排序 tuple 作項集的規範表示,以集合儲存交易。它採用共同前綴連接及直接子集剪枝,交易內的項目次序不影響結果。
from itertools import combinations
transactions = list(map(frozenset, ["ABC", "AB", "AC", "BC", "ABD", "AD"]))
items = tuple("ABCD")
minimum = 2
def support_count(itemset):
return sum(set(itemset).issubset(row) for row in transactions)
def join(previous):
proposals = set()
for left, right in combinations(sorted(previous), 2):
if left[:-1] == right[:-1]:
proposals.add(left + (right[-1],))
return sorted(proposals)
previous = set()
proposals = [(item,) for item in items]
level = 1
counted_candidates = 0
while proposals:
candidates = [
candidate for candidate in proposals
if level == 1 or all(
subset in previous for subset in combinations(candidate, level - 1)
)
]
measured = {candidate: support_count(candidate) for candidate in candidates}
counted_candidates += len(candidates)
frequent = {candidate: count for candidate, count in measured.items() if count >= minimum}
print(level, [("".join(candidate), frequent[candidate]) for candidate in sorted(frequent)])
previous = set(frequent)
proposals = join(previous)
level += 1
print("containment checks", counted_candidates * len(transactions))
輸出的頻繁層先是 ,再是 ,最後第三層為空。計數對象是四個單項、六個雙項及一個三項;十一個候選各對六行,得到 66 次候選與交易包含檢查。
這個數字不是 66 次數據庫掃描,也不是執行時間公式。一層的全部候選可以在一次數據庫掃描內計數;小程式只是把逐候選工作明確展示。顯示輸入表,並沒有暗中替 或 作支持度掃描。
練習
快速檢查
(使用相同六筆交易,改設 。寫出 與 。第二頻繁層能產生三項提案嗎?會否遺漏更大的頻繁項集?)
先計算單項與雙項的次數。
解答 · 答案
,。唯一頻繁雙項沒有另一個頻繁雙項可供連接,所以不產生三項提案。頻繁三項必須有全部雙項頻繁,這裏不可能成立,因此沒有遺漏更大頻繁項集。
快速檢查
(在 下,為甚麼 被剪枝?由此得到甚麼上界?它的確切次數在數學上是否沒有定義?事後直接檢查交易,求出該次數,並解釋這為何不改變先前的執行歷史。)
看 的哪個直接子集不在 。
解答 · 答案
的次數為 1,並且不在 ,所以 。無論挖掘過程有否量度,真實次數都是有定義的。另行檢查只找到 ,所以次數為 1。這個獨立計數並不表示先前的 Apriori 過程掃描過已被剪去的提案。
快速檢查
(對 ,計算支持度、置信度與提升度。有多少筆交易支持它觀察到的完美置信度?這對把該規則當作全稱陳述有何啟示?)
使用 、 與 。
解答 · 答案
、、,所以支持度為 ,置信度為 1,提升度為 。只有 包含前件,兩者都包含 ,這確立的是樣本中的比例,並不能確立將來每筆包含 的交易都必定包含 。
快速檢查
(把每筆交易複製一次,得到十二行。支持次數、支持度分數、置信度與提升度會怎樣?若絕對閾值仍為 ,與原數據庫相比,哪些項集新成為頻繁?保留原來的最小支持度分數 是否有相同效果?)
比較次數與分母如何變化。
解答 · 答案
每個支持次數都加倍,但分數、置信度與提升度不變,因為相應的分母同樣加倍。保持絕對閾值 時,原來次數為一的項集被納入: 新成為頻繁。改為保留支持度分數 ,則要求十二行中至少有四行,所以原來的頻繁族得以保持。必須說明閾值的單位。