基于PSO的不確定時間序列模體發(fā)現(xiàn)算法

王 菊,劉付顯,靳春杰

(1. 空軍工程大學防空反導學院, 陜西 西安 710051;2. 中國人民解放軍93527部隊, 河北 張家口 075000)

0 引 言

時間序列是一種按照時間先后順序排列的記錄序列,具有很廣泛的應用范圍,如醫(yī)藥、生物、計算機、金融等[1-2]。而模體是指時間序列中一些相似度很高的時間序列片段[3]。由于模體中包含被研究時間序列的一些很重要信息[4-5],且模體發(fā)現(xiàn)(motif discovery,MD)也是分類[6-7]、聚類[8-9]、異常檢測[10-11]和規(guī)則發(fā)現(xiàn)[12-13]等處理時間序列算法的核心,因此MD對于理解、建模和預測隱藏在時間序列背后的系統(tǒng)具有基礎性的作用。

目前針對時間序列MD的算法主要可以分為近似型算法和精確型算法2種。近似型算法的計算復雜度較低,是早些年的研究熱點,其核心思想是將時間序列劃分為一系列小的時間序列片段,并用符號或實數(shù)近似地表示這些時間序列片段,典型的算法主要有矩陣逼近的基元枚舉(enumeration of motifs through matrix approximation,EMMA)[14]、主題跟蹤算法(motif tracking algorithm,MTA)[15]和節(jié)省空間算法(space saving algorithm,SS)[16]等。但是這類算法的缺陷在于需要確定大量的參數(shù),且這些參數(shù)通常與被研究的時間序列相關。由于精確型算法的計算量非常大,一直以來被認為是不可實現(xiàn)的,直到文獻[17]提出了MK算法?；谒麄兊墓ぷ?一些改進算法被陸續(xù)提出,但是這些算法的一個共同缺點是需要指定模體的長度。為解決這個問題,文獻[18]提出了可以發(fā)現(xiàn)不同長度模體的MOEN算法。但是,該算法仍然存在一些缺點有待改進:①運算時間比較長;②只適用于歐式距離;③只能針對確定的時間序列展開研究。

為此,本文提出了基于粒子群(particle swarm optimization,PSO)的不確定時間序列(uncertain time series, UTS)的MD算法,在傳統(tǒng)MD算法的基礎上,增加了處理不確定性的功能。該算法設計了基于PSO的UTS MD的研究框架,通過對時間序列片段用該時間序列片段的起始時刻和持續(xù)時間進行編碼和修正,并利用PSO算法在參數(shù)設置少、機理簡單、收斂速度快、全局優(yōu)化能力強等方面的優(yōu)勢,實現(xiàn)了對UTS的MD。實驗結果表明,本文所提出的算法不僅可發(fā)現(xiàn)不同長度的模體,還可根據(jù)實際情況采用多種度量方法,且在精度較高的情況下不會占用較大的內存和運行時間。

1 UTS的預處理

1.1 UTS的表示方法

對于UTS的表示方法,一般可分為2種,即離散型和連續(xù)型[19]。其中離散型是指UTS中每個時刻的數(shù)據(jù)點可能取值由一系列離散的采樣點組成,且每個采樣點以一定的概率出現(xiàn)或服從某種離散型分布;連續(xù)型是指UTS中每個時刻的數(shù)據(jù)點可看作連續(xù)型隨機變量,他們服從某種一致的連續(xù)型概率分布[20]。在實際應用中,連續(xù)型的UTS通過采樣常常可以轉化為離散型UTS,因此本文的主要研究對象為離散型UTS,文中簡稱為UTS,其定義如下。

表1 UTS的示例

1.2 UTS的規(guī)約

在進行UTS的相似性匹配時,需要把已創(chuàng)建的UTS模型的可能世界都展開成確定的時間序列(certain time series,CTS)。但是由于所得CTS的數(shù)量是指數(shù)級的,存在組合爆炸的問題,計算量十分巨大。為了解決這個問題,常用的方法是將UTS規(guī)約為一條或幾條CTS,作為UTS的代表[22]。本文采用以下3種CTS作為對UTS真實值的近似。

定義2(Pmax時間序列)對于長度為n的UTS TSU，其相應的Pmax時間序列是由每個時刻取值概率最大的觀察值所構成。例如對于表1中的UTS，Pmax時間序列TSPmax為{0.9,1.3,1.6,1.6}。

