障碍空间中Voronoi图优化的反向近邻数聚类算法

来源：计算机科学与探索杂志2022年第9期北京时间：

作者：何云斌, 刘婉旭, 万静

单位：哈尔滨理工大学 计算机科学与技术学院,哈尔滨 150080

摘要：针对现有的障碍空间聚类算法需要人工选取聚类中心及设定阈值等问题,提出了一种障碍空间中Voronoi图优化的反向近邻数聚类算法（OBRK-means）。该算法从聚类中心的选取、离群点的筛选和广义覆盖圆三方面进行讨论和分析。首先,该算法引入Voronoi图来计算反向近邻数,进而确定聚类中心的候选集合;其次,利用Voronoi图和样本点密度进行数据集中离群点的筛选和剪枝;最后,引入广义覆盖圆来进行初始聚类,针对初始聚类结果不精确的问题提出内边界点和外边界点,并在内边界点和外边界点中根据公式分别计算出剔除点和拓展点来提高聚类准确性。理论研究和实验表明,该算法在处理障碍空间中的数据时具有更高的效率,能够得到更好的聚类结果。

关键词：聚类,Voronoi图,障碍空间,反向近邻数

基金资助：国家自然科学基金(61872105);黑龙江省教育厅科学技术研究项目(12531z004)