1、統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則-carma continuous association rule mining algorithm報(bào)告人：徐啟元報(bào)告人：徐啟元指導(dǎo)教師指導(dǎo)教師:謝邦昌謝邦昌日期：日期：2007年年11月月30日日統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組目錄目錄關(guān)聯(lián)規(guī)則基本概念關(guān)聯(lián)規(guī)則基本概念carma算法簡介算法簡介carma模塊的基本概念模塊的基本概念案例分析及案例分析及clementine操作步驟操作步驟購物籃分析購物籃分析-tabular類型數(shù)據(jù)類型數(shù)據(jù)網(wǎng)絡(luò)日志分析

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

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

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

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

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

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

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

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

10、智能應(yīng)用研究小組購物籃分析購物籃分析 加入加入type模塊對變量類型進(jìn)行設(shè)置。模塊對變量類型進(jìn)行設(shè)置。先點(diǎn)擊read values將各個(gè)變量實(shí)例化。統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組購物籃分析購物籃分析 將將carma 模塊加入模塊加入 流中，并雙流中，并雙 擊打開進(jìn)行擊打開進(jìn)行 參數(shù)設(shè)置。參數(shù)設(shè)置。點(diǎn)擊點(diǎn)擊統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組購物籃分析購物籃分析 對對model選項(xiàng)卡選項(xiàng)卡進(jìn)行設(shè)置。修改進(jìn)行設(shè)置。修改rule support、rule confidence以及以及rule size的的大

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

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

13、、support等。等。點(diǎn)擊該圖標(biāo)可點(diǎn)擊該圖標(biāo)可以按指定規(guī)則以按指定規(guī)則篩選出自己想篩選出自己想要的規(guī)則要的規(guī)則。生成對應(yīng)規(guī)則集的節(jié)點(diǎn)，包括三生成對應(yīng)規(guī)則集的節(jié)點(diǎn)，包括三種節(jié)點(diǎn)：種節(jié)點(diǎn)：select node、filtered node以及以及rule set節(jié)節(jié)點(diǎn)。點(diǎn)。統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組購物籃分析購物籃分析置信度（置信度（confidence）最高的前三個(gè)規(guī)則：）最高的前三個(gè)規(guī)則：cannedveg & beerfrozenmealfrozenmeal & beercannedvegcannedveg &

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

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

16、eatdairywine統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組購物籃分析購物籃分析除了直接使用生成的carma模型進(jìn)行預(yù)測外，還有一種預(yù)測方式即使用rule set。 使用generate菜單生成想要的rule set節(jié)點(diǎn)，并將該節(jié)點(diǎn)放入流中進(jìn)行預(yù)測。點(diǎn)擊確定以后可以生成點(diǎn)擊確定以后可以生成一個(gè)規(guī)則集節(jié)點(diǎn)，將該一個(gè)規(guī)則集節(jié)點(diǎn)，將該節(jié)點(diǎn)加入流中就可以進(jìn)節(jié)點(diǎn)加入流中就可以進(jìn)行預(yù)測了。行預(yù)測了。統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組案例研究之網(wǎng)絡(luò)日志分析案例研究之網(wǎng)絡(luò)日志分析 數(shù)據(jù)準(zhǔn)備數(shù)據(jù)準(zhǔn)備 使用數(shù)據(jù)為某網(wǎng)站五天的

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

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

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

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

21、ort； carma模型不能處理數(shù)值型的數(shù)據(jù)。模型不能處理數(shù)值型的數(shù)據(jù)。統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組carma算法原理算法原理 carma算法也包括兩個(gè)部分算法也包括兩個(gè)部分 尋找頻繁項(xiàng)集 在頻繁項(xiàng)集的基礎(chǔ)上產(chǎn)生關(guān)聯(lián)規(guī)則 carma尋找頻繁項(xiàng)集的過程又分為尋找頻繁項(xiàng)集的過程又分為phase i和和phase ii phase i：產(chǎn)生頻繁項(xiàng)集的超集，即產(chǎn)生潛在頻繁項(xiàng)集v在phase i中可以隨時(shí)調(diào)整最小支持度 phase ii：對潛在頻繁項(xiàng)集v進(jìn)行刪減得到最終的頻繁項(xiàng)集統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研

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

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

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

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

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

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

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

29、(v)的關(guān)鍵是計(jì)算maxmissed(v) 依據(jù)二：用戶以往定義的最小支持度的情況在i+1時(shí)刻，以往最小支持度序列表示為i(1,2 , 3, i)carma中定義了關(guān)于i的天花板(ceiling of )序列，記為天花板的含義是：當(dāng)j i時(shí)(j=1,2,.i-1)：當(dāng)j i時(shí)(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) 統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研

30、究小組carma算法原理算法原理 計(jì)算maxsupport(v)的關(guān)鍵是計(jì)算maxmissed(v) 依據(jù)二：用戶以往定義的最小支持度的情況 總之有：主要取決于以往的一系列最小支持度11max( )min (1)()| 1,max( )( ) 1iimissed viavgvmissed wcount w 111| | 1max( )()1iiivsupportvavgi 11max( )(1)()| | 1iimissed viavgv 統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組統(tǒng)計(jì)分析、數(shù)據(jù)挖掘與商業(yè)智能應(yīng)用研究小組b(0,1,3)1,1carma算法原理算法原理111(0.3,0,0)0.3avg 222(0.9,0.9,0)0.9avg phase i舉例 事務(wù)序列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