我國社會(huì)經(jīng)濟(jì)發(fā)展綜合評價(jià)指數(shù)

關(guān)聯(lián)規(guī)則--CARMA

ContinuousAssociationRuleMiningAlgorithm報(bào)告人：徐啟元指導(dǎo)教師:謝邦昌日期：2007年11月30日目錄關(guān)聯(lián)規(guī)則基本概念CARMA算法簡介CARMA模塊的基本概念案例分析及Clementine操作步驟購物籃分析----Tabular類型數(shù)據(jù)網(wǎng)絡(luò)日志分析----Transactional類型數(shù)據(jù)值得注意的問題CARMA算法原理（參考）關(guān)聯(lián)規(guī)則算法簡介關(guān)聯(lián)分析的目的是尋找數(shù)據(jù)項(xiàng)間的相關(guān)性．常用技術(shù)：關(guān)聯(lián)規(guī)則：即尋找在同一個(gè)事件中出現(xiàn)的不同項(xiàng)目的相關(guān)性

例如：找出顧客經(jīng)常同時(shí)購買哪些商品。網(wǎng)民瀏覽的網(wǎng)頁之間有沒有什么關(guān)聯(lián)性。CARMA算法簡介CARMA是一種比較新的關(guān)聯(lián)規(guī)則算法，它是1999年由Berkeley大學(xué)的ChristianHidber教授提出來的。1234能夠處理在線連續(xù)交易流數(shù)據(jù)僅需一次，最多兩次對數(shù)據(jù)的掃描就可以構(gòu)造出結(jié)果集允許在算法執(zhí)行過程中按需要重新設(shè)置支持度占用內(nèi)存少CARMAOn-lineCARMA模塊中的基本概念A(yù)ntecedent&Consequent它們指的是規(guī)則的前項(xiàng)和后項(xiàng)。Instances對于每一條規(guī)則，它的Instances值指的是所有記錄中包含該規(guī)則的antecedent的記錄的數(shù)量。面包牛奶前項(xiàng)Antecedent后項(xiàng)ConsequentIDP1P2P3P41breadcheesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbread總共4條購買數(shù)據(jù)，其中有三條都包含bread，那么該條規(guī)則的instances等于3CARMA模塊中的基本概念Support

它的定義和instances很接近，不同的是support描述的不是數(shù)量，而是比例。RuleSupport

它在Support定義的基礎(chǔ)上更進(jìn)一步，它指的是所有記錄中既包含某規(guī)則的antecedent，又包含consequent的記錄所占的比例。IDP1P2P3P41breadcheesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbreadSupport=3/4×100%=75%四條記錄中只有一條既包含了前項(xiàng)bread，又包含了后向milk，所以RuleSupport=1/4×100%=25%CARMA模塊中的基本概念Confidence

Confidence=RuleSupport/Support該指標(biāo)反映的是規(guī)則預(yù)測的準(zhǔn)確程度。Deployability

Deployability=Support–RuleSupport

它的作用與confidence類似。IDP1P2P3P41breadcheesebutterwater2watermilkbreadnoodle3orangenoodlemeatbeer4fishsoftdrinkfrozenmealbread根據(jù)規(guī)則“面包=》牛奶”，那么購買了面包的第一、二及四行都會(huì)被預(yù)測購買了牛奶，但事實(shí)上這三個(gè)預(yù)測只有第二個(gè)是正確的，所以confidence=1/3×100%=33.3%CARMA模塊中的基本概念Lift在已知某規(guī)則的consequent發(fā)生的先驗(yàn)概率的情況下，某規(guī)則的Lift被定義為Confidence和該先驗(yàn)概率的比率值。IDP1P2P3P41breadcheesebutterwater2watermilkbreadnoodle3milknoodlemeatbeer4fishsoftdrinkfrozenmealbread那么對于一條記錄，那么不采用任何規(guī)則進(jìn)行預(yù)測，隨便猜測該顧客是否該買牛奶的正確率是50%已知有50%的人購買了牛奶：）如果采用“面包=》牛奶”的規(guī)則進(jìn)行預(yù)測的話，正確率，即confidence=33.3%比隨便猜測的正確率還低。那么此時(shí)的Lift值為多少呢？？？Lift=33.3%/50%=66.6%<1所以只有那些Lift>1的規(guī)則才是有意義的規(guī)則源數(shù)據(jù)格式CARMA模塊能夠處理一下兩種格式的數(shù)據(jù)Tabular數(shù)據(jù)格式Transactional數(shù)據(jù)格式

