基于知識粒度的時間序列異常檢測研究

楊志勇，朱躍龍，萬定生

(河海大學 計算機與信息學院，江蘇 南京 210098)

基于知識粒度的時間序列異常檢測研究

楊志勇，朱躍龍，萬定生

(河海大學 計算機與信息學院，江蘇 南京 210098)

時間序列的異常檢測多以相似性分析方法來處理，時間代價高昂。為減少異常檢測的時間，文中圍繞知識粒度方法進行研究與探討。知識粒度在數據異常檢測中應用廣泛，但在時間序列的異常檢測上應用較少。文中針對時間序列上下文相關異常(點)檢測，提出利用知識粒度異常檢測方法對于輸入屬性越多檢測粒度越細的特性，來查找時間序列中的異常數據。實驗證明，基于知識粒度的方法無需先驗信息，在整個處理過程中無需事先分析歷史數據，而是通過屬性間的組合粒度來劃分異常數據與正常數據，提高了異常檢測的效率。知識粒度方法在不確定信息處理研究中的表現十分突出，文中將知識粒度在時間序列異常檢測中進行應用嘗試，為時間序列異常檢測提供了一種新的思路。

時間序列；知識粒度；粗糙集；異常檢測

0 引 言

異常檢測也稱為異常挖掘或離群檢測[1]，是從大量數據中提取隱含在其中的人們事先不知道的但又潛在有用的信息和知識的過程。異常檢測中包含時間序列和非時間序列的檢測。非時間序列的異常檢測主要用于發(fā)現異常點集，數據之間無先后順序，眾多學者已經對非時間序列數據進行了深入研究，常用的檢測方法有基于距離的方法[2-3]、基于統(tǒng)計的方法[4-5]、基于偏離的方法[6]、基于聚類的方法[7]和基于密度的方法[8]。而時間序列各個點數據有先后順序，有邏輯關系與遞推關系，時間序列的異常檢測難度極大，不能單純通過距離、密度等方法進行處理[9]。時間序列異常的挖掘，需要同時考慮幾年甚至幾十年跨度的數據[10]。

目前，時間序列異常檢測的研究分為三類：一是時間序列上下文相關異常(點)檢測；二是時間序列模式(子序列)異常檢測；三是時間序列異常周期檢測。

文中方法針對時間序列上下文相關異常(點)檢測，主要是檢測出時間序列中和上下文信息明顯偏離的個體(點異常)。

粒計算作為人工智能領域新興起的一個研究方向，是一種新的不確定信息處理方法[11]。粒計算通過粗糙集模型將論域的劃分視作知識，知識粒度則是其重要的度量工具。基于知識粒度的常規(guī)異常檢測方法是通過單個數據的存在與否對知識粒度的影響來度量數據的異常，如果直接使用此方法處理時間序列異常，則會因為時間序列屬性的單一性而變成了類似前面提到的基于距離的異常、基于密度的異常等傳統(tǒng)方法，從而無法正確檢測出異常。但是，根據知識粒度異常檢測屬性越多知識粒度越小[12]的特點以及時間序列往往會伴隨多條與之相關的時間序列的特點，在多條相關聯時間序列的伴隨下，可以使用基于知識粒度的異常檢測方法。

文中利用知識粒度異常檢測方法對于輸入屬性越多檢測粒度越細的特性，查找時間序列中的點異常[13]。根據知識粒度檢測方法對輸入數據不要求數據以外的任何先驗信息的優(yōu)點，提高時間序列異常檢測算法的效率，時間復雜度為O(m*n)[12]。

1 知識粒度

粒計算是一種新型的不確定性信息處理方法，其基本思想是利用不同粒度上的信息進行問題求解。粒計算的一個重要模型為粗糙集，粗糙集理論的要點是將分類與知識聯系在一起，并用等價關系形式化表示分類，每個等價類稱為一個知識粒[14]。知識粒有粗有細，為了度量等價類的粗細程度，因而有了知識粒度。知識粒度可以描述知識的區(qū)分能力，知識粒度越小，它的區(qū)分能力越強[15]。應用知識粒度區(qū)分知識的能力，可以檢測出數據中的異常。下面介紹知識粒度在異常檢測應用中的相關定義與定理[16]：

