數(shù)據(jù)挖掘研究生課件第六章時(shí)間序列和序列模

第六章時(shí)間序列和序列模式挖掘

內(nèi)容提要時(shí)間序列及其應(yīng)用

時(shí)間序列預(yù)測(cè)的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時(shí)間序列相似性查找基于規(guī)范變換的查找方法序列挖掘及其基本方法AprioriAll

算法AprioriSome

算法GSP算法2023/2/31DataMining:ConceptsandTechniques時(shí)間序列及其應(yīng)用時(shí)間序列（TimeSeries）挖掘是數(shù)據(jù)挖掘中的一個(gè)重要研究分支，有著廣泛的應(yīng)用價(jià)值。近年來(lái)，時(shí)間序列挖掘在宏觀的經(jīng)濟(jì)預(yù)測(cè)、市場(chǎng)營(yíng)銷、客流量分析、太陽(yáng)黑子數(shù)、月降水量、河流流量、股票價(jià)格變動(dòng)等眾多領(lǐng)域得到應(yīng)用。事實(shí)上，社會(huì)、科學(xué)、經(jīng)濟(jì)、技術(shù)等領(lǐng)域中廣泛存在著大量的時(shí)間序列數(shù)據(jù)有待進(jìn)一步的分析和處理。時(shí)間序列數(shù)據(jù)挖掘通過(guò)研究信息的時(shí)間特性，深入洞悉事物進(jìn)化的機(jī)制，是獲得知識(shí)的有效途徑。2023/2/32DataMining:ConceptsandTechniques時(shí)間序列有關(guān)概念從統(tǒng)計(jì)意義上來(lái)講，所謂時(shí)間序列就是將某一指標(biāo)在不同時(shí)間上的不同數(shù)值，按照時(shí)間先后順序排列而成的數(shù)列。時(shí)間序列挖掘通過(guò)對(duì)過(guò)去歷史行為的客觀記錄分析，揭示其內(nèi)在規(guī)律，進(jìn)而完成預(yù)測(cè)未來(lái)行為等決策性工作。簡(jiǎn)言之，時(shí)間序列數(shù)據(jù)挖掘就是要從大量的時(shí)間序列數(shù)據(jù)中提取人們事先不知道的、但又是潛在有用的與時(shí)間屬性相關(guān)的信息和知識(shí)，并用于短期、中期或長(zhǎng)期預(yù)測(cè)，指導(dǎo)人們的社會(huì)、經(jīng)濟(jì)、軍事和生活等行為。從數(shù)學(xué)意義上來(lái)講，如果我們對(duì)某一過(guò)程中的某一變量進(jìn)行X(t)觀察測(cè)量，在一系列時(shí)刻t1，t2，…，tn（t為自變量，且t1<t2<…，<tn）得到的離散有序數(shù)集合Xt1，Xt2，…，Xtn稱為離散數(shù)字時(shí)間序列。設(shè)X(t)是一個(gè)隨機(jī)過(guò)程，Xti(i=1，2，…，n)稱為一次樣本實(shí)現(xiàn)，也就是一個(gè)時(shí)間序列。2023/2/33DataMining:ConceptsandTechniques時(shí)間序列有關(guān)概念時(shí)間序列的研究必須依據(jù)合適的理論和技術(shù)進(jìn)行，時(shí)間序列的多樣性表明其研究必須結(jié)合序列特點(diǎn)來(lái)找到合適的建模方法。一元時(shí)間序列：如某種商品的銷售量數(shù)列等，可以通過(guò)單變量隨即過(guò)程的觀察獲得規(guī)律性信息。多元時(shí)間序列。如包含氣溫、氣壓、雨量等在內(nèi)的天氣數(shù)據(jù)，通過(guò)多個(gè)變量描述變化規(guī)律。時(shí)間序列挖掘需要揭示各變量間相互依存關(guān)系的動(dòng)態(tài)規(guī)律性。離散型時(shí)間序列：如果某一序列中的每一個(gè)序列值所對(duì)應(yīng)的時(shí)間參數(shù)為間斷點(diǎn)，則該序列就是一個(gè)離散時(shí)間序列。連續(xù)型時(shí)間序列：如果某一序列中的每個(gè)序列值所對(duì)應(yīng)的時(shí)間參數(shù)為連續(xù)函數(shù)，則該序列就是一個(gè)連續(xù)時(shí)間序列。序列的分布規(guī)律：序列的統(tǒng)計(jì)特征可以表現(xiàn)平穩(wěn)或者有規(guī)律的震蕩，這樣的序列是分析的基礎(chǔ)點(diǎn)。此外如果序列按某類規(guī)律（如高斯型）的分布，那么序列的分析就有了理論根據(jù)。2023/2/34DataMining:ConceptsandTechniques第六章時(shí)間序列和序列模式挖掘

內(nèi)容提要時(shí)間序列及其應(yīng)用時(shí)間序列預(yù)測(cè)的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時(shí)間序列相似性查找基于規(guī)范變換的查找方法序列挖掘及其基本方法AprioriAll

算法AprioriSome

