一种处理障碍约束的聚类算法

根据障碍约束空间聚类问题的特点，利用图论的相关知识，提出了一种分阶段的基于图的聚类的算法。首先，通过最小生成树聚类算法，在不考虑障碍约束的情况下对空间对象进行聚类；然后，引入障碍物对上一步的聚类结果进行分割；最后，根据被障碍物分割后形成的各个类之间的障碍距离，将距离较近的两个类合并，形成最终的聚类结果。最后通过实验验证了算法的效果，而且输入参数少，时间复杂度低。

Clustering arithmetic with obstacle constraints

According to the characteristics of clustering with obstacle constraints, using the knowledge of graph theory, a multi-step Arithmetic was proposed. Firstly, it clustered the objects without obstacles by minimum spanning tree clustering method. Then it took obstacles to divide the generated clusters. Lastly it merged the clusters whose obstruct distance was little enough. The algorithm need only one parameter, it is of good performance and can find clusters with arbitrary shapes and varying densities. At last its effectiveness was demonstrated through experiment.