1、關聯(lián)規(guī)那么-CARMA Continuous Association Rule Mining Algorithm報告人：徐啟元指點教師:謝邦昌日期：2007年11月30日目錄關聯(lián)規(guī)那么根本概念CARMA算法簡介CARMA模塊的根本概念案例分析及Clementine操作步驟購物籃分析-Tabular類型數(shù)據(jù)網(wǎng)絡日志分析-Transactional類型數(shù)據(jù)值得留意的問題CARMA算法原理參考關聯(lián)規(guī)那么算法簡介關聯(lián)分析的目的是尋覓數(shù)據(jù)項間的相關性常用技術：關聯(lián)規(guī)那么：即尋覓在同一個事件中出現(xiàn)的不同工程的相關性 例如：找出顧客經(jīng)常同 時購買哪些商品。網(wǎng)民 閱讀的網(wǎng)頁之間有沒有 什么關聯(lián)性。CARMA算

2、法簡介CARMA是一種比較新的關聯(lián)規(guī)那么算法，它是1999年由Berkeley大學的Christian Hidber教授提出來的。1234可以處置在線延續(xù)買賣流數(shù)據(jù)僅需一次，最多兩次對數(shù)據(jù)的掃描就可以構造出結果集允許在算法執(zhí)行過程中按需求重新設置支持度占用內(nèi)存少CARMAOn-lineCARMA模塊中的根本概念Antecedent&Consequent 它們指的是規(guī)那么的前項和后項。Instances對于每一條規(guī)那么，它的Instances值指的是一切記錄中包含該規(guī)那么的antecedent的記錄的數(shù)量。面包牛奶前項Antecedent后項ConsequentIDP1P2P3P41breadc

3、heesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbread總共4條購買數(shù)據(jù)，其中有三條都包含bread，那么該條規(guī)那么的instances等于3CARMA模塊中的根本概念Support 它的定義和instances很接 近，不同的是support描畫 的不是數(shù)量，而是比例。Rule Support 它在Support定義的根底 上更進一步，它指的是 一切記錄中既包含某規(guī) 那么的antecedent，又包含 consequent的記錄所占 的比例。IDP1P2P3P41breadc

4、heesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbreadSupport=3/4100%=75%四條記錄中只需一條既包含了前項bread，又包含了后向milk，所以Rule Support=1/4100%=25%CARMA模塊中的根本概念Confidence Confidence = Rule Support / Support 該目的反映的是規(guī)那么預測的 準確程度。Deployability Deployability = Support Rule Support 它的作用與c

5、onfidence類似。IDP1P2P3P41breadcheesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbread根據(jù)規(guī)那么“面包=牛奶，那么購買了面包的第一、二及四行都會被預測購買了牛奶，但現(xiàn)實上這三個預測只需第二個是正確的，所以confidence=1/3100%=33.3%CARMA模塊中的根本概念Lift在知某規(guī)那么的consequent發(fā)生的先驗概率的情況下，某規(guī)那么的Lift被定義為Confidence和該先驗概率的比率值。IDP1P2P3P41breadchees

6、ebutterwater2watermilkbreadnoodle3milknoodlemeatbeer4fishsoftdrinkfrozenmealbread那么對于一條記錄，那么不采用任何規(guī)那么進展預測，隨意猜測該顧客能否該買牛奶的正確率是50%知有50%的人購買了牛奶：假設采用“面包=牛奶的規(guī)那么進展預測的話，正確率，即confidence=33.3%比隨意猜測的正確率還低。那么此時的Lift值為多少呢？ Lift=33.3%/50%=66.6%1的規(guī)那么才是有意義的規(guī)那么源數(shù)據(jù)格式CARMA模塊可以處置一下兩種格式的數(shù)據(jù)Tabular數(shù)據(jù)格式 Transactional數(shù)據(jù)格式 案例

7、研討之購物籃分析數(shù)據(jù)預備運用數(shù)據(jù)為clementine自帶的Baskets1n數(shù)據(jù)集；該數(shù)據(jù)集樣本量為1000，每筆買賣包含了顧客的卡號、性別、年齡、收入、付款方式等一系列個人信息，以及其購買的各種食品清單；該數(shù)據(jù)集為Tabular格式的數(shù)據(jù)。研討目的為超市貨架的擺放提供科學的根據(jù)；為超市商品促銷決策提供支持。案例研討購物籃分析參與type模塊對變量類型進展設置。先點擊Read Values將各個變量實例化。購物籃分析將CARMA 模塊參與 流中，并雙 擊翻開進展 參數(shù)設置。點擊點擊購物籃分析對Model選項卡進展設置。修正Rule Support、Rule Confidence以及Rule

