關聯(lián)規(guī)則--CARMAppt課件

1、統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組關聯(lián)規(guī)則關聯(lián)規(guī)則-CARMA Continuous Association Rule Mining Algorithm報告人：徐啟元報告人：徐啟元指導教師指導教師:謝邦昌謝邦昌日期：日期：2019年年11月月30日日統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組目錄目錄關聯(lián)規(guī)則基本概念關聯(lián)規(guī)則基本概念CARMA算法簡介算法簡介CARMA模塊的基本概念模塊的基本概念案例分析及案例分析及Clementine操作步驟操作步驟購物籃分析購物籃分析-Tabular類型數(shù)據(jù)類型數(shù)據(jù)網(wǎng)絡日志分析

2、網(wǎng)絡日志分析-Transactional類型數(shù)據(jù)類型數(shù)據(jù)值得注意的問題值得注意的問題CARMA算法原理參考）算法原理參考）統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組關聯(lián)規(guī)則算法簡介關聯(lián)規(guī)則算法簡介 關聯(lián)分析的目的是尋找數(shù)據(jù)項間的相關關聯(lián)分析的目的是尋找數(shù)據(jù)項間的相關性常用技術：性常用技術： 關聯(lián)規(guī)則：即尋找在同一個事件中出現(xiàn)的關聯(lián)規(guī)則：即尋找在同一個事件中出現(xiàn)的不同項目的相關性不同項目的相關性 例如：找出顧客經(jīng)常同例如：找出顧客經(jīng)常同 時購買哪些商品。網(wǎng)民時購買哪些商品。網(wǎng)民 瀏覽的網(wǎng)頁之間有沒有瀏覽的網(wǎng)頁之間有沒有 什么關聯(lián)性。什么關聯(lián)性。統(tǒng)計分析、數(shù)據(jù)

3、挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法簡介算法簡介CARMA是一種比較新的關聯(lián)規(guī)則算法，它是2019年由Berkeley大學的Christian Hidber教授提出來的。1234能夠處理在線連續(xù)交易流數(shù)據(jù)僅需一次，最多兩次對數(shù)據(jù)的掃描就可以構造出結果集允許在算法執(zhí)行過程中按需要重新設置支持度占用內存少CARMAOn-line統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA模塊中的基本概念模塊中的基本概念 Antecedent&Consequent 它們指的是規(guī)則的前項和后項。 Instances 對于每一條規(guī)

4、則，它的 Instances值指的是所有 記錄中包含該規(guī)則的 antecedent的記錄的數(shù)量。面包面包牛奶牛奶前項前項Antecedent后項后項ConsequentIDP1P2P3P41breadcheesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbread總共4條購買數(shù)據(jù)，其中有三條都包含bread，那么該條規(guī)則的instances等于3統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA模塊中的基本概念模塊中的基本概念 Support

5、它的定義和instances很接 近，不同的是support描述 的不是數(shù)量，而是比例。 Rule Support 它在Support定義的基礎 上更進一步，它指的是 所有記錄中既包含某規(guī) 則的antecedent，又包含 consequent的記錄所占 的比例。IDP1P2P3P41breadcheesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbreadSupport=3/4100%=75%四條記錄中只有一條既包含了前項bread，又包含了后向milk，所以Rule Suppor

6、t=1/4100%=25%統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA模塊中的基本概念模塊中的基本概念 Confidence Confidence = Rule Support / Support 該指標反映的是規(guī)則預測的 準確程度。 Deployability Deployability = Support Rule Support 它的作用與confidence類似。IDP1P2P3P41breadcheesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkf

7、rozenmealbread根據(jù)規(guī)則“面包=牛奶”，那么購買了面包的第一、二及四行都會被預測購買了牛奶，但事實上這三個預測只有第二個是正確的，所以confidence=1/3100%=33.3%統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA模塊中的基本概念模塊中的基本概念 Lift 在已知某規(guī)則的 consequent發(fā)生 的先驗概率的情況 下，某規(guī)則的Lift 被定義為Confidence 和該先驗概率的比 率值。IDP1P2P3P41breadcheesebutterwater2watermilkbreadnoodle3milknoodlemea

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

