數(shù)據(jù)挖掘基于約束的挖掘(編輯修改稿)
2024-10-06 09:03 本頁面
【文章內(nèi)容簡介】 挖掘：路線圖 ? 布爾 vs. 定量 關(guān)聯(lián) (基于規(guī)則中所處理數(shù)據(jù)的值類型 ) ? buys(x, ―SQLServer‖) ^ buys(x, ―DMBook‖) ???buys(x, ―DBMiner‖) [%, 60%] ? age(x, ―30..39‖) ^ ine(x, ―42..48K‖) ???buys(x, ―PC‖) [1%, 75%] ? 單維 vs. 多維 關(guān)聯(lián) (基于規(guī)則中涉及的數(shù)據(jù)維 )(例子同上 ) ? 單層 vs. 多層 分析 (基于規(guī)則集所涉及的抽象層 ) ? 那個品種牌子的啤酒與那個牌子的尿布有關(guān)系 ? ? 各種擴展 ? 相關(guān)性、因果分析 ?關(guān)聯(lián)并不一定意味著相關(guān)或因果 ? 最大模式和閉合項集 第 6章：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則 ? 關(guān)聯(lián)規(guī)則挖掘 ? ? ? 聯(lián)規(guī)則 ? ? ? 關(guān)聯(lián)規(guī)則挖掘 —一個例子 對于 A ? C： support = support({A 、 C}) = 50% confidence = support({A 、 C})/support({A}) = % Apriori的基本思想 : 頻繁項集的任何子集也一定是頻繁的 交易 ID 購買商品2020 A ,B ,C1000 A ,C4000 A ,D5000 B ,E ,F頻繁項集 支持度{ A } 75%{ B } 50%{ C} 50%{ A ,C} 50%最小值尺度 50% 最小可信度 50% 關(guān)鍵步驟：挖掘頻繁集 ? 頻繁集 :是指滿足最小支持度的項目集合 ? 頻繁集的子集也一定是頻繁的 ? 如 , 如果 {AB} 是頻繁集，則 {A} {B} 也一定是頻繁集 ? 從 1到 k（ k頻繁集）遞歸查找頻繁集 ? 用得到的頻繁集生成關(guān)聯(lián)規(guī)則 Apriori算法 ? 連接 : 用 Lk1自連接得到候選 k項集 Ck ? 修剪 : 一個 k項集，如果他的一個 k1項集（他的子集 ）不是頻繁的，那他本身也不可能是頻繁的。 ? 偽代碼 : Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = { frequent items}。 for (k = 2。 Lk1 !=?。 k++) do begin Ck = candidates generated from Lk1。 for each transaction t in database do increment the count of all candidates in Ck that are contained in t Lk = candidates in Ck with min_support end return ?k Lk。 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ù)值低于閾值，那他本身也不可能是頻繁的。(157頁圖 66) : 不包含任何頻繁 k項集的交易也不可能包含任何大于 k的頻繁集，下一步計算時刪除這些記錄。 : 一個項集要想在整個數(shù)據(jù)庫中是頻繁的，那么他至少在數(shù)據(jù)庫的一個分割上是頻繁的。 兩次掃描數(shù)據(jù)。(157頁圖 56) : 使用小的支持度 +完整性驗證方法。在小的抽樣集上找到局部頻繁項集，然后在全部數(shù)據(jù)集找頻繁項集。 : 在添加一個新的候選集之前，先估計一下是不是他的所有子集都是頻繁的。 Apriori 夠快了嗎 ? — 性能瓶頸 ? Apriori算法的核心 : ? 用頻繁的 (k – 1)項集生成 候選 的頻繁 k項集 ? 用數(shù)據(jù)庫掃描和模式匹配計算候選集的支持度 ? Apriori 的瓶頸 : 候選集生成 ? 巨大的候選集 : ? 104 個頻繁 1項集要生成 107 個候選 2項集 ? 要找尺寸為 100的頻繁模式，如 {a1, a2, …, a 100}, 你必須先產(chǎn)生 2100 ? 1030 個候選集 ? 多次掃描數(shù)據(jù)庫： ? 如果最長的模式是 n的話，則需要 (n +1 ) 次數(shù)據(jù)庫掃描 挖掘頻繁集 不用生成候選集 ? 頻繁模式增長 (FP增長 )用 FrequentPattern tree (FPtree) 結(jié)構(gòu)壓縮數(shù)據(jù)庫 , ? 高度濃縮，同時對頻繁集的挖掘又完備的 ? 避免代價較高的數(shù)據(jù)庫掃描 開發(fā)一種高效的基于 FPtree的頻繁集挖掘算法 ? 采用分而治之的方法學(xué)：分解數(shù)據(jù)挖掘任務(wù)為小任務(wù) ? 避免生成關(guān)聯(lián)規(guī)則 : 分別挖掘條件數(shù)據(jù)庫 用 FPtree挖掘頻繁集 ? 基本思想 (分而治之 ) ? 用 FPtree地歸增長頻繁集 ? 方法 ? 對每個項，生成它的 條件模式庫 , 然后是它的 條件 FPtree ? 對每個新生成的條件 FPtree，重復(fù)這個步驟 ? 直到結(jié)果 FPtree為 空 , 或只含
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1