晏力

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065)

YAN Li

（College of Computer Science，Sichuan University，Chengdu 610065）

基于時(shí)序數(shù)據(jù)的top-k時(shí)間區(qū)間對(duì)比序列模式挖掘算法

晏力

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065)

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，現(xiàn)在越來(lái)越多的傳感器被應(yīng)用于人們的生活中，由此產(chǎn)生大量的時(shí)間序列數(shù)據(jù)。正是因?yàn)閿?shù)據(jù)的爆炸式增長(zhǎng)，人們迫切地希望從大量時(shí)間序列數(shù)據(jù)中發(fā)現(xiàn)有用的模式。目前已經(jīng)有大量的序列模式分析算法應(yīng)用到時(shí)序數(shù)據(jù)上。設(shè)計(jì)并實(shí)現(xiàn)一個(gè)應(yīng)用到時(shí)序數(shù)據(jù)的top-k時(shí)間區(qū)間對(duì)比挖掘算法。

時(shí)間序列；對(duì)比挖掘；top-k

0 引言

序列數(shù)據(jù)是一種重要的數(shù)據(jù)類型，這種數(shù)據(jù)類型常常出現(xiàn)在很多領(lǐng)域，如科學(xué)、醫(yī)學(xué)、商業(yè)、安全和其他應(yīng)用領(lǐng)域。而序列模式是序列數(shù)據(jù)挖掘中必不可少的任務(wù)，而序列模式中的對(duì)比序列模式[1]是一種比較熱門的模式，近年來(lái)引起了學(xué)術(shù)界的廣泛關(guān)注。對(duì)比序列模式（又稱為顯著序列模式）是指在一個(gè)序列數(shù)據(jù)集中頻繁出現(xiàn)，而在另外一個(gè)序列數(shù)據(jù)集中不頻繁出現(xiàn)的模式。對(duì)比序列模式主要是反映了兩個(gè)或多個(gè)序列數(shù)據(jù)集的差異性，可以用來(lái)理解和識(shí)別這些數(shù)據(jù)集的信息特征，因此可以用于個(gè)性化推薦、基因數(shù)據(jù)分類和異常探測(cè)等。目前，對(duì)比序列模式被應(yīng)用到了聚類、分類、預(yù)測(cè)等數(shù)據(jù)挖掘任務(wù)中。

在時(shí)間序列數(shù)據(jù)集上的對(duì)比序列模式挖掘正被越來(lái)越多的學(xué)者所關(guān)注。同時(shí)在這些算法與實(shí)際生產(chǎn)相結(jié)合的時(shí)候，用戶往往希望自定義一些時(shí)間區(qū)間，并希望能得到在這些時(shí)間區(qū)間上的模式的顯著度。本文正是基于上述用戶實(shí)際需求，開(kāi)發(fā)了一個(gè)基于固定時(shí)間區(qū)間的top-k對(duì)比挖掘算法。

1 問(wèn)題定義

那么現(xiàn)在我們從基礎(chǔ)的定義開(kāi)始。時(shí)間序列就是在字符序列數(shù)據(jù)的基礎(chǔ)上多了一個(gè)時(shí)間屬性，這種數(shù)據(jù)主要由傳感器接收到的事件組成，所以我們可以定義時(shí)間序列的基本元素為一個(gè)事件event，定義為一個(gè)二元組（e，t），e代表一個(gè)事件類型，t代表時(shí)間戳（時(shí)間戳可以是絕對(duì)時(shí)間和相對(duì)時(shí)間，為了方便，本文時(shí)間戳為非負(fù)整數(shù)）。我們定義表示數(shù)據(jù)集中所有事件類型的總表，T代表數(shù)據(jù)集的最大時(shí)間戳。一個(gè)時(shí)間序列S是一系列按照時(shí)間戳升序排列的事件列表，

其中ei∈E，ti∈[0，T]，且ti≤tj（1≤i〈j≤n）。對(duì)于事件時(shí)間序列S我們定義它的長(zhǎng)度為它所包含的事件個(gè)數(shù)，記為|S|。我們指定S[i]（1≤i≤|S|）表示在事件時(shí)間序列S中的第i個(gè)事件元素。對(duì)于S[i]，我們使用S[i].e來(lái)表示事件類型，S[i].t來(lái)表示與事件類型相關(guān)聯(lián)的時(shí)間戳。 例如：給定S=〈（e1，0），（e2，10），（e3，30），（e4，40）〉，可知|S|=4，S[2]=（e2，10），S[2].e=e2，S[2].t=10。

