關聯,其實很簡單,就是幾個東西或者事件是經常同時出現的,“啤酒+尿布”就是非常典型的兩個關聯商品。

所謂關聯,反映的是一個事件和其他事件之間依賴或關聯的知識。當我們查找英文文獻的時候,可以發現有兩個英文詞都能形容關聯的含義。第一個是相關性relevance,第二個是關聯性association,兩者都可以用來描述事件之間的關聯程度。其中前者主要用在互聯網的內容和文檔上,比如搜索引擎算法中文檔之間的關聯性,我們採用的詞是relevance;而後者往往用在實際的事物之上,比如电子商務網站上的商品之間的關聯度我們是用association來表示的,而關聯規則是用association rules來表示的

如果兩項或多項屬性之間存在關聯,那麼其中一項的屬性值就可以依據其他屬性值進行預測。簡單地來說,關聯規則可以用這樣的方式來表示:A→B,其中A被稱為前提或者左部(LHS),而B被稱為結果或者右部(RHS)。如果我們要描述關於尿布和啤酒的關聯規則(買尿布的人也會買啤酒),那麼我們可以這樣表示:買尿布→買啤酒。

關聯算法的兩個概念

在關聯算法中很重要的一個概念是支持度(Support),也就是數據集中包含某幾個特定項的概率。

比如在1000次的商品交易中同時出現了啤酒和尿布的次數是50次,那麼此關聯的支持度為5%。

和關聯算法很相關的另一個概念是置信度(Confidence),也就是在數據集中已經出現A時,B發生的概率,置信度的計算公式是 :A與B同時出現的概率/A出現的概率。

數據關聯是數據庫中存在的一類重要的可被發現的知識。若兩個或多個變量的取值之間存在某種規律性,就稱為關聯。關聯可分為簡單關聯、時序關聯、因果關聯等。關聯分析的目的是找出數據庫中隱藏的關聯網。有時並不知道數據庫中數據的關聯函數,或者即使知道也是不確定的,因此關聯分析生成的規則帶有置信度。

關聯規則挖掘發現大量數據中項集之間有趣的關聯或相關聯繫。它在數據挖掘中是一個重要的課題,最近幾年已被業界所廣泛研究。

關聯規則挖掘的一個典型例子是購物籃分析。關聯規則研究有助於發現交易數據庫中不同商品(項)之間的聯繫,找出顧客購買行為模式,如購買了某一商品對購買其他商品的影響。分析結果可以應用於商品貨架布局、貨存安排以及根據購買模式對用戶進行分類。

關聯規則的發現過程可分為如下兩步:

第一步是迭代識別所有的頻繁項目集(Frequent Itemsets),要求頻繁項目集的支持度不低於用戶設定的最低值;

第二步是從頻繁項目集中構造置信度不低於用戶設定的最低值的規則,產生關聯規則。識別或發現所有頻繁項目集是關聯規則發現算法的核心,也是計算量最大的部分。

支持度和置信度兩個閾值是描述關聯規則的兩個最重要的概念。一項目組出現的頻率稱為支持度,反映關聯規則在數據庫中的重要性。而置信度衡量關聯規則的可信程度。如果某條規則同時滿足最小支持度(min-support)和最小置信度(min-confidence),則稱它為強關聯規則。

關聯規則數據挖掘階段

第一階段必須從原始資料集合中,找出所有高頻項目組(Large Itemsets)。高頻的意思是指某一項目組出現的頻率相對於所有記錄而言,必須達到某一水平。以一個包含A與B兩個項目的2-itemset為例,我們可以求得包含{A,B}項目組的支持度,若支持度大於等於所設定的最小支持度(Minimum Support)門檻值時,則{A,B}稱為高頻項目組。一個滿足最小支持度的k-itemset,則稱為高頻k-項目組(Frequent k-itemset),一般表示為Large k或Frequent k。算法並從Large k的項目組中再試圖產生長度超過k的項目集Large k+1,直到無法再找到更長的高頻項目組為止。

關聯規則挖掘的第二階段是要產生關聯規則。從高頻項目組產生關聯規則,是利用前一步驟的高頻k-項目組來產生規則,在最小可信度(Minimum Confidence)的條件門檻下,若一規則所求得的可信度滿足最小可信度,則稱此規則為關聯規則。

例如:經由高頻k-項目組{A,B}所產生的規則,若其可信度大於等於最小可信度,則稱{A,B}為關聯規則。

就“啤酒+尿布”這個案例而言,使用關聯規則挖掘技術,對交易資料庫中的記錄進行資料挖掘,首先必須要設定最小支持度與最小可信度兩個門檻值,在此假設最小支持度min-support=5% 且最小可信度min-confidence=65%。因此符合需求的關聯規則將必須同時滿足以上兩個條件。若經過挖掘所找到的關聯規則 {尿布,啤酒}滿足下列條件,將可接受{尿布,啤酒} 的關聯規則。用公式可以描述為:

Support(尿布,啤酒)≥5% and Confidence(尿布,啤酒)≥65%。

其中,Support(尿布,啤酒)≥5%於此應用範例中的意義為:在所有的交易記錄資料中,至少有5%的交易呈現尿布與啤酒這兩項商品被同時購買的交易行為。Confidence(尿布,啤酒)≥65%於此應用範例中的意義為:在所有包含尿布的交易記錄資料中,至少有65%的交易會同時購買啤酒。

因此,今後若有某消費者出現購買尿布的行為,我們將可推薦該消費者同時購買啤酒。這個商品推薦的行為則是根據{尿布,啤酒}關聯規則而定,因為就過去的交易記錄而言,支持了“大部分購買尿布的交易,會同時購買啤酒”的消費行為。

從上面的介紹還可以看出,關聯規則挖掘通常比較適用於記錄中的指標取離散值的情況。

如果原始數據庫中的指標值是取連續的數據,則在關聯規則挖掘之前應該進行適當的數據離散化(實際上就是將某個區間的值對應於某個值),數據的離散化是數據挖掘前的重要環節,離散化的過程是否合理將直接影響關聯規則的挖掘結果