k-平均问题及其变形的算法综述

作     者：徐大川 许宜诚 张冬梅 XU Dachuan;XU Yicheng;ZHANG Dongmei

作者机构：北京工业大学应用数理学院北京100124 山东建筑大学计算机科学与技术学院济南250101 

出 版 物：《运筹学学报》 (Operations Research Transactions)

年 卷 期：2017年第21卷第2期

页      面：101-109页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：国家自然科学基金(No.11531014) 山东省高等学校科研计划项目(No.J15LN23) 

主　　题：聚类问题 k-平均 NP-难 

摘      要：k-平均问题是计算机科学和组合优化领域的经典问题之一.k-平均聚类作为最受重视而且最简单易懂的一种聚类分析方法流行于数据挖掘领域.k-平均问题可描述为:给定n个元素的观测集,其中每个观测点都是d维实向量,目标是把这n个观测点划分到k(≤n)个集合中,使得所有集合中的点到对应的聚类中心的距离的平方和最小,其中一个集合的聚类中心指的是该集合中所有观测点的均值.k-平均问题在理论上是NP-难的,但有高效的启发式算法,广泛应用在市场划分、机器视觉、地质统计学、天文学和农业等实际背景中.随着实际问题中遇到的k-平均问题更加复杂,数据量更加庞大,还需学者进行更深一步的研究.罗列出k-平均问题及其诸多变形及推广问题的经典算法,并总结k-平均中尚待研究的若干问题.