题目: K-means及其变形的算法综述

报告人: 徐大川，北京工业大学数理学院副院长，北京科学与工程计算研究院副院长，教授，博士生导师

报告时间: 2017年12月14日下午14:00-15:00

地点: 知新楼B1032

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