電商數(shù)據(jù)挖掘之關(guān)聯(lián)算法_數(shù)據(jù)分析師考試

所謂關(guān)聯(lián)，反映的是一個(gè)事件和其他事件之間依賴或關(guān)聯(lián)的知識。當(dāng)我們查找英文文獻(xiàn)的時(shí)候，可以發(fā)現(xiàn)有兩個(gè)英文詞都能形容關(guān)聯(lián)的含義。第一個(gè)是相關(guān)性relevance，第二個(gè)是關(guān)聯(lián)性association，兩者都可以用來描述事件之間的關(guān)聯(lián)程度。其中前者主要用在互聯(lián)網(wǎng)的內(nèi)容和文檔上，比如搜索引擎算法中文檔之間的關(guān)聯(lián)性，我們采用的詞是relevance；而后者往往用在實(shí)際的事物之上，比如電子商務(wù)網(wǎng)站上的商品之間的關(guān)聯(lián)度我們是用association來表示的，而關(guān)聯(lián)規(guī)則是用association rules來表示的。

如果兩項(xiàng)或多項(xiàng)屬性之間存在關(guān)聯(lián)，那么其中一項(xiàng)的屬性值就可以依據(jù)其他屬性值進(jìn)行預(yù)測。簡單地來說，關(guān)聯(lián)規(guī)則可以用這樣的方式來表示：A→B，其中A被稱為前提或者左部（LHS），而B被稱為結(jié)果或者右部（RHS）。如果我們要描述關(guān)于尿布和啤酒的關(guān)聯(lián)規(guī)則（買尿布的人也會(huì)買啤酒），那么我們可以這樣表示：買尿布→買啤酒。

關(guān)聯(lián)算法的兩個(gè)概念

在關(guān)聯(lián)算法中很重要的一個(gè)概念是支持度（Support），也就是數(shù)據(jù)集中包含某幾個(gè)特定項(xiàng)的概率。比如在1000次的商品交易中同時(shí)出現(xiàn)了啤酒和尿布的次數(shù)是50次，那么此關(guān)聯(lián)的支持度為5%。

和關(guān)聯(lián)算法很相關(guān)的另一個(gè)概念是置信度（Confidence），也就是在數(shù)據(jù)集中已經(jīng)出現(xiàn)A時(shí)，B發(fā)生的概率，置信度的計(jì)算公式是 ：A與B同時(shí)出現(xiàn)的概率/A出現(xiàn)的概率。

數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫中存在的一類重要的可被發(fā)現(xiàn)的知識。若兩個(gè)或多個(gè)變量的取值之間存在某種規(guī)律性，就稱為關(guān)聯(lián)。關(guān)聯(lián)可分為簡單關(guān)聯(lián)、時(shí)序關(guān)聯(lián)、因果關(guān)聯(lián)等。關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫中隱藏的關(guān)聯(lián)網(wǎng)。有時(shí)并不知道數(shù)據(jù)庫中數(shù)據(jù)的關(guān)聯(lián)函數(shù)，或者即使知道也是不確定的，因此關(guān)聯(lián)分析生成的規(guī)則帶有置信度。

關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。它在數(shù)據(jù)挖掘中是一個(gè)重要的課題，最近幾年被業(yè)界所廣泛研究。

關(guān)聯(lián)規(guī)則挖掘的一個(gè)典型例子是購物籃分析。關(guān)聯(lián)規(guī)則研究有助于發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品（項(xiàng)）之間的聯(lián)系，找出顧客購買行為模式，如購買了某一商品對購買其他商品的影響。分析結(jié)果可以應(yīng)用于商品貨架布局、貨存安排以及根據(jù)購買模式對用戶進(jìn)行分類。

規(guī)則的發(fā)現(xiàn)過程可分為如下兩步：

第一步是迭代識別所有的頻繁項(xiàng)目集（Frequent Itemsets），要求頻繁項(xiàng)目集的支持度不低于用戶設(shè)定的最低值；

第二步是從頻繁項(xiàng)目集中構(gòu)造置信度不低于用戶設(shè)定的最低值的規(guī)則，產(chǎn)生關(guān)聯(lián)規(guī)則。識別或發(fā)現(xiàn)所有頻繁項(xiàng)目集是關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法的核心，也是計(jì)算量最大的部分。

