1、統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組關聯規則關聯規則-carma continuous association rule mining algorithm報告人：徐啟元報告人：徐啟元指導教師指導教師:謝邦昌謝邦昌日期：日期：2007年年11月月30日日統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組目錄目錄關聯規則基本概念關聯規則基本概念carma算法簡介算法簡介carma模塊的基本概念模塊的基本概念案例分析及案例分析及clementine操作步驟操作步驟購物籃分析購物籃分析-tabular類型數據類型數據網絡日志分析

2、網絡日志分析-transactional類型數據類型數據值得注意的問題值得注意的問題carma算法原理（參考）算法原理（參考）統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組關聯規則算法簡介關聯規則算法簡介 關聯分析的目的是尋找數據項間的相關關聯分析的目的是尋找數據項間的相關性常用技術：性常用技術： 關聯規則：即尋找在同一個事件中出現關聯規則：即尋找在同一個事件中出現的不同項目的相關性的不同項目的相關性 例如：找出顧客經常同 時購買哪些商品。網民 瀏覽的網頁之間有沒有 什么關聯性。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組c

3、arma算法簡介算法簡介carma是一種比較新的關聯規則算法，它是1999年由berkeley大學的christian hidber教授提出來的。1234能夠處理在線連續交易流數據僅需一次，最多兩次對數據的掃描就可以構造出結果集允許在算法執行過程中按需要重新設置支持度占用內存少carmaon-line統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma模塊中的基本概念模塊中的基本概念 antecedent&consequent 它們指的是規則的前項和后項。 instances對于每一條規則，它的instances值指的是所有記錄中包含該規則的ant

4、ecedent的記錄的數量。面包面包牛奶牛奶前項前項antecedent后項后項consequentidp1p2p3p41breadcheesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbread總共4條購買數據，其中有三條都包含bread，那么該條規則的instances等于3統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma模塊中的基本概念模塊中的基本概念 support 它的定義和instances很接 近，不同的是support描述 的

5、不是數量，而是比例。 rule support 它在support定義的基礎 上更進一步，它指的是 所有記錄中既包含某規 則的antecedent，又包含 consequent的記錄所占 的比例。idp1p2p3p41breadcheesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbreadsupport=3/4100%=75%四條記錄中只有一條既包含了前項bread，又包含了后向milk，所以rule support=1/4100%=25%統計分析、數據挖掘與商業智能應用研究小組統

6、計分析、數據挖掘與商業智能應用研究小組carma模塊中的基本概念模塊中的基本概念 confidence confidence = rule support / support 該指標反映的是規則預測的 準確程度。 deployability deployability = support rule support 它的作用與confidence類似。idp1p2p3p41breadcheesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbread根據規則“面包=牛奶”，那么購買了面包的

7、第一、二及四行都會被預測購買了牛奶，但事實上這三個預測只有第二個是正確的，所以confidence=1/3100%=33.3%統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma模塊中的基本概念模塊中的基本概念 liftlift在已知某規則的consequent發生的先驗概率的情況下，某規則的lift被定義為confidence和該先驗概率的比率值。idp1p2p3p41breadcheesebutterwater2watermilkbreadnoodle3milknoodlemeatbeer4fishsoftdrinkfrozenmealbread那么對

8、于一條記錄，那么不采用任何規則進行預測，隨便猜測該顧客是否該買牛奶的正確率是50%已知有50%的人購買了牛奶：）如果采用“面包=牛奶”的規則進行預測的話，正確率，即confidence=33.3%比隨便猜測的正確率還低。那么此時的lift值為多少呢？ lift=33.3%/50%=66.6%1的規則才是有意義的規則統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組源數據格式源數據格式 carmacarma模塊能夠處理一下兩種格式的數據模塊能夠處理一下兩種格式的數據 tabular數據格式數據格式 transactional數據格式數據格式 統計分析、數據挖掘與商業

9、智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組案例研究之購物籃分析案例研究之購物籃分析 數據準備數據準備 使用數據為clementine自帶的baskets1n數據集； 該數據集樣本量為1000，每筆交易包含了顧客的卡號、性別、年齡、收入、付款方式等一系列個人信息，以及其購買的各種食品清單； 該數據集為tabulartabular格式格式的數據。 研究目的研究目的 為超市貨架的擺放提供科學的依據； 為超市商品促銷決策提供支持。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組案例研究案例研究統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業

