王丹丹

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

關(guān)鍵詞：時(shí)間序列;motifs;MOEN算法;枚舉

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2020）02-0096-02

0 引言

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

1 相關(guān)定義

1.1 定義1：時(shí)間序列與子序列

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

1.2 定義2：平凡匹配

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

2 改進(jìn)MOEN算法

2.1 MOEN算法

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

2.2 改進(jìn)MOEN算法

MOEN算法存在如下問(wèn)題，首先該算法只挖掘出了1-motif，而實(shí)際應(yīng)用中需要K-motifs;其次距離矩陣比較冗余。針對(duì)第一個(gè)問(wèn)題，將原算法中的第2步更改為挖掘K-motifs即可。針對(duì)第二個(gè)問(wèn)題，改進(jìn)算法通過(guò)避免產(chǎn)生“無(wú)用項(xiàng)”來(lái)減小距離矩陣。已知，? ? ? ? ? ? ? ? ? ? ? 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的匹配序列，故其為無(wú)用項(xiàng)。因此，只要在生成listm時(shí)設(shè)置合適的距離閾值M即可篩除無(wú)用項(xiàng)，降低計(jì)算復(fù)雜度。為了適應(yīng)不同長(zhǎng)度下子序列間距離的變化M=2λm，λ為正數(shù)。

3 實(shí)驗(yàn)結(jié)果與分析

表1和表2為部分實(shí)驗(yàn)結(jié)果，當(dāng)子序列長(zhǎng)度為5時(shí)，改進(jìn)算法的距離矩陣大小僅為原始算法產(chǎn)生的距離矩陣的3.1%;當(dāng)子序列長(zhǎng)度為11時(shí)，這個(gè)值為2.7%。

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

參考文獻(xiàn)

[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