（地图学与地理信息系统专业论文）带约束条件的交互式空间聚类算法研究.pdf

摘要 空间聚类，作为空间数据挖掘的一个重要分支，是根据某个相似性准则对空间实体集进行自 动分组，达到组内差异最小、组间差异最大的过程。从某种意义上讲，空间聚类也可以看作是一 种约束聚类，空间结构是聚类的约束条件。由于空间聚类的研究对象空间数据本身的特性以及空 间对象之间具有复杂的关系，使得一般的聚类算法适用于空间数据时往往会遇到以下几个重点与 难点问题：( 1 ) 聚类算法的效率问题，( 2 ) 带约束条件的聚类问题，( 3 ) 空间与属性一体化聚类的问 题，( 4 ) 聚类的可解释性与可用性问题。 为此本文提出一种以d e l a t m a y 三角网为基础白喉次空间聚类算法，充分运用d e l a u n a y 三角 网所具备的最近相邻性、唯一性等特性，来维护空间对象之间的邻近关系，利用邻近关系还可以 缩小计算两两对象之间距离的搜索空间，同时结合空间对象相互作用中的引力模型，实现将空间 对象的邻近关系与其属性特征一体化作为相似性准则，综合对象间的相邻关系和空间障碍物作为 约束条件进行聚类。 在面状数据聚类中，离散的面状数据可以转换为点状数据进行处理；而连续的面状数据可以 利用其自身的空阿邻接关系来构建邻接图来实现相邻约束的聚类，然后利用两地交通距离来代替 原始的欧式距离，来解决障碍约束的聚类问题。 在上述理论研究和算法设计的基础上，本文结合空间聚类可视化问题，利用n e t 开发平台 实现了本论文提出的两个聚类算法，并给出了聚类分析在城市群划分与居民地综合过程的两个应 用实例，对本文所提出算法的有效性进行了验证。 关键词：空间聚类，约束聚类，d e l a u n a y 三角网，最小生成树，可视化 a b s t r a c t a sa ni m p o r t a n tb r a n c ho fs p a t i a ld a t am i n i n g ，s p a t i a lc l u s t e r i n ga l g o r i t h mw h i c hg r o u p ss i m i l a r s p a t i a lo b j e c t si n t oc l u s t e r sc a nb eu s e df o r t h ei d e n t i f i c a t i o no f a r e a ss h a r i n gc o m m o nc h a r a c t e r i s t i c s i n as e n s e ，t h es p a t i a lc l u s t e rc a nb es e e na sac o n s t r a i n e dc l u s t e r t h es p a t i a ls t r u c t u r e sa r et h ec o n s t r a i n e d c o n d i t i o n s d u et ot h es p a t i a ld a t aa n ds p a t i a lc h a r a c t e r i s t i c so fo b j e c t sw i t hc o m p l e xr e l a t i o n s h i p s ，a c l u s t e r i n ga l g o r i t h ma p p l y i n gt os p a t i a ld a t ao f t e nn e e d st oa d d r e s st h ef o l l o w i n gi m p o r t a n ta n dd i f f i c u l t q u e s t i o n s ：( 1 ) a l g o r i t h me f f i c i e n c y ，( 2 ) t h ec o n s t r a i n e dc l u s t e r i n g ，( 3 ) i n t e g r a t i o no fs p a t i a la n da t t r i b u t e c l u s t e r i n g ，a n d ( 4 ) i n t e r p r e t a b i l i t ya n da v a i l a b i l i t yo ft h ec l u s t e r i n g t h em a i nc o n t r i b u t i o no ft h i sp a p e ri st op r e s e n tan e wh i e r a r c h i c a lc l u s t e r i n ga l g o r i t h mb a s e do n d e l a u n a yt r i a n g u l a t i o n ，w h i c hi n t e g r a t e st h es p a t i a lr e l a t i o n sa n da t t r i b u t ec h a r a c t e r i s t i c f i r s to fa l l ， c r e a t ead e l a u n a yt r i a n g u l a t i o nb yu s i n gs a m p l ep o i n t sa st h ep o 协to ft r i a n g l e t h ea u t h o re x p r e s s e s t h es p a t i a lr e l a t i o n so fs a m p l ep o i n t st h r o u g ht h et o p o l o g yo ft h ed e l a u n a yt r i a n g u l a t i o n t h e nf o r e v e r ys a m p l ep o i m ，a n a l y s i st h ea t t r i b u t e ，a n df i n do u tt h es a m p l ep o i n tb e i n gj o i n e da n dt h em a x i m a l a t t r a c t i v eb yi m p o s i n gg r a v i t ym o d e l t h i sk i n do ft w os a m p l et u r nt o w a r d st oac l u s t e r 。a n dt h e a l g o r i t h mi sf i n i s h e du n t i la l lo ft h es a m p l e sa r ea r r a n g e dt ob eo n ec l u s t e r s o m e t i m e sc l u s t e r i n gr e s u l t s a r eb yt h ei m p a c to fo b s t a c l e s ，s u c ha sr i v e r s ，m o u n t a i n s ，e t c 、7 v h e nf a c i n gt h ec o n t i n u o u sf a c i a le l e m e n t sw i t ht o p o l o g i c a lr e l a t i o n s ，c o n s t r u c tt h em i n i m u m s p a n n i n gt r e eo nt h eb a s i so ft h ea d j a c e n tm a p d i v i d et h et r e eb yd i s s i m i l a r i t i e sb e t w e e n 诵t l lt h e i n r l l d e ro fh i e r a r c h i c a lc l u s t e r i n gm e t h o dd i v i s i o n u s et h et r a f f i cd i s t a n c et or e p l a c et h ee u c l i d e a n d i s t a n c ei no r d e rt oc l u s t e r i n gd a t ai nt h ep r e s e n c eo fo b s t a c l e s o nt h eb a s i so ft h e o r e t i c a ls t u d ya n da l g o r i t h m si m p r o v e m e n t ，w ei m p l e m e n tt h e s et w os p a t i a l c l u s t e r i n ga l g o r i t h m su s i n gm i c r o s o f td o t n e tp l a t f o r m t h e nc i t et w oa p p l i c a t i o ne x a m p l e st ov e r i f yt h e e f f e c t i v e n e s sa n dee f f i c i e n c yo ft h ea l g o r i t h m k e y w o r d ：s p a t i a lc l u s t e r ，c o n s t r a i n e dc l u s t e r ，d e l a u n a yt r i a n g u l a t i o n ，m i n i m u ms p a n n i n gt r e e ， v i s u a l i z a t i o n i i 插图索引 图1 - 1 论文组织与章节安排5 图2 1 客户服务中心选址问题示意图6 图2 - 2 空间属性一体化聚类结果图6 图2 - 3 带障碍物的距离计算8 图2 - 4d c l a u n a y 三角网所表达的空间相邻关系1 0 图2 - 5 以机器或以人为中心的聚类过程示意图1 l 图2 6 不同尺度图像变化示意图。1 2 图2 7 本文研究的带约束条件的空间聚类分类定位图1 4 图2 - 8 对集合 咖，c , d ，e 的层次聚类1 5 图3 - 1d e l a u n a y 三角网和v o r o n o i 图1 7 图3 - 2 基于约束d e l a u n a y 三角网的聚类算法1 8 图3 3 查找与约束边相交的三角形的边。2 l 图3 - 4 交换相交三角形边2 l 图3 - 5 相交边交换后三角形的l o p 优化处理。2 l 图3 - 6 边界约束生成o d t 2 2 图3 7 第三阶段凝聚式层次聚类算法流程图。2 3 图3 - 8 原始数据分布图2 5 图3 - 9d e l a u n a y 三角网2 s 图3 1 0 根据属性特征值大小符号化空间点对象2 6 图3 1 1 无障碍物第一层次聚类2 6 图3 1 2 受障碍物影响下的第一层次聚类2 7 图3 1 3 第一级聚类结果2 7 图4 1 距离简化计算公式。3 0 图4 _ 2 连续面模式与点模式的模型转换3 l 图4 3 非连续面模式与点模式的模型转换。3 l 图4 4 点、最小生成树、基于最小生成树的聚类。3 2 图4 - 5 基于邻接图的空间聚类基本步骤3 3 图4 6m s t 算法流程图3 4 图4 7 根据面状空间邻接关系生成的邻接图。3 5 图4 8 依边长递增排序逐一比较并连接各点3 5 图4 9 以聚类层次树来表示聚类结果。3 6 图4 1 0 拓扑约束下连续面状聚类结果3 6 图5 - 1 技术路线图3 7 图5 - 2 系统的功能模块结构图。3 8 图5 - 3 算法界面模块类结构图。3 9 图5 4 聚类算法主界面。3 9 图5 - 5 聚类分析参数设置a 0 图5 - 6 专题地图可视化。4 1 图5 - 7 地图标注可视化。4 1 图5 - 8 空间属性一体化聚类结果图4 3 图5 - 9 原始数据分布图4 4 图5 1 0d e l a u n a y 三角网的创建4 4 图5 - 1 1 考虑约束条件下的d e l a u n a y 网。4 5 图5 1 2 第一层次凝聚式层次聚类结果4 5 图5 1 31 ：1 万居民地分布图4 7 图5 1 4 采用聚类算法对居民地进行某一尺度的综合结果4 8 图5 1 5 不同比例尺下居民地图版的变化4 9 v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得中国农业大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 兹声一 时间：叼 年6 月加日 关于论文使用授权的说明 本人完全了解中国农业大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的 复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。同意中国农业大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 研究生签名：前压钦时间：跏7 年6 月b 日 导师签名： ) 力嘭玺 时间：，) ，、舻 年g 月妒日 1 1 立论依据 第一章引言 随着各种空间技术的应用与发展，空间信息源源不断地产生，从而积累了海量、复杂的空间 数据，这对传统g i s 空间分析功能提出了严峻挑战。然而，目前空间分析模型的开发与应用技术 水平又存在诸多限制，为此，必须发展数据驱动和探索性的新型空间分析方法。空间数据挖掘技 术的产生正符合这种需求。作为空回数据挖掘的一个重要分支空间聚类，是根据某个相似性 准则对空间实体集进行自动分组，达到组内差异最小、组间差异最大的过程。空间聚类分析既 可作为独立的空间数据挖掘工具，又可作为其它方法比如分类方法的预处理，目前已经广泛应用 在地理信息系统、遥感、医学图像处理等领域，具有非常重要的应用价值。 目前在空间聚类分析技术的研究与应用中，存在以下几个重点和难点问题： l 、聚类算法的效率问题。由于空问聚类的研究对象空间数据本身的特性( 高维、多尺度和 海量等) 以及空间对象之间具有复杂的关系( 空间拓扑关系、方位关系和度量关系等) ，因此对 算法的要求很高，既需要算法挖掘出令人满意的结果，还要求算法具有较低的时问和空闻复杂度。 如何在提供满意聚类结果的同时，尽可能的减少算法复杂度，是近年来空间聚类面临的一大难题。 计算成本过高已成为传统的聚类算法最大的瓶颈点之一。导致了形成聚类的过程缺乏效率。一般 以距离为相似性准则的聚类算法从其计算过程中可以发现。虽然绝大部分的对象彼此并不相邻， 但由于无法得知每一对象彼此之间的远近或相邻关系，因此只能以近乎盲目的方式漫无目的地去 计算所有对象之间的距离后，再逐一找出较接近对象形成一个个的聚簇。而这其中又以计算不相 邻对象间的距离浪费最多的时间。为了提高效率，学者们通过改进空间索引、压缩数据库、对数 据库进行采样等各种手段不断改进传统算法和提出新的算法，来保证在得到好的运算结果的同 时尽可能的降低算法的复杂度。 2 ，约束聚类问题。约束聚类问题是指在满足用户某种特定条件下的聚类问题。约束出现将 使得数据成员的分布情况在聚类过程中变得复杂化，在很大程度上影响了聚类的结果。在聚类中 加入用户设定的限制性条件的过程，也可将其看作是是在非监督分类学习中加入了知识，成为半 监督的分类方法。由于约束聚类缩小了解空闾并抓住了应用的语义特征，它通常能够实现更有效 的挖掘。目前大部分的聚类算法都无法处理有关约束的问题，然而，现实世界中所遇到的聚类问 题大都是需要在某些约束下进行的，比如障碍物约束的存在，或者对空问进行区划时必须维护对 象的空间拓扑或相邻关系等，绝对理想的情况是不存在的，因此，约束聚类的研究成为了近年来 聚类算法自g 一大研究热点。 3 、空间与非空间属性一体化聚类问题。在实际应用中，空间聚类分析还存在着两个偏向： 一是从事g i s 理论方法和技术工具研究的工作者大多根据空间对象的地理坐标进行聚类，即只考 虑对象的空间距离关系，而不考虑对象的属性特征的影响( 邸凯昌，2 0 0 1 ，郭仁忠，2 0 0 0 ) i - ，j ； 另一种是从事g i s 应用和地学研究的工作者，则直接套用传统聚类分析方法，根据属性特征集进 行分析，而忽视了对象的空间关系。虽然有些聚类算法考虑了空问对象的两方面的特性( 李新运， 2 0 0 4 ) 【7 j ，但依旧采用的是基于欧式距离的聚类准则，只是将空间数据的坐标点看作非空间的属 性数据，然后对每一维属性数据赋予一定的权重，计算空间对象间的属性聚类。这种方法虽然将 l 中国农业大学硕十学位论文第一章引言 空间数据和属性数据一体化作为聚类的准则，但由于空间数据和属性数据对空间对象的描述特性 不同，所以将其平等的融合在一起很难挖掘出更有效的信息，并且在运算过程中空间数据和属性 数据的权重也很难确定p j 。 4 、聚类的可解释性与可用性问题。传统聚类过程往往是“黑箱”作业，用户不论感兴趣与 否都只能被动地接受聚类结果，而且这些结果往往是抽象的、不易理解的。这种状况正逐渐引起 学者的关注。在非空间数据挖掘领域，近年来在数据挖掘、数据可视化交互探索分析技术与0 l a p ( 在线联机分析) 技术集成研究方面有了初步进展，目前已形成了数据挖掘与知识发现的另一个 新热点可视化数据挖掘( v d m ) 嗍。目前大多数数据挖掘应用中都结合了一些可视化方法， 但这种结合是松散的，主要表现在可视化技术大多仅仅应用于数据挖掘结果的可视化。即将挖掘 后得到的知识以数据分布图、曲线( 面) 三维立方体、散列图、决策树等形式表示出来，但是用 户在其中并未涉及数据挖掘的过程，这样容易对最后结果的可信度产生怀疑。可视化数据挖掘在 此基础上还强调将数据挖掘的过程可视化，用户不荐是仅仅完成数据查询的工作，而是通过交互 手段参与后台数据挖掘算法的更多过程。可视化数据挖掘实现了数据可视化和数据挖掘之问自9 一 种更紧密的结合。可视化空间聚类作为其中一个分支，它的基本思想就是要打破传统空f 田聚类算 法的这种。封闭性”，充分利用各式各样的数据可视化技术，以一种完全开放，互动的方式支持 用户结合自身专业背景参与到空间聚类的全过程中，使聚类与特定的语义解释和应用相联系，最 终达到提高聚类的有效性和可靠性的目标。 本文针对上述四个问题为背景，考虑带约束条件的交互式空间聚类研究问题。将空间聚类与 数据的交互探索、多维表达等可视化技术紧密集成，从而为空间聚类中的可视化提供技术方法。 1 2 空间聚类分析的典型要求 空间聚类分析具备探索性数据分析的内在特质，它逐渐被看作是从空同数据库中发现知识的 一种主要的挖掘方法。然而，空间数据的高度复杂特征本身就使得空间聚类方法的设计、实现与 应用存在诸多难题，数据挖掘概念的提出又为聚类分析带来了大量亟待解决的更高需求。h a n j w 等提出，数据挖掘对聚类的典型要求如下九项： l 、可伸缩性：许多聚类算法在小于2 0 0 个数据对象的小数据集合上工作得很好，但却在大数 据集合样本上进行聚类可能会导致结果的偏差，所以需要具有高度可伸缩性的聚类算法 2 、处理不同类型属性的能力：许多算法被设计用来聚类数值类型的数据。但是应用可能要 求聚类其他类型的数据，如二元类型，分类、标称类型，序数型数据，或者这些数据类型的混合。 3 、发现任意形状的聚类：许多聚类算法基于欧几里德距离或者曼哈坦距离度量来决定聚类。 基于这样的聚类度量的算法趋向于发现具有相近尺度和密度的球状簇，但是一个簇可能是任意形 状的，提出能发现任意形状簇的算法是很重要的。 4 、用于决定输入参数的领域知识最小化：许多聚类算法要求用户输入一定的参数( 如类别 个数) ，其结果往往对输入参数十分敏感。实际上，参数确定往往很难。要求用户输入参数不仅 加重了用户的负担，也使得聚类的质量难以控制。 5 、处理噪声的能力：现实世界中的数据库大都包含了孤立点、空缺、未知数据或存在错误 的数据，聚类算法应该对此类数据不敏感，即对于噪声的稳健性。 2 中国农业大学硕十学位论文第一章引言 ! i ， 6 、对于输入记录的顺序不敏感：一些聚类算法对于输入数据的顺序是敏感的，例如，同一 个数据集合，当以不同的顺序提交给同一算法时却可能产生不同的聚类结果，这显然是不合理的。 7 、能够处理高维数据：许多聚类算法在处理低维数据时效果较好，一旦面临高维数据在算 法的效果与效率上就大打折扣。所以高维空间中进行聚类分析具有很大挑战性。 8 、基于约束的聚类：即发现满足用户定义限制的簇，由于其抓住了应用的语义特征。通常 能够导致更有效的挖掘。要找到既满足特定的约束，又具有良好聚类特性的数据分组是一项具有 挑战性的任务。 9 、可解释性和可用性：用户希望聚类结果是可解释、可理解和可用的。也就是说，聚类要 和特定的语义解释和应用相联系。应用目标如何影响聚类方法的选择也是一个重要的研究课题。 针对以上数据挖掘对聚类分析提出的新要求，目前大部分的聚类算法只能满足其中的一种或 几种要求。对空间聚类而言，由于空间数据往往有数据量庞大、维度高、结构复杂等特点，第1 、 2 、3 、4 、5 、8 、9 点以及可视化需求对于空间聚类方法的设计显得更加迫切。在当前技术条件 下，设计出满足上述所有要求的聚类方法是不太现实的，大多数空间聚类方法都只能选择其中部 分要求作为突破口，本文提出的交互式约束空间聚类的算法将基于约束的聚类、聚类的可解释性 与可用性和聚类的可视化需求作为突破口 1 3 本文的主要工作 1 3 1 带约束条件的空间聚类算法 传统的空间聚类算法，都是根据空间样本点的绝对位置来计算距离，没有考虑到样本点之间 的空间关系，将d e l a u n a y - 一角网思想引入到聚类算法中，实际上是利用d e l a u n a y - - 角阿生成的空 间样本点拓扑关系来表达样本点之间的邻近关系。这样，在计算两两对象之间距离的时候就可以 只计算相邻对象的距离，而不再盲目的计算所有空间对象之间的距离，极大的减少了运算次数， 而且在聚类结果中，能够更加合理的解释空间聚类在空间位置上的空间依赖关系，这可看成空间 相邻关系约束下的聚类。 针对离散的面状数据可以通过一定的模型进行转换，比如取面的中心或者重心来代替面状数 据进行处理，而对于本身就带有空间拓扑关系的连续面状数据来说，并不需要构建d e l a u n a y - - - 角 网来维护这种邻接的空问关系，可以直接利用其空间拓扑邻接关系的邻接图来构建最小生成树， 然后再根据空间对象间的属性差异来进行聚类。 二维地理空间中存在许多不同的实体，其中一些实体通过其所占据的空间位置而影响着周边 空间对象的分布形态和对象间的距离，当从这种影响的角度来考察一个地物时，我们称其为空间 障碍“，考虑如何将空间相邻关系和空间障碍作为约束条件进行聚类是本文的一个研究内容。 1 3 2 基于引力模型的空间与非空间属性的一体化聚类算法 在实际应用当中，空间对象之间往往存在着相互作用。本文尝试将引力模型集成到聚类算法 当中，提出一种综合考虑空间与非空间属性一体化的聚类算法。在建立d e l a u n a y 三角阿或者邻接 图来维护空间对象的相邻关系后，计算表达属性特征显著程度的一个综合指标，本文称之为属性 特征值。然后可以从任何一个空间对象( 记为当前对象) 出发，查找与之相邻的对象中对当前对 3 中国农业大学硕十学位论文第一章引言 象产生最大吸引作用的对象( 记作目标对象) ，再比较两者的属性特征值，如果当前对象特征值 大，不做归类处理，如果目标对象的特征值大，将当前对象归类到目标对象当中。 在引力模型中，i ，j 两对象的空间相互作用引力模型公式为： f 。i ：七竺：；拿上 ( 1 1 ) 。 d i 其中磊为i ，j 两对象的相互作用力，m i 、n j 分别用两对象的属性特征值来表示，d i 为i 、j 两对象的距离，k ，a ，b 为系数。 由公式所知，将空间距离和属性特征集成到一个引力模型中。由于该模型在空间对象相互作 用中比较普遍，比如在城市的相互作用研究。由于该模型能够抓住实际应用聚类对象的相互作用 关系，所以本文将该模型引入到聚类算法，来挖掘更丰富的聚类结果。 1 3 3 可视化交互技术在空间聚类中的应用 参考可视化数据挖掘三方面任务，本文将可视化交互技术应用至空间聚类当中，主要从以下 三个内容来研究： 1 、对原始空间数据的可视化 针对空间特征的可视化，将以地图的形式显示，然后可以添加相应的背景图层。用户可以直 观地观察空间实体所处的空间位置。对于其属性特征的可视化，可以运用当前流行的有关数据可 视化的新方法，比如采用基于几何可视化技术中的平行坐标法等方法进行显示，可以协助用户理 解属性的特征，包括变量，分布，数量等等，同时能够实现图形一属性、属性一图形之间的双向联 动。研究的难点在于如何将其空间特征和属性特征进行一体化显示。 2 、对聚类过程以及中间结果的可视化 聚类过程的可视化要求能够动态演示的聚类过程，如d e l a u n a y _ 三角网或最小生成树的生成过 程的可视化，显示聚类过程中产生的一些中间结果，提供用户根据中闻结果值以及结合自身的专 业背景适时地调整算法的某些参数，有了人机交互的过程，可以引导聚类满足用户的专业需要， 有助于对聚类所形成结果的理解，得出用户满意的结果。 3 、对聚类最终结果的可视化 最普遍的是对每个类进行类别标记，并且可以使用不同的颜色或者符号来直观的表达不同的 类别，通过图表的可视化手段表达不同类别的属性趋势，有助于用户对于聚类结果的理解。也可 以根据层次聚类的步骤生成一个层级聚类树。 1 4 论文的组织与安排 在分析研究国内外空间聚类研究进展的基础上，融合相关的聚类思想和方法，本文提出了一 种有效的空间数据与属性数据一体化的聚类算法，并考虑相邻关系和空间障碍物作为约束条件对 聚类的影响，最后结合实例验证了算法的有效性。本论文分别从基础理论、核心理论与关键技术、 应用实例三个层面进行研究 论文共分为六章，各章节的安排如下( 论文的组织与章节安排如图1 1 所示) ： 4 中国农业大学硕十学位论文 第一章引言 第一章： 引言介绍了本论文的立论依据，分析了总结当前空间聚类的存在的几个重点与难 点问题，介绍数据挖掘对空间聚类提出的新要求，归纳了本人在论文中所做的主要工作以及全文 组织安捧。 第二章：介绍了带约束条件的聚类算法理论基础，包括约束空间聚类研究，可视化交互技 术在空间聚类的应用，尺度空间理论和空间的相互作用模型。 第三章：详细讨论本论文提出的基于约束i ) c l a u n a y - - 角网实现相邻关系约束和障碍物约束下 聚类的方法。并对算法进行了分析。 第四章：介绍在拓扑约束下的连续面状数据聚类的研究，在空间拓扑关系的基础上构建最 小生成树。并详细讨论本论文提出的基于邻接图的聚类算法。 第五章：开发空间聚类原型系统，并结合聚类算法在中国城市群划分和居民地综合过程重 点的应用实例进行验证。 第六章：对带约束条件的交互式空间聚类研究成果进行总结与讨论，并提出下一步研究重 点 1 第一章引言 1 1 立论依据 1 2 聚类的典型要求 1 3 本文主要工作 1 4 章节组织与安排 一之岁 i 第二章相关理论研究及进展 1 1 带约束条件的空间聚类研究 1 2 空间聚类与可视化交互技术 1 3 尺度空间理论和空间相互作用模型 田i - i 论文组织与章节安排 5 护 量一- 核心理论 与 关键技术 l 弋、7 应用实例 l 弋、夕 结论 中国农业大学硕士学位论文 第二章相关研究理论及进展 第二章相关研究理论及进展 2 1 带约束的空间聚类研究 现实世界中的应用往往可能需要在各种约束下对目标分布情况进行聚类，因此研究约束条件 下的聚类对聚类技术的应用有着特殊的意义，并且近年来成为聚类研究的一大热点。下面将举例 作说明。 例l ：某公司计划在某一地区建设4 个客户服务中心，由于用户总是根据“就近”原贝来选择 服务中心，为了更好的服务客户，公司希望将服务中心设在客户集中的中心。这是一个典型的可 以通过聚类解决的问题，通常可选取聚类中心作为服务中心的最佳位置。如果不考虑河流、桥梁、 山坡的影响，直接用欧几里德距离来衡量会得到一些不合理的聚类结果。如图2 1 所示，这显 然不是我们所需要的结果。因为c 1 类被河流分割，位于河流南侧的用户必须绕很远的路才能到达 河流北侧的客服中心，对于这些用户，他们宁可去c 2 、c 3 或c a 的客服中心。而且c a 的中心位于 山坡上也不合理。所以这类问题聚类，必须考虑河流、山坡等实体障碍物的影响。在实际生活中， a t m 机、邮局、医院、学校等公共设施选址的问题“”，大多可以用空间聚类来解决，为了真实反 映现实世界的空问关系，在聚类时需要考虑实体障碍物的存在。 ( a ) 客户和障碍物的位置( b ) 不考虑障碍物的聚类结果 图2 1 客户服务中心选址问题示意图 例2 ：在城市群埘分应用当中，要求每一个城市群必须是相邻的，即不能被其他城市群分隔 开张峰对此做了一定的工作，其聚类结果如图2 2 所示”1 ： 图2 - 2 空阃属性体化聚类结果图 6 中圉农业大学硕十学位论文第二章相关研究理论及进展 但从上图的聚类结果可以看出，虽然能够得出京津塘、长三角，珠三角等城市群，但是由于 他所采用的算法受d c l a u n a y 的影响较大( 如将乌鲁木齐归至4 哈尔滨) ，这和实际的城市群划分需 求有些出入，可见该算法还存在着一定的缺陷。在实际应用中，比如区域划分此类的问题都涉及 到空间相邻关系约束的限制。 例1 所面对的约束是实体障碍物对空间目标的分布造成的影响，而例2 所面对的约束则是由于 类别内对象受到某种特定条件( 如空间相邻关系的) 限制。类似于上面的这两个实例中所碰至口的 问题是我们在现实世界中很常见的问题。通过上面的实例我们可以看出，约束条件下的空间聚类 问题在现实世界中有着相当普遍的应用，约束的出现，将在很大程度上影响聚类的结果以及算法 的复杂性。只有考虑到约束条件，空间聚类技术才更加符合客观世界的要求，其结果才具有实际 价值。 2 1 1 约束聚类定义 通常我们研究的聚类分析都假定是个自动的、算法计算的过程，基于对一组聚类对象的相似 性或距离函数的估计，而很少有用户的指导或交互。然而，甩户通常对应用需求有清楚的认识， 并且也很愿意利用这些认识来g i 导聚类过程并影响聚类结果。因此，在许多应用中，在聚类过程 中考虑用户的偏好和约束是令人期望的。这种信息的例子包括期望的聚簇数日、聚簇的最大或最 小规模、不同对象或者维的权重，以及对聚类结果的其他期望特征 约束聚类是指在聚类中加入用户设定的限制性条件的过程。也可将其看作是是在非监督分类 学习中加入了知识，成为半监督的分类方法由于约束聚类缩小了解空间并抓住了应用的语义特 征，它通常能够实现更有效的挖掘“1 。 由于约束条件与聚类实现过程的多样性，给出约束聚类自g 一般形式化定义是较为困难的，这 里介绍t u n g 等人从分割聚类角度给出的无约束、约束聚类的定义“”： 无约束聚类阎题 给定一个| l ? 个对象的数据集历一个距离函数够一个正整数七找到一个 聚类，也就是 口的一个分割方式，该方式将口分割成k 个分离的簇( c ，, c l k ) ，条件是目标函数 d i s p = 2 二i d i s p ( c l j ，r e p j ) ( 2 - 1 ) 最小。簇口，的散度d i s p ( c 1 dr e p , ) 衡量了( y ，中每个对象到代表点“研的总体距离，也就是 d 穑p 幻6 删用乙胪c i i 形【p r e p , ) 来定义。代表点的选择标准是使a i 印f 功b 酬达到最 小。 约束聚类问题 其目标函数形式和1 式相同，但加入如下约束条件：每个类别口满足约束c ，甩巩l = c 表示。 t g 等人的形式化定义只适用于分割型的聚类方法。适用于所有聚类方法的形式化定义很难 给出，一般可把d i s p 看作是一种聚类的代价函数，聚类的标准是使代价最小。如密度聚类，可以 把代价函数看作是满足指定密度要求的簇未被提取出的可能性最小。 胁砻恨据约束条件的定义层次和角度分析，将约束聚类分为以下4 类： 聚类对象层次上的约束：如对数据集中参与聚类的对象进行限制；例如，在不动产应用中， 可能只希望对那些简直5 0 0 万元以上的豪华住宅进行空间聚类。这种约束限制了聚类的对象集， 7 中国农业大学硕十学位论文第二章相关研究理论及进展 但它可以通过预处理( 例如s q l 查询进行选择) 可以容易地处理。预处理以后，问题就归结为无 约束的聚类问题。记数据集中有n 个对象i 分别为1 。2 ，n ，用公式表示聚类层次上的约束为： i = c o n d i t i o n对象层次有约束 lf 没有具体限制对象层次无约束 聚类参数约束：用户可能想对每个聚类参数设定一个期望的范围。对于给定的聚类算法，聚 类参数通常是明确的，比如，划分聚类的期望聚类数目，或者基于密度的聚类算法中的半径和点 的最小数目等。尽管这种用户指定的参数可能对聚类的结果产生很大影响，但是它们通常只对算 法本身进行限制。假设聚类的参数为p a r a m 参数需要满足条件为c o n d i t i o n ，可形式化表示： ip a r a mi _ c o n d i t i o n 聚类参数有约束 lp a r a m 没有具体限制聚类参数无约束 ” 障碍约束：如在聚类问题中加入河流、高山、高速路之类的障碍知识。这些障碍物对象及其 影响可以通过重新定义对象间的距离函数来得以实现。 类层次上的约束：主要是对类别的某些特性进行限定：如指定类别形状、包含点数；对于类 似图像分割、空间区划这样的问题，则要求聚类类别必须维护对象的空间拓扑或相邻关系不 我们按t u n g 的分类体系介绍约束聚类的研究进展。由于对象层次与参数约束相对简单且和论 文联系并不密切，这里只介绍障碍约束聚类与类层次上的邻近关系约束聚类的研究工作。 2 1 2 障碍约束聚类 障碍约束聚类，它的一个实例是银行a 1 m 机的选址问题。显然黼最好的选址是保证其服 务区内用户总体上的最短到达距离。现实中由于用户到达路径上往往有一些无法逾越、需要绕道 的障碍，单纯的基于直线距离的聚类算法不能满足要求。 q p 田2 - 3 带障碍物的距离计算 如图2 - 3 所示，假设a b c d 为四个居民地，p q 是一条河流，在这里作为障碍物来看待。假如某个 银行想在这个区域安装两个a t m 啻t 来方便附近居民。从图上明显可以看出，如果不考虑河流障碍 物的存在，和b d 分别为一类，在这两者之间的中心建a t m 就可以满足需求，但是由于有河流p q 作为障碍物的存在，使得之间的距离发生了变化，a 必须通过类似p 点这样的中转后才能到达c ， 我们用d ( 只，p ) 来代表霉，只之间的距离，这样我们可以用以下公式来表示考不考虑障碍物的不同 距离计算方法。 8 中国农业大学硕十学位论文第二章相关研究理论及进展 f丑 ld ( 弓，弓) 2 d ( 弓，上1 ) + 艺d ( l i ，丘“) + d ( 厶，弓) 存在障碍物，厶为第计通达点 j 扣1 ，、 1d ( 霉，弓) = m d ( 层，0 )存在障碍物，e ，p i 不可达，w 为障碍权重 l 。厂二_ 一 。 id ( o ，弓) 2 ( 一，) 2 + o _ 一y p j ) 2 无障碍距离 下面介绍了目前几种主要的能够处理障碍物约束的聚类算法。 c o d - c l a r a n s 是最早提出的基于障碍约束的聚类算法。该算法首先定义了障碍聚类，即两 对象之间在考虑障碍物存在的情况下的最短距离。由于该算法以c ir a n s 算法为基础，而且使用 了障碍距离，因此其不足之处是需要昂贵的预处理操作，算法的可扩展性小，只能针对一些较小 的数据库进行聚类，而且存在受噪声对象影响大、不便处理任意形状的聚类对象等缺陷。 a u t o c l u s t + “将d e l a a y 图引入到聚类算法当中。它是氆a o t o c l u s t “”基础上进行改 进，将障碍物模型化为一系列分割线段，生成约束下的d e l a u n a y 图，再根据a u t o c l u s l 核心算 法进行处理，得到最终的聚类结果。因此，算法继承了a u t o c l u s t 算法的特点，即对数据点采 取t d e l a u n a y 结构，聚类结果比较好。 d b _ c l u o c “”是一种基于密度的障碍约束下的聚类算法。该算法在d b s c a n 算法基础上， 考虑了障碍物存在的聚类情况。它将障碍物模型化为一组多边形，并通过这些多边形将数据空阃 进行划分，引入可视性和可视空间的概念。 d b r s + “”也是一种基于密度的障碍约束下的聚类算法。该算法以d b r s “”算法为基础，首先 提出了一个最小边界区域的概念，将障碍物的影响划入到最小边界区域，讨论这个区域中各点受 到障碍物的影响，聚类时采用d b r s 核心算法，因此。算法对障碍物的处理极为细致，可以处理 多种障碍，如连接型障碍约束等等，算法采用d b r s 算法为理论基础，在针对大型数据库效果较 好，但算法受到参数选取的影响，聚类结果往往对参数很敏感，而且参数选取需要一定的经验性。 另外算法需要首先对障碍物进行分类以及图形化处理，因此，预处理运算量大。 2 1 3 空间邻近约束聚类 空间聚类可以看作是在聚类中考虑空间结构特征的约束聚类，而空间结构特征的表达方式是 多样的，其中空回邻近关系是最常用的方式。传统空间数据聚类多针对其非空间属性进行，一般 未能考虑对象间的空间关系，因此不能称之为空间聚类。一种补偿性的解决方法是在聚类之后， 根据其邻居的非空间属性，进行类别的重分配“2 “。加入邻近信息的更直接的聚类方法有两种： 0 在差异性函数中加入对象间的空间距离成分；o 利用邻接矩阵与邻接图。前种方法将对象间的 差异性描述为属性上的距离测度+ 空间距离测度之和，对差异性的贡献率用各自权重调整4 “。 如果空间距离权重调整得足够大，则结果簇将在空闻上呈现邻近分布特点。显然，这类方法的最 大不足之处是难以客观地确定权重。第二种方法则利用邻接矩阵和邻接图进行聚类。 针对不同的数据类型，邻近关系( 邻居) 的定义标准与难度各不相同。对于多边形数据，通 常把和考察对象有公共边的多边形定义为它的邻居；对于图像数据，一般把某像元的4 邻域或8 邻 域像元( 或更高阶像元) 定义为其邻近像元。考虑多边形邻近约束的聚类，称为分区。 9 中国农业大学硕十学位论文第二章相关研究理论及进展 对于不占据空间范围且分布不规则的数据类型，如离散点数据，邻居的定义则较为复杂，方 法也多种多样。将点的邻居n ( i ) 定义为n ( i 户u l d i j 、产品销售m ) 联系量：d i i 表示i 、j 之间的几何距离；k 为系数，如i 地输送资源至j 地，那么j 地得到