定義3(Relative時間序列)對于長度為n的UTS TSU,利用時間序列的連續(xù)性,其相應的Relative時間序列是由后一時刻的觀察值集合中與前一時刻觀察值最接近的觀察值所構成,第1個時刻的觀察值為該時刻取值概率最大的觀察值。例如對于表1中的UTS,Relative時間序列TSRelative為{0.9,0.9,0.8,1.6}。

定義4(Ave時間序列)對于長度為n的UTS TSU,Ave時間序列是由每個時刻觀察值集合與其相應概率相乘并求和后的值所構成。例如對于表1中的UTS,Ave時間序列TSAve為{1,1.22,1.3,2.11}。

2 研究框架

基于PSO的UTS MD算法的核心有2個:①如何從UTS中發(fā)現(xiàn)更接近實際的模體;②如何將時間序列片段用合適的編碼方式表示出來。

基于此,本文通過將UTS同時轉化為Pmax時間序列,Relative時間序列和Ave時間序列,并對這3種CTS分別基于PSO進行MD。之后,給定可以容忍的距離比閾值δ,采用投票的方式?jīng)Q定某個時間序列片段是否被輸出,并對輸出模體中相似度較高的進行合并。其中每個時間序列片段都用該時間序列片段的起始時刻和持續(xù)時間表示,并將這兩個參數(shù)作為粒子編碼的對象,其研究框架如圖1所示。

圖1 研究框架Fig.1 Research framework

由圖1可以看出,基于PSO的UTS MD算法的核心是如何從轉化后的CTS中利用PSO算法發(fā)現(xiàn)其相應的模體集合,本文將該問題簡稱為基于PSO的MD,并在下文中關于這個問題展開論述。

3 基于PSO的MD

3.1 粒子編碼

3.2 初始化種群

表2 種群的初始化方法

3.3 適應度函數(shù)

DTW(g,h)=

(1)

3.4 粒子更新

(2)

(3)

式中,ξ是慣性權重;η1和η2是2個學習因子;r1和r2是由(0,1)區(qū)間內的均勻隨機數(shù)組成的4維隨機向量;pi=(pi,1,pi,2,pi,3,pi,4)表示第i個粒子在歷代中的個體最佳位置;pg=(pg,1,pg,2,pg,3,pg,4)表示在歷代種群中所搜索到的最佳位置;·表示點乘,即按照分量逐個做出乘積。

3.5 修正策略

按照第3.4節(jié)中的方法對粒子進行更新后,會產生以下3種不具有實際意義的情況:①粒子位置向量中各維的取值不是整數(shù);②粒子位置向量中各維的取值超出了其相應的取值范圍;③粒子位置向量中各維的取值不滿足相互不重疊的約束條件。為了消除由上述3種情況所產生的無意義的粒子,本文提出了一種修正粒子編碼的策略,主要分為以下6個步驟：

從上述步驟可以看出,所提策略的主要思想是對粒子的合法性進行修正。采用這樣的修正策略一方面可以保證種群中的所有粒子都具有實際意義,另一方面可以加快搜索過程,減少運行時間。

3.6 算法流程

上述過程被重復執(zhí)行,直到滿足終止條件,算法流程如圖2所示。

圖2 基于PSO的MD算法流程Fig.2 Algorithm flow of MD based on PSO

4 實驗結果與分析

實驗中,采用PSO算法的一般參數(shù)設置,即ξ=0.9,η1=η2=2,種群規(guī)模popsiza=30,最大迭代次數(shù)為1 000。在該參數(shù)設置下,首先，用廠軋鋼過程中凸度參數(shù)的變化情況驗證本文所提算法的可行性;其次，文中算法在運行時間、占用內存和收斂性方面與MK[17]和MOEN[18]算法進行了比較,驗證了其有效性;由于目前少有關于UTS的MD算法,為驗證文中算法的優(yōu)越性,實驗中通過固定文獻[23]中算法的窗口,使其退化為基于母題啟發(fā)多重期望最大化(multiple expectotion-maximization for motif elicitation,MEME)的靜態(tài)不確定數(shù)據(jù)MD算法后,在實際數(shù)據(jù)集和仿真數(shù)據(jù)集上比較了該算法與文中所提算法在MD準確率上的性能,具體實驗數(shù)據(jù)集和實驗結果如下。