9、數(shù)據(jù)格式數(shù)據(jù)格式 TransactionalTransactional數(shù)據(jù)數(shù)據(jù)格式格式 統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組案例研究之購物籃分析案例研究之購物籃分析 數(shù)據(jù)準備數(shù)據(jù)準備 使用數(shù)據(jù)為使用數(shù)據(jù)為clementineclementine自帶的自帶的Baskets1nBaskets1n數(shù)據(jù)數(shù)據(jù)集；集； 該數(shù)據(jù)集樣本量為該數(shù)據(jù)集樣本量為10001000，每筆交易包含了顧客，每筆交易包含了顧客的卡號、性別、年齡、收入、付款方式等一系的卡號、性別、年齡、收入、付款方式等一系列個人信息，以及其購買的各種食品清單；列個人信息，以及其購買的各種食品清單；

10、該數(shù)據(jù)集為該數(shù)據(jù)集為TabularTabular格式的數(shù)據(jù)。格式的數(shù)據(jù)。 研究目的研究目的 為超市貨架的擺放提供科學的依據(jù)；為超市貨架的擺放提供科學的依據(jù)； 為超市商品促銷決策提供支持。為超市商品促銷決策提供支持。統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組案例研究案例研究統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組購物籃分析購物籃分析 加入加入type模塊對變量類型進行設置。模塊對變量類型進行設置。先點擊Read Values將各個變量實例化。統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小

11、組購物籃分析購物籃分析 將將CARMA 模塊加入模塊加入 流中，并雙流中，并雙 擊打開進行擊打開進行 參數(shù)設置。參數(shù)設置。點擊點擊統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組購物籃分析購物籃分析 對對Model選項卡選項卡進行設置。修改進行設置。修改Rule Support、Rule Confidence以及以及Rule Size的的大小。大小。點擊此處，打開Model選項卡編輯對這三個選項進行編輯以控制輸出的規(guī)則的數(shù)目統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組購物籃分析購物籃分析 對對Expert選項選項卡進行設置，卡

12、進行設置，如果對如果對CARMA算法比較了解算法比較了解的用戶，可以的用戶，可以對該選項卡進對該選項卡進行設定以獲得行設定以獲得使使CARMA模塊模塊具有更好的性具有更好的性能。能。選擇此項，則輸出的規(guī)則中后項consequent只能由一個元素。選擇該選項可以讓CARMA算法周期性的剔除掉當前不太重要的規(guī)則，加速建模。設定周期的大小，周期設定的越小，則越省內存，但是CARMA算法執(zhí)行時間常；反之，則短。設定該選項可以加速CARMA算法的執(zhí)行。其大致思想是：一開始先給定一個較高的support值，將不顯著的規(guī)則排除在外，然后再一次降低support值。設定support值降低的速度選擇該項，則C

13、ARMA模型會輸出不包含antecedent的規(guī)則。統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組購物籃分析購物籃分析執(zhí)行后建執(zhí)行后建立的模型立的模型 會會顯示在顯示在Canvas內。內。共產(chǎn)生共產(chǎn)生16條規(guī)則條規(guī)則每一行分別顯示了一組每一行分別顯示了一組規(guī)則，以及度量該規(guī)則規(guī)則，以及度量該規(guī)則的一組指標，如：的一組指標，如：Lift、support等。等。點擊該圖標可點擊該圖標可以按指定規(guī)則以按指定規(guī)則篩選出自己想篩選出自己想要的規(guī)則。要的規(guī)則。生成對應規(guī)則集的節(jié)點，包括三生成對應規(guī)則集的節(jié)點，包括三種節(jié)點：種節(jié)點：Select Node、Filtered

