基于划分的K均值聚类算法
- 格式:pdf
- 大小:427.15 KB
- 文档页数:3
基于划分的聚类算法1.初始化:随机选择K个质心作为初始聚类中心。
2.分配:对于每个样本,计算其与K个聚类中心的距离,将其分配给距离最近的聚类。
3.更新:计算每个聚类中所有样本的平均值,更新聚类中心。
4.重复步骤2和3,直到聚类中心不再变化或达到预定的迭代次数。
K-means算法的优点是简单、高效,并且在大规模数据集上也能得到较好的结果。
然而,K-means算法也有一些缺点。
首先,算法对初始聚类中心的选择非常敏感,不同的初始聚类中心可能导致不同的聚类结果。
其次,K-means算法假设每个聚类的形状是球形的,对于非球形聚类效果不佳。
此外,K-means算法需要预先指定聚类的个数K,而对于未知聚类个数的情况下,很难确定合适的K值。
为了解决K-means算法的缺点,一些改进的基于划分的聚类算法被提出。
例如,K-medoids算法使用实际样本作为聚类中心,而不是计算样本的平均值。
这种方法更适用于非球形聚类。
另一个改进是谱聚类算法,它通过图论的方法将数据集转化为一个图,然后使用图划分的方法进行聚类。
除了K-means算法之外,还有一些其他的基于划分的聚类算法。
例如,二分K-means算法将数据集划分为两个聚类,然后逐步将每个聚类划分为更小的聚类,直到满足停止条件。
此外,基于密度的聚类算法(如DBSCAN)也是一种基于划分的聚类方法,它将数据集划分为不规则形状的聚类。
总之,基于划分的聚类算法是一种将数据集划分为不相交的子集的算法。
K-means算法是其中最常见的一种,但也存在一些缺点。
为了解决这些缺点,一些改进的基于划分的聚类算法被提出。
这些算法在不同的数据集和应用中都有广泛的应用。
k-means聚类方法1. K-means聚类方法的基本原理K-means聚类方法是一种基于划分的聚类算法,它将数据集划分为K 个簇,每个簇由与其中心距离最近的点组成。
K-means聚类方法的基本原理是:给定一组数据,将它们划分为K个簇,使得每个簇的内部距离最小,而簇之间的距离最大。
K-means算法通过迭代的方式,不断地调整簇的中心,以最小化每个簇内部的距离,从而实现最优的划分。
2. K-means聚类方法的优缺点K-means聚类方法具有计算简单、收敛快等优点,它可以将数据集划分为多个簇,每个簇内的数据点彼此具有较高的相似度,而簇与簇之间的数据点具有较低的相似度,从而有效地实现了数据分类。
但K-means聚类方法也有一些缺点,首先,K-means聚类方法的结果受初始值的影响较大,如果初始值不合理,可能导致聚类结果不理想;其次,K-means聚类方法只适用于线性可分的数据,如果数据不具有线性可分的特征,K-means聚类方法可能不能得到理想的结果;最后,K-means聚类方法没有考虑数据点之间的距离,因此可能会出现噪声数据点的情况,从而影响聚类结果。
3. K-means聚类方法的应用K-means聚类方法可以用于多种应用,如机器学习、数据挖掘、模式识别、图像处理等。
其中,最常见的应用是基于K-means聚类方法的聚类分析,用于将数据分成不同的组,以便更好地理解和分析数据。
此外,K-means聚类方法也可以用于多维数据可视化,以及探索数据中隐藏的模式和趋势。
K-means聚类方法还可以用于客户分类,以及市场细分,以更好地了解客户行为和需求。
此外,K-means聚类方法还可以用于语音识别,文本分类,图像分类等。
4. K-means聚类方法的参数调整K-means聚类方法的参数调整主要有两个:K值和距离度量标准。
K 值决定聚类的数量,距离度量标准决定两个点之间的距离。
参数调整的目的是为了让聚类结果尽可能满足用户的要求。
kmeans算法的原理
K-means算法是一种典型的基于划分的聚类算法,其原理是将数据集划分为K个簇,使得每个数据点都属于最近的簇,并且簇的中心是所有数据点的平均值。
K-means算法的原理可以分为以下几个步骤:
1. 初始化:选择要将数据集分成K个簇,并随机选择K个数据点作为初始簇中心。
2. 分配:将每个数据点分配到距离其最近的簇中心,每个数据点只能属于一个簇。
3. 更新:根据分配的数据点更新簇中心点,这是通过计算属于每个簇的数据点的平均值来实现的。
4. 重复:重复步骤2和3,直到簇中心点不再发生变化,或者达到预定的迭代次数。
K-means算法利用相似性度量方法来衡量数据集中所有数据之间的关系,将关系比较密切的数据划分到一个集合中。
该算法具有运算速度快,执行过程简单的优点,在很多大数据处理领域得到了广泛的应用。
以上是K-means算法的基本原理,可以咨询数学专业人士或查阅算法类书籍了解更多信息。
kmeans算法步骤K-means算法,也称为K-均值算法,是一种用于聚类的算法,其本质是将一组数据划分成K个不同的类别。
K-means算法在图像分割、客户分类、组织分组等领域中广泛应用。
K-means算法的核心思想是通过计算欧几里得距离的平方(点与点之间的距离的平方),将所有数据划分到K个不同的簇中。
算法的过程可以归纳为以下步骤:1.确定K个簇以及K个簇的中心点(质心)。
在开始算法之前,需要对数据进行分组。
首先,确定需要将数据分为多少个簇。
K的选择可能非常困难,因为不同的K值会导致不同的结果。
通常,可以基于业务需要、数据分析或以往的经验来选择K的值。
一个常见的方法是基于初始聚类的交互式方法来选择K,并通过观察聚类结果来选择最好的K值。
一般情况下,随机选择一些数据点作为初始质心。
2.计算距离并找到最接近的簇。
对于每个数据点,通过计算该点到所有质心的距离(通常是欧几里得距离平方),找到该点的最接近的质心,将其归入其指定的簇。
3.重新计算每个簇的质心。
对于每个簇,重新计算其质心的值。
计算的方法通常是对该簇中包含的数据点进行平均计算。
4.将数据重新分配到新的最接近的簇中。
重复上述步骤,不断重新计算每个簇的质心,直到不再有数据点被重新分配到新的簇中为止。
5.聚类结果的评估。
聚类结束后,需要对聚类结果进行评估。
可以使用误差平方和(SSE)或轮廓系数来进行评估。
K-means算法的优点是简单且易于理解,因此成为了聚类算法中应用最广泛的一种。
同时,由于其简单性和易于实现,它可以用于大型数据集的聚类。
但是,K-means算法也存在一些缺点。
最大的问题是它对簇的形状和大小的假设很强,通常会假设每个簇的形状为球形。
此外,它对数据噪声和离群值非常敏感,因此需要对数据进行预处理和噪声过滤。
总之,K-means算法是一种广泛应用于数据聚类的算法。
它通过将相似的数据点自动划分到一起,可以帮助我们更好地理解和分析数据。
虽然算法存在一些缺陷,但在实际数据分析中,它仍然是一种非常有用的工具。
5 聚类之层次聚类基于划分的聚类(k、层次聚类1、层次聚类的原理及分类1)层次法(Hierarchicalmethods )先计算样本之间的距离。
每次将距离最近的点合并到同一个类。
然后,再计算类与类之间的距离,将距离最近的类合并为一个大类。
不停的合并,直到合成了一个类。
其中类与类的距离的计算方法有:最短距离法,最长距离法,中间距离法,类平均法等。
比如最短距离法,将类与类的距离定义为类与类之间样本的最短距离。
层次聚类算法根据层次分解的顺序分为:自下底向上和自上向下,即凝聚的层次聚类算法和分裂的层次聚类算法agglomerative 和divisive ),也可以理解为自下而上法bottom-up )和自上而下法(top-down )。
自下而上法就是开始每个个体(object )都是一个类,然后根据linkage 寻找同类,最后形成一个“类” 。
自上而下法就是反过来,开始所有个体都属于一个“类”,然后根据linkage 排除异己,劣之分,只是在实际应用的时候要根据数据特点以及你想要的“类”的个数,来考虑是自上而下更快还是自下而上更快。
最后每个个体都成为一个“类” 。
这两种路方法没有孰优孰至于根据Linkage 判断“类”的方法就是最短距离法、最长距离法、中间距离法、类平均法等等(其中类平均法往往被认为是最常用也最好用的方法,一方面因为其良好的单调性,另一方面因为其空间扩张/浓缩的程度适中)。
为弥补分解与合并的不足,层次合并经常要与其它聚类方法相结合,如循环定位。
2)Hierarchical methods 中比较新的算法有BIRCH( BalancedIterative Reducingand Clustering Using Hierarchies 利用层次方法的平衡迭代规约和聚类)主要是在数据量很大的时候使用,而且数据类型是numerical 。
首先利用树的结构对对象集进行划分,然后再利用其它聚类方法对这些聚类进行优化;ROCK ( AHierarchical ClusteringAlgorithm for Categorical Attributes )主要用在categorical 的数据类型上;Chameleon(A HierarchicalClustering AlgorithmUsing Dynamic Modeling )里用到的linkage 是kNN (k-nearest-neighbor)算法,并以此构建一个graph,Chameleon 的聚类效果被认为非常强大,比BIRCH 好用,但运算复杂度很高,0(22)。
常规聚类算法常规聚类算法是一种重要的数据分析方法,可以帮助我们对大规模数据进行有效的分类和归纳。
通过对数据进行聚类,我们可以发现数据中的隐藏模式、规律和关系,从而为后续的数据挖掘、预测和决策提供有力支持。
常规聚类算法主要分为基于划分的聚类算法、基于层次的聚类算法和基于密度的聚类算法。
每种算法都有其独特的特点和适用场景,下面就分别进行介绍。
基于划分的聚类算法主要包括K-means算法和K-medoids算法。
K-means算法是一种常用且广泛应用的聚类算法,它将数据分成K个簇,每个簇的中心点代表了该簇的平均值。
该算法通过迭代的方式,将数据点不断归类到离其最近的簇中,直到达到稳定状态。
K-medoids算法是一种改进的K-means算法,它将簇的中心点定义为簇中所有数据点中与其他点的平均距离最小的点,从而可以更准确地划分簇。
基于层次的聚类算法主要包括凝聚层次聚类算法和分裂层次聚类算法。
凝聚层次聚类算法从每个数据点作为一个簇开始,然后通过计算两个最相似簇之间的距离来合并簇,直到形成一个大的簇。
分裂层次聚类算法则相反,从一个大的簇开始,然后通过计算簇中数据点之间的距离来分裂簇,直到形成多个小的簇。
这种算法的优点是可以在不同的层次上进行聚类,从而可以灵活地控制聚类的粒度。
基于密度的聚类算法主要包括DBSCAN算法和OPTICS算法。
DBSCAN算法是一种基于密度的聚类算法,它通过确定数据点的密度来划分簇,具有自动确定簇数和可处理噪声的优点。
OPTICS算法是DBSCAN算法的扩展,它通过将数据点的密度和可达距离进行排序,形成一个密度可达图,并根据该图来划分簇。
这种算法可以更好地处理数据中的离群点和噪声。
在使用常规聚类算法时,我们需要注意数据的选择和预处理。
合适的数据选择和预处理可以提高聚类算法的效果和准确性。
同时,我们还需要关注聚类结果的解释和评估。
解释聚类结果可以帮助我们理解数据中的模式和关系,评估聚类结果可以帮助我们判断算法的优劣和稳定性。
聚类分割算法聚类分割算法是一类常用于将数据集划分成具有相似特征的子集的方法。
这些算法主要用于无监督学习,即在没有先验标签的情况下,自动发现数据集内在的模式。
以下是一些常见的聚类分割算法:1. K均值聚类(K-Means Clustering):- K均值是最常见的聚类算法之一。
它将数据集分为K个簇,每个簇由其质心表示。
算法的目标是使每个数据点到其所属簇的质心的距离最小化。
2. 层次聚类(Hierarchical Clustering):-层次聚类根据数据点之间的相似性构建树状结构。
可以通过聚合或分割来创建簇。
分为凝聚式层次聚类(自底向上)和分裂式层次聚类(自顶向下)。
3. DBSCAN(Density-Based Spatial Clustering of Applications with Noise):- DBSCAN基于密度的聚类算法,能够发现具有足够密度的区域,并将稀疏区域视为噪声。
它不需要预先指定簇的数量。
4. Mean Shift聚类:- Mean Shift是一种基于梯度上升的聚类算法。
它通过不断迭代调整数据点的位置,使其移向密度最大的区域,从而找到簇的中心。
5. OPTICS(Ordering Points To Identify the Clustering Structure):- OPTICS是一种基于密度的聚类算法,类似于DBSCAN,但允许在数据集中存在不同密度的区域,并通过产生一系列密度相关的点来表示簇。
6. 谱聚类(Spectral Clustering):-谱聚类利用数据集的谱信息,通过将数据投影到低维子空间来执行聚类。
它在处理非凸形状的簇和图分割问题时效果较好。
7. 模糊聚类(Fuzzy Clustering):-模糊聚类考虑了数据点与簇的隶属度,而不是将每个数据点硬性地分配到一个簇。
模糊c均值(FCM)是模糊聚类的一个典型算法。
这只是聚类分割算法的一小部分,每个算法都有其适用的场景和限制。
k均值和层次聚类的异同k均值和层次聚类是两种常用的聚类算法,它们在数据挖掘和机器学习中被广泛应用。
本文将从算法原理、聚类过程、优缺点等方面进行对比,探讨k均值和层次聚类的异同点。
我们来了解一下k均值聚类算法。
k均值聚类是一种基于距离的聚类算法,其思想是将数据集划分为k个簇,使得每个样本点都属于离其最近的簇。
算法的过程如下:接下来,我们来介绍层次聚类算法。
层次聚类是一种自底向上或自顶向下的聚类算法,可以得到不同层次的聚类结果。
自底向上的层次聚类又称为凝聚型层次聚类,其思想是从单个样本开始,逐步合并相似的簇,直到形成一个大的簇。
自顶向下的层次聚类又称为分裂型层次聚类,其思想是从所有样本开始,逐步分裂成小的簇,直到形成单个样本的簇。
层次聚类的优点是不需要预先指定聚类个数,可以得到聚类的层次结构。
然而,它也存在一些缺点,比如计算复杂度较高,不适用于大规模数据集。
k均值和层次聚类在算法原理上有一些异同。
k均值聚类是一种划分式聚类算法,将数据集划分为不相交的簇;而层次聚类是一种层次式聚类算法,将数据集划分为树形的簇结构。
k均值聚类通过迭代优化聚类中心来实现簇的划分,而层次聚类通过簇的合并或分裂来实现聚类过程。
此外,k均值聚类需要预先指定聚类个数k,而层次聚类不需要预先指定聚类个数。
在聚类过程中,k均值和层次聚类也存在一些异同。
k均值聚类是一种迭代的优化过程,每次迭代都需要计算样本与聚类中心的距离,并重新分配样本到簇中。
而层次聚类是一种自底向上或自顶向下的合并或分裂过程,每次合并或分裂都需要计算簇与簇之间的距离。
在计算复杂度上,k均值聚类的时间复杂度为O(tkn),其中t为迭代次数,k为聚类个数,n为样本个数;而层次聚类的时间复杂度较高,通常为O(n^3)或O(n^2logn)。
此外,k均值聚类的空间复杂度较低,只需要存储聚类中心和样本的标记;而层次聚类的空间复杂度较高,需要存储距离矩阵或树形结构。
我们来总结一下k均值和层次聚类的优缺点。
列举常用聚类算法聚类算法是一种将数据集中的相似数据分组的方法。
它是无监督学习的一种应用,可以在没有标签或类别信息的情况下对数据进行分类。
在机器学习和数据挖掘中,聚类算法被广泛应用于数据分析、图像处理、模式识别等领域。
本文将列举常用的聚类算法。
一、K均值聚类算法(K-means Clustering)K均值聚类算法是一种基于距离度量的聚类方法,它将数据集划分为K 个簇,每个簇包含距离其它簇最近的点。
该算法首先随机选择K个点作为初始质心,然后将每个点分配到与其距离最近的质心所在的簇中,并计算每个簇内所有点的平均值作为新的质心。
重复以上过程直到质心不再改变或达到预定迭代次数。
二、层次聚类算法(Hierarchical Clustering)层次聚类算法是一种自下而上或自上而下逐步合并或拆分簇来建立层次结构的方法。
该算法有两种实现方式:凝聚层次聚类和分裂层次聚类。
凝聚层次聚类从每个数据点开始,将它们逐步合并成越来越大的簇,直到所有点都被合并为一个簇。
分裂层次聚类从整个数据集开始,将其逐步拆分成越来越小的簇,直到每个簇只包含一个点。
三、DBSCAN聚类算法(Density-Based Spatial Clustering of Applications with Noise)DBSCAN聚类算法是一种基于密度的聚类方法,它可以识别任意形状的簇,并能够自动排除离群值。
该算法首先选择一个未访问的核心点作为起始点,并找到其可达范围内的所有点,并将它们加入同一簇中。
然后继续寻找未访问的核心点,并重复以上过程直到所有核心点都被访问完毕。
四、谱聚类算法(Spectral Clustering)谱聚类算法是一种基于图论和线性代数的聚类方法,它将数据集看作是一个图,在图上进行划分。
该算法首先构建一个相似度矩阵或邻接矩阵,并通过特征值分解或奇异值分解来获取特征向量和特征值。
然后将特征向量作为新的数据集,使用K均值或层次聚类等方法对其进行聚类。
k均值聚类的实现步骤1. 简介k均值聚类(k-means clustering)是一种常用的无监督学习算法,用于将数据集划分为k个不重叠的类别。
该算法通过寻找数据集中各个样本之间的相似性,将相似的样本归为一类,从而实现聚类分析。
2. 算法步骤k均值聚类算法主要包含以下几个步骤:步骤1:初始化首先需要确定要划分的类别数k,并随机选择k个样本作为初始聚类中心。
这些聚类中心可以是随机选择的,也可以根据领域知识或经验来确定。
步骤2:分配样本到最近的聚类中心对于每个样本,计算它与各个聚类中心之间的距离,并将其分配到距离最近的聚类中心所代表的类别。
步骤3:更新聚类中心对于每个聚类,计算该类别内所有样本的平均值,作为新的聚类中心。
步骤4:重复步骤2和步骤3重复执行步骤2和步骤3,直到满足停止条件。
停止条件可以是达到最大迭代次数、聚类中心不再发生变化等。
步骤5:输出聚类结果k均值聚类算法输出每个样本所属的类别,即完成了对数据集的聚类分析。
3. 距离度量在k均值聚类算法中,需要选择合适的距离度量方法来计算样本之间的相似性。
常用的距离度量方法包括欧氏距离、曼哈顿距离和余弦相似度等。
欧氏距离欧氏距离是最常用的距离度量方法之一,它表示两个点在n维空间中的直线距离。
假设有两个点A(x1, y1)和B(x2, y2),则它们之间的欧氏距离为:d(A, B) = sqrt((x2 - x1)^2 + (y2 - y1)^2)曼哈顿距离曼哈顿距离是另一种常用的距离度量方法,它表示两个点在n维空间中沿坐标轴方向的绝对差值之和。
假设有两个点A(x1, y1)和B(x2, y2),则它们之间的曼哈顿距离为:d(A, B) = |x2 - x1| + |y2 - y1|余弦相似度余弦相似度是用于衡量两个向量之间的相似性的度量方法,它通过计算两个向量的夹角余弦值来确定它们的相似程度。
假设有两个向量A和B,则它们之间的余弦相似度为:sim(A, B) = (A·B) / (||A|| * ||B||)其中,A·B表示向量A和向量B的内积,||A||和||B||分别表示向量A和向量B 的模长。
基于划分的K -means 聚类算法丁丽1,孙高峰2(1.亳州职业技术学院信息工程系; 2.安徽电力亳州供电公司电力调度控制中心,安徽亳州236800)①摘要:文中首先介绍了聚类分析的涵义,然后分析K -means 算法的基本思想以及划分聚类的三个关键点,最后通过具体的实例讲解了K -means 算法的实现。
关键词:聚类分析;K -means 算法;簇中心中图分类号:TP301文献标识码:A 文章编号:1671-380X (2013)06-0028-03Research of K -means Clustering Algorithm Based on PartitionDING Li 1,SUN Gao -feng 2(1.Department of Information Engineering ,Bozhou Vocation and Technical College ;2.Power Dispatching Control Center ,Bozhou Power Supply Company ,Anhui Electric ,Bozhou 236800,China )Abstract :This paper firstly introduces the definition of cluster analysis ,then analyzes the general idea of K -means algorithm and the three crucial points of typifying clustering.Finally explains the realization of K -means al-gorithm through a concrete example.Key words :Cluster Analysis ;K -means Algorithm ;Cluster Center 随着信息技术的快速发展及广泛推进,数据挖掘成为当今社会研究的一个热点领域,聚类分析是数据挖掘中的一项核心技术,它通过研究数据的分布特征来发现数据背后隐藏的事物内部规律。
聚类算法有很多种,每一种算法都有自己的独特之处。
K -means 算法是聚类分析的经典算法之一,文中主要对K -means 算法进行阐述。
1聚类分析概述聚类分析是人的一项重要活动,比如,小孩子通过不断学习都能够区分动物和植物,也能够区分鸡和狗。
聚类与分类不同,分类是按照一定的标准把数据分成不同的类别,聚类是通过观察数据的特征寻找这个标准。
聚类分析的核心是聚类,即将物理或抽象对象的集合分成相似的对象类的过程。
通过聚类把数据分成不同的集合,同一个集合中的数据对象彼此相似,不同数据集合的对象之间彼此相异[1]。
形成聚类的原则是使类内部的相似性最大,类间的相似性最小。
聚类的研究方法有很多,用的比较多的是K -means (K -平均值)、BIRCH 算法、clara 算法、eLIQuE 算法、chameleon (变色龙)算法等。
聚类可以对迅猛增长的数据加以组织,人们通过聚类可以发现一些数据分布的特征,因此成为比较活跃的研究课题。
目前,很多领域已经成功地应用了该项技术,包括市场研究、人工智能和图像处理、生物学、数据压缩等领域[2]。
例如,在生物学领域,聚类可以自动对物种分类,依据是物种特征;还可以更好地理解生物学中基因的功能。
在商业中,市场分析员通过聚类分析可以很容易发现顾客库中不同的顾客群。
聚类还可以应用于客户关系管理,对从接触点收集到的数据进行分析,可以得出有价值的知识,以便用于改进营销方案、制定定价和促销策略。
2K -means 算法2.1K -means 算法基本思想K -means 算法,也被称为K -均值,是最常用、最著名的一种聚类算法。
K -means 算法是把n 个对象分成K 个簇,用簇中对象的均值表示每个·82·第35卷第6期2013年6月宜春学院学报Journal of Yichun College Vol.35,No.6June.2013①收稿日期:2013-02-27作者简介:丁丽(1983-),女,安徽亳州人,助教,硕士,主要从事数据挖掘及电子商务研究,Email :dingli0206@ ;孙高峰(1983-),男,安徽亳州人,工程师,学士,主要从事供电公司地区电网调度工作。
簇的质心,通过迭代使每个簇内的对象不再发生变化为止。
这时准则函数达到最优,每个簇内相似度高,簇间相似度低。
其过程描述如下:(1)首先,随机地选择K 个对象,代表要分成的K 个簇的初始均值或中心。
(2)计算其余对象与各个均值的距离,然后把它们分别划分到距离中心最近的簇中。
(3)计算每个簇中所有对象的平均值,作为每个新的簇中心(4)计算所有对象与新的K 个中心的距离,根据“距离中心最近”原则,重新划分所有对象到各个簇中(5)重复(3)、(4),直至所有簇中心不变为止。
2.2K -means 算法划分聚类的三个关键点(1)数据对象的划分①距离度量的选择K -means 算法比较适合处理连续型属性,对离散型属性不适合。
在计算数据对象之间的距离时要选择合适的相似性度量。
比较著名的距离度量是欧几里得距离和曼哈顿距离[3],其中最常用的是欧几里得距离,其公式如下:d x i ,x ()j =∑dk =1x ik -x ()jk槡2(2-1)这里x i ,x j 表示两个d 维数据对象,x i =(x i 1,x i 2,…,x id ),x j =(x j 1,x j 2,…,x jd ),d (x i ,x j )表示对象x i 和x j 之间的距离,距离越小,二者越相似;距离越大,二者差异就越大。
根据欧几里得距离,计算出每一个数据对象与各个簇中心的距离。
②选择最小距离,即如果d (p ,m i )=min {d (p ,m 1),d (p ,m 2),…,d (p ,m k )}那么,p ∈c i ;P 表示给定的数据对象;m 1,m 2,…,m k 分别表示簇c 1,c 2,…,c k 的初始均值或中心;(2)准则函数的选择。
K -means 算法采用平方误差准则函数来评价聚类性能,其公式如下:E =∑ki =1∑p ∈Cip -m i2(2-2)E 表示数据库中所有对象的平方误差和,P 表示给定的数据对象,m i 表示簇c i 的均值。
(3)簇中心的计算。
用每一簇的平均值作为计算相似度簇中心的依据,其公式如下:m i =1n i ∑p ∈C ip ,i =1,2,…,k (2-3)这里假设簇c 1,c 2,…,c k 中的数据对象个数分别为n 1,n 2,…,n k 。
2.3K -means 算法的实现(1)划分数据对象。
选择k 个数据对象作为初始k 个聚类的中心,根据欧几里得距离公式,依次比较每个数据对象与各个中心的距离,选择距离中心最近的簇,依次把n 个对象划分到k 个簇中[4]。
完成第一次划分之后,重新计算新的簇的中心,然后开始重新划分数据对象,直到新的簇中心不再发生变化,停止迭代。
(2)计算簇中心。
每次划分数据对象之后,都要重新计算簇中心,直到簇中心不再发生变化为止。
2.4K -means 算法实例现有一需要聚类的数据集合:{2,4,10,20,12,30,6,3,15,27};假设需要分成两个簇,即k =2,K -means 算法聚类过程如下:(1)选择数据集合的前两个元素作为初始簇中心,即m 1=2,m 2=4。
(2)对剩下的数据对象,利用欧几里得距离,分别计算它们与各个簇中心的距离,并分配给最近的簇。
对数据元素10:d (10,m 1)=d (10,2)=8,d (10,m 2)=d (10,4)=6,d (10,m 1)>d (10,m 2),因此把{10}分配给簇C 2;对数据元素20:d (20,m 1)=d (20,2)=18,d (20,m 2)=d (20,4)=16,d (20,m 1)>d (20,m 2),因此把{20}分配给簇C 2;对数据元素12:d (12,m 1)=d (12,2)=10,d (12,m 2)=d (12,4)=8,d (12,m 1)>d (12,m 2),因此把{12}分配给簇C 2;对数据元素30:d (30,m 1)=d (30,2)=28,d (30,m 2)=d (30,4)=26,d (30,m 1)>d (30,m 2),因此把{30}分配给簇C 2;对数据元素6:d (6,m 1)=d (6,2)=4,d (6,m 2)=d (6,4)=2,d (6,m 1)>d (6,m 2),因此把{6}分配给簇C 2;对数据元素3:d (3,m 1)=d (3,2)=1,d (3,m 2)=d (3,4)=1,d (3,m 1)=d (3,m 2),把{3}分配给簇C 1;对数据元素15:d (15,m 1)=d (15,2)=13,d (15,m 2)=d (15,4)=11,d (15,m 1)>d (15,m 2),因此把{15}分配给簇C 2;对数据元素27:d (27,m 1)=d (27,2)=25,d (27,m 2)=d (27,4)=23,d (27,m 1)>d (27,m 2),因此把{27}分配给簇C 2;·92·第6期丁丽,孙高峰:基于划分的K -means 聚类算法第35卷所以,C1={2,3},C2={4,6,10,12,15,20,27,30}。
(3)开始进行第一次迭代。
重新计算簇中心:m1=2.5,m2=15.5,重新计算各个数据元素与新的簇中心的距离。
对数据元素2:d(2,m1)=d(2,2.5)=0.5,d(2,m2)=d(2,15.5)=13.5,d(2,m1)<d(2,m2),因此把{2}分配给簇C1;对数据元素4:d(4,m1)=d(4,2.5)=1.5,d(4,m2)=d(4,15.5)=11.5,d(4,m1)<d(4,m2),因此把{4}分配给簇C1;对数据元素10:d(10,m1)=d(10,2.5)=7.5,d(10,m2)=d(10,15.5)=5.5,d(10,m1)>d(10,m2),因此把{10}分配给簇C2;对数据元素20:d(20,m1)=d(20,2.5)=17.5,d(20,m2)=d(20,15.5)=4.5,d(20,m1)>d(20,m2),因此把{20}分配给簇C2;对数据元素12:d(12,m1)=d(12,2.5)=9.5,d(12,m2)=d(12,15.5)=3.5,d(12,m1)>d(12,m2),因此把{12}分配给簇C2;对数据元素30:d(30,m1)=d(30,2.5)=27.5,d(30,m2)=d(30,15.5)=14.5,d(30,m1)>d(30,m2),因此把{30}分配给簇C2;对数据元素6:d(6,m1)=d(6,2.5)=3.5,d(6,m2)=d(6,15.5)=9.5,d(6,m1)<d(6,m2),因此把{6}分配给簇C1;对数据元素3:d(3,m1)=d(3,2.5)=0.5,d(3,m2)=d(3,15.5)=12.5,d(3,m1)<d(3,m2),因此把{3}分配给簇C1;对数据元素15:d(15,m1)=d(15,2.5)=12.5,d(15,m2)=d(15,15.5)=0.5,d(15,m1)>d(15,m2),因此把{15}分配给簇C2;对数据元素30:d(27,m1)=d(27,2.5)=24.5,d(27,m2)=d(27,15.5)=11.5,d(27,m1)>d(27,m2),因此把{27}分配给簇C2;所以,第一次迭代后的结果为:C1={2,3,4,6},C2={10,12,15,20,27,30}。