分類目錄：《深入理解機(jī)器學(xué)習(xí)》總目錄

許多商業(yè)企業(yè)在日復(fù)一日的運(yùn)營(yíng)中積聚了大量的數(shù)據(jù)。例如，食品商店的收銀臺(tái)每天都收集大量的顧客購物數(shù)據(jù)。下圖給出一個(gè)這種數(shù)據(jù)的例子，通常稱作購物籃事務(wù)（Market Basket Transaction）。表中每一行對(duì)應(yīng)一個(gè)事務(wù)，包含一個(gè)唯一標(biāo)識(shí)TID和給定顧客購買的商品的集合。零售商對(duì)分析這些數(shù)據(jù)很感興趣，以便了解他們的顧客的購買行為。可以使用這種有價(jià)值的信息來支持各種商務(wù)應(yīng)用，如市場(chǎng)促銷，庫存管理和顧客關(guān)系管理等。

關(guān)聯(lián)規(guī)則挖掘系列文章主要是介紹一種稱作關(guān)聯(lián)分析（Association Analysis）的方法，用于發(fā)現(xiàn)隱藏在大型數(shù)據(jù)集中的有意義的聯(lián)系。所發(fā)現(xiàn)的聯(lián)系可以用關(guān)聯(lián)規(guī)則（Association Rule）或頻繁項(xiàng)集的形式表示。例如，從上圖數(shù)據(jù)中可以提取出如下規(guī)則：

尿布 → 啤酒

該規(guī)則表明尿布和啤酒的銷售之間存在著很強(qiáng)的聯(lián)系，因?yàn)樵S多購買尿布的顧客也購買啤酒。零售商們可以使用這類規(guī)則，幫助他們發(fā)現(xiàn)新的交叉銷售商機(jī)。

除了購物籃數(shù)據(jù)外，關(guān)聯(lián)分析也可以應(yīng)用于其他領(lǐng)域，如生物信息學(xué)、醫(yī)療診斷、網(wǎng)頁挖掘和科學(xué)數(shù)據(jù)分析等。例如，在地球科學(xué)數(shù)據(jù)分析中，關(guān)聯(lián)模式可以揭示海洋、陸地和大氣過程之間的有趣聯(lián)系。這樣的信息能夠幫助地球科學(xué)家更好地理解地球系統(tǒng)中不同的自然力之間的相互作用。盡管這里提供的技術(shù)一般可以都用于更廣泛的數(shù)據(jù)集，但是為了便于解釋，討論將主要集中在購物籃數(shù)據(jù)上。

在對(duì)購物籃數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析時(shí)，需要處理兩個(gè)關(guān)鍵的問題：第一，從大型事務(wù)數(shù)據(jù)集中發(fā)現(xiàn)模式可能在計(jì)算上要付出很高的代價(jià)：第二，所發(fā)現(xiàn)的某些模式可能是虛假的，因?yàn)樗鼈兛赡苁桥既话l(fā)生的。

二元表示

購物籃數(shù)據(jù)可以用下圖所示的二元形式來表示，其中每行對(duì)應(yīng)一個(gè)事務(wù)，而每列對(duì)應(yīng)一個(gè)項(xiàng)。項(xiàng)可以用二元變量表示，如果項(xiàng)在事務(wù)中出現(xiàn)，則它的值為1，否則為0。因?yàn)橥ǔＵJ(rèn)為項(xiàng)在事務(wù)中出現(xiàn)比不出現(xiàn)更重要，因此項(xiàng)是非對(duì)稱（Asymmetric）二元變量。或許這種表示是實(shí)際購物籃數(shù)據(jù)極其簡(jiǎn)單的展現(xiàn)，因?yàn)檫@種表示忽略數(shù)據(jù)的某些重要的方面，如所購商品的數(shù)量和價(jià)格等。

項(xiàng)集和支持度計(jì)數(shù)

