一种基于空间相依性的移动对象聚类算法.pdfVIP

第32卷第 期 微 计 算 机 应 用 VoL32No．5 2011年5月 MICROCOMPUIERAPPLICAnONS May．2011 一 种基于空间相依性的移动对象聚类算法术 苏孝强，2 倪 宏2 (中国科学院研究生院 北京 100049 中国科学院声学研究所 国家网络新媒体工程技术研究中心 北京 1001~) 摘要：移动对象的聚类算法，要求能够适应移动对象移动模式动态变化的特点。针对该问题，提出了一种基于空间相依性的 移动对象聚类算法。该算法首先计算移动对象之间的空间相依度，空间相依度考虑了移动对象之间的移动速度、方向及位 置。当用户之间的空间相依度大于某一阈值时，认为对象之间可达，所有相依度可达对象划分为同一个群组，从而实现移动 对象聚类。算法采用一段时间内对象的平均速度和方向代替即时速度和方向，能够有效降低重新聚类次数。实验及分析表 明，该算法能够体现移动对象的移动特性，对于移动对象的聚类具有较高性能。 关键词：移动对象 聚类 空间相依性 数据挖掘 AClusteringAlgorithm forMovingObjectsBasedonSpatialDependency SU Xiaoqiang一 ，NIHong (G‘raduateUniversityofChineseAcademyofSciences，Beijing，100049，China，NationalNetworkNewMediaEngineering ResearchCenter，InstituteofAcoustics，ChineseAcademyofSciences，Beijing，100190，China) Abstract：Clusteringalgorithmformovingobjectsrequireshteabilitytoadapttodynamicchangesinmovingpatternsofmovingobjects． Tosolvehtisproblem，amehtodcalledspatialdependencybasedmovingobjectsclustering(SDMOC)algorithmisproposed．Firstly， itcalculatesthedegreeOfspatialdependency(SD)betweenmovingobjects．TheSDtakesintoaccountthemovingspeed，direction andthepositionofobjects．TheobjectscallreacheachohterwhenSDgraterthanathreshold．Allhtereachbaleobjectsaredividedinto thesarnegrouptogetallthegroups．Inthisprogress，itUSeSthehistoricalaveragespeedna ddirectioninashorttimetoinsteadofhte instancespeednaddirection．Itcanreducethefreuqencyofre—clustering．TestresultsnadevaluationsshowSDMOCcanreflectthe characteristicsofmovingobjects．Ithashighperformanceofrmovingobjectsclustering． Keywords：movingobjects，clustering，spatialdependency，datamining 1 引言 移动对象动态聚类对于有哪些信誉好的足球投注网站营救、预测交通流量以及推荐相关度较高的好友均有重要意义。然而，由 于移动对象的地理位置和运动状态不断变化，群组划分也将动态变化。要求聚类算法能够适应高度动态变 化的运动模式，同时尽量减少重新聚类的次数。现有多数聚类方法 卜。没有考虑到对象的移动特性，或假设 对象属性改变缓慢，因而不适合移动环境