留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于场论的空间异常探测方法

杨学习 徐枫 石岩 邓敏

杨学习, 徐枫, 石岩, 邓敏. 一种基于场论的空间异常探测方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(3): 364-371. doi: 10.13203/j.whugis20150237
引用本文: 杨学习, 徐枫, 石岩, 邓敏. 一种基于场论的空间异常探测方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(3): 364-371. doi: 10.13203/j.whugis20150237
YANG Xuexi, XU Feng, SHI Yan, DENG Min. Field-Theory Based Spatial Outlier Detecting Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(3): 364-371. doi: 10.13203/j.whugis20150237
Citation: YANG Xuexi, XU Feng, SHI Yan, DENG Min. Field-Theory Based Spatial Outlier Detecting Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(3): 364-371. doi: 10.13203/j.whugis20150237

一种基于场论的空间异常探测方法

doi: 10.13203/j.whugis20150237
基金项目: 

国家高技术研究发展计划(863计划) 2013AA122301

湖南省自然科学杰出青-基金 14JJ1007

国家自然科学基金 41471385

中南大学中央高校基本科研业务费专项资金 2016zzts085

详细信息
    作者简介:

    杨学习, 博士生, 主要从事空间/时空异常探测理论及其应用研究。studyang@sina.cn

  • 中图分类号: P208

Field-Theory Based Spatial Outlier Detecting Method

Funds: 

The National High-Tech R & D Program of China(863 Program) 2013AA122301

the Hunan Provincial Science Fund for Distinguished Young Scholars 14JJ1007

the National Natural Science Foundation of China 41471385

the Fundamental Research Funds for the Central Universities of Central South University 2016zzts085

More Information
    Author Bio:

    YANG Xuexi, PhD candidate, specializes in spatio-temporal data mining analysis. E-mail: studyang@sina.cn

图(11) / 表(2)
计量
  • 文章访问数:  1259
  • HTML全文浏览量:  99
  • PDF下载量:  378
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-01-25
  • 刊出日期:  2018-03-05

一种基于场论的空间异常探测方法

doi: 10.13203/j.whugis20150237
    基金项目:

    国家高技术研究发展计划(863计划) 2013AA122301

    湖南省自然科学杰出青-基金 14JJ1007

    国家自然科学基金 41471385

    中南大学中央高校基本科研业务费专项资金 2016zzts085

    作者简介:

    杨学习, 博士生, 主要从事空间/时空异常探测理论及其应用研究。studyang@sina.cn

  • 中图分类号: P208

摘要: 从空间数据场的角度,借鉴高斯势函数发展了一种新的空间异常度度量指标。进而,提出了一种基于场论的空间异常探测方法。该方法通过空间聚类获得局部相关性较强的空间簇,并构建合理、稳定的空间邻近域。在此基础上,采用专题属性变化梯度修复策略减弱空间邻近域中潜在异常的影响,并利用空间异常度度量指标计算实体的异常度,从而探测空间异常。实验结果及实例证明了此方法的正确性。

English Abstract

