K-means后数据聚类的50年发展
Anil K.Jain 密歇根州立大学计算机科学与工程系 高丽大学大脑与认知工程系
翻译人 徐天宇 专业班级 自动化1104 .
摘要：数据进行合理的聚群是理解和学习最基本的模式之一。例如，一个常见的
科学分类将生物归类为如下的类别体系：域、界、门、纲、目等。聚类分析是根据对象的可测得的或可感知的本质特征或相似度来对其进行聚群或聚类的方法和算法的正式研究。聚类分析并不使用种类标签，即通过如类标这样已有的标示符来标识对象。类别信息的缺失将数据聚类（无监督学习）和分类或判别分析（有监督学习）。聚类的目标是寻找数据的结构，因此是对自然的一种探索。聚类在不同的科学领域里面都有着悠久而丰富的历史。1955年第一次发表的K-means算法是最受欢迎的简单聚类算法之一。事实上，尽管K-means算法已经提出了50多年，而且从那时起发表了数以千计的其它聚类算法，K-means仍然有着广泛的运用。这说明设计一个有广泛适用性的聚类算法的困难以及聚类本身是一个病态问题。我们对聚类进行了简要的综述，总结了有名的聚类方法，讨论了设计聚类算法主要挑战和核心问题，指出了部分新兴和有用的研究方向包括半监督聚类、集成聚类、在数据聚类时同时进行特征选择以及大规模数据聚类。
关键词：数据聚类、用户困境、历史发展、聚类的前景、傅京孙奖
1. 引言
传感和存储技术的进步以及像互联网搜索、数字成像、视频监控等技术应用的迅猛发展产生了大量的高维数据集。据估计2007年数据全球数据使用量为281艾字节，预计2011年这个数字将增长10倍（1艾大约是1018B或1,000,000TB）。
大部分的数据数字化的存储在电子介质中，因此给自动化数据分析、分类和检索技术的发展提供了巨大的可能。可利用的数据除了量的增长，类型也增多了（文本、图像、视频）。并不昂贵的数字摄影机产生了大量的图像和视频。由于无线射频识别标签和收发机低价和小尺寸，它们得以普及并导致了成千上万的能有规律传输数据的传感器的部署。E-mail、博客、交易数据以及数以亿计的网页每天产生数TB的新数据。很多这类数据流都是松散的，给分析它们增加了难度。
数据数量和类别两方面的增长迫切的需要自动理解、处理和概括数据的方法的进步。数据分析方法可以概括的分为主要的两类（Tukey,1997）:(i)探索性的或描述性的，指研究者没有事先明确的模型或假设但是想理解高维数据的大体特征和结构。（ii）验证性的或推理性的，指研究者想要验证适用于可用数据的假设/模型或一系列假定。很多统计学方法被用来分析数据，举几个例子，比如方差分析、线性回归、判别式分析、典型相关分析、多维定标、因子分析、主成分分析和聚类分析。一个相关有用的综述已经发表（Tabachnick和Fidell，2007）。 在模式识别中，数据分析涉及预测建模：给定一些训练数据，我们想要预测未知测试数据的行为。这个任务也被叫做“学习”，通常两类学习之间有明确的区别（i）有监督的（分类）。（ii）无监督的（聚类）。第一种只涉及有标签的数据（训练模式有已知的类别标签），而第二种只涉及无标签数据（Duda et al.2001）.聚类相比分类是一个更加困难更有挑战性的问题。一种混合的设置，即半监督学习正在受到越来越多的关注（Chapelle et al. 2006)。在半监督分类中，训练数据集中只有一小部分的标签是可用的。那些没有标签的数据，也在学习过程中使用，而不是被放弃了。在半监督聚类中，有些对间约束是明确的，而不是有明确的类标，也就是有一种弱化的先验知识。一个对间“必须连接”相当于要求两个对象被赋予相同的聚类标签，反之，共享一个“不能连接”约束的两个对象的聚类标签应该是不同的。在潜在簇的准确定义缺失的数据聚类中，约束可以变得非常有用（Lange et al.,2005;Basu et al.,2008）。为了寻找好的模型，我们会应用所有的可用信息，不管是否是无标签的数据、有约束的数据还是有标签的数据。图1举例说明了这些模式识别和机器学习所感兴趣的不同类型的学习问题。
图1. 学习问题：圆点表示不带有标签的点。带有标签的点由加号、星号和叉号表示。在图（c）中，必须连接和不能连接约束由实线和虚线各自表示（图片取自Lange et al.(2005)）。
2. 数据聚类
数据聚类或者说聚类分析的目标是发现一系列模式、点或者对象的天然的分组情况。Webster（Merriam-Webster 在线字典,2008）将聚类分析定义为“关于通过定量比较多重特性发现群体中的个体是否属于不同的组别的一种统计分类方法。”图2是聚类的一个例子。目标是开发出一种可以从图2a中的无标签数据中发现图2b中的自然分组的自动化算法。
图2. 各种各样的簇。图（a）（在图1（b）中由7种不同的颜色表示）中的7个簇在形状、大小和密度上都不同。虽然这些簇对数据分析师来说是显而易见的，但是目前还没有可用的聚类算法可以找出所有这些簇。
聚类的一种实用性定义可以表示如下：给定n个对象的某种表示，找到基于相似度测量的K个分组使得在同一个分组中的对象间相似度高而处于不同分组