一种处理障碍约束的基于密度的空间聚类算法

Density-based spatial clustering method with obstacle constraints

在现有的基于障碍约束的空间聚类算法COD_CLARANS、DBCLuC、AUTOCLUST+和DBRS+的基础上,提出了一种新的基于密度的空间聚类算法——基于障碍距离的密度聚类算法(DBCOD)。该算法在DBCLuC算法的基础上,采用障碍距离代替欧几里得距离作为相异度的度量标准,并在预处理过程中用障碍多边形合并化简方法来提高障碍物的处理效率。仿真实验结果表明,DBCOD算法不仅具有密度聚类算法的优点,而且聚类结果比传统基于障碍约束的密度聚类算法更合理、更加符合实际情况。

Current spatial clustering algorithms in the presence of obstacles, such as COD_CLARANS, DBCLuC, AUTOCLUST ＋ and DBRS ＋, were studied and compared. Then a new method of density-based spatial clustering called DBCOD was proposed which could handle the obstacle constraints in a new way. In DBCOD, obstructed distance was used to replace Euclidean distance in DBCLuC as the criterion, and a polygon combination and reduction method was used in the preprocessing stage to improve the efficiency. Simulation results show that this new proposed approach not only has the advantages of density-based clustering algorithms, but also takes advantage of the obstructed distance to make the results more reasonable than traditional ways.