杨学习, 徐枫, 石岩, 邓敏. 一种基于场论的空间异常探测方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(3): 364-371. doi: 10.13203/j.whugis20150237
引用本文: 杨学习, 徐枫, 石岩, 邓敏. 一种基于场论的空间异常探测方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(3): 364-371. doi: 10.13203/j.whugis20150237
YANG Xuexi, XU Feng, SHI Yan, DENG Min. Field-Theory Based Spatial Outlier Detecting Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(3): 364-371. doi: 10.13203/j.whugis20150237
Citation: YANG Xuexi, XU Feng, SHI Yan, DENG Min. Field-Theory Based Spatial Outlier Detecting Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(3): 364-371. doi: 10.13203/j.whugis20150237
  • 空间异常探测是空间数据挖掘领域一项重要研究内容[1-3],旨在从海量空间数据中挖掘小部分偏离普遍模式的空间实体。这些异常实体通常蕴含着难以预知的知识,可能代表着地理现象或地理过程的特殊发展规律。近年来,空间异常探测受到学者们的广泛关注,并已应用于地质灾害监测、环境监测与保护、公共卫生、遥感图像数据处理等领域,具有重要的研究价值。

    异常(亦称离群点)的定义最初来源于文献[4]的研究工作,描述为“严重偏离其他对象的观测数据,以至于令人怀疑它是由不同机制产生的”。文献[5]将传统异常在空间上进行了有效扩展,指出空间异常是指专题属性与其空间邻近域内其他参考实体的专题属性显著不同,而在整体数据范围内差异可能不明显的空间实体。空间异常通常根据空间属性(即位置)确定空间邻近关系,进而借助专题属性确定异常程度。现有的空间异常探测方法可分为:(1)基于统计的方法[4];(2)基于图形的方法[6];(3)基于距离的方法[5, 7-8];(4)基于密度的方法[9-11];(5)基于聚类的方法[12-13];(6)基于模型的方法[14-15]。基于统计的方法要求数据服从一定的分布,适用性不强。基于图形的方法主要是采用可视化的方式(如变量云和散点图等)来显现空间异常点,利用人眼进行主观性的识别使这类方法已很少使用。基于距离的方法采用专题属性值与其空间邻域的专题属性的均值(或中值)的差值来度量实体的异常程度,继而通过统计测试的方法识别异常,这类方法采用全局策略,仅适合探测全局异常,不适合探测局部异常实体。基于密度的方法采用不同的密度估计策略度量实体的局部异常度,异常度较大的实体识别为空间异常。这类方法依赖于空间邻近域的选择,缺乏一定的准确性和稳定性。基于聚类的方法旨在发现空间簇,探测空间异常的能力有限,且探测结果依赖于聚类算法的选择。基于模型的方法采用统计模型、机器学习模型等数学工具进行空间异常探测。这类方法需满足模型的假设条件,如数据分布,这在实际运用中很难准确获得,可能使得探测结果偏离实际情况。

    对现有方法进行分析归纳可以发现,当前方法存在的主要问题是:(1)现有方法多认为所有空间实体之间具有等同的相关性,而实际上空间实体间具有局部的相关性,在全局更呈现异质性。如在一个大区域内,经常出现专题属性差异较明显的几个子区域,在探测时若不加以区分,一方面可能导致空间邻域内实体不满足相关性假设,导致异常度量的偏差;另一方面可能造成由于局部出现较多异常实体,使得一些在整体上不明显而局部差异明显的空间异常难以被发现。如图 1所示,采用一个模拟数据集来分析异常度量的差异[9],其中Ⅰ、Ⅱ、Ⅲ各自区域内的实体间具有较强的相关性,而不同区域内实体间的相关性较弱,甚至是独立的。根据空间局部异常度(spatial local outlier measure, SLOM)法[9]共探测出5个异常,如图 1(b)中浅绿色标识。然而,在区域Ⅱ、Ⅲ中3个浅蓝色背景标识SLOM值明显偏大,很可能是空间异常。但由于Ⅰ区出现较多明显的异常点,导致Ⅱ、Ⅲ区域内的异常被忽略。因此,需要加以区分。(2)现有方法多采用空间属性确定空间邻近关系、专题属性度量异常度,缺乏一种耦合两类属性的异常度度量的指标。针对上述问题,本文受物理学中场论思想的启发,从数据场的角度对空间异常探测进行解释,采用似高斯势函数度量空间异常度,发展了一种基于场论的空间异常探测方法(field-theory based spatial outlier detecting method, FTSOD)。

    图  1  模拟空间数据集[9]

    Figure 1.  Simulated Spatial Dataset[9]

    • 本文提出的空间异常探测方法主要分为4个步骤:(1)采用空间聚类技术获取空间簇,针对各空间簇生成Delaunay三角网,进而约束获得空间邻近域;(2)采用专题属性变化梯度修复策略处理空间邻域中潜在异常的影响;(3)引入空间数据场概念,采用似高斯势函数度量空间异常度;(4)针对各空间簇分别统计识别空间异常,并进行评价分析。

    • 本文采用一种基于多约束的自适应空间聚类方法[16](adaptive spatial clustering algorithm based on Delaunay triangulation, ASCDT)进行空间聚类。该方法通过施加不同层次、不同类型的约束可以适应空间数据分布不均匀、空间簇形态各异、位置邻近等复杂情况下的聚类,且输入参数较少,自适应能力强。通过聚类,将所有空间实体划分为若干空间相关性较强的空间簇。针对各空间簇,借助Delaunay三角网来构建空间邻近关系。Delaunay三角网是一种满足最大最小角特性、外接圆特性和唯一性的三角剖分,能自然地反映空间实体间的邻接关系。但从图 2(b)可以发现,原始Delaunay三角网在边界和空洞处的边长明显偏长,如实体ABCD空间邻近是不合理的。文献[17]通过实验证明,不合理的边可通过删除超过平均边长一定倍数的边来有效移除。本文亦采用一种稳健的平均边长来处理不合理的边。

      图  2  空间邻近域构建

      Figure 2.  Construction of Spatial Neighborhood

      定义1  稳健的平均边长:给定各空间簇S, S中所有实体构成Delaunay三角网的N条边,构成边长集合EE中所有边长按升序排列,序列中位于上四分位数和下四分位数之间所有边长的均值称为稳健的平均边长,记为RA(E),表示为:

      $$ {R_A}\left( E \right) = \frac{{\sum {E_i}}}{n}, {Q_1} \le {E_i} \le {Q_3} $$ (1)

      式中, Q1为上四分位数;Q3为下四分位数;n表示上下四分位数之间所有边的数量。

      定义2  不合理的边:边长集合E中,与稳健平均边长相比明显偏大的边定义为不合理的边,所有不合理的边构成不合理的边集合EI,表示为:

      $$ {E_I} = \left\{ {{E_i}|{E_i} > \alpha \times {R_A}\left( E \right)} \right\}, {E_i} \in E $$ (2)

      式中, α为调节因子,用于调整不合理边的判断阈值,其取值范围可通过启发式策略确定[17]。本文通过大量实验发现,α取值[2, 3]时较为合适。

      在空间簇Delaunay三角网中打断不合理的边后,可以获得每个实体的空间邻近实体。如图 2(c)所示,经打断操作后(α=2)空洞和边界处的不合理边被有效移除,据此建立的实体间邻近关系更为合理、稳定。没有隶属于任何簇的实体识别为空间位置孤立点,不参与接下来的检测。

      定义3  空间邻域:对于空间簇中任一空间实体Pi,与打断不合理的边后的Delaunay三角网的边直接相连的空间实体构成Pi的空间邻域NS(Pi),如图 2(c)中空间簇S1实体P的空间邻域为NS(P)={P1, P2, P3, P4, P5, P6}。

    • 在度量空间异常度时,首先需要有效消除空间邻近实体中异常值的影响,借鉴文献[12]的研究策略,本文提出了一种专题属性变化梯度修复策略消除异常值。

      定义4  专题属性变化梯度:给定空间实体P,其空间邻域为NS(P)={X1, X2Xn},f(Xi)表示实体Xi的专题属性值,专题属性变化梯度定义为空间实体P与其某一邻近域实体Xi的专题属性差值的绝对值与二者间欧氏距离的比值,记为G(P, Xi):

      $$ G(P, {X_i}) = \frac{{\left| {f\left( P \right)-f({X_i})} \right|}}{{{\rm{ }}D(P, {X_i})}}, \forall {X_i} \in {N_S}\left( P \right) $$ (3)

      式中,D(P, Xi)表示PXi的欧氏距离。

      针对任一空间实体P进行邻域异常值修复的步骤为:

      1) 令f(P)=0,分别计算实体P与其空间邻域实体Xi的专题属性变化梯度G(P, Xi),按升序排列获取序列G(P),并计算G(P)的中位数M(P)。

      2) 针对任一空间邻域Xi,计算专题属性变化梯度偏离GD(Xi)=|G(P, Xi)-M(P)|,按升序排列获取序列GD(P)。

      3) 将邻域实体按专题属性变化梯度偏离划分为大、中、小3个等级,处于最大等级的[(n+1)/3]个实体组成待修复集合R(P)。进而,采用专题属性变化梯度序列的中位数M(P)进行修复:

      $$ {f_R}({X_i}) = M\left( P \right) \times D(P, {X_i}), \forall {X_i} \in R\left( P \right) $$ (4)

      式中,fR(Xi)表示专题属性修复值。

      异常值修复策略旨在消除空间邻域内潜在异常值对度量异常度的影响,保证空间邻域内实体间专题属性的局部平稳性假设。且这种修复是暂时的,仅在空间异常度量的过程中进行,并不改变实体的固有专题属性值。

    • 场的概念最早由英国物理学家法拉第于1837年提出,用于描述物质粒子间的非接触相互作用。随着场论思想的发展,人们将其抽象为一个数学概念,用于描述某个物理量或数学函数在空间内的分布规律,分为矢量场和标量场。势场是一种重要的标量场,势函数是位置或距离的函数,可以叠加。数据场是指数据通过辐射将其数据能量从样本空间辐射到整个母体空间,接受数据能量并被数据辐射所覆盖的空间[18-19]。如图 3所示,是一个借助Voronoi图和Delaunay三角网得到的空间数据场[20]。数据场已应用于数据挖掘[20-22]和图像分割[23]等领域。实验研究表明,短程场作用更有利于揭示数据分布的凝聚特性,因此,数据场的作用范围必须在有限范围内迅速衰减[18, 22]。高斯函数则可以满足迅速衰减的特性,在充分考虑空间数据自身的特点以及空间数据辐射的特性,本文通过约束Delaunay三角网获取空间邻域的基础上,采用似高斯势函数来定义空间实体的空间异常度。

      图  3  空间数据场示意图

      Figure 3.  Schematic of Spatial Data Field

      定义5  空间异常度:给定空间实体P,其空间异常度MS_O(P)表达为:

      $$ \begin{array}{c} {M_{S\_O}}\left( P \right) = \frac{{\sum\limits_{i = 1}^{\left| {{N_S}\left( P \right)} \right|} {{D_{{\rm{Attr}}}}\left( {P, {X_i}} \right){{\rm{e}}^{-\frac{{D_{{\rm{Geo}}}^2\left( {P, {X_i}} \right)}}{{2{\sigma ^2}}}}}} }}{{\left| {{N_S}\left( P \right)} \right|}}\\ \forall {X_i} \in {N_S}\left( P \right) \end{array}, $$ (5)

      式中,NS(P)为实体P的空间邻域;|NS(P)|为空间邻域数目;DGeo(P, Xi)表示实体PXi之间的欧氏距离;DAttr(P, Xi)表示实体PXi之间的专题属性距离,本文采用归一化的闵氏距离;σ为辐射因子。

    • 针对空间聚类获取的若干空间相关性较强的空间簇,采用统计判别法进行识别,分别探测异常。

      定义6  空间异常:给定一空间簇数据集S,其空间异常集Soutlier为:

      $$ \begin{array}{c} {S_{{\rm{outlier}}}} = \left\{ {{X_i}|{M_{S\_O}}({X_i})-\mu > k\sigma } \right\}, \\ \forall {X_i} \in S \end{array} $$ (6)

      式中,μ为异常度平均值;σ为标准差;k为调节因子。通常k取值2或3,文献[24]通过实验结果表明,当k=1.645时判断异常的结果较合理可靠。因此,本文中k取值1.645。

      所有簇的异常集Soutlier的集合构成空间数据集的空间异常集。

      空间聚类后,各空间簇异常探测的样本减少。直接采用式(6)可能降低异常探测的稳定性。因此,针对小样本数据(样本数小于30)采用稳健统计量中位数median和中位数绝对偏差(median absolute deviation, MAD)[25]替代μσ。其中,μ=median(MS_O),σ=DM(MS_O)。

      $$ \begin{array}{c} {D_M}({M_{S\_O}}) = {\rm{median}}\{ |{M_{S\_O}}({X_1})-{\rm{median}}({M_{S\_O}})|\\ \cdots |{M_{S\_O}}({X_n})-{\rm{median}}({M_{S\_O}})|\} \end{array} $$ (7)
    • 基于以上定义,基于场论的空间异常探测算法可描述为如下所示。

      输入:包含N个实体的空间数据集

      输出:空间异常数据集

      1) 对空间数据集进行空间聚类,获取若干空间相关性较强的空间簇;

      2) 针对各空间簇分别生成Delaunay三角网,采用稳健平均边长移除不合理边,获取空间邻域;

      3) 采用专题属性变化梯度修复策略消除空间邻域内潜在异常值的影响;

      4) 采用异常度量指标计算各空间实体的空间异常度;

      5) 针对各空间簇分别采用统计判别准则识别异常,获取空间异常集。

      对于包含N个实体的空间数据库,非空间属性维数为d,其复杂度主要包括:ASCDT聚类算法的复杂度为O(NlgN);构建Delaunay三角网、打断不合理边并获取空间邻域的复杂度约为O(NlgN)+O(6N)+O(6N);专题属性归一化的复杂度为O(dN),异常度计算的复杂度为O(NlgN)+ O(6dN),异常判别的复杂度为O(NlgN)。于是,该算法的复杂度为:O(NlgN)+O(NlgN)+O(6N)+ O(6N)+ O(dN)+ O(NlgN)+ O(6dN)+O(NlgN)。当dN时,算法复杂度近似为O(NlgN)。

    • 本文设计了两组实验来验证所提出的异常探测算法的可行性。实验1采用模拟数据,模拟数据是由文献[13]中3组经典数据库的一部分组成,进一步增加了一维专题属性,专题属性服从正态分布,对其空间分布及部分预设异常局部放大,如图 4所示。实验2采用华南某市土壤重金属Cr浓度监测数据,进行实际应用分析。两组实验结果均与经典的SLOM算法[9]进行比较,SLOM算法需要两个输入参数,即空间邻域数目k和空间异常数目M。实验环境为acer Aspire V5笔记本电脑(处理器A10-5757M APU,内存4 GB,系统Windows 8.1中文版64-bit)和Matlab R2011b编程环境。

      图  4  模拟数据集SDB空间分布

      Figure 4.  Simulated Dataset SDB

      图  5  模拟数据集SDB的空间邻近域

      Figure 5.  Spatial Neighborhood of SDB

    • 本文采用的模拟数据集具有不同形状、不同密度的空间簇分布,且专题属性值服从正态分布。按照Shekhar-Outlier[5]定义在空间簇中预设了25个空间异常点,包含全局和局部异常点。实验结果中空间异常点用“X”表示。针对模拟数据集,本文算法调节因子α取值2,辐射因子σ取值0.05;针对SLOM算法,采用k-邻域搜索空间邻域,其中k取值为7,空间异常数目M取值25,即模拟数据预设空间异常点数目。

      图 67分别给出了本文方法和SLOM算法的异常度空间分布及空间异常探测结果。对比探测结果可以发现:(1)本文提出的空间异常探测算法顾及了实体间的局部相关性以及邻近域内空间异常点的影响,能够更全面地发现局部的异常现象,正确识别了预设的25个空间异常点。(2)SLOM算法在度量局部异常度时不能有效消除邻域内潜在异常的影响,使得异常度量不准确,且从全局去识别异常,没有顾及到实体的空间分异特性。其探测正确率为60%,误判率为40%,漏检率为40%。(3)SLOM算法的复杂度为O(NklgN+kdN)[9], 而本文算法需先聚类,再约束Delaunay三角网获取空间邻近域,进而度量空间异常并统计识别,算法复杂度高,且执行效率低于SLOM算法。而SLOM算法在确定异常数目时需要较多先验知识,且邻域参数的选择对异常度量影响明显,故本文算法在正确性及易用性方面略优于SLOM算法。

      图  6  本文算法的异常探测结果

      Figure 6.  Spatial Outlier Detection Results Obtained by the Proposed Algorithm

      图  7  SLOM算法异常探测结果

      Figure 7.  Spatial Outlier Detection Results Obtained by SLOM Algorithm

    • 采用中国华南某市环保数据中土壤重金属铬(Cr)浓度监测数据验证本文算法的可行性。采样点空间分布如图 8(a)所示,采样点共103个。首先进行空间聚类。图 8(b)为ASCDT算法聚类结果,所有空间实体均加入空间簇中,共获得11个空间簇。针对各空间簇分别生成Delaunay三角网并处理不合理的边,α取值2.5,空间邻域结果图如图 8(c)所示。当空间簇个数小于或等于6个时,簇中所有空间实体互为空间邻域。进而,采用本文提出的基于场论的方法在各个空间簇中探测空间异常。

      图  8  实际数据

      Figure 8.  Real-World Data

      FTSOD算法在11个空间簇中共探测出16个空间异常采样点,其空间分布如图 9(a)所示。SLOM算法空间邻域数目k取值为5,异常数目M取值16,探测结果图 9(b)所示。比较分析可以发现:(1)SLOM算法虽能顾及局部特性,但仅能发现整体上异常度较大的实体,对于局部异常现象,如簇9中的86号采样点(见表 1),在整体上异常程度不明显,但其专题属性严重偏离空间邻域的其他实体,表现为局部异常现象;(2)FTSOD算法在异常识别时所采用的小样本识别策略十分稳健(簇2、7中包含4个实体,簇8、9中包含5个实体)。

      图  9  空间异常探测结果

      Figure 9.  Results of Spatial Outlier Detection

      表 1  空间簇9中实体专题属性值

      Table 1.  Thematic Attribute of Objects in Cluster 9

      空间簇 采样点编号 土壤Cr实测值/(mg·kg-1)
      82 20.63
      83 12.05
      9 84 28.35
      85 24.58
      86 3.9

      通过对数据分布及来源进行分析,空间异常产生的原因可从土地使用类型(见表 2)、高程差异和污染源等3方面进行分析。本文把重金属污染企业(如电镀厂)视为主要污染源,空间分布如图 9(a)三角形所示。以异常采样站点为中心,建立半径L为5 km的缓冲区。

      表 2  空间异常采样点土地使用类型

      Table 2.  Land-Use Types of Spatial Outliers

      土地使用类型 采样点编号 土地使用类型 采样点编号 土地使用类型 采样点编号
      21 70 1
      22 71 水稻土 35
      菜地 31 菜地 86 42
      40 97 香蕉地 37
      51 98, 102 荔枝地 55

      综合以上信息,对采样点空间异常产生的原因进行分析,可以发现:(1)从表 2可以发现绝大多数空间异常发生在菜地和水稻土,这可能与化肥、农药的过度、不合理使用有密切关系;(2)从图 10可以看出,1、22、40、42、70、71、86、97、98号采样点与其邻近域实体间的高程差异明显,进而影响土壤重金属含量的分布,这可能是产生空间异常的主要因素;(3)从图 11可以发现1、31、35、42、51、55、71、102号采样点与污染源联系比较紧密,极有可能是受附近污染企业的影响。

      图  10  空间异常采样点与高程关系图

      Figure 10.  Relationship Between Spatial Outliers and Elevation

      图  11  异常采样站点缓冲区L=5 km

      Figure 11.  Buffer of Spatial Outliers

    • 空间异常探测对于揭示地理实体或地理现象的潜在发展规律具有重要价值。针对现有空间异常探测方法大多没有顾及空间实体之间的局部相关、整体分异的特性,且缺乏一种耦合专题属性和空间属性度量空间异常度的指标, 本文首先采用空间聚类技术获得空间相关性较强的空间簇,借助Delaunay三角网并打断不合理的边以获取合理、稳定的空间邻域,进而采用似高斯函数度量空间异常度,并在每个空间簇中探测空间异常。本文方法具有两方面的优势:(1)顾及了空间实体间的局部相关性,能更全面地探测局部空间异常;(2)空间异常度量指标耦合了专题属性和空间属性,使得探测的空间异常更具有物理意义。

参考文献 (25)

目录

    /

    返回文章
    返回