時空異常探測方法研究綜述

鄧 敏，石 巖，龔 健 雅，楊 學 習

(1.中南大學地球科學與信息物理學院地理信息系，湖南 長沙 410083;2.武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢 430079;3.武漢大學地球空間信息技術協同創新中心，湖北 武漢 430079)

時空異常探測方法研究綜述

鄧 敏1，石 巖2,3，龔 健 雅2,3，楊 學 習1

(1.中南大學地球科學與信息物理學院地理信息系，湖南 長沙 410083;2.武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢 430079;3.武漢大學地球空間信息技術協同創新中心，湖北 武漢 430079)

異常探測是數據挖掘領域的一個重要研究內容，旨在從海量數據中挖掘不符合普適性規律、表現出“與眾不同”特性的數據或模式，其在金融欺詐、公共衛生、極端氣候事件發現、交通擁堵判別、環境污染監測等領域具有重要應用價值。異常探測最初應用于事務型數據庫，后來擴展到空間數據庫和時空數據庫，出現了一系列有針對性的異常探測算法。為了更好地滿足應用需求，發展性能更高、適應性更強的異常探測方法，該文從所使用的數據類型將異常探測粗分為傳統異常探測、空間異常探測和時空異常探測，并詳細回顧了典型的傳統/空間/時空異常探測方法，指出這些方法存在的問題和局限性：1)不適用于高維數據的異常探測；2)自適應能力差；3)缺乏對異常探測結果的有效性評價。最后，展望了異常探測的相關熱點研究方向：1)顧及高維專題屬性的異常探測；2)顧及領域知識的異常探測；3)耦合度量關系和非度量關系的異常探測；4)異常探測的有效性評價。

異常；傳統異常探測;空間異常探測;時空異常探測

0 引言

近年來，極端氣候事件、交通擁堵、環境污染等已經成為熱點關注問題，其共性在于此類問題中包含的模式在數據庫中呈現出明顯的異常特性，且蘊含了大量未知和重要的知識，稱之為異常模式。在時空數據中，異常模式通常代表著事物發展的某種特殊規律，在現實生活中更能引起人們的興趣。例如，有效識別城市道路交通擁堵將有助于實行交通管制，以方便市民制定合理的出行計劃；探尋環境污染嚴重區域將有助于追根溯源，并輔助出臺相關政策進行環境治理；對極端氣候事件進行準確識別有助于深入分析其內在發展規律，為進一步準確預測奠定重要的先驗知識基礎；對流行病/犯罪爆發熱點進行探測識別將有利于掌握其時空演變規律，從而實現對流行病/犯罪爆發的準確預測。因此，對時空異常的探測分析具有重要研究價值，已成為時空數據挖掘的重要研究內容之一，引起了相關領域學者們的廣泛關注[1-3]。

“異?！币喾Q為離群點、孤立點。1980年，Hawkins給出異常的本質性定義，即“嚴重偏離其他對象的觀測數據，以至于令人懷疑它是由不同機制產生的”[4]。1994年，Barnett等進一步從統計學的角度給出“異常是指與數據集中其余數據分布不一致的觀測數據或觀測數據子集”[5]。2003年，Shekhar等[6]考慮到空間數據的特性，將傳統異常在空間數據中進行了擴展，并將空間異常定義為“專題屬性與其鄰近空間實體顯著不同，而在整體數據范圍內差異可能不明顯的空間實體”。2006年，Cheng等在空間異常的基礎上，從空間域進一步擴展到時空域，給出時空異常的定義，即“專題屬性值嚴重偏離其時間或(和)空間鄰近域內參考實體的時空實體”[7]。針對不同的異常類型，學者們提出了一系列相應的異常探測方法，大致歸納為傳統異常探測、空間異常探測和時空異常探測。針對各種類型異常的探測方法，又可以進行更加細致的分類，從而形成異常探測方法分類體系，如圖1所示。本文將對該體系中各類異常探測方法進行詳細回顧。

1 傳統異常探測方法

針對Hawkins所提出的“異?！备拍頪4]，學者們發展了一系列異常探測方法，從最初基于統計的方法，到后續為適應海量數據而發展了基于距離、基于密度、基于角度、基于聚類等探測方法。

