定義
關聯分析是一種簡單、實用的分析技術，就是發現存在于大量數據集中的關聯性或相關性，從而描述了一個事物中某些屬性同時出現的規律和模式。
關聯分析是從大量數據中發現項集之間有趣的關聯和相關聯系。關聯分析的一個典型例子是購物籃分析。該過程通過發現顧客放入其購物籃中的不同商品之間的聯系，分析顧客的購買習慣。通過了解哪些商品頻繁地被顧客同時購買，這種關聯的發現可以幫助零售商制定營銷策略。其他的應用還包括價目表設計、商品促銷、商品的排放和基于購買模式的顧客劃分。
可從數據庫中關聯分析出形如“由于某些事件的發生而引起另外一些事件的發生”之類的規則。如“67%的顧客在購買啤酒的同時也會購買尿布”，因此通過合理的啤酒和尿布的貨架擺放或捆綁銷售可提高超市的服務質量和效益。又如“‘C語言’課程優秀的同學，在學習‘數據結構’時為優秀的可能性達88%”，那麼就可以通過強化“C語言”的學習來提高教學效果。
相關名詞
示例1：如下是一個超市幾名顧客的交易信息。
TID代表交易流水号，Items代表一次交易的商品。
我們對這個數據集進行關聯分析，可以找出關聯規則{Diaper}→{Beer}。
它代表的意義是：購買了Diaper的顧客會購買Beer。這個關系不是必然的，但是可能性很大，這就已經足夠用來輔助商家調整Diaper和Beer的擺放位置了，例如擺放在相近的位置，進行捆綁促銷來提高銷售量。
1、事務：每一條交易稱為一個事務，例如示例1中的數據集就包含四個事務。
2、項：交易的每一個物品稱為一個項，例如Cola、Egg等。
3、項集：包含零個或多個項的集合叫做項集，例如{Cola, Egg, Ham}。
4、k−項集：包含k個項的項集叫做k-項集，例如{Cola}叫做1-項集，{Cola, Egg}叫做2-項集。
5、支持度計數：一個項集出現在幾個事務當中，它的支持度計數就是幾。例如{Diaper, Beer}出現在事務 002、003和004中，所以它的支持度計數是3。
6、支持度：支持度計數除于總的事務數。例如上例中總的事務數為4，{Diaper, Beer}的支持度計數為3，所以它的支持度是3÷4=75%，說明有75%的人同時買了Diaper和Beer。
7、頻繁項集：支持度大于或等于某個阈值的項集就叫做頻繁項集。例如阈值設為50%時，因為{Diaper, Beer}的支持度是75%，所以它是頻繁項集。
8、前件和後件：對于規則{Diaper}→{Beer}，{Diaper}叫做前件，{Beer}叫做後件。
9、置信度：對于規則{Diaper}→{Beer}，{Diaper, Beer}的支持度計數除于{Diaper}的支持度計數，為這個規則的置信度。例如規則{Diaper}→{Beer}的置信度為3÷3=100%。說明買了Diaper的人100%也買了Beer。
10、強關聯規則：大于或等于最小支持度阈值和最小置信度阈值的規則叫做強關聯規則。關聯分析的最終目标就是要找出強關聯規則。
關聯分析方法
Apriori算法
Apriori算法是挖掘産生布爾關聯規則所需頻繁項集的基本算法，也是最著名的關聯規則挖掘算法之一。Apriori算法就是根據有關頻繁項集特性的先驗知識而命名的。它使用一種稱作逐層搜索的叠代方法，k—項集用于探索（k+1）—項集。首先，找出頻繁1—項集的集合．記做L1，L1用于找出頻繁2—項集的集合L2，再用于找出L3，如此下去，直到不能找到頻繁k—項集。找每個Lk需要掃描一次數據庫。
為提高按層次搜索并産生相應頻繁項集的處理效率，Apriori算法利用了一個重要性質，并應用Apriori性質來幫助有效縮小頻繁項集的搜索空間。
Apriori性質：一個頻繁項集的任一子集也應該是頻繁項集。證明根據定義，若一個項集I不滿足最小支持度阈值min_sup，則I不是頻繁的，即P（I）
針對Apriori算法的不足，對其進行優化：
1）基于劃分的方法。該算法先把數據庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊并對它生成所有的頻繁項集，然後把産生的頻繁項集合并，用來生成所有可能的頻繁項集，最後計算這些項集的支持度。這裡分塊的大小選擇要使得每個分塊可以被放入主存，每個階段隻需被掃描一次。而算法的正确性是由每一個可能的頻繁項集至少在某一個分塊中是頻繁項集保證的。
上面所讨論的算法是可以高度并行的。可以把每一分塊分别分配給某一個處理器生成頻繁項集。産生頻繁項集的每一個循環結束後．處理器之間進行通信來産生全局的候選是一項集。通常這裡的通信過程是算法執行時間的主要瓶頸。而另一方面，每個獨立的處理器生成頻繁項集的時間也是一個瓶頸。其他的方法還有在多處理器之間共享一個雜湊樹來産生頻繁項集，更多關于生成頻繁項集的并行化方法可以在其中找到。
2）基于Hash的方法。Park等人提出了一個高效地産生頻繁項集的基于雜湊（Hash）的算法。通過實驗可以發現，尋找頻繁項集的主要計算是在生成頻繁2—項集Lk上，Park等就是利用這個性質引入雜湊技術來改進産生頻繁2—項集的方法。
3）基于采樣的方法。基于前一遍掃描得到的信息，對它詳細地做組合分析，可以得到一個改進的算法，其基本思想是：先使用從數據庫中抽取出來的采樣得到一些在整個數據庫中可能成立的規則，然後對數據庫的剩餘部分驗證這個結果。這個算法相當簡單并顯著地減少了FO代價，但是一個很大的缺點就是産生的結果不精确，即存在所謂的數據扭曲（Dataskew）。分布在同一頁面上的數據時常是高度相關的，不能表示整個數據庫中模式的分布，由此而導緻的是采樣5%的交易數據所花費的代價同掃描一遍數據庫相近。
4）減少交易個數。減少用于未來掃描事務集的大小，基本原理就是當一個事務不包含長度為志的大項集時，則必然不包含長度為走k+1的大項集。從而可以将這些事務删除，在下一遍掃描中就可以減少要進行掃描的事務集的個數。這就是AprioriTid的基本思想。
FP-growth算法
由于Apriori方法的固有缺陷．即使進行了優化，其效率也仍然不能令人滿意。2000年，Han Jiawei等人提出了基于頻繁模式樹（Frequent Pattern Tree，簡稱為FP-tree）的發現頻繁模式的算法FP-growth。在FP-growth算法中，通過兩次掃描事務數據庫，把每個事務所包含的頻繁項目按其支持度降序壓縮存儲到FP—tree中。在以後發現頻繁模式的過程中，不需要再掃描事務數據庫，而僅在FP-Tree中進行查找即可，并通過遞歸調用FP-growth的方法來直接産生頻繁模式，因此在整個發現過程中也不需産生候選模式。該算法克服了Apriori算法中存在的問颢．在執行效率上也明顯好于Apriori算法。
關聯規則生成
得到了頻繁項集，而此時的任務就是在頻繁項集裡面挖掘出大于最小置信度阈值的關聯規則。怎麼挖呢？把頻繁項集分成前件和後件兩部分，然後求規則前件→後件的置信度，如果大于最小置信度阈值，則它就是一條強關聯規則。但是把頻繁項集分成前件和後件的情況有很多，我們可以對其進行一些優化。
