何奇峰

（北京郵電大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 海淀 100876）

時(shí)空異常值檢測(cè)的研究

何奇峰

（北京郵電大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 海淀 100876）

異常值檢測(cè)是數(shù)據(jù)挖掘研究領(lǐng)域的一個(gè)相當(dāng)重要的分支，異常值檢測(cè)的目的是尋找與其他大多數(shù)對(duì)象不同的個(gè)體，又常被稱為離群檢測(cè)或者是例外挖掘。許多文獻(xiàn)已經(jīng)對(duì)空間異常值檢測(cè)和時(shí)間序列異常值的檢測(cè)進(jìn)行了研究，然而同時(shí)對(duì)時(shí)間維度和空間維度進(jìn)行異常值偵測(cè)的還不多；本文將分別從時(shí)間和空間這兩個(gè)維度出發(fā)對(duì)異常值的檢測(cè)進(jìn)行研究，然后再將這兩個(gè)維度結(jié)合起來(lái)，提出一種全新的時(shí)空異常值的檢測(cè)方法，為未來(lái)時(shí)空異常值的檢測(cè)奠定基礎(chǔ)。

異常值檢測(cè)；數(shù)據(jù)挖掘；voronoi圖；k-means聚類

本文著錄格式：何奇峰. 時(shí)空異常值檢測(cè)的研究[J]. 軟件，2016，37（12）：162-165

0 引言

異常值檢測(cè)是數(shù)據(jù)挖掘研究領(lǐng)域的一個(gè)相當(dāng)重要的分支，異常值檢測(cè)的目的是尋找與其他大多數(shù)對(duì)象不同的個(gè)體，又常被稱為離群檢測(cè)或者是例外挖掘。異常值檢測(cè)在諸如金融欺詐、入侵檢測(cè)、公眾健康與生態(tài)環(huán)境監(jiān)測(cè)預(yù)報(bào)等多個(gè)領(lǐng)域都取得了相當(dāng)不錯(cuò)的應(yīng)用。隨著大數(shù)據(jù)時(shí)代的到來(lái)，越來(lái)越容易取得像溫度，用戶流量使用等時(shí)空數(shù)據(jù)，檢測(cè)這類數(shù)據(jù)異常值的重要性也日益凸顯。

空間異常值是指那些非時(shí)空值與周圍相鄰的個(gè)體顯著不同的值。這表明具有空間異常值的個(gè)體是與它相鄰的個(gè)體顯著不同的，然而他并非與總體有顯著的不同。從空間異常值可以延伸出時(shí)空異常值的概念，即時(shí)空個(gè)體具有與周圍時(shí)間相鄰和空間相鄰個(gè)體顯著不同的非時(shí)空值。

時(shí)空異常值的檢測(cè)主要有三種方法：第一種是直接判定該個(gè)體是否與他時(shí)空相鄰的個(gè)體的非時(shí)空值有明顯的差異，第二種是時(shí)空異常值體的檢測(cè)，這種時(shí)空異常值體是跨越時(shí)間的，并不像時(shí)空異常值僅僅是某一時(shí)刻的值，第三種是對(duì)時(shí)空異常值軌跡的探索。

Birant和Kut[1]提出了一個(gè)基于密度的時(shí)空異常值檢測(cè)機(jī)制。他們使用了DBSCAN（具有噪聲的基于密度的聚類方法）聚類算法用于對(duì)空間維度進(jìn)行聚類從而識(shí)別空間異常值。DBSCAN能劃分任意形狀的類并且對(duì)高效的處理大數(shù)據(jù)集，然而DBSCAN并沒(méi)有考慮時(shí)間維度，當(dāng)不同類別密度不同時(shí)，它也不能判別出某些異常值。因此他們使用了改進(jìn)的DBSCAN，具體有兩點(diǎn)改進(jìn)：一直為了支持時(shí)間維度，通過(guò)遍歷一棵樹找出任一個(gè)個(gè)體在一定半徑范圍內(nèi)的時(shí)間鄰居和空間鄰居，二是當(dāng)類別具有不同的密度時(shí)，會(huì)給每一個(gè)類分配一個(gè)密度因子，然后將新生成類的值與平均值進(jìn)行比較從而發(fā)現(xiàn)異常值。Cheng和Li提出了一個(gè)四步法，用以處理語(yǔ)義和動(dòng)態(tài)屬性的地理現(xiàn)象的時(shí)空異常值檢測(cè)。這四步分別是發(fā)現(xiàn)語(yǔ)義個(gè)體，聚合，對(duì)比，驗(yàn)證。Adam（2004）[3]研究了基于距離的時(shí)空異常值檢測(cè)，根據(jù)微類的空間和語(yǔ)義相似性融合成巨類。運(yùn)用雅各比系數(shù)和輪廓系數(shù)來(lái)計(jì)算微類的空間相似性。在巨類中任一與其他點(diǎn)不同數(shù)據(jù)將被標(biāo)記為時(shí)空異常值。