(2)設IS=(U,A,V,f)是一個信息系統(tǒng)，P,Q?A，若對任意u,v∈U,有u(U/P)v?u(U/Q)v，則稱U/P與U/Q相等，記為U/P=U/Q。

(3)設IS=(U,A,V,f)是一個信息系統(tǒng)，P,Q?A，若對任意u,v∈U,有u(U/P)v?u(U/Q)v，則稱U/P比U/Q細，記為U/P≤U/Q。

(4)設IS=(U,A,V,f)是一個信息系統(tǒng)，P,Q?A，若對任意u,v∈U,有U/P≤U/Q且U/P≠U/Q，則稱U/P比U/Q嚴格細，記為U/P

(5)設IS=(U,A,V,f)是一個信息系統(tǒng)，U/A={X1,X2,…,Xm}，A的知識粒度記為KG(A)：

式中，|IND(A)|表示IND(A)∈U*U的基數，展開后如下式：

(1)

定理1:設IS=(U,A,V,f)是一個信息系統(tǒng)，P,Q?A，若P?A，則KG(P)≤KG(Q)。

因此，KG(P)≤KG(Q)得證。

從定理1可知，信息系統(tǒng)中，屬性越多，知識粒度就越小，區(qū)分能力就越強。

2 基于知識粒度的時間序列異常檢測

2.1 檢測方法定義

知識粒度是測量粗糙集理論中不確定信息的方法，在許多領域中都得到了應用，特別是機器學習與數據挖掘等，在非時間序列的異常檢測中國內外也有過研究，但對于時間序列的異常檢測研究卻極少關注。

文中通過時間序列數據的連續(xù)性、關聯性等特性，將時間序列異常檢測問題轉化為非時間序列異常檢測問題。主要思想為將時間序列中不該在某個時間點出現的數據異常通過調整等價函數轉化為非時間序列的離群異常。下面給出加入調整時間序列等價函數定義以及異常結果判定定義：

定義1：設IS=(U,A,V,F)是一個信息系統(tǒng)，A={a1,a2,…,am}，其中，a1,a2,…,am分別為多條隨時間變化且相互有關聯的時間序列屬性。

定義2：設IS=(U,A,V,F)是一個信息系統(tǒng)，A={a1,a2,…,am}，F={f1,f2,…,fm}，在一個等價關系IND(B)中，x,y∈IND(B)，有fa1(x)=fa1(y),fa2(x)=fa2(y),…,fam(x)=fam(y)。

定義8：設IS=(U,A,V,F)是一個信息系統(tǒng)，v為設定的一個閾值，對?x∈U，若KOF(x)>v，則x為一個異常對象。

2.2 算法描述

根據上述檢測方法中的相關定義，基于知識粒度的時間序列異常檢測算法可以分為以下幾個步驟：

(1)將多條相關的時間序列屬性按照定義1、2構造出信息系統(tǒng)，設為IS=(U,A,V,F)。

(2)根據定義2中的等價函數，循環(huán)A中屬性，設定時間序列多條屬性等價區(qū)間。同時劃分出知識U/IND({Ai})，并計算出知識粒度KG({Ai})。

(4)令x=0～m循環(huán)S中屬性a，j=0～n嵌套循環(huán)U中對象x，劃分出去除xj后的知識U/INDxj({ai})，并計算出知識粒度KGxj({ai})。

(10)根據定義8計算對象xj的異常度KOF(xj)，查找大于閾值v的異常對象。

(11)輸出結果集。

算法將時間序列異常問題描述為非時間序列異常問題，重點是時間序列屬性的搭配和等價函數定義。

3 實例分析

文中以水文時間序列片段樣本數據為例，取同一水利設施同一時間段內水庫水位a、降雨量b、河道水位c的時間序列數據，如表1所示。

表1 時間序列信息系統(tǒng)

