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

我國社會經(jīng)濟(jì)發(fā)展綜合評價指數(shù)研究--CARMA

ContinuousAssociationRuleMiningAlgorithm報告人：徐啟元指導(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ù)項間的相關(guān)性．常用技術(shù)：關(guān)聯(lián)規(guī)則：即尋找在同一個事件中出現(xiàn)的不同項目的相關(guān)性

例如：找出顧客經(jīng)常同時購買哪些商品。網(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ī)則的前項和后項。Instances對于每一條規(guī)則，它的Instances值指的是所有記錄中包含該規(guī)則的antecedent的記錄的數(shù)量。面包牛奶前項Antecedent后項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%四條記錄中只有一條既包含了前項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ī)則“面包=》牛奶”，那么購買了面包的第一、二及四行都會被預(yù)測購買了牛奶，但事實上這三個預(yù)測只有第二個是正確的，所以confidence=1/3×100%=33.3%CARMA模塊中的基本概念Lift在已知某規(guī)則的consequent發(fā)生的先驗概率的情況下，某規(guī)則的Lift被定義為Confidence和該先驗概率的比率值。IDP1P2P3P41breadcheesebutterwater2watermilkbreadnoodle3milknoodlemeatbeer4fishsoftdrinkfrozenmealbread那么對于一條記錄，那么不采用任何規(guī)則進(jìn)行預(yù)測，隨便猜測該顧客是否該買牛奶的正確率是50%已知有50%的人購買了牛奶：）如果采用“面包=》牛奶”的規(guī)則進(jìn)行預(yù)測的話，正確率，即confidence=33.3%比隨便猜測的正確率還低。那么此時的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，每筆交易包含了顧客的卡號、性別、年齡、收入、付款方式等一系列個人信息，以及其購買的各種食品清單；該數(shù)據(jù)集為Tabular格式的數(shù)據(jù)。研究目的為超市貨架的擺放提供科學(xué)的依據(jù)；為超市商品促銷決策提供支持。案例研究購物籃分析加入type模塊對變量類型進(jìn)行設(shè)置。先點(diǎn)擊ReadValues將各個變量實例化。購物籃分析將CARMA模塊加入流中，并雙擊打開進(jìn)行參數(shù)設(shè)置。點(diǎn)擊點(diǎn)擊購物籃分析對Model選項卡進(jìn)行設(shè)置。修改RuleSupport、RuleConfidence以及RuleSize的大小。點(diǎn)擊此處，打開Model選項卡編輯對這三個選項進(jìn)行編輯以控制輸出的規(guī)則的數(shù)目購物籃分析對Expert選項卡進(jìn)行設(shè)置，如果對CARMA算法比較了解的用戶，可以對該選項卡進(jìn)行設(shè)定以獲得使CARMA模塊具有更好的性能。選擇此項，則輸出的規(guī)則中后項（consequent）只能由一個元素。選擇該選項可以讓CARMA算法周期性的剔除掉當(dāng)前不太重要的規(guī)則，加速建模。設(shè)定周期的大小，周期設(shè)定的越小，則越省內(nèi)存，但是CARMA算法執(zhí)行時間常；反之，則短。設(shè)定該選項可以加速CARMA算法的執(zhí)行。其大致思想是：一開始先給定一個較高的support值，將不顯著的規(guī)則排除在外，然后再一次降低support值。設(shè)定support值降低的速度選擇該項，則CARMA模型會輸出不包含antecedent的規(guī)則。購物籃分析執(zhí)行后建立的模型會顯示在Canvas內(nèi)。共產(chǎn)生16條規(guī)則每一行分別顯示了一組規(guī)則，以及度量該規(guī)則的一組指標(biāo)，如：Lift、support等。點(diǎn)擊該圖標(biāo)可以按指定規(guī)則篩選出自己想要的規(guī)則。生成對應(yīng)規(guī)則集的節(jié)點(diǎn)，包括三種節(jié)點(diǎn)：SelectNode、FilteredNode以及Ruleset節(jié)點(diǎn)。購物籃分析置信度（Confidence）最高的前三個規(guī)則：Cannedveg&BeerFrozenmealFrozenmeal&BeerCannedvegCannedveg&FrozenmealBeerFrozenmealConnedvegBeer促銷購物籃分析CARMA模型可以直接放在流中對數(shù)據(jù)進(jìn)行打分預(yù)測（scoring）。在打分之前可以雙擊模型打開Settings選項卡進(jìn)行相關(guān)的參數(shù)設(shè)置。設(shè)定用于預(yù)測的規(guī)則個數(shù)為選取規(guī)則設(shè)定標(biāo)準(zhǔn)，從而可以根據(jù)該規(guī)則選出最顯著的n條規(guī)則，n由上一個選項設(shè)定。設(shè)定該項，則允許用于預(yù)測的n條規(guī)則可以有相同的后項，即可以允許幾條規(guī)則有相同的預(yù)測結(jié)果。勾選該項，則在應(yīng)用規(guī)則進(jìn)行預(yù)測之前，系統(tǒng)會剔除掉不符合要求的數(shù)據(jù)行，不對其進(jìn)行預(yù)測。購物籃分析對CARMA模型設(shè)置好了以后就可以將CARMA模型加入流中對數(shù)據(jù)進(jìn)行預(yù)測了，本文僅用一條規(guī)則進(jìn)行預(yù)測，結(jié)果存入表中（見下頁）。購物籃分析預(yù)測值預(yù)測置信度所使用規(guī)則的編號購物籃分析用CARMA模型預(yù)測顧客的購買行為ConfectioneryFreshmeatDairy？Wine購物籃分析除了直接使用生成的CARMA模型進(jìn)行預(yù)測外，還有一種預(yù)測方式即使用RuleSet。

