带障碍的空间分级聚类算法

Spatial Hierarchical Clustering in the Presence of Obstacle

带障碍的聚类问题是一个具有实际应用价值的问题,因为现实世界中确实存在河流、山脉等之类的物理障碍,它们的存在会影响聚类结果的合理性。传统的聚类算法在进行空间数据的聚类时,往往忽略了障碍对于聚类结果的影响。本文讨论了不同障碍对数据点间连通性的不同影响,提出了带障碍的分级聚类算法 OBHIEC。分级聚类方法使得需要计算障碍距离的点对数目减少,并能处理数据分布密度不同的情况。实验结果表明,OBHIEC 算法能有效完成带障碍的聚类,并具有较好的增量特性。

The problem of spatial clustering in the presence of obstacles has many practical applications. Many traditional clustering algorithms are performed without the presence of obstacles that exist in the real world, such as rivers, lakes and hills, but their presence may affect the result of clustering substantially. In this paper, a hierarchical clustering algorithm, called OBHIEC, is proposed, which can reduce the calculation of obstructed distance and is suitable for data set with varied distributing density. The experiment results show that OBHIEC is both effective and efficient.