8、Size的大小。點擊此處，翻開Model選項卡編輯對這三個選項進展編輯以控制輸出的規(guī)那么的數(shù)目購物籃分析對Expert選項卡進展設置，假設對CARMA算法比較了解的用戶，可以對該選項卡進展設定以獲得使CARMA模塊具有更好的性能。選擇此項，那么輸出的規(guī)那么中后項consequent只能由一個元素。選擇該選項可以讓CARMA算法周期性的剔除掉當前不太重要的規(guī)那么，加速建模。設定周期的大小，周期設定的越小，那么越省內(nèi)存，但是CARMA算法執(zhí)行時間常；反之，那么短。設定該選項可以加速CARMA算法的執(zhí)行。其大致思想是：一開場先給定一個較高的support值，將不顯著的規(guī)那么排除在外，然后再一次降低s

9、upport值。設定support值降低的速度選擇該項，那么CARMA模型會輸出不包含antecedent的規(guī)那么。購物籃分析執(zhí)行后建立的模型 會顯示在Canvas內(nèi)。共產(chǎn)生16條規(guī)那么每一行分別顯示了一組規(guī)那么，以及度量該規(guī)那么的一組目的，如：Lift、support等。點擊該圖標可以按指定規(guī)那么挑選出本人想要的規(guī)那么。生成對應規(guī)那么集的節(jié)點，包括三種節(jié)點：Select Node、Filtered Node以及Rule set節(jié)點。購物籃分析置信度Confidence最高的前三個規(guī)那么：Cannedveg & BeerFrozenmealFrozenmeal & BeerCannedvegC

10、annedveg & FrozenmealBeerFrozenmealConnedvegBeer促銷購物籃分析CARMA模型可以直接放在流中對數(shù)據(jù)進展打分預測scoring。在打分之前可以雙擊模型翻開Settings選項卡進行相關的參數(shù)設置。設定用于預測的規(guī)那么個數(shù)為選取規(guī)那么設定規(guī)范，從而可以根據(jù)該規(guī)那么選出最顯著的n條規(guī)那么，n由上一個選項設定。設定該項，那么允許用于預測的n條規(guī)那么可以有一樣的后項，即可以允許幾條規(guī)那么有一樣的預測結果。勾選該項，那么在運用規(guī)那么進展預測之前，系統(tǒng)會剔除掉不符合要求的數(shù)據(jù)行，不對其進展預測。購物籃分析對CARMA模型設置好了以后就可以將CARMA模型參與流

11、中對數(shù)據(jù)進展預測了，本文僅用一條規(guī)那么進展預測，結果存入表中見下頁。購物籃分析預測值預測置信度所運用規(guī)那么的編號購物籃分析用CARMA模型預測顧客的購買行為ConfectioneryFreshmeatDairyWine購物籃分析除了直接運用生成的CARMA模型進展預測外，還有一種預測方式即使用Rule Set。 運用Generate菜單生成想要的Rule Set節(jié)點，并將該節(jié)點放入流中進展預測。點擊確定以后可以生成一個規(guī)那么集節(jié)點，將該節(jié)點參與流中就可以進行預測了。案例研討之網(wǎng)絡日志分析數(shù)據(jù)預備運用數(shù)據(jù)為某網(wǎng)站五天的訪問日志；該數(shù)據(jù)集記錄數(shù)為173665，每行記錄對運用戶對效力器的一個頁面懇求

12、，記錄了用戶IP地址、懇求時間、懇求頁面URL、訪問協(xié)議、懇求形狀以及端口號等信息。本文為了簡化僅引入前三個變量，且頁面曾經(jīng)過分類，訪問已按事務劃分；該數(shù)據(jù)集為Transactional格式的數(shù)據(jù)。研討目的找出用戶的訪問方式，為網(wǎng)站構造上的調整和網(wǎng)站運營決策提供支持。網(wǎng)絡日志分析加載數(shù)據(jù)集網(wǎng)絡日志分析運用CARMA模塊來處置Transactional格式的網(wǎng)絡日志數(shù)據(jù)，并從中找出關聯(lián)規(guī)那么。雙擊翻開翻開Fields選項卡進展編輯。勾選該項，將CARMA模型處置的數(shù)據(jù)格式改為Transactional格式指定數(shù)據(jù)的獨一標識，標識一樣的記錄屬于同一個事務該欄用以指定買賣數(shù)據(jù)字段，本文中這里指定的是

13、當前懇求的頁面種類。網(wǎng)絡日志分析雙擊翻開Model選項卡進展編輯，設定Rules Support、Rule Confidence以及Rule Size等參數(shù)。網(wǎng)絡日志分析查看CARMA模型生成的規(guī)那么集網(wǎng)絡日志分析數(shù)據(jù)中定義的第一類頁面為文娛新聞版面，第二類是灌水版面。訪問文娛新聞版面訪問灌水版訪問灌水版面訪問文娛新聞版整合訪問量將灌水版和文娛新聞版整合為一個“我主文娛新版值得留意的問題CARMA模型運算速度不是最快的，但是它只需求對數(shù)據(jù)集一至兩遍的掃描就可以構造規(guī)那么集；CARMA模型及可以處置Tabular格式的數(shù)據(jù)，也可以處置Transactional格式的數(shù)據(jù)；CARMA模型中需求設定

