數(shù)據(jù)挖掘-CHAPTER8-序列數(shù)據(jù)挖掘

1、1Chapter 8. 序列(xli)數(shù)據(jù)挖掘1共五十四頁(yè)序列(xli)數(shù)據(jù)庫(kù)和序列(xli)模式挖掘事務(wù)數(shù)據(jù)庫(kù)vs. 序列數(shù)據(jù)庫(kù)頻繁模式 vs. (頻繁) 序列模式序列模式挖掘的應(yīng)用顧客購(gòu)物序列: 在3個(gè)月內(nèi), 先買計(jì)算機(jī), 然后買 CD-ROM, 再后買數(shù)字照相機(jī).醫(yī)療處治(chzh), 自然災(zāi)害 (例如, 地震), 科學(xué) 和 工程進(jìn)度, 股票 和市場(chǎng)等.電話呼叫模式, Web日志 點(diǎn)擊流DNA 序列和基因結(jié)構(gòu)2共五十四頁(yè)什么是序列(xli)模式挖掘?給定一個(gè)(y )序列的集合, 找出所有的 頻繁 子序列序列：事件的有序列表一個(gè) 序列數(shù)據(jù)庫(kù) 一個(gè) 序列 : 一個(gè)元素可能包含一個(gè)項(xiàng)集.在一個(gè)

2、元素中的項(xiàng)是無序的,我們可以用字典序列出它們. 是 的子序列給定 支持度閾值 min_sup =2, 是一個(gè) 序列模式SIDsequence102030403共五十四頁(yè)序列(xli)模式挖掘的挑戰(zhàn)大量的 可能的序列模式隱藏在數(shù)據(jù)庫(kù)中挖掘算法應(yīng)當(dāng) 可能的話, 找出滿足最小支持度閾值的模式的完全集高度 有效的, 可伸縮的, 僅涉及不多次數(shù)的數(shù)據(jù)庫(kù)掃描可以與各種用戶指定(zhdng)的約束結(jié)合4共五十四頁(yè)序列(xli)模式挖掘研究概念引進(jìn)和最初的 類Apriori算法R. Agrawal & R. Srikant. “Mining sequential patterns,” ICDE95GSP一種基

