數(shù)據(jù)挖掘基于約束的挖掘(存儲(chǔ)版)
【正文】 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) ? 簡(jiǎn)潔性約束 (succinct constraint) ? 不可轉(zhuǎn)變的約束 (nonconvertibale constraint) 約束的有關(guān)概念 ? 項(xiàng)目集： I={i1,i2,……,im}, ? 交易： T=tid,It ? 模式 S是項(xiàng)目集的子集， 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ù)庫(kù)中挖掘關(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個(gè)以上維 /謂詞 ? 維間關(guān)聯(lián)規(guī)則 (維詞 不重復(fù) ) age(X,‖1925‖) ? occupation(X,―student‖) ? buys(X,―coke‖) ? 混合維關(guān)聯(lián)規(guī)則 (維詞重復(fù) ) age(X,‖1925‖) ? buys(X, ―popcorn‖) ? buys(X, ―coke‖) ? 類別屬性 ? 有限個(gè)值 , 值之間無順序關(guān)系 ? 數(shù)量屬性 ? 數(shù)字的，值之間隱含了順序關(guān)系 挖掘多維關(guān)聯(lián)的技術(shù) ? 搜索頻繁 k維詞集合： ? 如 : {age, occupation, buys} 是一個(gè) 3維詞集合。 步驟 1: 建立 FPtree （ 159頁(yè)圖 68） ? 從 FPtree的頭表開始 ? 按照每個(gè)頻繁項(xiàng)的連接遍歷 FPtree ? 列出能夠到達(dá)此項(xiàng)的所有前綴路徑，得到條件模式庫(kù) 步驟 2:建立條件 FPtree進(jìn)行挖掘（ 159頁(yè)圖 69） ? 對(duì)每個(gè)模式庫(kù) ? 計(jì)算庫(kù)中每個(gè)項(xiàng)的支持度 ? 用模式庫(kù)中的頻繁項(xiàng)建立 FPtree 為什么 頻繁集增長(zhǎng) 速度快？ ? 我們的性能研究顯示 ? FPgrowth 比 Apriori快一個(gè)數(shù)量級(jí) , 同樣也比 treeprojection 快。 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 } 2如何生成候選集 ? 假定 Lk1 中的項(xiàng)按順序排列 ? 第一步 : 自連接 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 ? 計(jì)算支持度為什么會(huì)成為一個(gè)問題？ ? 候選集的個(gè)數(shù)非常巨大 ? 一筆交易可能包含多個(gè)候選集 生成候選集的例子 ? L3={abc, abd, acd, ace, bcd} ? 自連接 : L3*L3 ? abc 和 abd 得到 abcd ? acd 和 ace 得到 acde ? 修剪 : ? ade 不在 L3中，刪除 acde ? C4={abcd} 提高 Apriori效率的方法 Hash的項(xiàng)集計(jì)數(shù) : 若 k項(xiàng)集在 hashtree的路徑上的一個(gè)計(jì)數(shù)值低于閾值，那他本身也不可能是頻繁的。 ? 應(yīng)用： ? 購(gòu)物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計(jì)、 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ù)集應(yīng)用舉例 (續(xù) ) ? 將排序后的每次交易的項(xiàng)目列表的 前綴項(xiàng)目 映射到條件數(shù)據(jù)庫(kù) 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ù)點(diǎn)之間的距離動(dòng)態(tài)的離散化 數(shù)值屬性的靜態(tài)離散化 ? 在挖掘之前用概念層次先離散化 ? 數(shù)值被替換為區(qū)間范圍 ? 關(guān)系數(shù)據(jù)庫(kù)中，要找到所有頻繁 k維詞需要 k或k+1次表掃描。 S’是 S的子模式 (subpattern)且 S 是 S’的超模式 (superpattern)， if 有 S’=S. 約束的有關(guān)概念（續(xù)） ? 定義約束 : C是作用于項(xiàng)目集 I的冪集(powerset)上的謂詞 ,C(S)=True/False。amp。 數(shù)據(jù)挖掘查詢的逐步精化 ? 為什么要逐步精化 ? 挖掘操作的代價(jià)可能高或低，結(jié)果可能過細(xì)致或粗糙 ? 在速度和質(zhì)量之間折衷：逐步精化 ? 超集覆蓋特征： ? 預(yù)存儲(chǔ)所有正面答案 —允許進(jìn)一步正確性驗(yàn)證，而不必驗(yàn)證已經(jīng)錯(cuò)誤的 ? 2或多步挖掘： ? 先執(zhí)行粗糙的、容易的操作 (超集覆蓋 ) ? 然后在減少后的候選集上進(jìn)行計(jì)算量大的算法 (Koperski amp。 Apriori 夠快了嗎 ? — 性能瓶
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1