時(shí)間序列周期模式挖掘算法分析

鄒蕾

（北京科技大學(xué)　東凌經(jīng)濟(jì)管理學(xué)院，北京　100083）

?

時(shí)間序列周期模式挖掘算法分析

鄒蕾

（北京科技大學(xué)東凌經(jīng)濟(jì)管理學(xué)院，北京100083）

［摘要］時(shí)間序列周期模式的挖掘無(wú)論對(duì)科研活動(dòng)還是社會(huì)生活都有非常大的實(shí)際意義，有利于更好的預(yù)測(cè)及趨勢(shì)分析。已有的時(shí)間序列周期模式挖掘算法根據(jù)周期長(zhǎng)度參數(shù)是否已知可分為三類：已知周期長(zhǎng)度、給定周期長(zhǎng)度閾值及周期長(zhǎng)度未知的周期模式挖掘。

［關(guān)鍵詞］周期模式挖掘；周期長(zhǎng)度；算法綜述

1　引言

已有學(xué)者對(duì)時(shí)間序列周期模式挖掘進(jìn)行了大量的研究，并針對(duì)各種數(shù)據(jù)特征及應(yīng)用場(chǎng)景，提出了各種不同周期模式挖掘的算法。根據(jù)周期長(zhǎng)度是否已知，周期模式挖掘可以分為三類，即周期長(zhǎng)度參數(shù)已知的周期模式挖掘、給定周期長(zhǎng)度參數(shù)閾值的周期模式挖掘及周期長(zhǎng)度預(yù)先未知的周期模式挖掘。各種周期模式的具體分類及前人提出的挖掘算法的總結(jié)將在下文進(jìn)行詳細(xì)介紹。

2　時(shí)間序列周期模式挖掘的分類

2.1已知周期長(zhǎng)度的周期模式挖掘

周期模式挖掘中周期長(zhǎng)度是一個(gè)重要的參數(shù)，大部分算法都是基于周期長(zhǎng)度參數(shù)已知的前提下提出的，各種不同周期模式挖掘算法的分類如下：

（1）完全周期模式挖掘與部分周期模式挖掘。完全周期模式（FuII Periodic Patterns）挖掘最早由Ozden于1998年提出，他的輸入數(shù)據(jù)是一系列交易數(shù)據(jù)集，每條交易記錄又由一系列項(xiàng)集隨機(jī)組合而成，另外，每條交易記錄被標(biāo)記了發(fā)生時(shí)間。算法的目標(biāo)是挖掘出具有重復(fù)性的關(guān)聯(lián)規(guī)則。完全周期模式指一個(gè)序列經(jīng)過(guò)等間隔劃分為等長(zhǎng)的子序列，每個(gè)子序列為嚴(yán)格相同的周期模式。

事實(shí)上，部分周期模式（PartiaI Periodic Patterns）在生活中的存在更廣泛。部分周期模式［1］最早由Jiawei Han于1999年提出，大部分部分周期模式挖掘算法都是基于Apriori性質(zhì)。Han等人通過(guò)探索部分周期模式特有的性質(zhì)，包括Apriori啟發(fā)式性質(zhì)、最大子模式命中集（Max-subpattern hit set）屬性，進(jìn)一步提出幾種新的算法來(lái)挖掘部分周期模式。其中最大子模式命中集屬性將時(shí)間序列模式子集包含在最大命中子模式樹(shù)中，這樣挖掘部分周期模式只需要掃描兩次時(shí)間序列數(shù)據(jù)庫(kù)就能把時(shí)間序列中所有的頻繁模式分離出來(lái)。同時(shí)，該算法還可以挖掘多周期的時(shí)間序列部分周期模式。Rasheed等提出的增量周期模式［2］挖掘算法大大提高了周期模式的聯(lián)機(jī)分析處理能力，對(duì)周期模式的挖掘提出了更高的要求。