14、Node以及以及Rule set節(jié)節(jié)點。點。統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組購物籃分析購物籃分析置信度置信度Confidence最高的前三個規(guī)則：最高的前三個規(guī)則：Cannedveg & BeerFrozenmealFrozenmeal & BeerCannedvegCannedveg & FrozenmealBeer促銷統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組購物籃分析購物籃分析CARMA模型可以模型可以直接放在流中對直接放在流中對數(shù)據(jù)進行打分預數(shù)據(jù)進行打分預測測scoring）。）。在打分之前可以在打分

15、之前可以雙擊模型打開雙擊模型打開Settings選項卡進選項卡進行相關的參數(shù)設行相關的參數(shù)設置。置。設定用于預測的規(guī)則個數(shù)為選取規(guī)則設定標準，從而可以根據(jù)該規(guī)則選出最顯著的n條規(guī)則，n由上一個選項設定。設定該項，則允許用于預測的n條規(guī)則可以有相同的后項，即可以允許幾條規(guī)則有相同的預測結果。勾選該項，則在應用規(guī)則進行預測之前，系統(tǒng)會剔除掉不符合要求的數(shù)據(jù)行，不對其進行預測。統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組購物籃分析購物籃分析對CARMA模型設置好了以后就可以將CARMA模型加入流中對數(shù)據(jù)進行預測了，本文僅用一條規(guī)則進行預測，結果存入表中見下頁）。統(tǒng)

16、計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組購物籃分析購物籃分析預測值預測值預測置信度預測置信度所使用規(guī)所使用規(guī)則的編號則的編號統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組購物籃分析購物籃分析用CARMA模型預測顧客的購買行為ConfectioneryFreshmeatDairyWine統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組購物籃分析購物籃分析除了直接使用生成的CARMA模型進行預測外，還有一種預測方式即使用Rule Set。 使用Generate菜單生成想要的Rule Set節(jié)點，

17、并將該節(jié)點放入流中進行預測。點擊確定以后可以生成點擊確定以后可以生成一個規(guī)則集節(jié)點，將該一個規(guī)則集節(jié)點，將該節(jié)點加入流中就可以進節(jié)點加入流中就可以進行預測了。行預測了。統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組案例研究之網(wǎng)絡日志分析案例研究之網(wǎng)絡日志分析 數(shù)據(jù)準備數(shù)據(jù)準備 使用數(shù)據(jù)為某網(wǎng)站五天的訪問日志；使用數(shù)據(jù)為某網(wǎng)站五天的訪問日志； 該數(shù)據(jù)集記錄數(shù)為該數(shù)據(jù)集記錄數(shù)為173665173665，每行記錄對應用戶，每行記錄對應用戶對服務器的一個頁面請求，記錄了用戶對服務器的一個頁面請求，記錄了用戶IPIP地址、地址、請求時間、請求頁面請求時間、請求頁面URL

18、URL、訪問協(xié)議、請求狀、訪問協(xié)議、請求狀態(tài)以及端口號等信息。本文為了簡化僅引入前態(tài)以及端口號等信息。本文為了簡化僅引入前三個變量，且頁面已經(jīng)過分類，訪問已按事務三個變量，且頁面已經(jīng)過分類，訪問已按事務劃分；劃分； 該數(shù)據(jù)集為該數(shù)據(jù)集為TransactionalTransactional格式的數(shù)據(jù)。格式的數(shù)據(jù)。 研究目的研究目的 找出用戶的訪問模式，為網(wǎng)站結構上的調整和找出用戶的訪問模式，為網(wǎng)站結構上的調整和網(wǎng)站經(jīng)營決策提供支持。網(wǎng)站經(jīng)營決策提供支持。統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組網(wǎng)絡日志分析網(wǎng)絡日志分析加載數(shù)據(jù)集加載數(shù)據(jù)集統(tǒng)計分析、數(shù)據(jù)挖掘與

