基于模拟退火与贪心策略的平衡聚类算法

摘要 针对现实应用通常要求聚类的结果相对平衡的问题，提出了一种基于模拟退火与贪心策略的平衡聚类算法（BCSG），该算法包括基于模拟退火的初始点选择算法（SACI）与基于贪心策略的平衡聚类算法（BCGS）2个步骤，以提高平衡聚类算法的聚类效果与时间性能。首先基于模拟退火在数据集中快速定位出K个合适的数据点作为平衡聚类初始点，然后每个中心点分阶段贪婪地将距离其最近的数据点加入簇中直至达到簇规模上限。在6个UCI真实数据集与2个公开图像数据集上进行的聚类对比实验结果表明：在簇数目较大时相比Fuzzy C-Means聚类结果平衡度最高提升了50%以上；聚类结果的准确率相比Balanced K-Means、BCLS两个表现较好的算法平均提高了8个百分点；算法时间复杂度也更低，在较大规模的数据集上运行时间比Balanced K-Means最高减少了近40%。实验结果表明BCSG具有更佳的聚类效果和时间性能