（计算机应用技术专业论文）空间对象和移动对象聚类算法研究.pdf

n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n da s t r o n a u t i c s 砀eg r a d u a t es c h o o l c o l l e g eo fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y i l ll li ii ii ll iii ii ii ii y 18 2 5 9 4 0 r e s e a r c ho n c l u s t e r i n ga l g o r i t h m so fs p a t i a l o b j e c t sa n d m o v i n g0 b j e c t s a t h e s i si n c o m p u t e rs c i e n c ea n dt e c h n o l o g y b y z h a n g y u a d v i s e d b y p r o f e s s o rp id e c h a n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g d e c e m b e r , 2 0 0 9 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标 明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许 论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：继玉 日 期：丝；主。2 2 南京航空航天大学硕十学位论文 摘要 聚类分析作为数据挖掘的一个重要研究分支，根据在数据中发现的描述对象及其关系的信 息，依据各簇内对象相似性最大化和各簇间对象相似性最小化的基本聚类分析原则，将对象划 分为紧密且独立的簇集。目前，由于各应用数据库中的数据越来越大，聚类分析已广泛应用于 各种研究领域，成为数据挖掘领域中一个非常活跃的研究课题。随着数据收集技术、计算机网 络和数据库技术的飞速发展，各种复杂类型的数据有了爆炸性的增长，因此迫切需要对复杂数 据类型探索新的数据挖掘技术。本文对空间非移动对象聚类和移动对象轨道聚类这两个问题进 行研究，从改善空间非移动对象聚类效果、移动对象聚类效果、提高算法时间复杂度和减少输 入参数敏感性等角度对其中急需解决的问题进行了研究，主要工作如下： ( 1 ) 根据空间对象的邻域、反邻域和局部密度构造了基于邻域的局部异常因子，提出了一 种基于微簇的对称邻域聚类算法b m s n c 。b m s n c 首先运用经典的聚类算法将原数据集进行聚 类产生一定量的微簇，然后将每一个微簇的中心代表这整个微簇，通过对称邻域聚类算法在进 一步进行聚类。该算法能有效快速的对大数据集进行聚类分析，并且解决了不能从大的、稀疏 的聚类中识别出小的、稠密的邻近聚类这一缺陷，这就使得聚类结果的准确度大大提高。在真 实和合成数据集上的实验结果表明，b m s n c 是可行、有效的。 ( 2 ) k 近邻算法的结果依赖于距离度量的选取，这种距离通常涉及所有的特征，在距离公式 中引入一些特征权参数后，其聚类结果将依赖于这些权值，从而可以通过调整这些权值来优化 聚类结果。本文根据一种学习权值算法以改进聚类准确率提出了基于加权邻域聚类算法b w n c 。 b w n c 就是为每一个属性加一个特征权参数，让不同的属性在聚类中起不同的作用。从数学意 义上讲，这种权值学习相当于欧氏空间中对一组点进行线性变换。不仅对每个属性学习权值， 而且可以对每一个测试样本点的近邻基于它们到测试点的距离进行加权，通过实验表明该算法 能很大程度上使得聚类结果更加准确、有意义。 ( 3 ) 在已有的轨道聚类算法t r a c l u s 基础上，提出了一种基于对称邻域的轨道聚类改进 算法b s n t c 。b s n t c 解决了t r a c l u s 由于使用两个全局参数e p s 和m i n l n s ，存在不能从大 的、稀疏的轨道聚类中识别出小的、稠密的邻近轨道聚类这一缺陷，同时b s n t c 只需要输入 一个参数k ，减少了算法对输入参数敏感性问题。通过一系列的实验结果表明，b s n t c 在保持 t r a c l u s 时间效率的同时改善了轨道聚类效果。 关键词：数据挖掘，聚类，空间对象，移动对象，轨道，对称邻域 空间对象和移动对象聚类算法研究 a b s t r a c t c l u s t e r i n ga n a l y s i si so n eo ft h em o s ti m p o r t a n tr e s e a r c hf i e l d si nd a t am i n i n g ，a c c o r d i n gt o d i s c o v e r i n gd e s c r i p t i v eo b j e c t sa n d r e l a t i o n a li n f o r m a t i o ni nd a t a b a s e ，t h eg o a lo fa c l u s t e r i n ga n a l y s i s i st op a r t i t i o nt h eo b j e c t so fad a t a b a s ei n t oas e to fc l o s ea n di n d e p e n d e n tc l u s t e r sa c c o r d i n gt ot h e c r i t e r i o nw h i c hi st om a x i m i z et h es i m i l a r i t yb e t w e e nt h eo b j e c t so fe a c hc l u s t e ra n dt om i n i m i z et h e s i m i l a r i t yb e t w e e nt h eo b j e c to fc l u s t e r s n o w a d a y s ，d u et ot h ed a t a i nt h ea p p l i c a t i o nd a t a b a s e g r o w i n g ，c l u s t e r i n ga n a l y s i sh a v eb e e nw i d e l ya p p l i e di nv a r i o u so f r e s e a r c hf i e l d sa n dh a v eb e c o m ea v e r ya v t i v er e s e a r c ht o p i ci nt h ef i e l do fd a t am i n i n g w i t ht h ef a s td e v e l o p m e n to fd a t ac o l l e c t i n g t e c h n o l o g y , c o m p u t e rn e t w o r ka n dd a t a b a s et e c h n o l o g y , d a t ao fc o m p l e xd a t at y p e si n c r e a s e d d r a m a t i c a l l y , s oe x p l o r en o v e ld a t am i n i n gt e c h n o l o g i e sa r en e e d e du r g e n t l yt ob ea p p l i e dt oc o m p l e x d a t at y p e s t h i sp a p e rf o c u so nt h et w op r o b l e m sr e s e a r c ho fc l u s t e r i n go fs p a t i a lo b j e c t sa n d t r a j e c t o r yc l u s t e r i n go fm o v i n go b j e c t s f o r mi m p r o v i n gs p a t i a lo b j e c t sc l u s t e r i n gr e s u l t ，m o v i n g o b j e c t sc l u s t e r i n gr e s u l t ，i m p r o v i n gc l u s t e r i n ge f f i c i e n c y , a n da l l e v i a t i n gi n p u tp a r a m e t e r ss e n s i t i v i t y t h em a i nw o r ka r es u m m a r i z e da sf o l l o w s ： f i r s t l y , a c c o r d i n gt on e i g h b o r h o o d , r e v e r s en e i g h b o r h o o da n dl o c a ld e n s i t yo fs p a t i a lw h i c h c o n s t r u c tn e i g h b o r h o o d - b a s e dl o c a ld e n s i t y , a r e r w a r d s ，an o v e lc l u s t e r i n ga l g o r i t h mb a s e do n s y m m e t r i cn e i g h b o r h o o do fm i c r o - c l u s t e r sn a m e db m s n ci sp r o p o s e d b m s n cu s e s c l a s s i c a l c l u s t e r i n ga l g o r i t h mt oc l u s t e ro r i g i n a ld a t as e t st op r o d u c em i c r o - c l u s t e r s ，t h e nt h ec e n t e ro fe a c h m i c r o - c l u s t e rr e p r e s e n tt h em i c r o - c l u s t e r , b ys y m m e t r i cn e i g h b o r h o o dm e t h o dt oc l u s t e rt h e m i c r o - c l u s t e r s t h ea l g o r i t h mc a ne f f e c t i v ea n df a s tc l u s t e r i n ga n a l y s i sf o rl a r g ed a t as e t s ，a tt h es a m e t i m e ，i tc a nm a k eu pt h es h o r t c o m i n gt h a tc l a s s i c a lc l u s t e rc a l ln o td i s t i n g u i s hs m a l l ，d e n s e ，a n d a d j a c e n tc l u s t e r s f o r ml a r g ea n ds p a r s ec l u s t e r s ，w h i c hm a k e st h ea c c u r a c yo fc l u s t e r i n gr e s u l t i m p r o v e dg r e a t l y e x p e r i m e n t a lr e s u l t so nr e a la n ds y n t h e t i cd a t as e t sd e m o n s t r a t et h a tb m s n c i s f e a s i b l ea n de f f e c t i v e s e n c o n d l y , t h er e s u l to fk - n e a r e s tn e i g h b o rc l u s t e r i n ga l g o r i t h md e p e n d so nt h es e l e c t i o no f d i s t a n c em e t i r c s t h ee u c l i d e a nd i s t a n c ew h i c hu s u a l l yr e l a t e st oa l la t t r i b u t e s w h e nf e a t u r ew e i g h t p a r a m e t e r sa r ei n t o r d u c e dt ot h ed i s t a n c ef o r m u l a ，t h er e s u l to fc l u s t e r i n gw i l ld e p e n do nt h ew e i g h t v a l u e sa n da c c o r d i n g l yc a nt oi m p r o v e db ya d j u s t i n gw e i g h tv a l u e s ac l u s t e r i n ga l g o r i t h mb a s e do n w e i g h tn e i g h b o r h o o dn a m e db w n c i sp r o p o s e da c c o r d i n gt ol e a r n i n gf e a t u r ew e i g h t st oi m p r o v et h e a c c u r a c yo fc l u s t e r i n g b w n ca d daf e a t u r ep a r a m e t e rf o re a c ha t t r i b u t e ，s od i f f e r e n ta t t r i b u t ec a n p l a yad i f f e r e n tr o l ei nt h ec l u s t e r i n g m a t h e m a t i c a l l yi tc o r r e s p o n d st oal i n e a rt r a n s f o r m a t i o nf o ra i i 南京航卒航天大学硕士学位论文 s e to fp o i n t si nt h ee u c l i d e a ns p a c e i tn o to n l yl e a r n e df e a t u r ew e i g h t sf o re a c hf e a t u r e ，b u ta l s o w e i g h t e dt h ec o n t r i b u t i o no f e a c ho ft h ekn e i g h b o r sa c c o r d i n gt ot h e i rd i s t a n c et ot h et e s t i n gs a m p l e s ， t h a ti s ，g i v eg r e a t e rw e i g h t st o c l o s e rn e i g h b o r s s oi tc a r ll i l a k et h ec l u s t e r i n gr e s u l t sa r em o r e a c c u r a t ea n dm e a n i n g f i f lt ot h el a r g ee x t e n tt h r o u g ht h et e s to f e x p e r i m e n t t h i r d l y , at r a j e c t o r yc l u s t e r i n ga l g o r i t h mb a s e do ns y m m e t r i cn e i g h b o r h o o dn a m e db s n t ci s p r o p o s e db a s e do nt h ee x i s t i n gt r a j e c t o r yc l u s t e r i n ga l g o r i t h mt r a c l u s b s n t cm a k e su pt h e s h o r t c o m ew h i c ht r a c l u sc a nn o td i s t i n g u i s hs m a l l ，d e n s e ，a n da d j a c e n tt r a j e c t o r yc l u s t e r sf r o m l a r g ea n ds p a r s et r a j e c t o r yc l u s t e r sd u et ou s i n gt w og l o b a lp a r a m e t e r se p sa n dm i n l n s a tt h es a m e t i m e ，b s n t cu s eap a r a m t e r 七w h i c hc a na l l e v i a t ei n p u tp a r a m e t e rs e n s i t i v i t y as e r i e so f e x p e r i m e n t a lr e s u l t ss h o wt h a tt h eb s n t ci m p r o v e st h et r a j e c t o r yc l u s t e r i n gr e s u l to ft r a c l u s w h i l ek e e p st h ee f f i c i e n c y k e y w o r d s ：d a t am i n i n g , c l u s t e r i n g , s p a t i a lo b j e c t , m o v i n g o b j e c t ，t r a j e c t o r y , s y m m e t r i c n e i g h b o r h o o d m 空间对象和移动对象聚类算法研究 i v u 南京航空航天大学硕士学位论文 目录 第一章鲤 论。1 1 1 数据挖掘概述l 1 1 i 产生和发展。l 1 1 2 研究目的和意义2 1 1 3 国内外研究状况4 1 2 选题依据5 1 3 本文的主要内容和组织结构7 第二章聚类分析9 2 1 聚类分析9 2 1 i 聚类分析的定义9 2 1 2 聚类分析的基本要求1 0 2 1 3 主要聚类方法综述：l o 2 2 空间对象聚类分析1 3 2 2 1 空间索引l3 2 2 1 1r - t r e e 空间索引以及改进1 4 2 2 1 2 代价模型1 6 2 2 2k 最近邻聚类算法17 2 2 3 聚类结果的评估标准1 8 2 3 移动对象聚类分析1 9 2 3 1 代表性聚类算法1 9 2 3 2 聚类结果的评估标准2 2 2 4 本章小结2 2 第三章空间对象聚类分析2 3 3 1 对称邻域的相关概念2 3 3 1 1k - 近邻相关概念2 3 3 1 2 对称邻域引入及其概念2 4 3 2 基于微簇的对称邻域聚类算法b m s n c 2 6 3 2 1 微簇的概念2 6 3 2 2b m s n c 算法。2 7 3 2 2 1 基本思想2 7 3 2 ：2 2 算法描述2 8 3 2 3 实验与性能分析3 0 3 2 3 1 实验结果及说明。3 0 3 2 3 2 时间效率评价3 2 3 3 加权邻域聚类算法b w n c 3 3 3 1 3 1 问题的提出3 3 v 空间对象和移动对象聚类算法研究 3 4 第四章 4 1 4 2 4 3 第五章 3 3 2 特征权值的学习3 3 3 3 3 实验及分析3 5 3 3 4 时间效率评价3 7 本章小结3 7 移动对象聚类分析3 9 轨道聚类简述3 9 4 1 1 轨道聚类相关概念3 9 4 1 1 1 轨道相关概念3 9 4 1 1 2 线段之间距离度量公式4 0 4 1 2 轨道聚类框架4 1 4 1 2 1 轨道划分算法4 1 4 1 2 2 生成代表轨道4 3 基于对称邻域的轨道聚类算法b s n t c 4 4 4 2 1 相关概念4 4 4 2 2 基于对称邻域轨道聚类算法4 4 4 2 2 1 基本思想- 4 4 4 2 2 2 算法描述4 5 4 2 3 实验数据分析和评价4 7 4 2 3 1 实验数据。4 7 4 2 3 2 线段聚类结果分析4 7 本章小结5 0 结束语5 1 5 1 本文的总结5 1 5 2 未来研究方向5 2 参考文献 致谢 在学期间的研究成果及发表的学术论文 v i 6 0 南京航空航天大学硕士学位论文 图表清单 图1 1 论文框架。7 图2 1r - t r e e 15 图2 2 相似轨迹段2 0 图3 1k - 最近邻算法错误的离群点判断实例2 5 图3 2 对称邻域聚类算法离群点判断实例。2 5 图3 3b m s n c 算法框架：2 7 图3 4k - m e a n s 算法和b m s n c 算法对i r i s 数据集进行的聚类结果比较3 1 图3 5k - m e a n s 算法和b m s n c 算法对合成数据集进行的聚类结果比较3 2 图3 6 两种不同权值比较3 6 图4 1 线段之间的距离函数4 0 图4 2 轨道聚类框架4 1 图4 3 轨道划分实例4 2 图4 4 代表轨道的生成4 3 图4 5 坐标转换4 3 图4 6t r c l u s 和b s n t c 在e l k 9 3 上轨道聚类结果对比4 8 图4 7t r c l u s 和b s n t c 在d e e r 9 5 上轨道聚类结果对比。4 9 图4 81 r c l u s 和b s n t c 在交通网上轨道聚类结果对比5 0 表3 1k - m e a n s 算法和b m s n c 算法的聚类结果比较3 1 表3 2 学习特征权值前后聚类性能比较3 7 v 空间对象和移动对象聚类算法研究 d m k d d a c m s d m k d m o d g i s s t s 删c e m c b m b r m d l v l 注释表 d a t am i n i n g k n o w l e d g ed i s c o v e r yi nd a t a b a s e a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y s p a t i a ld a t am i n i n g k n o w l e d g ed i s c o v e r y m o v i n go b j e c t sd a t a b a s e s g e o g r a p h i ci n f o r m a t i o ns y s t e m s p a t i o - t e m p o r a ls p a c e m o v i n gm i c r oc l u s t e r e x p e c t a t i o nm a x i m i z a t i o n c l u s t e rb l o c k m i n i m u mb o u n d i n gr e c t a n g l e m i n i m u md e s c r i p t i o nl e n g t h 数据挖掘 数据库中知识发现 美国计算机学会 空间数据挖掘 知识发现 移动对象数据库 地理信息系统 时空空间 移动微聚类 最大期望 聚类块 最小边界矩形 最小描述长度 南京航空航天大学硕士学位论文 第一章绪论 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们能够非常方便地获取 和存储大量的数据。面对大规模的海量数据，传统的数据分析工具只能进行表层的处理，而无 法获得数据之间的内在关系和隐含的信息，从而陷入了“数据丰富，知识贫乏”的困境。为了 摆脱这种困境，人们迫切需要一种能够智能地、自动地把数据转换成有用信息，这种对强有力 数据分析工具的迫切需求使得数据挖掘( d a t am i n i n g ，d m ) 技术应运而生。 近几年，空间对象数据分析【1 2 】和移动对象数据分析【3 叼在学术研究和实际应用方面都已成 为研究热点话题。通过数据挖掘技术对空间对象和移动对象数据进行分析，获取的信息或知识 可以广泛应用国防军事、国家安全、交通管理、位置服务、移动计算和欺诈检测等领域，引起 了信息产业界和整个社会的极大关注，成为2 l 世纪经济竞争实力和综合国力的重要组成部分。 1 1 数据挖掘概述 当数据积累到一定数量时，某些潜在联系、分类、推导结果和待发现价值隐藏在其中，可 以使用数据发掘工具帮助发现这些有价值的数据。数据挖掘就是从海量数据中，提取隐含在其 中的、人们事先不知道的但又可能有用的信息和知识的过程。通过数据挖掘能找出数据库中隐 藏的信息，实现用模型来拟合数据、探索型数据分析、数据驱动型的发现和演绎型学习等功能。 数据挖掘是机器学习、数据库技术、人工智能、统计学、模式识别、神经网络、信息检索以及 可视化计算等多学科交叉发展而产生的新兴学科【5 l ，正在各行各业中以信息分析为基础的决策 支持系统活动中扮演着越来越重要的角色。 1 1 1 产生和发展 2 1 世纪以来，人类已步入以知识经济为主要标志的知识经济时代。在知识经济社会中，以 数据为表征的各种信息作为知识的载体飞速膨胀，并随着互联网的迅速发展和普及，产生了“数 据爆炸一，这就迫切需要有一种技术能够将这些数据转换成有用的信息和知识。在1 9 8 9 年8 月 于美国底特律市召开的第一届国际联合人工智能学术会议( u i ：a i ) 上，数据库、人工智能、数理 统计和可视化等技术的学者们首次提出了从数据库中知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) 标志着数据挖掘技术的诞生。许多人把数据挖掘视为数据库中知识发现的同义 词，而另一些人只是把数据挖掘视为数据库中知识发现过程的一个步骤。1 9 9 5 年，在美国计算 机年会( a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y , a c m ) 上，提出了数据挖掘的概念，即从大量的原 始数据中发现隐含的、未知的、具有潜在使用价值的知识过程。 空间对象和移动对象聚类算法研究 数据挖掘涉及到诸如机器学习、模式识别、统计学、数据库、人工智能、数学和可视化技 术等众多学科，是一个多学科相互交叉融合所形成的一个具有广泛应用前景的研究领域。九十 年代数据挖掘成为数据库届的热门话题。1 9 9 1 、1 9 9 3 和1 9 9 4 年又接着继续举行数据挖掘专题 讨论会。随着参加会议人数的增多，从1 9 9 5 年开始，每年都要举办一次有关数据挖掘技术的国 际会议。另外从1 9 9 7 年开始，数据挖掘也拥有了自己的杂志 k n o w l e d g ed i s c o v e r ya n dd a t a m i n i n g ) ) 。a c m 也成立了s i g k d d 专业组。数据挖掘虽然只有几年的历史，然而由于其极大的 潜在使用价值，使得数据挖掘技术已经深入到许多领域，并已经开发出了许多成功的产品，得 到了业界的广泛关注。较有代表性的数据挖掘工具主要有：美国k a n s a s 大学开发的l e r s 系统； 美国s p s s 公司著名的数据挖掘工具箱c l e m e n t i n e ；= l j l 拿大s n n o nf r a s e r 大学的d b m i n e r ：m m 公司的q u e s t 系统；s a s 公司的s a se m ( e n t e r p r i s em i n e r ) 系统等。 1 1 2 研究目的和意义 数据挖掘是近几年随着数据库和人工智能发展起来的一门新兴技术，它从大量原始数据中 发掘出隐含的、有用的信息和知识，帮助决策者寻找数据间潜在的关联，发现被忽略的因素。 数据挖掘因其巨大的商业前景，现已成为国际上数据库和信息决策领域最前沿的研究方向之一， 并引起了学术界和工业界的广泛关注。目前，数据挖掘技术已经在商务管理、生产控制、电子 商务、市场分析和科学探索等众多领域得到了广泛的应用。 面对海量数据，首要的任务就是对其进行归类，聚类分析就是对原始数据进行合理归类的 一种方法。所谓聚类，就是将一群物理的或抽象的对象，根据它们之间的相似程度分为若干组， 并使得同一个组内的数据对象具有较高的相似度，而不同组中的数据对象则是不相似的。聚类 是人类一项最基本的认识活动，通过适当聚类，事物才便于研究，事物的内部规律才可能为人 类所掌握。聚类是一种重要的数据分析技术，通过搜索并识别一个有限的种类集合，对数据进 行深入描述。通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及 数据属性之间有趣的相互关系。聚类分析的应用十分广泛，在商务中，聚类分析能够帮助市场 分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群特征；在生 物学中，聚类分析能用于推导植物和动物的分类，对基因进行分析，获得对种群中固有结构的 认识；另外，聚类分析还能通过对w e b 文档进行分类来获取信息。 作为一个数据挖掘的重要功能，聚类分析能作为一个独立的工具来获得数据的分布情况， 观察每个类的特点，集中对特定的某些类做进一步的分析。此外，聚类分析也可以作为其他算 法的预处理步骤。因此，聚类分析已经成为数据挖掘领域中一个非常活跃的研究课题。 由于空间数据在人们发现知识和改造自然的过程中具有越来越重要的作用，对空间数据挖 掘( s p a t i a ld a t am i n i n g ，s d m ) 和知识发现( k n o w l e d g ed i s c o v 盯y , k d ) 的研究应用也正愈来愈引起 2 南京航空航天大学硕士学位论文 人们的极大关注。s d m k d 目前已经成为国际研究和应用的热点，并且取得了相当的理论和技 术成就，很多学者对此及时进行总结。k o p e r s k i ，a d h i k a r y 和h a u l s 6 】总结了空间数据挖掘的发 展，认为大量的空间数据来自从遥感到g i s 、计算机制图、环境评价和规划等各种领域，空间 数据的积累已经远远超出人们的分析能力，数据挖掘已经从关系数据库扩展到空间数据库。他 们就空间数据生成、空间数据聚类和挖掘空间数据关联等方面总结了空间数据挖掘的最近发展。 h a r t 和k a m b 【s j 在其专著中，系统讲述了空间数据挖掘的概念和技术。李德仁院士很早关注空间 数据挖掘和知识发现【7 】，研究了从g i s 数据库中发现知识，构筑了空间数据挖掘和知识发现的 理论框架，系统研究了粗集和云理论在空间数据挖掘中理论和技术，提出了用于空间数据挖掘 的地学粗空间理论。m u r r a y 和e s t i v i l l - c a s t r o 【8 】回顾了探测性空间数据分析的聚类发现技术，分 析了基于统计学、数据挖掘和地理信息系统的空间模式识别和知识发现方法。 空间数据挖掘主要应用于军事、土地、电力、电信、石油和天然气、城市规划、交通运输、 环境监测和保护、1l o 和1 2 0 快速反应系统等资源管理和城市管理领域，在市场分析、企业客 户关系管理、银行保险、人口统计、房地产开发、个人位置服务等领域也正得到广泛关注与应 用，实际上，它正在深入到人们工作和生活的各个方面。 移动对象数据库( m o v i n go b j e c t sd a t a b a s e s ，m o d ) 的研究起源于二十世纪九十年代中期。 由于移动对象随着时间而发生地理空间上的变化，因此移动对象数据库属于时空数据库的范畴， 来源于描述地理空间的空间数据库和处理时间变化的时态数据库。然而与早期时空数据库只支 持地理空间的离散变化的情况不同，移动对象数据库关注地理空间随时问的连续变化。 近几年来，随着无线通信的一体化，移动对象数据的分析成为了学术界热门的话题，如交通 管理，海域管理，天气预报等能够跟踪移动对象，监控移动对象连续变化的位置，这样使得收 集大量移动对象的数据成为了可能，如车辆行驶位置、轮船行驶数据、飓风移动数据以及动物 迁徙数据等等。这就引起了学术界对这些移动对象数据分析产生浓厚的兴趣，从而发现其中有 价值的信息如从移动的数据中发现以相同方式运动的对象以及从大量数据集中发现可疑行为。 移动对象的聚类是数据库和数据挖掘学科中研究的前沿之一，具有十分广阔的应用前景。 移动对象的聚类可以被广泛地应用于国防军事、国家安全、智能交通管理、手机定位服务、 电子商务等领域。例如智能交通管理系统【2 l 】就是将汽车、驾驶员、道路及其相关的服务部门相 互联结起来，并使汽车在道路上的运行功能智能化。从而，使公众能够高效地使用公路交通设 施和能源。具体地说，该系统将采集到的各种道路交通及服务信息经交通管理中心集中处理后， 传输到公路运输系统的各个用户，出行者可实时选择交通方式和交通路线；交通管理部门可自 动进行合理的交通疏导、控制和事故处理；运输部门可随时掌握车辆的运行情况，进行合理调 度。从而，使路网上的交通流运行处于最佳状态，改善交通拥挤和阻塞，最大限度地提高路网 的通行能力，提高整个公路运输系统的机动性、安全性和生产效率。定位服务将成为短信息之 3 空间对象和移动对象聚类算法研究 后移动运营商的又一主力业务，无论是市场规模又或是盈利前景，这项业务都有可能继普通短 信息( s m s ) 、多媒体短信息( m m s ) 和数据服务之后，成为移动运营商业务的又一个亮点。国内 外对这些领域仍处于初步阶段，因此研究人员将面临着有一定挑战。总之，对于移动对象的聚 类分析将是人们感兴趣并且关注的话题。 1 1 3 国内外研究状况 上个世纪9 0 年代早期，大部分d m 研究人员来自于数据库领域，他们主要是为数据库系 统建立有效的数据分析工具。随后，更多领域的专家加入数据挖掘中，考虑问题的角度也被极 大的拓宽，提出了包括关联规则、聚类、分类、离群点检测等数据挖掘方向，这些方向的建立 也更好地推动了数据挖掘的前进，其中聚类分析是一门重要的技术，在数据挖掘、统计数据分 析、模式匹配和图像处理等领域具有广泛的应用前景。 国外研究人员在d m 的聚类分析这个领域已经发表了众多的研究成果和论文p l ，并且开 发了一大批数据挖掘软件，建立了大量的相关网站。空间聚类是在海量的空间数据中寻找有意 义的属性及其模型，通常这种空间关系在现实中是隐含的，由于海量的空间数据是来自宇宙图 像，地理信息系统，图像数据的采集等，因此对于用户来说分析详细的空间数据代价很高并且 是不现实的，空间聚类的目的就是自动根据相似性对数据对象进行分组，从而发现数据空间的分 布特征。迄今为止，学术界已经提出了大量的聚类算法【1 2 一埔】，通常可以分成5 类，( 1 ) 基于划分的， 如k - m e a n s 和k - m c d o i d s 算法；( 2 ) 基于层次的，如c r u b 和b r i c h ：( 3 ) 基于密度的，如d b s c a n 和o p t i c s ；( 4 ) 基于网格的，如s t i n g c l i q u e 和w a v e c l u s t e r ；( 5 ) 基于模型的，如c o b w e b 。 随着研究人员的不断的研究和探索，不断涌现出了许多新的算法，如n a c ( n e i g h b o r h o o d - b a s e d c l u s t e r i n g ) ，d b r s ( d e n s i t y - b a s e ds p a t i a lc l u s t e r i n gm e t h o dw i t hr