【毕业论文】基于文本的聚类算法

摘要

聚类作为一种知识发现的重要方法，它广泛地与中文信息处理技术相结合，应用于网络信息处理中以满足用户快捷地从互联网获得自己需要的信息资源。文本聚类是聚类问题在文本挖掘中的有效应用，它根据文本数据的不同特征，按照文本间的相似性，将其分为不同的文本簇。其目的是要使同一类别的文本间的相似度尽可能大，而不同类别的文本间的相似度尽可能的小。整个聚类过程无需指导，事先对数据结构未知，是一种典型的无监督分类。

本文首先介绍了文本聚类的相关的技术，包括文本聚类的过程，文本表示模型，相似度计算及常见聚类算法。本文主要研究的聚类主要方法是k-均值和SOM 算法，介绍了两种算法的基本思想和实现步骤，并分析两种算法的聚类效果。同时介绍了两种算法的改进算法。

关键词：文本聚类聚类方法K-MEAN SOM

Abstract

Clustering as an important knowledge discovery method, which extensively with Chinese information processing technology, used in network information processing to meet the users to quickly access from the Internet, the information resources they need. Text clustering is a clustering problem in the effective application of text mining, which according to the different characteristics of text data, according to the similarity between the text, the text will be divided into different clusters. The aim is to make the same class as large as possible the similarity between the text, and different types of text as small as possible the similarity between. The clustering process without guidance, prior to the data structure is unknown, is a typical unsupervised classification.

This paper studies the effect of influencing factors that text clustering, text representation of the model such as the Boolean model, vector space model, probabilistic retrieval model and language model. Also studied the analysis of such text clustering algorithm: hierarchical clustering, agglomerative hierarchical clustering algorithm, hierarchical clustering algorithm to split and so on. Also studied the text clustering algorithm analysis and methods of improvement.

Key words：Text clustering clustering method k-mean som

目录

摘要 ........................................................................................................................... I Abstract .............................................................................................................................II 目录 ........................................................................................................................ III 第一章绪论 . (1)

1.1 课题研究的背景 (1)

1.2课题研究的意义 (2)

第二章文本聚类效果影响因素 (3)

2.1文本聚类过程 (3)

2.2文本表示模型 (4)

2.2.1布尔模型 (5)

2.2.2向量空间模型 (5)

2.3 文本相似度计算 (6)

2.4文本聚类算法 (8)

2.5本章小结 (11)

第三章 k-均值聚类算法 (12)

3.1 K-均值聚类算法的思想 (12)

3.1.1 K-均值聚类算法的基本思想 (12)

3.1.2 K-均值聚类算法的算法流程 (12)

3.1.3 K-均值算法的优缺点分析 (13)

3.1.4现有的对于K-均值聚类算法的改进 (15)

3.1.5现有基于初始中心点改进的K-均值聚类算法 (16)

3.2 本章小结 (17)

第四章 SOM聚类算法 (18)

4.1 SOM聚类算法的网络特性与基本流程 (18)

4.1.1 SOM网络的特性 (18)

4.1.2 SOM网络聚类的基本流程 (19)

4.1.3 SOM网络聚类的优点及存在的问题 (19)

4.2改进的SOM聚类方法 (20)

4.2.1已有的学习策略改进 (20)

4.2.2等离差理论在神经元获胜策略中的应用改进 (21)

4.2.3初始化连接权值 (22)

4.2.4已有的初始化连接权的方法 (22)

4.2.5新的确定初始权值的方法 (23)

4.3本章小结 (25)

参考文献 (26)

致谢 (28)

第一章绪论

1.1 课题研究的背景

随着Internet的迅猛发展，信息的爆炸式增加，信息超载问题变的越来越严重，信息的更新率也越来越高，用户在信息海洋里查找信息就像大海捞针一样。搜索引擎服务应运而生，在一定程度上满足了用户查找信息的需要。然而Internet 的深入发展和搜索引擎日趋庞大，进一步凸现出海量信息和人们获取所需信息能力的矛盾。那么，如何从中获取特定内容的信息和知识成为摆在人们面前的一道难题。面对互联网时代庞杂无序的海量信息，智能高效地处理和深层次综合利用信息离不开文本挖掘技术，国际上多个国家都抓紧投入文本挖掘技术的研究，以期能对“堆积如山”的信息进行有效的过滤，开发和利用，提取发现具有指导意义的知识。

