时空异常探测方法研究综述

邓 敏，石 岩，龚 健 雅，杨 学 习

(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]。

“异常”亦称为离群点、孤立点。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