支持度和置信度兩個(gè)閾值是描述關(guān)聯(lián)規(guī)則的兩個(gè)最重要的概念。一項(xiàng)目組出現(xiàn)的頻率稱為支持度，反映關(guān)聯(lián)規(guī)則在數(shù)據(jù)庫中的重要性。而置信度衡量關(guān)聯(lián)規(guī)則的可信程度。如果某條規(guī)則同時(shí)滿足最小支持度（min-support）和最小置信度（min-confidence），則稱它為強(qiáng)關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘階段

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

關(guān)聯(lián)規(guī)則挖掘的第二階段是要產(chǎn)生關(guān)聯(lián)規(guī)則。從高頻項(xiàng)目組產(chǎn)生關(guān)聯(lián)規(guī)則，是利用前一步驟的高頻k-項(xiàng)目組來產(chǎn)生規(guī)則，在最小可信度（Minimum Confidence）的條件門檻下，若一規(guī)則所求得的可信度滿足最小可信度，則稱此規(guī)則為關(guān)聯(lián)規(guī)則。

例如：經(jīng)由高頻k-項(xiàng)目組{A,B}所產(chǎn)生的規(guī)則，若其可信度大于等于最小可信度，則稱{A,B}為關(guān)聯(lián)規(guī)則。

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

Support（尿布，啤酒）≥5% and Confidence（尿布，啤酒）≥65%。

其中，Support（尿布，啤酒）≥5%于此應(yīng)用范例中的意義為：在所有的交易記錄資料中，至少有5%的交易呈現(xiàn)尿布與啤酒這兩項(xiàng)商品被同時(shí)購買的交易行為。Confidence（尿布，啤酒）≥65%于此應(yīng)用范例中的意義為：在所有包含尿布的交易記錄資料中，至少有65%的交易會(huì)同時(shí)購買啤酒。

因此，今后若有某消費(fèi)者出現(xiàn)購買尿布的行為，我們將可推薦該消費(fèi)者同時(shí)購買啤酒。這個(gè)商品推薦的行為則是根據(jù){尿布，啤酒}關(guān)聯(lián)規(guī)則而定，因?yàn)榫瓦^去的交易記錄而言，支持了“大部分購買尿布的交易，會(huì)同時(shí)購買啤酒”的消費(fèi)行為。

從上面的介紹還可以看出，關(guān)聯(lián)規(guī)則挖掘通常比較適用于記錄中的指標(biāo)取離散值的情況。

如果原始數(shù)據(jù)庫中的指標(biāo)值是取連續(xù)的數(shù)據(jù)，則在關(guān)聯(lián)規(guī)則挖掘之前應(yīng)該進(jìn)行適當(dāng)?shù)臄?shù)據(jù)離散化（實(shí)際上就是將某個(gè)區(qū)間的值對應(yīng)于某個(gè)值），數(shù)據(jù)的離散化是數(shù)據(jù)挖掘前的重要環(huán)節(jié)，離散化的過程是否合理將直接影響關(guān)聯(lián)規(guī)則的挖掘結(jié)果。

這一期則以數(shù)據(jù)實(shí)例來看最著名的Apriori關(guān)聯(lián)算法的演算過程。從一家公司的銷售記錄中我們找到以下8條消費(fèi)記錄，并以3作為最小支持度，也就是說出現(xiàn)頻率在3次以下的記錄是被我們所忽略的。

所有滿足最小支持度3的1項(xiàng)頻集如下，其中的支持度是指該產(chǎn)品在整個(gè)數(shù)據(jù)集中出現(xiàn)的次數(shù)。比如牛奶出現(xiàn)了5次，而冰淇淋出現(xiàn)了3次。

遞歸執(zhí)行，所有滿足最小支持度3的2項(xiàng)頻集如下，這其中出現(xiàn)最多的頻集是｛牛奶，面包｝和｛面包，果醬｝，各自出現(xiàn)了4次。

再次遞歸執(zhí)行，所有滿足最小支持度3的3項(xiàng)頻集只剩下一條：

那么｛牛奶，果醬，面包｝就是我們要的滿足最小支持度3的3項(xiàng)頻集，也就是說牛奶、果醬和面包這三個(gè)商品是最經(jīng)常被一起購買的。

概念層次的數(shù)據(jù)挖掘

