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

購物籃分析“啤酒和尿布”的故事是營銷屆的神話，“啤酒”和“尿布”兩個看上去沒有關(guān)系的商品擺放在一起進行銷售、并獲得了很好的銷售收益，這種現(xiàn)象就是賣場中商品之間的關(guān)聯(lián)性，研究“啤酒與尿布”關(guān)聯(lián)的方法就是購物籃分析，購物籃分析是沃爾瑪秘而不宣的獨門武器，購物籃分析可以幫助我們在門店的銷售過程中找到具有關(guān)聯(lián)關(guān)系的商品，并以此獲得銷售收益的增長！

D={牛肉，雞肉，牛奶，奶酪，靴子，衣服，…..}t1:牛肉、雞肉、牛奶t2:牛肉、奶酪t3:奶酪、靴子t4:牛肉、雞肉、奶酪t5:牛肉、雞肉、衣服、奶酪、牛奶

t6:雞肉、衣服、牛奶t7:雞肉、牛奶、衣服..............如何從客戶購物籃中找出具有關(guān)聯(lián)關(guān)系的商品組合呢？關(guān)聯(lián)規(guī)則挖掘技術(shù)關(guān)聯(lián)規(guī)則反映一個事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果兩個或者多個事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個事物就能夠通過其他事物預測到。典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的貨籃數(shù)據(jù)（MarketBasket）進行分析。通過發(fā)現(xiàn)顧客放入貨籃中的不同商品之間的關(guān)系來分析顧客的購買習慣。

關(guān)聯(lián)規(guī)則簡介關(guān)聯(lián)規(guī)則(AssociationRuleMining)挖掘是數(shù)據(jù)挖掘中最活躍的研究方法之一最早是由R.Agrawal等人提出的其目的是為了發(fā)現(xiàn)超市交易數(shù)據(jù)庫中不同商品之間的關(guān)聯(lián)關(guān)系。一個典型的關(guān)聯(lián)規(guī)則的例子是：70%購買了牛奶的顧客將傾向于同時購買面包。經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法：Apriori算法和FP-growth算法關(guān)聯(lián)規(guī)則挖掘

1.1關(guān)聯(lián)規(guī)則挖掘的基本概念

1.購物籃分析－引發(fā)關(guān)聯(lián)規(guī)則挖掘的例子

問題：“什么商品組或集合顧客多半會在一次購物中同時購買？”購物籃分析：設(shè)全域為商店出售的商品的集合（即項目全集），一次購物購買（即事務(wù)）的商品為項目全集的子集，通過對購物籃清單的分析，得到反映商品頻繁關(guān)聯(lián)或同時購買的購買模式。這些模式可用關(guān)聯(lián)規(guī)則描述?！祭?〗購買計算機與購買財務(wù)管理軟件的關(guān)聯(lián)規(guī)則可表示為：computerfinancial_management_software [support=2%,confidence=60%]support為支持度，confidence為置信度。該規(guī)則表示：在所分析的全部事務(wù)中，有2％的事務(wù)同時購買計算機和財務(wù)管理軟件；在購買計算機的顧客中60％也購買了財務(wù)管理軟件。理解：關(guān)聯(lián)分析中的三個重要的概念

舉例：10000個人購買了產(chǎn)品，其中購買A產(chǎn)品的人是1000個，購買B產(chǎn)品的人是2000個，AB同時購買的人是800個。支持度指的是關(guān)聯(lián)的產(chǎn)品（假定A產(chǎn)品和B產(chǎn)品關(guān)聯(lián)）同時購買的人數(shù)占總?cè)藬?shù)的比例，即800/10000=8%，有8%的用戶同時購買了A和B兩個產(chǎn)品；可信度指的是在購買了一個產(chǎn)品之后購買另外一個產(chǎn)品的可能性，如購買了A產(chǎn)品之后購買B產(chǎn)品的可信度=800/1000=80%支持度可信度〖定義4－2〗關(guān)聯(lián)規(guī)則X

Y對事物集D的支持度（support）定義為D中包含有事務(wù)X和Y的百分比。關(guān)聯(lián)規(guī)則X

Y對事務(wù)集合D的置信度（confidence）定義為D中包含有X的事務(wù)數(shù)與同時包含Y的百分比。即：l

support(XY)＝(包含X和Y的事務(wù)數(shù)/事務(wù)總數(shù))×100％

l

confidence(XY)＝(包含X和Y的事務(wù)數(shù)/包含X的事務(wù)數(shù))×100％〖定義4－3〗置信度和支持度均大于給定閾值（即最小置信度閾值和最小支持度閾值）。即：

support(X

Y)>＝min_sup confidence(XY)>＝min_conf的關(guān)聯(lián)規(guī)則稱為強規(guī)則；否則稱為弱規(guī)則。數(shù)據(jù)挖掘主要就是對強規(guī)則的挖掘。通過設(shè)置最小支持度和最小置信度可以了解某些數(shù)據(jù)之間的關(guān)聯(lián)程度。強規(guī)則X