文本挖掘是指从大量文本数据中抽取出事先未知的，可理解的，最终可用的信息或知识的过程，它涉及Web，计算机语言，数据挖掘，信息检索等多个领域，较大程度地解决了信息杂乱的现象，方便用户准确地定位所需的信息和信息分流。文本挖掘可以对大量文档集合的内容进行总结，结构分析，分类，聚类，关联分析，分布分析以及利用文档进行趋势预测等，目前已成为一项具有较大实用价值的关键技术，是组织和管理数据和知识的有力手段。

聚类作为一种只是发现的重要方法，是数据挖掘中一项重要的研究课题，它广泛地与中文信息处理技术相结合，应用于网络信息处理中以满足用户快捷地从互联网获得自己需要的信息资源，文本聚类则是聚类问题在文本挖掘中的有效应用，是文本挖掘的重要内容之一。文本聚类是根据文本数据的不同特征，按照事物间的相似性，将其划分为不同数据类的过程。其目的是使同一类别的文本间相似度尽可能大，而不同类别的文本间的相似度尽可能的小。在这一过程中无需指导，是一种典型的无需督分类，从而打破了在许多实际应用中由于缺少形成模式类别过程的知识，或者模式类别的形成非常困难时的挖掘局限性。

随着人们对聚类问题更加深入地了解和重视，国内外大量学者不断投身到该项目研究，聚类主要工作集中在寻找针对大型数据库的聚类方法和世界的聚类分析方法上，使得各种成果不断涌现，各个领域的聚类分析算法层出不穷。通过聚

类分析可以发现隐藏在数据集中的簇，标识出有意义的模式或分布。不同算法针对与不同规模的数据集而提出，而使用却不仅仅限于某些特定的环境。

1.2课题研究的意义

文本聚类分析在信息检索领域有相当长的研究历史，近年来在文本数据上的聚类分析研究和应用越来越受到关注。关于文本数据上的聚类分析研究，较早的综合性介绍可以追溯到C.J.van Rijsbergen在IR领域的经典书籍《InformationRetrieval》中提到的利用文本聚类分析技术来提高信息检索系统的准确率，但近年来此类研究已不多见。上个世纪90年代以来，文本的聚类分析技术研究更多地集中在对大规模的文档集合的浏览上在对用户提出的查询重新组织搜索引擎的查询结果的研究中利用聚类技术重新组织文档集合，用于文档集合的浏览，这是近年来文本聚类中一个广受关注的研究点，2004年SIGIR上MSRA推出的Search Result Clustering技术代表了此类应用研究目前最新的进展。在此类研究中，主要利用K-Means或者后缀树聚类算法的变种来实现其需求。文档聚类分析算法被用于自动产生文档集合的层次结构，比如用于产生类似Yahoo!的网页分类目录结构。近年来，文档聚类算法还在文档分析处理领域中一个新的应用方向话题检测与跟踪中得到了进一步研究与应用。话题检测中利用文档聚类算法从大量的文档中自动地抽取话题，应用于个性化信息服务或者情报分析。在这些应用的推动之下，文本数据上的聚类分析算法层出不穷，各说各的好处，在我们的工程实践中具体该采用哪种算法，如何设计文本聚类算法并对其进行评价都是难以解决的问题。由于算法种类众多，文本聚类算法间缺乏一个进行横向比较与分析的机制，在工程实践中对算法的选择及参数的设定都是经验性的，这对进一步开展研究以及科学地设计算法、分析算法造成了困难。因此，需要对文本聚类分析结果的质量进行评价，利用这种评价机制来指导算法设计、算法选择、算法效能分析、参数优化等。有了文本聚类分析的科学评价机制，我们未来的工作就有据可依，可以更科学地选择算法，分析、设计算法。

