第六章時間序列和序列模式挖掘

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

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

算法AprioriSome

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

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

算法AprioriSome

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

其他方法

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

表示循環(huán)變動趨勢項，Rt表示隨機干擾項，yt

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

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

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

=Tt·St+Rt

或yt

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

通過建立隨機模型，對隨機時間序列進行分析，可以預(yù)測未來值。若時間序列是平穩(wěn)的，可以用自回歸(AutoRegressive，簡稱AR)模型、移動回歸模型(MovingAverage，簡稱MA)或自回歸移動平均(AutoRegressiveMovingAverage，簡稱ARMA)模型進行分析預(yù)測。

其他方法

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

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

算法AprioriSome

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

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

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

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

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

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

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

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

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

算法AprioriSome

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

內(nèi)容提要時間序列及其應(yīng)用時間序列預(yù)測的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時間序列相似性查找基于規(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個條件，可以認為與是-similar：（1）對任意的都成立；（2）存在一些比例因子和一些偏移使得下式成立：

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

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

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

算法AprioriSome

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

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

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

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

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

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

算法AprioriSome

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

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

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

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

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

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

算法AprioriSome

算法GSP算法2023/2/339DataMining:ConceptsandTechniquesAprioriSome算法AprioriSome算法可以看作是AprioriAll算法的改進，具體過程分為兩個階段：前推階段：此階段用于找出指定長度的所有大序列?；厮蓦A段：此階段用于查找其他長度的所有大序列。算法6-3AprioriSome算法輸入：大項集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫DT輸出：所有最長序列//ForwardPhase—前推階段；（1）L1={large1-sequences}；//大項目集階段的結(jié)果；（2）C1=L1；（3）last=1；//最后計數(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//對于在數(shù)據(jù)庫中的每一個客戶序列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//對于在DT中的每一個客戶序列c（19）SumthecountofallcandidatesinCkthatarecontainedinc；//對在Ck中包含在c中的所有的候選這的計數(shù)（20）Lk

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

已知（23）Answer=∪k

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

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

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