Y對應(yīng)的項集（X∪Y）必定是頻繁集。因此，可以把關(guān)聯(lián)規(guī)則挖掘劃分為以下兩個子問題：根據(jù)最小支持度找出事務(wù)集D中的所有頻繁項集。―核心根據(jù)頻繁項集和最小置信度產(chǎn)生關(guān)聯(lián)規(guī)則。―較易規(guī)則度量：支持度與可信度查找所有的規(guī)則X&YZ具有最小支持度和可信度支持度,s,一次交易中包含{X、Y、Z}的可能性可信度,c,

包含{X、Y}的交易中也包含Z的條件概率設(shè)最小支持度為50%,最小可信度為50%,則可得到AC(50%,66.6%)CA(50%,100%)ABDCABACADBCBDCD?ABCABDBCDACDABCDTransaction-idItemsbought10A,B,C20A,C30A,D，B40B,E,F，cLetmin_support=50%,min_conf=50%:CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerForruleA

C:support=support({A}

{C})=50%confidence=support({A}{C})/support({A})=66.6%Min.support50%Min.confidence50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%關(guān)聯(lián)規(guī)則就是支持度和信任度分別滿足用戶給定閾值的規(guī)則。發(fā)現(xiàn)關(guān)聯(lián)規(guī)則需要經(jīng)歷如下兩個步驟：找出所有頻繁項集。由頻繁項集生成滿足最小信任度閾值的規(guī)則。以商場超市的市場數(shù)據(jù)庫為例，形式化地描述關(guān)聯(lián)規(guī)則?！级x4－1〗設(shè)I={i1，i2，…,im}是項的集合，表示各種商品的集合；D={t1，t2，…,tn}為交易集，表示每筆交易的集合（是全體事務(wù)的集合）。其中每一個事務(wù)T都是項的集合，且有T

I。每個事務(wù)都有一個相關(guān)的唯一標識符和它對應(yīng)，也就是事務(wù)標識符或TID。設(shè)X為一個由項目構(gòu)成的集合，稱為項集，當且僅當X

T時我們說事務(wù)T包含X。項集X在在事務(wù)數(shù)據(jù)庫DB中出現(xiàn)的次數(shù)占總事務(wù)的百分比叫做項集的支持度。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集（或大項集）。關(guān)聯(lián)規(guī)則是形如X

Y的蘊含式，其中X

I，Y

I且X

Y=

，則X稱為規(guī)則的條件，Y稱為規(guī)則的結(jié)果。如果事務(wù)數(shù)據(jù)庫DB中有s%的事務(wù)包含XY，則稱關(guān)聯(lián)規(guī)則X

Y的支持度為s%。支持度是一個概率值。2.關(guān)聯(lián)規(guī)則關(guān)聯(lián)（Associations）分析的目的是為了挖掘隱藏在數(shù)據(jù)間的相互關(guān)系，即對于給定的一組項目和一個記錄集，通過對記錄集的分析，得出項目集中的項目之間的相關(guān)性。項目之間的相關(guān)性用關(guān)聯(lián)規(guī)則來描述，關(guān)聯(lián)規(guī)則反映了一組數(shù)據(jù)項之間的密切程度或關(guān)系。

一個簡單事務(wù)數(shù)據(jù)庫模型數(shù)據(jù)庫DB：TID項001ACD002BCE003ABCE004BE表4-13.關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘：給定一組Item和記錄集合，挖掘出Item間的相關(guān)性，使其置信度和支持度分別大于用戶給定的最小置信度和最小支持度?！祭劫徺I商品事務(wù)如下表所示，設(shè)最小支持度為50%,最小可信度為50%,則可得到以下關(guān)聯(lián)規(guī)則：

A

C(50%,66.6%) C

A(50%,100%)

支持度可信度表4-24.關(guān)聯(lián)規(guī)則挖掘的分類（1）

基于規(guī)則中處理的變量的類別 基于規(guī)則中處理的變量的類別,關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。布爾型關(guān)聯(lián)規(guī)則：如果規(guī)則考慮的關(guān)聯(lián)是項“在”或“不在”，則關(guān)聯(lián)規(guī)則是布爾型的。例如，由購物籃分析得出的關(guān)聯(lián)規(guī)則。量化型關(guān)聯(lián)規(guī)則：如果描述的是量化的項或?qū)傩灾g的關(guān)聯(lián)，則該規(guī)則是量化型的關(guān)聯(lián)規(guī)則。例如：以下是量化型關(guān)聯(lián)規(guī)則的一個例子（其中X為表示顧客的變量，量化屬性age和income已經(jīng)離散化）：age(X,“30…39”)∧income(“42K…48K”) buys(X,“high_resolution_TV”)量化型關(guān)聯(lián)規(guī)則中也可以包含多種變量。例如：性別=“女”=>職業(yè)=“秘書”，是布爾型關(guān)聯(lián)規(guī)則；性別=“女”=>avg（月收入）=2300，涉及的收入是數(shù)值類型，所以是一個量化型關(guān)聯(lián)規(guī)則。（2）基于規(guī)則中數(shù)據(jù)的抽象層次 基于規(guī)則中數(shù)據(jù)的抽象層次,可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。