(1)基于統計的方法。該方法的基本思想是根據數據集的特性先假定一個數據分布的概率模型，然后根據模型的不一致性確定異常[5]。通常采用基于單一分布模型和基于混合分布模型兩大類[8]。該類方法的優點是建立在成熟的統計學理論基礎上，異常含義明確；其缺陷是數據集的概率模型一般未知，估計時難免出現誤差甚至背離現實的錯誤。為解決這個問題，一些學者通過對數據集中每個實體給定一個深度值，并將其映射到二維空間的不同層上，將處于較淺層的實體識別為異常[9,10]。于是，基于深度的方法僅能有效探測低維數據，處理高維數據效率較低[11]。

圖1 異常探測方法分類體系

(2)基于距離的方法。該方法的基本思想是以對象間距離的大小檢測異常，將那些沒有足夠鄰居的對象識別為異常。Knorr等定義DB(p,D)-outlier為：若數據集中存在至少p%的實體到實體O的距離大于某距離閾值D，則實體O就是異常[12]。針對參數p和D難確定的缺陷，Ramaswamy等[13]通過計算每個實體的k鄰近距離并進行排序，選取k鄰近距離最大的N個實體作為異常。該方法具有明顯的幾何解釋，適用于探測全局異常，但探測局部異常能力有限，且需要人為輸入參數。

(3)基于密度的方法。為了探測數據集中的局部異常實體，Breunig等[14]在基于距離探測方法的基礎上引入局部密度的概念，提出一種基于密度的探測方法——LOF算法(圖2a)。借助實體的局部可達密度定義局部異常度，異常度與局部密度成反比，將異常度較大的實體識別為異常。為了解決密度差異較大的簇相鄰時易產生誤判的問題，Jin等[15]采用顧及對稱K鄰近域的影響域，提出一種INFLO法。此外，一些學者在LOF算法基礎上提出了一些改進算法(如GLOF[16]、LOCI[17])，并用于探測異常小簇。基于密度的方法亦需要用戶輸入大量參數，并且穩定性和可解釋性較差。

(4)基于角度的方法。為了避免直接采用實體間的距離度量，Krirgel等[18]提出了一種基于角度的異常探測思想。該方法通過度量實體與其鄰域內其他實體所構成的角度定義異常度，角度越大，異常度越小，反之異常度越大(圖2b)。Zhang等[19]進一步提出在子空間探測異常，并應用于工業故障檢測。然而，當數據呈線性分布時，基于角度的方法難以準確探測異常，并且效率低，無法適用于海量數據。

(5)基于聚類的方法。該方法的基本思想是將異常探測過程轉換成聚類過程。聚類的目的在于將數據集劃分為若干簇，并且簇內實體間距離盡可能小，簇間實體間距離盡可能大，將聚類后那些不隸屬于任何簇的實體識別為異常[20-23](圖2c)。通過聚類技術可高效地從數據集中發現異常實體，但聚類的主要目的在于發現簇，異常實體僅是一種副產物，使得異常探測精度較低。此外，異常探測結果嚴重依賴聚類算法的選擇，是一種粗糙的探測方法。

圖2 傳統異常探測

2 空間異常探測方法

遵循Shekhar等[6]提出的異常探測基本思想，并顧及空間數據的相關性、異質性等特性，學者們對傳統異常探測方法進行了擴展和改進，提出了一系列空間異常探測方法，可大致分為：基于圖形、基于距離、基于密度、基于圖論、基于智能學習、基于空間聚類等方法。與傳統異常探測不同的是，空間異常探測首先需要根據空間屬性建立空間實體間的鄰近關系，進而顧及鄰近實體間的非空間屬性差異度量空間異常[24]。

(1)基于圖形的方法。該方法是根據一定的準則將空間數據可視化，使得空間異常表現直觀，常采用變量云和散點圖等[25]。其中，變量云是根據所有空間實體對間的空間距離和專題屬性值差異繪制坐標平面，從空間距離較近而專題屬性值差異較大的實體對中篩選空間異常；散點圖根據實體的Z-core值與其空間鄰域內實體的Z-core值平均值繪制坐標平面，位于二、四象限的實體識別為空間異常[6](圖3a)。此類方法存在諸多缺點(如結果的主觀性強)，且無法用于海量空間數據的異常識別，現較少使用[26]。

