關聯規則是形如X→Y的蘊涵式，其中， X和Y分別稱為關聯規則的先導(antecedent或left-hand-side, LHS)和後繼(consequent或right-hand-side, RHS) 。其中，關聯規則XY，存在支持度和信任度。
簡介,故事,背景,定義,例子,挖掘過程,兩個階段,案例分析,分類,基於規則中處理的變數的類別,基於規則中數據的抽象層次,基於規則中涉及到的數據的維數,相關算法,Apriori算法,基於劃分的算法,FP-樹頻集算法,套用,套用,研究,
簡介
故事
在描述有關關聯規則的一些細節之前，先來看一個有趣的故事： "尿布與啤酒"的故事。
在一家超市里，有一個有趣的現象：尿布和啤酒赫然擺在一起出售。但是這個奇怪的舉措卻使尿布和啤酒的銷量雙雙增加了。這不是一個笑話，而是發生在美國沃爾瑪連鎖店超市的真實案例，並一直為商家所津津樂道。沃爾瑪擁有世界上最大的數據倉庫系統，為了能夠準確了解顧客在其門店的購買習慣，沃爾瑪對其顧客的購物行為進行購物籃分析，想知道顧客經常一起購買的商品有哪些。沃爾瑪數據倉庫里集中了其各門店的詳細原始交易數據。在這些原始交易數據的基礎上，沃爾瑪利用數據挖掘方法對這些數據進行分析和挖掘。一個意外的發現是："跟尿布一起購買最多的商品竟是啤酒！經過大量實際調查和分析，揭示了一個隱藏在"尿布與啤酒"背後的美國人的一種行為模式：在美國，一些年輕的父親下班後經常要到超市去買嬰兒尿布，而他們中有30%～40%的人同時也為自己買一些啤酒。產生這一現象的原因是：美國的太太們常叮囑她們的丈夫下班後為小孩買尿布，而丈夫們在買尿布後又隨手帶回了他們喜歡的啤酒。
背景
關聯規則最初提出的動機是針對購物籃分析(Market Basket Analysis)問題提出的。假設分店經理想更多的了解顧客的購物習慣。特別是，想知道哪些商品顧客可能會在一次購物時同時購買？為回答該問題，可以對商店的顧客事物零售數量進行購物籃分析。該過程通過發現顧客放入“購物籃”中的不同商品之間的關聯，分析顧客的購物習慣。這種關聯的發現可以幫助零售商了解哪些商品頻繁的被顧客同時購買，從而幫助他們開發更好的行銷策略。
1993年，Agrawal等人在首先提出關聯規則概念，同時給出了相應的挖掘算法AIS，但是性能較差。1994年，他們建立了項目集格空間理論，並依據上述兩個定理，提出了著名的Apriori算法，至今Apriori仍然作為關聯規則挖掘的經典算法被廣泛討論，以後諸多的研究人員對關聯規則的挖掘問題進行了大量的研究。
定義
根據韓家煒等觀點，關聯規則定義為：
假設是項的集合。給定一個交易資料庫D，其中每個事務(Transaction)t是I的非空子集，即，每一個交易都與一個唯一的標識符TID(Transaction ID)對應。關聯規則在D中的支持度(support)是D中事務同時包含X、Y的百分比，即機率；置信度(confidence)是D中事務已經包含X的情況下，包含Y的百分比，即條件機率。如果滿足最小支持度閾值和最小置信度閾值，則認為關聯規則是有趣的。這些閾值是根據挖掘需要人為設定。
基本概念表1：關聯規則的簡單例子
例子
TID | 網球拍 | 網 球 | 運動鞋 | 羽毛球 |
1 | 1 | 1 | 1 | 0 |
2 | 1 | 1 | 0 | 0 |
3 | 1 | 0 | 0 | 0 |
4 | 1 | 0 | 1 | 0 |
5 | 0 | 1 | 1 | 1 |
6 | 1 | 1 | 0 | 0 |
用一個簡單的例子說明。表1是顧客購買記錄的資料庫D，包含6個事務。項集I={網球拍,網球,運動鞋,羽毛球}。考慮關聯規則（頻繁二項集）：網球拍與網球，事務1,2,3,4,6包含網球拍，事務1,2,6同時包含網球拍和網球，X^Y=3, D=6，支持度(X^Y)/D=0.5；X=5, 置信度(X^Y)/X=0.6。若給定最小支持度α = 0.5，最小置信度β = 0.6，認為購買網球拍和購買網球之間存在關聯。
挖掘過程
兩個階段
關聯規則挖掘過程主要包含兩個階段：第一階段必須先從資料集合中找出所有的高頻項目組(Frequent Itemsets)，第二階段再由這些高頻項目組中產生關聯規則(Association Rules)。
關聯規則挖掘的第一階段必須從原始資料集合中，找出所有高頻項目組(Large Itemsets)。高頻的意思是指某一項目組出現的頻率相對於所有記錄而言，必須達到某一水平。一項目組出現的頻率稱為支持度(Support)，以一個包含A與B兩個項目的2-itemset為例，我們可以經由公式(1)求得包含{A,B}項目組的支持度，若支持度大於等於所設定的最小支持度(Minimum Support)門檻值時，則{A,B}稱為高頻項目組。一個滿足最小支持度的k-itemset，則稱為高頻k-項目組(Frequent k-itemset)，一般表示為Large k或Frequent k。算法並從Large k的項目組中再產生Large k+1，直到無法再找到更長的高頻項目組為止。
關聯規則挖掘的第二階段是要產生關聯規則(Association Rules)。從高頻項目組產生關聯規則，是利用前一步驟的高頻k-項目組來產生規則，在最小信賴度(Minimum Confidence)的條件門檻下，若一規則所求得的信賴度滿足最小信賴度，稱此規則為關聯規則。例如：經由高頻k-項目組{A,B}所產生的規則AB，其信賴度可經由公式(2)求得，若信賴度大於等於最小信賴度，則稱AB為關聯規則。
案例分析
就沃爾馬案例而言，使用關聯規則挖掘技術，對交易資料庫中的紀錄進行資料挖掘，首先必須要設定最小支持度與最小信賴度兩個門檻值，在此假設最小支持度min_support=5% 且最小信賴度min_confidence=70%。因此符合此該超市需求的關聯規則將必須同時滿足以上兩個條件。若經過挖掘過程所找到的關聯規則「尿布，啤酒」，滿足下列條件，將可接受「尿布，啤酒」的關聯規則。用公式可以描述Support(尿布，啤酒)>=5%且Confidence(尿布，啤酒)>=70%。其中，Support(尿布，啤酒)>=5%於此套用範例中的意義為:在所有的交易紀錄資料中，至少有5%的交易呈現尿布與啤酒這兩項商品被同時購買的交易行為。Confidence(尿布，啤酒)>=70%於此套用範例中的意義為:在所有包含尿布的交易紀錄資料中，至少有70%的交易會同時購買啤酒。因此，今後若有某消費者出現購買尿布的行為，超市將可推薦該消費者同時購買啤酒。這個商品推薦的行為則是根據「尿布，啤酒」關聯規則，因為就該超市過去的交易紀錄而言，支持了“大部份購買尿布的交易，會同時購買啤酒”的消費行為。
分類
基於規則中處理的變數的類別
關聯規則處理的變數可以分為布爾型和數值型。布爾型關聯規則處理的值都是離散的、種類化的，它顯示了這些變數之間的關係；而數值型關聯規則可以和多維關聯或多層關聯規則結合起來，對數值型欄位進行處理，將其進行動態的分割，或者直接對原始的數據進行處理，當然數值型關聯規則中也可以包含種類變數。例如：性別=“女”=>職業=“秘書” ，是布爾型關聯規則；性別=“女”=>avg（收入）=2300，涉及的收入是數值類型，所以是一個數值型關聯規則。
基於規則中數據的抽象層次
基於規則中數據的抽象層次，可以分為單層關聯規則和多層關聯規則。在單層的關聯規則中，所有的變數都沒有考慮到現實的數據是具有多個不同的層次的；而在多層的關聯規則中，對數據的多層性已經進行了充分的考慮。例如：IBM台式機=>Sony印表機，是一個細節數據上的單層關聯規則；台式機=>Sony印表機，是一個較高層次和細節層次之間的多層關聯規則。
基於規則中涉及到的數據的維數
關聯規則中的數據，可以分為單維的和多維的。在單維的關聯規則中，我們只涉及到數據的一個維，如用戶購買的物品；而在多維的關聯規則中，要處理的數據將會涉及多個維。換成另一句話，單維關聯規則是處理單個屬性中的一些關係；多維關聯規則是處理各個屬性之間的某些關係。例如：啤酒=>尿布，這條規則只涉及到用戶的購買的物品；性別=“女”=>職業=“秘書”，這條規則就涉及到兩個欄位的信息，是兩個維上的一條關聯規則。
相關算法
Apriori算法
Apriori算法：使用候選項集找頻繁項集
Apriori算法是一種最有影響的挖掘布爾關聯規則頻繁項集的算法。其核心是基於兩階段頻集思想的遞推算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。在這裡，所有支持度大於最小支持度的項集稱為頻繁項集，簡稱頻集。
該算法的基本思想是：首先找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然後由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。然後使用第1步找到的頻集產生期望的規則，產生只包含集合的項的所有規則，其中每一條規則的右部只有一項，這裡採用的是中規則的定義。一旦這些規則被生成，那么只有那些大於用戶給定的最小可信度的規則才被留下來。為了生成所有頻集，使用了遞推的方法。
Apriori算法採用了逐層搜尋的疊代的方法，算法簡單明了，沒有複雜的理論推導，也易於實現。但其有一些難以克服的缺點：
（1）對資料庫的掃描次數過多。
（2）Apriori算法會產生大量的中間項集。
（3）採用唯一支持度。
（4）算法的適應面窄。
基於劃分的算法
基於劃分的算法
Savasere等設計了一個基於劃分的算法。這個算法先把資料庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊並對它生成所有的頻集，然後把產生的頻集合併，用來生成所有可能的頻集，最後計算這些項集的支持度。這裡分塊的大小選擇要使得每個分塊可以被放入主存，每個階段只需被掃描一次。而算法的正確性是由每一個可能的頻集至少在某一個分塊中是頻集保證的。該算法是可以高度並行的，可以把每一分塊分別分配給某一個處理器生成頻集。產生頻集的每一個循環結束後，處理器之間進行通信來產生全局的候選k-項集。通常這裡的通信過程是算法執行時間的主要瓶頸；而另一方面，每個獨立的處理器生成頻集的時間也是一個瓶頸。
FP-樹頻集算法
FP-樹頻集算法
針對Apriori算法的固有缺陷，J. Han等提出了不產生候選挖掘頻繁項集的方法：FP-樹頻集算法。採用分而治之的策略，在經過第一遍掃描之後，把資料庫中的頻集壓縮進一棵頻繁模式樹（FP-tree），同時依然保留其中的關聯信息，隨後再將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻集相關，然後再對這些條件庫分別進行挖掘。當原始數據量很大的時候，也可以結合劃分的方法,使得一個FP-tree可以放入主存中。實驗表明，FP-growth對不同長度的規則都有很好的適應性，同時在效率上較之Apriori算法有巨大的提高。
套用
套用
關聯規則挖掘技術已經被廣泛套用在西方金融行業企業中，它可以成功預測銀行客戶需求。一旦獲得了這些信息，銀行就可以改善自身行銷。銀行天天都在開發新的溝通客戶的方法。各銀行在自己的ATM機上就捆綁了顧客可能感興趣的本行產品信息，供使用本行ATM機的用戶了解。如果資料庫中顯示，某個高信用限額的客戶更換了地址，這個客戶很有可能新近購買了一棟更大的住宅，因此會有可能需要更高信用限額，更高端的新信用卡，或者需要一個住房改善貸款，這些產品都可以通過信用卡賬單郵寄給客戶。當客戶打電話諮詢的時候，資料庫可以有力地幫助電話銷售代表。銷售代表的電腦螢幕上可以顯示出客戶的特點，同時也可以顯示出顧客會對什麼產品感興趣。
再比如市場的數據，它不僅十分龐大、複雜，而且包含著許多有用信息。隨著數據挖掘技術的發展以及各種數據挖掘方法的套用，從大型超市資料庫中可以發現一些潛在的、有用的、有價值的信息來，從而套用於超級市場的經營。通過對所積累的銷售數據的分析，可以得出各種商品的銷售信息。從而更合理地制定各種商品的定貨情況，對各種商品的庫存進行合理地控制。另外根據各種商品銷售的相關情況，可分析商品的銷售關聯性，從而可以進行商品的貨籃分析和組合管理，以更加有利於商品銷售。
同時，一些知名的電子商務站點也從強大的關聯規則挖掘中的受益。這些電子購物網站使用關聯規則中規則進行挖掘，然後設定用戶有意要一起購買的捆綁包。也有一些購物網站使用它們設定相應的交叉銷售，也就是購買某種商品的顧客會看到相關的另外一種商品的廣告。
但是在我國，“數據海量，信息缺乏”是商業銀行在數據大集中之後普遍所面對的尷尬。金融業實施的大多數資料庫只能實現數據的錄入、查詢、統計等較低層次的功能，卻無法發現數據中存在的各種有用的信息，譬如對這些數據進行分析，發現其數據模式及特徵，然後可能發現某個客戶、消費群體或組織的金融和商業興趣，並可觀察金融市場的變化趨勢。可以說，關聯規則挖掘的技術在我國的研究與套用並不是很廣泛深入。
研究
由於許多套用問題往往比超市購買問題更複雜，大量研究從不同的角度對關聯規則做了擴展，將更多的因素集成到關聯規則挖掘方法之中，以此豐富關聯規則的套用領域，拓寬支持管理決策的範圍。如考慮屬性之間的類別層次關係，時態關係，多表挖掘等。圍繞關聯規則的研究主要集中於兩個方面，即擴展經典關聯規則能夠解決問題的範圍，改善經典關聯規則挖掘算法效率和規則興趣性。
