數(shù)據(jù)挖掘基于約束的挖掘-文庫吧資料
2024-09-08 09:03本頁面
【正文】 聯(lián)規(guī)則 (維詞重復(fù) ) age(X,‖1925‖) ? buys(X, ―popcorn‖) ? buys(X, ―coke‖) ? 類別屬性 ? 有限個值 , 值之間無順序關(guān)系 ? 數(shù)量屬性 ? 數(shù)字的，值之間隱含了順序關(guān)系 挖掘多維關(guān)聯(lián)的技術(shù) ? 搜索頻繁 k維詞集合： ? 如 : {age, occupation, buys} 是一個 3維詞集合。 ? 例子 ? 奶制品 ? 白面包 [support = 8%, confidence = 70%] ? 酸奶 ? 白面包 [support = 2%, confidence = 72%] ? 酸奶占 奶制品 25% ? 我們稱第一個規(guī)則是第二個規(guī)則的祖先 ? 參考規(guī)則的祖先，如果他的支持度與我們“預(yù)期”的支持度近似的話，我們就說這條規(guī)則是冗余的。 黃面包 [6%, 50%]. ? 多層關(guān)聯(lián)規(guī)則的變種 1 支持度不變 : 在各層之間使用統(tǒng)一的支持度 ? + 一個最小支持度閾值 . 如果一個項集的父項集不具有最小支持度，那他本身也不可能滿足最小支持度。 ? 使用緊縮的數(shù)據(jù)結(jié)構(gòu) ? 避免重復(fù)數(shù)據(jù)庫掃描 ? 基本操作是計數(shù)和建立 FPtree 樹 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 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 關(guān)聯(lián)規(guī)則結(jié)果顯示 (Table Form ) 關(guān)聯(lián)規(guī)則可視化 Using Plane Graph 關(guān)聯(lián)規(guī)則可視化 Using Rule Graph 第 6章：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則 ? 關(guān)聯(lián)規(guī)則挖掘 ? ? ? 聯(lián)規(guī)則 ? ? ? 多層關(guān)聯(lián)規(guī)則 ? 項通常具有層次 ? 底層的項通常支持度也低 ? 某些特定層的規(guī)則可能更有意義 ? 交易數(shù)據(jù)庫可以按照維或?qū)泳幋a ? 可以進行共享的多維挖掘 食品 面包 牛奶 脫脂奶 光明 統(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 }挖掘多層關(guān)聯(lián)規(guī)則 ? 自上而下，深度優(yōu)先的方法： ? 先找高層的“強”規(guī)則： 牛奶 174。 步驟 1: 建立 FPtree （ 159頁圖 68） ? 從 FPtree的頭表開始 ? 按照每個頻繁項的連接遍歷 FPtree ? 列出能夠到達此項的所有前綴路徑，得到條件模式庫 步驟 2:建立條件 FPtree進行挖掘（ 159頁圖 69） ? 對每個模式庫 ? 計算庫中每個項的支持度 ? 用模式庫中的頻繁項建立 FPtree 為什么 頻繁集增長 速度快？ ? 我們的性能研究顯示 ? FPgrowth 比 Apriori快一個數(shù)量級 , 同樣也比 treeprojection 快。 : 在添加一個新的候選集之前，先估計一下是不是他的所有子集都是頻繁的。(157頁圖 56) : 使用小的支持度 +完整性驗證方法。 : 一個項集要想在整個數(shù)據(jù)庫中是頻繁的，那么他至少在數(shù)據(jù)庫的一個分割上是頻繁的。 Apriori算法 — 例子 T ID Ite m s100 1 3 4200 2 3 5300 1 2 3 5400 2 5數(shù)據(jù)庫 D ite m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 4 } 1{ 5 } 3i te m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 5 } 3掃描 D C1 L1 item set{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}ite m s et s up{ 1 2} 1{ 1 3} 2{ 1 5} 1{ 2 3} 2{ 2 5} 3{ 3 5} 2ite m s e t s u p{ 1 3 } 2{ 2 3 } 2{ 2 5 } 3{ 3 5 } 2L2 C2 C2 掃描 D C3 L3 item set{2 3 5}掃描 D ite m s e t s u p{ 2 3 5 } 2如何生成候選集 ? 假定 Lk1 中的項按順序排列 ? 第一步 : 自連接 Lk1 insert into Ck select , , …, k1, from Lk1 p, Lk1 q where =, …, k2=, ? 第二步 : 修剪 For all itemsets c in Ck do For all (k1)subsets s of c do if (s is not in Lk1) then delete c from Ck ? 計算支持度為什么會成為一個問題？ ? 候選集的個數(shù)非常巨大 ? 一筆交易可能包含多個候選集 生成候選集的例子 ? L3={abc, abd, acd, ace, bcd} ? 自連接 : L3*L3 ? abc 和 abd 得到 abcd ? acd 和 ace 得到 acde ? 修剪 : ? ade 不在 L3中，刪除 acde ? C4={abcd} 提高 Apriori效率的方法 Hash的項集計數(shù) : 若 k項集在 hashtree的路徑上的一個計數(shù)值低于閾值，那他本身也不可能是頻繁的。 k++) do begin Ck = candidates generated from Lk1。 for (k = 2。 Y ? Z 具有最小支持度和可信度 ? 支持度 , s, 一次交易中包含{X 、 Y 、 Z}的 可能性 ? 置信度 , c, 包含 {X 、 Y}的交易中也包含 Z的 條件概率
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1