logo资料库

Data Clustering: 50years beyond kmeans 翻译.doc

发布时间：2022-06-12 发布人：admin 分类：说明书 资料大小：2.65M 资料格式：doc 举报 版权申诉
第1页 / 共38页
第2页 / 共38页
第3页 / 共38页
第4页 / 共38页
第5页 / 共38页
第6页 / 共38页
第7页 / 共38页
第8页 / 共38页
资料共38页，剩余部分请下载后查看
    K-means后数据聚类的50年发展
    1. 引言
    传感和存储技术的进步以及像互联网搜索、数字成像、视频监控等技术应用的迅猛发展产生了大量的高维数据集。
    数据数量和类别两方面的增长迫切的需要自动理解、处理和概括数据的方法的进步。数据分析方法可以概括的分为
    在模式识别中，数据分析涉及预测建模：给定一些训练数据，我们想要预测未知测试数据的行为。这个任务也被叫
    图1. 学习问题：圆点表示不带有标签的点。带有标签的点由加号、星号和叉号表示。在图（c）中，必须连接
    2. 数据聚类
    数据聚类或者说聚类分析的目标是发现一系列模式、点或者对象的天然的分组情况。Webster（Merri
    图2. 各种各样的簇。图（a）（在图1（b）中由7种不同的颜色表示）中的7个簇在形状、大小和密度上都
    聚类的一种实用性定义可以表示如下：给定n个对象的某种表示，找到基于相似度测量的K个分组使得在
    2.1. 为什么要聚类？
    在任何涉及多变量数据分析的学科中聚类分析都是很普遍的。通过谷歌学术搜索引擎（2009）搜索关
    数据聚类主要被用在以下三个地方：
    (a)构造底层结构：获得对数据的深入了解，产生假设，侦测异常，识别特征。
    (b)自然分类：识别形式或生物间的相似程度（系统发育关系）。
    (c)压缩：通过聚类原型作为一种组织和概括数据的方法。
    图3是类别发现的一个例子。这里聚类被用在一个在线手写字符识别应用程序中来发现不同的子类（Connel
    图3. 使用数据聚类找到子簇。图（a）和（b）以两种不同的方式写数字2；图（c）是字符‘f’的三种不
    给定大量的英特网上的网页，很多查询词条会典型的返回大量的网页可点击数。这产生了对组织搜索结果的需要。
    2.2. 历史发展
    聚类方法的发展确实是多学科共同努力的结果。分类学家、社会科学家、心理学家、生物学家、统计学家、数学家
    聚类算法可以粗略的分为两组：基于层次的和基于划分的。基于层次的聚类算法使用凝聚的模式（从将每个数据点
    最著名的基于层次的算法是单一连接和完全链接；最受欢迎也最简单的基于划分的算法是K-means。由于可
    2.3. K-means算法
    令X={xi}，i=1，...,n是要用来分成K个簇C={ck，k=2，...,K}的d维点集。K-
    1.选择一个有K个簇的初始划分；重复步骤2和3直到每个聚类中的对象稳定。
    2.通过将每个模式分配给各距离簇中心最近的簇产生一个新的划分。
    3.计算新簇中心。
    图4是一个有三类的2维数据集K-means算法的例子。
    图4. K-means算法的例子。图（a）表示有三个簇的二维输入数据；图（b）表示了用作簇中心的三个
    2.4. K-means的参数
    K-means算法需要用户确定三个参数：类的数目K、类的初始化、距离尺度。其中最重要的参数是K。因为
    K-means一般会选择欧几里得距离作为距离尺度来计算点和簇中心之间的距离。因此K-means找到的
    2.5. K-means的扩展
    基础的K-means算法已经被很多不同的方式扩充了。有些扩充使用额外的试探性方法处理簇尺寸最小化，合
    2.6. 聚类的主要方法
    就像之前提到的一样，在很多不同的学科的文献中提出了数以千计的聚类算法。这使得回顾所有这些已经发表的方
    簇可以被定义为在特征空间中由低密度区域分开的高密度区域。算法根据这个簇的定义直接搜索特征空间中连通的
    虽然基于密度的方法，尤其是无参数的基于密度的方法因为可以处理任意形状的簇的内在性质而很有吸引力，但是
    图论聚类，有时也被叫做谱聚类，用一个加权的图代表数据点。连接两个节点之间的边由对间相似度加权。主要思
    有些聚类算法有一个信息理论公式。比如，Roberts et al.(2001)提出的最小熵方法假设数
    3. 用户的困境
    尽管有如此大量的聚类算法，而且这些算法也在许多不同的领域成功应用，聚类仍然是一个困难的问题。这可以归
    （Jain和Dubes，1998）强调以下聚类的主要挑战，这即使到今天来看依然是中肯的。
    （a）什么是一个簇？
    （b）应该使用哪些特征？
    （c）数据需要标准化吗？
    （d）数据是否有异常值？
    （e）怎样定义对间相似度？
    （f）数据中有多少簇？
    （g）应该使用哪个聚类方法？
    （h）数据是否有聚类趋势？
    （i）发现的簇和划分是否有效？
    以下我们会强调和举例说明其中一些挑战。
    3.1. 数据表示法
    数据表示是影响聚类算法性能最重要的因素之一。如果表示法（特征的选择）很好，那么簇很有可能是紧凑而孤立
    图5. 一个好的表示法的重要性。图（a）表示K-means无法找出“自然”簇的“两环”数据集；虚线表
    3.2. 分组的目的
    数据的表示和分组的目的密切联系。表示法必须和用户最终的目的相配合。（Pampalk et al.,2
    图6. 数据特征的不同权重导致数据的不同划分。16种动物由与外形和活动相关的13个布尔特征值表示。图
    3.3. 簇的数目
    自动确定簇的数目是数据聚类中最困难的问题之一。大部分自动确定簇数目的方法是将其转化为模型选择问题。通
    图7. 簇数目K的自动选择。图（a）表示由6个高斯分布混合产生的输入数据；图（b）-（d）各自表示适
    3.4. 簇的有效性
    聚类算法倾向于找到数据中的簇而不考虑是否有簇的存在。图8a展示了一个没有自然聚集的数据集；这里所有的
    图8. 聚类有效性。图（a）表示没有自然聚集情况的数据集；图（b）表示K-means当K = 3时的
    聚类有效性指标可以基于3个不同的准则来定义：内部的、外部的和相对的（Jain和Dubes，1988）
    图9. 15个二维模式的几个聚类结果：图（a）表示15个模式；图（b）表示15个模式的最小生成树；图
    3.5. 比较聚类算法
    即使对于相同的数据不同的聚类算法往往会产生完全不同的划分。在图9中，7种不同的算法被用来聚类15个二
    图10. 聚类算法的聚类结果。图（a）表示35种不同算法的层次聚类结果；图（b）表示通过将35种算法
    一个有趣的问题是如何确定不管数据如何变化，都能产生相似划分的算法。换句话说，我们能对聚类算法进行聚类
    聚类算法也可以基于目标函数在理论层面上进行比较。为了进行这样的比较，聚类方法和聚类算法之间的差异应该
    以上这些讨论说明了聚类的一个很重要的事实：没有最好的聚类算法。每一种聚类算法都或明确或含蓄的给数据一
    3.5. 聚类算法的容许性分析
    Fisher和vanNess（1971）正式以比较聚类算法和为选择聚类步骤提供指导为目标分析了聚类算
    (a)凸状：一个聚类算法聚类结果的簇的凸壳并不相交则称该聚类算法是是凸状容许的。
    (b)簇均衡：如果聚类算法的结果使一些簇复制任意次数情况下，簇的边界都不改变，那么就称这个聚
    (c)簇冗余：如果从聚类算法结果中移除其中一个簇的数据，再运行算法，得到的K-1个簇和未再运
    (d)单调：如果当相似度矩阵元素单调改变时，聚类算法结果不发生改变，那么就称该聚类算法是单调
    Fisher和Van Ness证明不能设计出满足一定容许准则的算法。比如，如果一个算法是单调容许的，
    Kleinberg（2002）指出了一个相似的问题，并定义了三个准则：
    (a)标度不变性：任意标度的相似度矩阵不改变聚类结果。
    (b)丰富性：聚类算法能获得数据的所有可能划分。
    (c)一致性：收缩簇内距离和拉伸簇间距离，聚类结果并不改变。
    Kleinberg也提供了和（Fisher与VanNess，1971）相似的结论，表明设计出同时满足
    4. 数据聚类的趋势
    信息爆炸不仅仅是创造了大量的数据，同时也创造了包括有结构的和无结构的多样化的数据。无结构的数据是指一
    4.1. 聚类集成
    有监督学习的集成方法应用的成功激发了无监督学习集成方法的发展（Fred和Jain，2002）。主要思
    图11. 聚类集成。通过多次运行K-means，基于簇中点的“共现”学习对间相似度。这种相似度可以被
    有很多方法用于产生聚类集成和综合划分结果。比如多重数据划分可以通过以下方法产生：（i）应用不同的聚类
    4.2. 半监督聚类
    聚类问题本身是一个病态问题。它的目标是只基于固有的信息将数据划分成不知道簇数目的簇。聚类问题数据驱动
    图12是半监督学习在图像分割中应用的一个例子（Lange et al.,2005）。图12a表示用于
    图12. 半监督学习。图（a）表示由5种均匀质地区域组成的输入图像；像素点之间必须连接（蓝色实线）和
    大部分半监督聚类方法（Bar-Hillel et al.,2003;Basu et al.,2004
    图13. 随着对间约束增加BoostCluster（使用标准化的交互信息（NMI）来衡量）的性能变化
    4.3. 大规模聚类
    大规模数据聚类处理关于由数以千计特征表示的有数以百万计数据点的数据集的聚类问题的挑战。表1展示了一些
    表1. 大规模数据聚类应用的例子
    基于内容的图像检索（CBIR）的目标是根据给定的查询图像检索出看上去相似的图像。虽然大概过去的15年
    图14.使用SIFT关键点表示的三个纹身。图（a）表示一对相似图像间有370个一致的关键点；图（b）
    另一方面，文本检索的应用要快很多。在Google大概只需要十分之一秒就能检索100亿的文档。一个图像
    能够有效处理大规模数据集的聚类算法已经开发了很多了。大部分这些研究可以被分成四类：
    (a)有效最近邻（NN）搜索：在任何聚类算法中的一个基本操作是确定每个数据点的簇身份，而这需
    (b)数据概括：它的目标是通过先将大数据集概括为相对小的子集，然后应用聚类算法对概括后的数据
    (c)分布式计算：这一类方法（Dhillon和Modha，1999）将数据聚类算法的每个步骤
    (d)增量聚类：这类算法，比如（Bradley et al.,1998）设计对数据进行单次扫
    (e)基于抽样的方法：像CURE（Guha et al.,1998;Kollios et a
    4.4. 多方式聚类
    被用来聚类的对象或者实体往往是相关的不同成分的一个组合。比如，一个文档是由字、标题、作者和引文等组成
    共同聚类（Hartigan，1972；Mirkin，1996）试图对数据实体和特征同时进行聚类（或者
    共同聚类框架被拓展到多方式聚类（Bekkerman et al.,2005），通过聚类对象集的同时也
    4.5. 异构数据
    在传统的模式识别设定中，一个特征向量由一个对象的不同特性的衡量组成。对几种类型的数据来说这种对象的表
    排名数据：考虑不同的人对n部电影排名所生成的数据集，n个对象中只有一些被排名了。任务是聚类排名相似的
    动态数据：动态数据和静态数据相反，比如博客、网页等会随着时间进程而发生改变。当数据修改之后，聚类结果
    图数据：有些对象，比如说化合物、蛋白质结构等可以非常自然的用图来表示。很多最初的关于图聚类的工作专注
    关系型数据：另一个吸引大量兴趣的方面是聚类关系型（网络）数据。不像以划分图集为不相交的组为目的的聚类
    5. 总结
    对数据进行合理的分组问题很自然的出现在很多科学领域。因此见证数据聚类的不断流行并不令人惊讶。记住聚类
    聚类在数据分析领域有许多成功的案例。尽管如此，机器学习和模式识别领域还需要处理许多问题，用于提高我们
    (a)研究群体需要可用的一系列基准数据（有地面事实的）来测试评估聚类方法。基准数据应该来自不
    (b)我们需要聚类算法和应用需要之间更加紧密的整合。比如，有些应用只需要产生一些紧密结合的簇
    (c)无论原则（或目标），大部分聚类方法最后都转化为组合优化问题，它的目的是找到优化目标的数
    (d)关于聚类的一个基本问题是它的稳定性和一致性。一个好的聚类原则应该使得在数据中有扰动情况
    (e)根据对已有公设的满足来选择聚类原则。尽管有Kleinberg的不可能理论，有些研究已经
    (f)考虑到聚类本身的困难，这使得开发半监督聚类算法变得更有意义。它可以使用有标识的数据和（
    致谢
    我要感谢国家科学基金和海军研究办公室对我关于数据聚类、降维、分类和半监督学习的研究工作的支持。我要感
    参考文献
    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 个分组使得在同一个分组中的对象间相似度高而处于不同分组
    中的对象间相似度低。但是，相似度的定义是什么？簇的定义又是什么？图 2 表明簇的形状、大小和密度可以是不同的。数据集中存在的噪声使得发现簇更加 的困难。一个理想的簇可以被定义为一系列紧凑的、孤立的点集。事实上，从一 个观看者的角度来看，一个簇是一个主观的实体，它的重要性和解释需要相应领 域的知识。虽然人类本身是二维可能三维数据中簇的出色探求者，但是我们需要 自动化算法来处理高维数据。聚类时因为不知道所给定数据到底可以分成几个 簇，导致了数以千计的聚类算法的出现和将继续出现。 2.1. 为什么要聚类？ 在任何涉及多变量数据分析的学科中聚类分析都是很普遍的。通过谷歌学术 搜索引擎（2009）搜索关键词 “数据聚类”仅仅出现在 2007 年的就有 1660 个 条目。如此大量的文献足以说明聚类在数据分析中的地位。很难一一列举聚类方 法在众多科学领域和应用领域的使用，同样，也很难一一列举已经发表的数以千 计的聚类算法。图像分割作为计算机视觉中的一个重要问题可以表示为一个聚类 问题（Jain 和 Flynn，1996；Frigui 和 Krishnapuram，1999；Shi 和 Malik，2000）。 文档可以被聚类（Iwayama 和 Tokunaga，1995）为几个有效信息访问或检索的 局部层次结构（Bhatia 和 Deogun，1998）。聚类被用来将顾客聚群为不同的类 型以便进行有效的营销（Arabie 和 Hubert，1994）；被用来聚群服务提供协议以 便进行劳动力管理和规划（Hu et al.,2007）；还被用来研究生物学中的基因组信 息（Baldi 和 Hatfield，2002）。 数据聚类主要被用在以下三个地方： (a)构造底层结构：获得对数据的深入了解，产生假设，侦测异常，识别特征。 (b)自然分类：识别形式或生物间的相似程度（系统发育关系）。 (c)压缩：通过聚类原型作为一种组织和概括数据的方法。 图 3 是类别发现的一个例子。这里聚类被用在一个在线手写字符识别应用程 序中来发现不同的子类（Connell 和 Jain，2002）。不同的用户会用不同的方式 写同一个数字，所以要适当增加类内差异。在一个类中聚类训练模式可以发现新 的子类，叫做手写字符的词位。使用基于不同子类的多重模型而不是每个字符的 单一模型可以用来提高识别的准确率（见图 3）。
    图 3. 使用数据聚类找到子簇。图（a）和（b）以两种不同的方式写数字 2；图（c）是 字符‘f’的三种不同的子类；图（d）是字母‘y’的三种不同子类。 给定大量的英特网上的网页，很多查询词条会典型的返回大量的网页可点击 数。这产生了对组织搜索结果的需要。像 Clusty（www.clusty.org）这样的搜索 引擎聚类了搜索结果，并将一个更加有序的结果呈现给用户。 2.2. 历史发展 聚类方法的发展确实是多学科共同努力的结果。分类学家、社会科学家、心 理学家、生物学家、统计学家、数学家、工程师、计算机科学家、医学研究者以 及其他收集和处理真实数据的人都为聚类方法做出了贡献。根据 JSTOR（2009）， 数据聚类第一次出现是在 1954 年发表的一篇处理人类学数据的文章的标题中。 数据聚类根据不同的的应用领域也被叫做 Q 分析、类型学、聚丛、分类学（Jain 和 Dubes，1988）。目前有几本关于数据聚类的书，经典的是由 Sokal 和 Sneath （1963）、Anderberg（1973）、Hartigan（1975）、Jain 和 Dubes（1988）和 Duda et al.(2001)写的。数据挖掘领域也广泛研究了聚类算法（参见 Han 和 Kamber （2000）和 Tan et al.(2005)写的书以及《机器学习》（Bishop，2006））。 聚类算法可以粗略的分为两组：基于层次的和基于划分的。基于层次的聚类 算法使用凝聚的模式（从将每个数据点作为一个簇开始相继的融合最相似的一对 簇为一个新的簇层）或者分裂（自顶向下）的模式（从将所有数据点作为一个簇 开始递归的分裂每个簇为一个更小的簇）递归的找到嵌套的簇。和基于层次的聚 类算法相比，基于划分的算法找到所有的簇的同时也找到了数据的一个划分而且 并不使用层级结构。基于层次的算法的输入是一个 n*n 的相似度矩阵，期中 n
    是用于聚类的数据对象的数量。另一方面，基于划分的算法既可以使用 n*d 的模 式矩阵，期中 n 是表示有 d 维特征空间的 n 个对象，也可以使用相似度矩阵。值 得注意的是相似度矩阵可以很容易的由模式矩阵导出，但是要从相似度矩阵中导 出模式矩阵就要使用像多维定标（MDS）这样的定标方法。 最著名的基于层次的算法是单一连接和完全链接；最受欢迎也最简单的基于 划分的算法是 K-means。由于可用数据本身的性质决定基于划分的算法在模式识 别中更加受欢迎，我们在这里主要讨论这类算法。K-means 自从在不同的科学领 域中由 Steinhaus（1956）、Lloyd（1957 年提出，1982 年发表）、Ball 和 Hall （1965）以及 MacQueen（1967）独立的发现以来，已经有了丰富而多样的历史。 即使 K-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 和点之间的平方误差定义为  2 J c  。  u    x i k k x i c  k K-means 的目标是使得所有 K 个聚类中平方误差的和  J C   K    k 1 i x  c  k x i  u k 2  最 小。最小化这个目标函数是一个 NP 困难问题（即使 K=2）（Drineas et al.,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）表示了用 作簇中心的三个种子点以及数据点的初始簇分配。图（c）和（d）表示簇标和簇中心的中间 迭代。图（e）表示 K-means 收敛最后得到的聚类结果。 2.4. K-means 的参数 K-means 算法需要用户确定三个参数：类的数目 K、类的初始化、距离尺度。 其中最重要的参数是 K。因为目前还没有准确的数学标准存在，可以选择已有的 许多试探性求解（见 Tibshirani et al.，2001）K 的方法。一般来说，K-means 在 不同的 K 下会独立的运行，并产生不同的划分，对于领域专家来说最有意义的 那种划分就会被选择。因为 K-means 只能收敛于局部最优解，不同的初始化会产 生不同的聚类结果。一种寻找全局最优解的方法是在一个给定的 K 下，使用不 同的初始划分多次运行 K-means 算法，然后选择平方误差最小的划分。 K-means 一般会选择欧几里得距离作为距离尺度来计算点和簇中心之间的 距离。因此 K-means 找到的是数据中球面和球体的簇。K-means 利用马氏距离可 以被用来寻找超椭球体的簇（Mao 和 Jain，1996），但是这需要更大量的计算 花费。一个 K-means 的变体使用板仓距离来处理在语音处理中的矢量量化问题
    （Linde et al.，1980）。L1 距离被建议用来为 K-means 开发 Bregman 距离族 （Kashima et al.,2008.Banerjee et al.2004）。 2.5. K-means 的扩展 基础的 K-means 算法已经被很多不同的方式扩充了。有些扩充使用额外的试 探性方法处理簇尺寸最小化，合并和分离簇。在模式识别文献中的两个有名的 K-means 变体是 ISODATA(Ball 和 Hall，1965)和 FORGY（Forgy，1965）。在 K-means 中，每个数据点被分配到一个单一簇中（叫做硬分配）。由 Dunn（1973） 提出，并由 Bezdek（1981）改进的模糊 c-means，作为 K-means 的一个拓展，它 的每个数据点可以是多个簇的成员（软分配），其中用成员值加以区分。一个好 的可供使用的关于基于模糊的聚类综述是（Backer，1978）。在聚类之前，通过 用分组数据的中心代替原来的数据可以加速 K-means 和模糊 c-means（Eschrich et al.,2003）。下面概括 K-means 的其它重要的修正算法：Steinbach et al.(2000)提 出了一种 K-means 的层次分裂版本，叫做二等分 K-means，它每一步迭代划分数 据为两个簇。在（Pelleg 和 Moore，1999）中，kd 树被用来处理 K-means 的核心 步骤，即有效的识别所有数据点中最近的簇中心。Bradlry et al.(1998)提出了 K-means 的一个快速可伸缩单次扫描版本，它不需要所有的数据同时适合内存。 X-means（Pelleg 和 Moore，2000）可以通过优化比如 AIC 或 BIC 这样的准则自 动化的找到 K。在 K-medoids（Kaufman 和 Rousseeuw，2005）中，由数据的中 位数代替均值表示簇。核心 K-means（Scholkopf et al.,1998）被提出来通过选择 核心相似度函数用于发现任意形状的簇。值得注意的是所有这些拓展都要增加由 用户确定的算法附加参数。 2.6. 聚类的主要方法 就像之前提到的一样，在很多不同的学科的文献中提出了数以千计的聚类算 法。这使得回顾所有这些已经发表的方法变得非常困难。好在，聚类算法的主要 差异是在目标函数的选择、概率生成模型和试探法三个方面。我们将简要回顾一 些主要的方法。 簇可以被定义为在特征空间中由低密度区域分开的高密度区域。算法根据这
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料