數(shù)據(jù)挖掘從大數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則-文庫(kù)吧
2025-07-28 09:03 本頁(yè)面
【正文】 andidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end return ?k Lk。 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 11 Apriori算法 — 例子 T ID Ite m s100 1 3 4200 2 3 5300 1 2 3 5400 2 5數(shù)據(jù)庫(kù) 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 } 22020116 數(shù)據(jù)挖掘：概念和技術(shù) 12 如何生成候選集 ? 假定 Lk1 中的項(xiàng)按順序排列 ? 第一步 : 自連接 Lk1 insert into Ck select , , …, k1, from Lk1 p, Lk1 q where =, …, k2=, ? 第二步 : 修剪 forall itemsets c in Ck do forall (k1)subsets s of c do if (s is not in Lk1) then delete c from Ck 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 13 如何計(jì)算候選集的支持度 ? 計(jì)算支持度為什么會(huì)成為一個(gè)問題 ？ ? 候選集的個(gè)數(shù)非常巨大 ? 一筆交易可能包含多個(gè)候選集 ? 方法 : ? 用 hashtree 存放候選集 ? 樹的 葉子節(jié)點(diǎn) of存放項(xiàng)集的列表和支持度 ? 內(nèi)部節(jié)點(diǎn) 是一個(gè) hash表 ? Subset 函數(shù) : 找到包含在一筆交易中的所有候選集 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 14 生成候選集的例子 ? L3={abc, abd, acd, ace, bcd} ? 自連接 : L3*L3 ? abc 和 abd 得到 abcd ? acd 和 ace 得到 acde ? 修剪 : ? ade 不在 L3中，刪除 acde ? C4={abcd} 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 15 提高 Apriori效率的方法 ? 基于 Hash的項(xiàng)集計(jì)數(shù) : 如果一個(gè) k項(xiàng)集在 hashtree的路徑上的一個(gè)計(jì)數(shù)值低于閾值，那他本身也不可能是頻繁的。 ? 減少交易記錄 : 不包含任何頻繁 k項(xiàng)集的交易也不可能包含任何大于k的頻繁集 ? 分割 : 一個(gè)項(xiàng)集要想在整個(gè)數(shù)據(jù)庫(kù)中是頻繁的，那么他至少在數(shù)據(jù)庫(kù)的一個(gè)分割上是頻繁的。 ? 采樣 : 在給定數(shù)據(jù)的子集上挖掘，使用小的支持度 +完整性驗(yàn)證方法 ? 動(dòng)態(tài)項(xiàng)集計(jì)數(shù) : 在添加一個(gè)新的候選集之前，先估計(jì)一下是不是他的所有子集都是頻繁的。 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 16 Apriori 夠快了嗎 ? — 性能瓶頸 ? Apriori算法的核心 : ? 用頻繁的 (k – 1)項(xiàng)集生成 候選 的頻繁 k項(xiàng)集 ? 用數(shù)據(jù)庫(kù)掃描和模式匹配計(jì)算候選集的支持度 ? Apriori 的瓶頸 : 候選集生成 ? 巨大的候選集 : ? 104 個(gè)頻繁 1項(xiàng)集要生成 107 個(gè)候選 2項(xiàng)集 ? 要找尺寸為 100的頻繁模式，如 {a1, a2, …, a100}, 你必須先產(chǎn)生 2100 ? 1030 個(gè)候選集 ? 多次掃描數(shù)據(jù)庫(kù) ： ? 如果最長(zhǎng)的模式是 n的話，則需要 (n +1 ) 次數(shù)據(jù)庫(kù)掃描 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 17 挖掘頻繁集 不用生成候選集 ? 用 FrequentPattern tree (FPtree) 結(jié)構(gòu)壓縮數(shù)據(jù)庫(kù) , ? 高度濃縮，同時(shí)對(duì)頻繁集的挖掘又完備的 ? 避免代價(jià)較高的數(shù)據(jù)庫(kù)掃描 ? 開發(fā)一種高效的基于 FPtree的頻繁集挖掘算法 ? 采用分而治之的方法學(xué)：分解數(shù)據(jù)挖掘任務(wù)為小任務(wù) ? 避免生成關(guān)聯(lián)規(guī)則 : 只使用部分?jǐn)?shù)據(jù)庫(kù) ! 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 18 用交易數(shù)據(jù)庫(kù)建立 FPtree {} 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 最小支持度 = TID Items bought (ordered) frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o} {f, b} 400 {b, c, k, s, p} {c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 步驟 : 1. 掃描數(shù)據(jù)庫(kù)一次，得到頻繁1項(xiàng)集 2. 把項(xiàng)按支持度遞減排序 3. 再一次掃描數(shù)據(jù)庫(kù)，建立 FPtree 2020116 數(shù)據(jù)挖掘：概念和技術(shù) 19 FPtree 結(jié)構(gòu)的好處 ? 完備 :
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1