(2)基于距離的方法。該方法的基本思想是在空間鄰域內通過度量該實體與其空間鄰域內其他實體間的專題屬性值差異，利用統計檢驗指標識別空間異常(圖3b)，中心實體與其4-鄰域度量屬性差異。Shekhar等[6]給出一種基于距離的探測框架，并應用于交通異常檢測。例如，Liu等[27]利用八方向法劃分實體的空間鄰域，根據實體空間鄰域內其他實體的專題屬性值，采用反距離加權法(IDW)獲得該實體的估值，并通過度量實體觀測值和估值之間的差異探測空間異常；李光強等[28]、鄭旻琦等[29]利用Delaunay三角網構建空間鄰域，進而利用與Liu等[27]類似的策略獲得空間異常；Chen等[30]采用KNN建立空間鄰域，并將單一專題屬性擴展到多維專題屬性，利用馬氏距離度量實體間的多維專題屬性距離以探測空間異常；馬榮華等[31]則利用專題屬性距離建立KNN鄰域，用空間屬性定義距離函數，進而探測空間異常。當空間數據分布不均勻時，基于距離的方法僅能探測全局異常實體，而難以識別密度差異較大區域中的局部異常實體。此外，若實體空間鄰域內存在空間異常，也將對空間異常度量產生較大影響，從而導致誤判或漏判。

(3)基于密度的方法。為了更加細致地探測不同密度分布等復雜空間數據集中的異常實體，Chawla等[32]將LOF算法的思想引入空間異常探測。針對空間鄰近實體間專題屬性差異計算其鄰域距離，并引入波動參數，進而度量空間局部異常度SLOM(圖3c)。當空間鄰域較少或波動幅度較小時，難以準確表現波動情況，從而容易產生漏判或誤判。薛安榮等[33]則通過鄰域距離與其空間鄰域實體的鄰域距離均值的比值度量空間局部異常度SLOF，提高了檢測率。然而，該類方法通過剔除空間鄰域中屬性值較大的實體以減小潛在異常的影響，使得異常度量的結果不夠穩健。

(4)基于圖論的方法。該方法的基本思想在于將空間數據轉換為圖形(如Delaunay三角網、MST等)后，從圖形結構數據中探測空間異常。Lu等[34]提出一種基于圖形的空間異常點和異常區域的探測方法，通過空間屬性建立KNN鄰域圖，以邊所連接的兩實體間的專題屬性值距離作為權重，通過連續打斷具有高權重的邊獲取與空間鄰域顯著不同的孤立點或區域；但該算法缺乏對數據的局部差異分析，仍屬于全局探測，當數據的空間分布以及專題屬性值分布較為復雜時，難以準確識別各類空間異常。為此，Shi等[35]提出一種融合圖論與局部密度度量的思想進行空間異常探測，借助Delaunay三角網，分別根據空間距離和專題屬性距離對Delaunay三角網進行層次刪邊操作，并提出一個分布模式識別規則，從各子圖中識別空間均質區域、空間異質區域和空間異常區域，最后利用局部密度度量思想計算空間均質區域和空間異常區域中實體的異常度，并通過IDW插值對空間實體異常度可視化以識別潛在的空間異常區域。楊學習等[36]則借助Delaunay三角網對空間距離和專題屬性距離進行層次約束以獲取空間異常，并應用于極端降水事件站點的檢測。

(5)基于智能學習的方法。在計算機領域，一些學者打破傳統空間異常探測直接從數據出發的思路，通過機器學習方法對空間數據進行建模分析以探測空間異常。典型方法有：Chen等[37]顧及空間數據集的局部特性利用高斯隨機場進行建模，通過對觀測值與模型中的估計值進行比較，將差異較大的實體識別為空間異常；Liu等[38]結合圖論和隨機游走模型(Random Walk)構建圖模型，進而度量實體間的相似度以挖掘空間異常；Cai等[39]利用自組織學習模型將高維空間數據映射到二維格網空間，尋找實體的多維屬性鄰域，進而在各鄰域內探測空間異常。基于智能學習的方法多需對空間數據進行必要假設。例如，假設數據服從高斯分布，此種情況下對數據施加約束往往使得探測結果同樣被約束在模型框架內，可能會導致探測結果脫離實際而失去應用價值。

(6)基于空間聚類的方法：空間聚類技術可用于空間異常探測，主要有直接法和間接法兩類。直接法通過對空間數據集進行聚類分析，將那些不隸屬于任何空間簇的實體識別為空間異常。例如李光強等[40]提出一種DDBSC算法，同時顧及空間鄰近和專題屬性相似進行空間聚類分析，得到空間簇和空間異常點；間接法則主要采用空間聚類技術獲取空間實體間準確的鄰近關系，將離散的空間數據集劃分為各個空間簇，進而在各個簇內探測空間異常。例如，Adam等[41]利用Voronoi圖建立空間實體間的鄰接關系，并顧及語義關系采用JC系數進一步精化實體間的鄰近關系，然后將空間鄰近且語義相似的實體進行空間聚類分析以獲取空間鄰域，并在各空間鄰域內利用基于距離的方法探測空間異常實體；鄧敏等[42]通過聚類分析獲取空間自相關較強的各空間簇，充分考慮空間數據的局部相似特性，以更充分地挖掘同一數據集中不同分布中的局部空間異常，并應用于異常土壤重金屬采樣點探測。與傳統異常探測類似，基于空間聚類的方法嚴重依賴聚類算法的選擇，不同聚類算法可得到不同的異常探測結果。

