中南大学计算机学院、生物信息学湖南省重点实验室成员2017级张震博士研究生在聚类分析和噪音识别领域取得重要研究成果。该研究成果以“A local search algorithm for k-means with outliers”为题，在人工智能期刊《Neurocomputing》上发表。
给定欧氏空间中的一个数据集合，鲁棒k-均值问题要求移除集合中的m个异常点，使得剩余数据的聚类代价最小。鲁棒k-均值问题在微阵列分析和图像处理等对聚类结果鲁棒性要求较高的领域中被广泛应用。该研究为鲁棒k-均值问题提出了一个多项式时间的局部搜索算法RLS（Relaxation-based Local Search）。RLS算法利用贪心采样方法构造候选聚类中心集合，并基于局部搜索技术求解一个松弛的目标函数。该研究基于一组在局部最优解和最优解之间执行的中心点交换对分析RLS算法的性能，证明了一个双标准常数近似保证。此外，该研究在PenDigits、PageBlocks、SensorReadings、Yeast等公开数据集上验证RLS的聚类效果与噪声识别准确率。实验结果表明，RLS的性能明显优于k-means--、T-k-means++、LS-Outlier等现有的启发式算法，且对输入参数k和m的取值具有较高的容错性。
王建新教授团队长期致力于计算机算法与优化、生物信息学、医学影像分析等方面研究。该研究工作得到国家自然科学基金等基金支持。
移除数据集合中的异常点可以改进数据的聚类效果