10、智能應用研究小組購物籃分析購物籃分析 加入加入type模塊對變量類型進行設置。模塊對變量類型進行設置。先點擊read values將各個變量實例化。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組購物籃分析購物籃分析 將將carma 模塊加入模塊加入 流中，并雙流中，并雙 擊打開進行擊打開進行 參數設置。參數設置。點擊點擊統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組購物籃分析購物籃分析 對對model選項卡選項卡進行設置。修改進行設置。修改rule support、rule confidence以及以及rule size的的大

11、小。大小。點擊此處，打開model選項卡編輯對這三個選項進行編輯以控制輸出的規則的數目統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組購物籃分析購物籃分析 對對expert選項選項卡進行設置，卡進行設置，如果對如果對carma算法比較了解算法比較了解的用戶，可以的用戶，可以對該選項卡進對該選項卡進行設定以獲得行設定以獲得使使carma模塊模塊具有更好的性具有更好的性能。能。選擇此項，則輸出的規則中后項（consequent）只能由一個元素。選擇該選項可以讓carma算法周期性的剔除掉當前不太重要的規則，加速建模。設定周期的大小，周期設定的越小，則越省內存，但是c

12、arma算法執行時間常；反之，則短。設定該選項可以加速carma算法的執行。其大致思想是：一開始先給定一個較高的support值，將不顯著的規則排除在外，然后再一次降低support值。設定support值降低的速度選擇該項，則carma模型會輸出不包含antecedent的規則。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組購物籃分析購物籃分析執行后建執行后建立的模型立的模型 會會顯示在顯示在canvas內。內。共產生共產生16條規則條規則每一行分別顯示了一組每一行分別顯示了一組規則，以及度量該規則規則，以及度量該規則的一組指標，如：的一組指標，如：lift

13、、support等。等。點擊該圖標可點擊該圖標可以按指定規則以按指定規則篩選出自己想篩選出自己想要的規則要的規則。生成對應規則集的節點，包括三生成對應規則集的節點，包括三種節點：種節點：select node、filtered node以及以及rule set節節點。點。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組購物籃分析購物籃分析置信度（置信度（confidence）最高的前三個規則：）最高的前三個規則：cannedveg & beerfrozenmealfrozenmeal & beercannedvegcannedveg &

14、frozenmealbeer促銷統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組購物籃分析購物籃分析carma模型可以模型可以直接放在流中對直接放在流中對數據進行打分預數據進行打分預測（測（scoring）。）。在打分之前可以在打分之前可以雙擊模型打開雙擊模型打開settings選項卡進選項卡進行相關的參數設行相關的參數設置。置。設定用于預測的規則個數為選取規則設定標準，從而可以根據該規則選出最顯著的n條規則，n由上一個選項設定。設定該項，則允許用于預測的n條規則可以有相同的后項，即可以允許幾條規則有相同的預測結果。勾選該項，則在應用規則進行預測之前，系統會剔除

15、掉不符合要求的數據行，不對其進行預測。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組購物籃分析購物籃分析對carma模型設置好了以后就可以將carma模型加入流中對數據進行預測了，本文僅用一條規則進行預測，結果存入表中（見下頁）。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組購物籃分析購物籃分析預測值預測值預測置信度預測置信度所使用規所使用規則的編號則的編號統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組購物籃分析購物籃分析用carma模型預測顧客的購買行為confectioneryfreshm

16、eatdairywine統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組購物籃分析購物籃分析除了直接使用生成的carma模型進行預測外，還有一種預測方式即使用rule set。 使用generate菜單生成想要的rule set節點，并將該節點放入流中進行預測。點擊確定以后可以生成點擊確定以后可以生成一個規則集節點，將該一個規則集節點，將該節點加入流中就可以進節點加入流中就可以進行預測了。行預測了。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組案例研究之網絡日志分析案例研究之網絡日志分析 數據準備數據準備 使用數據為某網站五天的