14、的Rule Support的大小，而不是Support；CARMA模型不能處置數(shù)值型的數(shù)據(jù)。CARMA算法原理Carma算法也包括兩個部分尋覓頻繁項集在頻繁項集的根底上產(chǎn)生關聯(lián)規(guī)那么Carma尋覓頻繁項集的過程又分為Phase I和Phase IIPhase I：產(chǎn)生頻繁項集的超集，即產(chǎn)生潛在頻繁項集V在Phase I中可以隨時調整最小支持度Phase II：對潛在頻繁項集V進展刪減得到最終的頻繁項集CARMA算法原理初始V為空集，將事務按照序號排序,逐條讀入事務數(shù)據(jù)，并計算以下三個整數(shù)存儲在V的支持格(Support Lattice)中：Count(v)：v被插入V以后在事務數(shù)據(jù)庫中出現(xiàn)的次

15、數(shù)firstTrans(v)：v被插入V時所在事務的事務序號maxMissed(v)：v被插入V之前已讀入的事務個數(shù)例如：項集a,b在j時辰進入V,當j時辰時以上三個整數(shù)的情況CARMA算法原理根據(jù) Count(v)、maxMissed(v)定義了v項集的支持度的上限和下限：minSupport(v)是項集的實踐支持度maxSupport(v)用來判別項集v用來能否可以保管在V中CARMA算法原理Phase I中V產(chǎn)生的根本過程：初始V為空集(此時只可添加1-項集)，讀入第i條事務數(shù)據(jù)v，給出當前的最小支持度i,在計算過程中，算法自動調整最小支持度，即給每個事務以一個最小支持度，會構成一個最小

16、支持度序列t個事務(1,2 , 3,)假設v是1-項集:假設第一次出現(xiàn)，那么令Count(v)1, maxMissed(v) 0(1-項集的maxMissed(v)規(guī)定為0), firstTrans(v) i,且將v參與V(1-項集自動進入V)假設不是第一次出現(xiàn)，那么Count(v)Count(v)+1; CARMA算法原理假設v是k-項集(k=2)，那么先按前述方式處置包含的一切1-項集，且：假設第一次出現(xiàn)，判別該k-項集能否可以進入V，且令Count(v)1, firstTrans i,且假設不是第一次出現(xiàn)，那么項集各子集的Count(v)Count(v)+1; “修剪，默許每讀入500個

17、事務作一次修剪(從效率角度思索，其實可以讀入一條修剪一次)，即判別支持格中一切k-項集的maxSupport(v)，假設小于當前的最小支持度i ,那么剔除相應項集出VCARMA算法原理在Phase I階段，k-項集v進入V的主要原那么假設一個項集是頻繁項集，那么其一切子集必定也是頻繁項集；反之，如一個項集的某個子集不是頻繁項集，那么該項集必定也不是頻繁項集；Carma在決議k-項集v進入頻繁項集V時，應確保v的一切真子集已在當前事務之前進入V中，這是v進入V的條件之一要看一切子集，假設2項無所謂，假設3項那么需求檢驗其2項子集能否也在內(nèi)。項集v參與V的必要條件表述為：i為當前的事務序號，即v的

18、一切真子集w都是頻繁項集且已在當前事務之前進入V中CARMA算法原理在Phase I階段，k-項集v進入V的主要原那么判別v的真子集時應從包含工程較多的子集開場判別，假設包含工程較多的子集已在V中，那么包含工程較少的子集也一定在V中。因此，不用檢查一切子集，只需求檢驗那些包含工程最多的子集即可。為提高效率不用檢驗一切真子集，只需求檢查那些：其中：|w|、 |v|為所包含的工程數(shù)kCARMA算法原理計算maxSupport(v)的關鍵是計算maxMissed(v)maxMissed計算的根據(jù)一：其最大子集的頻繁程度在第i個時辰， v的具有最大firstTrans的真子集w(|w|=|v|-1)，

19、其支持度一定大于v的，即：此時i是相等的明顯然CARMA算法原理計算maxSupport(v)的關鍵是計算maxMissed(v) 根據(jù)二：用戶以往定義的最小支持度的情況在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)：例如：(0.3,0.7,0.9,0.5)CARMA算法原理計算maxSupport(v)的關鍵是計算maxMissed(v) 根據(jù)二：用戶以往定義的最小支持度的情況總之有：主要取決于以往的一系列最小支持度b(0,1,3)1,1CARMA算法原理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,cVa,b,c,a,b,b,c1=0.5a(0,1,2)0.66,0.66c(0,2,2)0.66,0.66a,