算法GSP算法2023/2/35DataMining:ConceptsandTechniques時(shí)間序列預(yù)測(cè)的常用方法時(shí)間序列分析的一個(gè)重要應(yīng)用是預(yù)測(cè)，即根據(jù)已知時(shí)間序列中數(shù)據(jù)的變化特征和趨勢(shì)，預(yù)測(cè)未來(lái)屬性值。為了對(duì)時(shí)間序列預(yù)測(cè)方法有一個(gè)比較全面的了解，我們首先對(duì)時(shí)間序列預(yù)測(cè)的主要方法加以歸納。確定性時(shí)間序列預(yù)測(cè)方法隨機(jī)時(shí)間序列預(yù)測(cè)方法

其他方法

2023/2/36DataMining:ConceptsandTechniques時(shí)間序列預(yù)測(cè)的常用方法(續(xù))確定性時(shí)間序列預(yù)測(cè)方法對(duì)于平穩(wěn)變化特征的時(shí)間序列來(lái)說(shuō)，假設(shè)未來(lái)行為與現(xiàn)在的行為有關(guān)，利用屬性現(xiàn)在的值預(yù)測(cè)將來(lái)的值是可行的。例如，要預(yù)測(cè)下周某種商品的銷售額，可以用最近一段時(shí)間的實(shí)際銷售量來(lái)建立預(yù)測(cè)模型。一種更科學(xué)的評(píng)價(jià)時(shí)間序列變動(dòng)的方法是將變化在多維上加以綜合考慮，把數(shù)據(jù)的變動(dòng)看成是長(zhǎng)期趨勢(shì)、季節(jié)變動(dòng)和隨機(jī)型變動(dòng)共同作用的結(jié)果。長(zhǎng)期趨勢(shì)：隨時(shí)間變化的、按照某種規(guī)則穩(wěn)步增長(zhǎng)、下降或保持在某一水平上的規(guī)律。季節(jié)變動(dòng)：在一定時(shí)間內(nèi)（如一年）的周期性變化規(guī)律（如冬季羽絨服銷售增加）。隨機(jī)型變動(dòng)：不可控的偶然因素等。設(shè)Tt表示長(zhǎng)期趨勢(shì)，St表示季節(jié)變動(dòng)趨勢(shì)項(xiàng)，Ct

表示循環(huán)變動(dòng)趨勢(shì)項(xiàng)，Rt表示隨機(jī)干擾項(xiàng)，yt

是觀測(cè)目標(biāo)的觀測(cè)記錄。則常見的確定性時(shí)間序列模型有以下幾種類型：加法模型：yt

=Tt+St+Ct+Rt。乘法模型：yt

=Tt·St·Ct·Rt?；旌夏Ｐ停簓t

=Tt·St+Rt

或yt

=St+Tt·Ct·Rt。2023/2/37DataMining:ConceptsandTechniques時(shí)間序列預(yù)測(cè)的常用方法(續(xù))隨機(jī)時(shí)間序列預(yù)測(cè)方法

通過(guò)建立隨機(jī)模型，對(duì)隨機(jī)時(shí)間序列進(jìn)行分析，可以預(yù)測(cè)未來(lái)值。若時(shí)間序列是平穩(wěn)的，可以用自回歸(AutoRegressive，簡(jiǎn)稱AR)模型、移動(dòng)回歸模型(MovingAverage，簡(jiǎn)稱MA)或自回歸移動(dòng)平均(AutoRegressiveMovingAverage，簡(jiǎn)稱ARMA)模型進(jìn)行分析預(yù)測(cè)。

其他方法

可用于時(shí)間序列預(yù)測(cè)的方法很多，其中比較成功的是神經(jīng)網(wǎng)絡(luò)。由于大量的時(shí)間序列是非平穩(wěn)的，因此特征參數(shù)和數(shù)據(jù)分布隨著時(shí)間的推移而變化。假如通過(guò)對(duì)某段歷史數(shù)據(jù)的訓(xùn)練，通過(guò)數(shù)學(xué)統(tǒng)計(jì)模型估計(jì)神經(jīng)網(wǎng)絡(luò)的各層權(quán)重參數(shù)初值，就可能建立神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型，用于時(shí)間序列的預(yù)測(cè)。2023/2/38DataMining:ConceptsandTechniques第六章時(shí)間序列和序列模式挖掘

內(nèi)容提要時(shí)間序列及其應(yīng)用時(shí)間序列預(yù)測(cè)的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時(shí)間序列相似性查找基于規(guī)范變換的查找方法序列挖掘及其基本方法AprioriAll

算法AprioriSome