第二章文本聚类效果影响因素

2.1文本聚类过程

影响文本聚类分析效果的因素是多方面的，文本聚类分析全过程中的每个步骤都有可能对聚类结果造成影响。下面通过简要描述聚类分析过程来说明对结果可能造成影响的各种因素,如图2-1所示:

图2-1 聚类流程

聚类分析过程分成三个步骤，通过这三个步骤可以找到影响聚类分析效果四个方面的因素。聚类流程三个步骤的实际处理内容为：

(1)文本聚类分析首先将文本表示成机器可计算的形式。不论是抽取文本特征形成一个向量还是抽取文本特征形成一个特殊的结构，对文本的这种机器表示过程简称为文本表示。文本表示过程显然需要领域知识参与，文本中哪些因素可以构成特征，特征中哪些在聚类中可用以及如何使用是文本聚类第一步骤文本表示考察的内容；

(2)文本聚类分析的第二个步骤是算法。不同的算法有不同的特性，对相同的数据输入，不同的算法会产生出不同的聚类结果。聚类分析算法可以从不同的角度进行比较，比如是否产生层次聚类结构、是否需要参数、是否能够产生模糊聚类、能否识别出不规则形状的簇等等。目前在文献中出现的聚类分析算法数目众多，但在文本数据上效果孰优孰劣仍没有得到有效的研究。这个步骤中算法的时空效率、聚类结果质量是研发中选择算法的主要标准。该步骤还有一个关键因素就是对象距离(或者相似度)如何定义；

(3)第三个步骤是算法中参数的选择。不同的算法对参数的敏感性不同，但是基本上参数的好坏对结果的影响都比较显著。从这三个步骤可以看出影响文本聚类分析效果的因素包括四个方面：文本表示模型、距离度量方法、算法模型和参数优化。参数的设定主观性比较强，如何设定才是一个好的参数缺乏有效的方法，利用本文中实现的聚类算法包和聚类评价方法可以通过指标的变化曲线图寻找算法的最佳参数。

2.2文本表示模型

在实际的文本聚类分析研究，将实际文本内容变成机器内部表示结构的方法多种多样，可以用词、字、短语、n-Gram、显著性短语等形成向量、树等结构。在经典的研究中通常利用特征(Term，包括字、词、词组等)的词频信息建立文本向量，通过文本向量与文本向量之间的相似度来进行聚类分析。

文本表示包括两个问题：表示与计算。表示特指特征的提取，计算指权重的定义和语义相似度的定义。特征提取包括特征的定义和筛选，特征定义和筛选考虑以什么作为文本的特征，并不是所有的词和字都要求或者可以成为特征。特征的权重定义及特征结构上的相似度度量可以选取不同的模型，如向量空间模型、概率模型、语言模型等。文本表示是文本聚类的第一步，该步骤的变化很多，对最终聚类效果的影响也不尽相同。文本表示本质上是对原始文本进行转换，使之在机器上可形式化描述、可计算。特征定义与筛选可以采用不同的特征选择方法，可利用N-Gram、PAT树提取特征、可利用LSI降维转化特征、也可利用语义词典

WordNet或者HowNet定义更复杂的特征结构。关于特征定义与筛选可以参考自然语言处理领域中的相关研究，这里不详细介绍。本节接下来主要介绍信息检索和文本分析处理中经常用到的几个检索模型，这几个检索模型根据不同的理论假设推导、定义了不同的特征权重计算方法与语义相似度计算方法，是文本表示模型的重要组成部分。

2.2.1布尔模型

布尔模型是基于集合论与布尔代数之上的一种简单模型，主要应用于信息检索中。在布尔模型中，一个文档表示成文档中出现的特征的集合，也可以表示成为特征空间上的一个向量，向量中每个分量权重为0或者1，这种布尔模型称为经典布尔模型。经典布尔模型中查询与文档的相关性只能是0或者1，满足查询query中的所有逻辑表达式的文档被判定相关，不满足的被判定为不相关。经典布尔模型只能用于信息检索中计算用户查询与文档的相关性，而无法利用该模型计算两个文档更深层面的相似度，无法在更多的文本处理应用中使用。在经典布尔模型基础上，研究人员又提出了扩展布尔模型(Extended Boolean Approach)，重新定义了And与Or操作符成为多元操作符，使相关性可以成为[0,1]之间的数。

