一種改進(jìn)的時(shí)間序列特征模式提取方法研究

史震

摘 要：傳統(tǒng)的時(shí)間序列特征模式提取算法，在基于前綴檢索的基礎(chǔ)上引入了項(xiàng)集間隔約束的思想，優(yōu)化了特征模式提取的質(zhì)量。本文在此基礎(chǔ)上引入了跨度閾值，對(duì)模式候選集進(jìn)行了深度的剪紙及優(yōu)化，有效提高了特征模式的挖掘質(zhì)量。通過(guò)實(shí)驗(yàn)結(jié)果證明，特征模式質(zhì)量改善明顯。

關(guān)鍵詞：時(shí)間序列；特征模式；跨度閾值

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-2064（2017）08-0254-01

隨著大數(shù)據(jù)時(shí)代的到來(lái)，時(shí)間序列方面的研究也逐步被重視并占據(jù)著重要的的地位。賈艷芳等人提出的基于改進(jìn)的PrefixSpan算法[1]對(duì)序列化數(shù)據(jù)進(jìn)行特征模式提取，其融入了MPP算法的思想，使其可以對(duì)單序列數(shù)據(jù)進(jìn)行模式挖掘。該方法充分利用了序列的原始特性，但提取的模式候選集中序列之間的部分屬性存在較大的偏差，因此可信度較低，模式的特征性不強(qiáng)。

在單序列特征模式提取問(wèn)題中，為了提高模式的可信度，謝飛等人提出了MAIL算法，該算法引入了項(xiàng)集間隔約束思想，從而避免了候選集中序列項(xiàng)集間隔的較大差異，在模式質(zhì)量方面有所改善和提高。但在滿(mǎn)足序列自身項(xiàng)集間隔約束的同時(shí)并未對(duì)序列之間跨度差異進(jìn)行限定，因此在部分特征模式候選集中序列與序列之間的跨度差異較大，抗干擾性較弱，影響特征模式質(zhì)量。

本文在前人算法的基礎(chǔ)上引入了跨度閾值約束機(jī)制，通過(guò)模式候選集的模式過(guò)濾，優(yōu)化了特征模式的提取。經(jīng)驗(yàn)證，提取的特征模式質(zhì)量得以顯著改善。

1 序列特征模式提取

1.1 跨度閾值

定義：跨度閾值。目標(biāo)序列S中，模式P匹配到的所有序列位置組成模式候選集M。在候選集M中，每一個(gè)序列都對(duì)應(yīng)一個(gè)跨度值L，在候選集總的跨度值中選取該集合中位數(shù)，記為MI，與MI差值的絕對(duì)值滿(mǎn)足自給定約束范圍的序列記為可用序列。其中，自給定約束范圍即為跨度閾值。

不同的跨度閾值對(duì)特征模式提取的影響不同，因此可以靈活的按需提取不同精度的特征模式，從而發(fā)現(xiàn)模式的潛在特性，細(xì)粒度化的提高特征模式質(zhì)量。

1.2 特征性判定

序列中滿(mǎn)足設(shè)定支持度的模式即為特征模式，由于序列本身周期性特點(diǎn)以及其中較多孤立干擾點(diǎn)的存在，其挖掘出的特征模式候選集中的序列之間存在互相重疊的特性，若重疊率較高，在一定程度上會(huì)影響特征模式的質(zhì)量，致使特征模式的特征性不明顯。

為了定性的表征特征模式的該特性，可以通過(guò)如下公式來(lái)計(jì)算得出，計(jì)算公式為：

其中，分母為特征模式候選集中所有序列的總跨度之和，分子為候選集中所有子序列段的跨度乘以其權(quán)重之和，其中權(quán)重為該重疊子序列個(gè)數(shù)的倒數(shù)，η的取值范圍在[0，1]之間。該值作為特征模式質(zhì)量參考值可以在一定程度上有效的判定出特征模式獨(dú)特性的強(qiáng)弱。

2 模式候選集結(jié)構(gòu)的改進(jìn)

模式候選集用以模式的擴(kuò)展，記錄匹配序列在目標(biāo)序列中出現(xiàn)的位置信息，并以首字符位置作為該模式匹配序列的索引標(biāo)記。為了保證模式的完備性和一致性，模式候選集采用如下數(shù)據(jù)結(jié)構(gòu)（模式候選集結(jié)構(gòu)（部分）見(jiàn)表1）。

由以前基于前綴式的檢索方式改為基于首字符位置的內(nèi)外混合式搜索方式。外部搜索加快了對(duì)模式位置的定位，內(nèi)部搜索實(shí)現(xiàn)了對(duì)特征模式的跨度閾值檢測(cè)。

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

3.1 實(shí)驗(yàn)環(huán)境

所有算法運(yùn)行在Pentium Dual CPU 3.0GHz，內(nèi)存為2GB的計(jì)算機(jī)上，使用JDK1.7開(kāi)發(fā)環(huán)境實(shí)現(xiàn)。

3.2 數(shù)據(jù)來(lái)源及預(yù)處理

數(shù)據(jù)源采用提供的來(lái)自不同領(lǐng)域的3條時(shí)間序列的實(shí)際數(shù)據(jù)集：Ocean、Burstin和Advertisement，序列長(zhǎng)度均為12000。

3.3 實(shí)驗(yàn)對(duì)比分析

跨度閾值的引入對(duì)特征模式的提取質(zhì)量產(chǎn)生很大的影響，從提取的特征模式數(shù)量、特征η值這兩個(gè)方面進(jìn)行對(duì)比。實(shí)驗(yàn)參數(shù)：跨度閾值約束等級(jí)分為5和10，項(xiàng)集間隔約束采用g=[0，4]，支持度support=20。

經(jīng)實(shí)驗(yàn)驗(yàn)證，隨著跨度閾值約束逐漸增強(qiáng)，序列中提取出的特征模式數(shù)量較以往算法有明顯減少，但特征模式的特征η值均值有顯著提高，這表明特征模式候選集中序列之間的重疊率下降，特征模式的特征性和可信度得到明顯加強(qiáng)和提高。例如Ocean序列數(shù)據(jù)集，以往算法所提取的特征模式的特征η值均值僅為18.4%和42.1%，可見(jiàn)其中特征模式候選集中序列之間的重疊率較高，而改進(jìn)算法的特征性均值提升至77.1%，在一定程度上剪去了重疊率較高的特征模式，突出了特征模式的特征性。

4 結(jié)語(yǔ)

跨度閾值的引入，一方面限定特征模式候選集中序列間跨度的差異，降低了特征模式候選集中序列之間的重疊率，提高了特征模式質(zhì)量；另一方面提供了一種將特征模式的特征性進(jìn)行細(xì)粒度劃分的方式，為更深入的理解序列特征模式提供了依據(jù)。

參考文獻(xiàn)

[1]Pei J， Han J， Mortazavi-Asl B， et al. Prefixspan： Mining sequential patterns efficiently by prefix-projected pattern growth[C]//icccn. IEEE，2001：0215.