17、訪問日志； 該數據集記錄數為173665，每行記錄對應用戶對服務器的一個頁面請求，記錄了用戶ip地址、請求時間、請求頁面url、訪問協議、請求狀態以及端口號等信息。本文為了簡化僅引入前三個變量，且頁面已經過分類，訪問已按事務劃分； 該數據集為transactionaltransactional格式格式的數據。 研究目的研究目的 找出用戶的訪問模式，為網站結構上的調整和網站經營決策提供支持。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組網絡日志分析網絡日志分析加載數據集加載數據集統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組網絡

18、日志分析網絡日志分析 使用使用carma模塊來處理模塊來處理transactional格式的網絡日格式的網絡日志數據，并從志數據，并從中找出關聯規中找出關聯規則。則。 雙擊打開打開雙擊打開打開fields選項卡進選項卡進行編輯。行編輯。勾選該項，將carma模型處理的數據格式改為transactional格式指定數據的唯一標識，標識相同的記錄屬于同一個事務該欄用以指定交易數據字段，本文中這里指定的是當前請求的頁面種類。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組網絡日志分析網絡日志分析雙擊打開雙擊打開model選項卡進行編選項卡進行編輯，設定輯，設定rule

19、s support、rule confidence以及以及rule size等參等參數。數。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組網絡日志分析網絡日志分析 查看查看carma模型生成的規則集模型生成的規則集統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組網絡日志分析網絡日志分析數據中定義的第一類頁面為娛樂新聞版面，第二數據中定義的第一類頁面為娛樂新聞版面，第二類是灌水版面。類是灌水版面。訪問娛樂訪問娛樂新新聞聞版面版面訪問訪問灌水版灌水版訪問訪問灌水版面灌水版面訪問娛樂訪問娛樂新新聞聞版版整合整合訪問訪問量量將灌水版和娛

20、將灌水版和娛樂新聞版整合樂新聞版整合為一個為一個“我主我主娛樂娛樂”新版新版統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組值得注意的問題值得注意的問題 carma模型運算速度不是最快的，但模型運算速度不是最快的，但是它只需要對數據集一至兩遍的掃描就是它只需要對數據集一至兩遍的掃描就可以構造規則集；可以構造規則集； carma模型及可以處理模型及可以處理tabular格式的格式的數據，也可以處理數據，也可以處理transactional格式的格式的數據；數據； carma模型中需要設定的模型中需要設定的rule support的大小，而不是的大小，而不是supp

21、ort； carma模型不能處理數值型的數據。模型不能處理數值型的數據。統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma算法原理算法原理 carma算法也包括兩個部分算法也包括兩個部分 尋找頻繁項集 在頻繁項集的基礎上產生關聯規則 carma尋找頻繁項集的過程又分為尋找頻繁項集的過程又分為phase i和和phase ii phase i：產生頻繁項集的超集，即產生潛在頻繁項集v在phase i中可以隨時調整最小支持度 phase ii：對潛在頻繁項集v進行刪減得到最終的頻繁項集統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研

22、究小組carma算法原理算法原理 初始v為空集，將事務按照序號排序,逐條讀入事務數據，并計算以下三個整數存儲在v的支持格(support lattice)中：count(v)：v被插入v以后在事務數據庫中出現的次數firsttrans(v)：v被插入v時所在事務的事務序號maxmissed(v)：v被插入v之前已讀入的事務個數例如：項集a,b在j時刻進入v,當j時刻時以上三個整數的情況統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma算法原理算法原理 根據 count(v)、maxmissed(v)定義了v項集的支持度的上限和下限： minsupport