19、商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組網(wǎng)絡日志分析網(wǎng)絡日志分析 使用使用CARMA模塊來處理模塊來處理Transactional格式的網(wǎng)絡日格式的網(wǎng)絡日志數(shù)據(jù)，并從志數(shù)據(jù)，并從中找出關聯(lián)規(guī)中找出關聯(lián)規(guī)則。則。 雙擊打開打開雙擊打開打開Fields選項卡進選項卡進行編輯。行編輯。勾選該項，將CARMA模型處理的數(shù)據(jù)格式改為Transactional格式指定數(shù)據(jù)的唯一標識，標識相同的記錄屬于同一個事務該欄用以指定交易數(shù)據(jù)字段，本文中這里指定的是當前請求的頁面種類。統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組網(wǎng)絡日志分析網(wǎng)絡日志分析雙擊打開雙

20、擊打開Model選項卡進行編選項卡進行編輯，設定輯，設定Rules Support、Rule Confidence以及以及Rule Size等參等參數(shù)。數(shù)。統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組網(wǎng)絡日志分析網(wǎng)絡日志分析 查看查看CARMA模型生成的規(guī)則集模型生成的規(guī)則集統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組網(wǎng)絡日志分析網(wǎng)絡日志分析數(shù)據(jù)中定義的第一類頁面為娛樂新聞版面，第二數(shù)據(jù)中定義的第一類頁面為娛樂新聞版面，第二類是灌水版面。類是灌水版面。訪問娛樂訪問娛樂新新聞聞版面版面訪問訪問灌水版灌水版訪問訪問灌水版面灌水

21、版面訪問娛樂訪問娛樂新新聞聞版版整合整合訪問訪問量量將灌水版和娛將灌水版和娛樂新聞版整合樂新聞版整合為一個為一個“我主我主娛樂新版娛樂新版統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組值得注意的問題值得注意的問題 CARMA模型運算速度不是最快的，但模型運算速度不是最快的，但是它只需要對數(shù)據(jù)集一至兩遍的掃描就是它只需要對數(shù)據(jù)集一至兩遍的掃描就可以構造規(guī)則集；可以構造規(guī)則集； CARMA模型及可以處理模型及可以處理Tabular格式的格式的數(shù)據(jù)，也可以處理數(shù)據(jù)，也可以處理Transactional格式的格式的數(shù)據(jù)；數(shù)據(jù)； CARMA模型中需要設定的模型中需要設定

22、的Rule Support的大小，而不是的大小，而不是Support； CARMA模型不能處理數(shù)值型的數(shù)據(jù)。模型不能處理數(shù)值型的數(shù)據(jù)。統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法原理算法原理 Carma算法也包括兩個部分算法也包括兩個部分 尋找頻繁項集尋找頻繁項集 在頻繁項集的基礎上產(chǎn)生關聯(lián)規(guī)則在頻繁項集的基礎上產(chǎn)生關聯(lián)規(guī)則 Carma尋找頻繁項集的過程又分為尋找頻繁項集的過程又分為Phase I和和Phase II Phase I：產(chǎn)生頻繁項集的超集，即產(chǎn)生：產(chǎn)生頻繁項集的超集，即產(chǎn)生潛在頻繁項集潛在頻繁項集V在在Phase I中可以隨時調中

23、可以隨時調整最小支持度整最小支持度 Phase II：對潛在頻繁項集：對潛在頻繁項集V進行刪減得進行刪減得到最終的頻繁項集到最終的頻繁項集統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法原理算法原理 初始V為空集，將事務按照序號排序,逐條讀入事務數(shù)據(jù)，并計算以下三個整數(shù)存儲在V的支持格(Support Lattice)中： Count(v)：v被插入V以后在事務數(shù)據(jù)庫中出現(xiàn)的次數(shù) firstTrans(v)：v被插入V時所在事務的事務序號 maxMissed(v)：v被插入V之前已讀入的事務個數(shù)例如：項集a,b在j時刻進入V,當j時刻時以上三個整數(shù)