算法GSP算法2023/2/39DataMining:ConceptsandTechniques基于ARMA模型的序列匹配方法ARMA模型（特別是其中的AR模型）是時(shí)序方法中最基本的、實(shí)際應(yīng)用最廣的時(shí)序模型。早在1927年，G.U.Yule就提出了AR模型，此后，AR模型逐步發(fā)展為ARMA模型、多維ARMA模型。ARMA通常被廣泛用于預(yù)測(cè)。由于ARMA模型是一個(gè)信息的凝聚器，可將系統(tǒng)的特性與系統(tǒng)狀態(tài)的所有信息凝聚在其中，因而它也可以用于時(shí)間序列的匹配。1．ARMA模型對(duì)于平穩(wěn)、正態(tài)、零均值的時(shí)序，若X在t時(shí)刻的取值不僅與其前n步的各個(gè)值有關(guān)，而且還與前m步的各個(gè)干擾有關(guān)（n，m=1，2，…），則按多元線性回歸的思想，可得到最一般的ARMA（n，m）模型：其中。2023/2/310DataMining:ConceptsandTechniques基于ARMA模型的序列匹配方法(續(xù))2．AR模型AR（n）模型是ARMA（n，m）模型的一個(gè)特例。在上面ARMA（n，m）模型表達(dá)中，當(dāng)時(shí)，有其中。由于此時(shí)模型中沒有滑動(dòng)平均部分，所以稱為n階自回歸模型，記為AR（n）。3．MA模型MA（m）模型是ARMA（n，m）模型的另一個(gè)特例。在上面ARMA（n，m）模型表達(dá)中，當(dāng)時(shí)，有其中。由于模型中沒有自回歸部分，所以稱為m階滑動(dòng)平均（MovingAverage）模型，記為MA（m）。2023/2/311DataMining:ConceptsandTechniques建立AR模型建立AR模型的最常用方法是最小二乘法。具體方法如下：對(duì)于AR（n）模型，有，其中，即可以用以下線性方程組表示： ， ，

……， ?；蛘邔懗扇缦戮仃囆问剑? ，其中

根據(jù)多元線性回歸理論，參數(shù)矩陣的最小二乘估計(jì)為：。，。

，，，2023/2/312DataMining:ConceptsandTechniques構(gòu)造判別函數(shù)

根據(jù)上面的模型，我們可以獲得待測(cè)序列的參數(shù)模型，同樣我們也可以得到序列數(shù)據(jù)庫(kù)中的其他序列Yi的參數(shù)模型。和都是n維向量，故均可視為n維空間上的點(diǎn)，從而序列的相似性問(wèn)題就歸結(jié)為n維空間Rn中的距離問(wèn)題。因此，我們下面簡(jiǎn)單介紹幾種基于距離的判別函數(shù)。1．Euclide

2．殘差偏移距離判別其中是待檢序列的協(xié)方差矩陣，N表示待檢序列的長(zhǎng)度。3．Mahalanobis距離判別其中是參考序列的協(xié)方差矩陣。4．Mann距離判別

其中，為待檢序列的協(xié)方差矩陣，為待測(cè)時(shí)序的方差。，。

，，2023/2/313DataMining:ConceptsandTechniques第六章時(shí)間序列和序列模式挖掘

內(nèi)容提要時(shí)間序列及其應(yīng)用時(shí)間序列預(yù)測(cè)的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時(shí)間序列相似性查找基于規(guī)范變換的查找方法序列挖掘及其基本方法AprioriAll

算法AprioriSome

算法GSP算法2023/2/314DataMining:ConceptsandTechniques基于離散傅立葉變換的時(shí)間序列相似性查找為了方便討論，我們首先給出一些符號(hào)來(lái)表示序列及序列的相似性：表示一個(gè)序列；Len（X）表示序列X的長(zhǎng)度；First（X）表示序列X的第一個(gè)元素；Last（X）表示序列X的最后一個(gè)元素；表示X在i時(shí)刻的取值，；序列上元素之間的“<”關(guān)系，在序列X上，如果i<j，那么X[i]<X[j]；本文用表示X的子序列，如果序列X有k個(gè)子序列，則把這些子序列分別表示為。子序列間的<關(guān)系，為X的子序列，如果，則稱。子序列重疊（Overlap），假定XS1，XS2為X的兩個(gè)子序列，如果或成立，則XS1與XS2重疊。2023/2/315DataMining:ConceptsandTechniques基于離散傅立葉變換的時(shí)間序列相似性查找一般地，相似性匹配可分為兩類：完全匹配（WholeMatching）。給定N個(gè)序列和一個(gè)查詢序列X，這些序列有相同的長(zhǎng)度，如果存在，那么我們稱完全匹配。子序列匹配（SubsequenceMatching）。給定N個(gè)具有任意長(zhǎng)度的序列和一個(gè)查詢序列X以及參數(shù)。子序列匹配就是在上找到某個(gè)子序列，使這個(gè)子序列與X之間的距離小于等于。2023/2/316DataMining:ConceptsandTechniques完全匹配所謂完全匹配必須保證被查找的序列與給出的序列有相同的長(zhǎng)度。因此，與子序列匹配相比，工作就相對(duì)簡(jiǎn)單一些。1．特征提取給定一個(gè)時(shí)間序列，對(duì)X進(jìn)行離散傅立葉變換，得到,這里，X與xt代表時(shí)域信息，而與代表頻域信息，，為傅立葉系數(shù)。2．首次篩選根據(jù)Parseval的理論，時(shí)域能量譜函數(shù)與頻域能量譜函數(shù)相同，得到2023/2/317DataMining:ConceptsandTechniques完全匹配(續(xù))按照Parseval的理論，如下式子也應(yīng)該成立：對(duì)大多數(shù)序列來(lái)說(shuō)，能量集中在傅立葉變換后的前幾個(gè)系數(shù)，也就是說(shuō)一個(gè)信號(hào)的高頻部分相對(duì)來(lái)說(shuō)并不重要。因此我們只取前面?zhèn)€系數(shù)，即因此，這樣就濾掉一大批與給定序列的距離大于的序列。3．最終篩選計(jì)算每個(gè)首次被選中的序列與給定序列在時(shí)域空間的歐氏距離，如果兩個(gè)序列的歐氏距離小于或等于，則接受該序列。2023/2/318DataMining:ConceptsandTechniques第六章時(shí)間序列和序列模式挖掘

