關(guān)聯(lián)規(guī)則挖掘舉例課件

1、關(guān)聯(lián)規(guī)則挖掘的步驟關(guān)聯(lián)規(guī)則挖掘是一個(gè)兩步的過程：找出所有頻繁項(xiàng)集由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須大于或者等于最小支持度和最小置信度大于或者等于最小支持度的項(xiàng)集Apriori算法Apriori算法是一種經(jīng)典的生成布爾型關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集挖掘算法。Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個(gè)步驟：通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項(xiàng)集，即支持度不低于用戶設(shè)定的閾值的項(xiàng)集；利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小置信度的規(guī)則。挖掘或識(shí)別出所有頻繁項(xiàng)集是該算法的核心，占整個(gè)計(jì)算量的大部分。 Apriori算法的重要性質(zhì)性質(zhì)1：頻繁項(xiàng)集的子集必為頻繁項(xiàng)集性質(zhì)2：非頻繁項(xiàng)集的超集一定是非頻繁的假設(shè)項(xiàng)集A

2、,C是頻繁項(xiàng)集，則A和C也為頻繁項(xiàng)集假設(shè)項(xiàng)集D不是頻繁項(xiàng)集，則A,D和C,D也不是頻繁項(xiàng)集Apriori算法舉例現(xiàn)有A、B、C、D、E五種商品的交易記錄表，找出所有頻繁項(xiàng)集，假設(shè)最小支持度=50%,最小置信度=50%Apriori算法舉例_產(chǎn)生頻繁項(xiàng)集K=1支持度50K=2支持度50支持度50Apriori算法舉例_產(chǎn)生頻繁項(xiàng)集支持度50支持度50Apriori算法舉例_產(chǎn)生關(guān)聯(lián)規(guī)則對于頻繁項(xiàng)集B,C,E,它的非空子集有B、C、E、B,C、B,E、C,E。以下就是據(jù)此獲得的關(guān)聯(lián)規(guī)則及其置信度。規(guī)則置信度ConfidenceBCE66.7%CBE66.7%EBC66.7%CEB1BEC66.7%

3、BCE1置信度50%(最小置信度)，都是強(qiáng)關(guān)聯(lián)規(guī)則Apriori算法弊端需要多次掃描數(shù)據(jù)表如果頻繁集最多包含10個(gè)項(xiàng)，那么就需要掃描交易數(shù)據(jù)表10遍，這需要很大的I/O負(fù)載產(chǎn)生大量頻繁集若有100個(gè)項(xiàng)目，可能產(chǎn)生候選項(xiàng)數(shù)目FP-growth算法Jiawei Han等人在2000年提出了一種基于FP-樹的關(guān)聯(lián)規(guī)則挖掘算法FP_growth，它采取“分而治之”的策略，將提供頻繁項(xiàng)目集的數(shù)據(jù)庫壓縮成一棵頻繁模式樹（FP-樹）。僅兩次掃描數(shù)據(jù)庫。理論和實(shí)驗(yàn)表明該算法優(yōu)于Apriori算法。FP-growth算法其他關(guān)聯(lián)規(guī)則挖掘算法約束性關(guān)聯(lián)規(guī)則挖掘算法僅設(shè)置支持度和置信度閾值，缺乏用戶控制，可能產(chǎn)生過

4、多的規(guī)則，實(shí)際效果可能并不好。用戶關(guān)心的是某些特定的關(guān)聯(lián)規(guī)則，這需要把一些約束條件引入到挖掘算法中，從而篩選出符合約束條件的有用規(guī)則，提高算法的運(yùn)行效率和用戶滿意度。增量式關(guān)聯(lián)規(guī)則挖掘算法數(shù)據(jù)集不斷增長，有新的數(shù)據(jù)加入后，重新挖掘很費(fèi)時(shí)。增量式關(guān)聯(lián)規(guī)則挖掘算法是當(dāng)數(shù)據(jù)庫變化后，在原挖掘結(jié)果的基礎(chǔ)上生成新的關(guān)聯(lián)規(guī)則，刪除過時(shí)的關(guān)聯(lián)規(guī)則。多層關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則的價(jià)值衡量客觀上，使用“支持度和置信度”框架可能會(huì)產(chǎn)生一些不正確的規(guī)則。只憑支持度和置信度閾值未必總能找出符合實(shí)際的規(guī)則。例：歌曲A、歌曲C為小眾歌曲，歌曲B為口水歌，共有10萬個(gè)用戶，有200個(gè)人聽過歌曲A，這200個(gè)人里面有60個(gè)聽過口

5、水歌B，有40個(gè)人聽過歌曲C。聽過歌曲C的人數(shù)是300，聽過口水歌B的人為50000。Confidence(AB) = 0.3，Confidence(AC) = 0.2但是10W人里面有5W聽過歌曲B，有一半的用戶都喜歡歌曲B，但聽過歌曲A的人里面只有30%的人喜歡歌曲 B聽過歌曲A的人不喜歡歌曲B貌似A和B更相關(guān)矛盾的規(guī)則，如何評價(jià)？關(guān)聯(lián)規(guī)則價(jià)值衡量提升度Lift(AB)=Confidence(AB)/Support(B)=引入提升度Lift，以度量此規(guī)則是否可用。它描述的是：相對于不用規(guī)則，使用規(guī)則可以提高多少。Lift(AB) =Confidence(AB)/Support(B)=0.3/0.5=0.6Lift(AC)=Confidence(AC)/Support(C)=0.2/(300/100000)=66.7歌曲A與B負(fù)相關(guān)，A與C正相關(guān)。Lift大于1，表示使用這條規(guī)則進(jìn)行推薦能提升用戶聽歌曲C的概率。Lift小于1，則表示使用這條規(guī)則來進(jìn)行推薦，還不如不推薦，讓顧客自行選擇好了。Confidence(AB) = 0.3Confidence(AC) = 0.2Support(B)=0.5Support(C)=300/100000關(guān)聯(lián)規(guī)則的價(jià)值衡量主觀上，一個(gè)規(guī)則的有用與否最終取決于用戶的感覺，只有用戶才能決定規(guī)則的有效性、可行性。所以