圖3 空間異常探測

3 時空異常探測方法

在實際應用中，同時顧及時間域和空間域的時空異常探測具有更加重要的價值和意義。例如，在氣象方面，預測臺風路徑突然變化的原因對提前發出疏散指令起到至關重要的作用；預測某個地區不尋常的降水行為將有助于對突如其來的洪澇災害等極端事件做好充分準備。通過對現有文獻進行分析總結，時空異常探測主要包括時空點事件異常探測、時空序列異常探測和時空軌跡異常探測。

3.1 時空點事件異常探測

時空點事件中的異常主要包括離群和熱點兩類。其中，時空離群指那些不屬于任何時空簇的孤立點事件以及僅包含少量時空點事件的小簇，基于聚類的方法是時空點事件離群探測的一種重要手段[43-45]。例如，Lee等[46]針對從Twitter中獲取的時空點事件，首先從時間維角度顧及Twitter數據的動態性，基于密度進行聚類分析獲取其中的異常事件，進而在空間維對異常事件進行定位分析和可視化。Shi等[47]針對Twitter時空點事件，從時空演變的角度出發，通過顧及時空點事件的空間和時空異常分布，提出一種基于時空耦合聚類的時空異常點事件演變模式探測方法，如圖4a所示。

時空熱點指那些局部聚集程度顯著偏大的簇，主要采用的是基于時空掃描統計的方法。例如，針對流行病、犯罪事件等的爆發熱點區域探測，一些學者進行了一系列相關研究，其基本假設為事件的發生在時空范圍內服從泊松分布[48,49]。首先通過某種方式(如畫圓法)劃定一個區域，計算該區域內事件發生頻率與區域外事件發生頻率的比值，并構造一個統計量，進而通過逐漸改變區域的范圍和位置，尋找整個研究范圍中統計量最大值所對應的區域，最后通過蒙特卡洛模擬等方法對探測結果進行檢驗，排除結果的隨機性。

3.2 時空序列異常探測

時空序列即各空間實體的專題屬性值以時間序列的形式進行記錄。通過文獻分析，對時空序列異常探測的研究始于2006年Cheng等[7]提出的時空異常探測思想，認為針對某個時刻t，若某空間實體的專題屬性值與該時刻其空間鄰域內其他實體差異較大，那么該實體為空間異常；若時刻t內的某空間異常與該實體前后時刻的專題屬性值差異亦較大，那么該空間異常就屬于時空異常。通過對文獻進行分析，現有的時空序列異常探測方法主要包括：

(1)基于距離的方法。這實際上是基于距離的空間異常探測方法在時間維的擴展，通常分別在空間維和時間維進行異常探測，進而將同時屬于空間異常和時間異常的實體作為時空異常。例如，Sun等[50]針對氣候時空序列數據，采取基于距離的策略分別在空間維和時間維進行異常探測，但得到的并非真正意義上的時空異常；劉啟亮等[51]提出一種時空一體化框架下的時空異常探測算法，首先利用空間異常探測算法提取空間異常點，進而在建立時空鄰域的基礎上對各個空間異常點進行驗證分析，最終獲得時空異常點(圖4b)。

(2)基于聚類的方法。很多學者將聚類技術引入時空異常探測，形成混合的探測方法，以更加全面、準確地探測時空異常。例如，Birant等[52]將傳統的基于密度的聚類算法DBSCAN擴展到空間領域，通過同時顧及空間屬性和專題屬性進行聚類操作，篩選不隸屬于任何簇的實體為空間異常，進而將空間異常在時間維進行驗證以獲取時空異常實體；Telang等[53]充分考慮實體間的局部差異，借助統計學工具發展了一種融合聚類思想的空間異常探測方法，針對時空數據集，通過觀察連續時刻的空間異常變化獲取空間異常隨時間的變化規律。