單層的關(guān)聯(lián)規(guī)則：所有的變量都不涉及不同抽象層次的項或?qū)傩浴? 例如：

buys(X,“computer”) buys(X,“printer”)

顧客X購買的商品不涉及不同抽象層次（“computer”

和“printer”在同一個抽象層），因此是單層關(guān)聯(lián)規(guī)則。多層的關(guān)聯(lián)規(guī)則：變量涉及不同抽象層次的項或?qū)傩浴? 例如：

age(X,“30…39”) buys(X,“l(fā)aptopcomputer”) age(X,“30…39”) buys(X,“computer”) 顧客X購買的商品涉及不同抽象層次（“computer”

在比“l(fā)aptopcomputer”高的抽象層），因此是多層關(guān)聯(lián)規(guī)則。

（3）基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù),關(guān)聯(lián)規(guī)則可以分為單維的和多維的。

單維關(guān)聯(lián)規(guī)則：處理單個維中屬性間的關(guān)系，即在單維的關(guān)聯(lián)規(guī)則中，只涉及到數(shù)據(jù)的一個維。 例如：用戶購買的物品：“咖啡=>砂糖”，這條規(guī)則只涉及到用戶的購買的物品。多維關(guān)聯(lián)規(guī)則：處理多個維中屬性之間的關(guān)系，即在多維的關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會涉及多個維。 例如：性別=“女”=>職業(yè)=“秘書”，這條規(guī)則就涉及到兩個維中字段的信息，是兩個維上的一條關(guān)聯(lián)規(guī)則。給出了關(guān)聯(lián)規(guī)則的分類之后，就可以考慮某個具體的關(guān)聯(lián)規(guī)則挖掘算法適用于哪一類規(guī)則的挖掘，某類關(guān)聯(lián)規(guī)則又可以用哪些不同的方法進行處理。最簡單的是單維、單層、布爾型的關(guān)聯(lián)規(guī)則。1.術(shù)語關(guān)聯(lián)規(guī)則挖掘即給定一組Item和記錄集合，挖掘出Item間的相關(guān)性，使其置信度和支持度分別大于用戶給定的最小置信度和最小支持度。

4.2關(guān)聯(lián)規(guī)則挖掘的過程〖定義4－4〗在關(guān)聯(lián)規(guī)則挖掘算法中，把項目的集合稱為項集（itemset），包含有k個項目的項集稱為k-項集。包含項集的事務(wù)數(shù)稱為項集的出現(xiàn)頻率，簡稱為項集的頻率或支持度計數(shù)。如果項集的出現(xiàn)頻率大于或等于最小支持度s與D中事務(wù)總數(shù)的乘積，則稱該項集滿足最小支持度s。如果項集滿足最小支持度，則稱該項集為頻繁項集（frequentitemset）?！祭揭粋€食品連鎖店保留著每周的事務(wù)記錄，其中每一條事務(wù)表示在一項收款機業(yè)務(wù)中賣出的項目。連鎖店的管理會收到一個事務(wù)匯總報告，報告表明了每種項目的銷售量是多少。此外，他們要定期了解哪些項目經(jīng)常被顧客一起購買。他們發(fā)現(xiàn)顧客購買了花生醬后，100%地會購買面包。而且，顧客購買了花生醬后，有33%也購買果凍。不過，所有事務(wù)中大約只有50%包含花生醬。被用于在其中尋找關(guān)聯(lián)規(guī)則的數(shù)據(jù)庫可以看作為一個元組集合，每個元組包含一組項目。一個元組可能是：