2.2.2向量空间模型

Salton教授提出的向量空间模型简称VSM模型(Vector Space Model)，是信息检索领域中经典的检索模型。向量空间模型将文档表示成一个向量，向量的每一维表示一个特征，这个特征可以是一个字、一个词、一个n-gram或某个复杂的结构。通过对文档的解析处理可以得到这些特征。通常情况下用向量空间模型中的向量表示文档时，需要对文档进行切分(中文分词、英文通过词的分界符识别单词)、停用词处理、英文词的词形还原或者提取词干(Stemming)，经过若干个处理步骤后，基本上就可以得到一系列词，将这些词作为文档的特征。所有的这些词构成一个“空间”，每个词对应着空间中的一维。每个文档可以用文档中的词来表示，这些词及其对应的权重构成一个向量。文档对应特征空间中的一个向量，对应特征空间中的一个点。表2.1 说明VSM模型中文档与向量空间之间的映射关系。

表2.1 VSM模型中文档与向量空间之间的映射关系

2.3 文本相似度计算

文本相似度计算是自然语言处理、Web智能检索、文本分类和文本聚类研究中的一个基本问题。一个文本聚类分析过程的质量取决于对度量标准的选择。因此，在研究聚类算法之前，先要讨论其度量标准。文本相似度是用来衡量文本之间相似程度大小的一个统计量。文本相似度一般定义为界于0和1之间的一个值。如果两文本之间相似度为1，则说明这两个文本对象完全相同；反之，则说明两文本没有相似之处。

2.3.1样本间相似度

在向量空间模型中，文本相似性的度量方法很多，主要有内积法、Dice系数法、余弦法和距离度量法等。

1.内积法

通常在文本向量中，最常使用的相似度计算公式就是两个文本向量之间的“内积”运算，其定义为：

2.Dice系数法

3.余弦法

上述各公式中，Sim(di,dj)表示文本di和dj之间的相似程度，分W ki,W kj分别表示文本di和dj的第k个特征项的权重，n为文本特征项数。Sim值越大表示两个文本越相似，Sim越小则表示两个文本区别越大。

4.距离度量法

在文本相似度计算中，我们也可以用两个文本之间的距离来度量文本之间的相似程度。常使用的距离公式如下：

公式中，Dis(di,dj)表示文本向量di和dj在向量空间的距离，W ki,W kj分别表示文本的第k个特征项的权重，参数p决定了选择的是哪种距离计算。

(1)当p=1时

(2)当p=2时

这就是欧式距离，也就是向量空间中的直线距离。

2.3.2簇间相似度

在聚类分析中，我们还需要衡量类与类之间的相似度，实现类与类之间的合并或拆分。为了衡量文本集合之间的相似度，常见的方法有：最小距离、最大距离、平均距离、质心法、离差平方和等。

2.4文本聚类算法

聚类分析作为一个活跃的研究领域，已经出现了很多聚类算法，总体上聚类算法可分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法等。每种算法都有各自的优缺点，都有其适用的领域，并不是每一类算法都适合于文本聚类，我们必须根据文本数据的特点对聚类算法进行分析选择。

2.4.1基于划分的方法

基于划分的聚类算法（Partitioning Method）是文本聚类应用中最为普遍的算法。方法将数据集合分成若干个子集，它根据设定的划分数目k选出k个初始聚类中心，得到一个初始划分，然后采用迭代重定位技术，反复在k个簇之间重新计算每个簇的聚类中心，并重新分配每个簇中的对象，以改进划分的质量。使得到的划分满足“簇内相似度高，簇间相似度小”的聚类原则。典型的划分聚类方法有k-means算法[36]和k-medoids算法，两者的区别在于簇代表点的计算方法不同。前者使用所有点的均值来代表簇，后者则采用类中某个数据对象来代表簇。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，各类改进的划分算法逐渐增多。