內(nèi)容提要時(shí)間序列及其應(yīng)用時(shí)間序列預(yù)測(cè)的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時(shí)間序列相似性查找基于規(guī)范變換的查找方法

序列挖掘及其基本方法AprioriAll

算法AprioriSome

算法GSP算法2023/2/319DataMining:ConceptsandTechniques基于規(guī)范變換的查找方法

圖6-3

序列X與Y

圖6-4

去掉Gap后的序列X與Y

圖6-5

偏移變換后的序列X與Y

圖6-6

幅度縮放后的序列X與Y2023/2/320DataMining:ConceptsandTechniques基本概念定義6-1

如果序列所包含的不相互重疊的子序列和與Y所包含的不相互重疊的子序列滿足如下3個(gè)條件，可以認(rèn)為與是-similar：（1）對(duì)任意的都成立；（2）存在一些比例因子和一些偏移使得下式成立：

其中“”表示兩個(gè)子序列相似，表示對(duì)子序列以為比例因子進(jìn)行縮放，按照進(jìn)行偏移變換。（3）給定，下式成立這個(gè)定義意味著如果序列X與Y匹配的長(zhǎng)度之和與這兩個(gè)序列的長(zhǎng)度之和的比值不小于，則認(rèn)為序列X與Y是-similar。這樣事先給定的閾值，就找到一個(gè)序列相似的評(píng)價(jià)函數(shù)。當(dāng)被比較的序列X與Y的長(zhǎng)度非常懸殊，我們可以用如下函數(shù)來(lái)評(píng)價(jià)相似度：。2023/2/321DataMining:ConceptsandTechniques基于規(guī)范變換的查找方法

Agrawal把X與Y的相似性比較問(wèn)題分為三個(gè)子問(wèn)題：原子序列匹配；窗口縫合；子序列排序。1．原子序列匹配與基于離散傅立葉變換的時(shí)間序列查找方法相同，原子序列匹配（AtomicMatching）也采用了滑動(dòng)窗口技術(shù)。根據(jù)用戶事先給定的一個(gè)（通常為5~20），將序列映射為若干長(zhǎng)度為的窗口，然后對(duì)這些窗口進(jìn)行幅度縮放與偏移變換。我們首先討論窗口中點(diǎn)的標(biāo)準(zhǔn)化問(wèn)題。通過(guò)下面的轉(zhuǎn)換，可以將窗口內(nèi)不規(guī)范的點(diǎn)轉(zhuǎn)換成標(biāo)準(zhǔn)點(diǎn)：其中表示窗口中第i個(gè)點(diǎn)的值，、分別表示窗口內(nèi)所有點(diǎn)的最大值與最小值。通過(guò)上面的公式使得窗口內(nèi)的每個(gè)點(diǎn)的值落在（-1，+1）之間。把這種標(biāo)準(zhǔn)化后的窗口稱為原子。2023/2/322DataMining:ConceptsandTechniques基于規(guī)范變換的查找方法(續(xù))2．窗口縫合窗口縫合（WindowStitching）即子序列匹配，其主要任務(wù)是將相似的原子連接起來(lái)形成比較長(zhǎng)的彼此相似的子序列。分別為X與Y上m個(gè)標(biāo)準(zhǔn)化后的原子，縫合使它們形成一對(duì)相似的子序列的條件如下：（1）對(duì)于任意的i都有相似；（2）對(duì)于任何j>i，；（3）對(duì)任何i>1，如果不與重疊，且與之間的Gap小于等于，同時(shí)Y也滿足這個(gè)條件；如果與重疊，重疊長(zhǎng)度為d，與也重疊且重疊長(zhǎng)度也為d。（4）X上的每個(gè)窗口進(jìn)行標(biāo)準(zhǔn)化時(shí)所用的比例因子大致相同，Y上的每個(gè)窗口進(jìn)行標(biāo)準(zhǔn)化時(shí)所用的比例因子也大致相同。2023/2/323DataMining:ConceptsandTechniques基于規(guī)范變換的查找方法(續(xù))3．子序列排序通過(guò)對(duì)窗口縫合得到一些相似的子序列，再對(duì)這些子序列排序（SubsequenceOrdering），則可以找到兩個(gè)彼此匹配的序列。子序列排序的主要任務(wù)是從沒有重疊的子序列匹配中找出匹配得最長(zhǎng)的那些序列。如果把所有的相似的原子對(duì)看作圖論中的頂點(diǎn)，兩個(gè)窗口的縫合看作兩個(gè)頂點(diǎn)之間的邊的話，那么從起點(diǎn)到終點(diǎn)有多條路經(jīng)，子序列排序就是尋找最長(zhǎng)路徑。2023/2/324DataMining:ConceptsandTechniques第六章時(shí)間序列和序列模式挖掘

