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

關(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ī)則 關(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)集 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ì)算量的大部分 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)集 Apriori算法舉例 現(xiàn)有A B C D E五種商品的交易記錄表 找出所有頻繁項(xiàng)集 假設(shè)最小支持度 50 最小置信度 50 Apriori算法舉例 產(chǎn)生頻繁項(xiàng)集 K 1 支持度 50 Apriori算法舉例 產(chǎn)生頻繁項(xiàng)集 Apriori算法舉例 產(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ī)則及其置信度 置信度 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算法 JiaweiHan等人在2000年提出了一種基于FP 樹的關(guān)聯(lián)規(guī)則挖掘算法FP growth 它采取 分而治之 的策略 將提供頻繁項(xiàng)目集的數(shù)據(jù)庫(kù)壓縮成一棵頻繁模式樹 FP 樹 僅兩次掃描數(shù)據(jù)庫(kù) 理論和實(shí)驗(yàn)表明該算法優(yōu)于Apriori算法 FP growth算法 其他關(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ī)則挖掘 關(guān)聯(lián)規(guī)則的價(jià)值衡量 客觀上 使用 支持度和置信度 框架可能會(huì)產(chǎn)生一些不正確的規(guī)則 只憑支持度和置信度閾值未必總能找出符合實(shí)際的規(guī)則 例 歌曲A 歌曲C為小眾歌曲 歌曲B為口水歌 共有10萬(wàn)個(gè)用戶 有200個(gè)人聽過(guò)歌曲A 這200個(gè)人里面有60個(gè)聽過(guò)口水歌B 有40個(gè)人聽過(guò)歌曲C 聽過(guò)歌曲C的人數(shù)是300 聽過(guò)口水歌B的人為50000 Confidence A B 0 3 Confidence A C 0 2 但是10W人里面有5W聽過(guò)歌曲B 有一半的用戶都喜歡歌曲B 但聽過(guò)歌曲A的人里面只有30 的人喜歡歌曲B 聽過(guò)歌曲A的人不喜歡歌曲B 貌似A和B更相關(guān) 矛盾的規(guī)則 如何評(píng)價(jià) 關(guān)聯(lián)規(guī)則價(jià)值衡量 提升度 Lift A B Confidence A B Support B 引入提升度Lift 以度量此規(guī)則是否可用 它描述的是 相對(duì)于不用規(guī)則 使用規(guī)則可以提高多少 Lift A B Confidence A B Support B 0 3 0 5 0 6Lift A C Confidence A C 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ī)則來(lái)進(jìn)行推薦 還不如不推薦 讓顧客自行選擇好了 Confidence A B 0 3Confidence A C 0 2Support B 0 5Support C 300 100000 關(guān)聯(lián)規(guī)則的價(jià)值衡量 主觀上 一個(gè)規(guī)則的有用與否最終取決于用戶的感覺 只有用戶才能決定規(guī)則的有效性 可