(3)基于小波變換的方法。Barua等[54]利用小波變換在氣象數據中進行了多尺度時空異常探測研究，在空間維上認為屬性值主要隨緯度變化較為明顯，即在各個緯度探測多尺度空間異常，在時間維上則挖掘變化頻率較高的時間點為時間異常。

(4)基于掃描統計的方法。Wu等[55]以降水時空數據為研究對象，將傳統的空間掃描統計進行了擴展，從空間數據集中發現k個與其他區域具有明顯差異的異常區域，并通過連接不同時段探測得到的空間異常以獲得時空異常。

3.3 時空軌跡異常探測

時空軌跡的異常可以大致分為時空軌跡形狀異常和時空軌跡分布異常兩大類，相應地，現有方法根據這兩類時空軌跡異常也可以分為時空軌跡形狀異常探測方法和時空軌跡分布異常探測方法。其中，時空軌跡的形狀異常探測方法主要包括：1)基于劃分的方法。Lee等[56]通過充分度量時空軌跡之間的空間關系，提出一種基于劃分的時空軌跡聚類方法，并從中探測異常軌跡。2)基于方向和密度的方法。Ge等[57]通過對研究區域進行格網劃分，提出一種基于方向和密度的時空軌跡異常度量方法，并通過將各軌跡在時間序列上的異常度進行衰減性疊加，進一步獲得那些偏離其他軌跡的異常軌跡。3)基于格網計數的方法。Zhang等[58]首先將研究區域劃分為若干規則格網，并以通過選定起點格網和終點格網的時空軌跡為研究對象，利用時空軌跡之間所經過格網之間的頻度差異探測那些由不同原因(例如出租車載客、路段整修等)所引起的異常軌跡(圖4c)。

圖4 時空異常探測

另外，時空軌跡的分布異常探測方法主要有：1)基于距離的方法。Liu等[59]根據城市道路網絡將城市劃分為若干功能區域，進而將獲取的車輛GPS數據與城市路網進行匹配，形成一系列穿梭于各區域之間的子軌跡，融合不同時間間隔得到的車輛數量形成一套時空數據，通過距離度量探測時空異常軌跡，并利用頻繁模式挖掘異常軌跡之間的關聯模式；Pan等[60]針對GPS獲取的浮動車行駛軌跡數據，首先提取行駛時間較長的軌跡作為候選異常，進而將候選異常軌跡連接成網，最后利用微博文本數據對得到的異常軌跡網進行時空事件驗證。2)基于PCA的方法。Chawla等[61]同樣根據城市道路網絡的區域劃分與獲取的車輛GPS數據進行匹配，形成時空軌跡的OD數據，通過PCA手段探測時空異常軌跡，進而利用線性優化手段探索引起異常軌跡的根源。3)基于掃描統計的方法。Pang等[62]針對某一時段首先將城市劃分為三維時空格網，根據該時段內所記錄的GPS軌跡數據可得各時空格網中經過的軌跡數目，進而將統計方法探測出的軌跡數目相對較多的格網作為異常。

4 總結與展望

本文對傳統異常探測、空間異常探測以及時空異常探測的基本內涵進行了闡述，進而系統地對現有典型的異常探測方法進行了詳細回顧，通過總結分析發現，現有方法主要存在以下局限性：1)現有異常探測方法普遍不適用于高維數據的異常探測；2)很多方法需要先驗知識的指導，自適應能力差；3)缺乏對異常探測結果的有效性評價。

未來值得進一步研究的工作包括：1)高維時空異常探測，顧及高維專題屬性度量實體間相似和異質特征，以有效提高時空異常探測效率；2)顧及領域知識的異常探測，通過考慮多變量間的時空關聯特性以及探測領域的背景知識，深入探測發現那些通過先驗知識無法解釋的時空異常；3)耦合度量關系(如距離關系)和非度量關系(如拓撲、方向、形狀關系)的時空異常探測；4)時空異常的有效性評價，指導從探測結果中提取真正有效的時空異常。

[1] 李德仁,王樹良,李德毅,等.論空間數據挖掘和知識發現的理論和方法[J].武漢大學學報(信息科學版),2002,27(3):221-233.

[2] 劉大有,陳慧靈,齊紅,等.時空數據挖掘研究進展[J].計算機研究與發展,2013,50(2):225-239.

[3] HAN J,KAMBER M,PEI J.Data Mining:Concepts and Techniques,3rd Edition[M].San Francisco:Morgan Kaufman,2012.

[4] HAWKINS D.Identification of Outliers[M].London:Chapman and Hall,1980.

[5] BARNETT V,LEWIS T.Outliers in Statistical Data[M].John Wiley & Sons,1994.