內(nèi)容提要時(shí)間序列及其應(yīng)用時(shí)間序列預(yù)測(cè)的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時(shí)間序列相似性查找基于規(guī)范變換的查找方法序列挖掘及其基本方法AprioriAll

算法AprioriSome

算法GSP算法2023/2/325DataMining:ConceptsandTechniques序列挖掘序列挖掘或稱序列模式挖掘，是指從序列數(shù)據(jù)庫(kù)中發(fā)現(xiàn)蘊(yùn)涵的序列模式。時(shí)間序列分析和序列模式挖掘有許多相似之處，在應(yīng)用范疇、技術(shù)方法等方面也有很大的重合度。但是，序列挖掘一般是指相對(duì)時(shí)間或者其他順序出現(xiàn)的序列的高頻率子序列的發(fā)現(xiàn)，典型的應(yīng)用還是限于離散型的序列。序列模式挖掘最早是由Agrawal等人提出的，它的最初動(dòng)機(jī)是針對(duì)帶有交易時(shí)間屬性的交易數(shù)據(jù)庫(kù)中發(fā)現(xiàn)頻繁項(xiàng)目序列以發(fā)現(xiàn)某一時(shí)間段內(nèi)客戶的購(gòu)買活動(dòng)規(guī)律。近年來(lái)序列模式挖掘已經(jīng)成為數(shù)據(jù)挖掘的一個(gè)重要方面，其應(yīng)用范圍也不局限于交易數(shù)據(jù)庫(kù)，在DNA分析等尖端科學(xué)研究領(lǐng)域、Web訪問(wèn)等新型應(yīng)用數(shù)據(jù)源等眾多方面得到針對(duì)性研究。2023/2/326DataMining:ConceptsandTechniques序列挖掘—基本概念定義6-3一個(gè)序列（Sequence）是項(xiàng)集的有序表,記為α=α1→α2→?→αn，其中每個(gè)αi是一個(gè)項(xiàng)集（Itemset）。一個(gè)序列的長(zhǎng)度（Length）是它所包含的項(xiàng)集。具有k長(zhǎng)度的序列稱為k-序列。定義6-4

設(shè)序列α=α1→α2→?→αn，序列β=β1→β2→?→βm

。若存在整數(shù)i1<i2<?<in，使得，則稱序列α是序列β的子序列，或序列β包含序列α。在一組序列中,如果某序列α不包含其他任何序列中，則稱α是該組中最長(zhǎng)序列(Maximalsequence)。定義6-5給定序列S，序列數(shù)據(jù)庫(kù)DT,序列S的支持度（Support）是指S在DT中相對(duì)于整個(gè)數(shù)據(jù)庫(kù)元組而言所包含S的元組出現(xiàn)的百分比。支持度大于最小支持度(min-sup)的k-序列,稱為DT上的頻繁k-序列。2023/2/327DataMining:ConceptsandTechniques序列挖掘—數(shù)據(jù)源的形式表6-1帶交易時(shí)間的交易數(shù)據(jù)源示例客戶號(hào)（Cust_id）交易時(shí)間（Tran_time）物品（Item）11June25’99June30’993090222June10’99June15’99June20’9910，203040，60，703June25’9930，50，70444June25’99June30’99July25’993040，70905June12’9990表6-2顧客序列表示例客戶號(hào)（Cust_id）顧客序列（CustomerSequence）1<（30）（90）>2<（10，20）（30）（40，60，70）>3<（30，50，70）>4<（30）（40，70）（(90)>5<（90）>帶交易時(shí)間的交易數(shù)據(jù)庫(kù)的典型形式是包含客戶號(hào)（Customer-id）、交易時(shí)間（Transaction-Time）以及在交易中購(gòu)買的項(xiàng)（Item）等的交易記錄表。表6-1給出了一個(gè)這樣數(shù)據(jù)表的示例。這樣的數(shù)據(jù)源需要進(jìn)行形式化的整理，其中一個(gè)理想的預(yù)處理方法就是轉(zhuǎn)換成顧客序列，即將一個(gè)顧客的交易按交易時(shí)間排序成項(xiàng)目序列。例如表6-2給出了表6-1對(duì)應(yīng)的所有顧客序列表。2023/2/328DataMining:ConceptsandTechniques序列挖掘—數(shù)據(jù)源的形式(續(xù))表6-2顧客序列表示例

