基于道路网络的约束聚类.pdfVIP

CN43-1258／TP 计算机工程与科学 2008年第 3O卷第 12期 ISSN 1007—130X COMPUTERENGINEERING SCIENCE Vo1．30，No．12，2008 文章编号：1007—130X(2008)12—0131—03 基于道路网络的约束聚类 ConstraintClusteringBasedonaRoadNetwork 刘文婷，王志坚，冯 钧 LIUWen-ting。WANGzm-jian。FENGJim (河海大学计算机及信息工程学院。江苏 南京210024) (SchoolofComputerandInformationEngineering。HohaiUniversity。Nanjing210024，China) 摘 要：聚类法是最重要的空间数据分析方法之一。在大多数真实的应用中，对受限于网络空间的数据访问和分析更 有意义(如道路网络上对象的分析)。目前已有一些道路网络聚类方法，但都是基于理想的抽象空问，没有考虑现实存在的 约束条件(如交通限制信息)，因此不能直接应用到现实环境中。本文提出了带约束条件的道路网络模型，扩展 了已有的聚 类算法。算法的实验结果表明，算法对真实的道路网络中的对象聚类是高效的。 Abstract：ClusteringisoneofthemostimportantanalysistasksinspatiM databases．However，inmanyrealapplica- tions，itismoremeaningfultoworkOilclusteringobjectsinaconstrainedspatialnetwork(己g．roadnetwork)．Theexist— ingmethodsdonotconsidertheconstrainedcondition (巴g．trafficinformation)，whichisbasedOliallidealandabstract network．Itisthereforedifficulttoapplythem toarealroadnetwork．Thispaperproposesamodelofclusteringobjectsin aroadnetworkwithconstrainedeonditionsandimprovestheexistingalgorithmsTheexpermienta1resultsshow thatthe mode1achievesahighefficiency． 关键词：聚类；约束条件；道路网络 Keywords：clustering；constraintcondition；roadnetwork 中图分类号：TP3l1 ， 文献标识码：A 聚类问题 ，提出了带约束条件的道路网络模型；将道路网上 1 引言 已有的对象聚类算法嘲转化为基于道路网络的约束聚类。 聚类[1]是指一个类簇内的实体是相似的，不同类簇的 2 相关工作 实体是不相似的。聚类是数据挖掘、模式识别等研究方向 的重要研究内容之一，在识别数据的内在结构方面具有极 目前，道路网上对象的聚类研究有基于静态数据集的 其重要的作用。文献[23已提到，研究空问网络上的移动对 研究[～，也有基于道路网上持续移动对象的聚类研究[6j， 象的聚类很有意义。在真实的世界中，对象往往是在一个 这些研究涉及的道路模型都是由Yiu等人 2004年提出的 受限的网络空间中移动。在实际的应用场景中，用户常常 网络模型。此模型能很好地表示城市道路网络及其上的移 具有清晰的应用需求 ，并且希望能够将这些需求作为背景 动对象，但这些聚类