障碍空间里基于密度的快速聚类算法

传统的聚类方法不能直接运用于分布空间内存在障碍物的数据的聚类.提出了一种障碍空间内基于密度的快速聚类算法DBCO来解决此类问题.DBCO中,在基于密度的聚类基础上引入了障碍模型,提出了一种保持数据间可见性的简化障碍的方法.为了使障碍模型不影响聚类质量,定义了障碍顶点距离、连接距离和判断距离来维持聚类的质量.另外,在聚类过程中,选择某一些代表点和拓展点而不是每一个点来对每一个聚类进行扩展,从而大大提高了聚类算法的效率.实验结果表明了DB-CO算法可以快速地得到高质量的聚类结果.

Fast Density-based Clustering Algorithm Containing Obstacles

Hitherto,although many methods have been proposed,there exist many obstacles in the real world such as rivers and high ways whose existence may affect the quality of clustering and cannot be solved by conventional clustering methods.In this paper,a clustering algorithm called DBCO to handle obstacles is proposed.An obstacle model in order to take obstacles into consideration while clustering is introduced in the algorithm and a method to simplify polygon obstacles with less segments than edges of polygon and without any loss of ability of maintaining the visibility of data points outside the polygon is also presented.The obstacle-vertex distance,connection distance and judge distance are defined to counteract the influence from obstacles on the cluster.Moreover,in order to enhance the efficiency of the algorithm,some data called select-point and expend-point rather than each point are chosen in the neighborhood to expand every cluster.Various performance studies show that DBCO is both efficient and effective.