完全周期模式強(qiáng)調(diào)序列中每個(gè)元素都嚴(yán)格參與構(gòu)成周期模式，而部分周期模式中未必每個(gè)元素都對(duì)周期性有貢獻(xiàn)，實(shí)際上，部分周期模式是比完全周期模式更松散的一種周期模式，在生活中的存在也更加廣泛，因此部分周期模式的研究就更富有意義，也是當(dāng)前的研究熱點(diǎn)。

（2）同步周期模式挖掘與異步周期模式挖掘。同步周期模式（Synchronous Periodic Patters）指周期子序列與原序列嚴(yán)格對(duì)齊，如在字符序列｛a，f，c，a，d，c，a，g，c，d，c，a｝中，子序列｛a，*，c｝，｛a，*，*｝，｛*，*，c｝都是原序列同步周期模式。如果原序列由于噪聲干擾或者元素丟失等，導(dǎo)致子序列與原序列錯(cuò)位性匹配，則構(gòu)成的周期模式稱為異步周期模式（Asynchronous Periodic Patters），上文提到的字符序列中，子序列｛a，*｝，｛c，*｝，｛c，a｝都是原序列的異步周期模式。

現(xiàn)實(shí)生活中，如果一味的去追求同步周期模式的話很可能就會(huì)丟失掉一些規(guī)律。只要周期模式客觀存在、錯(cuò)位幅度在最大偏差以內(nèi)、干擾的時(shí)間持續(xù)長(zhǎng)度在可檢測(cè)范圍，那么我們?nèi)耘f可以找到該事件的周期模式。Jiong Yang等人提出的異步周期模式挖掘算法LSI［3］就是基于上述思想，他定義了兩個(gè)參數(shù)，“周期模式的最小重復(fù)次數(shù)”min_rep和兩個(gè)連續(xù)有效的分段間的“最大允許間隔距離”max_dis?；谝陨蟽蓚€(gè)參數(shù)，他提出一種兩階段的挖掘算法，首先，根據(jù)“最大允許間隔距離”參數(shù)剪枝生成候選周期模式，然后迭代驗(yàn)證候選周期模式的有效性，并生成最長(zhǎng)周期子序列。Kuo-Yu Huang等人在LSI算法的基礎(chǔ)上進(jìn)一步提出SMCA［4］算法，該算法的改進(jìn)之處在于，除了LSI算法的兩個(gè)參數(shù)外，SMCA算法新增了一個(gè)參數(shù)——“有效序列的最小重復(fù)次數(shù)”gIobaI_rep，并且SMCA算法允許同一時(shí)間點(diǎn)發(fā)生多個(gè)事件，能處理的數(shù)據(jù)更復(fù)雜。Xiangzhan Yu等人提出的異步周期挖掘算法［5］通過(guò)設(shè)置多個(gè)最小項(xiàng)集支持度閾值，不僅關(guān)注模式的頻繁性，更關(guān)注同一模式中各個(gè)元素的周期性挖掘。

（3）稀有周期模式挖掘。以往的周期模式挖掘算法都是關(guān)注頻繁周期模式的挖掘，Jiong Yang等人提出一個(gè)算法InfoMiner，用于稀少但具有統(tǒng)計(jì)意義的周期模式——稀有周期模式（Surprising Periodic Patterns）［6］的挖掘。稀有周期模式挖掘基于信息論中的“信息量”（Information）和“信息增益”（Information Gain）概念，提出一種新的信息增益模型，代替以往的支持度（Support）模型。該模型更關(guān)注事件發(fā)生概率很小，但一旦出現(xiàn)就具有周期性的序列模式的挖掘。該算法采用“信息增益”指標(biāo)度量序列中各模式的“奇異度”（Surprise），從而選出奇異度大于用戶預(yù)定義的閾值的周期模式。由于上述算法沒(méi)有考慮周期模式的發(fā)生位置信息，因此Jiong Yang等人提出一個(gè)改進(jìn)的InfoMiner+算法［7］，用廣義的信息增益指標(biāo)度量各模式的奇異度，從而找出所有具有統(tǒng)計(jì)意義的部分周期子序列。

