關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則挖掘黎都2004-12-21基本概念（1）數(shù)據(jù)，數(shù)據(jù)集項目，項目集事務t包含項目集X支持數(shù)，頻繁項目集（頻集）Support（X）=a(x)/|D|置信度基本概念（2）關(guān)聯(lián)規(guī)則：若項目集X與Y交集為空，則X=>Y為關(guān)聯(lián)規(guī)則，其中：Support(X=>Y)=Support(X并Y）Confidence（X=>Y）=Suppose(X并Y）/Suppose(X)關(guān)聯(lián)規(guī)則的目的對于指定的minsupport和minconfidence使得support(X)>=minsupportConfidence(X）>=minconfidence則稱關(guān)聯(lián)規(guī)則X=>Y為強規(guī)則關(guān)聯(lián)規(guī)則挖掘的就是挖掘出事務集D中的強規(guī)則關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘分為兩個子問題：1，根據(jù)最小支持度找出數(shù)據(jù)集D中的所有頻集；2，根據(jù)頻集和最小置信度產(chǎn)生關(guān)聯(lián)規(guī)則；關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)算法發(fā)現(xiàn)算法解決的是關(guān)聯(lián)規(guī)則挖掘的第一個問題關(guān)聯(lián)規(guī)則分為布爾關(guān)聯(lián)規(guī)則和多值規(guī)則多值關(guān)聯(lián)規(guī)則都轉(zhuǎn)化為布爾關(guān)聯(lián)規(guī)則來解決，因此先介紹布爾關(guān)聯(lián)規(guī)則算法Apriori，AprioriTid，AprioriHybridApriori算法Agrawal等人在1993年提出的AIS和SETM的基礎上在1994年提出Apriori和AprioriTiApriori和AprioriTid算法利用前次過程中的數(shù)據(jù)項目集來生成新的候選數(shù)據(jù)項目集，減少了中間不必要的數(shù)據(jù)項目集的生成，提高了效率Apriori算法L1={大項目集1項目集}For(k=2;Lk-1

非空；k++)dobeginCk=apriori-gen(Lk-1);for所有事務tdobeginCt=subset(Ck,t)for所有候選c（屬于Ct

）doc.count++;Apriori算法End

Lk

={c屬于Ck|c.count>=minsupp}EndApriori算法得到的頻集為Lk

的并集Apriori算法分析分為第一次遍歷和第k次遍歷第一次遍歷計算每個項目的具體值，確定大項目集1項目集L1

第k次遍歷利用前一次找到的大項集Lk-1

和Apriori-gen函數(shù)產(chǎn)生候選集Ck，然后掃描數(shù)據(jù)庫，得到Ck

中候選的支持度，剔除了不合格的候選后Ck作為Lk

Apriori算法分析:Apriori-gen本質(zhì)是合并項目集成為候選項目集算法：InsertintoCk

Selectp[1],p[2],……，p[k-1]，q[k-1]FromLk-1p，Lk-1qWherep[1]=q[1]，……，p[k-2]=q[k-2]p[k-1]<q[k-1]Apriori算法分析:Apriori-gen然后，對于Ck

中某集合c的任意子集，如果不存在于Lk-1，則刪除c；例子：L3

為{123}{124}{135}{234}在合并后為C3:{{1234}{1345}}；因為{1345}中的{145}不存在，所以C3

中{1345}應該刪除，故L4:{1234}Apirori算法分析：Subset候選項目集Ck

是存儲在一個Hash樹中的，并且要求項目集中的項目有序Subset函數(shù)尋找所有包含在某個事務中的候選，使用Hash查找實質(zhì)：得到候選集Ck

中候選項c的支持度AprioriTid算法AprioriTid算法由Apriori算法改進優(yōu)點：只和數(shù)據(jù)庫做一次交互，無須頻繁訪問數(shù)據(jù)庫將Apirori中的Ck

擴展，內(nèi)容由{c}變?yōu)閧TID，c}，TID用于唯一標識事務引入Bk

，使得Bk

對于事務的項目組織集合，而不是被動的等待Ck