事件類型序列E是一個(gè)事件類型的有序序列，格式為E=〈e1，e2，…，en〉，其中ei（1≤i≤n）；如果存在著整數(shù)1≤k1〈k2〈…〈k|E′|≤|E|，使得E′=〈E[k1]，E[k2]，…，E [kn]〉，那么我們稱E是E′的超序，記為E′?E。例如〈e1，e2，e3，e4〉是〈e2，e4〉的超序。

時(shí)間延遲約束r被規(guī)定為兩個(gè)非負(fù)整數(shù)，形式為r =[rmin，rmax]，滿足條件0≤rmin≤rmax≤T。

給定一個(gè)時(shí)間序列S、事件類型序列E、時(shí)間窗口W和時(shí)間延遲約束r，如果存在著整數(shù)1≤k1〈k2〈…〈k|E|≤|S|，使得他們之間滿足如下兩個(gè)條件：（1）1≤i≤ |E|，滿足S[ki].e=E[i]，W.ts≤S[ki].t≤W.te；（2）1≤j≤|E|-1，滿足S[kj+1].t-S[kj].t∈[rmin，rmax]。那么我們說(shuō)這是一個(gè)匹配，記為例如：給定 S=〈（e1，0），（e2，10），（e3，30），（e4，40）〉，E=〈e2，e3〉，r=[0，20]和W=[0，30]，其中 S[2].e=E[1]=e2，S[3].e=E[2]=e3，且 S[2].t≥0，S[3].t≤30，S[2].t-S[3].t∈r。有此可見(jiàn)，對(duì)于事件類型序列E，我們可以得到這樣一個(gè)匹配

有了上面的匹配的定義，我們可以給出類似于傳統(tǒng)序列數(shù)據(jù)挖掘頻繁模式支持度的概念。這里我們注意到，因?yàn)槲覀兪褂昧斯潭〞r(shí)間區(qū)間的定義，那么我們的模式定義為一個(gè)二元組（E，W），其中E為事件類型序列，W為一個(gè)時(shí)間窗口。那么在數(shù)據(jù)集D上，給定一個(gè)事件類型序列E在時(shí)間窗口W中，滿足時(shí)間延遲約束r的支持度記為Sup（D，（E，W））。具體公式如下：

也就是（E，W）在數(shù)據(jù)集D中的匹配的數(shù)量與數(shù)據(jù)集的大小的比值。這樣我們可以給出對(duì)比度的定義：CR（E，W）=Sup（D+，（E，W））-Sup（D-，（E，W））。那么，我們可以給出本文模式的準(zhǔn)確定義。

定義1（時(shí)間區(qū)間對(duì)比模式WCTP）。在給定兩個(gè)時(shí)序數(shù)據(jù)集D+/D-，事件類型序列E，時(shí)間窗口W，在時(shí)間延遲約束r下，一個(gè)模式（E，W）是一個(gè)時(shí)間區(qū)間對(duì)比模式，那么該模式滿足條件：（1）CR（E，W）〉0；（2）不存在W′使得（E，W′）滿足條件一，且a.CR（E，W′）〉CR（E，W）或CR（E，W′）=CR（E，W），且||W′||〈||W||。

本文的目的就是要在兩組時(shí)序數(shù)據(jù)集D+/D-中挖掘出對(duì)比度最高的top-k個(gè)WCTP模式。

2 算法實(shí)現(xiàn)

本文提出的算法WCTP-Miner主要用來(lái)在正負(fù)列數(shù)據(jù)集D+/D-中，找出給定的時(shí)間窗口W下滿足時(shí)間延遲約束r的top-k WCTP。其中WCTP是一個(gè)二元組（E，W），相對(duì)于之前的對(duì)比序列挖掘，本算法不僅要枚舉出所有的候選事件類型E，而且需要找到使得E的對(duì)比度最高的時(shí)間窗口W。所以WCTP算法的主要分為三個(gè)步驟a.生成候選事件類型E，b.選出候選時(shí)間窗口W，使得CR（E，W）最大，c.更新結(jié)果集R。算法1給出了本文的算法框架。

算法1：WCTP-Miner算法框架

