一种基于场模型的空间聚类方法-遥感学报

一种基于场模型的空间聚类 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 -遥感学报 基于场论的空间聚类算法 1112 邓敏 刘启亮 李光强 程涛 (1 中南大学 测绘与国土信息工程系，长沙，410083;2. 英国伦敦大学 城市、环境与地理信息工程系, 伦敦) 摘 要:空间聚类作为空间数据挖掘和空间分析的主要手段之一常用于揭示空间数据的分布规律以及探测空间异常。现有的空间聚类算法难以适应空间密度变化较大的情形，并且需要用户输入参数。为此，本文从空间数据场的角度出发，提出了一种适用于空间聚类的场—凝聚场，并给出了一种新的空间聚类度量指标(即凝聚力)。进而，提出了一种基于场论的空间聚类算法(简称FTSC算法)。该算法根据凝聚力的矢量计算获取每个实体的邻近实体，并通过递归搜索的策略，生成一系列不同的空间簇。通过模拟实验验证、经典算法比较和实际应用分析，可以发现本文提出的算法具有三个方面的优势:(1)不需要用户输入参数;(2)能够发现任意形状的空间簇;(3)能够很好适应空间数据分布不均匀的特性。 关键词:空间聚类;凝聚力;场论;空间数据挖掘 1. 引言 空间聚类是地理信息科学与计算机科学领域共同关注的一个问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。空间聚类技术已广泛应用于地理学、制图学、地质学、遥感学、生物学、经济学等众多领域(Blackman & Popoli, 1999; Bar-shalom & Blair, 2000; Hofmann-wellenhof 等, 1994; 毛政元 & 李霖, 2004)，主要用于揭示空间数据的分布规律，或者探测空间离群点(亦称空间异常)。 现有的空间聚类算法大致可以划分为:(1)基于划分的聚类算法，代表算法有k-Means(Macqueen, 1967)、k-Mediods(Ng & Han, 1994)、FCM(Dave & Bhaswan, 1992)等。基于划分的聚类算法需要首先给定聚类数目和目标 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 ，然后随机选择聚类中心，通过迭代不断降低目标函数的误差，直到目标函数收敛至一定阈值时，完成聚类。这类算法需要较多的先验信息来确定输入参数和收敛阈值，并且这些参数和阈值在聚类过程中是固定的，很难适应空间密度变化较大的情况，聚类结果严重依赖初始聚类中心的选择，而且不能发现任意形状的空间簇。(2)基于层次的聚类算法，代表算法有BIRCH(Zhang 等, 1998)、CURE(Guha 等, 1998)、ROCK(Guha 等, 1999)、CHAMELEON(Karypis 等, 1999)和基于引力的聚类算法(Wright, 1977; 淦文燕等, 2006)。基于层次的聚类算法又可以分为凝聚法和分裂法。前者从每个实体出发，通过反复聚合，从而得到不同层次的聚类簇;后者对整个数据集反复进行分裂，直至所有数据被分裂为单目标的簇，从而得到不同层次的聚类簇。层次聚类算法采用固定的分裂或聚合度量阈值，实质上假设了空间实体分布的均匀性。(3)基于密度或距离的聚类算法，代表算法有DBSCAN(Ester等, 1996)、VDBSCAN(Liu 等, 2007)、OPTICS(Ankerst 等, 1999)、ADBSC(李光强等, 2009)、DDBSC(李光强等, 2008)等。基于密度的聚类方法将局部密度大于给定阈值的实体聚为一类，能够发现任意形状的簇，具有一定的抗噪能力。但是，基于密度的聚类方法使用的参数有时很难确定，且这些参数在聚类过程中保持固定，从而难以适应空间密度变化大的情况，聚类结果易受邻域内空间离群点的影响。基于距离的聚类算法将实体间空间距离和非空间属性距离均小于一定阈值的实体聚为一类，不考虑非空间属性时等同于MinPts=1的基于密度的聚类方法，亦存在阈值不易确定且很难适应空间分布不均匀情况下聚类的缺陷。(4)基于图论的聚类算法，代表算法有ZEMST(Zahn, 1971)、SFMST(Paivinen, 2005)、AUTOCLUST(Estivill-Castro & Lee, 2000)等。基于图论的聚类算法首先在全部数据集内构建一个完全图，每个实体都视为图的一个顶点，继而通过打断图的不一致边，形成一系列的子图，每个子图即视为一个簇。然而当空间分布不均匀时，不一致边很难确定。(5)混合聚类算法，代表算法有STING(Wang 等, 1997)、Wave Cluster 基金项目:国家863计划项目(2009AA12Z206);地理空间信息工程国家测绘局重点实验室开放基金重点项目(200805);江苏省资源环境信息工程重点实验室(中国矿业大学)开放基金项目(20080101) 第一作者简介:邓敏(1974,)，男，江西临川人，博士，教授，博士生导师，主要研究方向为时空数据挖掘、推理与分析，发表 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 90余篇。Email: dengmin208@tom.com (Sheikholeslami 等, 1998)、CLIQUE(Agrawal 等, 1998)、GDCIC(Song & Ying, 2006)、NN-Density(Pei 等, 2006)等。该类算法综合采用多种类型算法进行聚类，其中采用格网结构对空间实体进行储存，进而结合其它聚类算法进行混合聚类是最常见的形式，这种算法最主要的优点是减少全局遍历，从而提高了算法的效率。然而，混合聚类算法仍然具有上述几种聚类算法中存在的缺陷，如最常用的格网-密度混合聚类算法只是对高密度区域较为敏感，很难适应空间局部密度差异较大情况下的聚类。此外，在某些情况下，混合聚类算法的聚类质量降低，如STING算法。 综上所述，现有空间聚类算法都很难适应空间数据分布差异较大的情况，同时聚类结果多依赖于聚类参数的选择，影响了其实用性。为此，本文首先引入数据场概念对空间聚类问题进行描述，继而发展一种适用于空间聚类的场，并给出聚类度量指标，在此基础上提出了一种基于场论的空间聚类算法。 2. 基于场论的空间聚类算法原理及描述 空间聚类是将空间数据库中的空间实体划分成具有一定意义的若干簇，使得每个簇内实体具有最大相似度，而簇间实体差别最大。然而，聚类“相似度”和“差别”大多是采用空间实体间的距离来度量(Kovács 等, 2006)，缺乏实际的物理意义。本文受物理学中场论思想的启发，从数据场的角度对空间聚类问题进行解释，提出一种适用于空间聚类的数据场，即凝聚场。 2.1 凝聚场与凝聚力 数据通过数据辐射将其数据能量从样本空间辐射到整个母体空间，接受数据能量并被数据辐射所覆盖的空间，叫做数据场(王树良, 2002)。广义上讲，凝聚场也是一种数据场，本文将其定义为一种有源矢量场，具体描述为:(1)空间中每个实体均视为一个具有单位质量的质点，亦可为一个凝聚场源(简称场源);(2)每个场源在其周围一定范围内产生一个虚拟作用场，本文称之为凝聚场;(3)位于凝聚场内的任何其他空间实体均将受到场源实体的内向引力作用，这种引力称为凝聚力。基于凝聚场理论，空间聚类的机理和过程可以描述为:(1)凝聚场内所有实体受到的凝聚力标量和越大，则表明场源的“吸附”能力越强。(2)每个空间簇的形成均是从一个“吸附”能力较强的场源开始，各实体不断向外“吸附”其它实体，最终形成一个簇。(3)同一个簇内实体间的凝聚力作用较强，而不同簇内的实体之间凝聚力的作用较弱。显然，离群点受到的凝聚力较小。 凝聚场的空间分布规律可以用矢量场强函数进行描述。对于空间聚类而言，短程场作用更有利于揭示数据分布的聚簇特性，即凝聚场的场强在有限的影响范围内迅速衰减。淦文燕等(2006)提出了选用衰减较快标量势函数及影响因子的方法，然而影响因子的选择非常困难，从而增加了聚类的难度。为此，本文借助Voronoi图和Delaunay三角网对空间进行划分，继而构造了凝聚场的场强函数表达形式。为了便于理解和描述，下面给出一些定义。 定义1 二维Voronoi图(陈军, 2002):给定空间实体集合P，P={p, p, p …, p}，对于P中任一点123,n Vp，其对应的Voronoi多边形p可以定义为: ii 2Vp={x?d(x, p) ?d(x, p), p, p?P, i?j , x?R} (1) iijij 式中:d表示欧氏距离函数。P中所有点的Voronoi多边形构成点集P的Voronoi图(如图1实线所示)，表达为: VVVVV P= { p, p, p, …, p} (2) 123n VP的对偶图为Delaunay三角网，记为D(P)，如图1虚线所示。 VV定义2 直接Voronoi邻近实体(Gold, 1992):给定空间实体集合P，p, p?P，若p和p具有公共ijijVoronoi边，则p和p互为直接Voronoi邻近实体。实体p的所有直接邻近实体即为p的Delaunay邻近实ijii体，表示为ND(p)。如图1，p点的直接邻近实体为p，p，p，p和 p。 i123456 V定义3 直接Voronoi区域:对于空间实体p，p与p的直接Voronoi邻近实体对应的Voronoi多边形iii VVV所构成的区域称为p的直接Voronoi区域，记为DNV(p)。如图1，p的直接Voronoi区域包括p, p, p, ii1123VVVp, p, p。 456p7 pp15 8 p3 p4 p9 p1 p14 p5 p2 p6 pp 13 10 pp12 11 图1 凝聚场 二维Voronoi图可以视为以平面内每个点作为生长核，以相同速率向外扩张，直到彼此相遇后停止生长，反映了实体天然的“势力范围”。根据这种特性，可以表达凝聚场的场强函数为: 1,x,DNV(p),1i (3) E,ke，,,,ppx2,ixDNVp，,,,()dpx(,)ii, 式中:E为场源(亦是一个实体)p在空间上产生的凝聚场的场强;k为凝聚场辐射因子，本文设置为1;p x为任意一个空间位置;d(p, x)为实体p与x的欧氏距离;σ为衰减因子;e为p指向x的单位矢量。 iiipxii 从式(3)可以看出，一个场源产生的凝聚场，在其直接Voronoi区域内，场强函数的衰减满足距离平方反比关系;而在空间其他的区域场强函数迅速衰减，迅速达到可以忽略的程度。同时，对凝聚场的假设也满足数据场的基本特征，即必须同时满足独立性、就近性、遍历性、叠加性、衰减性和各向同性等条件(王树良, 2002)。进而，可以表达两个实体间的凝聚力为: m1,,()qNDp,1q(,),,,,,FpqEmkmee (4) ,,Cpqqpqpq2,2,，,,q,ND(p)(,)(,)dpqdpq, 式中:m为实体q的质量，考虑到可以将空间点实体均视为单位质点，故令m为1;d(p, q)为实体p与qqq 的欧氏距离;σ表示衰减因子;e表示p指向q的单位矢量。 pq 分析式(4)可以发现，一个场源只对其Delaunay邻近实体有明显的凝聚力作用，对其它空间实体的作用可以忽略。此外，与Wright(1977)、淦文燕(2006)等采用的“引力”概念不同，本文采用的凝聚力是一种矢量，并顾及了力的方向特性，这亦是与传统聚类度量指标最大的区别。 2.2 基于场论的空间聚类算法原理 根据2.1节的假设，基于场论的空间聚类算法包括两个核心步骤:(1)每个实体的邻近实体的获取;(2)从“吸附”能力作用较强的场源开始，各实体不断向外“吸附”其他邻近实体，最终生成空间簇。下面简要阐述这两个步骤的基本原理。 获取场源邻近实体实质上是确定与场源凝聚力较大的若干实体。由于凝聚力是一种矢量，根据作用力与反作用力的原理，场源“吸引”凝聚场域内其它实体的同时，其它实体也会对场源产生一个反作用力，场源所受凝聚力的合力方向一般指向局部的一个聚类中心(李海民, 1999)，即场源对该合力的反方向实体的“吸附”能力最强。凝聚场中各实体对场源的凝聚力合力表达为: FFpq,(,)， q?ND(p) (5) ,TC 。若某一实体对场源的凝聚分力与合力的夹角小于90，则分力对合力有增强的作用，可以认为场源能对其有“吸附”作用，该实体极有可能成为场源的邻近实体。如图2(a)，虚线箭头表示合力F，显然F(A,B), TC 。。F(A,C), F(A,D)与F夹角小于90，则A可以对B，C，D进行“吸附”;F(A,E) 与F夹角大于90，则CCTCTA点无法对E进行“吸附”，因此B，C，D更有可能为A的邻近实体。 A B C B FT FT A C E D D E (a) (b) 图2 邻近实体获取 (a)凝聚力矢量计算简例; (b) 边界效应简例 然而，上述判别方式没有顾及一种特殊情况，即 “边界效应”。如图2(b)，以A点为场源计算聚类 。场内合力方向为虚线箭头所指方向，并且四个分力与合力夹角都小于90。然而D，E两点明显与A点不邻近，这是由于A点位于簇的边界上，其它簇内的实体对其产生了干扰。因此，下面进一步给出一个凝聚力标量的约束条件，提出一种三步法判别邻近实体的方法，描述为: ? 给定场源p，首先判别候选邻近实体，即所有对场源的凝聚力与场源所受凝聚力合力的夹角小于 。90的实体均被视为候选邻近实体，记为CNS(p)，表达为: 。 CNS(p)={q?θ(F(p, q), F)<90，q?ND(p) } (6) CT 式中:θ(F(p, q), F)表示各分力与合力的夹角。 CT ? 平均凝聚力，即在候选邻近实体集合中获得凝聚力的平均大小。为了避免少部分极小值的干扰， 首先除去最小的[N/2]个力后，再计算其他力的平均值，记为E(F)，其中[]表示取整操作，N为候 选邻近实体数量。 ? 邻近实体获取。由于其他簇内实体对边界点的凝聚力远小于簇内实体对其产生的凝聚力，如图2 )，D、E点对A的凝聚力远小于B、C点。于是，本文在大量实验的基础上给出了一个标量(b 约束条件:若凝聚力标量大小超过平均凝聚力的五分之一，则将其视为场源的邻近实体，记为 NS(p)，表达为: NS (p)={q??F(p, q)?>E(F)/5，q?CNS(p)} (7) C 式中:?F(p, q)?表示分力的标量大小。 C 经过以上计算和识别过程，如图2(a)中A的邻近实体为B，C，D，很好地与E点进行了分离;而(b)中A点的邻近实体为B，C，排除了D，E点的干扰，达到了获取场源邻近实体的目的。进而，另一个重要步骤在于从“吸附”能力较强场源开始，不断向外“吸附”邻近实体，生成空间簇。直观上，一个场源对其Delaunay邻近实体的凝聚力标量和越大，则可以认为其“吸附”能力越强。其中，凝聚力标量和计算表达式为: FFpq,(,)，q?ND(p) (8) ,TC 式中:?F(p, q)?为凝聚力的标量大小。本文将“吸附”能力较强的场源称为聚类核，并进行如下定义: C 定义4 聚类核:给定空间实体集合P，P中每个实体凝聚力标量和构成集合F(P)，凝聚力标量和最大的实体即为聚类核，记为Core(P)，表示为: Core(P)= p，SF(p) = max(F(P)) (9) 进而，基于场论的空间聚类算法的基本过程可以描述为: ? 在每个实体产生的凝聚场中分别获取其邻近实体。 ? 选取聚类核，各实体不断向外“吸附”其邻近实体，直到生成一个簇;只有一个实体的簇，标记 为异常点。 ? 如果仍有实体未加入簇中或未被标记为异常点，则重复步骤?。 空间实体一旦加入某个簇中，即从P中退出，以至于每个簇生成时都是从当前实体中选凝聚力标量和最大的点作为聚类核。根据凝聚力的表达形式可知，一个场源的凝聚力标量和越大，则其与邻近实体的距离越短，故空间密度越大。于是，空间密度大的实体最先生成簇。最终在整个空间中，由高密度到低密度依次生成一系列的簇，故可以自动适应空间局部密度的变化。为了避免生成过于松散的空间簇，可以对聚类核进行限制，即:凝聚力标量和极小的实体(与平均值之差的绝对值大于三倍 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 差)，不将其作为聚类核。 2.3算法描述 根据上述基本原理，给定一个空间数据库SDB，基于场论的空间聚类算法(即FTSC算法)可以描述如下: ? 在整个数据集中生成Delaunay三角网，获得每一实体p的Delaunay邻近域实体集合;同时计算每i 个实体的凝聚力的标量和，获得凝聚力标量和集合。 ? 针对SDB中任一点p获得其邻近实体集合。 i ? 选取凝聚力标量和最大的实体p，将其作为聚类核，将p与其邻近实体聚为一类，存入集合C中xx 并进行标记，标明p已进行“吸附”操作。 x ? 针对C中未进行“吸附”操作的任一实体p，将其邻近实体不断加入C中，直到C中所有实体均j 已进行“吸附”操作为止，一个簇生成结束。 ? 统计C中实体的数目Cnum。如果Cnum<2，则将C中实体标记为异常点。 ? 如果SDB中仍有实体未被加入簇中或被标记为异常点，则搜索下一个聚类核，重复?-?步骤;否 则，返回聚类结果。 3. 实验验证与分析 下面设计两个实验来验证本文所提出的FTSC算法的正确性。实验一采用模拟数据，共包含四组数据，其中模拟了Ester等(1996)使用的三组经典数据库，并另外设计了一组数据;实验二采用FTSC算法针对两组实际地理空间数据进行实际应用分析。两个实验的结果分别与经典的DBSCAN算法进行比较。 3.1模拟算例分析与比较 本实验采用Ester等人(1996)使用的三组数据库来验证FTSC算法可以发现任意形状的簇，并且具有抗噪性。图3(a),(c)给出三个数据库的数据分布情况及各自生成的Delaunay三角网;图3(d),(f)给出了FTSC算法的聚类结果。 (a) (b) (c) (d) (e) (f) 图3 模拟数据库及FTSC算法聚类结果(×—异常点) (a)数据库1; (b) 数据库2; (c) 数据库3; (d) 结果1; (e) 结果2; (f) 结果3 与DBSCAN算法(Ester 等, 1996)聚类结果比较，图3(d)的聚类结果与DBSCAN算法在Eps=4,9，Minpts=1,11时的聚类结果完全一致，图3(e)的聚类结果与DBSCAN算法在Eps=4,6，Minpts=1,17时的聚类结果完全一致。图3(f)所示数据库3的聚类结果与DBSCAN算法在Eps=4，Minpts=2,6时的聚类结果完全一致。此外，通过实验发现:(1) FTSC算法能够探测任意形状的簇;(2) FTSC算法对于靠近簇的异常点很敏感，而且可以区分非常接近的簇;而DBSCAN算法则需要非常严格的参数设定才能达到相同的效果。例如，对于数据库3，DBSCAN算法的参数限制非常严格，尤其是Eps的设定，稍微增大则无法区分相邻的簇或离簇较近的异常点。 为了验证FTSC算法能够自动适应空间分布不均匀情况下的聚类，本文设计了另一组数据(即数据库4)来进行测试。如图4(a)，模拟数据共包含了336个数据点，预设6个空间簇和11个异常点(图中用符号“×”标记)。这组数据密度变化较大，形状各异，同时包含了不同密度区域邻接的情况。图4(b)为FTSC算法的聚类结果。为了便于比较，图4(c),(h)给出了DBSCAN算法取不同参数时的聚类结果，其中MinPts采用了Birant 和Kut(2007)给出的最优设置，即MinPts= ln(336)?6。 (a) (b) (c) (d) (e) (f) (g) (h) 图4 FTSC算法与DBSCAN算法聚类结果比较(×—异常点) (a)数据库4; (b) 结果4; (c)Eps=3, Minpts=6; (d) Eps=5, Minpts=6; (e) Eps=7, Minpts=6; (f)Eps=9, Minpts=6 (g) Eps=11,17, Minpts=6; (h) Eps=18, Minpts=6 分析图4中DBSCAN的聚类结果可以发现:DBSCAN算法对于空间分布不均匀或不同的簇邻接情况下的聚类效果很差，当Eps设定过小时，低密度区域的点易被判为异常点，如图4(c),(e);随着Eps的增大，不同密度的空间簇很难进行区分，直到所有实体聚为一类，如图4(f),(h)，并且最多只能正 确区分三个簇，如图4(f)。而FTSC算法对各个簇以及异常点都能较好地区分。通过上述实验表明，本文选取的凝聚力标量约束条件具有较好的普适性。下面采用实际数据来进一步验证FTSC算法的实用性。 3.2 实际算例分析与比较 本实验使用FTSC算法分别进行城市空间分布的集聚模式挖掘以及气象站点选址优化的实际应用研究。实验数据分别为云南省126个县级城市空间数据和湖南省96个气象站点空间数据，如图5(a)和(e)所示。针对云南省县级城市空间数据，FTSC算法的聚类结果如图5(b)所示，相应DBSCAN算法的聚类结果如图5(c)、(d)所示。针对湖南省气象站数据，FTSC算法的聚类结果如图5(f)所示，相应DBSCAN算法的聚类结果如图5(g)、(h)所示。限于篇幅，本文只给出了DBSCAN算法具有代表性的聚类结果，其中MinPts= ln(n)，n为空间实体数量。 昆明 大理 个开蒙地区 玉溪 (a) (b) (c) (d) (e) (f) (g) (h) 图5 FTSC算法与DBSCAN算法聚类结果比较 (× —异常点) (a)云南省县级城市空间分布;(b)结果5; (c) Eps=60km, Minpts=5;(d) Eps=80km, Minpts=5 (e)湖南省气象站点空间分布;(f)结果6; (g) Eps=40km, Minpts=4; (h) Eps=65km, Minpts=4 分析云南省县级城市集聚模式的挖掘结果可以发现:(1)DBSCAN算法难以适应实际空间数据分布不均匀的特性，不能很好地发现城市的局部集聚模式，而FTSC算法则可以发现不同密度的空间簇，且各个簇内实体的分布较为均匀;(2)进一步分析FTSC算法聚类获得的各个簇，可以发现实体较多且密度相对较大的空间簇主要集中在大理、昆明、玉溪、个开蒙(个旧、开远、蒙自)地区周边，这些簇中的实体在空间上表现为局部聚集的趋势，反映出城市的发展状况，可以认为这些区域的城市化水平相对较高，城市较为密集。当前云南省城市发展状况及空间分布已有的研究成果表明(吴启焰等, 2007):“云南省城市分布趋向大分散、小集中的格局，发展较好的小城市主要从几个中心向外扩延，特别是昆明市、个开蒙地区、玉溪市、大理市周边地区，城市发展水平远高于全省城镇发展水平”。由此可见，本文空间聚类分析的结果与实际情况非常吻合。 气象站在布局设置时一般要求其空间分布要尽可能均匀，然而实际上在某些局部经常会出现一些过分稀疏或密集的区域，因此对这些区域进行优化设置在气象研究中具有重要意义。分析FTSC算法空间聚类结果可以发现:(1)所有站点整体上主要形成两个较大的空间簇，说明气象站点总体分布比较均匀，符合气象站点空间布局的基本要求;(2)在局部发现了数个空间离群点和小簇，这些区域的气象站点分布相对 过于稀疏或密集，不利于气象因子的恢复，因而应考虑调整气象站布局(如增设气象站点)进行局部优化。此外，采用这些气象站点采集的数据进行气象因子恢复时可能会有较大的误差，在进行深层次的时空数据分析时需要顾及。而DBSCAN算法的聚类结果难以反映气象站点分布的局部信息，对于气象站点空间分布优化的指导价值很有限。 3.3 实验总结与讨论 通过模拟算例与实际算例分析以及与DBSCAN算法的比较，充分验证了FTMS算法在进行空间模式挖掘方面的有效性和优越性。同时可以进一步分析本文提出的FTMS算法与传统的空间聚类算法的联系与区别。FTMS算法采用凝聚力来度量空间聚类中的相似性问题，即空间实体通过相互间力的吸引作用而聚集成簇，从凝聚力的定义中可以发现，这种相似性度量准则也是与距离密切相关的，这一点与传统的空间聚类相似性度量方法的作用是一致的。也就是说，传统聚类中簇内实体的相似性在空间聚类中体现的是空间相关性，即空间聚类是对空间数据依据其空间相关性进行划分，同一个簇内的实体其空间相关性要尽可能大。但是，凝聚力将实体之间距离的关系转化为矢量力的关系，具有明确的物理意义，顾及了实体间的方向关系，易于对空间聚类的结果进行解释。尤其是，两个空间簇邻接时的区分问题采用凝聚力的矢量关系进行度量，这个难点问题就迎刃而解了，这主要是因为不同簇中实体受到凝聚力合力的方向具有较强的可区分性。 此外，空间聚类的多尺度与有效性评价问题虽然在本文中没有具体涉及，但也是空间聚类的两个重要研究内容。空间相关性是依赖尺度变化的，故在不同的尺度上空间聚类的相似性程度判断将有所区别，如在大城市周围可能分布若干卫星城市，在大尺度上所有的城市构成一个空间簇;而随着尺度减小，一些卫星城市可能又会构成一些更为细致的空间簇。因此，空间聚类的多尺度问题应该采取一种“自上而下”的策略进行考虑，从大尺度到小尺度进行层次聚类。对于空间聚类有效性的评价，现有的聚类有效性评价指标多是从簇内实体的紧实度和簇之间的分离程度进行度量，即簇内实体越紧密，簇之间分离度越大，则聚类效果越好(Kovács 等, 2006)。而本文在很大程度上仅是从视觉感知以及根据先验知识对聚类结果的有效性进行评价的。在实际应用中，对聚类结果进行有效性评价通常还需要进一步考虑空间数据的多尺度特征，因为在不同尺度上进行空间聚类得到的结果可能代表着不同的空间格局或模式。 4. 结论与展望 针对已有空间聚类算法大多需要输入参数，人为干预多且不适应空间数据不均匀分布的局限，本文首先从空间数据场的角度对空间聚类问题进行解释，发展了一种适用于空间聚类的凝聚场。在此基础上，提出了一种基于场论的空间聚类算法—FTSC。通过模拟实验和实际数据验证，以及与经典的DBSCAN算法进行比较，发现:(1)FTSC算法可以发现任意形状的空间簇，可以有效发现空间异常点;(2)FTSC算法具有自适应性，可以处理空间分布不均匀、空间簇邻接等复杂情况下的聚类;(3)FTSC算法不需要用户输入参数，避免了过多人为因素的干扰，实用性强。 本文的进一步研究工作主要包括:(1)利用统计学方法确定凝聚力标量约束条件并加以证明，有利于本文所提聚类方法的进一步完善。本文对凝聚力标量约束条件的设置是建立在大量实验的基础上，并没有给出严密的理论证明;(2)研究顾及非空间属性的聚类方法，拓展空间聚类的应用范围;(3)构建GRID索引，发展一种混合聚类算法，提高算法的运行效率，以适用于海量空间数据库;(4)研究基于场论的空间聚类有效性评价方法。 REFERENCES Agrawal R, Gehrke J, Gunopulos D and Raghavan P. 1998. Automatic subspace clustering of high dimensional data for data mining applications. Proceedings of the 1998 ACM-SIGMOD International Conference on Management of Data, Settle WA, 94-105. Ankerst M, Breunig M , Kriegel H P and Sander J. 1999. OPTICS: ordering points to identify the clustering structure. Proceedings of the 1999 ACM-SIGMOD International Conference on Management of Data. Philadelphia, PA, 49-60. Bar-shalom Y and Blair W D. 2000. Multitarget-multisensor tracking: applications and advances Volume III. Artech House, Norwood, MA. Birant D and Kut A. 2007. ST-DBSCAN: an algorithm for clustering spatial–temporal data. Data & Knowledge Engineering, 60(1): 208-221. Blackman S and Popoli R. 1999. Design and analysis of modern tracking system. Artech House, Norwood, MA. Chen J. 2002. Dynamic Spatial Data Model Based on Voronoi. Beijing : Surveying & Mapping Press. Dave R N and Bhaswan K. 1992. Adaptive fuzzy c-shells clustering and detection of ellipses. IEEE Transactions on Neural Network, 3(5): 643-662. Ester M, Kriegel H P, Sander J and Xu X. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the 2nd the International Conference on Knowledge Discovery and Data Mining. Portland, OR, 226-231. Estivill-Castro V and Lee I. 2000. AUTOCLUST: automatic clustering via boundary extraction for mining massive point-data sets. Proceedings of the Fifth International Conference on Geo-computation, Beijing, China. Gold C M. 1992. The meaning of “Neighbor”. Theories and Methods of Spatial-Temporal Reasoning in Geographic Space, Lecture Notes in Computing Science No. 639, Berlin. Gan W Y, Li D Y and Wang J M. 2006.A hierarchical clustering method based on data fields. ACTA ELECTRONICA SINIA, 34(2): 258-262. Guha S, Rastogi R and Shim K. 1998. CURE: an efficient clustering algorithm for large databases. Proceedings of 1998 ACM-SIGMOD International Conference on Management of Data. Seattle, Washington, 73-84. Guha S, Rastogi R and Shim K. 1999. ROCK: a robust clustering algorithm for categorical attributes. Proceedings of the International Conference of Data Engineering. Sydney, Australia, 512-521. Hofmann-wellenhof B, Lichtenegger H and Collins J. 1994. Global positioning system: theory and practice. Springer-Verlag Wien, New York. Karypis G, Han E H and Kumar V. 1999. Chameleon: hierarchical clustering using dynamic modeling. IEEE Computer, 32(8): 68-75. Kovács F, Legány C and Babos, A. 2006. Cluster validity measurement techniques. Proceedings of the 5th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering and Data Bases, Madrid, Spain, 88-393. Li G Q, Deng M, Cheng T and Zhu J J. 2008. A dual distance based spatial clustering method. ACTA GEODAETICA et CARTOGRAPHICA SINICA, 37(4): 482-488. Li G Q, Deng M, Liu Q L and Cheng, T. 2009. A spatial clustering method adaptive to local density change. ACTA GEODAETICA et CARTOGRAPHICA SINICA, 38(3): 255-263. Li H M. 1999. Research on the performance of genetic algorithms and their applications in clustering analysis. Xian: Xidian University. Liu P, Zhou D and Wu N J. 2007. VDBSCAN: varied density based spatial clustering of applications with noise. Proceedings of IEEE International Conference on Service System and Service Management, Chengdu, China, 1-4. Macqueen J. 1967. Some methods for classification and analysis of multivariate observations. Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, University of California Press, 281-297. Mao Z Y and Li L. 2004. The Measurement of Spatial Patterns and Its Applications. Beijing : Science Press. Ng R and Han J. 1994. Efficient and effective clustering method for spatial data mining. Proceedings of the 1994 International Conference on Very Large Data Bases, 144-155. Paivinen N. 2005. Clustering with a minimum spanning tree of scale-free-like structure. Pattern Recognition Letter, 26(7): 921– 930. Pei T, Zhu A X, Zhou C H, Li B L and Qin C Z. 2006. A new approach to the nearest-neighbor method to discover cluster features in overlaid spatial point processes. International Journal of Geographical Information Science, 20(2): 153-168. Sheikholeslami G, Chatterjee S and Zhang A. 1998. Wave Cluster: a multi-resolution clustering approach for very large spatial databases. Proceedings of the 24th International Conference on Very Large Databases. New York City, 428-439. Song G and Ying X. 2006. GDCIC: a grid-based density-confidence-interval clustering algorithm for multi-density dataset in large spatial databases. Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications, 713–717. Wang S L.2002.Data field and cloud model based spatial data mining and knowledge discovery. Wuhan: Wuhan University. Wang W, Yang J and Muntz R. 1997. STING: a statistical information grid approach to spatial data mining. Proceedings of the 1997 International Conference on Very Large Data Bases, Athens, Greece, 186-195. Wright W E. 1977. Gravitational clustering. Pattern Recognition, 9(3): 151-166. Wu Q Y and Chen H. 2007. Urban Economic Effect Region Spatial Evolution: Taking Yunnan Province as an Example. Acta Geographica Sinica, 62(12): 1244-1252. Zahn C T. 1971. Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Transaction on Computers C20 (1): 68-86. Zhang T, Ramakrishnan R and Livny M. 1996. BIRCH: an efficient data clustering method for very large databases. Proceedings of the International Conference Management of Data, Montreal, Canada, 103-114. 附中文参考文献: 毛政元, 李霖. 2004. 空间模式的测度及其应用. 北京: 科学出版社. 淦文燕, 李德毅, 王建民. 2006. 一种基于数据场的层次聚类算法. 电子学报, 34(2): 258-262. 李光强, 邓敏, 刘启亮, 程涛. 2009. 一种适应局部密度变化的空间聚类方法. 测绘学报, 38(3): 255-263. 李光强, 邓敏, 程涛, 朱建军. 2008. 一种基于双重距离的空间聚类算法. 测绘学报, 37(4): 482-488. 王树良. 2002. 基于数据场与云模型的空间数据挖掘和知识发现. 武汉:武汉大学博士学位论文. 陈军. 2002. Voronoi动态空间数据模型. 北京:测绘出版社. 李海民. 1999. 遗传算法性能及其在聚类分析中的应用研究. 西安:西安电子科技大学博士学位论文. 吴启焰, 陈浩. 2007. 云南城市经济影响区空间组织演变规律. 地理学报, 62(12): 1244-1252. A Field-Theory Based Spatial Clustering Method 1112 Deng Min, Liu Qiliang, Li Guangqiang, Cheng Tao (1. Department of Surveying and Geo-informatics, Central South University, Changsha 410083, China; 2. University College London, Department of Civil, Environmental and Geomatic Engineering, Gower St, WC1E 6BT, London) Abstract: Spatial clustering is an important approach for spatial data mining and spatial analysis. It can be used to discover the spatial association rules and spatial outliers in spatial datasets. Most current spatial clustering algorithms have two aspects of limitations. On the one hand, the inhomogeneity of spatial distribution of the spatial points is not fully considered, so that it is almost impossible to obtain satisfied clustering results in the case that the spatial points distribute in different densities. On the other hand, more input parameters are required. To overcome these limitations, the data field theory is firstly employed to describe the issue of spatial clustering, where a field for spatial clustering, called aggregation field, is developed. Then a novel concept of aggregation force is utilized to measure the degree of aggregation among the entities. Further, a field-theory based spatial clustering algorithm (FTSC in abbreviation) is proposed. This algorithm does not involve the setting of input parameters, and can automatically generate the neighbor entities of each spatial point. A series of recursion strategies are implemented to obtain different clusters according to the local densities of spatial distribution. Indeed, the FTSC algorithm can adapt to the change of local densities among spatial points. Finally, two experiments are presented to illustrate the advantages of the FTSC algorithm. The practical experiment indicates that FTSC algorithm can discover urban aggregation pattern effectively. The comparative experiment is made to further demonstrate the FTSC algorithm superior than classic DBSCAN algorithm. Through these two experiments, one can see clearly that the FTSC algorithm is very robust and suitable to discover the clusters with different shapes. Key Words: spatial clustering; aggregation force; field theory; spatial data mining