關聯規則挖掘概述

在網上購物時，系統會主動推薦一些商品，贈送一些優惠券，并且這些推薦的商品和贈送的優惠券往往都能直抵我們的需求，誘導我們消費。這背後主要使用使用了關聯分析技術，通過分析哪些商品經常一起購買，可以幫助商家了解使用者的購買行為。從大規模資料中挖掘對象之間的隐含關系被稱為關聯分析（associate analysis）或者關聯規則學習（associate rule learning），其可以揭示資料中隐藏的關聯模式，幫助人們進行市場運作，決策支援等。本部落格将介紹關聯規則挖掘及其在文本資料集中的應用。

關聯規則

正如上面所述，關聯規則最早是為了進行購物籃分析（Market Basket Analysis）而提出的，例如：在超市銷售資料中發現了規則 { o n i o n s p o , p o t a t o e s } ⇒ { b u r g e r } \{\rm{onions po,potatoes\}\Rightarrow}\{burger\} {onionspo,potatoes}⇒{burger}，可能訓示如果一個顧客同時購買了onions和potatoes，那麼他很可能也會購買hamburger meat，這些資訊可以用于指導市場活動，比如商品定價，商品擺放位置。

定義

1993年Agrawal等人在論文Mining association rules between sets of items in large databases中首先提出了關聯規則的概念：

I = { i 1 , i 2 , … , i n } I=\{i_1,i_2,\dots,i_n\} I={i1​,i2​,…,in​}被稱為項集（items），其中 i j ∈ { 0 , 1 } i_j\in \{0,1\} ij​∈{0,1}被稱為項。

D = { t 1 , t 2 , … , t m } D=\{t_1,t_2,\dots,t_m\} D={t1​,t2​,…,tm​}被稱為資料庫（database），其中 t k t_k tk​被稱為事務（transaction）。

事務是項的集合，即事務是 I I I的一個子集， t k ⊆ I t_k\sube I tk​⊆I，每個事務用一個唯一的transaction ID進行辨別。規則（rule）定義如下：

X ⇒ Y ， 其 中 X , Y ⊆ I X\Rightarrow Y，其中X,Y\sube I X⇒Y，其中X,Y⊆I

每條規則由兩個不同項目集（itemset） X , Y X,Y X,Y組成，其中 X X X稱為前提或left-hand-side（LHS）， Y Y Y稱為結論或right-hand-side（RHS）。圖下表所示：

transaction ID	milk	bread	butter	beer	diapers
1	1	1
2	1
3	1	1
4	1	1	1
5	1

項集 I = { m i l k , b r e a d , b u t t e r , b e e r , d i a p e r s } I=\{milk,bread,butter,beer,diapers\} I={milk,bread,butter,beer,diapers}，每一個條目中，1表示項出現在相應的事務中，0表示項沒有出現在事務中。 { b u t t e r , b r e a d } ⇒ { m i l k } \{butter,bread\}\Rightarrow\{milk\} {butter,bread}⇒{milk}是一條關聯規則，表示如果butter和bread同時被購買了，milk也會被購買。當然這個例子非常的簡單，在實際應用中，資料庫通常包含成千上萬的事務，一條規則需要上百個事務的支援才能被認為是統計顯著的。

有用的概念

為了從所有可能的規則集中選出有趣的規則（interesting rules），需要用到各種重要度（significance）、興趣度（interest）限制，其中最有名的是支援度（support）和置信度（confidence）。

支援度

支援度用來表示項目集在資料庫中的出現頻率。 對于資料庫 D D D中的項目集 X X X，其支援度定義為：資料庫中包含項目集 X X X的事務數 t t t與所有事務數 T T T之比

s u p p ( X ) = ∣ { t ∈ T ; X ⊆ t } ∣ ∣ T ∣ supp(X)=\frac{|\{t\in T;X\sube t\}|}{|T|} supp(X)=∣T∣∣{t∈T;X⊆t}∣​

以上面例子為例，項目集 X = { b e e r , d i a p e r s } X=\{beer,diapers\} X={beer,diapers}的支援度為 1 / 5 = 0.2 1/5=0.2 1/5=0.2，因為它出現在20%的事務中。

置信度

置信度用來衡量規則的可信程度。 對于規則 X ⇒ Y X\Rightarrow Y X⇒Y，其置信度定義為：資料庫中同時包含 X ， Y X，Y X，Y的事務數與包含 X X X的事務數之比

c o n f ( X ⇒ Y ) = s u p p ( X ∪ Y ) s u p p ( X ) conf(X\Rightarrow Y)=\frac{supp(X\cup Y)}{supp(X)} conf(X⇒Y)=supp(X)supp(X∪Y)​