許多文獻(xiàn)已經(jīng)對(duì)空間異常值檢測(cè)和時(shí)間序列異常值的檢測(cè)進(jìn)行了研究，然而同時(shí)對(duì)時(shí)間維度和空間維度進(jìn)行異常值偵測(cè)的還不多，有一些研究也是單純的把時(shí)空分割開，即分別檢測(cè)出時(shí)間異常值和空間異常值，最后結(jié)合這兩部分來(lái)判定時(shí)空異常值。然而時(shí)間維度和空間維度是相互關(guān)聯(lián)的，所以同時(shí)結(jié)合時(shí)空兩個(gè)維度進(jìn)行異常值的檢測(cè)是很有必要的。

1 時(shí)空異常值簡(jiǎn)介

1.1 時(shí)間維度異常值檢測(cè)

時(shí)空數(shù)據(jù)多以面板數(shù)據(jù)的形式存在，面板數(shù)據(jù)是在時(shí)間序列上取多個(gè)截面，在這些截面上同選取樣本觀測(cè)值所構(gòu)成的樣本數(shù)據(jù)，也就是把截面和時(shí)間序列數(shù)據(jù)融合在一起的數(shù)據(jù)集。面板數(shù)據(jù)集顯示個(gè)體之間存在差異，而單獨(dú)的時(shí)間序列或橫截面不能有效反映這種差異，如果只是簡(jiǎn)單使用時(shí)間序列或橫截面分析就可能獲得有偏結(jié)果。同時(shí)面板數(shù)據(jù)能夠提供更多信息、更多變化性、更少共線性、更多自由度和更高效率。

圖1 滑動(dòng)窗口圖

時(shí)空數(shù)據(jù)通常具有數(shù)據(jù)流的特點(diǎn)，數(shù)據(jù)流是指連續(xù)產(chǎn)生的、沒(méi)有邊界的大量數(shù)據(jù)元素所組成的序列。為了能更好的處理數(shù)據(jù)流，本文將使用滑動(dòng)窗口模型，隨著新數(shù)據(jù)的到來(lái)?；瑒?dòng)窗口以基本窗口為單位不斷更新。每進(jìn)入一個(gè)新的基本窗口，最舊的一個(gè)基本窗口被刪除，滑動(dòng)窗口隨之更新一次。因此，滑動(dòng)窗口中包含的數(shù)據(jù)不斷變化和更新。

1.2 空間維度異常值檢測(cè)

空間離群點(diǎn)是與其空間鄰域中其它空間對(duì)象的非空間屬性值存在明顯差異的空間對(duì)象。空間離群點(diǎn)挖掘是空間數(shù)據(jù)挖掘的一個(gè)重要分支，在交通控制、遙感圖像分析、氣象預(yù)報(bào)和人口統(tǒng)計(jì)數(shù)據(jù)分析等應(yīng)用中可揭示重要現(xiàn)象。隨著傳感器設(shè)備技術(shù)的發(fā)展，數(shù)據(jù)采集設(shè)備的數(shù)量越來(lái)越多，精度越來(lái)越高，采集的項(xiàng)目也越來(lái)越多，因此數(shù)據(jù)量越來(lái)越大，維數(shù)越來(lái)越高。然而現(xiàn)有的空間離群點(diǎn)挖掘算法主要是針對(duì)單維或中低維的中小規(guī)模數(shù)據(jù)量的挖掘，難以適應(yīng)高維大數(shù)據(jù)量的挖掘，并且現(xiàn)有算法沒(méi)有充分考慮空間數(shù)據(jù)的特點(diǎn)，挖掘的不是真正意義上的空間離群點(diǎn)，而是全局離群點(diǎn)。算法存在用戶依賴性大，檢測(cè)精度低，挖掘效率低等局限。

考慮空間這一維度，需要對(duì)整個(gè)空間的點(diǎn)進(jìn)行區(qū)域劃分，對(duì)此本文將研究Voronoi圖等能保持區(qū)域拓?fù)浣Y(jié)構(gòu)的模型。Voronoi圖是計(jì)算幾何中一種幾何結(jié)構(gòu)，也是一種空間分割的方法[6]。Voronoi圖可以作為表示各種元素之間關(guān)系的一個(gè)結(jié)構(gòu)，通過(guò)這個(gè)結(jié)構(gòu)可以提取出重要信息。這樣的實(shí)例多見于用Voronoi圖研究自然界物質(zhì)結(jié)構(gòu)的性質(zhì)。把Voronoi圖作為一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)，通過(guò)這個(gè)數(shù)據(jù)結(jié)構(gòu)可以完成許多物體形態(tài)或鄰近關(guān)系的計(jì)算任務(wù)。把Voronoi圖作為提高某些幾何算法運(yùn)算速度的重要手段．一般來(lái)說(shuō)，二維的Voronoi圖可以在O(nlogn)時(shí)間內(nèi)獲得，三維的Voronoi圖可以在O(n2)時(shí)間內(nèi)獲得．Voronoi圖的性質(zhì)決定了它與許多其它幾何結(jié)構(gòu)具有內(nèi)在關(guān)系，通過(guò)Voronoi圖，許多幾何算法可以得到快速運(yùn)算。