使用Generate菜單生成想要的RuleSet節(jié)點(diǎn)，并將該節(jié)點(diǎn)放入流中進(jìn)行預(yù)測。點(diǎn)擊確定以后可以生成一個規(guī)則集節(jié)點(diǎn)，將該節(jié)點(diǎn)加入流中就可以進(jìn)行預(yù)測了。案例研究之網(wǎng)絡(luò)日志分析數(shù)據(jù)準(zhǔn)備使用數(shù)據(jù)為某網(wǎng)站五天的訪問日志；該數(shù)據(jù)集記錄數(shù)為173665，每行記錄對應(yīng)用戶對服務(wù)器的一個頁面請求，記錄了用戶IP地址、請求時間、請求頁面URL、訪問協(xié)議、請求狀態(tài)以及端口號等信息。本文為了簡化僅引入前三個變量，且頁面已經(jīng)過分類，訪問已按事務(wù)劃分；該數(shù)據(jù)集為Transactional格式的數(shù)據(jù)。研究目的找出用戶的訪問模式，為網(wǎng)站結(jié)構(gòu)上的調(diào)整和網(wǎng)站經(jīng)營決策提供支持。網(wǎng)絡(luò)日志分析加載數(shù)據(jù)集網(wǎng)絡(luò)日志分析使用CARMA模塊來處理Transactional格式的網(wǎng)絡(luò)日志數(shù)據(jù)，并從中找出關(guān)聯(lián)規(guī)則。雙擊打開打開Fields選項卡進(jìn)行編輯。勾選該項，將CARMA模型處理的數(shù)據(jù)格式改為Transactional格式指定數(shù)據(jù)的唯一標(biāo)識，標(biāo)識相同的記錄屬于同一個事務(wù)該欄用以指定交易數(shù)據(jù)字段，本文中這里指定的是當(dāng)前請求的頁面種類。網(wǎng)絡(luò)日志分析雙擊打開Model選項卡進(jìn)行編輯，設(shè)定RulesSupport、RuleConfidence以及RuleSize等參數(shù)。網(wǎng)絡(luò)日志分析查看CARMA模型生成的規(guī)則集網(wǎng)絡(luò)日志分析數(shù)據(jù)中定義的第一類頁面為娛樂新聞版面，第二類是灌水版面。訪問娛樂新聞版面訪問灌水版訪問灌水版面訪問娛樂新聞版整合訪問量將灌水版和娛樂新聞版整合為一個“我主娛樂”新版值得注意的問題CARMA模型運(yùn)算速度不是最快的，但是它只需要對數(shù)據(jù)集一至兩遍的掃描就可以構(gòu)造規(guī)則集；CARMA模型及可以處理Tabular格式的數(shù)據(jù)，也可以處理Transactional格式的數(shù)據(jù)；CARMA模型中需要設(shè)定的RuleSupport的大小，而不是Support；CARMA模型不能處理數(shù)值型的數(shù)據(jù)。CARMA算法原理Carma算法也包括兩個部分尋找頻繁項集在頻繁項集的基礎(chǔ)上產(chǎn)生關(guān)聯(lián)規(guī)則Carma尋找頻繁項集的過程又分為PhaseI和PhaseIIPhaseI：產(chǎn)生頻繁項集的超集，即產(chǎn)生潛在頻繁項集V在PhaseI中可以隨時調(diào)整最小支持度PhaseII：對潛在頻繁項集V進(jìn)行刪減得到最終的頻繁項集CARMA算法原理初始V為空集，將事務(wù)按照序號排序,逐條讀入事務(wù)數(shù)據(jù)，并計算以下三個整數(shù)存儲在V的支持格(SupportLattice)中：Count(v)：v被插入V以后在事務(wù)數(shù)據(jù)庫中出現(xiàn)的次數(shù)firstTrans(v)：v被插入V時所在事務(wù)的事務(wù)序號maxMissed(v)：v被插入V之前已讀入的事務(wù)個數(shù)例如：項集{a,b}在j時刻進(jìn)入V,當(dāng)j時刻時以上三個整數(shù)的情況CARMA算法原理根據(jù)Count(v)、maxMissed(v)定義了v項集的支持度的上限和下限：minSupport(v)是項集的實際支持度maxSupport(v)用來判斷項集v用來是否可以保留在V中CARMA算法原理PhaseI中V產(chǎn)生的基本過程：初始V為空集(此時只可添加1-項集)，讀入第i條事務(wù)數(shù)據(jù)v，給出當(dāng)前的最小支持度i,在計算過程中，算法自動調(diào)整最小支持度，即給每個事務(wù)以一個最小支持度，會形成一個最小支持度序列t個事務(wù)＝(1,2,3…,)如果v是1-項集:如果第一次出現(xiàn)，則令Count(v)1,maxMissed(v)