置信度可以看作是條件機率 P ( X ∪ Y ∣ X ) P(X\cup Y|X) P(X∪Y∣X)，以上面例子為例，規則 { b u t t e r , b r e a d } ⇒ { m i l k } \{butter,bread\}\Rightarrow\{milk\} {butter,bread}⇒{milk}的置信度為 0.2 / 0.2 = 1.0 0.2/0.2=1.0 0.2/0.2=1.0，因為項目集 X ∪ Y = { b u t t e r , b r e a d , m i l k } X\cup Y=\{butter,bread,milk\} X∪Y={butter,bread,milk}的支援度為 1 / 5 = 0.2 1/5=0.2 1/5=0.2，項目集 X = { b u t t e r , b r e a d } X=\{butter,bread\} X={butter,bread}的支援度為 1 / 5 = 0.2 1/5=0.2 1/5=0.2。規則 { b u t t e r , b r e a d } ⇒ { m i l k } \{butter,bread\}\Rightarrow\{milk\} {butter,bread}⇒{milk}的置信度為1意味着每次顧客購買了butter和bread後，一定也會購買milk。

Lift

一個規則的lift定義為

l i f t ( X ⇒ Y ) = c o n f ( X ⇒ Y ) s u p p ( Y ) = s u p p ( X ∪ Y ) s u p p ( X ) × s u p p ( Y ) lift(X\Rightarrow Y)=\frac{conf(X\Rightarrow Y)}{supp(Y)}=\frac{supp(X\cup Y)}{supp(X)\times supp(Y)} lift(X⇒Y)=supp(Y)conf(X⇒Y)​=supp(X)×supp(Y)supp(X∪Y)​

例如，規則 { m i l k , b r e a d } ⇒ { b u t t e r } \{milk,bread\}\Rightarrow \{butter\} {milk,bread}⇒{butter}的lift值為 0.2 0.4 × 0.4 = 1.25 \frac{0.2}{0.4\times 0.4}=1.25 0.4×0.40.2​=1.25。如果一個規則的lift值等于1，這暗示前提和結論對應的事件互相獨立；如果lift值大于1，訓示了兩個事件之間的互相依賴程度，值越大，關聯越強；如果lift值小于1，表明一個item的出現對其他item的出現存在消極影響（相斥），反之亦然（其中一個出現另一個一般不會出現）。lift的意義在于其即考慮了置信度也考慮了整個資料集中結論的支援度。

Conviction

一個規則的conviction定義如下：

c o n v ( X ⇒ Y ) = 1 − s u p p ( Y ) 1 − c o n f ( X ⇒ Y ) conv(X\Rightarrow Y)=\frac{1-supp(Y)}{1-conf(X\Rightarrow Y)} conv(X⇒Y)=1−conf(X⇒Y)1−supp(Y)​

conviction表示 X X X出現而 Y Y Y不出現的機率，即規則預測錯誤的機率。例如，規則 { m i l k , b r e a d } ⇒ { b u t t e r } \{milk,bread\}\Rightarrow \{butter\} {milk,bread}⇒{butter}的lift值為 1 − 0.4 1 − 0.5 = 1.2 \frac{1-0.4}{1-0.5}=1.2 1−0.51−0.4​=1.2，表明這條規則的出錯率是20%。

處理過程

關聯規則隻有滿足最小支援度門檻值和最小置信度門檻值，這條規則才能認為是有趣的。關聯規則生成通常分成兩個獨立的步驟：

1. 利用最小支援度門檻值從資料庫中找出所有的頻繁項集（frequent itemsets）；
2. 利用最小置信度門檻值從這些頻繁項集中生成規則。

其中，生成規則的階段是直接的，但是尋找頻繁項集需要更多的精力，因為其涉及搜尋所有可能項目集，項目集的大小是 I I I的幂集，大小為 2 n − 1 2^n-1 2n−1（除去沒有意義的空集）。頻繁項集有兩個非常重要性質：

• 性質1：頻繁項集的所有非空子集也是頻繁的。
• 性質2：非頻繁項集的所有超集是非頻繁的。

如上圖，方塊的顔色代表包含該項目集的事務數目，低一層的項目集最多能包含其所有父類的最小項目數，如： { a c } \{ac\} {ac}最多有 m i n ( a , c ) min(a,c) min(a,c)個項目。利用這個性質，許多高效的算法（例如：Apriori、Eclat）可以用來發現所有的頻繁項集。

其他有趣度度量方式