23、(v)是項集的實際支持度 maxsupport(v)用來判斷項集v用來是否可以保留在v中max( )(max( )( )/min( )( )/isupport vmissed vcount visupport vcount vi統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma算法原理算法原理 phase i中v產生的基本過程：初始v為空集(此時只可添加1-項集)， 讀入第i條事務數據v，給出當前的最小支持度i, 在計算過程中，算法自動調整最小支持度，即給每個事務以一個最小支持度，會形成一個最小支持度序列t個事務(1,2 , 3,) 如果v是1-項集:

24、如果第一次出現，則令count(v)1, maxmissed(v) 0(1-項集的maxmissed(v)規定為0), firsttrans(v) i,且將v加入v(1-項集自動進入v) 如果不是第一次出現，則count(v)count(v)+1; 統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma算法原理算法原理 如果v是k-項集(k=2)，則先按前述方式處理包含的所有1-項集，且： 如果第一次出現，判斷該k-項集是否可以進入v，且令count(v)1, firsttrans i,且 如果不是第一次出現，則項集各子集的count(v)count(v)+

25、1; “修剪”，默認每讀入500個事務作一次修剪(從效率角度考慮，其實可以讀入一條修剪一次)，即判斷支持格中所有k-項集的maxsupport(v)，如果小于當前的最小支持度i ,則剔除相應項集出v統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma算法原理算法原理 在phase i階段，k-項集v進入v的主要原則如果一個項集是頻繁項集，則其所有子集必定也是頻繁項集；反之，如一個項集的某個子集不是頻繁項集，則該項集必定也不是頻繁項集；carma在決定k-項集v進入頻繁項集v時，應確保v的所有真子集已在當前事務之前進入v中，這是v進入v的條件之一（要看所有子

26、集，若2項無所謂，若3項則需要檢驗其2項子集是否也在內）。項集v加入v的必要條件表述為：i為當前的事務序號，即v的所有真子集w都是頻繁項集且已在當前事務之前進入v中: ( ) max( )iwv wv and firsttrans wi andsupport wmax( )(max( )( )/support wmissed wcount wi其中：統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma算法原理算法原理 在phase i階段，k-項集v進入v的主要原則判斷v的真子集時應從包含項目較多的子集開始判斷，如果包含項目較多的子集已在v中，則包含項目較

27、少的子集也一定在v中。因此，不必檢查所有子集，只需要檢驗那些包含項目最多的子集即可。為提高效率不必檢驗所有真子集，只需要檢查那些：:| | 1 ( ) max( )iwvwvand wv and firsttrans wi andsupport w其中：|w|、 |v|為所包含的項目數kmax( )(max( )( )/support wmissed wcount wi其中：統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma算法原理算法原理計算maxsupport(v)的關鍵是計算maxmissed(v)maxmissed計算的依據一：其最大子集的頻繁程

28、度 在第在第i i個時刻個時刻， v的具有最大firsttrans的真子集w(|w|=|v|-1)，其支持度一定大于v的，即：max( )max( )iisupport wsupport v此時i是相等的明顯然max( )( )max( )( )missed wcount wmissed vcount v cmax( )( )max( ) 1missed wcount wmissed vmax( )max( )( ) 1missed vmissed wcount w統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組carma算法原理算法原理計算maxsupport

29、(v)的關鍵是計算maxmissed(v) 依據二：用戶以往定義的最小支持度的情況在i+1時刻，以往最小支持度序列表示為i(1,2 , 3, i)carma中定義了關于i的天花板(ceiling of )序列，記為天花板的含義是：當j i時(j=1,2,.i-1)：當j i時(j=1,2,.i-1)：i 123(,.,0,0,.)ii (,.)iiiii 例如：(0.3,0.7,0.9,0.5)1(0.3,0,0,0) 2(0.7,0.7,0,0) 3(0.9,0.9,0.9,0) 4(0.5,0.7,0.9,0.5) 統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研

30、究小組carma算法原理算法原理 計算maxsupport(v)的關鍵是計算maxmissed(v) 依據二：用戶以往定義的最小支持度的情況 總之有：主要取決于以往的一系列最小支持度11max( )min (1)()| 1,max( )( ) 1iimissed viavgvmissed wcount w 111| | 1max( )()1iiivsupportvavgi 11max( )(1)()| | 1iimissed viavgv 統計分析、數據挖掘與商業智能應用研究小組統計分析、數據挖掘與商業智能應用研究小組b(0,1,3)1,1carma算法原理算法原理111(0.3,0,0)0.3avg 222(0.9,0.9,0)0.9avg phase i舉例 事務序列t=(a,b,a,b,c,b,c),定義的支持度閥值序列=(0.3,0.9,0.5)vt1=a,b1=0.3va,bt2=a,b,c2=0.9va,b,c,a,ba,b的maxsupport均大于0.3,不能剔除出va(0,1,1)1,1b(0,1,1)1,1a(0,1,2)1,1b(0,1,2)1,1c(0,2,1)0.5,0.5a,b(1,2,1)0.5,1t3=b,cv