【文章內(nèi)容簡介】
遞歸構造條件 FPtrees 同時增長其包含的頻繁集 ? 如果條件 FPtree直包含一個路徑,則直接生成所包含的頻繁集。 2021/6/14 數(shù)據(jù)挖掘:概念和技術 19 步驟 1: 建立 FPtree ( 159頁圖 68) ? 從 FPtree的頭表開始 ? 按照每個頻繁項的連接遍歷 FPtree ? 列出能夠到達此項的所有前綴路徑,得到條件模式庫 步驟 2:建立條件 FPtree進行挖掘( 159頁圖 69) ? 對每個模式庫 ? 計算庫中每個項的支持度 ? 用模式庫中的頻繁項建立 FPtree 2021/6/14 數(shù)據(jù)挖掘:概念和技術 20 為什么 頻繁集增長 速度快? ? 我們的性能研究顯示 ? FPgrowth 比 Apriori快一個數(shù)量級 , 同樣也比 treeprojection 快。 ? 原因 ? 不生成候選集,不用候選測試。 ? 使用緊縮的數(shù)據(jù)結構 ? 避免重復數(shù)據(jù)庫掃描 ? 基本操作是計數(shù)和建立 FPtree 樹 2021/6/14 數(shù)據(jù)挖掘:概念和技術 21 FPgrowth vs. Apriori: 相對于支持度的擴展性 01020304050607080901000 0 . 5 1 1 . 5 2 2 . 5 3S u p p o r t t h r e s h o l d ( % )Run time(sec.)D 1 F P g r o w t h r u n t i m eD 1 A p r i o r i r u n t i m eData set T25I20D10K 2021/6/14 數(shù)據(jù)挖掘:概念和技術 22 FPgrowth vs. TreeProjection:相對于支持度的擴展性 0204060801001201400 0 . 5 1 1 . 5 2S u p p o r t t h r e s h o l d ( % )Runtime (sec.)D 2 F P g r o w t hD 2 T r e e P r o j e c t i o nData set T25I20D100K 2021/6/14 數(shù)據(jù)挖掘:概念和技術 23 關聯(lián)規(guī)則結果顯示 (Table Form ) 2021/6/14 數(shù)據(jù)挖掘:概念和技術 24 關聯(lián)規(guī)則可視化 Using Plane Graph 2021/6/14 數(shù)據(jù)挖掘:概念和技術 25 關聯(lián)規(guī)則可視化 Using Rule Graph 2021/6/14 數(shù)據(jù)挖掘:概念和技術 26 第 6章:從大數(shù)據(jù)庫中挖掘關聯(lián)規(guī)則 ? 關聯(lián)規(guī)則挖掘 ? ? ? ? ? ? 2021/6/14 數(shù)據(jù)挖掘:概念和技術 27 多層關聯(lián)規(guī)則 ? 項通常具有層次 ? 底層的項通常支持度也低 ? 某些特定層的規(guī)則可能更有意義 ? 交易數(shù)據(jù)庫可以按照維或層編碼 ? 可以進行共享的多維挖掘 食品 面包 牛奶 脫脂奶 光明 統(tǒng)一 酸奶 白 黃 T I D I t e m sT1 { 1 1 1 , 1 2 1 , 2 1 1 , 2 2 1 }T2 { 1 1 1 , 2 1 1 , 2 2 2 , 3 2 3 }T3 { 1 1 2 , 1 2 2 , 2 2 1 , 4 1 1 }T4 { 1 1 1 , 1 2 1 }T5 { 1 1 1 , 1 2 2 , 2 1 1 , 2 2 1 , 4 1 3 }2021/6/14 數(shù)據(jù)挖掘:概念和技術 28 挖掘多層關聯(lián)規(guī)則 ? 自上而下,深度優(yōu)先的方法: ? 先找高層的“強”規(guī)則: 牛奶 174。 面包 [20%, 60%]. ? 再找他們底層的“弱”規(guī)則: 酸奶 174。 黃面包 [6%, 50%]. ? 多層關聯(lián)規(guī)則的變種 1 支持度不變 : 在各層之間使用統(tǒng)一的支持度 ? + 一個最小支持度閾值 . 如果一個項集的父項集不具有最小支持度,那他本身也不可能滿足最小支持度。 ? – 底層項不會成為頻繁集,如果支持度 ? 太高 ? 丟失底層關聯(lián)規(guī)則 ? 太低 ? 生成太多的高層關聯(lián)規(guī)則 2 支持度遞減 : 隨著層次的降低支持度遞減 2021/6/14 數(shù)據(jù)挖掘:概念和技術 29 多層關聯(lián)規(guī)則 : 支持度不變 vs. 支持度遞減 3層次交叉單項過濾 : 4層次交叉 K項過濾 : ? 4種搜索策略: ? 層與層獨立 ? 用 k項集跨層過濾 ? 用項跨層過濾 ? 用項進行可控跨層過濾 2021/6/14 數(shù)據(jù)挖掘:概念和技術 30 支持度不變 支持度不變多層挖掘 牛奶 [support = 10%] 酸奶 [support = 6%] 脫脂奶 [support = 4%] 層 1 min_sup = 5% 層 2 min_sup = 5% 2021/6/14 數(shù)據(jù)挖掘:概念和技術 31 支持度遞減 支持度遞減多層挖掘 酸奶 [suppor