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

關(guān)聯(lián)規(guī)則挖掘舉例對(duì)于規(guī)則A

C：支持度

=support({A,C})=50%置信度

=support({A,C})/support({A})=66.6%假設(shè)最小值支持度為50%，最小置信度為50%規(guī)則A

C滿足最小支持度和最小置信度，所以它是強(qiáng)關(guān)聯(lián)規(guī)則2021/3/71關(guān)聯(lián)規(guī)則挖掘舉例對(duì)于規(guī)則AC：假設(shè)最小值支持度為50%，關(guān)聯(lián)規(guī)則挖掘的步驟關(guān)聯(lián)規(guī)則挖掘是一個(gè)兩步的過(guò)程：找出所有頻繁項(xiàng)集由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須大于或者等于最小支持度和最小置信度大于或者等于最小支持度的項(xiàng)集2021/3/72關(guān)聯(lián)規(guī)則挖掘的步驟關(guān)聯(lián)規(guī)則挖掘是一個(gè)兩步的過(guò)程：大于或者等于Apriori算法Apriori算法是一種經(jīng)典的生成布爾型關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集挖掘算法。Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過(guò)程分為兩個(gè)步驟：通過(guò)迭代，檢索出事務(wù)數(shù)據(jù)庫(kù)中的所有頻繁項(xiàng)集，即支持度不低于用戶設(shè)定的閾值的項(xiàng)集；利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小置信度的規(guī)則。挖掘或識(shí)別出所有頻繁項(xiàng)集是該算法的核心，占整個(gè)計(jì)算量的大部分。2021/3/73Apriori算法Apriori算法是一種經(jīng)典的生成布爾型關(guān)Apriori算法的重要性質(zhì)性質(zhì)1：頻繁項(xiàng)集的子集必為頻繁項(xiàng)集性質(zhì)2：非頻繁項(xiàng)集的超集一定是非頻繁的假設(shè)項(xiàng)集{A,C}是頻繁項(xiàng)集，則{A}和{C}也為頻繁項(xiàng)集假設(shè)項(xiàng)集{D}不是頻繁項(xiàng)集，則{A,D}和{C,D}也不是頻繁項(xiàng)集2021/3/74Apriori算法的重要性質(zhì)假設(shè)項(xiàng)集{A,C}是頻繁項(xiàng)集，則Apriori算法舉例現(xiàn)有A、B、C、D、E五種商品的交易記錄表，找出所有頻繁項(xiàng)集，假設(shè)最小支持度>=50%,最小置信度>=50%2021/3/75Apriori算法舉例現(xiàn)有A、B、C、D、E五種商品的交易記Apriori算法舉例_產(chǎn)生頻繁項(xiàng)集K=1支持度<50K=2支持度<50支持度<502021/3/76Apriori算法舉例_產(chǎn)生頻繁項(xiàng)集K=1支持度<50K=2Apriori算法舉例_產(chǎn)生頻繁項(xiàng)集支持度<50支持度<502021/3/77Apriori算法舉例_產(chǎn)生頻繁項(xiàng)集支持度<50支持度<50Apriori算法舉例_產(chǎn)生關(guān)聯(lián)規(guī)則對(duì)于頻繁項(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%BCE1置信度≥50%(最小置信度)，都是強(qiáng)關(guān)聯(lián)規(guī)則2021/3/78Apriori算法舉例_產(chǎn)生關(guān)聯(lián)規(guī)則對(duì)于頻繁項(xiàng)集{B,C,EApriori算法弊端需要多次掃描數(shù)據(jù)表如果頻繁集最多包含10個(gè)項(xiàng)，那么就需要掃描交易數(shù)據(jù)表10遍，這需要很大的I/O負(fù)載產(chǎn)生大量頻繁集若有100個(gè)項(xiàng)目，可能產(chǎn)生候選項(xiàng)數(shù)目2021/3/79Apriori算法弊端需要多次掃描數(shù)據(jù)表2021/3/79FP-growth算法JiaweiHan等人在2000年提出了一種基于FP-樹(shù)的關(guān)聯(lián)規(guī)則挖掘算法FP_growth，它采取“分而治之”的策略，將提供頻繁項(xiàng)目集的數(shù)據(jù)庫(kù)壓縮成一棵頻繁模式樹(shù)（FP-樹(shù)）。僅兩次掃描數(shù)據(jù)庫(kù)。理論和實(shí)驗(yàn)表明該算法優(yōu)于Apriori算法。2021/3/710FP-growth算法JiaweiHan等人在2000年提FP-growth算法2021/3/711FP-growth算法2021/3/711其他關(guān)聯(lián)規(guī)則挖掘算法約束性關(guān)聯(lián)規(guī)則挖掘算法僅設(shè)置支持度和置信度閾值，缺乏用戶控制，可能產(chǎn)生過(guò)多的規(guī)則，實(shí)際效果可能并不好。用戶關(guān)心的是某些特定的關(guān)聯(lián)規(guī)則，這需要把一些約束條件引入到挖掘算法中，從而篩選出符合約束條件的有用規(guī)則，提高算法的運(yùn)行效率和用戶滿意度。增量式關(guān)聯(lián)規(guī)則挖掘算法數(shù)據(jù)集不斷增長(zhǎng)，有新的數(shù)據(jù)加入后，重新挖掘很費(fèi)時(shí)。增量式關(guān)聯(lián)規(guī)則挖掘算法是當(dāng)數(shù)據(jù)庫(kù)變化后，在原挖掘結(jié)果的基礎(chǔ)上生成新的關(guān)聯(lián)規(guī)則，刪除過(guò)時(shí)的關(guān)聯(lián)規(guī)則。多層關(guān)聯(lián)規(guī)則挖掘……2021/3/712其他關(guān)聯(lián)規(guī)則挖掘算法約束性關(guān)聯(lián)規(guī)則挖掘算法2021/3/71關(guān)聯(lián)規(guī)則的價(jià)值衡量客觀上，使用“支持度和置信度”框架可能會(huì)產(chǎn)生一些不正確的規(guī)則。只憑支持度和置信度閾值未必總能找出符合實(shí)際的規(guī)則。例：歌曲A、歌曲C為小眾歌曲，歌曲B為口水歌，共有10萬(wàn)個(gè)用戶，有200個(gè)人聽(tīng)過(guò)歌曲A，這200個(gè)人里面有60個(gè)聽(tīng)過(guò)口水歌B，有40個(gè)人聽(tīng)過(guò)歌曲C。聽(tīng)過(guò)歌曲C的人數(shù)是300，聽(tīng)過(guò)口水歌B的人為50000。Confidence(A→B)=0.3，Confidence(A→C)=0.2但是10W人里面有5W聽(tīng)過(guò)歌曲B，有一半的用戶都喜歡歌曲B，但聽(tīng)過(guò)歌曲A的人里面只有30%的人喜歡歌曲B聽(tīng)過(guò)歌曲A的人不喜歡歌曲B貌似A和B更相關(guān)矛盾的規(guī)則，如何評(píng)價(jià)？2021/3/713關(guān)聯(lián)規(guī)則的價(jià)值衡量客觀上，使用“支持度和置信度”框架可能會(huì)產(chǎn)關(guān)聯(lián)規(guī)則價(jià)值衡量提升度Lift(AB)=Confidence(AB)/Support(B)=引入提升度Lift，以度量此規(guī)則是否可用。它描述的是：相對(duì)于不用規(guī)則，使用規(guī)則可以提高多少。Lift(A→B)=Confidence(AB)/Support(B)=0.3/0.5=0.6Lift(A→C)=Confidence(AC)/Support(C)=0.2/(300/100000)=66.7歌曲A與B負(fù)相關(guān)，A與C正相關(guān)。Lift大于1，表示使用這條規(guī)則進(jìn)行推薦能提升用戶聽(tīng)歌曲C的概率。Lift小于1，則表示使用這條規(guī)則來(lái)進(jìn)行推薦，還不如不推薦，讓顧客自行選擇好了。Confidence(A→B)=0.3Confidence(A→C)=0.2Support(B)=0.5Support(C)=300/1000002021/3/714關(guān)聯(lián)規(guī)則價(jià)值衡量提升度Lift(AB)=Confidenc關(guān)聯(lián)規(guī)則的價(jià)值衡量主觀上，一個(gè)規(guī)則的有用與否最終取決于用戶的感覺(jué)，只有用戶才能決定規(guī)則的有效性、可行性。所以，應(yīng)該將需求和關(guān)聯(lián)規(guī)則挖掘方法緊密地結(jié)合起來(lái)。例如使用“約束性關(guān)聯(lián)規(guī)則挖掘算法”，將約束條件與算法緊密結(jié)合，既能提高數(shù)據(jù)挖掘效率，又能明確數(shù)據(jù)挖掘的目標(biāo)。