2 時(shí)空異常值檢測(cè)的結(jié)合

在空間維度上運(yùn)用Voronoi 圖對(duì)空間位置進(jìn)行劃分，重新定義了各個(gè)位置之間的距離以及相鄰關(guān)系，利用重新的定義的距離對(duì)非時(shí)空值從空間維度進(jìn)行限制；在時(shí)間維度上，由于時(shí)空數(shù)據(jù)多以面板數(shù)據(jù)的形式存在，面板數(shù)據(jù)是在時(shí)間序列上取多個(gè)截面，在這些截面上同選取樣本觀測(cè)值所構(gòu)成的樣本數(shù)據(jù)，也就是把截面和時(shí)間序列數(shù)據(jù)融合在一起的數(shù)據(jù)集。面板數(shù)據(jù)集顯示個(gè)體之間存在差異，而單獨(dú)的時(shí)間序列或橫截面不能有效反映這種差異，如果只是簡(jiǎn)單使用時(shí)間序列或橫截面分析就可能獲得有偏結(jié)果。同時(shí)面板數(shù)據(jù)能夠提供更多信息、更多變化性、更少共線性、更多自由度和更高效率。時(shí)空數(shù)據(jù)通常具有數(shù)據(jù)流的特點(diǎn)，數(shù)據(jù)流是指連續(xù)產(chǎn)生的、沒(méi)有邊界的大量數(shù)據(jù)元素所組成的序列。為了能更好的處理數(shù)據(jù)流，本文將使用滑動(dòng)窗口模型，隨著新數(shù)據(jù)的到來(lái)。滑動(dòng)窗口以基本窗口為單位不斷更新。每進(jìn)入一個(gè)新的基本窗口，最舊的一個(gè)基本窗口被刪除，滑動(dòng)窗口隨之更新一次。因此，滑動(dòng)窗口中包含的數(shù)據(jù)不斷變化和更新。

對(duì)當(dāng)前的滑動(dòng)窗口的非時(shí)空值使用k－means聚類[8]，得到時(shí)間維度的各個(gè)分類；通過(guò)Voronoi 圖重新定義的相鄰關(guān)系對(duì)這個(gè)聚類結(jié)果再加以細(xì)分從而得到了時(shí)空相結(jié)合的聚類結(jié)果，根據(jù)聚類的結(jié)果將數(shù)據(jù)樣本很少的類別判定為異常值，由此得到了一個(gè)滑動(dòng)窗口下的異常值判定；接下來(lái)使用三次指數(shù)平滑算法進(jìn)行迭代。

三次指數(shù)平滑算法可以對(duì)同時(shí)含有趨勢(shì)和季節(jié)性的時(shí)間序列進(jìn)行預(yù)測(cè)，該算法是基于一次指數(shù)平滑和二次指數(shù)平滑算法的。[9]

一次指數(shù)平滑算法基于以下的遞推關(guān)系：

其中α是平滑參數(shù)，si是之前i個(gè)數(shù)據(jù)的平滑值，取值為[0,1]，α越接近1，平滑后的值越接近當(dāng)前時(shí)間的數(shù)據(jù)值，數(shù)據(jù)越不平滑，α越接近0，平滑后的值越接近前i個(gè)數(shù)據(jù)的平滑值，數(shù)據(jù)越平滑，α的值通常可以多嘗試幾次以達(dá)到最佳效果。

一次指數(shù)平滑算法進(jìn)行預(yù)測(cè)的公式為：xi+h=si，其中i為當(dāng)前最后的一個(gè)數(shù)據(jù)記錄的坐標(biāo)，亦即預(yù)測(cè)的時(shí)間序列為一條直線，不能反映時(shí)間序列的趨勢(shì)和季節(jié)性。

二次指數(shù)平滑保留了趨勢(shì)的信息，使得預(yù)測(cè)的時(shí)間序列可以包含之前數(shù)據(jù)的趨勢(shì)。二次指數(shù)平滑通過(guò)添加一個(gè)新的變量t來(lái)表示平滑后的趨勢(shì)：