基于划分方法的优点是运行速度快，但该方法必须事先确定k的取值。算法容易局部收敛，且不同的初始聚类中心选取对聚类结果影响较大。为此，应用最广泛的k-means算法有很多变种，他们可能在初始k个聚类中心的选择、相似度的计算和计算聚类中心等策略上有所不同，最终实现聚类结果改进的目标。

2.4.2基于层次的方法

基于层次的聚类算法（Hierarchical Method）又叫“分级聚类算法”或“树聚类”，它通过分解给定的数据对象集来创建一个层次。这种聚类方法有两种基本的技术途径：一是先把每个对象看作一个簇，然后逐步对簇进行合并，直到所有对象合为一个簇，或满足一定条件为止；二是把所有对象看成一类，根据一些规则不断选择一个簇进行分解，直到满足一些预定的条件，如类的数目达到了预定

值，或两个最近簇的距离达到阈值等。前者称为自下而上的凝聚式聚类，后者称为自上而下的分裂式聚类。

在文本聚类中，最常见的是凝聚的层次聚类算法。使用该算法可以得到较好的聚类结果，而且该方法无需用户输入参数；但是层次聚类算法的时间复杂度比较高，达到了O(n2)，对于大规模的文本集合，有其不适用性。此外，在层次聚类算法中，一旦两个簇在凝聚和分裂后，这个过程将不能被撤销，簇之间也不能交换对象。如果某一步没有很好的选择要凝聚或者分裂的簇，将会导致低质量的聚类结果。

2.4.3基于密度的方法

绝大多数划分算法都是基于对象之间的距离进行聚类，这类方法只能发现圆形或球状的簇，较难发现任意形状的簇。为此，提出了基于密度的聚类算法（Density-Based Clustering Method），其主要思想是：只要邻近区域的对象或数据点的数目超过某个阈值，就继续聚类。即对给定类中的每个数据点，在一个给定范围的区域中至少包含某个数目的点，这样就能很好的过滤掉“噪声”数据，发现任意形状的簇。其基本出发点是，寻找低密度区域分离的高密度区域。具有代表性的方法是DBSCAN（Density Based Spatial Clustering of Applications with Noise），它是将密度足够大的那部分记录组成类，可以在带有“噪声”的空间数据库中发现任意形状的聚类，但它需要用户主观来选择参数，从而影响了最终的聚类结果。

基于密度的聚类算法在当前的文献中较少被用于文本聚类中。这是由于文本间的相似度不稳定，同属一簇的文本，有些文本间的相似度较高，所以密度高；有些相似度较低，所以密度低。如果根据全局的密度参数进行判断，显然是不适合的。并且密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。

2.4.4基于网格的方法

基于网格的算法（Grid-Based Clustering Method）把对象空间量化为有限数目的单元，形成了一个网络结构。所用的聚类操作都在整个网络结构即量化的空间

上进行。这种方法的一个突出的优点就是处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中的每一维的单元数目有关。此外，它还可以处理高维数据。代表算法有统计信息网格法STING算法、聚类高维空间法CLIQUE算法、基于小波变换的聚类法WAVE-CLUSTER算法。

STING（Statistical Information Grid），利用了存储在网格中的统计信息，它不但能并行处理且能增量更新，因而效率很高，缺点是簇的质量和精确性欠佳。

WaveCluster（Clustering Using Wavelet Transformation）是一种多分辨率的聚类算法。其主要优点是能有效地处理大规模数据集；能发现任意形状的簇；能成功地处理孤立点；对于输入的顺序不敏感；不要求指定任何参数；且效率和聚类质量都比较高。

CLIQUE（Clustering in Quest）是一种将基于密度的方法与基于网格的方法相结合的算法，能有效处理大型数据库的高维数据。它对输入顺序不敏感，无需假设任何规范的数据分布。另外，它还具有良好的可伸缩性。但由于方法大大简化，聚类结果的精确可能降低。

2.4.5基于模型的方法