操作系統(tǒng)及其系統(tǒng)進(jìn)程調(diào)用是評(píng)價(jià)系統(tǒng)安全性的一個(gè)重要方面。通過(guò)對(duì)正常調(diào)用序列的學(xué)習(xí)可以預(yù)測(cè)隨后發(fā)生的系統(tǒng)調(diào)用序列、發(fā)現(xiàn)異常的調(diào)用。因此序列挖掘是從系統(tǒng)調(diào)用等操作系統(tǒng)審計(jì)數(shù)據(jù)中發(fā)現(xiàn)有用模式的一個(gè)理想的技術(shù)。表6-3給出了一個(gè)系統(tǒng)調(diào)用數(shù)據(jù)表示意，它是利用數(shù)據(jù)挖掘技術(shù)進(jìn)行操作系統(tǒng)安全性審計(jì)的常用數(shù)據(jù)源。表6-3系統(tǒng)進(jìn)程調(diào)用數(shù)據(jù)示例進(jìn)程號(hào)（Pro_id）調(diào)用時(shí)間（Call_time）調(diào)用號(hào)（Call_id）74474410699106974410699-104：01：10：3004：01：10：3104：01：10：3204：01：10：3404：01：10：3504：01：10：3804：01：10：3904：01：10：4023144245816216表6-4系統(tǒng)調(diào)用序列數(shù)據(jù)表示例進(jìn)程號(hào)（Pro_id）調(diào)用序列（Call_sequence）74410699<（23，14，81）><（14，24，16）><（4，5，62）>2023/2/329DataMining:ConceptsandTechniques序列模式挖掘的一般步驟我們分五個(gè)具體階段來(lái)介紹基于上面概念發(fā)現(xiàn)序列模式的方法。這些步驟分別是排序階段、大項(xiàng)集階段、轉(zhuǎn)換階段、序列階段以及選最大階段。1.排序階段對(duì)數(shù)據(jù)庫(kù)進(jìn)行排序（Sort），排序的結(jié)果將原始的數(shù)據(jù)庫(kù)轉(zhuǎn)換成序列數(shù)據(jù)庫(kù)（比較實(shí)際可能需要其他的預(yù)處理手段來(lái)輔助進(jìn)行）。例如，上面介紹的交易數(shù)據(jù)庫(kù)，如果以客戶號(hào)（Cust_id）和交易時(shí)間（trans-time）進(jìn)行排序，那么在通過(guò)對(duì)同一客戶的事務(wù)進(jìn)行合并就可以得到對(duì)應(yīng)的序列數(shù)據(jù)庫(kù)。2.大項(xiàng)集階段這個(gè)階段要找出所有頻繁的項(xiàng)集（即大項(xiàng)集）組成的集合L。實(shí)際上，也同步得到所有大1-序列組成的集合，即{<l>|l

L}。在上面表6-2給出的顧客序列數(shù)據(jù)庫(kù)中，假設(shè)支持?jǐn)?shù)為2，則大項(xiàng)集分別是（30），（40），（70），（40，70）和（90）。實(shí)際操作中，經(jīng)常將大項(xiàng)集被映射成連續(xù)的整數(shù)。例如，上面得到的大項(xiàng)集映射成表6-6對(duì)應(yīng)的整數(shù)。當(dāng)然，這樣的映射純粹是為了處理的方便和高效。LargeItemsetsMappedTo（30）（40）（70）（40，70）（90）123452023/2/330DataMining:ConceptsandTechniques序列模式挖掘的一般步驟(續(xù))3.轉(zhuǎn)換階段在尋找序列模式的過(guò)程中，我們要不斷地進(jìn)行檢測(cè)一個(gè)給定的大序列集合是否包含于一個(gè)客戶序列中。表6-7給出了表6-2數(shù)據(jù)庫(kù)經(jīng)過(guò)轉(zhuǎn)換后的數(shù)據(jù)庫(kù)。比如，在對(duì)ID號(hào)為2的客戶序列進(jìn)行轉(zhuǎn)換的時(shí)候，交易（10，20）被剔除了，因?yàn)樗]有包含任何大項(xiàng)集；交易（40，60，70）則被大項(xiàng)集的集合{（40），（70），（40，70）}代替。4.序列階段利用轉(zhuǎn)換后的數(shù)據(jù)庫(kù)尋找頻繁的序列，即大序列（LargeSequence）。5.選最大階段在大序列集中找出最長(zhǎng)序列（MaximalSequences）。LargeItemsetsMappedTo（30）（40）（70）（40，70）（90）123452023/2/331DataMining:ConceptsandTechniques第六章時(shí)間序列和序列模式挖掘

內(nèi)容提要時(shí)間序列及其應(yīng)用時(shí)間序列預(yù)測(cè)的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時(shí)間序列相似性查找基于規(guī)范變換的查找方法序列挖掘及其基本方法AprioriAll

算法AprioriSome

算法GSP算法2023/2/332DataMining:ConceptsandTechniquesAprioriAll算法AprioriAll算法源于頻繁集算法Apriori，它把Apriori的基本思想擴(kuò)展到序列挖掘中，也是一個(gè)多遍掃描數(shù)據(jù)庫(kù)的算法。在每一遍掃描中都利用前一遍的大序列來(lái)產(chǎn)生候選序列，然后在完成遍歷整個(gè)數(shù)據(jù)庫(kù)后測(cè)試它們的支持度。在第一遍掃描中，利用大項(xiàng)目集階段的輸出來(lái)初始化大1-序列的集合。在每次遍歷中，從一個(gè)由大序列組成的種子集開始，利用這個(gè)種子集，可以產(chǎn)生新的潛在的大序列。在第一次遍歷前，所有在大項(xiàng)集階段得到的大1-序列組成了種子集。2023/2/333DataMining:ConceptsandTechniquesAprioriAll算法表6-2顧客序列表示例

1.AprioriAll算法描述算法6-1

AprioriAll算法輸入：大項(xiàng)集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫(kù)DT輸出：所有最長(zhǎng)序列（1）L1={large1-sequences}；//大項(xiàng)集階段得到的結(jié)果（2）FOR（k=2；Lk-1