在研究挖掘關(guān)聯(lián)規(guī)則的過程中，許多學(xué)者發(fā)現(xiàn)在實(shí)際應(yīng)用中，對于很多應(yīng)用來說，由于數(shù)據(jù)分布的分散性，數(shù)比較少，所以很難在數(shù)據(jù)最細(xì)節(jié)的層次上發(fā)現(xiàn)一些強(qiáng)關(guān)聯(lián)規(guī)則。要想在原始的概念層次上發(fā)現(xiàn)強(qiáng)的（strong）和有意義的（interesting）關(guān)聯(lián)規(guī)則是比較困難的，因?yàn)楹枚囗?xiàng)集往往沒有足夠的支持?jǐn)?shù)。

當(dāng)我們引入概念層次后，就可以在較高的層次上進(jìn)行挖掘。雖然較高層次上得出的規(guī)則可能是更普通的信息，但是對于一個(gè)用戶來說是普通的信息，對于另一個(gè)用戶卻未必如此。所以數(shù)據(jù)挖掘應(yīng)該提供這樣一種在多個(gè)層次上進(jìn)行挖掘的功能。

概念層次在要挖掘的數(shù)據(jù)庫中經(jīng)常是存在的，比如在一個(gè)超市中會(huì)存在這樣的概念層次：蒙牛牌牛奶是牛奶，伊利牌牛奶是牛奶，王子牌餅干是餅干，康師傅牌餅干是餅干等。

如果我們只是在數(shù)據(jù)基本層發(fā)掘關(guān)系，｛蒙牛牌牛奶，王子牌餅干｝，｛蒙牛牌牛奶，康師傅牌餅干｝，｛伊利牌牛奶，王子牌餅干｝，｛伊利牌牛奶，康師傅牌餅干｝都不符合最小支持度。不過如果我們上升一個(gè)層級，會(huì)發(fā)現(xiàn)｛牛奶，餅干｝ 的關(guān)聯(lián)規(guī)則是有一定支持度的。

我們稱高層次的項(xiàng)是低層次項(xiàng)的父親層次（parent），這種概念層次關(guān)系通常用一個(gè)DAG（directed acyclic graph，有向無環(huán)圖)來表示。所謂有向無環(huán)圖是指，任意一條邊有方向，且不存在環(huán)路的圖。這樣我們就可以在較高的概念層次上發(fā)現(xiàn)關(guān)聯(lián)規(guī)則。

支持度的設(shè)置策略

根據(jù)規(guī)則中涉及的層次和多層關(guān)聯(lián)的規(guī)則，我們可以把關(guān)聯(lián)規(guī)則分為同層關(guān)聯(lián)規(guī)則和層間關(guān)聯(lián)規(guī)則。多層關(guān)聯(lián)規(guī)則的挖掘基本上可以沿用“支持度—置信度”的框架。不過，在支持度設(shè)置的問題上有一些要考慮的東西。

同層關(guān)聯(lián)規(guī)則可以采用兩種支持度策略：

統(tǒng)一的最小支持度。對于不同的層次，都使用同一個(gè)最小支持度。這樣對于用戶和算法實(shí)現(xiàn)來說都比較容易，但是弊端也是顯而易見的。

遞減的最小支持度。每個(gè)層次都有不同的最小支持度，較低層次的最小支持度相對較小。同時(shí)還可以利用上層挖掘得到的信息進(jìn)行一些過濾的工作。層間關(guān)聯(lián)規(guī)則考慮最小支持度的時(shí)候，應(yīng)該根據(jù)較低層次的最小支持度來定。

以上我們討論的基本上都是同一個(gè)字段的值之間的關(guān)系，比如用戶購買的物品。換句話說就是在單維或者叫維內(nèi)的關(guān)聯(lián)規(guī)則，這些規(guī)則很多都是在交易數(shù)據(jù)庫中挖掘的。

但是對于實(shí)際應(yīng)用來說，多維的關(guān)聯(lián)規(guī)則可能是更加有價(jià)值的。

同時(shí)，在挖掘維間關(guān)聯(lián)規(guī)則和混合維關(guān)聯(lián)規(guī)則的時(shí)候，還要考慮不同的字段種類，是分類型數(shù)據(jù)還是數(shù)值型數(shù)據(jù)等等。