2.2給定周期長(zhǎng)度閾值的周期模式挖掘

實(shí)際上，周期模式挖掘算法中提前預(yù)知周期長(zhǎng)度的情況很少見(jiàn)，但是用戶可能會(huì)提供一些有用的周期長(zhǎng)度信息，比如，雨季來(lái)臨時(shí)每隔三到五天會(huì)有一場(chǎng)大雨降臨，這說(shuō)明周期長(zhǎng)度閾值為3～5天，這對(duì)周期模式的挖掘也有重大意義。

近似周期模式挖掘不僅允許序列模式中事件的發(fā)生位置近似具有周期性，也允許序列模式的結(jié)構(gòu)近似具有周期性。著名的近期周期模式挖掘算法由Dehne等［8］提出，該算法定義一個(gè)參數(shù)α∈［0，1］，使單一事件相鄰發(fā)生時(shí)間間隔絕對(duì)差的最大值與最小值之比——周期比最大值為1+α。該算法的缺陷是時(shí)間復(fù)雜度為O（n3），當(dāng)輸入數(shù)據(jù)量很大時(shí)，算法時(shí)間復(fù)雜度太高。因此，作者通過(guò)定義一個(gè)新的參數(shù)ε，尋找周期比至多為（1+α）（1+ε）的子序列，從而將時(shí)間復(fù)雜度降低為O（n1+γ），其中γ為一任意小的正常數(shù)。Amir等［9］提出的近似周期模式挖掘算法允許序列模式中事件的發(fā)生位置近似具有周期性。該算法預(yù)先給定一個(gè)參數(shù)ε∈［0，1），目標(biāo)是尋找同一事件的相鄰兩次發(fā)生時(shí)間間隔絕對(duì)差介于p與p（1+ε）之間的最長(zhǎng)周期模式。與之前的近似周期模式挖掘算法相比，該算法的時(shí)間復(fù)雜度為亞三次方，且大部分情況下為O（n2），算法的時(shí)間復(fù)雜度有了很大提高。

2.3未知周期長(zhǎng)度的周期模式挖掘

所有以上的算法都需要用戶主觀輸入周期長(zhǎng)度參數(shù)，即用戶需要預(yù)先知道周期長(zhǎng)度或周期長(zhǎng)度的閾值范圍，這使得這些算法更適用于自然周期長(zhǎng)度的數(shù)據(jù)，比如以小時(shí)、日、周、月、年等為周期長(zhǎng)度的數(shù)據(jù)。然而，大部分?jǐn)?shù)據(jù)集可能不以自然周期長(zhǎng)度重復(fù)，因此，需要一種適用性更廣的算法來(lái)抽取隱含的周期長(zhǎng)度及周期模式。

Ma等［10］于2001年提出一種未知周期長(zhǎng)度的周期模式挖掘算法。作者將周期模式關(guān)聯(lián)規(guī)則挖掘分為兩個(gè)子任務(wù)：即序列模式周期長(zhǎng)度發(fā)現(xiàn)和時(shí)序關(guān)聯(lián)規(guī)則挖掘。文中提出兩個(gè)算法，前者首先進(jìn)行序列模式周期長(zhǎng)度發(fā)現(xiàn)，而后進(jìn)行周期模式關(guān)聯(lián)規(guī)則挖掘，其中，周期長(zhǎng)度發(fā)現(xiàn)算法采用卡方檢驗(yàn)尋找周期長(zhǎng)度。后者首先進(jìn)行事件間關(guān)聯(lián)規(guī)則挖掘，然后進(jìn)行序列模式周期長(zhǎng)度發(fā)現(xiàn)。經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，事件間關(guān)聯(lián)規(guī)則優(yōu)先挖掘的算法受噪聲影響更小，但周期長(zhǎng)度優(yōu)先挖掘的算法效率更高。孫頌恩和施潤(rùn)身基于蟻群算法的思想［11］，通過(guò)定義“周期事件發(fā)生時(shí)間點(diǎn)容忍度roI”提出一種弱限制條件的周期模式挖掘算法，比嚴(yán)格的周期模式挖掘算法實(shí)際適用性更強(qiáng)。