；k++）DOBEGIN（3）Ck=aprioriALL_generate(Lk-1)；//Ck是從Lk-1中產(chǎn)生的新的候選者（4）FOReachcustomer-sequencecinDTDO//對(duì)于在數(shù)據(jù)庫(kù)中的每一個(gè)顧客序列c（5）SumthecountofallcandidatesinCkthatarecontainedinc；//被包含于c中Ck內(nèi)的所有候選者計(jì)數(shù)（6）Lk=CandidatesinCkwithminimumsupport//Lk＝Ck中滿足最小支持度的候選者（7）END；（8）Answer=MaximalSequencesin∪kLk；由于我們?cè)陉P(guān)聯(lián)規(guī)則一章對(duì)Apriori算法進(jìn)行了詳盡地介紹，因此上面給出的算法流程很容易理解。它的關(guān)鍵仍然是侯選集的產(chǎn)生，具體候選者的產(chǎn)生如下：2023/2/334DataMining:ConceptsandTechniquesAprioriAll算法舉例例子6-1對(duì)于如下所示的長(zhǎng)度為3的序列集合。若將其作為函數(shù)aprioriALL_generate的輸入?yún)?shù)，在連接之后將如圖6-10(b)所示。再修剪掉子序列不在L3中的序列后，得到的序列如圖6-10(c)所示。在修剪的過(guò)程中，對(duì)于<1，2，4，3>，因?yàn)?lt;2，4，3>不在L3大3序列中，所以<1，2，4，3>將被修剪掉。同理其他序列的修剪也是如此。此外，需要說(shuō)明的是在產(chǎn)生候選4序列時(shí)不會(huì)產(chǎn)生長(zhǎng)度大于4的序列，比如<1，2，4>和<1，3，5>連接時(shí)，程序在WHERE條件語(yǔ)句將終止此操作。2023/2/335DataMining:ConceptsandTechniquesAprioriAll算法舉例例子6-2給出一個(gè)客戶序列組成的數(shù)據(jù)庫(kù)如圖6-11（a）所示，在這里我們沒有給出源數(shù)據(jù)庫(kù)的形式，即客戶序列已經(jīng)以轉(zhuǎn)換的形式出現(xiàn)。假如最小支持度為40%（也就是至少兩個(gè)客戶序列）那么在大項(xiàng)集階段可以得到大1-序列，之后應(yīng)用AprioriAll算法可以逐步演變成最終的大序列集。圖6-11給出了整個(gè)過(guò)程。2023/2/336DataMining:ConceptsandTechniquesAprioriAll算法舉例2023/2/337DataMining:ConceptsandTechniquesAprioriAll算法舉例至此，AprioriAll算法找到了所有的大-k序列集，即L1、L2、L3、L4，對(duì)于大-k序列集進(jìn)行MaximalSequencesin∪kLk運(yùn)算，最終得到最大的大序列。上例結(jié)果如下表所示：AprioriAll利用了Apriori算法的思想，但是在候選產(chǎn)生和生成頻繁序列方面需要考慮序列元素有序的特點(diǎn)進(jìn)行相應(yīng)地處理。表6-8只給出了最終的頻繁序列，實(shí)際上在候選產(chǎn)生過(guò)程中有大量序列產(chǎn)生。例如圖6-11中，在由L2產(chǎn)生C3過(guò)程中，諸如〈2，3，4〉和〈2，4，3〉都作為候選被測(cè)試，只不過(guò)因?yàn)椤?，4，3〉不滿足支持度要求而在演化L3過(guò)程中被裁減掉。Sequences

Support<1，2，3，4>2<1，3，5>2<4，5>22023/2/338DataMining:ConceptsandTechniques第六章時(shí)間序列和序列模式挖掘

內(nèi)容提要時(shí)間序列及其應(yīng)用時(shí)間序列預(yù)測(cè)的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時(shí)間序列相似性查找基于規(guī)范變換的查找方法序列挖掘及其基本方法AprioriAll

算法AprioriSome

算法GSP算法2023/2/339DataMining:ConceptsandTechniquesAprioriSome算法AprioriSome算法可以看作是AprioriAll算法的改進(jìn)，具體過(guò)程分為兩個(gè)階段：前推階段：此階段用于找出指定長(zhǎng)度的所有大序列?；厮蓦A段：此階段用于查找其他長(zhǎng)度的所有大序列。算法6-3AprioriSome算法輸入：大項(xiàng)集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫(kù)DT輸出：所有最長(zhǎng)序列//ForwardPhase—前推階段；（1）L1={large1-sequences}；//大項(xiàng)目集階段的結(jié)果；（2）C1=L1；（3）last=1；//最后計(jì)數(shù)的Clast

（4）FOR（k=2；Ck-1

andLlast

