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

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

2、元素中的項是無序的,我們可以用字典序列出它們. 是 的子序列給定 支持度閾值 min_sup =2, 是一個 序列模式SIDsequence102030403共五十四頁序列(xli)模式挖掘的挑戰(zhàn)大量的 可能的序列模式隱藏在數(shù)據(jù)庫中挖掘算法應當 可能的話, 找出滿足最小支持度閾值的模式的完全集高度 有效的, 可伸縮的, 僅涉及不多次數(shù)的數(shù)據(jù)庫掃描可以與各種用戶指定(zhdng)的約束結合4共五十四頁序列(xli)模式挖掘研究概念引進和最初的 類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共五十四頁序列(xli)模式的基本性質: Apriori基本性質: Apriori (Agrawal & Sirkant94) 如果(rgu)序列 S 不是頻繁的 則 S 的任何超序列都不是頻繁的例, 是非頻繁的 和 也是非頻繁的5040302010SequenceSeq. ID給定 支持度閾值 min_sup =2 6

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

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

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

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

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

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

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

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

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

14、影可以壓縮投影數(shù)據(jù)庫的數(shù)量和大小物理投影 vs. 偽投影 當投影數(shù)據(jù)庫可以放在內存時, 偽投影可能降低投影的效果并發(fā)投影 vs. 劃分投影劃分投影可以避免磁盤空間爆炸通過兩級投影擴展基于(jy)長度為2的序列模式劃分搜索空間只形成投影數(shù)據(jù)庫, 并在兩級投影數(shù)據(jù)庫上進行遞歸挖掘26共五十四頁兩級投影（S矩陣(j zhn)）加速掃描數(shù)據(jù)庫兩次，構建s-矩陣所有長度為2的序列模式(msh)都在 S-矩陣中發(fā)現(xiàn)(逐個檢查)27共五十四頁使用(shyng)S-矩陣逐對檢查SID序列10203040SDB長度(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次所有長度為2的序列模式 都在 S-矩陣中發(fā)現(xiàn)28共五十四頁挖掘(wju) -投影數(shù)據(jù)庫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ù)庫局部長度為1的序列模式:, , a0c(1, 0, 1)1(_c)(, 2, )(, 1, )ac(_c)S-矩陣不希望形成 (_ac), 因此不必對它計數(shù).導致模式 長度為1的序列模式:4, :4, :4, :3, :3, :329共五十四頁三路 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)!(因為:1小于2)從 -投影數(shù)據(jù)庫排除 d使用 Apriori 啟發(fā)式方法在投影數(shù)據(jù)庫中剪去項類Apriori算法的優(yōu)點30共五十四頁兩級投影(tuyng)的好處每次可以(ky)發(fā)現(xiàn)更多的模式較少的投影在上例中, 有 53 個模式.53 個逐級投影22 個兩級投影31共五十四頁PrefixSpan 比 GSP 和 FreeSpan快32共五十四頁PrefixSpan的進一步演變(ynbin)閉的

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

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

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

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

22、onContinuous QueryStream QueryProcessorResultsMultiple streamsDSMS40共五十四頁DSMSScratch StoreDSMSInput streamsRegisterQueryStreamedResultStoredResultArchiveStoredRelations41共五十四頁目前(mqin)的DSMS項目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共五十四頁應用領域新的應用領域 以連續(xù)的、有序的“流”的形式輸入數(shù)據(jù)網(wǎng)絡監(jiān)聽和流量控制(Network monitoring and traffic engineering)電話通信(Telecom call records)網(wǎng)絡安全 (Network security )金融領域(Financial Application)工業(yè)生產(Manufacturing Processes)網(wǎng)頁(wn y)日志與點擊流(Web logs and clickstreams)43共

25、五十四頁應用(yngyng)實例網(wǎng)絡安全 數(shù)據(jù)包流，用戶的會話信息查詢: URL 過濾，異常監(jiān)測，網(wǎng)絡攻擊和病毒來源金融領域(ln y)交易數(shù)據(jù)流， 股票行情， 消息反饋查詢: 套匯可能性分析，模式44共五十四頁現(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共五十四頁流數(shù)據(jù)