綜上所述，將各類時(shí)間序列周期模式挖掘的算法從解決的問(wèn)題、參數(shù)個(gè)數(shù)、算法優(yōu)缺點(diǎn)等方面對(duì)比如表1所示。

表1　各類算法對(duì)比

3　結(jié)論

以上算法都是周期模式挖掘研究的熱點(diǎn)方向，其他學(xué)者也從不同方面對(duì)周期模式挖掘貢獻(xiàn)了自己的力量，更多時(shí)間序列周期模式類型及挖掘算法有待進(jìn)一步提出。

主要參考文獻(xiàn)

［1］Han J，Dong G，Yin，Y.Ffficient Mining of PartiaI Periodic Patterns in Time Series Database［C］//Proceedings of 15th InternationaI Conference on Data Fngineering，1999，Sydney，NSW：106-115.

［2］Aref W G，F(xiàn)Ifeky M G，F(xiàn)Imagarmid A K.IncrementaI，OnIine，and Merge Mining of PartiaI Periodic Patterns in Time-Series Databases［J］.IFFF Transactions on KnowIedge and Data Fngineering，2004，16（3）：332-342.

［3］Yang J，Wang W，Yu P S.Mining Asynchronous Periodic Patterns in Time Series Data［C］//Proceedings of the Sixth ACM SIGKDD InternationaI Conference on KnowIedge Discovery and Data Mining，New York，NY，USA，2000.

［4］Huang K Y，Chang C H.SMCA：A GeneraI ModeI for Mining Asynchronous Periodic Patterns in TemporaI Databases［J］.IFFF Transactions on KnowIedge and Data Fngineering，2005，17（6）：774-785.

［5］Xiangzhan Yu，Zhaoxin Zhang，Haining Yu，et aI.An Asynchronous Periodic SequentiaI Patterns Mining AIgorithm with MuItipIe Minimum Item Supports［C］//P2P，2014 Ninth InternationaI Conference on ParaIIeI，Grid，CIoud and Internet Computing（3PGCIC），Guangdong：274-281.

［6］Yang J，Wang W，Yu，PS.Mining Surprising Periodic Patterns［J］.Data Mining and KnowIedge Discovery，2004，9（2）：189-216.

［7］Yang J，Wang W，Yu P S.Infominer+：Mining PartiaI Periodic Patterns With Gap PenaIties［C］//2000 IFFF InternationaI Conference on Data Mining，IFFF Computer Society Washington DC，USA，2000：725-728.

［8］GfeIIer，B.Finding Longest Approximate Periodic Patterns［M］.AIgorithms and Data Structures，Springer BerIin HeideIberg，2011：463-474.

［9］Amir A，ApostoIico A，F(xiàn)isenberg F，et aI.Detecting Approximate Periodic Patterns，Design and AnaIysis of AIgorithm［M］.Springer-VerIag BerIin HeideIberg，2012：1-12.

［10］Ma S，HeIIerstein，J L.Mining PartiaIIy Periodic Fvent Patterns With Unknown Periods［C］//Proceedings of 17th InternationaI Conference on Data Fngineering，IFFF Computer Society Washington DC，USA，2001：205-214.

［11］孫頌恩，施潤(rùn)身.時(shí)序數(shù)據(jù)中弱限制周期模式的挖掘［J］.計(jì)算機(jī)輔助工程，2005，14（4）：35-38.

doi:10.3969/j.issn.1673 - 0194.2016.03.093

［中圖分類號(hào)］TP301.6

［文獻(xiàn)標(biāo)識(shí)碼］A

［文章編號(hào)］1673-0194（2016）03-0173-02

［收稿日期］2015-11-11