；k++）DOBEGIN（5）IF（Lk-1know）THENCk=NewcandidatesgeneratedfromLk-1；//Ck＝產(chǎn)生于Lk-1新的候選集（6）ELSECk=NewcandidatesgeneratedfromCk-1；//Ck＝產(chǎn)生于Ck-1新的候選集（7）IF（k=next（last））THENBEGIN（9）FOReachcustomer-sequencecinthedatabaseDO//對(duì)于在數(shù)據(jù)庫(kù)中的每一個(gè)客戶序列c（10）SumthecountofallcandidatesinCkthatarecontainedinc；//求包含在c中的Ck的候選者的數(shù)目之和（11）Lk=CandidatesinCkwithminimumsupport；//Lk＝在Ck中滿足最小支持度的候選者（12）last=k；（13）END；（14）END；2023/2/340DataMining:ConceptsandTechniquesAprioriSome算法(續(xù))表6-2顧客序列表示例//BackwardPhase—回溯階段；（15）FOR（k--；k>=1；k--）DO（16）IF（Lknotfoundinforwardphase）THENBEGIN//Lk在前推階段沒有確定的情況（17）DeleteallsequencesinCkcontainedinSomeLi，i>k；//刪除所有在Ck中包含在Lk中的序列，i>k（18）FOReachcustomer-sequencecinDTDO//對(duì)于在DT中的每一個(gè)客戶序列c（19）SumthecountofallcandidatesinCkthatarecontainedinc；//對(duì)在Ck中包含在c中的所有的候選這的計(jì)數(shù)（20）Lk

=CandidatesinCkwithminimumsupport//Lk=在Ck中滿足最小支持度的候選者（21）END；（22）ELSEDeleteallsequencesinLkcontainedinSomeLi，i>k；//Lk

已知（23）Answer=∪k

Lk；//從k到m求Lk的并集在前推階段（forwardphase）中，我們只對(duì)特定長(zhǎng)度的序列進(jìn)行計(jì)數(shù)。比如，前推階段我們對(duì)長(zhǎng)度為1、2、4和6的序列計(jì)數(shù)（計(jì)算支持度），而長(zhǎng)度為3和5的序列則在回溯階段中計(jì)數(shù)。next函數(shù)以上次遍歷的序列長(zhǎng)度作為輸入，返回下次遍歷中需要計(jì)數(shù)的序列長(zhǎng)度。算法6-4next（k:integer）IF（hitk<0.666）THENreturnk+1；ELSEIF（hitk<0.75）THENreturnk+2；ELSEIF（hitk<0.80）THENreturnk+3；ELSEIF（hitk<0.85）THENreturnk+4；ELSETHENreturnk+5；hitk被定義為大k-序列（largek-sequence）和候選k-序列（candidatek-sequence）的比率，即|Lk|/|Ck|。這個(gè)函數(shù)的功能是確定對(duì)哪些序列進(jìn)行計(jì)數(shù)，在對(duì)非最大序列計(jì)數(shù)時(shí)間的浪費(fèi)和計(jì)算擴(kuò)展小候選序列之間作出權(quán)衡。2023/2/341DataMining:ConceptsandTechniquesAprioriSome算法例子6-3我們?nèi)匀徊捎肁prioriAll算法用過(guò)的圖6-11（a）數(shù)據(jù)庫(kù)例子來(lái)說(shuō)明AprioriSome算法。在大項(xiàng)集階段可以找出L1（和圖6-9（b）的L1相同）。假設(shè)next（k）=2k，則通過(guò)計(jì)算C2可以得到L2（和圖6-11（d）中的L2相同）。第三次遍歷后，apriori_generate函數(shù)以L2作為輸入?yún)?shù)來(lái)產(chǎn)生C3。圖6-12（e）給出了C3中的候選序列。我們不計(jì)算C3，因此也不產(chǎn)生L3。下一步apriori_generate函數(shù)以C3來(lái)產(chǎn)生C4，在經(jīng)過(guò)剪枝后，得到的結(jié)果和圖6-9（i）所示的C4相同。在以C4計(jì)算L4（圖6-12（i））之后，我們?cè)噲D產(chǎn)生C5，這時(shí)的結(jié)果為空。前推階段的具體運(yùn)行見下圖6-12所示。2023/2/342DataMining:ConceptsandTechniquesAprioriSome算法2023/2/343DataMining:ConceptsandTechniquesAprioriSome算法回溯階段的具體運(yùn)行見下圖6-13所示。2023/2/344DataMining:ConceptsandTechniquesAprioriAll和AprioriSome比較AprioriAll和AprioriSome比較AprioriAll用Lk-1去算出所有的候選Ck，而AprioriSome會(huì)直接用Ck-1去算出所有的候選Ck.，因?yàn)镃k-1包含Lk-1，所以AprioriSome會(huì)產(chǎn)生比較多的候選。雖然AprioriSome跳躍式計(jì)算候選，但因?yàn)樗a(chǎn)生的候選比較多，可能在回溯階段前就占滿內(nèi)存。如果內(nèi)存滿了，AprioriSome就會(huì)被強(qiáng)迫去計(jì)算最后一組的候選，（即使原本是要跳過(guò)此項(xiàng)）。這樣，會(huì)影響并減少已算好的兩個(gè)候選間的跳躍距離，而使得AprioriSome會(huì)變的跟AprioriAll一樣。對(duì)于較低的支持度，有較長(zhǎng)的大序列，也因此有較多的非最大序列，所以AprioriSome

比較好。2023/2/345DataMining:ConceptsandTechniques第六章時(shí)間序列和序列模式挖掘

內(nèi)容提要時(shí)間序列及其應(yīng)用時(shí)間序列預(yù)測(cè)的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時(shí)