基于時序數據的top-k時間區間對比序列模式挖掘算法

晏力

（四川大學計算機學院，成都 610065)

YAN Li

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

基于時序數據的top-k時間區間對比序列模式挖掘算法

晏力

（四川大學計算機學院，成都 610065)

隨著物聯網技術的發展，現在越來越多的傳感器被應用于人們的生活中，由此產生大量的時間序列數據。正是因為數據的爆炸式增長，人們迫切地希望從大量時間序列數據中發現有用的模式。目前已經有大量的序列模式分析算法應用到時序數據上。設計并實現一個應用到時序數據的top-k時間區間對比挖掘算法。

時間序列；對比挖掘；top-k

0 引言

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

在時間序列數據集上的對比序列模式挖掘正被越來越多的學者所關注。同時在這些算法與實際生產相結合的時候，用戶往往希望自定義一些時間區間，并希望能得到在這些時間區間上的模式的顯著度。本文正是基于上述用戶實際需求，開發了一個基于固定時間區間的top-k對比挖掘算法。

1 問題定義

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

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

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

時間延遲約束r被規定為兩個非負整數，形式為r =[rmin，rmax]，滿足條件0≤rmin≤rmax≤T。

給定一個時間序列S、事件類型序列E、時間窗口W和時間延遲約束r，如果存在著整數1≤k1〈k2〈…〈k|E|≤|S|，使得他們之間滿足如下兩個條件：（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]。那么我們說這是一個匹配，記為例如：給定 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。有此可見，對于事件類型序列E，我們可以得到這樣一個匹配

有了上面的匹配的定義，我們可以給出類似于傳統序列數據挖掘頻繁模式支持度的概念。這里我們注意到，因為我們使用了固定時間區間的定義，那么我們的模式定義為一個二元組（E，W），其中E為事件類型序列，W為一個時間窗口。那么在數據集D上，給定一個事件類型序列E在時間窗口W中，滿足時間延遲約束r的支持度記為Sup（D，（E，W））。具體公式如下：

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

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

本文的目的就是要在兩組時序數據集D+/D-中挖掘出對比度最高的top-k個WCTP模式。

2 算法實現

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

算法1：WCTP-Miner算法框架

輸入：D+：正例數據集，D–：負例數據集，k：top-k，r：時間延遲約束，Ω：用戶指定相鄰的時間區間集合

輸出：R：top-k WCTP結果集

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

3： 根據Ω，選擇使得對比度最高的W

4： if（E，W）的優先級屬于最高的top-k個then

5： 更新R；

6： end if

7：end for

8：return R；

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

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

對于步驟二，因為我們的候選時間窗口以根據用戶給定的Ω根據組合直接得到，那么本文的任務就是在候選集中找出使得對比度最高的W。通過研究我們給出了如下剪枝。

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

3 算法實驗

本文采用了在UCI機器學習庫中的在線零售數據集[3]作為實驗數據集，該數據集記錄了一個網上零售商店的交易記錄，我們采用該商店2011/02的交易數據作為正列數據集D+，2011/01的交易數據作為負列數據集D-，且Ω為每個時間作為元素，r以10分鐘作為跨度。表1展示了使用本算法挖掘出的top-5 WCTPs。

4 結語

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

表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－），男，四川大學計算學院研究生

2017－03－16

2017－03－20

YAN Li

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