基于改進MOEN算法的時序數據主旨模式挖掘

王丹丹

摘要：主旨模式挖掘常用于發(fā)現時間序列中具有代表性的相似子序列，其中MOEN算法（Efficient Enumeration of Motifs，MOEN）基于枚舉的思想來發(fā)現指定長度范圍內的主旨模式（motifs），采用候選相似子序列的方法降低了計算所需資源。本研究對距離矩陣的生成策略加以改進，進一步降低計算成本，并通過實驗驗證其有效性。

關鍵詞：時間序列;motifs;MOEN算法;枚舉

中圖分類號：TP311 文獻標識碼：A 文章編號：1007-9416（2020）02-0096-02

0 引言

主旨模式挖掘作常用于發(fā)現時間序列中具有代表性的相似子序列。Patel等首次提出主旨模式（motifs）[1]，并提出了K-motif算法，該算法無法發(fā)現長度不等的motif。Tang等人在K-motif的基礎上提出一種通過綜合發(fā)現的motif來生成原型模式的方法[2]，來發(fā)現長度不等的motif。Muenn等先提出了精確主旨模式挖掘算法[3]，后又提出了MOEN算法[4]（Efficient Enumeration of Motifs，MOEN），算法采用候選相似子序列的方法解決了傳統(tǒng)枚舉法計算量大的問題，本文針對此算法的不足加以改進，并驗證其有效性。

1 相關定義

1.1 定義1：時間序列與子序列

時間序列T是一條長度為n的實數序列，可表示為T=t1，t2，t3，…，tn。子序可表示為Si，m=ti，ti+1，…，ti+m-1，其中m

1.2 定義2：平凡匹配

給定序列T與實數R，已知Sp，m與Sq，m，其中mr>q時，不存在Sr，m，使得D（Sp，m，Sr，m）>R，則稱Sp，m為Sq，m的平凡匹配序列。

2 改進MOEN算法

2.1 MOEN算法

MOEN算法通過邊界策略來減少枚舉次數，降低運算復雜度。算法第一步計算長度為m的子序列間的距離dmi，j=D（Si，m，Sj，m），i≠j與距離矩陣list;第二步統(tǒng)計非平凡匹配數，找出長度m下的1-motif;第三步將距離矩陣由小到大排序，候選距離矩陣listm為其前n項;第四步計算長度為m+1時的距離上界LB，公式為LB2=（+z2）-1d2，式中z為長度為m的子序列標準化后的最大值，d 為候選矩陣中距離最大值;第5步，基于listm計算新的距離，若小于LB則重復步驟2～6，若大于LB則返回步驟1。

2.2 改進MOEN算法

MOEN算法存在如下問題，首先該算法只挖掘出了1-motif，而實際應用中需要K-motifs;其次距離矩陣比較冗余。針對第一個問題，將原算法中的第2步更改為挖掘K-motifs即可。針對第二個問題，改進算法通過避免產生“無用項”來減小距離矩陣。已知，? ? ? ? ? ? ? ? ? ? ? D（Si，m+1，Sj，m+1）≥D（Si，m，Sj，m），若Sj，m+1與Si，m+1的不匹配，則D（Si，m+1，Sj，m+1）>R，D（Si，m，Sj，m）>R，R為閾值。由此推得Sj，m一定不是Si，m的匹配序列，故其為無用項。因此，只要在生成listm時設置合適的距離閾值M即可篩除無用項，降低計算復雜度。為了適應不同長度下子序列間距離的變化M=2λm，λ為正數。

3 實驗結果與分析

表1和表2為部分實驗結果，當子序列長度為5時，改進算法的距離矩陣大小僅為原始算法產生的距離矩陣的3.1%;當子序列長度為11時，這個值為2.7%。

圖1與圖2 分別為原始算法與改進算法產生的候選序列，圖中每條折線代表一個序列，可以看出改進MOEN算法在降低距離矩陣大小的同時，提升了算法的精度，具有實際的意義與價值。

參考文獻

[1] Patel P，Keogh E J，Lin J，et al.Mining Motifs in Massive Time Series Databases[J].Proc.of IEEE Intl Conf.on Data Mining Maebashi Japan，2002：370-377.

[2] Tang H，Liao S S.Discovering original motifs with different lengths from time series[J].Knowledge-Based Systems，2008，21（7）：666-671.

[3] Mueen A，Keogh E J，Zhu Q，et al.Exact Discovery of Time Series Motifs[C]//SDM.2009：473-484.

[4] Mueen A.Enumeration of Time Series Motifs of All Lengths[C]//2013 IEEE 13th International Conference on Data Mining.IEEE Computer Society，2013.

Find Time Series Motifs Based on Improved MOEN Algorithm

WANG Dan-dan

（Chongqing JiaoTong University， Chongqing? 400000）

Abstract：Motifs mining is often used to find representative similar subsequences in time series. MOEN algorithm （efficiency enumeration of motifs， Moen） is based on the idea of enumeration to find the motifs within the specified length range. The method of candidate similar subsequences reduces the computing resources. In this study， the generation strategy of distance matrix is improved to further reduce the calculation cost， and its effectiveness is verified by experiments.

Key words：time series; motifs; MOEN algorithm; enumeration