[6] SHEKHAR S,LU C T,ZHANG P.A unified approach to detecting spatial outliers[J].Geoinformatica,2003,7(2):139-166.

[7] CHENG T,LI Z.A multiscale approach for spatio-temporal outlier detection[J].Transactions in GIS,2006,10(2):253-263.

[8] TAN P N,STEINBACH M,KUMAR V.Introduction to Data Mining[M].Boston:Addison Wesley,2006.

[9] RUS I,ROUSSEEUW P.Computing depth contours of bivariate point clouds[J].Journal of Computational Statistics and Data Analysis,1996,40(23):153-168.

[10] JOHNSON T,KWOK I,NG R.Fast computation of 2-dimensional depth contours[A].Proceeding of the 4th International Conference on Knowledge Discovery and Data Mining[C].New York,USA,1998.224-228.

[11] ANGIULLI F,PIZZUTI C.Outlier mining in large high-dimensional data sets[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(2):203-215.

[12] KNORR E M,NG R T.Algorithms for mining distance-based outliers in large dataset[A].Proceedings of the 24th International Conference on Very Large Data Bases[C].New York,USA,1998.392-403.

[13] RAMASWAMY S,RASTOGI R,SHIM K.Efficient algorithms for mining outliers from large data sets[A].Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data[C].Dallas,Texas,USA,2000.427-438.

[14] BREUNIG M M,KRIEGEL H P,NG R T,et al.LOF:Identifying density-based local outliers[A].Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data[C].Dallas,Texas,USA,2000.93-104.

[15] JIN W,TUNG A K H,HAN J,et al.Ranking outliers using symmetric neighborhood relationship[J].Advances in Knowledge Discovery and Data Mining,2006,3918:577-593.

[16] JIANG S Y,LI Q H,LI K L.GLOF:A new approach for mining local outlier[A].Proceedings of the 2nd International Conference on Machine Learning and Cybernetics[C].Xi′an,China,2003.157-161.

[17] PAPADIMITRIOU S,KITAGAWA H,GIBBONS P B,et al.LOCI:Fast outlier detection using the local correlation integral[C].Proc Icde,2003.315-326.

[18] KRIRGEL H P,SCHUBERT M,ZIMEK A.Angle-based outlier detection in high-dimensional data[A].Proceeding of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Las Vegas,Nevada,USA,2008.444-452.

[19] ZHANG L,LIN J,KARIM R.An angle-based subspace anomaly detection approach to high-dimensional data:With an application to industrial fault detection[J].Reliability Engineering & System Safety,2015,142:482-497.

[20] JIANG M F,TSENG S S,SU C M.Two-phase clustering process for outliers detection[J].Pattern Recognition Letters,2001,22(6):691-700.

[21] THOMAS B,RAJU G.A novel fuzzy clustering method for outlier detection in data mining[J].International Journal of Recent Trends in Engineering,2009,1(2):161-165.

[22] Al-ZOUBI M B,Al-DAHOUD A,A.YAHYA A.New outlier detection method based on fuzzy clustering[J].WSEAS Transaction on Information Science and Applications,2010,7(5):681-690.

[23] SHIY,DENG M,YANG X,et al.Adaptive detection of spatial point event outliers using multilevel constrained Delaunay triangulation[J].Computers Environment & Urban Systems,2016,59:164-183.

[24] 石巖.時空數據異常模式挖掘方法研究[D].長沙：中南大學,2015.

[25] HASLETT J,BRANDLEY R,CRAIG P,et al.Dynamic graphics for exploring spatial data with application to locating global and local anomalies[J].The American Statistician,1991,45(3):234-242.

[26] 黃添強,秦小麟,王欽敏.空間數據庫中離群點的度量與查找新方法[J].中國圖象圖形學報,2006,11(7):982-989.

[27] LIU H G,JEZEK K C,O′KELLY M E.Detecting outliers in irregularly distribution spatial data sets by locally adaptive and robust statistics analysis in GIS[J].International Journal of Geographical Information Science,2001,15(8):721-741.

[28] 李光強,鄧敏,朱建軍,等.一種顧及鄰近域內實體間距離的空間異常檢測新方法[J].遙感學報,2009,13(2):197-202.

[29] 鄭旻琦,陳崇成,樊明輝,等.基于Delaunay三角網的空間離群挖掘[J].微型計算機應用,2008,29(6):76-82.

[30] CHEN D C,LU C-T,KOU Y F,et al.On detection of spatial outliers[J].Geoinformatica,2008,12(4):455-475.

[31] 馬榮華,何增友.從GIS 數據庫中挖掘空間離群點的一種高效算法[J].武漢大學學報(信息科學版),2006,31(8):679-682.

[32] CHAWLA S,SUN P.SLOM:A new measure for local spatial outliers[J].Knowledge and Information System,2006,9(4):412-429.

[33] 薛安榮,鞠時光,何偉華,等.局部離群點挖掘算法研究[J].計算機學報,2007,30(8):1455-1463.

[34] LU C T,DOS SANTOS J R F,LIU X,et al.A graph-based approach to detect abnormal spatial points and regions[J].International Journal on Artificial Intelligence Tools,2011,20(4):721-751.

[35] SHI Y,DENG M,YANG X,et al.A spatial anomaly points and regions detection method using multi-constrained graphs and local density[J].Transactions in GIS,2016,doi:10.1111/tgis.12208.

[36] 楊學習,石巖,鄧敏,等.一種基于多層次專題屬性約束的空間異常探測方法[J].武漢大學學報(信息科學版),2016,41(6):810-817.

[37] CHEN F,LU C T,BOEDIHARDJO A P.GLS-SOD:A generalized local statistical approach for spatial outlier detection[A].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Washington D.C.,USA,2010.1069-1078.

[38] LIU X,LU C T,CHEN F.Spatial outlier detection:Random walk based approaches[A].Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].San Diego,California,USA,2010.370-379.