基于模型的算法（Model-Based Clustering Method）试图优化给定的数据和某些数学模型之间的适应性。这样的算法经常是基于这样的假设，数据是根据潜在的概率分布生成的。它通过为每个聚类假设一个模型来发现符合相应模型的数据对象。根据标准统计方法并综合考虑“噪声”或异常数据，该方法可以自动确定聚类个数，从而得到鲁棒性较好的聚类方法。基于模型的算法主要有两类，分别为统计学方法和神经网络方法。

大多数的概念聚类采用的是统计的方法，即在决定一个类时，用可能性的描述语句，典型的代表就是COBWEB，它是一个通用且简单的聚类方法。基于神经网络的聚类方法是将每一个类看作一个标本，它是这个类型的“典型”，但不需要和某个具体的对象或例子相对应。根据新对象和这个标本之间的距离，就可以将这个对象进行分类了。如基于SOM的文档聚类方法在数字图书馆等领域得到了较好的应用。聚类分析算法众多，应用于文档的聚类分析算法也种类繁多，

如何评价文档聚类分析的效果，目前还没有一个确定的说法。在实际的应用中一般都是实现几种算法，然后用人工判断的方法去选择合适的算法以及算法相对应的参数。这么多的算法虽然带来了更多的选择，但同时也带来了应用上的困难，因此有必要在一个统一的尺度上来衡量一些算法并对他们做出评价。

2.5本章小结

本章主要介绍了影响文本聚类结果的三方面主要因素：文本表示模型、相似度计算方法及聚类算法。文本聚类过程中每个步骤都有可能影响最终的聚类效果，各方面因素变化情形众多，在实际研究和工程应用中，聚类评价工作困难重重。为了更好地评价聚类结果，我们在下一章将详细介绍已有的文本聚类评价方法，比较各自的优缺点。

第三章 k-均值聚类算法

3.1 K-均值聚类算法的思想

3.1.1 K-均值聚类算法的基本思想

一九六七年，麦克奎因[B. Mac Queen]提出了K-均值聚类算法，用来处理数据聚类的问题，该种算法由于其算法简便，又很早提出，因此在科学和工业领域的应用中影响力极为广泛。该算法首先随机选取k个数据点作为n个簇的初始簇中心，集合中每个数据点被划分到与其距离最近的簇中心所在的类簇之中，形成了k个聚类的初始分布。对分配完的每一个类簇计算新的簇中心，然后继续进行数据分配过程，这样迭代若干次后，若簇中心不再发生变化，则说明数据对象全部分配到自己所在的类簇中，聚类准则函数收敛，否则继续进行迭代过程，直至收敛。这里的聚类准则函数一般采用聚类误差平方和准则函数。本算法的一个特点就是在每一次的迭代过程中都要对全体数据点的分配进行调整，然后重新计算簇中心，进入下一次的迭代过程，若在某一次迭代过程中，所有数据点的位置没有变化，相应的簇中心也没有变化，此时标志着聚类准则函数已经收敛，算法结束。

3.1.2 K-均值聚类算法的算法流程

原始的K-均值聚类算法:

输入:数据集x={x1，x2，……x n}，聚类数目k;

输出: k个类簇c j，j=1，2，……，k

[stepl]令I=1，随机选取k个数据点作为k个类簇的初始簇中心，m j(I) j=1，2，…，k;

[step2]计算每一个数据点与这k个簇中心的距离d(x i，m j，(i)), i=1，2，…n，j=1，2，…，k，,如果满足d(x i，m j(I))=min{d(x i， m j(I))，j=1，2，…，k}则xi cj.

[steP3]计算k个新的聚类中心

[step4]判断:若m j(i+1) m j(I)，j=1，2，…，k，则I=i+1，返回step2:否则，算法结束。

K-均值聚类算法在执行过程中还可以加入聚类准则函数来终止迭代过程，一般采用聚类误差平方和准则函数，即在上面算法流程中的step4中计算聚类误差平方和J，然后加入判断，若两次的J值没有明显变化，则说明J值已经收敛，结束算法，否则转入step2继续执行。具体流程如下:

