基于道路网络的移动对象聚类.pdf

74 20I6，52(7) ComputerEngineeringandApplications计算机工程与应用 基于道路网络的移动对象聚类 王金凤 ，邢长征 WANGJinfeng，XING Changzheng 辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105 SchoolofElectronicandInformationEngineering，LiaoningTechnicalUniversity，Huludao，Liaoning125105，China WANG Jinfeng，XING Changzheng．Clusteringalgorithm formovingobjectsbasedonroadnetwork．Computer EngineeringandApplications，2016，52(7)：74-78． Abstract：Existingobjectsbasedonroadnetworkclusteringalgorithmeb-·clsusesthenewtorkdistancetodescribesimi-- laritybetweenmovingobjects．Itdoesnotmakefulluseoftimeandspacepropertiesoftheobjects，whichmayleadtothe algorithmcan’treflectthemovementpatternofmobileobjectdynamicevolution，frequentlyupdatedclusteringresults， notsatisfactoryclusteringaccuracy,low efficiencyandSOon．Aimedatthesedeficiencies，thispaperputsforwardthe MovingObjectsBasedonRoadNetwork(MOBORN)clusteringalgorithm．Itintroducesthesimilaritycoefficientof timeandspace，takesthespeed，thedirectionandthepositionofmobileobjectintoaccount，Whenthesimilaritycoeffi— cientofspaceandtimebetweenmovingobjectsreachtothegiventhreshold，itassignsthemtothesamecluster,andatthe sametime，dynamicallymaintenancesclusteringresults，reducesthetimeofclustering．Theexperimentalresultsshow thatthealgorithm achieves97％accuracyand40％higherefficiencyforclusteringmovingobjectsinrealroadnetwork thantheeb-clsalgorithm ． Keywords：roadnetwork；movingobjects；clustering；temporalandspatialsimilaritycoefficient；datamining 摘 要：现有的基于道路网络对象聚类算法eb—c1s采用网络距离描述移动对象间的相似性，没有充分利用对象的时 间和空间属性，造成算法不能体现移动对象动态演化的移动模式，频繁更新聚类结果并且聚类精度不理想，执行效 率低等问题。针对这些不足 ，提 出基于道路网络的移动对象聚类算法MOBORN(MovingObjectsBasedonRoad Network)，该算法引入时空相似系数 ，考虑 了移动对象速度、方向和位置。当移动对象间的时空相似系数达到给定 阈值，将其分到同一聚类，并动态维护聚类结果，减少聚类次数。实验结果证明，与eb．cls算法相比，该算法聚类精度 保持在97％以上，运行效率提高了40％。 关键词：道路 网络；移动对象；聚类；时空相似系数；数据挖掘 文献标志码：A 中图分类号：TP311．5 doi：10．3778／j．issn．1002．8331．1405．0423 1 引言 的相似度，提高聚类精度 ，但该算法在数据量增大时，效 聚类是将数据对象分成类或者簇的过程 ，使 同一簇 率较