24、的情況統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法原理算法原理 根據(jù) Count(v)、maxMissed(v)定義了v項集的支持度的上限和下限： minSupport(v)是項集的實際支持度 maxSupport(v)用來判斷項集v用來是否可以保留在V中max( )(max( )( )/min( )( )/iSupport vMissed vcount viSupport vcount vi統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法原理算法原理 Phase I中V產(chǎn)生的基本過程：初始V為空集

25、(此時只可添加1-項集)， 讀入第i條事務數(shù)據(jù)v，給出當前的最小支持度i, 在計算過程中，算法自動調整最小支持度，即給每個事務以一個最小支持度，會形成一個最小支持度序列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; 統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法原理算法原理 如果v是k-項集(k=2

26、)，則先按前述方式處理包含的所有1-項集，且： 如果第一次出現(xiàn)，判斷該k-項集是否可以進入V，且令Count(v)1, firstTrans i,且 如果不是第一次出現(xiàn)，則項集各子集的Count(v)Count(v)+1; “修剪”，默認每讀入500個事務作一次修剪(從效率角度考慮，其實可以讀入一條修剪一次)，即判斷支持格中所有k-項集的maxSupport(v)，如果小于當前的最小支持度i ,則剔除相應項集出V統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法原理算法原理 在Phase I階段，k-項集v進入V的主要原則 如果一個項集是頻繁項集，則

27、其所有子集必定也是頻繁項集；反之，如一個項集的某個子集不是頻繁項集，則該項集必定也不是頻繁項集；Carma在決定k-項集v進入頻繁項集V時，應確保v的所有真子集已在當前事務之前進入V中，這是v進入V的條件之一要看所有子集，若2項無所謂，若3項則需要檢驗其2項子集是否也在內）。 項集v加入V的必要條件表述為：i為當前的事務序號，即v的所有真子集w都是頻繁項集且已在當前事務之前進入V中: ( ) max( )iwv wV and firstTrans wi andSupport wmax( )(max( )( )/Support wMissed wcount wi其中：統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能

28、應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法原理算法原理 在Phase I階段，k-項集v進入V的主要原則 判斷v的真子集時應從包含項目較多的子集開始判斷，如果包含項目較多的子集已在V中，則包含項目較少的子集也一定在V中。因此，不必檢查所有子集，只需要檢驗那些包含項目最多的子集即可。 為提高效率不必檢驗所有真子集，只需要檢查那些：:| | 1 ( ) max( )iwvwvand wV and firstTrans wi andSupport w其中：|w|、 |v|為所包含的項目數(shù)kmax( )(max( )( )/Support wMissed wcount wi其中

29、：統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法原理算法原理計算maxSupport(v)的關鍵是計算maxMissed(v)maxMissed計算的依據(jù)一：其最大子集的頻繁程度在第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 vma

30、x( )max( )( ) 1Missed vMissed wCount w統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組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)：i 123(,.,0,0,.)ii (,.)iiiii 例如：(0.3,0.7,0.9,0.

31、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) 統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法原理算法原理 計算maxSupport(v)的關鍵是計算maxMissed(v) 依據(jù)二：用戶以往定義的最小支持度的情況 總之有：主要取決于以往的一系列最小支持度11max( )min (1)()| | 1,max( )( ) 1iiMissed viavgvMissed wcount w 111| | 1max( )()1iiivSupportvavgi 11max(

32、)(1)()| | 1iiMissed viavgv 統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組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,cVa,b,c,a,b,b,c1=0.5a(0,1,2)0.66,0.66c(0,2,2)0.66,0.66a,b(1,2,1)0.33,0.66b,c(1,3,1)0.33,0.66(maxMissed,firstTrans,count)minSupport,maxSupport統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組統(tǒng)計分析、數(shù)據(jù)挖掘與商業(yè)智能應用研究小組CARMA算法原理算法原理用戶自行給出各個 是不現(xiàn)實的，用戶只需要給出初始的 ，Carma便可以自行調整，通過固定 、不斷減少maxSupport來