2.6 關聯分析模型

關聯分析又稱關聯挖掘，就是在交易數據、關系數據或其他信息載體中查找存在于項目集合或對象集合之間的頻繁模式、關聯、相關性或因果結構。關聯分析是一種簡單、實用的分析技術，就是發現存在于大量數據集中的關聯性或相關性，從而描述一個事物中某些屬性同時出現的規律和模式。

關聯分析的一個典型例子是購物籃分析，通過合理的啤酒和尿布的貨架擺放或捆綁銷售可提高超市的服務質量和效益，如圖2-6所示。該過程通過發現顧客放入其購物籃中的不同商品之間的聯系，分析顧客的購買習慣，幫助零售商制定營銷策略等。

?事務：每一條交易稱為一個事務。

?項：交易的每一個物品稱為一個項。

?項集：包含零個或多個項的集合。

?k?項集：包含k個項的項集。

?支持度計數：一個項集出現在幾個事務當中，它的支持度計數就是幾。

?支持度：支持度計數除于總的事務數。

?頻繁項集：支持度大于或等于某個閾值的項集。

?前件和后件：對于規則A→B, A叫作前件，B叫作后件。

?置信度：對于規則A→B，{A, B}的支持度計數除以A的為這個規則的置信度。

?強關聯規則：大于或等于最小支持度閾值和最小置信度閾值的規則。

Apriori算法是挖掘產生布爾關聯規則所需頻繁項集的基本算法，也是最著名的關聯規則挖掘算法之一。Apriori算法是根據有關頻繁項集特性的先驗知識而命名的。它使用一種稱作逐層搜索的迭代方法，k-項集用于探索（k+1）-項集。首先，找出頻繁1-項集的集合，記作L1，L1用于找出頻繁2-項集的集合L2，再用于找出L3，如此下去，直到不能找到頻繁k-項集。找出每個Lk都需要掃描一次數據庫。

由于Apriori方法的效率仍然不能令人滿意。2000年，Han Jiawei等人提出了基于頻繁模式樹（FP-tree）的發現頻繁模式的算法FP-growth。它通過兩次掃描事務數據庫，把每個事務所包含的頻繁項目按其支持度降序壓縮存儲到FP—tree中。在以后發現頻繁模式的過程中，不需要再掃描事務數據庫，而僅在FP-Tree中進行查找即可，并通過遞歸調用FP-growth的方法來直接產生頻繁模式，因此在整個發現過程中也不需要產生候選模式。