令 I = { i 1 , i 2 , ? ? , i d } I=\{i_1, i_2, \cdots, i_d\} I={i1?,i2?,?,id?}是購物籃數(shù)據(jù)中所有項(xiàng)的集合，而 T = { t 1 , t 2 , ? , t N } T=\{t_1, t_2, \cdot, t_N\} T={t1?,t2?,?,tN?}是所有事務(wù)的集合。每個(gè)事務(wù)$t_i$包含的項(xiàng)集都是$I$的子集。在關(guān)聯(lián)分析中，包含0個(gè)或多個(gè)項(xiàng)的集合被稱為項(xiàng)集（Itemset）。如果一個(gè)項(xiàng)集包含$k$個(gè)項(xiàng)，則稱它為$k$-項(xiàng)集。例如，{啤酒，尿布，牛奶}是一個(gè)3-項(xiàng)集，而空集是指不包含任何項(xiàng)的項(xiàng)集。

事務(wù)的寬度定義為事務(wù)中出現(xiàn)項(xiàng)的個(gè)數(shù)。如果項(xiàng)集$X$是事務(wù)$t_j$的子集，則稱事務(wù)$t_j$包括項(xiàng)集$X$。例如，在上圖中第二個(gè)事務(wù)包括項(xiàng)集{面包，尿布}，但不包括項(xiàng)集{面包，牛奶}。項(xiàng)集的一個(gè)重要性質(zhì)是它的支持度計(jì)數(shù)，即包含特定項(xiàng)集的事務(wù)個(gè)數(shù)。數(shù)學(xué)上，項(xiàng)集$X$的支持度計(jì)數(shù)$\sigma (X)$可以表示為：
σ ( X ) = ∣ { t i ∣ X ? t i , t i ∈ T } ∣ \sigma(X)=|\{t_i|X\subseteq t_i, t_i\in T\}| σ(X)=∣{ti?∣X?ti?,ti?∈T}∣

其中，符號(hào)$|?|$表示集合中元素的個(gè)數(shù)。在上圖顯示的數(shù)據(jù)集中，項(xiàng)集{啤酒，尿布，牛奶}的支持度計(jì)數(shù)為2，因?yàn)橹挥?個(gè)事務(wù)同時(shí)包含這3個(gè)項(xiàng)。

關(guān)聯(lián)規(guī)則（Association Rule）