{花生醬、面包、果凍}包含三個項目：花生醬、面包、果凍每個項目表示購買的一種產(chǎn)品一個元組是一次購買的產(chǎn)品列表演示關(guān)聯(lián)規(guī)則的樣本數(shù)據(jù)事務(wù)項目t1面包、果凍、花生醬t2面包、花生醬t3面包、牛奶、花生醬t4啤酒、面包t5啤酒、牛奶表4-3找出的所有項目集合的支持度集合支持度集合支持度啤酒40啤酒、面包、牛奶0面包80啤酒、面包、花生醬0果凍20啤酒、果凍、牛奶0牛奶40啤酒、果凍、花生醬0花生醬60啤酒、牛奶、花生醬0啤酒、面包20面包、果凍、牛奶0啤酒、果凍0面包、果凍、花生醬20啤酒、牛奶20面包、牛奶、花生醬20啤酒、花生醬0果凍、牛奶、花生醬0面包、果凍、20啤酒、面包、果凍、牛奶0面包、果凍20啤酒、面包、果凍、花生醬0面包、花生醬60啤酒、面包、牛奶、花生醬0果凍、牛奶0啤酒、果凍、牛奶、花生醬0果凍、花生醬20面包、果凍、牛奶、花生醬0牛奶、花生醬20啤酒、面包、果凍、牛奶、花生醬0啤酒、面包、果凍0項目的個數(shù)成指數(shù)增長：從5個項目的集合得到31個項目集合（忽略空集）表4-42．關(guān)聯(lián)規(guī)則的挖掘過程最常用的關(guān)聯(lián)規(guī)則挖掘方法被分解為下面兩步：第1步：找出所有的頻繁項集，即找出支持度大于或等于給定的最小支持度閾值的所有項集?？梢詮?到k遞歸查找k-頻繁項集。第2步：由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，即找出滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則。找出滿足定義的大項目集從大項目集（頻繁項目集）生成關(guān)聯(lián)規(guī)則〖定義4－5〗大（頻繁）項目集是出現(xiàn)次數(shù)大于閾值S的項目集。用符號L表示大項目集組成的整個集合，用

表示一個特定的大項目集。一旦找出大項目集，則對于任何有趣的關(guān)聯(lián)規(guī)則X

Y，在頻繁項目集的集合中一定有XY。任何大項目集的子集也是大的4.3

大項目集關(guān)聯(lián)規(guī)則中使用了大量的符號，這些符號匯總?cè)缦?。一個特定符號所帶的下標表示所考慮的集合的大小，例如，lk表示一個大小為k的項目集。一些算法將事務(wù)集合分為若干個分區(qū)，在這種情況下，用p表示分區(qū)的數(shù)目，用上標表明分區(qū)的編號。例如，Di表示D的第i個分區(qū)。關(guān)聯(lián)規(guī)則使用的符號符號描述符號描述D事務(wù)數(shù)據(jù)庫X

Y關(guān)聯(lián)規(guī)則tiD中的事務(wù)L大項目集的集合s支持度lL中的大項目集

可信度C候選項目集的集合X，Y項目集p分區(qū)的數(shù)目表10-5幾個概念：潛在的大項目集稱為候選。所有被計數(shù)的（潛在大的）項目集的集合稱為候選項目集C。關(guān)聯(lián)規(guī)則使用的一個性能度量指標是C的大小。找出所有大項目集以后，關(guān)聯(lián)規(guī)則的生成變得非常直接。有關(guān)算法：改自[AS94]，用support返回輸入項目集的支持度。輸入：

D //事務(wù)數(shù)據(jù)庫

I //項目集合

L //大項目集

s //支持度

//可信度（置信度）輸出:

R //滿足s和

的關(guān)聯(lián)規(guī)則集合ARGen算法：

R=；

foreachlLdo foreachxlsuchthatx

do

if

support(l)/support(x)

then

R=R

{x

(l-x)}；有關(guān)算法演示：參考表4-3、4-4假定輸入的支持度和可信度分別為s=30%和

=50%。利用該s值得到如下大項目集的集合：L={{啤酒},{面包},{牛奶}，{花生醬},{面包、花生醬}}查看最后一個大項目集可以生成的關(guān)聯(lián)規(guī)則,其中：l={面包、花生醬}有兩個非空子集：{面包}和{花生醬}對于第一個非空子集，可得：support({面包、花生醬})/support({面包})=60/80=0.75意味著關(guān)聯(lián)規(guī)則：“面包

花生醬”的置信度為75%，因為其置信度高于

，所以是一條有效的關(guān)聯(lián)規(guī)則。演示關(guān)聯(lián)規(guī)則的樣本數(shù)據(jù)事務(wù)項目t1面包、果凍、花生醬t2面包、花生醬t3面包、牛奶、花生醬t4啤酒、面包t5啤酒、牛奶表4-3找出的所有項目集合的支持度集合支持度集合支持度啤酒40啤酒、面包、牛奶0面包80啤酒、面包、花生醬0果凍20啤酒、果凍、牛奶0牛奶40啤酒、果凍、花生醬0花生醬60啤酒、牛奶、花生醬0啤酒、面包20面包、果凍、牛奶0啤酒、果凍0面包、果凍、花生醬20啤酒、牛奶20面包、牛奶、花生醬20啤酒、花生醬0果凍、牛奶、花生醬0面包、果凍、20啤酒、面包、果凍、牛奶0面包、果凍20啤酒、面包、果凍、花生醬0面包、花生醬60啤酒、面包、牛奶、花生醬0果凍、牛奶0啤酒、果凍、牛奶、花生醬0果凍、花生醬20面包、果凍、牛奶、花生醬0牛奶、花生醬20啤酒、面包、果凍、牛奶、花生醬0啤酒、面包、果凍0項目的個數(shù)成指數(shù)增長：從5個項目的集合得到31個項目集合（忽略空集）表4-4對于第二個非空子集，可得：support({面包、花生醬})/support({花生醬})=60/60=1意味著關(guān)聯(lián)規(guī)則：“花生醬