其中，設定檢測閾值v=0.5，等價函數分別為：

fa(x)=?x/15」,fb(x)=?x/5」,fc(x)=?x/2」

接下來根據算法步驟，進行單屬性知識的劃分：

U/IND(a)={{x1,x3,x4},{x2,x7},{x5,x6}}

U/IND(b)={{x1,x2,x3},{x4,x5,x6,x7}}

U/IND(c)={{x1,x2,x3},{x4,x5,x6,x7}}

知識粒度為：

KG({a})=(3×3+2×2+2×2)/(7×7)=0.347

KG({b})=(3×3+4×4)/(7×7)=0.510

KG({c})=(3×3+4×4)/(7×7)=0.510

得到S={c,b,a}。

再計算劃分去除xj后的知識粒度：

KGx1(c)=KGx2(c)=KGx3(c)=0.408

KGx4(c)=KGx5(c)=KGx6(c)=KGx7(c)=0.367

KGx1(b)=KGx2(b)=KGx3(b)=0.408

KGx4(b)=KGx5(b)=KGx6(b)=KGx7(b)=0.367

KGx1(a)=KGx3(a)=KGx4(a)=0.286

KGx2(a)=KGx7(a)=0.286

KGx5(a)=KGx6(a)=0.286

Wx1({c})=Wx2({c})=Wx3({c})=0.571

Wx4({c})=Wx5({c})=Wx6({c})=Wx7({c})= 0.429Wx1({b})=Wx2({b})=Wx3({b})=0.571

Wx4({b})=Wx5({b})=Wx6({b})=Wx7({b})= 0.429

Wx1({a})=Wx3({a})=Wx4({a})=0.571

Wx2({a})=Wx7({a})=Wx5({a})=Wx6({a})= 0.714

進而根據步驟6構造AS序列，如下:

AS={{a,b,c},{a,b},…,{a}}

使用上一步同樣方法劃分并計算知識粒度，得：

U/IND(A1)={{x1,x3},{x2},{x4},{x5,x6}, {x7}}

U/IND(A2)={{x1,x3},{x2},{x4},{x5,x6}, {x7}}

U/IND(A3)={{x1,x3,x4},{x2,x7},{x5,x6}}

然后計算劃分去除xj后的知識粒度：

KGx1(A1)=KGx3(A1)=0.163

KGx2(A1)=KGx4(A1)=KGx7(A1)=0.204

KGx5(A1)=KGx6(A1)=0.163

KGx1(A2)=KGx3(A2)=0.163

KGx2(A2)=KGx4(A2)=KGx7(A2)=0.204

KGx5(A2)=KGx6(A2)=0.163

KGx1(A3)=KGx3(A3)=KGx4(A3)=0.245

KGx2(A3)=KGx7(A3)=0.286

KGx5(A3)=KGx6(A3)=0.286

最后根據以上結果計算KOF(xj)，如表2所示。

表2 KOF計算結果

通過表2可以看出，對象x2被發(fā)現為異常，其水位109在時間序列中是不應該發(fā)生的，在整個處理過程中并沒有分析其周圍的數據,而是通過屬性間的組合粒度來劃分異常數據與正常數據。

4 結束語

文中研究內容為時間序列的異常檢測提供了一種新的思路，將知識粒度異常檢測方法應用在時間序列的點異常檢測上。然而時間序列的異常檢測還包括子序列異常與周期異常，在下一步的研究中，應更加充分利用知識粒度在確定性數據處理上的優(yōu)勢，解決更多時間序列異常檢測的問題。

[1]ChandolaV,BanerjeeA,KumarV.Anomalydetection:asurvey[J].ACMComputingSurveys,2009,41(3):1-15.

[2]RamaswamyS,RastogiR,ShimK.Efficientalgorithmsforminingoutliersfromlargedatasets[J].ACMSigmodRecord,2000,29(2):427-438.

[3]HaoY,WangB,GangX,etal.Distance-basedoutlierdetectiononuncertaindata[C]//ProcofIEEEinternationalconferenceoncomputerandinformationtechnology.[s.l.]:IEEE,2009:293-298.