案例研究之購物籃分析數(shù)據(jù)準(zhǔn)備使用數(shù)據(jù)為clementine自帶的Baskets1n數(shù)據(jù)集；該數(shù)據(jù)集樣本量為1000，每筆交易包含了顧客的卡號、性別、年齡、收入、付款方式等一系列個(gè)人信息，以及其購買的各種食品清單；該數(shù)據(jù)集為Tabular格式的數(shù)據(jù)。研究目的為超市貨架的擺放提供科學(xué)的依據(jù)；為超市商品促銷決策提供支持。案例例研研究究購物物籃籃分分析析加入入type模模塊塊對對變變量量類類型型進(jìn)進(jìn)行行設(shè)設(shè)置置。。先點(diǎn)擊ReadValues將各個(gè)變量實(shí)例化。購物物籃籃分分析析將CARMA模塊塊加加入入流中中，，并并雙雙擊打打開開進(jìn)進(jìn)行行參數(shù)數(shù)設(shè)設(shè)置置。。點(diǎn)擊擊點(diǎn)擊擊購物物籃籃分分析析對Model選選項(xiàng)項(xiàng)卡卡進(jìn)進(jìn)行行設(shè)設(shè)置置。。修修改改RuleSupport、、RuleConfidence以以及及RuleSize的的大大小小。。點(diǎn)擊擊此此處處，，打打開開Model選選項(xiàng)項(xiàng)卡卡編編輯輯對這這三三個(gè)個(gè)選選項(xiàng)項(xiàng)進(jìn)進(jìn)行行編編輯輯以以控控制制輸輸出出的的規(guī)規(guī)則則的的數(shù)數(shù)目目購物物籃籃分分析析對Expert選選項(xiàng)項(xiàng)卡卡進(jìn)進(jìn)行行設(shè)設(shè)置置，，如如果果對對CARMA算算法法比比較較了了解解的的用用戶戶，，可可以以對對該該選選項(xiàng)項(xiàng)卡卡進(jìn)進(jìn)行行設(shè)設(shè)定定以以獲獲得得使使CARMA模模塊塊具具有有更更好好的的性性能能。。選擇擇此此項(xiàng)項(xiàng)，，則則輸輸出出的的規(guī)規(guī)則則中中后后項(xiàng)項(xiàng)（（consequent））只只能能由由一一個(gè)個(gè)元元素素。。選擇擇該該選選項(xiàng)項(xiàng)可可以以讓讓CARMA算算法法周周期期性性的的剔剔除除掉掉當(dāng)當(dāng)前前不不太太重重要要的的規(guī)規(guī)則則，，加加速速建建模模。。設(shè)定定周周期期的的大大小小，，周周期期設(shè)設(shè)定定的的越越小小，，則則越越省省內(nèi)內(nèi)存存，，但但是是CARMA算算法法執(zhí)執(zhí)行行時(shí)時(shí)間間常常；；反反之之，，則則短短。。設(shè)定定該該選選項(xiàng)項(xiàng)可可以以加加速速CARMA算算法法的的執(zhí)執(zhí)行行。。其其大大致致思思想想是是：：一一開開始始先先給給定定一一個(gè)個(gè)較較高高的的support值值，，將將不不顯顯著著的的規(guī)規(guī)則則排排除除在在外外，，然然后后再再一一次次降降低低support值值。。設(shè)定定support值值降降低低的的速速度度選擇擇該該項(xiàng)項(xiàng)，，則則CARMA模模型型會(huì)會(huì)輸輸出出不不包包含含antecedent的的規(guī)規(guī)則則。。購物物籃籃分分析析執(zhí)行行后后建建立的的模模型型會(huì)顯示示在在Canvas內(nèi)。。共產(chǎn)產(chǎn)生生16條條規(guī)規(guī)則則每一一行行分分別別顯顯示示了了一一組組規(guī)規(guī)則則，，以以及及度度量量該該規(guī)規(guī)則則的的一一組組指指標(biāo)標(biāo)，，如如：：Lift、、support等等。。點(diǎn)擊擊該該圖圖標(biāo)標(biāo)可可以以按按指指定定規(guī)規(guī)則則篩篩選選出出自自己己想想要要的的規(guī)規(guī)則則。生成成對對應(yīng)應(yīng)規(guī)規(guī)則則集集的的節(jié)節(jié)點(diǎn)點(diǎn)，，包包括括三三種種節(jié)節(jié)點(diǎn)點(diǎn)：：SelectNode、、FilteredNode以以及及Ruleset節(jié)節(jié)點(diǎn)點(diǎn)。。購物物籃籃分分析析置信信度度（（Confidence））最最高高的的前前三三個(gè)個(gè)規(guī)規(guī)則則：：Cannedveg&BeerFrozenmealFrozenmeal&BeerCannedvegCannedveg&FrozenmealBeerFrozenmealConnedvegBeer促銷銷購物物籃籃分分析析CARMA模模型型可可以以直接接放放在在流流中中對對數(shù)據(jù)據(jù)進(jìn)進(jìn)行行打打分分預(yù)預(yù)測（（scoring））。。在打打分分之之前前可可以以雙擊擊模模型型打打開開Settings選選項(xiàng)項(xiàng)卡卡進(jìn)進(jìn)行相相關(guān)關(guān)的的參參數(shù)數(shù)設(shè)設(shè)置。。設(shè)定定用用于于預(yù)預(yù)測測的的規(guī)規(guī)則則個(gè)個(gè)數(shù)數(shù)為選選取取規(guī)規(guī)則則設(shè)設(shè)定定標(biāo)標(biāo)準(zhǔn)準(zhǔn)，，從從而而可可以以根根據(jù)據(jù)該該規(guī)規(guī)則則選選出出最最顯顯著著的的n條條規(guī)規(guī)則則，，n由由上上一一個(gè)個(gè)選選項(xiàng)項(xiàng)設(shè)設(shè)定定。。設(shè)定定該該項(xiàng)項(xiàng)，，則則允允許許用用于于預(yù)預(yù)測測的的n條條規(guī)規(guī)則則可可以以有有相相同同的的后后項(xiàng)項(xiàng)，，即即可可以以允允許許幾幾條條規(guī)規(guī)則則有有相相同同的的預(yù)預(yù)測測結(jié)結(jié)果果。。勾選選該該項(xiàng)項(xiàng)，，則則在在應(yīng)應(yīng)用用規(guī)規(guī)則則進(jìn)進(jìn)行行預(yù)預(yù)測測之之前前，，系系統(tǒng)統(tǒng)會(huì)會(huì)剔剔除除掉掉不不符符合合要要求求的的數(shù)數(shù)據(jù)據(jù)行行，，不不對對其其進(jìn)進(jìn)行行預(yù)預(yù)測測。。購物物籃籃分分析析對CARMA模模型型設(shè)設(shè)置置好好了了以以后后就就可可以以將將CARMA模型型加加入入流流中中對對數(shù)數(shù)據(jù)據(jù)進(jìn)進(jìn)行行預(yù)預(yù)測測了了，，本本文文僅僅用用一一條規(guī)規(guī)則則進(jìn)進(jìn)行行預(yù)預(yù)測測，，結(jié)結(jié)果果存存入入表表中中（（見見下下頁頁））。。購物物籃籃分分析析預(yù)測測值值預(yù)測測置置信信度度所使使用用規(guī)規(guī)則則的的編編號號購物物籃籃分分析析用CARMA模模型型預(yù)預(yù)測測顧顧客客的的購購買買行行為為ConfectioneryFreshmeatDairy？Wine購物物籃籃分分析析除了了直直接接使使用用生生成成的的CARMA模模型型進(jìn)進(jìn)行行預(yù)預(yù)測測外，，還還有有一一種種預(yù)預(yù)測測方方式式即即使使用用RuleSet。。使用用Generate菜菜單單生生成成想想要要的的RuleSet節(jié)節(jié)點(diǎn)點(diǎn)，，并并將將該該節(jié)節(jié)點(diǎn)點(diǎn)放放入入流流中中進(jìn)進(jìn)行行預(yù)預(yù)測測。。點(diǎn)擊擊確確定定以以后后可可以以生生成成一一個(gè)個(gè)規(guī)規(guī)則則集集節(jié)節(jié)點(diǎn)點(diǎn)，，將將該該節(jié)節(jié)點(diǎn)點(diǎn)加加入入流流中中就就可可以以進(jìn)進(jìn)行預(yù)預(yù)測測了了。。案例例研研究究之之網(wǎng)網(wǎng)絡(luò)絡(luò)日日志志分分析析數(shù)據(jù)據(jù)準(zhǔn)準(zhǔn)備備使用用數(shù)數(shù)據(jù)據(jù)為為某某網(wǎng)網(wǎng)站站五五天天的的訪訪問問日日志志；；該數(shù)數(shù)據(jù)據(jù)集集記記錄錄數(shù)數(shù)為為173665，，每每行行記記錄錄對對應(yīng)應(yīng)用用戶戶對對服服務(wù)務(wù)器器的的一一個(gè)個(gè)頁頁面面請請求求，，記記錄錄了了用用戶戶IP地地址址、、請請求求時(shí)時(shí)間間、、請請求求頁頁面面URL、、訪訪問問協(xié)協(xié)議議、、請請求求狀狀態(tài)態(tài)以以及及端端口口號號等等信信息息。。本本文文為為了了簡簡化化僅僅引引入入前前三三個(gè)個(gè)變變量量，，且且頁頁面面已已經(jīng)經(jīng)過過分分類類，，訪訪問問已已按按事事務(wù)務(wù)劃劃分分；；該數(shù)據(jù)集集為Transactional格式的數(shù)據(jù)。。研究目的的找出用戶戶的訪問問模式，，為網(wǎng)站站結(jié)構(gòu)上上的調(diào)整整和網(wǎng)站站經(jīng)營決決策提供供支持。。網(wǎng)絡(luò)日志志分析加載數(shù)據(jù)據(jù)集網(wǎng)絡(luò)日志志分析使用CARMA模塊來來處理Transactional格式的的網(wǎng)絡(luò)日日志數(shù)據(jù)據(jù)，并從從中找出出關(guān)聯(lián)規(guī)規(guī)則。雙擊打開開打開Fields選選項(xiàng)卡進(jìn)進(jìn)行編輯輯。勾選該項(xiàng)項(xiàng)，將CARMA模型型處理的的數(shù)據(jù)格格式改為為Transactional格式式指定數(shù)據(jù)據(jù)的唯一一標(biāo)識(shí)，，標(biāo)識(shí)相相同的記記錄屬于于同一個(gè)個(gè)事務(wù)該欄用以以指定交交易數(shù)據(jù)據(jù)字段，，本文中中這里指指定的是是當(dāng)前請請求的頁頁面種類類。網(wǎng)絡(luò)日志志分析雙擊打開開Model選項(xiàng)卡進(jìn)進(jìn)行編輯，設(shè)定定RulesSupport、RuleConfidence以及RuleSize等等參數(shù)。網(wǎng)絡(luò)日志志分析查看CARMA模型生生成的規(guī)規(guī)則集網(wǎng)絡(luò)日志志分析數(shù)據(jù)中定定義的第第一類頁頁面為娛娛樂新聞聞版面，，第二類是灌水水版面。。訪問娛樂新聞版面訪問灌水版訪問灌水版面訪問娛樂新聞版整合訪問量將灌水版和娛樂新聞版整合為一個(gè)“我主娛樂”新版值得注意意的問題題CARMA模型型運(yùn)算速速度不是是最快的的，但是是它只需需要對數(shù)數(shù)據(jù)集一一至兩遍遍的掃描描就可以以構(gòu)造規(guī)規(guī)則集；；CARMA模型型及可以以處理Tabular格式的的數(shù)據(jù)，，也可以以處理Transactional格式的的數(shù)據(jù)；；CARMA模型型中需要要設(shè)定的的RuleSupport的大小小，而不不是Support；；CARMA模型型不能處處理數(shù)值值型的數(shù)數(shù)據(jù)。CARMA算法法原理Carma算法法也包括括兩個(gè)部部分尋找頻繁繁項(xiàng)集在頻繁項(xiàng)項(xiàng)集的基基礎(chǔ)上產(chǎn)產(chǎn)生關(guān)聯(lián)聯(lián)規(guī)則Carma尋找找頻繁項(xiàng)項(xiàng)集的過過程又分分為PhaseI和和PhaseIIPhaseI：產(chǎn)生生頻繁項(xiàng)項(xiàng)集的超超集，即即產(chǎn)生潛潛在頻繁繁項(xiàng)集V在PhaseI中中可以隨隨時(shí)調(diào)整整最小支支持度PhaseII：對對潛在頻頻繁項(xiàng)集集V進(jìn)行行刪減得得到最終終的頻繁繁項(xiàng)集CARMA算法法原理初始V為為空集，，將事務(wù)務(wù)按照序序號排序序,逐條條讀入事事務(wù)數(shù)據(jù)據(jù)，并計(jì)計(jì)算以下下三個(gè)整整數(shù)存儲(chǔ)儲(chǔ)在V的的支持格格(SupportLattice)中中：Count(v)：v被插入入V以后后在事務(wù)務(wù)數(shù)據(jù)庫庫中出現(xiàn)現(xiàn)的次數(shù)數(shù)firstTrans(v)：v被被插入V時(shí)所在在事務(wù)的的事務(wù)序序號maxMissed(v)：：v被插插入V之之前已讀讀入的事事務(wù)個(gè)數(shù)數(shù)例如：項(xiàng)項(xiàng)集{a,b}在j時(shí)時(shí)刻進(jìn)入入V,當(dāng)當(dāng)j時(shí)刻刻時(shí)以上上三個(gè)整整數(shù)的情情況CARMA算法法原理根據(jù)Count(v)、maxMissed(v)定定義了v項(xiàng)集的的支持度度的上限限和下限限：minSupport(v)是項(xiàng)集集的實(shí)際際支持度度maxSupport(v)用來判判斷項(xiàng)集集v用來來是否可可以保留留在V中中CARMA算法法原理PhaseI中V產(chǎn)產(chǎn)生的基基本過程程：初始始V為空空集(此此時(shí)只可可添加1-項(xiàng)集集)，讀入第i條事務(wù)務(wù)數(shù)據(jù)v，給出出當(dāng)前的的最小支支持度i,在計(jì)算過過程中，，算法自自動(dòng)調(diào)整整最小支支持度，，即給每每個(gè)事務(wù)務(wù)以一個(gè)個(gè)最小支支持度，，會(huì)形成成一個(gè)最最小支持持度序列列t個(gè)事事務(wù)＝＝(1,2,3……,)如果v是是1-項(xiàng)項(xiàng)集:如果第一一次出現(xiàn)現(xiàn)，則令令Count(v)1,maxMissed(v)0(1-項(xiàng)集集的maxMissed(v)規(guī)定定為0),firstTrans(v)i,且將v加入V(1-項(xiàng)項(xiàng)集自動(dòng)動(dòng)進(jìn)入V)如果不是是第一次次出現(xiàn)，，則Count(v)Count(v)+1;CARMA算法法原理如果v是是k-項(xiàng)項(xiàng)集(k>=2)，則則先按前前述方式式處理包包含的所所有1-項(xiàng)集，，且：如果第一一次出現(xiàn)現(xiàn)，判斷斷該k-項(xiàng)集是是否可以以進(jìn)入V，且令Count(v)1,firstTransi,且如果不是是第一次次出現(xiàn)，，則項(xiàng)集集各子集集的Count(v)Count(v)+1;“修剪””，默認(rèn)認(rèn)每讀入入500個(gè)事務(wù)務(wù)作一次次修剪(從效率率角度考考慮，其其實(shí)可以以讀入一一條修剪剪一次)，即判判斷支持持格中所所有k-項(xiàng)集的的maxSupport(v)，如如果小于于當(dāng)前的的最小支支持度i,則剔除除相應(yīng)項(xiàng)項(xiàng)集出VCARMA算法法原理在PhaseI階段段，k-項(xiàng)集v進(jìn)入V的主要要原則如果一個(gè)個(gè)項(xiàng)集是是頻繁項(xiàng)項(xiàng)集，則則其所有有子集必必定也是是頻繁項(xiàng)項(xiàng)集；反反之，如如一個(gè)項(xiàng)項(xiàng)集的某某個(gè)子集集不是頻頻繁項(xiàng)集集，則該該項(xiàng)集必必定也不不是頻繁繁項(xiàng)集；；Carma在在決定k-項(xiàng)集集v進(jìn)入入頻繁項(xiàng)項(xiàng)集V時(shí)時(shí)，應(yīng)確保v的所有有真子集集已在當(dāng)當(dāng)前事務(wù)務(wù)之前進(jìn)進(jìn)入V中中，這是是v進(jìn)入入V的條條件之一一（要看看所有子子集，若若2項(xiàng)無無所謂，，若3項(xiàng)項(xiàng)則需要要檢驗(yàn)其其2項(xiàng)子子集是否否也在內(nèi)內(nèi)）。項(xiàng)集v加加入V的的必要條條件表述述為：i為當(dāng)前前的事務(wù)務(wù)序號，，即v的的所有真真子集w都是頻頻繁項(xiàng)集集且已在在當(dāng)前事事務(wù)之前前進(jìn)入V中CARMA算法法原理在PhaseI階段段，k-項(xiàng)集v進(jìn)入V的主要要原則判斷v的的真子集集時(shí)應(yīng)從從包含項(xiàng)項(xiàng)目較多多的子集集開始判判斷，如如果包含含項(xiàng)目較較多的子子集已在在V中，，則包含含項(xiàng)目較較少的子子集也一一定在V中。因因此，不不必檢查查所有子子集，只只需要檢檢驗(yàn)?zāi)切┬┌?xiàng)項(xiàng)目最多多的子集集即可。。為提高效效率不必必檢驗(yàn)所所有真子子集，只只需要檢檢查那些些：其中：|w|、、|v|為所所包含的的項(xiàng)目數(shù)數(shù)kCARMA算法法原理計(jì)算maxSupport(v)的的關(guān)鍵是是計(jì)算maxMissed(v)maxMissed計(jì)計(jì)算的依依據(jù)一：：其最大大子集的的頻繁程程度在第i個(gè)個(gè)時(shí)刻，v的的具有最最大firstTrans的的真子集集w(|w|=|v|-1)，其支支持度一一定大于于v的，，即：此時(shí)i是相等的明顯然CARMA算法法原理計(jì)算maxSupport(v)的的關(guān)鍵是是計(jì)算maxMissed(v)依據(jù)二：：用戶以以往定義義的最小小支持度度的情況況在i+1時(shí)刻，，以往最小支持持度序列列表示為為i＝(1,2,3…,i)Carma中定定義了關(guān)關(guān)于i的天花板(ceilingof)序列，記為天花板的的含義是是：當(dāng)j>i時(shí)(j=1,2,..i-1)：當(dāng)j<i時(shí)(j=1,2,..i-1)：例如：＝(0.3,0.7,0.9,0.5)CARMA算法法原理計(jì)算maxSupport(v)的的關(guān)鍵是是計(jì)算maxMissed(v)依據(jù)二：：用戶以以往定義義的最小小支持度度的情況況總之有：主主要取決于于以往的一一系列最小小支持度(0,1,3)[1,1]CARMA算法原理理PhaseI舉例例事務(wù)序列T=({a,b},{a,b,c},{b,c}),定定義的支持持度閥值序序列=(0.3,0.9,0.5)V{}t1={a,b}1=0.3V{{a},}t2={a,b,c}2=0.9V{{a},,{c},{a,b}}a,b的maxSupport均大于于0.3,不能剔除出出V{a}(0,1,1)[1,1](0,1,1