來匹配ApioriTid算法舉例：minsupp=2數(shù)據(jù)庫：TID項目100134200235300123540025ApioriTid算法示例TID項目集100{1}{3}{4}200{2}{3}{5}300{1}{2}{3}{5}400{2}{5}項集支持度{1}2{2}3{3}

3{5}3ApioriTid算法示例TID項目集100{{13}}200{{23}{25}{35}}300{{12}{13}{15}{23}{25}{35}}400{{25}}項集支持度{13}2{23}2{25}

3{35}2ApioriTid算法示例TID項目集100空200{{235}}300{{235}}400空ApioriTid算法上面圖中分別為Bk

和Lk，而Ck

和Apriori算法產(chǎn)生的一樣，因此沒有寫出來可以看到Bk

由Bk-1

得到，無須由數(shù)據(jù)庫取數(shù)據(jù)缺點：內(nèi)存要求很大，事務過多的時候資源難以滿足ApioriHybrid算法這種算法將Apriori算法和AprioriTid算法混合，利用各自優(yōu)點彌補不足；利用的原理：隨著候選集的元素擴充，所能匹配的事務將可能減少算法：先使用Apriori算法，當能匹配的事務減少到內(nèi)存可以容納的程度，使用ApiroriTid算法ApioriHybrid算法性能AprioriHybrid算法性能比Apriori和AprioriTid算法都要好經(jīng)過算法統(tǒng)計平均，AprioriHybrid比Apriori效率高30%，比AprioriTid高60%但是應用上比兩者都復雜，相對而言用Apriori可以得到更簡單的應用多值屬性關(guān)聯(lián)剛才介紹的都是布爾屬性關(guān)聯(lián)，實際中多值屬性應用也很多解決多值關(guān)聯(lián)的辦法在于把QARP轉(zhuǎn)為BARP來解決解決要點：劃分值域區(qū)間太寬，置信度將降低太窄，支持度將降低多值屬性關(guān)聯(lián)定義：挖掘多值關(guān)聯(lián)規(guī)則問題就是在給定的交易集合D中產(chǎn)生所有滿足最小支持度和最小置信度的多值關(guān)聯(lián)規(guī)則的過程MAQA算法MAQA算法MAQA算法將QARP問題轉(zhuǎn)為BARP問題。Step1：對于多值屬性A，若取值范圍為[L,R]，劃分為若干區(qū)間。若為數(shù)量屬性，應用聚類算法確定值的劃分，若為類別屬性，采用歸納進行劃分。MAQA算法Step2：將劃分后的屬性區(qū)間映射為序?qū)?lt;A,k>，A屬于布爾集Step3：從項目集中找出有價值的項，構(gòu)成頻集Step4：在頻集中迭代的找到支持度合格的兩個項，并加入頻集項目集中Step5：應用頻集產(chǎn)生關(guān)聯(lián)規(guī)則Step6：確定有價值的關(guān)聯(lián)規(guī)則作為輸出MAQA算法第一步劃分為關(guān)鍵，支持度和置信度證明對立矛盾的關(guān)系，合適劃分是個重要的步驟。第二步和第五步都很直接，第五步計算最小置信度如：ABCD和AB都為頻集，通過Conf=supp(ABCD)/supp(AB)判斷是否超過最小置信度MAQA算法第三步為Apriori算法或者其改進算法第六步采用interest度量方法下面重點介紹第一步和第四步多值劃分的聚類算法CP聚類算法CPFor每個屬性值大于N的屬性do計算每個屬性對應的事務數(shù)目尋找局部最大點和最小點確定區(qū)間計算minL和maxL之間的事務數(shù)sumi如果滿足合并條件則合并相鄰區(qū)間得到k個區(qū)間S=sumi的和-max(sumi)–min(sumi)聚類算法CPS平均=S/（K-2）尋找所有大于c*S平均的sumi，并把結(jié)果存于PForP中每個區(qū)間jdoIfsumi/(minRi–MinLi)>S/(minR-minL)then保存區(qū)間j作為輸