摘要
根据障碍约束空间聚类问题的特点,利用图论的相关知识,提出了一种分阶段的基于图的聚类的算法。首先,通过最小生成树聚类算法,在不考虑障碍约束的情况下对空间对象进行聚类;然后,引入障碍物对上一步的聚类结果进行分割;最后,根据被障碍物分割后形成的各个类之间的障碍距离,将距离较近的两个类合并,形成最终的聚类结果。最后通过实验验证了算法的效果,而且输入参数少,时间复杂度低。
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 ef...
出处
《计算机应用》
CSCD
北大核心
2009年第2期406-408,411,共4页
journal of Computer Applications
基金
国家自然科学基金资助项目(70771110)
关键词
聚类
障碍约束
最小生成树
障碍距离
clustering
obstacle constraints
minimum spanning tree
obstruct distance
