時空異常值檢測的研究

何奇峰

（北京郵電大學經濟管理學院，北京 海淀 100876）

時空異常值檢測的研究

何奇峰

（北京郵電大學經濟管理學院，北京 海淀 100876）

異常值檢測是數據挖掘研究領域的一個相當重要的分支，異常值檢測的目的是尋找與其他大多數對象不同的個體，又常被稱為離群檢測或者是例外挖掘。許多文獻已經對空間異常值檢測和時間序列異常值的檢測進行了研究，然而同時對時間維度和空間維度進行異常值偵測的還不多；本文將分別從時間和空間這兩個維度出發對異常值的檢測進行研究，然后再將這兩個維度結合起來，提出一種全新的時空異常值的檢測方法，為未來時空異常值的檢測奠定基礎。

異常值檢測；數據挖掘；voronoi圖；k-means聚類

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

0 引言

異常值檢測是數據挖掘研究領域的一個相當重要的分支，異常值檢測的目的是尋找與其他大多數對象不同的個體，又常被稱為離群檢測或者是例外挖掘。異常值檢測在諸如金融欺詐、入侵檢測、公眾健康與生態環境監測預報等多個領域都取得了相當不錯的應用。隨著大數據時代的到來，越來越容易取得像溫度，用戶流量使用等時空數據，檢測這類數據異常值的重要性也日益凸顯。

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

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

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

許多文獻已經對空間異常值檢測和時間序列異常值的檢測進行了研究，然而同時對時間維度和空間維度進行異常值偵測的還不多，有一些研究也是單純的把時空分割開，即分別檢測出時間異常值和空間異常值，最后結合這兩部分來判定時空異常值。然而時間維度和空間維度是相互關聯的，所以同時結合時空兩個維度進行異常值的檢測是很有必要的。

1 時空異常值簡介

1.1 時間維度異常值檢測

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

圖1 滑動窗口圖

時空數據通常具有數據流的特點，數據流是指連續產生的、沒有邊界的大量數據元素所組成的序列。為了能更好的處理數據流，本文將使用滑動窗口模型，隨著新數據的到來。滑動窗口以基本窗口為單位不斷更新。每進入一個新的基本窗口，最舊的一個基本窗口被刪除，滑動窗口隨之更新一次。因此，滑動窗口中包含的數據不斷變化和更新。

1.2 空間維度異常值檢測

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

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

2 時空異常值檢測的結合

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

對當前的滑動窗口的非時空值使用k－means聚類[8]，得到時間維度的各個分類；通過Voronoi 圖重新定義的相鄰關系對這個聚類結果再加以細分從而得到了時空相結合的聚類結果，根據聚類的結果將數據樣本很少的類別判定為異常值，由此得到了一個滑動窗口下的異常值判定；接下來使用三次指數平滑算法進行迭代。

三次指數平滑算法可以對同時含有趨勢和季節性的時間序列進行預測，該算法是基于一次指數平滑和二次指數平滑算法的。[9]

一次指數平滑算法基于以下的遞推關系：

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

一次指數平滑算法進行預測的公式為：xi+h=si，其中i為當前最后的一個數據記錄的坐標，亦即預測的時間序列為一條直線，不能反映時間序列的趨勢和季節性。

二次指數平滑保留了趨勢的信息，使得預測的時間序列可以包含之前數據的趨勢。二次指數平滑通過添加一個新的變量t來表示平滑后的趨勢：

二次指數平滑的預測公式為xi+h=si+hti二次指數平滑的預測結果是一條斜的直線。三次指數平滑在二次指數平滑的基礎上保留了季節性的信息，使得其可以預測帶有季節性的時間序列。三次指數平滑添加了一個新的參數p來表示平滑后的趨勢。

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

下式為累乘的三次指數平滑：

累乘三次指數平滑的預測公式為：

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

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

3 結論

本文提出了一種將時間維度和空間維度有效結合起來的異常值檢測方法，在時間維度上，運用滑動窗口模型，能很好的處理數據流形式的數據，同時能很好的壓縮數據的信息；在空間維度上，運動

Voronoi圖對空間進行區域劃分，保持空間整體的拓撲性質，同時在Voronoi圖的背景下定義距離和連通性的概念，為后續聯系時間維度和空間維度的研究奠定了基礎。

[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-)，男，碩士研究生，主要研究方向：數據挖掘