設定與約定
定義 2.2.1
(交易、支持度與頻繁性)
- 一個非空有限項目全集 。
- 項集的定義域是 的所有子集所成的集合,即冪集 。其中包括 及 。
- 一個有限非空交易多重集 ,其中每項交易 都是一個集合。兩項交易作為集合可以相等,但仍分開計算。
- 項集 的支持度計數為
按索引計算,因此重複的交易各自貢獻一次。
- 一個正整數最小支持度 。當 時,項集 稱為頻繁。
命題 2.2.2
(支持度具反單調性)
若 ,則 。
證明
(較大的項集被較少的交易包含)
每項包含 的交易也包含 ,所以為 計算的索引集是為 計算的索引集的子集。
Apriori 正是依賴這個性質。
三個定義
定義 2.2.3
(閉項集、閉頻繁項集與極大頻繁項集)
- 若每個真超集 都滿足 ,則項集 稱為閉項集。
- 若項集 既是閉項集又是頻繁項集,則稱 為閉頻繁項集。
- 若項集 是頻繁項集,而且它沒有任何真超集是頻繁的,則稱 為極大頻繁項集。
常見錯誤
(混淆閉與極大)
閉性詢問更大的項集是否保持完全相同的次數;極大頻繁性詢問更大的項集是否仍達閾值。因此,閉項集仍可有更大的頻繁擴展,只要該擴展的支持度較小。在下面的例題中, 的支持度為 並且是閉項集,但頻繁集 (支持度 )包含它,所以 不是極大項集。
以交集定義閉包
設 具有正支持度。其閉包定義為
我們只在 時使用這個構造。此時被取交集的集族非空,所以交集是良好定義的。
當 時,該集族為空,公式需要額外的約定。一個常見約定是把空交集視為 ;本章則在此情況下不定義閉包。閉性本身仍按上面的定義:支持度為零的項集是閉項集,當且僅當它等於 。事實上,若 ,則其真超集 的支持度亦為 ,所以 不是閉項集。若 ,它沒有真超集,因此空虛地是閉項集,即使其支持度為 亦然。這個結論並不需要 的值。在本章中,由於 ,「閉頻繁」總是涉及正支持度。
引理 2.2.4
(閉包保持支持度)
若 ,則 且 。
證明
(兩個集合被同一批交易包含)
集族中每項交易都包含 ,所以它們的交集亦包含 。由此得 。
現在比較兩者的支持度。
- 若 ,則 是被取交集的集合之一,所以 。
- 反之,若 ,則 。
因此兩個集合所計算的索引完全相同。
引理 2.2.5
(閉項集是閉包的不動點)
若 ,則 是閉項集當且僅當 。
證明
(閉包是支持度相同的最大超集)
設 且 。包含 的交易的索引,構成包含 的交易的索引的子集。兩個索引集大小相同,所以兩者相等。因此每項包含 的交易都包含 ,由此得 。
這表明 是 具有相同支持度的最大超集。
- 若 ,則 是一個支持度相等的真超集,所以 不是閉項集。
- 若 ,則每個真超集 的支持度都不等於 ,因為支持度相等會迫使 。由反單調性,該支持度嚴格較小,所以 是閉項集。
概念視角結構
閉項集就是交易的交集
的超集構成龐大的集族 。閉包 是該集族中的一個特定成員,但它是由交易計算出來的,而不是透過搜尋超集得到。具正支持度的閉項集,恰好就是交易的非空子族的交集。一個方向就是 的定義。另一個方向:若 ,其中 是交易的非空子族,則 的每個成員都包含 ,所以 ,因而 。這樣的交集不一定是你最初所取的某個特定 的超集。
極大蘊含閉
定理 2.2.6
(極大頻繁項集都是閉項集)
每個極大頻繁項集都是閉項集。
證明
(保持支持度的超集會是頻繁的)
設 為極大頻繁項集。則 ,所以 具有正支持度。
假設 不是閉項集。那麼存在某個真超集 ,使得 。這樣 就是 的一個頻繁真超集,與極大性矛盾。
反例模式
閉頻繁項集不一定是極大的
命題:每個閉頻繁項集都是極大頻繁項集。取 、,交易為 、、、、、。項集 出現在前三項交易中,所以 。它的超集 (支持度 )、(支持度 )及 (支持度 )都嚴格小於 ,所以 是閉頻繁項集。然而 是 的頻繁真超集,所以 不是極大項集。更正後的陳述就是上面證明的蘊含:極大頻繁蘊含閉,反之不然。
重構支持度
命題 2.2.7
(由閉頻繁項集恢復支持度)
對任何 , 是頻繁項集當且僅當 有一個頻繁的閉超集。在此情況下,
證明
(閉包取得最大值)
設 是頻繁項集。由閉包的兩個引理, 是閉項集,包含 ,且支持度為 。由反單調性,任何其他超集 都有 。所以最大值在 處取得,並等於 。
反之,若 有一個頻繁超集,則 至少等於該超集的支持度,所以 是頻繁項集。
證明透視
為甚麼閉包是合適的見證
這個證明只有一步不尋常:指出取得最大值的超集,就是 。反單調性只給出對每個超集 都有 的不等式,所以最大值不會超過 。要取得等號,需要一個既是閉的、支持度又相等的超集,這正是兩個閉包引理所提供的。「 是頻繁的」這個假設,用來確保見證 是頻繁的,這就是為何最大值取遍閉頻繁集。對非頻繁的 ,陳述只關乎隸屬關係:此時沒有閉頻繁超集,因為這樣的超集的支持度會迫使 頻繁。
因此,閉頻繁集連同其支持度,構成一個無損的摘要:你可以從中還原每個頻繁項集及其確切支持度。
極大頻繁集只告訴你哪些項集是頻繁的:恰好是某個極大集的子集。它們給出每個支持度的下界 ,但不給出確切計數。最後一個例題展示兩個具有相同極大集族但支持度不同的數據庫。
例題
例題 2.2.8
(十六個項集的支持度與閉包)
取 及 。交易多重集為:
| 索引 | 交易 |
|---|---|
注意 與 是重複的,並計算兩次。閉包只在支持度為正時計算。最後一列對每個項集(包括支持度為零者)都使用閉性的定義。
| 包含它的交易 | supp | 頻繁? | 閉? | ||
|---|---|---|---|---|---|
| 全部六項 | 6 | 是 | 是 | ||
| 1,2,3,4,6 | 5 | 是 | 是 | ||
| 1,2,3,5 | 4 | 是 | 是 | ||
| 1,2,4 | 3 | 是 | 否 | ||
| 4,5 | 2 | 是 | 是 | ||
| 1,2,3 | 3 | 是 | 是 | ||
| 1,2,4 | 3 | 是 | 是 | ||
| 4 | 1 | 否 | 否 | ||
| 1,2 | 2 | 是 | 否 | ||
| 5 | 1 | 否 | 是 | ||
| 4 | 1 | 否 | 否 | ||
| 1,2 | 2 | 是 | 是 | ||
| 無 | 0 | 否 | (未定義) | 否 | |
| 4 | 1 | 否 | 是 | ||
| 無 | 0 | 否 | (未定義) | 否 | |
| 無 | 0 | 否 | (未定義) | 是 |
全部六項交易的交集是 ,所以 是閉項集,支持度為 ,並且是頻繁項集。
頻繁項集(9 個)是 。閉頻繁項集(7 個)是 、、、、、、。極大頻繁項集(2 個)是 (因為 )和 (因為 、 及 的支持度均為 )。兩者都是閉項集,正如關於極大項集的定理所預測。
例題 2.2.9
(由閉頻繁集重構支持度)
在同一個數據庫中,由閉頻繁項集 、、、、、、 恢復支持度。
- 對於 :頻繁閉超集為 及 。最大值為 ,與 相符。
- 對於 :唯一的頻繁閉超集是 ,得出 。
- 對於 :沒有頻繁閉超集,所以 不是頻繁項集,與 一致。
例題 2.2.10
(極大集會遺失計數)
從上面的數據庫刪去 ,得到第二個由五項交易組成的多重集。支持度的變化如下: 變為 , 變為 ,其他所有支持度保持不變。頻繁集族完全相同,所以極大集仍然是 。然而, 的支持度在一個數據庫中是 ,在另一個中是 。單憑極大集無法區分這兩個數據庫,閉頻繁集卻可以: 變為 , 變為 。
常見錯誤
(把重複的交易只計一次)
在上面的數據庫中, 與 作為集合相等,但是兩項獨立的交易。若把它們合併,, 就會錯誤地變成非頻繁。支持度計數是按索引計算的,重複的交易各自貢獻一次。
練習
快速檢查
(取 、,交易為 、、。求 、 及 。、、 之中哪些是閉項集?)
把包含各項集的交易取交集。
解答 · 答案
三項交易都包含 ,而 ,所以 。包含 的交易是前兩項,所以 。包含 的交易是後兩項,所以 。三者都不等於各自的閉包,所以都不是閉項集。尤其是這裏 不是閉項集,因為全部交易的交集不是空集。
快速檢查
(對同一個數據庫,列出閉頻繁項集及其支持度,以及極大頻繁項集。)
先算出所有支持度:,而 、 的支持度為 。
解答 · 答案
支持度為 、、、、、、、。頻繁項集是 。其中的閉項集是 、 及 ,因為 已證明不是閉項集。極大頻繁項集是 與 。兩者都是閉項集,與預期相符;而 是閉頻繁項集,卻不是極大項集。
快速檢查
(只用同一數據庫的閉頻繁項集 、、,求 與 ,並判斷 是否頻繁。)
應用重構公式。
解答 · 答案
的頻繁閉超集只有 ,所以 。 的頻繁閉超集只有 ,所以 。沒有閉頻繁項集包含 ,所以 不是頻繁項集;事實上 。
路線圖與檢查清單
- 固定 、多重集 及整數 。重複的交易須分開計算。
- 列出所有支持度,或用 Apriori 挖掘頻繁集。
- 對每個頻繁的 ,透過把包含它的交易取交集來計算 。若 ,則把 標記為閉項集。
- 記住空集:只要所有交易的交集為空,空集就是閉項集。
- 若沒有任何頻繁集真包含頻繁的 ,則把 標記為極大。驗證每個極大集都出現在閉項集之中。
- 如存在的話,舉出一個閉但非極大的頻繁集。
- 從閉頻繁集重構支持度。極大集只用於判斷是否屬於頻繁集族。
- 把零支持度的約定與正支持度的交集構造分開處理。