利用层次约束Delaunay三角网探测空间点事件离群模式

Detection of Spatial Outlier Patterns from Point Events Based on Multi-constrained Delaunay Triangulation

空间离群模式探测是空间数据挖掘的一个研究热点。以带有空间位置属性的点事件为研究对象,针对现有方法的局限性,在扩展了空间离群模式定义的基础上引入层次约束Delaunay三角网,发展了一种空间点事件离群模式探测方法(简称层次约束TIN法)。首先,借助Delaunay三角网粗略地构建空间点事件间的邻接关系;然后,利用统计学方法针对Delaunay三角网的边长特性进行三个层次约束分析,以精化空间点事件的邻近域;最后,对具有空间邻接关系的点事件集合进行统计分析,以形成一系列空间簇,并通过一个统计约束指标提取数量较少的空间簇,即空间点事件离群模式。该方法不需要人为输入参数,通过模拟数据和实际数据实验,证明该方法可以有效、稳健地识别各类空间点事件离群模式。

In recent years,spatial outlier detection has become a research hotspot in the domain of spatial data mining.The aim of spatial outlier detection is to discover those small parts of spatial entities deviating from the global or local distribution in massive spatial datasets.Spatial outliers may indicate potential,unknown,and important knowledge instead of noise in many application domains,e.g.,environmental science,meteorology,urban traffic,and so on.Existing spatial outlier detection methods focus on detecting spatial outliers in the spatial datasets with non-spatial attributes.There is still a lack of detection methods specifically designed for spatial point event datasets,in particular,for complicated spatial point event datasets with clusters having arbitrary shapes and/or different densities.Therefore,we developed a method of detecting outlier patterns for spatial point events by considering spatial locations;the definition of a spatial outlier is extended and a multi-level constrained Delaunay triangulation is employed.Spatial adjacency relationships are roughly obtained from Delaunay triangulation.Then,three-level constraints are described and utilized for precise spatial adjacency relationships with the consideration of statistical characteristics.Finally,those spatial point events connected by the remained edges are gathered to form a series of clusters.The clusters containing very few point events are regarded as spatial outlier patterns.This algorithm does not involve any parameters.Experiments on both synthetic and real-world spatial datasets demonstrate that this algorithm can detect all kinds of spatial outlier patterns efficiently and robustly.