本節(jié)中所有的算法都用Matlab實現(xiàn),運行在一臺裝有64位Windows7操作系統(tǒng)的臺式計算機上。該計算機帶有2個因特爾酷睿i5-4590處理器和4 GB的RAM。

4.1 實驗數(shù)據(jù)

為驗證所提算法的可行性、有效性和優(yōu)越性,文中實驗分別在實際數(shù)據(jù)集和仿真數(shù)據(jù)集上進行,他們的構成方法如下。

實際數(shù)據(jù)集:鋼廠軋鋼過程中凸度參數(shù)的變化情況

在實際鋼廠軋鋼過程中,將每一卷鋼板作為一個周期(約為150個時間點),每一卷的凸度參數(shù)變化情況是按時間順序變化的,具有時間序列的特征。統(tǒng)計100卷的凸度參數(shù)變化情況,得到每一時間點的取值是一個可能的集合,將該集合中每個取值所出現(xiàn)的頻率視為概率,進而可以得到一個關于凸度參數(shù)的UTS。

仿真數(shù)據(jù)集:帶有噪聲干擾的UCR時間序列集

UCR是研究CTS的常用數(shù)據(jù)庫,文中主要選取其中的Synthetic Control(60個時間點)、CBF(128個時間點)、OSU Leaf(427個時間點)、Trace(275個時間點)、Wafer(128個時間點)、Beef(470個時間點)、Olive Oil(570個時間點)、Lighting-2(637個時間點)和Adiac(176個時間點)9個數(shù)據(jù)集為研究對象。為驗證所提方法的性能,本文在原始數(shù)據(jù)的基礎上加入了離散均勻分布的噪聲進行干擾,將這9個數(shù)據(jù)集中存儲序列變?yōu)閁TS。

4.2 實例驗證

圖3是關于凸度參數(shù)的UTS。

圖3 關于凸度參數(shù)的UTSFig.3 UTS on convexity parameters

從圖3可以發(fā)現(xiàn),每一個時刻凸度值都對應若干種取值,且每種取值具有不同的概率,因此直接對這樣的UTS進行MD時不可能的。根據(jù)圖1中的研究框架,文中對上述時間序列進行了轉化,得到了Pmax時間序列,Relative時間序列和Ave時間序列,如圖4所示。

圖4 轉換后的時間序列Fig.4 Time series after conversion

將wmin和wmax分別設為5和10后,對圖4中轉換后的3種時間序列分別采用基于PSO的MD算法發(fā)現(xiàn)其中的模體,全局最優(yōu)解所對應的結果如圖5所示。

圖5 轉換后的時間序列及所發(fā)現(xiàn)的模體Fig.5 Transformed time series and the found motifs after transform

依次將圖5中所示的模體表示為mPmax,mRelative和mAve,為提高所發(fā)現(xiàn)模體的精度,他們將進一步通過投票的方式來決定其是否被保留。例如mPmax,投票過程如下:①計算mPmax與Relative時間序列中相應時間片段的DTW距離DTW1及與Ave時間序列中相應時間片段的DTW距離DTW2;②判斷|DTW1/DTW2-1|是否大于給定距離比閾值δ=0.1,大于或等于則認為有1個反對者,否則是支持者;③包含自身,當支持者的個數(shù)大于2個時,該模體被最終保留,否則被丟棄,因此由于mPmax的支持者為2,其最終被保留。采用同樣的方式,可以得到mRelative被丟棄,mAve被保留。進一步地,由于mPmax和mAve所代時間序列片段對的起止時刻基本重合,且該時間段內的凸度值大小基本相同,因此在最終的輸出結果中,這2個模體被合并。

4.3 運行時間、占用內存和收斂性分析

為驗證所提算法的有效性,針對仿真數(shù)據(jù)集,本文將不同模體長度下該算法的核心(即基于PSO的MD算法)與Mueen提出的MK和MOEN算法在運行時間、占用內存和收斂性3個方面進行了比較。在比較過程中,文中算法的wmin被設為0,橫軸的數(shù)值分別對應于文中算法的wmax和MK算法的模體長度。本文對仿真數(shù)據(jù)集中的確定型時間序列進行了大量實驗,發(fā)現(xiàn)在不同確定型時間序列下所得的性能結果具有相似性,因此文中僅展示了上述3種算法針對較短時間序列Synthetic Control和較長時間序列OSU Leaf在運行時間、占用內存和收斂性上的結果,分別如圖6～圖8所示。