關(guān)聯(lián)規(guī)則是形如$X\to Y$的蘊(yùn)涵表達(dá)式，其中$X$和$Y$是不相交的項(xiàng)集，即$X\cap Y=?$。關(guān)聯(lián)規(guī)則的強(qiáng)度可以用它的支持度（Support）和置信度`（Confidence）度量。支持度確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，而置信度確定$Y$在包含$X$的事務(wù)中出現(xiàn)的頻繁程度。支持度$s$和置信度$c$這兩種度量的形式定義如下：
$$\begin{array}{rl}s(X\to Y)& =\frac{\sigma (X\cup Y)}{N}\\ c(X\to Y)& =\frac{\sigma (X\cup Y)}{\sigma (X)}\end{array}$$

考慮規(guī)則{牛奶，尿布} → {啤酒}，由于項(xiàng)集{牛奶，尿布，啤酒}的支持度計(jì)數(shù)是2，而事務(wù)的總數(shù)是5，所以規(guī)則的支持度為$\frac{2}{5}=0.4$。置信度是項(xiàng)集{牛奶，尿布，啤酒}的支持度計(jì)數(shù)與項(xiàng)集{牛奶，尿布}支持度計(jì)數(shù)的商。由于存在3個(gè)事務(wù)同時(shí)包含牛奶和尿布，所以該規(guī)則的置信度為$\frac{2}{3}=0.67$。

支持度是一種重要度量，因?yàn)橹С侄群艿偷囊?guī)則可能只是偶然出現(xiàn)。從商務(wù)角度來看，低支持度的規(guī)則多半也是無意義的，因?yàn)閷?duì)顧客很少同時(shí)購買的商品進(jìn)行促銷可能并無益處。因此，支持度通常用來刪去那些無意義的規(guī)則。此外，支持度還具有一種期望的性質(zhì)，可以用于關(guān)聯(lián)規(guī)則的有效發(fā)現(xiàn)。另一方面，置信度度量通過規(guī)則進(jìn)行推理具有可靠性。對(duì)于給定的規(guī)則$X\to Y$，置信度越高，$Y$在包含$X$的事務(wù)中出現(xiàn)的可能性就越大。置信度也可以估計(jì)$Y$在給定$X$下的條件概率。

應(yīng)當(dāng)小心解釋關(guān)聯(lián)分析的結(jié)果。由關(guān)聯(lián)規(guī)則作出的推論并不必然蘊(yùn)涵因果關(guān)系。它只表示規(guī)則前件和后件中的項(xiàng)明顯地同時(shí)出現(xiàn)。另一方面，因果關(guān)系需要關(guān)于數(shù)據(jù)中原因和結(jié)果屬性的知識(shí)，并且通常涉及長(zhǎng)期出現(xiàn)的聯(lián)系。

關(guān)聯(lián)規(guī)則的挖掘問題可以形式地描述如下：關(guān)聯(lián)規(guī)則發(fā)現(xiàn)給定事務(wù)的集合$T$，關(guān)聯(lián)規(guī)則發(fā)現(xiàn)是指找出支持度大于等于$\text{minsup}$，并且置信度大于等于$\text{minconf}$的所有規(guī)則，其中$\text{minsup}$和$\text{minconf}$是對(duì)應(yīng)的支持度和置信度閥值。

控?fù)?jù)關(guān)聯(lián)規(guī)則的一種原始方法是：計(jì)算每個(gè)可能規(guī)則的支持度和置信度。但是這種方法的代價(jià)很高，令人望而卻步，因?yàn)榭梢詮臄?shù)據(jù)集提取的規(guī)則的數(shù)目達(dá)指數(shù)級(jí)。更具體地說，從包含$d$個(gè)項(xiàng)的數(shù)據(jù)集提取的可能規(guī)則的總數(shù)為：
$$R=3^d+2^{d+1}+1$$

提高關(guān)聯(lián)規(guī)則挖掘算法性能的第一步是拆分支持度和置信度要求。由前文可知，規(guī)則$X\to Y$的支持度僅依賴于其對(duì)應(yīng)項(xiàng)集$X\cup Y$的支持度。例如，{啤酒，尿布}$\to${牛奶}和{啤酒，牛奶}$\to${尿布}有相同的支持度，因?yàn)樗鼈兩婕暗捻?xiàng)都源自同一個(gè)項(xiàng)集{啤酒，尿布，牛奶}。

如果項(xiàng)集{啤酒，尿布，牛奶}是非頻繁的，則可以立即剪掉所有相關(guān)的候選規(guī)則（如：{啤酒，尿布}$\to${牛奶}、{啤酒，牛奶}$\to${尿布}、{尿布，牛奶}$\to${啤酒}等），而不必計(jì)算它們的置信度值。

因此，大多數(shù)關(guān)聯(lián)規(guī)則挖掘算法通常采用的一種策略是，將關(guān)聯(lián)規(guī)則挖掘任務(wù)分解為如下兩個(gè)主要的子任務(wù)：

• 頻繁項(xiàng)集產(chǎn)生：其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閥值的所有項(xiàng)集，這些項(xiàng)集稱作頻繁項(xiàng)集（Frequent Itemset）。
• 規(guī)則的產(chǎn)生：其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取所有高置信度的規(guī)則，這些規(guī)則稱作強(qiáng)規(guī)則（Strongrule）。

通常，頻繁項(xiàng)集產(chǎn)生所需的計(jì)算開銷遠(yuǎn)大于產(chǎn)生規(guī)則所需的計(jì)算開銷。頻繁項(xiàng)集和關(guān)聯(lián)規(guī)產(chǎn)生的有效技術(shù)將在后續(xù)文章中討論。

參考文獻(xiàn)：
[1] Pang-NingTan, MichaelSteinbach, VipinKumar. 數(shù)據(jù)挖掘?qū)д揫M]. 人民郵電出版社, 2006.文章來源地址http://www.zghlxwxcb.cn/news/detail-498950.html

到了這里，關(guān)于深入理解機(jī)器學(xué)習(xí)——關(guān)聯(lián)規(guī)則挖掘：基礎(chǔ)知識(shí)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！