《Dataclustering：50yearsbeyondk-means翻译.doc》由会员分享，可在线阅读，更多相关《Dataclustering：50yearsbeyondk-means翻译.doc（40页珍藏版）》请在金锄头文库上搜索。
1、K-means后数据聚类的50年发展Anil K.Jain 密歇根州立大学计算机科学与工程系 高丽大学大脑与认知工程系翻译人 徐天宇 专业班级 自动化1104 . 摘要：数据进行合理的聚群是理解和学习最基本的模式之一。例如，一个常见的科学分类将生物归类为如下的类别体系：域、界、门、纲、目等。聚类分析是根据对象的可测得的或可感知的本质特征或相似度来对其进行聚群或聚类的方法和算法的正式研究。聚类分析并不使用种类标签，即通过如类标这样已有的标示符来标识对象。类别信息的缺失将数据聚类（无监督学习）和分类或判别分析（有监督学习）。聚类的目标是寻找数据的结构，因此是对自然的一种探索。聚类在不同的科学领域里
2、面都有着悠久而丰富的历史。1955年第一次发表的K-means算法是最受欢迎的简单聚类算法之一。事实上，尽管K-means算法已经提出了50多年，而且从那时起发表了数以千计的其它聚类算法，K-means仍然有着广泛的运用。这说明设计一个有广泛适用性的聚类算法的困难以及聚类本身是一个病态问题。我们对聚类进行了简要的综述，总结了有名的聚类方法，讨论了设计聚类算法主要挑战和核心问题，指出了部分新兴和有用的研究方向包括半监督聚类、集成聚类、在数据聚类时同时进行特征选择以及大规模数据聚类。关键词：数据聚类、用户困境、历史发展、聚类的前景、傅京孙奖1. 引言传感和存储技术的进步以及像互联网搜索、数字成像、
3、视频监控等技术应用的迅猛发展产生了大量的高维数据集。据估计2007年数据全球数据使用量为281艾字节，预计2011年这个数字将增长10倍（1艾大约是1018B或1,000,000TB）。大部分的数据数字化的存储在电子介质中，因此给自动化数据分析、分类和检索技术的发展提供了巨大的可能。可利用的数据除了量的增长，类型也增多了（文本、图像、视频）。并不昂贵的数字摄影机产生了大量的图像和视频。由于无线射频识别标签和收发机低价和小尺寸，它们得以普及并导致了成千上万的能有规律传输数据的传感器的部署。E-mail、博客、交易数据以及数以亿计的网页每天产生数TB的新数据。很多这类数据流都是松散的，给分析它们增
4、加了难度。数据数量和类别两方面的增长迫切的需要自动理解、处理和概括数据的方法的进步。数据分析方法可以概括的分为主要的两类（Tukey,1997）:(i)探索性的或描述性的，指研究者没有事先明确的模型或假设但是想理解高维数据的大体特征和结构。（ii）验证性的或推理性的，指研究者想要验证适用于可用数据的假设/模型或一系列假定。很多统计学方法被用来分析数据，举几个例子，比如方差分析、线性回归、判别式分析、典型相关分析、多维定标、因子分析、主成分分析和聚类分析。一个相关有用的综述已经发表（Tabachnick和Fidell，2007）。在模式识别中，数据分析涉及预测建模：给定一些训练数据，我们想要预测
5、未知测试数据的行为。这个任务也被叫做“学习”，通常两类学习之间有明确的区别（i）有监督的（分类）。（ii）无监督的（聚类）。第一种只涉及有标签的数据（训练模式有已知的类别标签），而第二种只涉及无标签数据（Duda et al.2001）.聚类相比分类是一个更加困难更有挑战性的问题。一种混合的设置，即半监督学习正在受到越来越多的关注（Chapelle et al. 2006)。在半监督分类中，训练数据集中只有一小部分的标签是可用的。那些没有标签的数据，也在学习过程中使用，而不是被放弃了。在半监督聚类中，有些对间约束是明确的，而不是有明确的类标，也就是有一种弱化的先验知识。一个对间“必须连接”相当
6、于要求两个对象被赋予相同的聚类标签，反之，共享一个“不能连接”约束的两个对象的聚类标签应该是不同的。在潜在簇的准确定义缺失的数据聚类中，约束可以变得非常有用（Lange et al.,2005;Basu et al.,2008）。为了寻找好的模型，我们会应用所有的可用信息，不管是否是无标签的数据、有约束的数据还是有标签的数据。图1举例说明了这些模式识别和机器学习所感兴趣的不同类型的学习问题。图1. 学习问题：圆点表示不带有标签的点。带有标签的点由加号、星号和叉号表示。在图（c）中，必须连接和不能连接约束由实线和虚线各自表示（图片取自Lange et al.(2005)）。2. 数据聚类数据聚类
7、或者说聚类分析的目标是发现一系列模式、点或者对象的天然的分组情况。Webster（Merriam-Webster 在线字典,2008）将聚类分析定义为“关于通过定量比较多重特性发现群体中的个体是否属于不同的组别的一种统计分类方法。”图2是聚类的一个例子。目标是开发出一种可以从图2a中的无标签数据中发现图2b中的自然分组的自动化算法。图2. 各种各样的簇。图（a）（在图1（b）中由7种不同的颜色表示）中的7个簇在形状、大小和密度上都不同。虽然这些簇对数据分析师来说是显而易见的，但是目前还没有可用的聚类算法可以找出所有这些簇。 聚类的一种实用性定义可以表示如下：给定n个对象的某种表示，找到基于相似
8、度测量的K个分组使得在同一个分组中的对象间相似度高而处于不同分组中的对象间相似度低。但是，相似度的定义是什么？簇的定义又是什么？图2表明簇的形状、大小和密度可以是不同的。数据集中存在的噪声使得发现簇更加的困难。一个理想的簇可以被定义为一系列紧凑的、孤立的点集。事实上，从一个观看者的角度来看，一个簇是一个主观的实体，它的重要性和解释需要相应领域的知识。虽然人类本身是二维可能三维数据中簇的出色探求者，但是我们需要自动化算法来处理高维数据。聚类时因为不知道所给定数据到底可以分成几个簇，导致了数以千计的聚类算法的出现和将继续出现。2.1. 为什么要聚类？ 在任何涉及多变量数据分析的学科中聚类分析都是很
9、普遍的。通过谷歌学术搜索引擎（2009）搜索关键词 “数据聚类”仅仅出现在2007年的就有1660个条目。如此大量的文献足以说明聚类在数据分析中的地位。很难一一列举聚类方法在众多科学领域和应用领域的使用，同样，也很难一一列举已经发表的数以千计的聚类算法。图像分割作为计算机视觉中的一个重要问题可以表示为一个聚类问题（Jain 和 Flynn，1996；Frigui 和Krishnapuram，1999；Shi 和 Malik，2000）。文档可以被聚类（Iwayama 和 Tokunaga，1995）为几个有效信息访问或检索的局部层次结构（Bhatia和Deogun，1998）。聚类被用来将顾客
10、聚群为不同的类型以便进行有效的营销（Arabie和Hubert，1994）；被用来聚群服务提供协议以便进行劳动力管理和规划（Hu et al.,2007）；还被用来研究生物学中的基因组信息（Baldi和Hatfield，2002）。数据聚类主要被用在以下三个地方： (a)构造底层结构：获得对数据的深入了解，产生假设，侦测异常，识别特征。 (b)自然分类：识别形式或生物间的相似程度（系统发育关系）。 (c)压缩：通过聚类原型作为一种组织和概括数据的方法。图3是类别发现的一个例子。这里聚类被用在一个在线手写字符识别应用程序中来发现不同的子类（Connell和Jain，2002）。不同的用户会用不同
11、的方式写同一个数字，所以要适当增加类内差异。在一个类中聚类训练模式可以发现新的子类，叫做手写字符的词位。使用基于不同子类的多重模型而不是每个字符的单一模型可以用来提高识别的准确率（见图3）。图3. 使用数据聚类找到子簇。图（a）和（b）以两种不同的方式写数字2；图（c）是字符f的三种不同的子类；图（d）是字母y的三种不同子类。给定大量的英特网上的网页，很多查询词条会典型的返回大量的网页可点击数。这产生了对组织搜索结果的需要。像Clusty（www.clusty.org）这样的搜索引擎聚类了搜索结果，并将一个更加有序的结果呈现给用户。2.2. 历史发展聚类方法的发展确实是多学科共同努力的结果。分
12、类学家、社会科学家、心理学家、生物学家、统计学家、数学家、工程师、计算机科学家、医学研究者以及其他收集和处理真实数据的人都为聚类方法做出了贡献。根据JSTOR（2009），数据聚类第一次出现是在1954年发表的一篇处理人类学数据的文章的标题中。数据聚类根据不同的的应用领域也被叫做Q分析、类型学、聚丛、分类学（Jain和Dubes，1988）。目前有几本关于数据聚类的书，经典的是由Sokal和Sneath（1963）、Anderberg（1973）、Hartigan（1975）、Jain和Dubes（1988）和Duda et al.(2001)写的。数据挖掘领域也广泛研究了聚类算法（参见Han
13、和Kamber（2000）和Tan et al.(2005)写的书以及机器学习（Bishop，2006）。聚类算法可以粗略的分为两组：基于层次的和基于划分的。基于层次的聚类算法使用凝聚的模式（从将每个数据点作为一个簇开始相继的融合最相似的一对簇为一个新的簇层）或者分裂（自顶向下）的模式（从将所有数据点作为一个簇开始递归的分裂每个簇为一个更小的簇）递归的找到嵌套的簇。和基于层次的聚类算法相比，基于划分的算法找到所有的簇的同时也找到了数据的一个划分而且并不使用层级结构。基于层次的算法的输入是一个n*n的相似度矩阵，期中n是用于聚类的数据对象的数量。另一方面，基于划分的算法既可以使用n*d的模式矩阵
14、，期中n是表示有d维特征空间的n个对象，也可以使用相似度矩阵。值得注意的是相似度矩阵可以很容易的由模式矩阵导出，但是要从相似度矩阵中导出模式矩阵就要使用像多维定标（MDS）这样的定标方法。最著名的基于层次的算法是单一连接和完全链接；最受欢迎也最简单的基于划分的算法是K-means。由于可用数据本身的性质决定基于划分的算法在模式识别中更加受欢迎，我们在这里主要讨论这类算法。K-means自从在不同的科学领域中由Steinhaus（1956）、Lloyd（1957年提出，1982年发表）、Ball和Hall（1965）以及MacQueen（1967）独立的发现以来，已经有了丰富而多样的历史。即使K
15、-means距离它第一次提出已经过去了50多年，它仍然是聚类中最广泛使用的算法之一。易实现、简单、有效、经验上的成功是这个算法如此受欢迎的主要原因。下面，我们先总结一下K-means的发展历程，然后讨论数据聚类中的主要的成熟方法。2.3. K-means算法令X=xi，i=1，.,n是要用来分成K个簇C=ck，k=2，.,K的d维点集。K-means算法找到一个使得一个聚类中经验均值和点之间的平方误差最小。令k为ck的均值，类ck中k和点之间的平方误差定义为。K-means的目标是使得所有K个聚类中平方误差的和最小。最小化这个目标函数是一个NP困难问题（即使K=2）（Drineas et al
16、.,1999）。因此K-means是一个贪心算法，只能收敛于局部最优解，即使最近的研究表明当簇很好分开时K-means有很大的可能概率收敛于全局最优解（Meila，2006）。K-means从初始划分的K个聚类开始，并给簇分配模式以便减少平方误差。因为当簇数目K增加时平方误差总会减少（当K=n时，J（C）=0），只有当聚类数目是固定数量时才可以最小化J（C）。K-means算法的主要步骤如下（Jain and Dubes，1988）：1. 选择一个有K个簇的初始划分；重复步骤2和3直到每个聚类中的对象稳定。2. 通过将每个模式分配给各距离簇中心最近的簇产生一个新的划分。3. 计算新簇中心。 图4是一个有三类的2维数据集K-means算法的例子。图4. K-means算法的例子。图（a）表示有三个簇的二维输入数据；图（b）表示了用作簇中