由于MOEN算法的一個優(yōu)勢在于可以發(fā)現(xiàn)時間序列中任意長度的模體,也就是說發(fā)現(xiàn)模體的過程與模體長度無關,因此從圖6和圖7可以看出,針對不同的確定型時間序列,無論是運行時間還是所占用的內存,隨著模體長度的變化都不會發(fā)生巨大的變化。

圖6 不同模體長度下運行時間的比較Fig.6 Comparison result of runtime under different motif length

圖7 不同模體長度下占用內存的比較Fig.7 Comparison result of memory usage under different motif length

從圖6的結果中可以發(fā)現(xiàn)MK算法的運行時間隨著模體長度的增加一直呈現(xiàn)出上升趨勢,文中所提出的算法在一定階段以后,運行時間隨著模體長度的變化趨于不顯著。造成這種結果的原因主要有2個:①每當MK算法的模體長度發(fā)生變化時,該算法都需要從頭開始重新計算,且計算復雜度正比于模體長度;②隨著模體長度的增加,本文中所提出的修正策略的作用趨于不顯著,整個算法的運行時間趨于穩(wěn)定。從圖7的結果中可以發(fā)現(xiàn)本文所提出的算法所占用的內存不隨著模體長度的變化而變化,MK算法所占用的內存隨著模體長度的增加呈現(xiàn)出增長的趨勢,但是不超過MOEN算法所占用的內存。造成這種現(xiàn)象的原因主要有2點:①文中所提算法的內存主要占用于存儲種群和最優(yōu)個體,但是根據(jù)文中所采用的編碼方式,每個個體只需要用4個參數(shù)進行表示,不因模體的長度變化而占用更多的內存;② MK算法所占用的內存主要是用于計算和存儲所發(fā)現(xiàn)的模體,因此隨著模體長度的增加,占用內存呈現(xiàn)上升趨勢,但是MK算法只存儲了某種特定長度的模體,而MOEN算法需要存儲的是符合算法要求的所有長度的模體,因此MK算法所占用的內存要比MOEN算法少。

為了驗證所提算法的收斂性,將Synthetic Control和OSU Leaf中模體的長度分別設定為10和50后,對比基于PSO的MD算法和MK算法所發(fā)現(xiàn)的模體數(shù)量,結果如圖8所示。本實驗中僅采用MK算法作為對比算法的原因是當模體長度給定時,MOEN算法和MK算法所發(fā)現(xiàn)的模體數(shù)量是相同的。

圖8 收斂性分析Fig.8 Convergence analysis

從圖8可以看出,隨著迭代次數(shù)不斷增加,文中所提算法與精確的MK算法所發(fā)現(xiàn)的模體數(shù)量逐漸趨于相同,表明文中所提算法具有較好的收斂性。說明文中所提算法可以在占用較少的運行時間和內存的情況下快速地收斂于最終的結果,證明了該方法的有效性。

4.4 MD準確率分析

由于目前少有關于UTS的MD算法,為驗證文中算法的優(yōu)越性,實驗中首先按照第4.1節(jié)的方法,對每一種數(shù)據(jù)集生成100組UTS,然后固定文獻[23]中算法的窗口,使其退化為基于MEME的靜態(tài)不確定數(shù)據(jù)MD算法(為便于闡述,下文中簡稱為MDUS-MEME算法)后,對比了該算法和本文方法所產生的模體集合與上述UTS中實際出現(xiàn)模體的平均重合率,結果如表3所示。

表3 平均重合率比較

從表3可以看出,該算法在這10種數(shù)據(jù)集上有著較好的平均重合率,表明本文所提算法具有較高的MD準確率,所得模體可以反映出原不確定時間數(shù)列的信息。

5 結束語

本文在UTS上提出了基于PSO的MD算法,不僅可以發(fā)現(xiàn)不同長度的模體,還可以根據(jù)實際情況采用多種度量方法。實驗中用實例驗證了本文所提算法的可行性,用該算法在運行時間、占用內存、收斂性和MD準確率等方面的性能驗證了其有效性和優(yōu)越性。本文的研究屬于探索性研究,不確定性理論、智能搜索算法與MD算法的深入結合將是下一步的研究內容。

參考文獻：

[1] 何書元. 應用時間序列分析[M]. 北京: 北京大學出版社, 2004.

HE S Y. Applied time series analysis[M]. Beijing: Peking University press, 2004.