面包”的置信度為100%，也是一條有效的關(guān)聯(lián)規(guī)則。找出大項目集的算法可以很簡單，但代價很高。簡單的方法是：對出現(xiàn)在事務(wù)中的所有項目集進行計數(shù)。給定一個大小為m的項目集合，共有2m個子集，去掉空集，則潛在的大項目集數(shù)為2m-1。隨著項目數(shù)的增多，潛在的大項目集數(shù)成爆炸性增長。（當m=5，為31個；當m=30，變成1073741823個）解決問題的難點：如何高效確定所有大項目集。大部分關(guān)聯(lián)規(guī)則算法都利用巧妙的方法來減少要計數(shù)的項目集。4.4關(guān)聯(lián)規(guī)則挖掘的Apriori算法4.4.1Apriori算法的基本思想Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則大（頻繁）項目集的算法。它使用一種稱作逐層搜索的迭代算法，通過k-項集用于探索（k+1）-項集。已經(jīng)為大部分商業(yè)產(chǎn)品所使用。Apriori算法的基本思想是：首先，通過掃描數(shù)據(jù)集，產(chǎn)生一個大的候選數(shù)據(jù)項集,并計算每個候選數(shù)據(jù)項發(fā)生的次數(shù)，然后基于預先給定的最小支持度生成頻繁1-項集的集合，該集合記作；然后基于和數(shù)據(jù)集中的數(shù)據(jù)，產(chǎn)生頻繁2-項集；用同樣的方法，直到生成頻繁n-項集，其中已不再可能生成滿足最小支持度的（N+1）－項集。最后，從大數(shù)據(jù)項集中導出規(guī)則。在第一次迭代的第一步中，產(chǎn)生的候選集包含所有1-項集，實為數(shù)據(jù)庫中所有的項，再計算各自的支持度。實例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}21.大項目集的性質(zhì)

大項目集的任一子集也一定是大的。大項目集也稱作是向下封閉的，如果一個項目集滿足最小支持度的要求，其所有的子集也滿足這一要求。其逆命題：如果知道一個項目集是小的，就不需要生成它的任何超集來作為它的候選集，因為它們也一定是小的。Apriori性質(zhì)基于如下事實：根據(jù)定義，如果項集I不滿足最小支持度閾值min_sup，則I不是頻繁的，即sup（I）<min_sup。如果將項A添加到I，則結(jié)果項集（即I∪A）不可能比I更頻繁出現(xiàn)。因此，I∪A也不是頻繁的，即sup（I∪A）<min_sup。頻繁項集的Apriori性質(zhì)用于壓縮搜索空間（剪枝），以提高逐層產(chǎn)生頻繁項集的效率。Apriori算法利用了大項目集的這些性質(zhì)用圖表示上述性質(zhì)，例子中有四個項目{A，B，C，D}，格中的線表示子集關(guān)系，大項目集的性質(zhì)表明：如果原來的項目集是大的，則在路徑中位于其上的任何集合也一定是大的。ABDCABACADBCBDCD?ABCABDBCDACDABCD{A，B，C，D}項目集的格結(jié)構(gòu)項目{ACD}的非空子集是：{AC，AD，CD，A，C，D}如果{A，C，D}是大的，則其每一個子集也是大的，如果其任何一個子集是小的，則{A，C，D}也是小的。?ABDCABACADBCBDCDABCABDBCDACDABCD{A，C，D}的子集項目{ACD}的非空子集是：{AC，AD，CD，A，C，D}按照Apriori算法：在第i趟掃描的過程中，對Ci進行計數(shù)，只有那些大的候選集被用于生成下一趟掃描的候選集，即用Li生成Ci+1。只有一個項目集的所有子集都是大的，它才被認為是候選。為了生成大小為i+1的候選，要對前一趟掃描發(fā)現(xiàn)的大項目集進行連接運算。表示：Lk*Lk={X

Y其中X，Y

Lk，|X

Y|=k–1}例：對表4-3進行演算，其中s=30%，

=50%假如有項目集合I={1，2，3，4，5}，有事務(wù)集T：

1,2,31,2,41,3,41,2,3,51,3,52,4,51,2,3,4

設(shè)定minsup=3/7，misconf=5/7。首先：生成頻繁項目集：