3、于Apriori的, 有影響的算法 (IBM Almaden開發(fā)(kif)R. Srikant & R. Agrawal. “Mining sequential patterns: Generalizations and performance improvements,” EDBT96由序列模式到 episodes (類Apriori+ 約束)H. Mannila, H. Toivonen & A.I. Verkamo. “Discovery of frequent episodes in event sequences,” Data Mining and Knowledge Discove

4、ry, 1997挖掘具有約束的序列模式M.N. Garofalakis, R. Rastogi, K. Shim: SPIRIT: Sequential Pattern Mining with Regular Expression Constraints. VLDB 19995共五十四頁(yè)序列(xli)模式的基本性質(zhì): Apriori基本性質(zhì): Apriori (Agrawal & Sirkant94) 如果(rgu)序列 S 不是頻繁的 則 S 的任何超序列都不是頻繁的例, 是非頻繁的 和 也是非頻繁的5040302010SequenceSeq. ID給定 支持度閾值 min_sup =2 6

5、共五十四頁(yè)GSP一種拓廣的序列(xli)模式挖掘算法GSP (Generalized Sequential Pattern) 挖掘算法Agrawal 和 Srikant提出, EDBT96方法概述初始, 數(shù)據(jù)庫(kù)中的每個(gè)項(xiàng)都是長(zhǎng)度為1的候選(hu xun)for each level (即, 長(zhǎng)度為k的序列) do掃描數(shù)據(jù)庫(kù)對(duì)每個(gè)候選序列收集支持度計(jì)數(shù)使用Apriori , 由長(zhǎng)度為k 的頻繁序列產(chǎn)生長(zhǎng)度為(k+1)的候選序列repeat until 找不到頻繁序列或候選主要優(yōu)點(diǎn): 根據(jù)Apriori對(duì)后選剪枝7共五十四頁(yè)找長(zhǎng)度為1的序列(xli)模式使用一個(gè)例子(l zi)考查 GSP初始候選

6、: 所有單元素序列, , , , , , , 掃描數(shù)據(jù)庫(kù)一次, 對(duì)候選進(jìn)行支持度計(jì)數(shù)5040302010SequenceSeq. IDmin_sup =2 CandSup354332118共五十四頁(yè)產(chǎn)生長(zhǎng)度(chngd)為2的候選51 個(gè)長(zhǎng)度為2的候選: 上下兩個(gè)(lin )表格的組合不使用 Apriori 性質(zhì),8*8+8*7/2=92 個(gè)候選Apriori 剪裁掉 44.57% 的候選9共五十四頁(yè)找出長(zhǎng)度(chngd)為2的序列模式再掃描數(shù)據(jù)庫(kù)一次, 對(duì)每個(gè)長(zhǎng)度為2的候選(hu xun)收集支持度計(jì)數(shù)有 19 長(zhǎng)度為2 的候選, 滿足最小支持度閾值 它們是長(zhǎng)度為2的序列模式10共五十四頁(yè)產(chǎn)

7、生長(zhǎng)度為3的候選(hu xun)并找出長(zhǎng)度為3的模式產(chǎn)生長(zhǎng)度為3的候選 長(zhǎng)度為2的序列模式自連接根據(jù) Apriori 性質(zhì), 和 都是長(zhǎng)度為2的序列模式 是一個(gè)長(zhǎng)度為3的候選, 和 都是長(zhǎng)度為2的序列模式 是一個(gè)長(zhǎng)度為3的候選產(chǎn)生46 個(gè)候選找出長(zhǎng)度為3的序列模式再次掃描數(shù)據(jù)庫(kù), 收集(shuj)候選的支持度計(jì)數(shù)46個(gè)候選中有19個(gè)滿足支持度計(jì)數(shù)11共五十四頁(yè)GSP 挖掘(wju)過程 第1次掃描: 8 候選. 6 個(gè)長(zhǎng)度為1 的序列模式第2次掃描: 51 候選. 19 個(gè)長(zhǎng)度為2 的序列模式. 10 候選不在 DB第3次掃描: 46 個(gè)候選. 19 長(zhǎng)度為3的序列模式. 20 個(gè)候選不在DB

8、第4次掃描: 8 個(gè)候選. 6 個(gè)長(zhǎng)度為4的序列模式. 第5次掃描: 1 個(gè)候選. 1 長(zhǎng)度為5 的序列模式候選不滿足 支持度閾值候選不在DB中5040302010SequenceSeq. IDmin_sup =2 12共五十四頁(yè)GSP 算法(sun f)取形如 的模式作為長(zhǎng)度為1的候選(hu xun)掃描數(shù)據(jù)庫(kù)1次, 找出 F1, 長(zhǎng)度為1的序列模式的集合令 k=1; while Fk is not empty do由Fk形成Ck+1, 長(zhǎng)度為(k+1) 的候選的集合;如果 Ck+1 非空, 掃描一次數(shù)據(jù)庫(kù), 找出 Fk+1, 長(zhǎng)度為(k+1) 序列模式的集合令 k=k+1;13共五十四頁(yè)G

9、SP的瓶頸(pn jn)可能產(chǎn)生(chnshng)的候選的集合可能很大1,000 長(zhǎng)度為1的頻繁序列可以產(chǎn)生 長(zhǎng)度為2的候選!挖掘中多次掃描數(shù)據(jù)庫(kù)實(shí)際挑戰(zhàn): 挖掘長(zhǎng)序列模式指數(shù)個(gè)數(shù)短候選一個(gè)長(zhǎng)度為100的序列模式 需要 1030 個(gè)候選序列!14共五十四頁(yè)The SPADE AlgorithmSPADE (Sequential PAttern Discovery using Equivalent Class) developed by Zaki 2001垂直數(shù)據(jù)格式的序列模式挖掘方法序列數(shù)據(jù)庫(kù)轉(zhuǎn)化為垂直數(shù)據(jù)格式Item: 序列模式挖掘： 模式一次增長(zhǎng)(zngzhng)一個(gè)項(xiàng)基于Apriori性

10、質(zhì)，連接兩個(gè)k-1子序列為k序列候選連接時(shí)必須保證涉及事件的時(shí)間序15共五十四頁(yè)The SPADE Algorithm16共五十四頁(yè)P(yáng)refixSpan: 前綴投影的序列(xli)模式增長(zhǎng)PrefixSpan：不需要產(chǎn)生候選的方法基于投影(tuyng)，但僅基于前綴的投影(tuyng): 較少的投影, 并且序列收縮較快基本思想先找出頻繁項(xiàng)，然后產(chǎn)生投影數(shù)據(jù)庫(kù)的集合每個(gè)投影數(shù)據(jù)庫(kù)關(guān)聯(lián)一個(gè)頻繁項(xiàng)每個(gè)(投影)數(shù)據(jù)單獨(dú)(以遞歸方式)挖掘。算法構(gòu)造前綴模式，與后綴模式相聯(lián)得到頻繁模式，從而避免產(chǎn)生候選17共五十四頁(yè)前綴和后綴(huzhu) (投影), , 和 是序列 的前綴(qinzhu)給定序列 前綴

11、后綴 (基于前綴的投影)18共五十四頁(yè)通過前綴投影挖掘序列(xli)模式步驟 1: 找出長(zhǎng)度為1的序列(xli)模式, , , , , 步驟 2: 劃分搜索空間. 序列模式的完全集可以劃分成6個(gè)子集合 :具有前綴 的模式;具有前綴 的模式;具有前綴 的模式SID序列1020304019共五十四頁(yè)找出具有(jyu)前綴 的序列模式只需要考慮關(guān)于 的投影-投影數(shù)據(jù)庫(kù) : , , , 找出所有長(zhǎng)度為2的序列模式. 含有前綴 : , , , , , 進(jìn)一步劃分成6個(gè)子集合(jh)具有前綴 ;具有前綴 SID序列1020304020共五十四頁(yè)P(yáng)refixSpan的完全性SID序列10203040SDB，

12、最小支持(zhch)度2長(zhǎng)度(chngd)為1的序列模式, , , , , -投影數(shù)據(jù)庫(kù)-投影數(shù)據(jù)庫(kù)的1頻繁項(xiàng)是a:2,b:4,_b:2, c:4,d:2, f:2.長(zhǎng)度為2的序列模式, , , , 具有前綴 具有前綴 -proj. db-proj. db具有前綴 -projected database具有前綴 具有前綴 , , 21共五十四頁(yè)P(yáng)refixSpan的有效性不需要(xyo)產(chǎn)生候選序列投影數(shù)據(jù)庫(kù)不斷收縮PrefixSpan的主要開銷: 構(gòu)造投影數(shù)據(jù)庫(kù)可以用兩級(jí)( bi-level) 投影改進(jìn)22共五十四頁(yè)通過(tnggu)偽投影加速PrefixSpan的主要開銷: 投影序列(xl

13、i)的后綴經(jīng)常 在遞歸投影數(shù)據(jù)庫(kù)中重復(fù)地出現(xiàn)當(dāng) (投影) 數(shù)據(jù)庫(kù)不能放在內(nèi)存時(shí), 使用指針形成投影指向序列后綴的偏移s=s|: ( , 2)s|: ( , 4)23共五十四頁(yè)偽投影(tuyng) vs. 物理投影偽投影避免物理地拷貝后綴當(dāng)數(shù)據(jù)庫(kù)可以放在內(nèi)存時(shí), 運(yùn)行時(shí)間和空間是有效的然而, 當(dāng)數(shù)據(jù)庫(kù)不能放在內(nèi)存時(shí), 它不太有效基于磁盤(c pn)的隨即訪問開銷很大建議的方法:集成物理投影和偽投影當(dāng)數(shù)據(jù)集可以放在內(nèi)存時(shí), 切換成偽投影24共五十四頁(yè)偽投影(tuyng)的影響25共五十四頁(yè)P(yáng)refixSpan的優(yōu)化技術(shù)(jsh)PrefixSpan的優(yōu)化技術(shù)單級(jí) vs.兩級(jí)投影具有3路檢驗(yàn)的兩級(jí)投

14、影可以壓縮投影數(shù)據(jù)庫(kù)的數(shù)量和大小物理投影 vs. 偽投影 當(dāng)投影數(shù)據(jù)庫(kù)可以放在內(nèi)存時(shí), 偽投影可能降低投影的效果并發(fā)投影 vs. 劃分投影劃分投影可以避免磁盤空間爆炸通過兩級(jí)投影擴(kuò)展基于(jy)長(zhǎng)度為2的序列模式劃分搜索空間只形成投影數(shù)據(jù)庫(kù), 并在兩級(jí)投影數(shù)據(jù)庫(kù)上進(jìn)行遞歸挖掘26共五十四頁(yè)兩級(jí)投影（S矩陣(j zhn)）加速掃描數(shù)據(jù)庫(kù)兩次，構(gòu)建s-矩陣所有長(zhǎng)度為2的序列模式(msh)都在 S-矩陣中發(fā)現(xiàn)(逐個(gè)檢查)27共五十四頁(yè)使用(shyng)S-矩陣逐對(duì)檢查SID序列10203040SDB長(zhǎng)度(chngd)為1的序列模式:4, :4, :4, :3, :3, :3a2b(4, 2, 2)1

15、c(4, 2, 1)(3, 3, 2)3d(2, 1, 1)(2, 2, 0)(1, 3, 0)0e(1, 2, 1)(1, 2, 0)(1, 2, 0)(1, 1, 0)0f(2, 1, 1)(2, 2, 0)(1, 2, 1)(1, 1, 1)(2, 0, 1)1abcdefS-矩陣 出現(xiàn)2次 出現(xiàn)4次 出現(xiàn)2次 出現(xiàn)1次所有長(zhǎng)度為2的序列模式 都在 S-矩陣中發(fā)現(xiàn)28共五十四頁(yè)挖掘(wju) -投影數(shù)據(jù)庫(kù)SID序列10203040SDBa2b(4, 2, 2)1c(4, 2, 1)(3, 3, 2)3d(2, 1, 1)(2, 2, 0)(1, 3, 0)0e(1, 2, 1)(1, 2

16、, 0)(1, 2, 0)(1, 1, 0)0f(2, 1, 1)(2, 2, 0)(1, 2, 1)(1, 1, 1)(2, 0, 1)1abcdefS-矩陣(j zhn)-投影數(shù)據(jù)庫(kù)局部長(zhǎng)度為1的序列模式:, , a0c(1, 0, 1)1(_c)(, 2, )(, 1, )ac(_c)S-矩陣不希望形成 (_ac), 因此不必對(duì)它計(jì)數(shù).導(dǎo)致模式 長(zhǎng)度為1的序列模式:4, :4, :4, :3, :3, :329共五十四頁(yè)三路 Apriori 檢查(jinch)a2b(4, 2, 2)1c(4, 2, 1)(3, 3, 2)3d(2, 1, 1)(2, 2, 0)(1, 3, 0)0e(1

17、, 2, 1)(1, 2, 0)(1, 2, 0)(1, 1, 0)0f(2, 1, 1)(2, 2, 0)(1, 2, 1)(1, 1, 1)(2, 0, 1)1abcdeF 不可能是模式(msh)!(因?yàn)?1小于2)從 -投影數(shù)據(jù)庫(kù)排除 d使用 Apriori 啟發(fā)式方法在投影數(shù)據(jù)庫(kù)中剪去項(xiàng)類Apriori算法的優(yōu)點(diǎn)30共五十四頁(yè)兩級(jí)投影(tuyng)的好處每次可以(ky)發(fā)現(xiàn)更多的模式較少的投影在上例中, 有 53 個(gè)模式.53 個(gè)逐級(jí)投影22 個(gè)兩級(jí)投影31共五十四頁(yè)P(yáng)refixSpan 比 GSP 和 FreeSpan快32共五十四頁(yè)P(yáng)refixSpan的進(jìn)一步演變(ynbin)閉的