[Stepl][初始化l随机指定k个聚类中心(m l，m2，……m k);

[Step2][分配xi]对每一个样本xi，，找到离它最近的聚类中心，并将其分配到该类:

[Step3][修正簇中心]重新计算各簇中心

[Step4][计算偏差]

[Step5][收敛判断]如果J值收敛，则return(m1， m2，……，mk)，算法终止;否则，转Step2。

从上面的算法思想及流程中可以看出，k个类簇的初始簇中心点的选取对聚类的最终结果至关重要，算法中，每一次迭代都把数据点划分到与其距离最近的簇中心所在的类簇中去，然后重新计算簇中心，进而反复迭代，直到每一个数据点都不再重新划分为止。

3.1.3 K-均值算法的优缺点分析

K-均值算法是一种基于划分的聚类算法，它通过不断的迭代过程来进行聚类，当算法收敛到一个结束条件时就终止迭代过程，输出聚类结果。由于其算法思想

简便，又容易实现，因此K-均值算法己成为一种目前最常用的聚类算法之一。然而K-means过分依赖于初始中心点的选取，且容易受噪音点的影响。为解决这一问题，出现了各种基于全局最优化思想的K-均值聚类方法，比如模拟退火算法、遗传算法等。然而这些技术并没有得到广泛认可，在许多实际应用中还是反复利用K-均值聚类算法来解决问题。

K-均值聚类算法采用迭代式的过程对样本点进行分配来寻求最终的聚类结果，其终止条件是所有样本的位置不再变化，其迭代过程可以概括如下:(l)分配样本点，即对每个样本点，将其分配到与其距离最近的簇中心所在的类簇中;(2)重新计算簇中心，对于每一个重新分配后的类簇，重新计算其簇中心。和大多数的聚类算法一样，K-均值聚类算法也有其自身的局限，主要局限如下:

(1)K-均值聚类算法中的聚类数目即K值需要由用户预先给出。从K-均值聚类算法的算法流程中可以看出，K值作为一个需要预先确定的参数，在已知的前提下才能执行K-均值聚类算法，而在实际应用中，需要聚类的数据究竟要分成多少个类别，往往不是被用户所知的。当聚类数目不被人所知的情况下，人们往往需要结合其它算法来获取聚类数目，即K值。往往获取K值的代价要比K-均值聚类算法的代价大得多，因此K值的不确定性是K-均值聚类算法的一个很大的不足之处。

(2)K-均值聚类算法严重依赖于初始簇中心点的选取。K-均值聚类算法随机的选取K个初始簇中心点，并针对这K个簇中心点进行迭代运算，即重新分配数据点和重新计算簇中心的运算，直到所有的数据点位置不再变化或聚类误差准则函数不再变化。这样就导致了K-均值聚类算法对初始簇中心点的严重依赖性。初始簇中心点选取不当很容易造成聚类结果陷入局部最优解甚至或导致错误的聚类结果。

(3)K-均值聚类算法的聚类结果容易受噪音点数据的影响。在K-均值聚类算法中，每次对于簇中心的重新计算，都是通过对每一个类簇中所有数据点求均值，这样，当数据集中存在噪音点数据时，均值点的计算将导致聚类中心(即簇中心偏离数据真正密集的区域，而趋向噪音点数据歹这样导致聚类结果的不准确。因此，当数据集中存在远离所有数据点的噪音点时，聚类结果将很大程度上受这些噪音点的影响，导致聚类结果的错误，所以K-均值聚类算法对噪声点和孤立点非常敏感。

(4)K-均值聚类算法无法发现任意形状的簇。K-均值聚类算法采用距离函数作为度量数据点间相似度的方法，这里的距离函数多采用欧氏距离，同时采用聚类误差平方和准则函数作为聚类准则函数，对于基于欧式距离的聚类算法而言，其只能发现数据点分布较均匀的类球状簇，对于聚类误差平方和准则函数而言，当类簇大小差别较大，形状较不规则时，容易造成对较大的类簇进行分割来达到目标函数取极小值的目的，因此容易造成错误的聚类结果。

(5)K-均值聚类算法不适用于大数据量的聚类问题。K-均值聚类算法每次迭代过程都要调整簇中心及重新分配数据点，因此，当数据量比较大的时候，这些迭代过程的计算量是相当大的，算法的时间开销也是巨大的，因此，由于需要大量的计算时间，因此K-均值聚类算法在待聚类数据量较大的时候并不适用。

3.1.4现有的对于K-均值聚类算法的改进

目前，对于K-均值聚类算法的改进主要集中在以下两个方面:

(1)初始聚类中心的选择K-均值聚类算法是一个迭代的求解最优解的问题，这里的最优解一般指的是目标函数(即聚类误差和准则函数)的最优解，是一个优化问题。然而，作为聚类误差和准则函数，通常存在一些局部最小点，目标函数的搜索方向总是沿着聚类误差和准则函数的递减方向进行，当初始簇中心不同时，搜索路径也会不同，而目标函数具有很多局部最优解，这样就存在着，当初始簇中心选取不当时，目标函数容易陷入局部最优解。而K-均值聚类算法采取随机选取初始簇中心点，这样，初始中心点的不同或数据输入顺序的不同都有可能导致聚类结果的不稳定性，且无法得到全局最优解而陷入局部最优解。

(2)K值的确定问题K-均值聚类算法中，K值是由用户预先确定的，而在实际应用中，这个K值很难直接确定，尤其是当数据量较大时，K值的确定问题将成为K一均值聚类算法的一个很大的困难，因为在多数情况下人们并不能提前预知数据的分布情况及分类情况。而K-均值聚类算法的聚类结果受K值的影响，K值不同时，聚类结果往往也随着不同，很多方法是通过试探K值来达到获取K值的目的，而在数据量较大时，这种方法并不行得通，需要大量的时间代价，因此，为了得到确定的聚类结果，K值的确定显得尤为重要。因此，在无监督情况下，通过某种学习方法得到合适的K值是很有必要的。

基于K-均值聚类算法的改进，国内外的专家学者做了大量的研究工作，主要

总结如下。

3.1.5现有基于初始中心点改进的K-均值聚类算法

目前的K-均值聚类算法中，对于初始聚类中心点的选取方法主要总结如下:

(1)随机选取k个样本作为初始聚类中心，由于是最早提出的这种选择初始聚类中心点的方法，因此在后来的很多文献中把这种随机选择初始聚类中心的方法称为FA(ForgyAPProach)。

(2)按最大最小距离聚类法中寻找聚类中心的方法来确定K-均值聚类算法

中的初始聚类中心。

(3)将全部样本以某种规则直观的分成k类，分别计算每一类的均值点作为

K-均值聚类算法的初始聚类中心。

(4)采用基于数据采样的方法。分别选取K组采样数据分别执行K-均值聚

类算法，然后选择聚类结果最好的一组聚类中心作为算法的初始聚类中心点。

(5)通过“密度法”选择代表点作为初始聚类中心。这里所指的密度是指样本点分布的密集情况，描述为，对于所有的样本，、将每个样本点假设为中心，设定一个半径，则落入这个半径所在圆内的所有样本点的数目即为该样本点的密度值，在计算完所有样本点的密度值后，选取最大密度值的样本点作为第一个初始聚类中心，然后将该样本点及其半径所在圆内的数据点去除后，重新设定半径选取下一个初始中心点，以此类推，直到得到K个初始中心点。

(6)聚类问题解出k类问题的中心。算法思路如下:先将全部样本点看成是一个类簇的聚类问题，执行K-均值聚类算法后得到的簇中心即为一个类簇的聚类问题的最佳解，然后选取与现有簇中心距离最远的点作为下一个类簇的初始簇中心，以此类推，确定出K个类簇的初始聚类中心。

(7)进行多次初始值的选择、聚类、找出一组最优的聚类结果。

(8)采用遗传算法或者免疫规划方法lv1进行混合聚类。除了以上列出的初始中心点的选取方法以外，还有很多对K-均值聚类算法的初始中心点的改进算法，在这里由于篇幅的关系我们没有一一列出。