1-頻繁項目集：{1}，{2}，{3}，{4}，{5}

生成2-頻繁項目集：根據(jù)1-頻繁項目集生成所有的包含2個元素的項目集：任意取兩個只有最后一個元素不同的1-頻繁項目集，求其并集，由于每個1-頻繁項目集元素只有一個，所以生成的項目集如下：

{1，2}，{1，3}，{1，4}，{1，5}

{2，3}，{2，4}，{2，5}

{3，4}，{3，5}

{4，5}計算它們的支持度，發(fā)現(xiàn)只有{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{2，5}的支持度滿足要求，因此求得2-頻繁項目集：

{1，2}，{1，3}，{1，4}，{2，3}，{2，4}

生成3-頻繁項目集：因為{1，2}，{1，3}，{1，4}除了最后一個元素以外都相同，所以求{1，2}，{1，3}的并集得到{1，2，3}，

{1，2}和{1，4}的并集得到{1，2，4}，{1，3}和{1，4}的并集得到{1，3，4}。但是由于{1，3，4}的子集{3，4}不在2-頻繁項目集中，所以需要把{1，3，4}剔除掉。然后再來計算{1，2，3}和{1，2，4}的支持度，發(fā)現(xiàn){1，2，3}的支持度為3/7，{1，2，4}的支持度為2/7，所以需要把{1，2，4}剔除。同理可以對{2，3}，{2，4}求并集得到{2，3，4}，但是{2，3，4}的支持度不滿足要求，所以需要剔除掉。因此得到3-頻繁項目集：{1，2，3}。到此頻繁項目集生成過程結(jié)束。注意生成頻繁項目集的時候，頻繁項目集中的元素個數(shù)最大值為事務(wù)集中事務(wù)中含有的最大元素個數(shù)，即若事務(wù)集中事務(wù)包含的最大元素個數(shù)為k，那么最多能生成k-頻繁項目集，這個原因很簡單，因為事務(wù)集合中的所有事務(wù)都不包含（k+1）個元素，所以不可能存在（k+1）-頻繁項目集。在生成過程中，若得到的頻繁項目集個數(shù)小于2，生成過程也可以結(jié)束了。現(xiàn)在需要生成強關(guān)聯(lián)規(guī)則：這里只說明3-頻繁項目集生成關(guān)聯(lián)規(guī)則的過程：對于集合{1，2，3}先生成1-后件的關(guān)聯(lián)規(guī)則：（1，2）—>3，

置信度=3/4（1，3）—>2，置信度=3/5（2，3）—>1

置信度=3/3（1，3）—>2的置信度不滿足要求，所以剔除掉。因此得到1后件的集合{1}，{3}，然后再以{1，3}作為后件

2—>1，3

置信度=3/5不滿足要求，所以對于3-頻繁項目集生成的強關(guān)聯(lián)規(guī)則為：（1，2）—>3和（2，3）—>1。演示關(guān)聯(lián)規(guī)則的樣本數(shù)據(jù)事務(wù)項目t1面包、果凍、花生醬t2面包、花生醬t3面包、牛奶、花生醬t4啤酒、面包t5啤酒、牛奶表4-3回憶找出的所有項目集合的支持度集合支持度集合支持度啤酒40啤酒、面包、牛奶0面包80啤酒、面包、花生醬0果凍20啤酒、果凍、牛奶0牛奶40啤酒、果凍、花生醬0花生醬60啤酒、牛奶、花生醬0啤酒、面包20面包、果凍、牛奶0啤酒、果凍0面包、果凍、花生醬20啤酒、牛奶20面包、牛奶、花生醬20啤酒、花生醬0果凍、牛奶、花生醬0面包、果凍、20啤酒、面包、果凍、牛奶0面包、果凍20啤酒、面包、果凍、花生醬0面包、花生醬60啤酒、面包、牛奶、花生醬0果凍、牛奶0啤酒、果凍、牛奶、花生醬0果凍、花生醬20面包、果凍、牛奶、花生醬0牛奶、花生醬20啤酒、面包、果凍、牛奶、花生醬0啤酒、面包、果凍0項目的個數(shù)成指數(shù)增長：從5個項目的集合得到31個項目集合（忽略空集）表4-4趟數(shù)候選大項目集1{啤酒}，{面包}，{果凍}，{牛奶}，{花生醬}{啤酒}，{面包}，{牛奶}，{花生醬}2{啤酒，面包}，{啤酒，牛奶}，{啤酒，花生醬}，{面包，牛奶}，{面包，花生醬}，{牛奶，花生醬}{面包，花生醬}對表4-3采用Apriori算法為了組合出下一級候選，每個項目集除了一個項目之外，其它的項目都相同。因為只有一個大小為2的大項目集，所以沒有大小為3的候選4.4.2Apriori算法中的關(guān)鍵步驟Apriori算法中的關(guān)鍵步驟是由Lk-1找Lk，該步驟可分為兩步：第1步（連接）：為找Lk，通過Lk-1與自己連接產(chǎn)生候選K-項集的集合。將該候選項集的集合記作Ck。設(shè)l1和l2是Lk-1中的項集，記號li[j]表示li的第j項。執(zhí)行連接Lk-1和Lk-1，其中Lk-1的元素是可連接，如果它們前（k-2）個項相同而且第（k-2）項不同（為簡單計，設(shè)l1[k-1]<l2[k-1]），即：l1[1]=l2[1]∧l1[2]=l2[2]∧……∧l1[k-2]=l2[k-2]∧l1[k-1]<l2[k-1]則Lk-1的元素l1和l2是可連接的。連接l1和l2產(chǎn)生的結(jié)果的項集是l1[1]l1[2]……l1[k-1]l2[k-1]。第2步（剪枝）：Ck是Lk的超集，即它的成員可以是也可以不是頻繁的，但所有的頻繁k-項集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每個候選的計數(shù)，從而確定Lk。然而，Ck可能很大，這樣所涉及的計算量就很大。為壓縮Ck，可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的（k-1）-項集都不可能是頻繁k-項集的子集。因此，如果一個候選k-項集的（k-1）-子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。一個稱為Apriori-Gen的算法：用于生成除第一趟之外的每一趟掃描的候選項目集。所有的單元素項目集在第一趟時作為候選使用。前一趟發(fā)現(xiàn)的大項目集的集合Li-1與自身進行連接運算以確定候選。為了組合出下一級候選，每個項目集除了一個項目之外，其它的項目都相同。Apriori-Gen算法實例：一個女士服裝店在一天中有20個收款機事務(wù)記錄，如表：衣服事務(wù)樣本事務(wù)項目事務(wù)項目t1罩衣t11T恤t2鞋，裙子，T恤t12罩衣，牛仔褲，鞋，裙子，T恤t3牛仔褲，T恤t13牛仔褲，鞋，短褲，T恤t4牛仔褲，鞋，T恤t14鞋，裙子，T恤t5牛仔褲，短褲t15牛仔褲，T恤t6鞋，T恤t16裙子，T恤t7牛仔褲，裙子t17罩衣，牛仔褲，裙子t8牛仔褲，鞋，短褲，T恤t18牛仔褲，鞋，短褲，T恤t9牛仔褲t19牛仔褲t10牛仔褲，鞋，T恤t20牛仔褲，鞋，短褲，T恤Apriori-Gen實例掃描候選集大項目集1{罩衣}，{牛仔褲}，{鞋}，{短褲}，{裙子}，{T恤}{牛仔褲}，{鞋}，{短褲}，{裙子}，{T恤}2{牛仔褲，鞋}，{牛仔褲，短褲}，{牛仔褲，裙子}，{牛仔褲，T恤}，{鞋，短褲}，{鞋，裙子}，{鞋，T恤}，{短褲，裙子}，{短褲，T恤}，{裙子，T恤}{牛仔褲，鞋}，{牛仔褲，短褲}，{牛仔褲，T恤}，{鞋，短褲}，{鞋，T恤}，{短褲，T恤}，{裙子，T恤}3{牛仔褲，鞋，短褲}，{牛仔褲，鞋，T恤}，{牛仔褲，短褲，T恤}，{牛仔褲，裙子，T恤}，{鞋，短褲，T恤}，{鞋，裙子，T恤}，{短褲，裙子，T恤}{牛仔褲，鞋，短褲}，{牛仔褲，鞋，T恤}，{牛仔褲，短褲，T恤}，{鞋，短褲，T恤}4{牛仔褲，鞋，短褲，T恤}{牛仔褲，鞋，短褲，T恤}5

Apriori-Gen算法處理過程：第一趟掃描得到6個候選項目集，其中5個候選是大的。對該5個候選應(yīng)用Apriori-Gen算法，將每一個候選與另外4個進行組合，得到第二趟掃描：4+3+2+1=10個候選，其中7個候選是大的。在7個候選中再應(yīng)用Apriori-Gen算法，將每一個項目集與另外一個與之具有一個公共成員的項目集進行連接運算，第三趟掃描后得到4個大項目集。第四趟掃描后只剩下一個大項目集，也不存在下一趟計數(shù)為5個的新項目集。在客戶關(guān)系管理（CRM）理論中有一個經(jīng)典的2/8原則，即80%利潤來自20%客戶。那么，這20%的客戶都有什么特征呢？調(diào)查發(fā)現(xiàn)，大部分企業(yè)每年有20%～50%的客戶是變動的。企業(yè)一方面在挖空心思爭取新客戶，另一面卻不斷失去老客戶。有沒有辦法找出，失去的是哪一類型的客戶，得到的又是哪種類型的客戶。在競爭激烈的商業(yè)時代，資源占有成為決定企業(yè)生死成敗的關(guān)鍵。在客戶關(guān)系方面，企業(yè)總希望建立與客戶最穩(wěn)固的關(guān)系，并最有效率地把這種關(guān)系轉(zhuǎn)化為利潤，即留住老顧客、發(fā)展新顧客并鎖定利潤率最高的客戶，這也就是CRM要重點研究的問題。為了實現(xiàn)這個目標，企業(yè)就需要盡可能地了解客戶的行為，但這種了解不可能通過與客戶接觸直接獲得，因為企業(yè)不可能挨個與客戶交談，而且他們所需要的信息單個客戶往往無法提供。4.9

關(guān)聯(lián)規(guī)則挖掘在CRM中的應(yīng)用4.9.1CRM簡介企業(yè)所能做的，就是盡可能收集顧客的信息，借助各種分析方法，透過無序的、表層的信息挖出內(nèi)在的知識和規(guī)律，這就當前十分流行的數(shù)據(jù)挖掘技術(shù)所研究的。在挖出大量信息之后，企業(yè)就可以根據(jù)這些規(guī)律或用這些信息設(shè)計數(shù)學模型，對未發(fā)生行為做出結(jié)果預測，為企業(yè)的綜合經(jīng)營決策、市場策劃提供依據(jù)。在CRM中，數(shù)據(jù)挖掘是從大量的有關(guān)客戶的數(shù)據(jù)中挖掘出隱含的、先前未知的、對企業(yè)決策有潛在價值的知識和規(guī)則。

數(shù)據(jù)挖掘的第一步就是挖出顧客的特征描述。企業(yè)在了解客戶信息方面永不滿足，他們不僅會想方設(shè)法了解顧客的地址、年齡、性別、收入、職業(yè)、教育程度等基本信息，對婚姻、配偶、家庭狀況、疾病、愛好等等的收集也是不遺余力。也由于這個原因，在談到CRM的時候，個人隱私便成為一個敏感話題。

（1）客戶特征：通過客戶行為分析，歸類出消費額最高、最為穩(wěn)定的客戶群，確定為“黃金客戶”。針對不同的客戶檔次，確定相應(yīng)的營銷投入。對于“黃金客戶”，往往還需要制定個性化營銷策略，以求留住高利潤客戶。所以，不要期待在CRM時代繼續(xù)人人平等。當然，成功的CRM不會讓顧客感覺到歧視。如果你不幸發(fā)現(xiàn)自己受到的待遇比別人低，很有可能別人是“黃金”，而你是“白銀”或者“黑鐵”。

（2）“黃金客戶”：通過與客戶接觸，收集大量客戶消費行為信息，通過分析，得出客戶最關(guān)注的方面，從而有針對性地進行營銷活動，把錢花在“點”上。同樣的廣告內(nèi)容，根據(jù)客戶不同的行為習慣，有的人會接到電話，有的人就可能收到信函；同一個企業(yè)，會給他們的客戶發(fā)送不同的信息，而這些信息往往就是顧客感興趣的方面。不要驚訝于為什么企業(yè)給你送來的正是你最需要的、最滿意的，你和其他與你相似的顧客的數(shù)據(jù)，在企業(yè)的數(shù)據(jù)倉庫里經(jīng)不住百般“拷打”，已經(jīng)集體招供了。

（3）客戶關(guān)注點：（4）客戶忠誠度：得出客戶持久性、牢固性及穩(wěn)定性分析。對于高忠誠度客戶，要注意保持其良好印象，對于低忠誠度客戶，要么不要浪費錢財，要么就下大工夫把他們培養(yǎng)成忠誠客戶。在CRM中，必不可少的要素是將海量的、復雜的客戶行為數(shù)據(jù)集中起來的，形成整合的、結(jié)構(gòu)化的數(shù)據(jù)倉庫（DataWearhouse），這是數(shù)據(jù)挖掘的基礎(chǔ)。在此基礎(chǔ)上，就需要借助大量的知識和方法，把表面的、無序的信息整合，揭示出潛在的關(guān)聯(lián)性和規(guī)律，從而用于指導決策。4.9.2關(guān)聯(lián)規(guī)則挖掘在CRM中的應(yīng)用類別

主要類別：橫向關(guān)聯(lián)

次序關(guān)聯(lián)

橫向關(guān)聯(lián)是挖掘表面看似獨立的事件間的相互關(guān)系，例如“90%的顧客在一次購買活動中購買商品A的同時購買商品B”之類的知識。比如經(jīng)典的“尿布和啤酒”的故事，就是利用這種方法，發(fā)現(xiàn)二者之間有很高的相關(guān)系數(shù)，引起重視，然后深入分析后才找出內(nèi)在原因的。

橫向關(guān)聯(lián)