[39] CAI Q,HE H,MAN H.Spatial outlier detection based on iterative self-organizing learning model[J].Neurocomputing,2013,117:151-172.

[40] 李光強,鄧敏,程濤,等.一種基于雙重距離的空間聚類方法[J].測繪學報,2008,37(4):482-487.

[41] ADAM N,JANEJA V P,ATLURI V.Neighborhood based detection of anomalies in high dimensional spatio-temporal sensor datasets[A].Proceedings of the 19th ACM Symposium on Applied Computing[C].Nicosia,Cyprus,2004.576-583.

[42] 鄧敏,劉啟亮,李光強.采用聚類技術探測空間異常[J].遙感學報,2010,14(5):951-958.

[43] WANG M,WANG A,LI A.Mining spatial-temporal clusters from geo-database[J].Lecture Notes in Artificial Intelligence,2006,4093:263-270.

[44] PEI T,ZHOU C,ZHU A,et al.Windowed nearest neighbour method for mining spatio-temporal clusters in the presence of noise[J].International Journal of Geographic Information Science,2010,24(6):925-948.

[45] LIU Q,DENG M,BI J,et al.A novel method for discovering spatio-temporal clusters of different sizes,shapes and densities in the presence of noise[J].International Journal of Digital Earth,2014,7(2):138-157.

[46] LEE C H.Mining spatio-temporal information on microblogging streams using a density-based online clustering method[J].Expert Systems with Applications,2012,39(10):9623-9641.

[47] SHI Y,DENG M,YANG X,et al.A framework for discovering evolving domain related spatio-temporal patterns in Twitter[J].ISPRS International Journal of Geo-Information,2016,5(10):193

[48] KULLDORFF M,HEFFERNAN R,HARTMAN J,et al.A space-time permutation scan statistic for disease outbreak detection[J].Plos Medicine,2005,2(3):e59.

[49] NEILL D B,MOORE A W,SABHNANI M,et al.Detection of emerging space-time clusters[A].Proceeding of the 11th ACM SIGKDD Conference on Knowledge Discovery and Data Mining[C].Chicago,Illinois,USA,2005.218-227.

[50] SUN Y,XIE K,MA X,et al.Detecting spatio-temporal outliers in climate dataset:A method study[A].Proceedings of the 2005 IEEE International Conference on Geoscience and Remote Sensing Symposium[C].2005.25-29.

[51] 劉啟亮,鄧敏,王佳璆,等.時空一體化框架下時空異常探測[J].遙感學報,2011,15(3):465-474.

[52] BIRANT D,KUT A.Spatio-temporal outlier detection in large databases[J].Journal of Computing and Information Technology,2006,14(4):291-297.

[53] TELANG A,DEEPAK P,JOSHI S,et al.Detecting localized homogeneous anomalies over spatio-temporal data[J].Data Mining and Knowledge Discovery,2014,28(5-6):1480-1502.

[54] BARUA S,ALHAJJ R.Parallel wavelet transform for spatio-temporal outlier detection in large meteorological data[J].Intelligent Data Engineering and Automated Learning-IDEAL,2007,4881:684-694.