18、和最大的序列模式僅找出最有意義的 (最大的) 序列模式基于約束(yush)的序列模式增長(zhǎng)增加用戶指定的約束由序列模式到結(jié)構(gòu)化的模式除序列模式外, 在XML文檔中挖掘結(jié)構(gòu)化的模式33共五十四頁(yè)閉的和最大的序列(xli)模式閉的序列模式 是頻繁序列 s , 不存在s的 真超集, 與s具有相同的支持(zhch)讀計(jì)數(shù)最大序列模式 是序列模式 p 使得 p的任何真超模式都不是頻繁的閉的序列模式的優(yōu)點(diǎn), , min_sup = 1 有2100 序列模式, 但只有 2 是閉的最大序列模式有類似的優(yōu)點(diǎn)34共五十四頁(yè)挖掘(wju)閉的和最大的序列模式的方法PrefixSpan 或 FreeSpan 可以看作投

19、影引導(dǎo)的深度優(yōu)先搜索 為挖掘 最大序列模式, 不包含比已經(jīng)發(fā)現(xiàn)的序列模式更多東西的任何序列模式將從投影數(shù)據(jù)庫(kù)中刪除, , min_sup = 1 如果我們(w men)已經(jīng)發(fā)現(xiàn)一個(gè)最大序列模式 , 不在任何投影數(shù)據(jù)庫(kù)做投影類似的思想可以用于閉的序列模式35共五十四頁(yè)由序列(xli)模式到結(jié)構(gòu)化的模式集合(jh), 序列, 樹和其它結(jié)構(gòu)事務(wù)數(shù)據(jù)庫(kù): 項(xiàng)的集合 i1, i2, , im, 序列數(shù)據(jù)庫(kù): 集合的序列:, 序列的集合: , , , 樹的集合 (每個(gè)元素是一棵樹): t1, t2, , tn方法: 挖掘 XML 文檔中結(jié)構(gòu)化的模式36共五十四頁(yè)DNA 分析(fnx)和生物醫(yī)學(xué)數(shù)據(jù)挖掘相似