[4]RousseeuwPJ,LeroyAM.Robustregressionandoutlierdetection[M].[s.l.]:JohnWiley&Sons,2005.

[5]JohnsonT,KwokI.Fastcomputationof2-dimensionaldepthcontours[C]//Procofthe4thinternationalconferenceonknowledgediscoveryanddatamining.NewYork:ACMPress,1998:224-228.

[6]JagadishHV,KoudasN,MuthukrishnanS.Miningdeviantsinatimeseriesdatabase[C]//Proceedingsofinternationalconferenceonverylargedatabases.Edinburgh,Scotland,UK:[s.n.],1999:102-113.

[7]BudalakotiS,SrivastavaA,AkellaR,etal.Anomalydetectioninlargesetsofhigh-dimensionalsymbolsequences[R].MoffettField:NASAAmesResearchCenter,2006.

[8]BreunigM,KriegelH,NgRT,etal.LOF:identifyingdensity-basedlocaloutliers[C]//ProceedingsoftheACMSIGMODinternationalconferenceonmanagementofData.[s.l.]:ACM,2000:93-104.

[9] 陳運文,吳 飛,吳廬山,等.基于異常檢測的時間序列研究[J].計算機技術與發(fā)展,2015,25(4):166-170.

[10] 林 森.時間序列異常檢測的研究與應用[D].南京:河海大學,2008.

[11] 苗奪謙,王國胤,劉 清,等.粒計算:過去、現在與展望[M].北京:科學出版社,2007.

[12] 陳玉明,吳克壽,孫金華.基于知識粒度的異常數據挖掘算法[J].計算機工程與應用,2012,48(4):118-120.

[13] 肖 輝.時間序列的相似性查詢與異常檢測[D].上海:復旦大學,2005.

[14] 王國胤.Rough集理論與知識獲取[M].西安：西安交通大學出版社,2001.

[15] 李道國,苗奪謙,張紅云.粒度計算的理論、模型與方法[J].復旦學報：自然科學版,2004,43(5):837-841.

[16] 苗奪謙,范世棟.知識的粒度計算及其應用[J].系統(tǒng)工程理論與實踐,2002,22(1):48-56.

Research on Time Series Anomaly Detection Based on Knowledge Granularity

YANG Zhi-yong，ZHU Yue-long，WAN Ding-sheng

(College of Computer and Information,Hohai University,Nanjing 210098,China)

Most of the time series’ anomaly detections are processed with the similarity analysis,and their time complexity is rather high.In order to reduce the time of anomaly detection,it studies and discusses the method of knowledge granularity in this paper.Knowledge granularity is widely applied in the anomaly detection of data,but rarely used in anomaly detection on time series.In view of context dependent anomaly (point) detection in time series,the knowledge-granularity-based anomaly detection is proposed to search the anomalous data in time series,in which the more the attributes are,the finer the detection granularity is.Experiments show that the method based on knowledge granularity does not require a priori information,partition of the abnormal data and normal data through the combination of the attributes without analysis of historical data previously,and the efficiency of anomaly detection has been improved.The knowledge granularity method is very prominent in the research of uncertain information processing.It tries to apply the knowledge granularity in the anomaly detection of time series in this paper,thus to provide a new approach for anomaly detection of time series.

time series;knowledge granularity;rough set;anomaly detection

2015-09-27

2016-01-06

時間：2016-06-22

國家科技支撐計劃課題(2015BAB07B01)；水利部公益性行業(yè)科研專項(201501022)

楊志勇(1990-)，男，碩士研究生，研究方向為數據挖掘；朱躍龍，教授，博士生導師，研究方向為水信息學、智能信息處理；萬定生，教授，CCF會員，研究方向為信息處理與信息系統(tǒng)。

http://www.cnki.net/kcms/detail/61.1450.TP.20160621.1701.012.html

TP31

A

1673-629X(2016)07-0051-04

10.3969/j.issn.1673-629X.2016.07.011