基于障碍物约束的遗传-中心点聚类算法研究

Research on the genetic-medoid clustering algorithm with obstacles restriction

面对障碍物约束的聚类问题,分析了目前障碍物约束聚类算法的不足,定义了相关概念,随机选择k个样本作为聚类中心点,以距各聚类中心点的可达距离为样本划分依据,以类内平方误差和(WGSS)为聚类目标函数,引入遗传算法,提出一种基于障碍物约束的遗传-中心点聚类算法。最后,通过实例进行了算法测试,并与k-中心点算法进行比较。算法测试结果表明:基于障碍物约束的遗传-中心点聚类算法是完全可行和有效的,所提算法使得聚类结果符合地理空间实际情况,解决了聚类结果对初始化敏感的问题。

The shortcomings about these days clustering algorithm with obstacles restriction are analyzed. Facing the clustering question with obstacles restriction, the approach describing obstacles, the direct accessibility distance, the indirect accessibility distance are defined. The genetic-medoids clustering algorithm with obstacles restriction is put forward, selecting randomly the clustering medoids, partitioning samples according to the best-close distances to the medoids considering obstacles entities, calculating cluster target function on within-group sum of squares error, importing genetic algorithm. In the end, the algorithm is validated and compared with k-medoids by examples. Algorithm testing show： the new algorithm with obstacles restriction is completely feasible and availability. The genetic-medoids clustering algorithm with obstacles restriction makes clustering outcome according with geography space instance and solves the sensitivity question of clustering outcome to initialization.