20、性搜索和 DNA 序列比較比較每個(gè)類頻繁出現(xiàn)的模式 (例如(lr), 疾病和健康)識(shí)別在各種疾病中起作用的基因模式關(guān)聯(lián)分析: 識(shí)別同時(shí)出現(xiàn)的基因序列大部分疾病不是由單個(gè)基因引發(fā)的, 而是由一起起作用的基因組引發(fā)的關(guān)聯(lián)分析可以幫助確定多半可能同時(shí)出現(xiàn)在目標(biāo)樣本中的基因類型路徑分析: 將基因與疾病的不同發(fā)展階段相聯(lián)系不同的基因可能在疾病的不同階段是活躍的針對(duì)不同階段, 分別開發(fā)治療藥物可視化工具和遺傳數(shù)據(jù)分析37共五十四頁(yè)流數(shù)據(jù)挖掘流數(shù)據(jù)頻繁模式挖掘簡(jiǎn)介流數(shù)據(jù)頻繁模式挖掘算法概念 一系列連續(xù)且有序的點(diǎn)組成的序列 x1, xi, , xn,稱為(chn wi)數(shù)據(jù)流；按照固定的次序，這些點(diǎn)只能被讀取

21、一次或者幾次特點(diǎn)大數(shù)據(jù)量，甚至無限頻繁的變化和快速的響應(yīng)線性掃描算法，查詢次數(shù)有限r(nóng)andom access is expensive38共五十四頁(yè)DBMS 與 DSMS持久的關(guān)系One-time queries隨機(jī)的訪問(fngwn)“無限”的磁盤空間當(dāng)前狀態(tài)有效相對(duì)較低的更新率很少“實(shí)時(shí)服務(wù)”假定數(shù)據(jù)精確無誤訪問策略由查詢處理器在數(shù)據(jù)庫(kù)設(shè)計(jì)時(shí)確定瞬間的流 連續(xù)的查詢(chxn)序列化的訪問有限的主存數(shù)據(jù)的到達(dá)順序是關(guān)鍵數(shù)據(jù)傳輸率未知實(shí)時(shí)響應(yīng)過時(shí)/模糊的數(shù)據(jù)變化的數(shù)據(jù)及數(shù)據(jù)量39共五十四頁(yè)Scratch Space(Main memory and/or Disk)User/Applicati

