存在物理约束下基于密度空间聚类算法.doc

存在物理约束下基于密度空间聚类算法 　　（ 天津科技大学 计算机科学与信息工程学院， 天津 300222） 　　?? 　　摘 要：在现有的基于空间约束的空间聚类算法DBCluC和DBRS+等的研究和比较基础上，提出了一种新的处理物理约束的基于密度的空间聚类算法――DBCluC+。该算法在DBCluC算法基础上，采用网络拓扑结构建模通达对象，并增加通达对象访问点的宽度属性，从而采用约束距离（constrained distance）代替简单的欧几里德距离或障碍距离(obstacle distance)作为相异度的度量标准。理论分析和实验结果表明，DBCluC+算法不仅具有密度聚类算法的优点，而且聚类结果比传统的处理通达约束的聚类算法更合理，也更加符合实际情况的需要。 　　?す丶?词：聚类； 约束距离； 网络拓扑； 障碍距离; 无向图 　　?ぶ型挤掷嗪牛?TP301.6 文献标志码：A 　　 文章编号：1001?B3695(2009)03?B0873?B03 　　?? 　　Clustering spatial data in presence of physical constraints:?? 　　densitybased approach 　　?? 　　SUN Zhiwei 　　?? 　　(College of Computer Science Information Engineering, Tianjin University of Science Technology, Tianjin 300222, China) 　　?? 　　Abstract:Based on learning the current spatial clustering algorithms in the presence of constrains, such as DBCluC, DBRS+ and so on, this paper proposed a new method of densitybased spatial clustering called DBCluC+ which could handle the spatial constrains in a new way. In DBCluC+, the algorithm used network topology to model the facilitator and added a attribute named width of access point, so it used the constraint distance to replace the Euclidean distance or obstacle distance in DBCluC to as the criterion of the dissimilarly. Both theory analysis and experimental results confirm that the experiments show that the new proposed approach not only has the advantages of densitybased clustering algorithms, but also takes advantage of the constraint distance to make the results more reasonable than traditional ways, and the model of algorithm is according to the need of application. 　　??Key words：clustering; constraint distance; network topology; obstacle distance; indirect graph 　　?お? 　　 　　空间聚类是空间数据挖掘中一个重要的研究领域，能够发现空间数据库中隐含的知识、空间关系或其他有意义的模式。在现实生活中，存在很多约束条件，包括障碍物约束和通达约束。其中障碍物约束包括山川、湖泊、河流，而通达约束包括高速公路、山川中的隧道以及河流上的桥梁。这些因素严重影响地理数据的聚类结果。目前有一些能够处理障碍约束的算法，但是几乎没有合适的算法能够较好地处理公路、河流等通达约束对象并满足实际应用的需要。为了使得空间聚类算法能对现实情况更实用，本文提出了一种基于密度的空间聚类算法来更好地处理通达约束存在下的聚类问题。?? 　　1 相关工作?? 　　目前为止，比较典型的可以处理空间约束