下载文档原格式
kmeans聚类优化方法
K均值（K-means）聚类是一种常用的无监督学习方法，用于将数据点分成不同的组或簇。
在K均值聚类中，首先需要选择簇的数量K，然后算法会尝试将数据点分成K个簇，使得每个数据点都属于离它最近的簇。
这一过程是通过最小化数据点与其所属簇中心之间的距离来实现的。
然而，K均值聚类也存在一些局限性和优化方法。
首先，K均值对初始簇中心的选择非常敏感，不同的初始簇中心可能导致不同的聚类结果。
因此，为了优化K均值聚类，可以采用多次随机初始化簇中心的方法，然后选择最优的聚类结果。
另外，K均值对异常值和噪声敏感，这可能会导致聚类结果不稳定。
为了解决这个问题，可以采用基于密度的聚类方法，如DBSCAN（基于密度的空间聚类应用噪声）来优化K均值聚类。
DBSCAN可以有效地处理异常值和噪声，同时不需要预先指定簇的数量。
此外，K均值聚类还存在簇形状不规则、大小不平衡等问题。
针对这些问题，可以考虑使用层次聚类或者基于密度的聚类方法，
这些方法可以更好地处理不规则形状的簇和大小不平衡的数据。
最后，K均值聚类还可以通过加入权重、使用不同的距离度量、采用核方法等方式进行优化，以适应不同类型的数据和应用场景。
总之，K均值聚类是一种常用的聚类方法，但在实际应用中需
要考虑到其局限性，并结合其他方法进行优化，以获得更稳定、准
确的聚类结果。
kmeans++聚类算法步骤K-means++是一种改进的K-means聚类算法，其主要目的是为了解决K-means算法在初始化质心时的随机性，以避免陷入局部最优解。
以下是K-means++的步骤：1.选择初始质心：在开始时，算法随机选择一个点作为第一个质心。
然后，在选择下一个质心时，算法会考虑所有未被选为质心的点，并选择一个使聚类结果尽可能好的点作为质心。
具体来说，算法计算每个点的"代价"，这取决于该点与已选质心的距离。
然后，选择具有最小代价的点作为下一个质心。
这个过程重复k次，直到选择了k个质心。
2.分配数据点到最近的质心：一旦确定了k个质心，每个数据点被分配到最近的质心所代表的聚类中。
3.重新计算质心：对于每个聚类，新的质心被计算为该聚类中所有点的平均值。
4.迭代：步骤2和步骤3重复进行，直到质心不再发生显著变化或者达到预设的最大迭代次数。
这种改进使得K-means++在许多情况下都比传统的K-means更稳定，并且通常能找到更好的聚类结果。
然而，由于它需要更多的计算和存储，所以在大数据集上可能比K-means慢。
K-means++聚类算法适用于需要找到紧凑、分离良好的聚类的场景。
具体来说，以下是一些可能适用的场景：1.特征维度为数值型的数据聚类：该算法适用于对数值型特征进行聚类的任务，例如市场分析、金融分析、社交网络分析等领域。
2.文本聚类：在文本聚类中，可以将文本数据转换为数值矩阵，然后使用K-means++算法进行聚类。
例如，可以将新闻网站上的相同话题的新闻聚集在一起，并自动生成一个个不同话题的新闻专栏。
3.图像分割：在图像分割中，可以使用K-means++算法将图像中的像素划分为不同的区域，以便更好地识别和理解图像。
4.市场细分：市场细分是指将整个市场划分为不同的细分市场，以满足不同消费者的需求。
K-means++算法可以根据消费者的行为、兴趣和偏好将消费者划分为不同的群体。
聚类算法：K-Means和DBSCAN的比较K-Means和DBSCAN是两种常见的聚类算法，它们在数据挖掘和机器学习领域具有重要的应用价值。
本文将比较这两种算法的优缺点、适用场景等方面，以期帮助读者更好地理解它们的特点和区别。
1. K-Means算法K-Means算法是一种基于距离的聚类算法，它的基本思想是将数据集划分为K个簇，使得每个样本点都属于与其最近的簇。
具体来说，K-Means算法的工作流程如下：（1）随机初始化K个中心点；（2）将每个样本点分配到距离最近的中心点所对应的簇中；（3）更新每个簇的中心点，即将该簇内所有样本点的均值作为新的中心点；（4）重复执行步骤（2）和（3），直到中心点不再发生变化或达到迭代次数上限。
K-Means算法的优点包括实现简单、计算高效等，适用于数据量较大的情况。
但它也存在一些缺点，比如对初始中心点的选择敏感，容易陷入局部最优解，不适用于发现非凸簇等情况。
2. DBSCAN算法DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法是一种基于密度的聚类算法，它的核心思想是通过样本点的密度来发现聚类簇。
DBSCAN算法的具体步骤如下：（1）以任意顺序选择一个未访问的样本点；（2）计算该样本点的邻域内的样本点个数，若超过预设的阈值，则标记为核心点，否则标记为噪声点；（3）将与核心点密度相连的样本点放入同一个簇中，并继续递归地扩展该簇；（4）重复执行步骤（1）和（2），直到所有样本点都被访问为止。
DBSCAN算法的优点在于可以发现任意形状的簇，并且对噪声数据具有鲁棒性，不受初始参数的影响。
但它也存在一些局限性，比如对密度不同的簇难以处理，对参数的敏感性较强等。
3. K-Means和DBSCAN的比较K-Means和DBSCAN是两种不同的聚类算法，它们在很多方面存在明显的差异。
下面将分别从适用场景、对数据特点的适应性、算法复杂度等方面对它们进行比较。
一种基于局部异常因子（LOF）的k-means算法陈静;王伟【摘要】聚类分析算法是数据挖掘技术的一个重要分支，目前其研究已经广泛应用于教育、金融、零售等众多领域并取得了较好的效果。
本文结合了基于划分和密度的聚类思想，提出了一个适用于挖掘任意形状的、密度不均的、高效的聚类算法。
%Cluster analysis is an important research field in data mining,at present,the research has been applied to the financial, retail and other fields, and have achieved good results.This paper studied partition and density clustering algorithm, proposed a new algorithm which is suitable for mining arbitrary shape and uneven density.【期刊名称】《电子测试》【年(卷),期】2016(000)012【总页数】2页(P60-61)【关键词】数据挖掘;聚类算法;局部异常因子【作者】陈静;王伟【作者单位】青岛职业技术学院，山东青岛，266555;青岛职业技术学院，山东青岛，266555【正文语种】中文随着数据挖掘技术应用领域越来越广泛，聚类分析也接受着各种严峻的“考验”：处理的数据类型的多样化，对大数据集进行高效处理的迫切需求，对任意形状聚类的有效识别等等。
这些都要求聚类算法能够具体高效、灵活等特点，因此，寻求一个高效、灵活的聚类算法，是研究人员的当务之急。
聚类分析方法是数据挖掘技术应用最广泛的算法之一。
在机器学习领域，聚类分析算法属于无指导型学习算法。
给定一组对象，聚类分析自动地将其聚集成k个集群，每个集群中的对象具有极高的相似度，而属于不同集群的对象间的相似度很低。
专利名称：一种基于K-means聚类的数字化调香方法专利类型：发明专利
发明人：孔波,蔡佳校,钟科军,卢红兵,杨华武,李燕春,吴榆申请号：CN201910704921.9
申请日：20190731
公开号：CN112397156A
公开日：
20210223
专利内容由知识产权出版社提供
摘要：本发明公开了一种基于K‑means聚类的数字化调香方法，是通过建立的香原料信息库，使用K‑means聚类算法将香原料信息库中相互之间相似度较高的香原料进行聚类，再基于聚类划分结果对创香目标经验配方单中的香原料进行自动识别，得到相关性强的相关香原料并对其进行替换，完成香原料信息更新，最后通过香比强值的差异，对香原料的用量信息进行调整，生成并输出新的配方单。
由于香原料之间存在部分相似的性质，但又性能各异，此类方法创作的配方，在保持原配方的主要特征的同时，还能表现出新的特性。
申请人：湖南中烟工业有限责任公司
地址：410014 湖南省长沙市雨花区万家丽中路三段188号
国籍：CN
代理机构：长沙市融智专利事务所(普通合伙)
代理人：颜勇
更多信息请下载全文后查看。
kmeans的聚类算法K-means是一种常见的聚类算法，它可以将数据集划分为K个簇，每个簇包含相似的数据点。
在本文中，我们将详细介绍K-means算法的原理、步骤和应用。
一、K-means算法原理K-means算法基于以下两个假设：1. 每个簇的中心是该簇内所有点的平均值。
2. 每个点都属于距离其最近的中心所在的簇。
基于这两个假设，K-means算法通过迭代寻找最佳中心来实现聚类。
具体来说，该算法包括以下步骤：二、K-means算法步骤1. 随机选择k个数据点作为初始质心。
2. 将每个数据点分配到距离其最近的质心所在的簇。
3. 计算每个簇内所有数据点的平均值，并将其作为新质心。
4. 重复步骤2和3直到质心不再变化或达到预定迭代次数。
三、K-means算法应用1. 数据挖掘：将大量数据分成几组可以帮助我们发现其中隐含的规律2. 图像分割：将图像分成几个部分，每个部分可以看做是一个簇，从而实现图像的分割。
3. 生物学：通过对生物数据进行聚类可以帮助我们理解生物之间的相似性和差异性。
四、K-means算法优缺点1. 优点：（1）简单易懂，易于实现。
（2）计算效率高，适用于大规模数据集。
（3）结果可解释性强。
2. 缺点：（1）需要预先设定簇数K。
（2）对初始质心的选择敏感，可能会陷入局部最优解。
（3）无法处理非球形簇和噪声数据。
五、K-means算法改进1. K-means++：改进了初始质心的选择方法，能够更好地避免陷入局部最优解。
2. Mini-batch K-means：通过随机抽样来加快计算速度，在保证精度的同时降低了计算复杂度。
K-means算法是一种常见的聚类算法，它通过迭代寻找最佳中心来实现聚类。
该算法应用广泛，但也存在一些缺点。
针对这些缺点，我们可以采用改进方法来提高其效果。
一种基于遗传算法的K-means聚类算法一种基于遗传算法的K-means聚类算法摘要：传统K-means算法对初始聚类中心的选取和样本的输入顺序非常敏感，容易陷入局部最优。
针对上述问题，提出了一种基于遗传算法的K-means聚类算法GKA，将K-means算法的局部寻优能力与遗传算法的全局寻优能力相结合，通过多次选择、交叉、变异的遗传操作，最终得到最优的聚类数和初始质心集，克服了传统K-means 算法的局部性和对初始聚类中心的敏感性。
关键词：遗传算法；K-means；聚类聚类分析是一个无监督的学习过程，是指按照事物的某些属性将其聚集成类，使得簇间相似性尽量小，簇内相似性尽量大，实现对数据的分类[1]。
聚类分析是数据挖掘技术的重要组成部分，它既可以作为独立的数据挖掘工具来获取数据库中数据的分布情况，也可以作为其他数据挖掘算法的预处理步骤。
聚类分析已成为数据挖掘主要的研究领域，目前已被广泛应用于模式识别、图像处理、数据分析和客户关系管理等领域中。
K-means算法是聚类分析中一种基本的划分方法，因其算法简单、理论可靠、收敛速度快、能有效处理较大数据而被广泛应用，但传统的K-means算法对初始聚类中心敏感，容易受初始选定的聚类中心的影响而过早地收敛于局部最优解，因此亟需一种能克服上述缺点的全局优化算法。
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法。
在进化过程中进行的遗传操作包括编码、选择、交叉、变异和适者生存选择。
它以适应度函数为依据，通过对种群个体不断进行遗传操作实现种群个体一代代地优化并逐渐逼近最优解。
鉴于遗传算法的全局优化性，本文针对应用最为广泛的K-means方法的缺点，提出了一种基于遗传算法的K-means聚类算法GKA(Genetic K-means Algorithm)，以克服传统K-means算法的局部性和对初始聚类中心的敏感性。
用遗传算法求解聚类问题，首先要解决三个问题：(1)如何将聚类问题的解编码到个体中；(2)如何构造适应度函数来度量每个个体对聚类问题的适应程度，即如果某个个体的编码代表良好的聚类结果，则其适应度就高；反之，其适应度就低。
K-means聚类算法是一种经典的基于距离的聚类算法，它被广泛应用于数据挖掘、模式识别、图像分割等领域。
K-means算法通过不断迭代更新簇中心来实现数据点的聚类，其算法流程如下：1. 初始化：首先需要确定要将数据分成的簇的个数K，然后随机初始化K个簇中心，可以从数据集中随机选择K个样本作为初始簇中心。
2. 分配数据：对于每个数据点，计算它与各个簇中心的距离，将该数据点分配给距离最近的簇，并更新该数据点所属簇的信息。
3. 更新簇中心：计算每个簇中所有数据点的均值，将该均值作为新的簇中心，更新所有簇中心的位置。
4. 重复迭代：重复步骤2和步骤3，直到簇中心不再发生变化或者达到预定的迭代次数。
5. 输出结果：最终得到K个簇，每个簇包含一组数据点，形成了聚类结果。
K-means算法的优点在于简单易实现，时间复杂度低，适用于大规模数据；但也存在一些缺点，如对初始聚类中心敏感，对噪声和离裙点敏感，需要事先确定聚类个数K等。
K-means聚类算法是一种常用的聚类方法，通过迭代更新簇中心的方式逐步将数据点划分为不同的簇，实现数据的聚类分析。
通过对算法流程的详细了解，可以更好地应用K-means算法解决实际问题。
K-means算法是一种非常经典的聚类算法，它在数据挖掘和机器学习领域有着广泛的应用。
在实际问题中，K-means算法可以帮助我们对数据进行分组和分类，从而更好地理解数据的内在规律，为我们提供更准确的数据分析和预测。
接下来，我们将对K-means聚类算法的一些关键要点进行探讨，包括算法的优化、应用场景、以及与其他聚类算法的比较等方面。
1. 算法的优化：在实际应用中，K-means算法可能会受到初始簇中心的选择和迭代次数的影响，容易收敛到局部最优解。
有一些改进的方法可以用来优化K-means算法，例如K-means++算法通过改进初始簇中心的选择方式，来减少算法收敛到局部最优解的可能性；另外，Batch K-means算法通过批量更新簇中心的方式来加快算法的收敛速度；而Distributed K-means算法则是针对大规模数据集，通过并行计算的方式来提高算法的效率。
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.19, No.7, July 2008, pp.1683−1692 DOI: 10.3724/SP.J.1001.2008.01683 Tel/Fax: +86-10-62562563© 2008 by Journal of Software. All rights reserved.∗一种基于K-Means局部最优性的高效聚类算法雷小锋1,2+, 谢昆青1, 林帆1, 夏征义31(北京大学信息科学技术学院智能科学系/视觉与听觉国家重点实验室,北京 100871)2(中国矿业大学计算机学院,江苏徐州 221116)3(中国人民解放军总后勤部后勤科学研究所,北京 100071)An Efficient Clustering Algorithm Based on Local Optimality of K-MeansLEI Xiao-Feng1,2+, XIE Kun-Qing1, LIN Fan1, XIA Zheng-Yi31(Department of Intelligence Science/National Laboratory on Machine Perception, Peking University, Beijing 100871, China)2(School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China)3(Logistics Science and Technology Institute, P.L.A. Chief Logistics Department, Beijing 100071, China)+ Corresponding author: E-mail: leiyunhui@Lei XF, Xie KQ, Lin F, Xia ZY. An efficient clustering algorithm based on local optimality of K-Means.Journal of Software, 2008,19(7):1683−1692. /1000-9825/19/1683.htmAbstract: K-Means is the most popular clustering algorithm with the convergence to one of numerous localminima, which results in much sensitivity to initial representatives. Many researches are made to overcome thesensitivity of K-Means algorithm. However, this paper proposes a novel clustering algorithm called K-MeanSCANby means of the local optimality and sensitivity of K-Means. The core idea is to build the connectivity betweensub-clusters based on the multiple clustering results of K-Means, where these clustering results are distinct becauseof local optimality and sensitivity of K-Means. Then a weighted connected graph of the sub-clusters is constructedusing the connectivity, and the sub-clusters are merged by the graph search algorithm. Theoretic analysis andexperimental demonstrations show that K-MeanSCAN outperforms existing algorithms in clustering quality andefficiency.Key words: K-MeanSCAN; density-based; K-Means; clustering; connectivity摘要: K-Means聚类算法只能保证收敛到局部最优,从而导致聚类结果对初始代表点的选择非常敏感.许多研究工作都着力于降低这种敏感性.然而,K-Means的局部最优和结果敏感性却构成了K-MeanSCAN聚类算法的基础.K-MeanSCAN算法对数据集进行多次采样和K-Means预聚类以产生多组不同的聚类结果,来自不同聚类结果的子簇之间必然会存在交集.算法的核心思想是,利用这些交集构造出关于子簇的加权连通图,并根据连通性合并子簇.理论和实验证明,K-MeanScan算法可以在很大程度上提高聚类结果的质量和算法的效率.关键词: K-MeanSCAN;基于密度;K-Means;聚类;连通性中图法分类号: TP18文献标识码: A∗ Supported by the National High-Tech Research and Development Plan of China under Grant No.2006AA12Z217 (国家高技术研究发展计划(863)); the Foundation of China University of Mining and Technology under Grant No.OD080313 (中国矿业大学科技基金)Received 2006-10-09; Accepted 2007-07-171684 Journal of Software软件学报 V ol.19, No.7, July 2008聚类分析在统计学、机器学习、数据挖掘、生物学、空间数据库、Web搜索、分布式网络、市场营销等领域得到广泛的研究和应用,在文献[1]中对聚类方法进行了很好的综述.一般地,假设d维数据空间A中有n个样本,每个样本可以视为d维空间的一个点,聚类是将这n个点分组,每组就形成一个类簇,要求属于同一类簇的点尽可能相近,不同类簇间的点尽可能远离.常用的聚类算法主要有划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法.本文提出一种新的聚类算法——K-MeanSCAN,集成多种聚类方法的性质,特别是K-Means算法的局部最优特征和结果敏感性.理论分析和实验结果表明,K-MeanSCAN算法具有如下特点:(1) 可以发现任意形状的类簇.K-MeanSCAN算法充分借鉴了基于密度聚类方法的思想,能够发现任意形状的类簇,并对异常点和噪声数据不敏感.(2) 考虑了子簇之间的连通强度.避免了基于密度聚类算法中由于密度连通关系的传递性导致绝大多数的样本点聚集到非常少的几个类簇中(通常是一类).(3) 算法具有很好的时间性能和伸缩性.算法结合采样技术、K-Means预聚类技术和图搜索算法提供高效的聚类性能,其时间复杂度为O(n),且对大数据集有很强的伸缩性.(4) 算法引入了钝参数的概念,减轻了聚类结果对参数阈值的敏感性,使得算法无需过多的先验知识.此外,算法仅使用一个参数对类簇的密度进行建模,与DBSCAN(density based spatial clustering of application with noise)[2]的Eps和MinPts两个参数相比,易于交互式或自动计算以确定密度阈值.本文第1节对现有的一些聚类算法进行综述.第2节详细阐述K-MeanSCAN算法的基本思想及其形式化定义,并给出具体的算法描述和复杂性分析.第3节提供详细的实验以证明K-MeanSCAN算法的聚类质量和执行效率.最后是结论和下一步工作说明.1 常用聚类算法综述划分聚类算法通过迭代重定位策略优化特定的目标函数,尝试确定数据集的一个划分.最常用的目标函数是误差平方和准则,如K-Means算法.K-Means算法对类球形且大小差别不大的类簇有很好的表现,但不能发现形状任意和大小差别很大的类簇,且聚类结果易受噪声数据影响.此外,K-Means算法仅保证快速收敛到局部最优结果,从而导致聚类结果对初始代表点的选择非常敏感,本文称其为结果敏感性,是许多研究工作所要着力解决的问题.层次聚类算法以自顶向下(分裂)或自底向上(凝聚)的方式将数据对象划分成一个层次树结构,即类簇树.算法的聚类效果很大程度上依赖于度量类簇之间相异度的距离函数.此外,一般层次聚类算法的伸缩性不强,其时间复杂度通常为O(n2).BIRCH(balanced iterative reducing and clustering using hierarchies)[3]和CURE(clustering using representatives)[4]算法试图提高层次聚类结果的质量,解决其算法伸缩性问题.BIRCH算法具有O(n)的计算复杂度,在有限内存下可以很好地工作.但是,算法使用的相异度度量导致BIRCH只能发现球形类簇.CURE使用固定数量的代表点来定义类簇,可以发现复杂形状和不同大小的类簇,对噪声具有很好的免疫能力.然而,CURE算法的收缩方式隐含地依赖于球形类簇假设,故在处理特殊形状的类簇时比较困难.基于密度的聚类算法中类簇被定义为连通的稠密子区域.因此,算法能够发现任意形状的类簇,并对异常点和噪声有自然的免疫能力.DBSCAN是典型的面向低维空间数据聚类的基于密度的算法,其关键概念是由对象最近邻域的局部分布度量的密度及其连通性.DBSCAN算法本质上只是提供了一个根据密度阈值参数进行聚类结果搜索的过程,聚类结果在用户指定密度阈值那一刻已经唯一地确定,算法本身并不对聚类的结果负责.其主要缺陷包括:(1) 算法通常对参数值的设置非常敏感,聚类结果的质量很大程度上依赖于密度阈值参数的合理选取,因而对用户的经验和专业素养提出很高的要求;(2) 真实的数据集合经常分布不均匀,导致这种全局性的密度参数通常不能刻画数据内在的聚类结构;(3) 算法中通过密度连通性来合并高密子簇,由于密度连通关系的传递性,往往使得绝大多数的样本点雷小锋 等:一种基于K -Means 局部最优性的高效聚类算法1685C 聚集到非常少的几个类簇中(通常是一类). OPTICS(ordering points to identify the clustering structure)[5]算法针对DBSCAN 算法的缺陷进行了改进. 2 K -MeanSCAN 算法2.1 算法思想2.1.1 从搜索到构造许多聚类算法的基本框架是搜索与合并.如在层次方法中需要搜索两个距离最近的类簇然后合并;而基于密度的聚类算法则不断地搜索高密子区域,然后利用连通性将其合并到当前聚类结果中.很明显,搜索过程需要面对整个样本集合,通常会导致算法低效.如DBSCAN 需要测试每个对象是否是核心对象,并对每个核心对象搜索其直接密度可达的对象,如果没有空间索引的辅助,DBSCAN 算法的复杂度为O (n 2).实际上,现有的很多聚类算法已经关注到这个问题,如CURE 算法利用采样方法减小搜索空间,而Chameleon [6]算法则通过图划分算法将样本对象聚类为大量相对较小的子簇.具体到本文,我们采用了随机采样和K -Means 算法高效地聚出大量的高密子簇,后续处理都基于这些构造出的高密子簇进行,无须直接面对所有的样本.我们称这种算法框架为构造与合并.因此,K -MeanSCAN 算法的处理流程为:随机采样、预聚类、合并和后处理.聚类算法的本质是密度估计问题,K -MeanSCAN 算法的核心思想是,增加K -Means 算法中高斯混合模型的高斯分量数目以提升密度估计的精度,并利用K -Means 聚类的局部最优和结果敏感性的特征进行高斯分量(即高密子簇)的合并剪枝,克服过拟合问题,最终实现有效的聚类.2.1.2 K -Means 算法的概率模型K -Means 算法实质上是一种将聚类视为密度估计问题的概率方法.在概率方法中,假设样本来自于如下形式的混合模型: ,1:(|)()(|,)j j j j j k p P C p Θθ==∑x x 式中,Θ=(θ1,…,θk )是待估计的参数向量;条件概率密度p (x |θj ,C j )称为分量密度,表示类别j 的概率密度形式,且参数向量θj 未知;先验概率P (C j )称为混合因子.为了简化问题,K-Means 算法进一步假设:(1) 每个类别的概率密度形式为球形高斯分布,即θj =(μj ,Σ)且Σ1=…=Σk =σ2I ,μj ,σ2未知;(2) 每个样本唯一地属于一个类别;(3) 假设所有类别的混合因子相等.于是,混合模型简化为 22/221:1:11(|)max (|,,)max exp ||||(2)2j j j d j k j k p C ΘφμΣμσσ==⎧⎫⎛==−⎞−⎨⎬⎜π⎝⎠⎩⎭x x x ⎟ (1) 该简化模型可以通过最大似然方法求解,对于观测样本X =(x 1,…,x n ),相应的对数似然函数为2/222111(|)ln (|)ln[(2)]||||2i j n kd i i j l X p n ΘΘσσ====−π−−∑x x i j C μ∈∑∑x j (2)最大化该对数似然函数等价于最小化上式的欧氏距离平方项,即得到K -Means 的误差平方和准则:(3)21||||i j ke i j C J μ=∈=−∑∑x x 通过迭代优化上述的误差平方和准则,K -Means 算法最终可以估计出每个高斯分量的均值向量和协方差矩阵Σ=σ2I .式中,n j 是类簇C j 的样本数目.1i j j i C j n μ∈=∑x x ,211||||i j k e i j j C 2J nd nd σμ=∈=−∑∑x x = (4) 2.1.3 K -MeanSCAN 的过拟合-合并剪枝策略要获得更有效的样本密度估计,J e 的值自然是越小越好.但是,J e 的值不仅取决于样本的分类情况,而且与类别数目k 有关.当类别数目k 给定时,J e 的值由样本的分类情况所决定,且存在一个最小值J k -min 对应于最优的样本类别划分.如果类别数目k 和高斯混合模型假设与实际问题相匹配时,最小值J k -min 必定很小,从而可以很好地近似样本密度;而如果模型假设不合理,则最小值J k -min 可能依然很大,对样本分布的近似效果较差.1686Journal of Software 软件学报 V ol.19, No.7, July 2008对于任意形状的类簇,很明显不能直接要求数据分布满足高斯混合模型的假设,否则会导致最小的误差平方和J k -min 很大.实际上,高斯混合模型具有很强的表达能力,如果高斯分量密度的数目k 足够大,则高斯混合模型几乎可以近似任意一种概率分布.换言之,随着类别数目k 的增加,相应的J k -min 会减小.简单证明如下:类别数目k 的增加,必然导致最终每个类簇的形状缩小,对应于高斯分量的σ2减小;而从公式(3)和公式(4)可以得出J k -min =nd σ2,即最小的误差平方和正比于σ2;因此,k 的增加会导致最小的误差平方和J k -min 的减小.极端情况下,k =n ,则每个样本点都是一个类簇,即J k -min =0,说明此时的经验误差为0,但是此时,模型的推广能力极差.根据统计学习理论,经验误差最小并不等于期望误差最小,经验风险只有在样本数无穷大时才趋近于期望风险.因此,经验误差最小不能保证分类器的推广能力,需要找到经验风险最小和推广能力最大的平衡点.同样,利用足够多的高斯分量组成的混合模型来描述数据会导致过拟合的问题,影响模型的推广能力.因此,在K -MeanSCAN 算法中,我们采用过拟合-剪枝的策略进行聚类,即首先使用分量足够多的高斯混合模型来较好地近似样本分布,然后通过合并一些高斯分量的剪枝策略来处理过拟合问题.除了提高对样本分布的近似精度以外,增加类别数目还有其他好处.已知K -Means 算法通过迭代重定位技术最小化误差平方和准则,最终快速收敛到一个局部最优的解.形象地,可以认为K -Means 算法是在对数似然函数空间上的随机爬山算法,对于具有k 个全局最高点和大量局部极高点的数据集,K -Means 聚类算法很可能陷入局部极高点,从而导致对于不同的初始类簇代表点,算法会收敛到不同的局部极值点,即聚类结果对初始代表点的选择非常敏感,本文称其为“结果敏感性”.类别数目k 的增大类似于开辟更多的爬山路径,如果k ′>>k 个路径,则到达全局最高点的可能性自然会增大,当然过拟合问题不可避免.2.1.4 类簇的合并剪枝在K -MeanSCAN 算法中,利用K -Means 的结果敏感性对类簇进行合并剪枝来处理过拟合问题.假设在样本集上进行两次K -Means 聚类,得到两组结果分别是R 1={C 11,C 12,…,C 1k ′}和R 2={C 21,C 22,…,C 2k ′},且因结果敏感性使得R 1≠R 2,则至少存在一个属于R 1(或R 2)的类簇C 1m 与R 2(或R 1)中至少两个类簇之间都存在交集(证明略).实际中,K -Means 算法的结果敏感性导致不同聚类结果中大量的类簇之间存在交集.如图1所示,对于 图1(a)的样本集合,图1(b)、图1(c)分别是两次K -Means 聚类的结果,图1(c)说明两次聚类结果之间存在交集.如果不同聚类结果中两个类簇之间交集的基数足够大,则我们宁愿相信这两个类簇中的样本不应该分为两类,而应合并为一个类簇.通过这种方式,可以建立如图2所示的类簇间的连通关系,并根据连通关系将类簇合并. S C 1C 21C ′2C′(a) (b) (c) (d)Fig.1 A demo of the sensitivity of K -Means algorithm图1 K -Means 算法结果敏感性的示意C 11C 12C 13C 14C 151112131415(a) (b)Fig.2 Building the connection relationships between clusters图2 建立类簇之间的连通关系R 1Pre-Clustering Connectivity6雷小锋 等:一种基于K -Means 局部最优性的高效聚类算法1687n 上述思路构成了K -MeanSCAN 算法实现类簇合并剪枝的基础.基于K -Means 算法预聚类的结果, K -MeanSCAN 算法的主要步骤包括:(1) 在多次预聚类结果上构造类簇之间的加权连通图;(2) 利用图搜索算法合并连通的类簇;(3) 算法最后还包括一个后处理阶段,利用凝聚层次聚类算法对步骤(2)生成的合并类簇再进行一次聚类,以进一步保证聚类结果的质量.此外,后处理步骤还需要对所有在合并剪枝中剔除的样本进行重新计算,确定其最终的类别标记或者标记为噪声.在描述具体算法之前,我们首先引入一些形式化的概念和定义.以下用k 表示实际的类簇数目,用k ′表示预聚类的类簇数目.2.2 概念和定义设P =(R 1,R 2,…,R h )表示h 次K -Means 聚类结果,且R i ={C i 1,C i 2,…,C ik ′}∈P ,并称C ij 为聚类结果R i 的一个子簇. 定义1(子簇密度和高密子簇). 假设C ij 为一个子簇,其密度应正比于子簇中的样本数量,反比于子簇的空间范围,形式化定义如下:den (C ij )=||C ij ||/r d ,max((,.))l ijl ij C r dist C mea ∈=x x . 式中,||*||表示集合*的基数,r 为所有样本到子簇均值中心的最大距离.如果den (C ij )大于给定阈值denh ,则称该子簇为高密子簇.在K -MeanSCAN 算法中,只有高密子簇才参与合并.定义2(直接连通). 假设C ij ∈R i 和C st ∈R s 是两个高密子簇,且二者的交集非空,则称C ij 与C st 是直接连通的,并定义C ij 与C st 之间的直接连通强度为两个子簇交集的基数与其并集基数的比值,dcn (C ij ,C st )=||C ij ,∩C st ||/||C ij ,∪C st ||.直接连通关系具有自反、对称和传递性,是一种等价关系.可以看到,来自同一聚类结果的任意两个子簇之间都不存在交集,不可能直接连通或者连通强度为0.如果两个直接连通的子簇的直接连通强度大于给定的阈值dcnh ,则称两个子簇是强直接连通的.定义3(间接连通). 假设C i 和C j 是任意两个高密子簇,且二者的交集为空,如果存在一个子簇的序列C 1,C 2,…,C s ,且C 1=C i ,C s =C j ,使得C t +1与C t 之间是强直接连通的,则称C i 与C j 是强间接连通的,并且间接连通的连通强度为所有强直接连通强度的最小值.定义4(合并簇). 基于上述的连通关系,可以构造关于所有高密子簇的加权连通图(weighted connected graph,简称WCG),其中,一个高密子簇对应于图中的一个顶点,并且为每条边分配一个连通强度作为权值.于是,一个合并簇C 就定义为所有强连通(包括直接连通和间接连通)的子簇的并集,最终产生的合并簇满足两个条件:(1) C 中任意两个子簇必定是强连通的;(2) 如果C i 属于C ,且与C j 是强连通的,则C j 也必定属于C .2.3 算法描述K -MeanSCAN 算法在构造与合并的算法框架下实现.在构造过程中,算法首先从样本数据集中随机抽取一组样本.然后,算法利用K -Means 对随机样本进行预聚类,预聚类的类簇数目为k ′>>k .重复采样和预聚类过程h 次,得到h 组在随机样本上的聚类结果,每组聚类结果包括k ′个类簇中心.此时,对整个样本集进行单遍扫描,将每个样本对象分配给相应的距离最近的h 个类簇中心.至此,产生h 组关于数据集的划分.基于这些数据集的划分,K -MeanSCAN 算法计算来自不同划分的子簇之间的连通性,并构造加权连通图,然后利用广度优先的图搜索算法求得最大连通的子图,从而将相应的高密子簇合并,即上文定义的合并簇.最后,利用凝聚的层次聚类算法对合并簇进一步处理,得到最终聚类结构.在层次聚类过程中使用的距离度量定义为两个待合并簇中所有子簇中心的最小距离,假设MC 1和MC 2是两个合并簇,则11221212,(,)min (.,.C MC C MC dist MC MC dist C mean C mean ∈∈=). 最后,根据最终的聚类结构对所有未参与合并剪枝的样本进行重新标记,确定其类别或者标记为噪声.以下通过伪代码给出K -MeanSCAN 算法的流程说明.Algorithm program K -MeanSCAN(SetOfPoints ,h =2,k ′)var RandomSample: rndsmp ;1688Journal of Software 软件学报 V ol.19, No.7, July 2008Clusters: cluss , mergedcluss , finalcluss ;Cluster: clus ; Connection: conns ;Integer: iterations ; Float: denh , dcnh ;begin//pre-clusteringrepeatrndsmp =DrawSample ();clus =K-Means (rndsmp ,k ′);cluss .add (clus ); iterations ++;until iterations =hAssignEachObject (SetOfPoints ,cluss );denh =ComputeDenh (cluss );conns =BuildWCG (cluss );dcnh =ComputeDcnh (conns );mergedcluss =MergedByBFS (cluss ,conns ); finalcluss =MergedByAgglom (mergedcluss );return finalcluss ;end. //K -MeanSCAN算法中,参数h 是采样和预聚类的次数,也是构造过程产生的划分数.参数k ′是K -Means 预聚类时的类簇数目.在K -MeanSCAN 算法中,局部变量denh 和dcnh 分别是密度阈值和连通强度阈值.函数AssignEachObject ()在样本集上执行单遍扫描,将每个样本对象分配给相应的子簇;函数BuildWCG ()计算子簇之间的连通关系,并构造加权连通图;函数MergedByBFS ()通过广度优先的图搜索算法合并子簇;最后,函数MergedByAgglom ()通过层次聚类算法产生最终的聚类结构,并对被剔除的样本重新标记.限于篇幅,本文略去关于这些函数更为详细的 描述.2.4 算法参数设置2.4.1 采样大小在文献[4]中已经阐明合理的随机采样大小能够相当精确地反映类簇的几何结构,并通过如下定理给出了相应的采样精度保证.假设对于类簇u ,如果样本集包含至少f |u |个来自类簇u 的样本点,0≤f ≤1,则在聚类中丢失该类簇的概率很小.定理1. 对于一个类簇u ,如果采样大小s 满足如下约束:则随机样本集中来自类簇u 的样本数小于f |u |的概率小于δ,0≤δ≤1. 211log log 2||log ||||n n s fn f u u u 1δδδ⎛⎞⎛⎞⎛⎞⎛⎞≥+++⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠⎝⎠⎝⎠. 假设u min 是需要关注的最小类簇,根据定理1可以得到相应的s min .对于k 个类簇,在样本大小为s min 时,从任意类簇u 中采样数目小于f |u |的概率具有上界k δ.2.4.2 预聚类次数h 和类簇数k ′参数h 是预聚类或采样的次数,很明显,h ≥2.根据K -MeanSCAN 算法的原理,h 较大,则属于同一类簇的子簇之间被合并的几率就较大,从而可以产生更高质量的聚类结果,不过同时也会增加计算代价.本文的实验测试表明,h =3~10通常已经足够.预聚类的另一个重要参数是类簇数目k ′.对于该参数的约束是要求k ′远远大于实际的类簇数目k ,小于样本集的大小n .为了能够捕捉到感兴趣的最小类簇u min ,k ′必须大于⎡n /|u min |⎤.在文献[7]中研究了k 近邻分类算法中参雷小锋 等:一种基于K -Means 局部最优性的高效聚类算法 1689 数k 的设置,给出一个法则:k ≈n 3/8.参考这一结论,我们推荐k ′值的选取满足如下约束:min(α⎡n /|u min |⎤,n 5/8),α取值一般小于等于10.需要说明的是,在满足上述约束条件时,k ′的取值对于聚类结果不敏感,我们称这种对结果不敏感的参数为“钝参数”,可以降低对先验知识和用户专业素养的要求,下文的实验将对这一事实进行说明.2.4.3 子簇密度阈值denh 和连通强度阈值dcnh参数denh 是子簇密度阈值,只有密度大于denh 的子簇才参与K -MeanSCAN 算法的合并过程,而密度小于denh 的子簇必包含大量的噪声.直观地,对于包含噪声或完全由噪声样本形成的子簇,其样本数目少,而空间分布范围却较大,故其密度很小;而对实际存在的类簇,则子簇比较紧缩,密度较大.假设h 次预聚类形成的hk ′个子簇的密度集合为dens ={den i |i =1,…,hk ′},以升序排序得到sort _dens ,其曲线模式如图3(a)所示.可以看出,从低密区域到高密区域存在一个急剧的跃迁,即可确定密度阈值.为了自动求解密度阈值,首先对sort _dens 进行差分运算得到diff _dens .绘制差分曲线,与密度曲线的跃迁处相对应,在差分曲线上存在一个较大的峰值.取前一半的差分运算值,并利用高斯函数形式对其进行曲线拟合,差分曲线的峰值处就对应于高斯函数的均值mu ,是密度阈值在sort _dens 中对应的索引值,如图3(b)所示.于是,密度阈值为denh =sort _dens [round (mu )].实验测试表明,这种自动密度阈值计算方法效果很好.而连通强度阈值dcnh 的设置取决于实际用户的主观倾向.一般情况下,可直接设置dcnh =0,或者取所有的连通强度的均值.0.20(a) Pattern of sort _dens (b) Finding denh on diff _dens(a) 子簇密度变化的曲线模式 (b) 差分曲线上的密度阈值求解Fig.3 Density threshold denh图3 密度阈值denh2.5 算法复杂性分析K -Means 算法是相当高效的,其计算复杂度为O (nkdt ),其中,n 为所有样本对象的数目,k 是设定的类簇数目,d 是样本数据的维度,t 是迭代的次数.通常,k <<n 且t <<n .h 次预聚类的时间复杂度为O (hn smp kdt ),这里,n smp 为随机样本的大小.单遍扫描样本集需要的时间代价为O (hn ).此后,所有的运算都基于K -Means 的预聚类结果,其中不涉及任何代价较高的空间几何计算.函数BuildWCG ()需要(hk )2次集合求交运算,假定每个子簇的平均样本数目为n /k ,则整个集合求交运算的时间代价为O (h 2kn ).函数MergedByBFS ()的时间复杂度为O (k 2),即广度优先搜索的代价.最后,函数MergedByAgglom ()的时间代价为O (k 2).于是,K -MeanSCAN 算法的总代价为O (hkn smp dt )+ O (hn )+O (h 2kn )+O (k 2)+O (k 2),假定n 很大,h 为常数,k <<n ,则算法的时间复杂度约为O (n ).3 实验评估本节我们通过实验比较来研究K -MeanSCAN 算法的性能和有效性.实验采用的数据包括在各种聚类算法评估中常用的模拟数据(如图4所示),以及DBSCAN 算法中使用的来自真实地球科学领域的SEQUOIA 2000基准测试数据[8].实验的硬件环境为P4 1.86Ghz 的CPU 和512MB 的内存,软件环境为Microsoft Windows XP Sub-Clusters of high density 0.180.160.140.120.100.080.060.04denh D e n s i t y 0.020.00sort _dens 160 180diff _dens0 10 20 30 80 0.000mu Gaussian fitting curve 0.0150.0050.0101690 Journal of Software 软件学报 V ol.19, No.7, July 2008 (professional)操作系统,所有代码均用Visual C++ 6.0实现.(a) Data 1 (b) Data 2 (c) Data 3 (d) Data 4Fig.4 Synthetic datasets for evaluating clustering algorithms图4 常用的评估聚类算法的模拟数据3.1 聚类结果图5~图8分别给出了上述4组数据经过预聚类、合并剪枝后的结果,以及相应的DBSCAN 聚类结果.实验中,预聚类的类簇数目均设置为k ′≈n 5/8,预聚类次数h =5,连通强度阈值dcnh =0.在每个图中,图(a)是K -MeanSCAN 聚类结果,图(b)是相应的密度曲线和密度阈值,图(c)是密度差分序列和高斯函数拟合曲线,图(d)是DBSCAN 聚类结果.denh Gaussian fitting curve (a) (b) sort_dens (c) diff_dens (d) Eps =21, Min Pts =4Fig.5 Clustering result of data 1 and its threshold denh图5 Data 1聚类结果及其密度阈值Gaussian fitting curve denh (a) (b) sort_dens (c) diff_dens (d) Eps =18.64, Min Pts =4Fig.6 Clustering result of data 2 and its threshold denh图6 Data 2聚类结果及其密度阈值(a) (b) sort_dens (c) diff_dens (d) Eps =15.38, Min Pts =4Fig.7 Clustering result of data 3 and its threshold denh图7 Data 3聚类结果及其密度阈值denh Gaussian fitting curve雷小锋 等:一种基于K -Means 局部最优性的高效聚类算法1691(a) (b) sort_dens (c) diff_dens (d) Eps =10.58, Min Pts =4Fig.8 Clustering result of data 4 and its threshold denh (dcnh =0)图8 Data 4聚类结果及其密度阈值(dcnh =0)可以看出,对于上述4组数据,K -MeanSCAN 算法无需后处理步骤即可得到高质量的聚类结果.对于数据集Data 4而言,当将其连通阈值设置为所有连通强度的均值时,无后处理步骤的K -MeanSCAN 聚类结果如图9所示.此时,下方的两个子簇得到区分,经后处理过程即可得到高质量的聚类效果.此外,DBSCAN 算法亦可取得不错的结果,但其密度参数设置需要多次调试,且对于Data 4而言,无法区分下方的两个子簇.同时可以看出密度曲线的变化模式,即对于有噪声的数据集,其密度曲线的跃迁区域远离y 轴;而对于无噪声的数据集,则其密度曲线的跃迁区域非常靠近y 轴.(a) (b) sort_dens (c) diff_densFig.9 Clustering result of data 4 and its threshold denh (dcnh =average connectivity)图9 Data 4聚类结果及其密度阈值(dcnh =平均连通强度)3.2 参数敏感性和算法伸缩性评估在K -MeanSCAN 算法中,一个重要的参数是预聚类时的子簇数目k ′.前文已经说明该参数对聚类结果不敏感,是“钝参数”.这里,我们在Data 4上对参数k ′进行敏感性分析.实验中,k ′≈206,h =5,dcnh =0.最终结果中,簇数的变化在图10中给出.可以看出,在k ′>30之后,K -MeanSCAN 算法均可获得满意的聚类结果.在SEQUOIA 2000的点数据集上执行DBSCAN,CURE 和K -MeanSCAN 这3种算法的时间代价在图11中给出.其中,DBACAN 算法在R*树索引基础上实现.在样本数量较少时(<10000),DBSCAN 算法性能较高;当样本数量继续增加时,采样技术使得CURE 和K -MeanSCAN 算法具有更好的伸缩性.Fig.10 Sensitivity analysis of k ′ Fig.11 Comparison of algorithm scalability图10 参数k ′敏感性分析 图11 算法的伸缩性比较实验denh Gaussian fittingcurve denh Gaussian fitting curve250642200150100500T i m e (s ) 0 10000 20000 30000 40000 50000 60000 Num of pints DBSCAN K -MeanSCAN CURE o f c l u s t e r s k ′。