[2] HOPPE C, REINER K. Economic growth and business cycles: a critical comment on detrending time series[J]. Studies in Nonlinear Dynamics and Econometrics, 2017, 5(1): 202-205.

[3] LIN J, KEOGH E, LONARDI S, et al. Finding motifs in time series[C]∥Proc.of the Workshop on Temporal Data Mining, 2002:53-56.

[4] MUEEN A. Time series motif discovery: dimensions and applications[J]. Data Mining and Knowledge Discovery，2014, 4(2): 152-159.

[5] PUNEET A, GAUTAM S, SARMIMALA S, et al. Efficiently discovering frequent motifs in large-scale sensor data[R]. Technical Report, 2015, 1-13.

[6] TORKAMANI S, LOHWEG V. Survey on time series motif discovery[J]. Wiley Interdisciplinary Reviews Data Mining and Knowledge Discovery, 2017, 7(2): 1199.

[7] BUZA K, SCHMIDY-THIEME L. Motif-based classification of time series with Bayesian networks and SVMs[M].Berlin Heidelbeng: Springer, 2009.

[8] CAO D T, ANH D T. A novel clustering-based method for time series discovery under time warping measure[J]. International Journal of Data Science and Analytics, 2017(1): 1-14.

[9] PHU L, ANH D T. Motif-based method for initial the k-means clustering for time series[J]. Journal of Computational and Applied Mathematics, 2012, 236(7): 1733-1742.

[10] TORKAMANI S, DICKS A, LOHWEG V. Anomaly detection and ATMs via time series motif discovery[C]∥Proc.of the IEEE International Conference on Emerging Technologies and Factory Automation, 2016: 6-9.

[11] LIN Y, MCCOOL M D, GHORBANI A A. Time series motif discovery and anomaly detection based on subseries join[J].Laeng International Journal of Computer Science,2010,37(3): 259-271.

[12] MUEEN A. Enumeration of time series motifs of all lengths[C]∥Proc.of the IEEE International Conference on Data Mining, 2013: 547-556.

[13] SCHOKOOHI-YEKTA M, CHEN Y, CAMPANA B, et al. Discovery of meaningful rules in time series[C]∥Proc.of the ACM SIGKKD International Conference on Knowledge Discovery and Data Mining, 2015: 1085-1094.

[14] LIN J, KEOGH E, LONARDI S, et al. Finding motifs in time series[C]∥Proc.of the Workshop on Temporal Data Mining, 2002: 53-56.

[15] LI Y, LIN J. Approximate variable-length time series motif discovery using grammar inference[C]∥Proc.of the International Workshop on Multimedia Data Mining, 2010: 10-15.

[16] CASTRO N, AZEVEDO P. Multi-resolution motif discovery in time series[C]∥Proc.of the SIAM International Conference on Data Mining, 2010: 665-676.

[17] MUEEN A, KEOGH E, ZHU Q, et al. Exact discovery of time series motif[C]∥Proc.of the SIAM International Conference on Data Mining, 2009: 1-12.

[18] ABDULLAH M, NIKAN C. Enumeration of time series motifs of all lengths[J]. Knowledge Information System, 2015, 45: 1050-132.

[19] KRIEGEL H P, KUNATH P, PFEIFLE M, et al. Probabilistic similarity join on uncertain data[C]∥Proc.of the 11th International Conference on Data base Systems for Advanced Applications, 2006: 295-309.

[20] BARBAR D, GAREIA-MOLINA H, PORTER D. The management of probabilistic data[J]. IEEE Trans. Knowledge and Data Engineering, 1992, 4(5): 487-502.

[21] SANNA A, NABAR S, WIDOM J. Representing uncertain data: uniqueness, equivalence, minimization, and approximation[J]. Technical Report, 2005: 1-15.

[22] 宋轉,廖小飛,肖瑞. 不確定時間序列的相似性匹配研究[J]. 計算機應用研究, 2014, 34(11): 3349-3352.

SONG Z, LIAO X F, XIAO R. Similarity matching for uncertain time series[J]. Application Research of Computers, 2014, 34(11): 3349-3352.

[23] 王菊,劉付顯,靳春杰，等. 一種面向不確定數(shù)據(jù)流的模體發(fā)現(xiàn)算法[J]. 電子科技大學學報,2017,46(1): 81-87.

WANG J, LIU F X, JIN C J, et al. New motif discovery algorithm for uncertain data stream[J]. Journal of University of Electronic Science and Technology of China, 2017, 46(1): 81-87.