22、onContinuous QueryStream QueryProcessorResultsMultiple streamsDSMS40共五十四頁(yè)DSMSScratch StoreDSMSInput streamsRegisterQueryStreamedResultStoredResultArchiveStoredRelations41共五十四頁(yè)目前(mqin)的DSMS項(xiàng)目STREAM (Stanford): A general-purpose DSMSCougar (Cornell): sensorsAurora (Brown/MIT): sensor monitoring, dataf

23、lowHancock (AT&T): telecom streamsNiagara (OGI/Wisconsin): Internet XML databasesOpenCQ (Georgia Tech): triggers, incr. view maintenanceTapestry (Xerox): pub/sub content-based filteringTelegraph (Berkeley): adaptive engine for sensorsTradebot (): stock tickers & streamsTribeca (Bellcore): network mo

24、nitoringStreaminer (UIUC): new project for stream data mining42共五十四頁(yè)應(yīng)用領(lǐng)域新的應(yīng)用領(lǐng)域 以連續(xù)的、有序的“流”的形式輸入數(shù)據(jù)網(wǎng)絡(luò)監(jiān)聽和流量控制(Network monitoring and traffic engineering)電話通信(Telecom call records)網(wǎng)絡(luò)安全 (Network security )金融領(lǐng)域(Financial Application)工業(yè)生產(chǎn)(Manufacturing Processes)網(wǎng)頁(yè)(wn y)日志與點(diǎn)擊流(Web logs and clickstreams)43共

25、五十四頁(yè)應(yīng)用(yngyng)實(shí)例網(wǎng)絡(luò)安全 數(shù)據(jù)包流，用戶的會(huì)話信息查詢: URL 過濾，異常監(jiān)測(cè)，網(wǎng)絡(luò)攻擊和病毒來源金融領(lǐng)域(ln y)交易數(shù)據(jù)流， 股票行情， 消息反饋查詢: 套匯可能性分析，模式44共五十四頁(yè)現(xiàn)有的研究(ynji)方向流數(shù)據(jù)建模(Stream data model)STanford stREam datA Manager (STREAM)Data Stream Management System (DSMS)流檢索(jin su)/查詢建模(Stream query model)Continuous QueriesSliding windows流數(shù)據(jù)挖掘(Stream data mining)Clustering & summarization (Guha, Motwani et al.)Correlation of data streams (Gehrke et al.)Classification of stream data (Domingos et al.)45共五十四頁(yè)流數(shù)據(jù)