毕业论文移动版

除了词聚类，还有许多类似的聚类方式，包括自动分类、数值分类和类型分 析等。“集群”的概念没有精确的定义，这也是为什么有那么多的聚类算法，但 是都有一个共同点：对一组数据对象的处理。然而，根据实际的需要，不同的研 究者采用不同的聚类模型，并为这些每个簇模型给出不同的算法。“集群”的概 念不同，通过不同的算法，其性能有些显著的差异，而了解这些集群模型的关键

在于理解各种算法之间的差异。其典型的集群模型有：基于连通性的聚类模型， 基于划分的聚类模型，基于分布的聚类模型和基于密度的聚类模型等。

1.1.2 基于连通性的聚类模型

基于连通性的聚类模型，也被称为分层聚类，其核心理念在于每个物体与其 附近的物体联系比与其远处的物体关系更为紧密[27]。这些算法根据对象的距离 将“对象”连接到形成“聚类”，一个集群可以尽可能大的表述为需要连接聚类 各个部分的最大距离，根据不同的距离，会形成不同的聚类结果，它可以用一个 树状图来表示，也说明了“分层聚类”名字的由来：这些算法不提供一个单独的 数据集合集群，而是提供一个聚类间的广泛的层次结构来相互合并到一定的距离。

例如，假设图 1.1 所表示的数据被聚集，以欧式距离作为距离度量，其层次

聚类树状图由图 1.2 来表示。

起始时我们有 6 个元素{a}~{f}，我们每一步都是选择比较相近的两个元素

将它们聚集为 1 类，不难发现，最开始的时候{b}和{c}相距比较近，{d}和{e} 相距比较近，于是聚集出了{bc}和{de}，随后再将{f}聚集到{de}中形成{def}， 继而又可以得到{bcdef}，最后再与最远的{a}聚集起来，形成了{abcdef}的大集 合，聚类过程以一个树状图的形式完整表现出来了。

1.1.3 基于划分的聚类模型

在基于划分的聚类模型中，最主要用到的算法就是 K-means 算法，也是本文 研究的聚类算法[2]，集群由中心向量来表示，这个中心向量可能不是原数据集 中第一个元素。当确定集群的数目是 K 的时候，K-means 聚类给出了优化解决此 问题的正式定义：找到 K 个聚类中心并且把所有的元素分配给其最近的聚类中心， 也就是所有点到其聚类的距离的平方和最小。

这个问题的本身实际上是一个 NP 难问题，因此，常用的方法是只搜索出近 似解，K-means 算法就是解决这个问题的一个方法，然而它只能找到一个局部最 优解，所以通常情况下，让它以不同的随机初始化的点集运算多次，然后选择多 次运行中最佳的结果。

K-means 有一些有趣的理论特性。一方面，它将数据空间划分为结构图，称 为 Voronoi 图，另一方面，在概念上与最近邻分类比较接近，第三方面，它可以 被看作是一个变化的基于分类的模型。

1.1.4 基于分布的聚类模型

与统计最密切相关的聚类模型是基于分布的聚类模型。集群可以很容易地被 定义为属于最有可能相同的分布对象[7]。这种方法的一个很好的特性是，这非 常类似于人工数据集的生成方式，它是由一个随机抽样的对象产生的分布。 虽然这些方法的理论基础是优秀的，但是他们有着一个很关键的问题，被称之为 过度拟合，除非约束模型的复杂度。在一个更复杂的模型数据的解释总是好的， 这很难使模型的复杂程度选择合适的。

一个突出的方法是高斯混合模型，其使用期望最大化算法。在这里，数据集 通常与一个固定数目的高斯分布来建模，选择随机的初始化和参数来进行迭代优 化，以更好地适应数据集。结果将会收敛到局部最优，所以多次运行可能产生不 同的结果，对象将分配给他们最有可能属于的高斯分布来获得硬聚类；软聚类的 计算则没有必要了。 (责任编辑：qin)