[55] WU E,LIU W,CHAWLA S.Spatio-temporal outlier detection in precipitation data[J].Knowledge Discovery from Sensor Data,2010,5840:115-133.

[56] LEE J G,HAN J,LI X.Trajectory outlier detection:A partition-and-detect framework[A].Proceedings of the 2008 IEEE 24th International Conference on Data Engineering[C].Cancun,Mexico,2008.140-149.

[57] GE Y,XIONG H,ZHOU Z H,et al.TOP-EYE:Top-k evolving trajectory outlier detection[A].Proceedings of the 19th ACM International Conference on Information and Knowledge Management[C].Toranto,Canada,2010.1733-1736.

[58] ZHANG D,LI N,ZHOU Z H,et al.iBAT:Detecting anomalous taxi trajectories from GPS traces[A].Proceedings of the 13th International Conference on Ubiquitous Computing[C].Beijing,China,2011.99-108.

[59] LIU W,ZHENG Y,CHAWLA S.Discovering spatio-temporal causal interactions in traffic data streams[A].Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].San Diego,California,USA,2011.1010-1018.

[60] PAN B,ZHENG Y,WILKIE D,et al.Crowd sensing of traffic anomalies based on human mobility and social media[A].Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].Orlando,Florida,USA,2013.344-353.

[61] CHAWLA S,ZHENG Y,HU J.Inferring the root cause in road traffic anomalies[A].Proceedings of the 2012 IEEE 12th International Conference on Data Mining[C].Brussels,Belgium,2012.141-150.

[62] PANG L X,CHAWLA S,LIU W,et al.On mining anomalous patterns in road traffic streams[J].Journal of Neuroendocrinology,2011,22(2):110-118.

A Summary of Spatio-temporal Outlier Detection

DENG Min1,SHI Yan2,3,GONG Jian-ya2,3,YANG Xue-xi1

(1.DepartmentofGeo-informatics,SchoolofGeosciencesandInfo-Physics,CentralSouthUniversity,Changsha410083;2.StateKeyLaboratoryofInformationEngineeringinSurveying,Mapping&RemoteSensing,WuhanUniversity,Wuhan430079;3.CollaborativeInnovationCenterofGeospatialTechnology,WuhanUniversity,Wuhan430079,China)

Outlier detection is an important research theme in the field of data mining,which is very valuable to detect financial fraud,public health,extreme climate event,traffic congestion and heavy environmental pollution.Outlier is identified as “an observation which deviates so much from other observations as to arouse suspicions that it is generated by a different mechanism”.As a result,outlier detection will be very helpful to discover the unusual geographical phenomena.Outlier detection is involved in transaction databases at first,and some representative methods are presented,e.g.distance-based,density-based,and clustering-based.These methods do not consider spatial or spatio-temporal characteristics (e.g.spatial or spatio-temporal correlation,heterogeneity).For this purpose,some researchers expand them for the applications of the spatial and spatio-temporal databases.Spatial outliers represent locations which are significantly different from their neighborhoods even though they may not be significantly different from the entire population.Spatio-temporal outlier represents spatio-temporal objects whose thematic attribute values are significantly different from those of other spatially and temporally referenced objects in its spatio-temporal neighborhood.Correspondingly,spatial or spatio-temporal outlier detection methods (e.g.spatial or spatio-temporal clustering-based,spatial or spatio-temporal scanning statistics-based) are developed by considering spatial or spatio-temporal characteristics.Obviously,there are still many shortcomings in these outlier detection methods for different application domains,because each of these methods is to large degree proposed for a special application.Therefore,in order to develop more general methods for detecting various types of outliers,this paper firstly describes the basic concepts and classifications of traditional outlier detection,spatial outlier detection and spatio-temporal outlier detection in details.Further,several classic algorithms are reviewed and their shortages are also analyzed.Finally,some hot research directions of spatio-temporal outlier detection are highlighted.

outliers；traditional outlier detection；spatial outlier detection；spatio-temporal outlier detection

2016-09-22；

2016-10-27

國家自然科學基金項目(41471385)；國家重點研發計劃項目(2016YFB0502303)；湖南省自然科學杰出青年基金項目(14JJ1007)

鄧敏(1974-)，男，教授，博士生導師，主要從事時空數據挖掘與信息服務研究。E-mail:dengmin208@tom.com

10.3969/j.issn.1672-0504.2016.06.008

TP311.13

A

1672-0504(2016)06-0043-08