0(1-項集的maxMissed(v)規(guī)定為0),firstTrans(v)i,且將v加入V(1-項集自動進(jìn)入V)如果不是第一次出現(xiàn)，則Count(v)Count(v)+1;CARMA算法原理如果v是k-項集(k>=2)，則先按前述方式處理包含的所有1-項集，且：如果第一次出現(xiàn)，判斷該k-項集是否可以進(jìn)入V，且令Count(v)1,firstTransi,且如果不是第一次出現(xiàn)，則項集各子集的Count(v)Count(v)+1;“修剪”，默認(rèn)每讀入500個事務(wù)作一次修剪(從效率角度考慮，其實可以讀入一條修剪一次)，即判斷支持格中所有k-項集的maxSupport(v)，如果小于當(dāng)前的最小支持度i,則剔除相應(yīng)項集出VCARMA算法原理在PhaseI階段，k-項集v進(jìn)入V的主要原則如果一個項集是頻繁項集，則其所有子集必定也是頻繁項集；反之，如一個項集的某個子集不是頻繁項集，則該項集必定也不是頻繁項集；Carma在決定k-項集v進(jìn)入頻繁項集V時，應(yīng)確保v的所有真子集已在當(dāng)前事務(wù)之前進(jìn)入V中，這是v進(jìn)入V的條件之一（要看所有子集，若2項無所謂，若3項則需要檢驗其2項子集是否也在內(nèi)）。項集v加入V的必要條件表述為：i為當(dāng)前的事務(wù)序號，即v的所有真子集w都是頻繁項集且已在當(dāng)前事務(wù)之前進(jìn)入V中CARMA算法原理在PhaseI階段，k-項集v進(jìn)入V的主要原則判斷v的真子集時應(yīng)從包含項目較多的子集開始判斷，如果包含項目較多的子集已在V中，則包含項目較少的子集也一定在V中。因此，不必檢查所有子集，只需要檢驗?zāi)切┌椖孔疃嗟淖蛹纯?。為提高效率不必檢驗所有真子集，只需要檢查那些：其中：|w|、|v|為所包含的項目數(shù)kCARMA算法原理計算maxSupport(v)的關(guān)鍵是計算maxMissed(v)maxMissed計算的依據(jù)一：其最大子集的頻繁程度在第i個時刻，v的具有最大firstTrans的真子集w(|w|=|v|-1)，其支持度一定大于v的，即：此時i是相等的明顯然CARMA算法原理計算maxSupport(v)的關(guān)鍵是計算maxMissed(v)依據(jù)二：用戶以往定義的最小支持度的情況在i+1時刻，以往最小支持度序列表示為i＝(1,2,

3…,i)Carma中定義了關(guān)于i的天花板(ceilingof)序列，記為天花板的含義是：當(dāng)j>i時(j=1,2,..i-1)：當(dāng)j<i時(j=1,2,..i-1)：例如：＝(0.3,0.7,0.9,0.5)CARMA算法原理計算maxSupport(v)的關(guān)鍵是計算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)[1,1]{a}(0,1,2)[1,1](0,1,2)[1,1]{c}(0,2,1)[0.5,0.5]{a,b}(1,2,1)[0.5,1]t3={b,c}V{{a},,{c},{a,b},{b,c}}1=0.5{a}(0,1,2)[0.6