二次指數(shù)平滑的預(yù)測(cè)公式為xi+h=si+hti二次指數(shù)平滑的預(yù)測(cè)結(jié)果是一條斜的直線。三次指數(shù)平滑在二次指數(shù)平滑的基礎(chǔ)上保留了季節(jié)性的信息，使得其可以預(yù)測(cè)帶有季節(jié)性的時(shí)間序列。三次指數(shù)平滑添加了一個(gè)新的參數(shù)p來(lái)表示平滑后的趨勢(shì)。

三次指數(shù)平滑有累加和累乘兩種方法，下面是累加的三次指數(shù)平滑

下式為累乘的三次指數(shù)平滑：

累乘三次指數(shù)平滑的預(yù)測(cè)公式為：

α，?，γ的值都位于[0,1]之間，可以多試驗(yàn)幾次以達(dá)到最佳效果。

S，t，p初始值的選取對(duì)于算法整體的影響不是特別大，通常的取值為s0=x0，t0=x1-x0，累加時(shí)p=0，累乘時(shí)p=1。

3 結(jié)論

本文提出了一種將時(shí)間維度和空間維度有效結(jié)合起來(lái)的異常值檢測(cè)方法，在時(shí)間維度上，運(yùn)用滑動(dòng)窗口模型，能很好的處理數(shù)據(jù)流形式的數(shù)據(jù)，同時(shí)能很好的壓縮數(shù)據(jù)的信息；在空間維度上，運(yùn)動(dòng)

Voronoi圖對(duì)空間進(jìn)行區(qū)域劃分，保持空間整體的拓?fù)湫再|(zhì)，同時(shí)在Voronoi圖的背景下定義距離和連通性的概念，為后續(xù)聯(lián)系時(shí)間維度和空間維度的研究奠定了基礎(chǔ)。

[1] Birant, D. and Kut, A. (2006). Spatio-Temporal Outlier Detection in Large Databases. Journar of Computing and Information Technology

[2] A Multiscale Approach for Spatio-Temporal Outlier Detection. Transactions in Geographic Information Systems, 10(2): 253–263.

[3] Sun, Y., Xie, K., Ma, X., Jin, X., Pu, W., and Gao, X. (2005). Detecting Spatio-Temporal Outliers in Climate Dataset: A Method Study. In Proc. Of the 2005IEEE Intl. Geoscience and Remote Sensing Symposium, pages 760–763.

[4] Drosdowsky, W. (1993). An Analysis of Australian SeasonalRainfall Anomalies: 1950–1987. Intl. Journal of Climatology, 13(1): 1–30.

[5] Ester, M., Kriegel, H. -P., Sander, J. , and Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proc. Of the 2nd ACM Intl. Conf on Knowledge Discovery and Data Mining(KDD), pages 226–231.

[6] Adam, N. R., Janeja, V. P., and Atluri, V. (2004). Neighborhood Based Detection of Anomalies in High Dimensional Spatio-temporal Sensor Datasets. In Proc. of the 2004 ACM Symposium on Applied Computing, pages 576–583.

[7] Wu, E., Liu, W., and Chawla, S. (2010). Spatio-Temporal Outlier Detection in Precipitation Data. In Proc. Of the 2nd Intl. Conf. on Knowledge Discovery from Sensor Data, pages 115–133.

[8] Lu, C. -T. and Liang, L. R. (2004). Wavelet Fuzzy Classification for Detecting and Tracking Region Outliers in Meteorological Data. In Proc. Of the 12th Annual ACM Intl. Workshop on Geographic Information Systems, pages 258–265.

[9] Neill, D. B. and Cooper, G. F. (2010). A Multivariate Bayesian Scan Statistic for Early Event Detection and Characterization. Machine Learning, 79(3): 261–282.

[10] Ge, Y., Xiong, H., Zhou, Z. -h., Ozdemir, H., Yu, J., and Lee, K. C. (2010). Top-Eye: Top-K Evolving Trajectory Outlier Detection. In Proc. Of the 19th ACM Intl. Conf. on Information and Knowledge Management, pages 1733–1736.

Research on The Spatio-temporal Outlier Detection

HE Qi-feng

(School of Economics and Management, Beijing University of Post and Telecommunication, Beijing)

Outlier detection is a very important branch of data mining, the purpose of outliers detection is to find out the individuals that are different from most other objects, it is often called outlier detection or exception mining. Many literatures have studied the detection of spatial outliers and detection of temporal outliers, but there are not too many methods to connect temporal outliers and spatial outliers. This paper will research temporal outliers and spatial outliers individually, and then combine these two dimensions to propose a new detection method of spatiotemporal anomalies, which will lay a foundation for the future detection of Spatio-temporal anomalies.

Outlier detection; Data mining; Voronoi graph; K-means clustering

TP311

A

10.3969/j.issn.1003-6970.2016.12.034

何奇峰(1991-)，男，碩士研究生，主要研究方向：數(shù)據(jù)挖掘