本文介紹資料挖掘中關聯分析的基本概念與基本術語。
基本概念與術語
1. 事務：
一條資料也叫一條事務(transaction)，資料的ID即事務的ID，簡寫為TID，表6-1是購物籃事務的例子，可以了解為顧客的購物記錄。
2. 二進制表示 （這個術語暫時不了解也沒關系）
如表6-2所示，每行對應一個事務，每一列對應一個項。
項用二進制變量表示：如果項在事務中出現，則它的值是1，否則為0。
因為通常認為項在事務中出現比不出現更重要，是以項是非對稱(asymmetric)二進制變量。
3. 關聯分析(association analysis)：
用于發現隐藏在大型資料之中的有意義的聯系。
所發現的聯系可以用關聯規則(association rule)或者頻繁項集表示。
表6-1可以提取出如下規則：
{尿布} → {啤酒}
表示尿布和啤酒之間存在着很強的聯系，因為很多購買尿布的顧客也購買了啤酒。
4. 項集和支援度計數
令 I = { i 1 , i 2 , … , i d } I=\{i_1, i_2, …, i_d\} I={i1,i2,…,id}是資料中所有項的集合， T = { t 1 , t 2 , … , t N } T = \{t_1, t_2, …, t_N\} T={t1,t2,…,tN} 是所有事務的集合，則每個事務 t i t_i ti包含的項集都是I的子集。
在關聯分析中，包含0個或多個的項的集合叫 項集(itemset) 。如果一個項集包含了k個項，則稱它為 k-項集。
項集的 支援度計數 σ ( X ) σ(X) σ(X) ：（X表示某項集）
支援度計數表示包含了項集X的事務個數。
5. 關聯規則：
關聯規則是形如 X → Y X → Y X→Y 的蘊涵表達式，其中 X 和 Y 是不相交的項集。
關聯規則的強度可以用它的 支援度(support) 和 置信度(confidence) 度量。
支援度 ( s ) 表示同時包含項集 X、Y 的事務總數，即該規則在總資料集出現的頻繁程度。
置信度 ( c ) 表示 Y 在包含項集 X 的事務中出現的頻繁程度。
他們的計算公式如下：
N: 事務總數
由公式(6-1)可以看出，規則 X → Y X → Y X→Y 的支援度僅依賴于其對應項集 X ∪ Y X∪Y X∪Y的支援度，是以為了提高效率，避免不必要的計算，目前的大多數關聯規則挖掘算法都将關聯規則挖掘任務分解為以下兩個主要的子任務：
1. 頻繁項集産生：目标是發現滿足最小支援度門檻值的所有項集，這些項集稱作頻繁項集(frequent itemset)。
2. 規則的産生：目标是從上一步發現的頻繁項集中提取所有高置信度的規則，這些規則稱為強規則(strong rule)。
這樣就避免了非頻繁項集置信度的計算，節省了很多時間。
然而，頻繁項集産生所需要的計算量也是很大的，發現頻繁項集的一種原始方法是确定每個 候選項集(candidate itemset) 的支援度計數。為了完成這一任務，必須将每個候選項集與每個事務進行比較，計算每個候選項集的支援度，這個過程中也包含着很多不必要的計算，是以還需要降低頻繁項集的計算複雜度，目前常用以下兩種方法：
1. 減少候選項集的數目：常用基于先驗(apriori)原理的算法。
2. 減少比較次數：使用更進階的資料結構，用于存儲候選項集或壓縮資料集。
6. 格結構(lattice structure)
格結構常常被用來枚舉所有可能的項集。圖 6-1 是 I = { a , b , c , d , e } I=\{a, b, c, d, e\} I={a,b,c,d,e}的項集格。一般包含k個項的資料集可能産生 2 k − 1 2^k - 1 2k−1個項集，不包括空集在内。是以當 k 非常大時，項集的搜尋空間是指數規模的。
參考資料：
《資料挖掘導論》