數(shù)據(jù)挖掘基于約束的挖掘(存儲版)
【正文】 nce threshold=50% Lives(C,_,”Pudong”)^Sales(C,”Census_CD”,_)^Sales(C,”MS/Office”,_)=Sales(C,”MS/SQLSever”,_) [%,65%] 約束的分類 ? 單調(diào)性約束 (monotone constraint) ? 反單調(diào)性約束 (antimonotone constraint) ? 可轉(zhuǎn)變的約束 (convertibale constraint) ? 簡潔性約束 (succinct constraint) ? 不可轉(zhuǎn)變的約束 (nonconvertibale constraint) 約束的有關(guān)概念 ? 項目集： I={i1,i2,……,im}, ? 交易： T=tid,It ? 模式 S是項目集的子集， S={ij1,ij2,…,i jk} ? 模式 S包含與 T,T=tid,It,iff S=It。= (5)group by C, (6)having sum(=100)amp。 Han, SSD’95). 第 6章：從大數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則 ? 關(guān)聯(lián)規(guī)則挖掘 ? ? ? 聯(lián)規(guī)則 ? ? ? 多維關(guān)聯(lián)規(guī)則： 概念 ? 單維規(guī)則： buys(X, ―milk‖) ? buys(X, ―bread‖) ? 多維規(guī)則： 2個以上維 /謂詞 ? 維間關(guān)聯(lián)規(guī)則 (維詞 不重復 ) age(X,‖1925‖) ? occupation(X,―student‖) ? buys(X,―coke‖) ? 混合維關(guān)聯(lián)規(guī)則 (維詞重復 ) 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維詞集合。 步驟 1: 建立 FPtree （ 159頁圖 68） ? 從 FPtree的頭表開始 ? 按照每個頻繁項的連接遍歷 FPtree ? 列出能夠到達此項的所有前綴路徑，得到條件模式庫 步驟 2:建立條件 FPtree進行挖掘（ 159頁圖 69） ? 對每個模式庫 ? 計算庫中每個項的支持度 ? 用模式庫中的頻繁項建立 FPtree 為什么 頻繁集增長 速度快？ ? 我們的性能研究顯示 ? FPgrowth 比 Apriori快一個數(shù)量級 , 同樣也比 treeprojection 快。 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ù)值低于閾值，那他本身也不可能是頻繁的。 ? 應用： ? 購物籃分析、交叉銷售、產(chǎn)品目錄設計、 lossleader analysis、聚集、分類等。 b:3。=1999 amp。amp。 f:3 Transaction_ID Items In Transaction 100 a,e,c,d,f 200 a,b 300 a,e,c,f 400 a,e,b,c,d,f 500 a,e,b,d 頻繁數(shù)據(jù)集應用舉例 (續(xù) ) ? 將排序后的每次交易的項目列表的 前綴項目 映射到條件數(shù)據(jù)庫 TDB|f。 ? 偽代碼 : Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = { frequent items}。 兩次掃描數(shù)據(jù)。 面包 [20%, 60%]. ? 再找他們底層的“弱”規(guī)則： 酸奶 174。 3. 基于距離的關(guān)聯(lián)規(guī)則 ? 用數(shù)據(jù)點之間的距離動態(tài)的離散化 數(shù)值屬性的靜態(tài)離散化 ? 在挖掘之前用概念層次先離散化 ? 數(shù)值被替換為區(qū)間范圍 ? 關(guān)系數(shù)據(jù)庫中，要找到所有頻繁 k維詞需要 k或k+1次表掃描。 S’是 S的子模式 (subpattern)且 S 是 S’的超模式 (superpattern)， if 有 S’=S. 約束的有關(guān)概念（續(xù)） ? 定義約束 : C是作用于項目集 I的冪集(powerset)上的謂詞 ,C(S)=True/False。amp。 數(shù)據(jù)挖掘查詢的逐步精化 ? 為什么要逐步精化 ? 挖掘操作的代價可能高或低，結(jié)果可能過細致或粗糙 ? 在速度和質(zhì)量之間折衷：逐步精化 ? 超集覆蓋特征： ? 預存儲所有正面答案 —允許進一步正確性驗證，而不必驗證已經(jīng)錯誤的 ? 2或多步挖掘： ? 先執(zhí)行粗糙的、容易的操作 (超集覆蓋 ) ? 然后在減少后的候選集上進行計算量大的算法 (Koperski amp。 Apriori 夠快了嗎 ? — 性能瓶
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1