采用标準方法尋找關聯規則可能發現許多虛假的關聯規則。例如：在一個資料庫中共包含10000條事務，其中包含項目 X X X的事務有7000條，包含項目 Y Y Y的事務有7500條，同時包含項目 X , Y X,Y X,Y的事務有5000條，那麼項目集 X ∪ Y X\cup Y X∪Y的支援度為0.5，關聯規則 X ⇒ Y X\Rightarrow Y X⇒Y的置信度為0.71，當最小支援度門檻值和最小置信度門檻值均設為0.5是，關聯規則 X ⇒ Y X\Rightarrow Y X⇒Y将被認為是有趣的，即 X X X和 Y Y Y之間存在強關聯規則。但是，在不考慮前提 X X X的情況下， Y Y Y的機率為0.75，也就是說在有 X X X的情況下， Y Y Y發生的機率反而降低了，即事件 X X X和 Y Y Y是相斥的。是以，需要一些其他新穎的有趣度度量方式，如：All-confidence，Convition，Leverage，Lift等，也可以用到一些其他的統計檢測的方式。

算法

頻繁項集挖掘算法可以按照搜尋方式和支援度計算公式進行分類，按搜尋方式分，可以分為BFS（Breath-First Search）和DFS（Depth-First Search）

• BFS寬度優先搜尋：先産生所有頻繁(k-1)-項集，再根據頻繁(k-1)-項集計算頻繁k-項集。
• DFS深度優先搜尋：DFS通過遞歸調用産生頻繁項集，頻繁項集的産生次序與其長度無關。

從支援度計算方式看，可以分為計數法和交集法

• 計數法：直接計算項集在資料庫中的發生數，逐一掃描資料庫中所有事務，如果某候選項集在某個事務中出現，那麼該候選項集的支援數加1。
• 交集法：将包含項集 X X X的事務放入集合 X . t l i s t X.tlist X.tlist，如果要計算候選項集 C = X ∪ Y C=X\cup Y C=X∪Y，可以通過對 X . t l i s t X.tlist X.tlist和 Y . t l i s t Y.tlist Y.tlist求交集，即 C . t l i s t = X . t l i s t ∩ Y . t l i s t C.tlist=X.tlist\cap Y.tlist C.tlist=X.tlist∩Y.tlist。 C . t l i s t C.tlist C.tlist中包含的元素個數就是候選項集 C C C的支援數。

對應的挖掘算法如下圖所示：

Apriori

Apriori是廣度優先搜尋的典型算法，由Agrawal于1994年提出。Apriori算法首先産生頻繁1-項集 L 1 L_1 L1​，然後對 L 1 L_1 L1​中隻包含一個不同項的兩個項集進行組合，産生頻繁2-項集 L 2 L_2 L2​。重複該過程，直至某個 r r r值使得 L r L_r Lr​為空。雖然根據頻繁項集的性質，Apriori不需要計數所有的 L r L_r Lr​項集，但是對所有候選項集進行計數同樣是一個巨大的工程。

FP-growth

FP代表frequent pattern，FP-growth是一種無需産生候選項集的深度優先搜尋算法。FP-growth将資料庫中的頻繁1-項集壓縮為一棵頻繁模式樹（FP-Tree），同時保留了其中的關聯資訊，然後采用遞歸的方式周遊這棵樹生成頻繁模式。相比Apriori算法其主要提升點展現在：（1）将資料庫中的頻繁1-項集壓縮為一棵頻繁模式樹，避免了計數時反複掃描資料庫；（2）基于FP-Tree的挖掘采用遞歸方式生成長頻繁模式，避免了産生大量的候選項集；（3）采用分治的政策将FP-Tree劃分成若幹個事務子集，減小了搜尋規模。

其他

Partition将資料庫分成若幹部分，先分别找出每一部分的頻繁項集，然後将這些局部頻繁項集合并起來，掃描整個資料庫，得到最終的頻繁項集。Eclat是一種基于交集法的深度優先搜尋算法，最大的特點是适合并行計算。

總結

這是本人第一次接觸關聯規則挖掘，本部落格也隻簡單的記錄關聯規則挖掘的一些基本概念，下一步将會将會進行文本關聯規則挖掘，具體的算法将會在之後的部落格中介紹，希望能多多交流。

參考文獻

Association rule learning

關聯規則

R語言 關聯規則

萬曉鴿. 文本關聯規則挖掘方法研究與應用[D]. 西安建築科技大學, 2010.

陳曉雲. 文本挖掘若幹關鍵技術研究[D]. 複旦大學, 2005.