輸入：D+：正例數(shù)據(jù)集，D–：負(fù)例數(shù)據(jù)集，k：top-k，r：時(shí)間延遲約束，Ω：用戶指定相鄰的時(shí)間區(qū)間集合

輸出：R：top-k WCTP結(jié)果集

1：for從事件類型序列候選集中選取一個(gè)E do

3： 根據(jù)Ω，選擇使得對(duì)比度最高的W

4： if（E，W）的優(yōu)先級(jí)屬于最高的top-k個(gè)then

5： 更新R；

6： end if

7：end for

8：return R；

對(duì)于步驟一，為了能系統(tǒng)且無(wú)缺失的選出所有的事件類型序列候選集，本算法采用了在對(duì)比序列挖掘常用的集合枚舉樹(shù)[2]。在枚舉樹(shù)上，我們提出了如下剪枝條件：

剪枝條件1 給定事件類型序列E，如果Sup（D+，（E，[0，T]））〈CRk（CRk表示當(dāng)結(jié)果集中最小的第k個(gè)的對(duì)比度），那么在枚舉樹(shù)上，以該E為根的枚舉樹(shù)都會(huì)被剪掉。

對(duì)于步驟二，因?yàn)槲覀兊暮蜻x時(shí)間窗口以根據(jù)用戶給定的Ω根據(jù)組合直接得到，那么本文的任務(wù)就是在候選集中找出使得對(duì)比度最高的W。通過(guò)研究我們給出了如下剪枝。

剪枝條件2 如果時(shí)間窗口W滿足Sup（D+，（E，W））〈CRk，那么對(duì)于?W′?W，我們都可以直接減去這個(gè)時(shí)間窗口W′。

3 算法實(shí)驗(yàn)

本文采用了在UCI機(jī)器學(xué)習(xí)庫(kù)中的在線零售數(shù)據(jù)集[3]作為實(shí)驗(yàn)數(shù)據(jù)集，該數(shù)據(jù)集記錄了一個(gè)網(wǎng)上零售商店的交易記錄，我們采用該商店2011/02的交易數(shù)據(jù)作為正列數(shù)據(jù)集D+，2011/01的交易數(shù)據(jù)作為負(fù)列數(shù)據(jù)集D-，且Ω為每個(gè)時(shí)間作為元素，r以10分鐘作為跨度。表1展示了使用本算法挖掘出的top-5 WCTPs。

4 結(jié)語(yǔ)

本文在以往的對(duì)比時(shí)序挖掘的基礎(chǔ)上提出了在用戶指定時(shí)間區(qū)間上的對(duì)比序列模式挖掘。從表1可以看出，在挖掘出的對(duì)比模式中，帶有用戶規(guī)定的時(shí)間區(qū)間。如模式E2的語(yǔ)義為在時(shí)間12點(diǎn)到16點(diǎn)之間，交易事件〈粉色茶杯茶托〉的2月與1月的對(duì)比中對(duì)比度為0.875。這在一定的程度上增加了對(duì)比模式的語(yǔ)義，同時(shí)用戶自定義的時(shí)間區(qū)間也更能符合用戶的需要，具有一定的實(shí)際意義。挖掘出的模式，也有助于用戶解釋模式所蘊(yùn)含的意義。

表1

[1]Dong，G.，Bailey，J.（eds.）:Contrast Data Mining:Concepts，Algorithms，and Applications.CRC Press，Boca Raton（2013）

[2]Rymon，R.:Search Through Systematic Set Enumeration.In:Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning，KR，pp.539－550，（1992）

[3]Dr Daqing Chen，Director:UCI Machine Learning Repository，（2015）

Mining Top-k Contrast Time Interval Sequential Patterns from Time Sequences

Nowadays，with the development of Internet of Thing technology，more and more sensors have been applied in people′s life，so a lot of time sequences data has been produced.Because the explosion of time sequences data，people want to find useful pattern from time sequences data urgently.There are a lot of sequential patterns analysis algorithms are applied to the time sequences data.Designs and implements an algorithm of mining top-k contrast time interval sequential patterns from time sequences.

Time Sequence;Contrast Mining;Top-k

1007-1423（2017）09-0028-03

10.3969/j.issn.1007-1423.2017.09.007

晏力（1988－），男，四川大學(xué)計(jì)算學(xué)院研究生

2017－03－16

2017－03－20

YAN Li

（College of Computer Science，Sichuan University，Chengdu 610065）