數(shù)據(jù)挖掘從大數(shù)據(jù)庫中挖掘關聯(lián)規(guī)則(編輯修改稿)
2024-10-06 09:03 本頁面
【文章內容簡介】 ? 不會打破交易中的任何模式 ? 包含了序列模式挖掘所需的全部信息 ? 緊密 ? 去除不相關信息 —不包含非頻繁項 ? 支持度降序排列 : 支持度高的項在 FPtree中共享的機會也高 ? 決不會比原數(shù)據(jù)庫大（如果不計算樹節(jié)點的額外開銷 ) ? 例子 : 對于 Connect4 數(shù)據(jù)庫 ,壓縮率超過 100 2020116 數(shù)據(jù)挖掘：概念和技術 20 用 FPtree挖掘頻繁集 ? 基本思想 (分而治之 ) ? 用 FPtree地歸增長頻繁集 ? 方法 ? 對每個項，生成它的 條件模式庫 , 然后是它的 條件 FPtree ? 對每個新生成的條件 FPtree， 重復這個步驟 ? 直到結果 FPtree為 空 , 或只含 維一的一個路徑 (此路徑的每個子路徑對應的相集都是頻繁集 ) 2020116 數(shù)據(jù)挖掘：概念和技術 21 挖掘 FPtree的主要步驟 1) 為 FPtree中的每個節(jié)點生成條件模式庫 2) 用條件模式庫構造對應的條件 FPtree 3) 遞歸構造條件 FPtrees 同時增長其包含的頻繁集 ? 如果條件 FPtree直包含一個路徑，則直接生成所包含的頻繁集。 2020116 數(shù)據(jù)挖掘：概念和技術 22 步驟 1: 從 FPtree 到條件模式庫 ? 從 FPtree的頭表開始 ? 按照每個頻繁項的連接遍歷 FPtree ? 列出能夠到達此項的所有前綴路徑，得到條件模式庫 條件模式庫 item cond. pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1 {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 頭表 Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 2020116 數(shù)據(jù)挖掘：概念和技術 23 FPtree支持條件模式庫構造的屬性 ? 節(jié)點褳接 ? 任何包含 ai, 的可能頻繁集，都可以從 FPtree頭表中的 ai沿著 ai 的節(jié)點鏈接得到 ? 前綴路徑 ? 要計算路徑 P 中包含節(jié)點 ai 的頻繁集，只要考察到達 ai 的路徑前綴即可，且其支持度等于節(jié)點 ai 的支持度 2020116 數(shù)據(jù)挖掘：概念和技術 24 步驟 2: 建立條件 FPtree ? 對每個模式庫 ? 計算庫中每個項的支持度 ? 用模式庫中的頻繁項建立 FPtree m條件模是庫 : fca:2, fcab:1 {} f:3 c:3 a:3 mconditional FPtree All frequent patterns concerning m m, fm, cm, am, fcm, fam, cam, fcam ? ? {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 頭表 Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 2020116 數(shù)據(jù)挖掘：概念和技術 25 通過建立條件模式庫得到頻繁集 Empty Empty f {(f:3)}|c {(f:3)} c {(f:3, c:3)}|a {(fc:3)} a Empty {(fca:1), (f:1), (c:1)} b {(f:3, c:3, a:3)}|m {(fca:2), (fcab:1)} m {(c:3)}|p {(fcam:2), (cb:1)} p 條件 FPtree 條件模式庫 項 2020116 數(shù)據(jù)挖掘：概念和技術 26 第 3步 : 遞歸挖掘條件 FPtree {} f:3 c:3 a:3 m條件 FPtree ―am‖的條件模式庫 : (fc:3) {} f:3 c:3 am條件 FPtree ―cm‖的條件模式 : (f:3) {} f:3 cm條件 FPtree ―cam‖條件模式庫 : (f:3) {} f:3 cam條件 FPtree 2020116 數(shù)據(jù)挖掘：概念和技術 28 特例 : FPtree 中的 唯一 前綴路徑 ? 假定一個 (條件 ) FPtree T 又一個共享唯一前綴路徑 P ? 挖掘可分解為如下兩個步驟 ? 用一個節(jié)點代替此前綴路徑 P ? 分別計算這兩個部分的結果 ? a2:n2 a3:n3 a1:n1 {} b1:m1 C1:k1 C2:k2 C3:k3 b1:m1 C1:k1 C2:k2 C3:k3 r1 + a2:n2 a3:n3 a1:n1 {} r1 = 2020116 數(shù)據(jù)挖掘：概念和技術 29 頻繁集增長的原理 ? 模式增長的特征 ? 令 ? 為 DB的一個頻繁集， B 為 ? 的條件模式庫， ? 是 B中的一個項，要使 ? ? ? 是 DB中的頻繁集，當且僅當 ? 是 B 的頻繁項 . ? ―abcdef ‖ 是頻繁集 ,當且僅當 ? ―abcde ‖ 是頻繁集 , 且 ? ―f ‖ 在包含 “ abcde ‖的事務中是頻繁的。 2020116 數(shù)據(jù)挖掘：概念和技術 30 為什么 頻繁集增長 速度快？ ? 我們的性能研究顯示 ? FPgrowth 比 Apriori快一個數(shù)量級 , 同樣也比 treeprojection 快。 ? 原因 ? 不生成候選集，不用候選測試。 ? 使用緊縮的數(shù)據(jù)結構 ? 避免重復數(shù)據(jù)庫掃描 ? 基本操作是計數(shù)和建立 FPtree 樹 2020116 數(shù)據(jù)挖掘：概念和技術 31 FPgrowth vs. Apriori: 相對于支持度的擴
環(huán)評公示相關推薦
鄂ICP備17016276號-1