k均值聚类_k均值聚类

k均值聚类由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“k均值聚类”。

K-均值聚类算法

摘要关于对生活中各种各样的数据的聚类分类问题己经成为众多学者的研究热题之一。聚类方法有很多种，其中最简单的形式便是划分式聚类，划分式聚类试图将给定的数据集合分割成不相交的子集，使具体的聚类准则是最优的。一种最流行的基于最小聚类误差平法和的聚类方法是K-均值算法。然而，K-均值算法是一个局部搜索的算法，它存在一些严重的不足，比如K值需要预先确定、聚类结果的好坏依赖于初始点的选取。本文对聚类进行了简单的介绍，并对K-均值算法进行了研究分析。

关键词 数据挖掘；聚类分析；K-均值聚类算法

1.引言

在因特网无处不在的今天，人们所面临的形形色色的数据量呈急速增长状态。然而，在数据如此海量的同时，人们却缺乏对这些数据中所隐含的信息或知识的充分理解。在这种需求情况下，数据挖掘技术应运而生。

聚类分析作为数据挖掘在实际应用中的主要任务之一，是数据挖掘中一个很活跃的研究领域，与其他学科的研究方向具有很好的的交叉性。在识别数据内部结构方面具有极其重要的作用。

K-均值聚类算法是聚类分析中的一种基本划分式方法。由于其算法简便易懂，且在计算速度上具有无可比拟的优势，通常被作为大样本聚类分析的首选方案。

2.数据挖掘中聚类分析算法的相关介绍

聚类分析是多元统计分析方法中的一种，是非监督模式识别的一个重要分支。所谓聚类就是按照事物的某些属性，把事物聚集成簇，使簇内的对象之间具有较高的相似性，而不同簇的对象之间的相似程度较差。聚类是一个无监督的学习过程，它同分类的根本区别在于:分类是需要事先知道所依据对象的类别特征，而聚类是要找到这个对象的类别特征，因此，在很多应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数据的基础。

2.1 关于聚类分析的概述

聚类问题是普遍存在于众多领域的基本问题，如模式识别、图像处理、机器学习和统计学等。聚类的基本形式定义为在已给的数据集合中寻找数据点集的同类集合。每一个集合叫做一个类，并确定了一个区域，在区域中对象的密度高于其他区域中的密度。其他区域中的密度。

Everitt在1974年给出的定义:

聚类就是“将数据分成许多类簇，其中一个类簇内的实体是相似的，不同类簇的实体是不相似的;一个类簇是测试空间中点的会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离;类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离。”

2.2 聚类分析中的数据类型

在这里，给出聚类分析中常用的数据结构，假设我们要进行聚类的实体集合共包含n个实体，每个实体有p个属性，大多数的聚类算法在内存中都采用以下两种数据结构网:

(1)数据矩阵

数据矩阵即实体一属性的结构，我们用矩阵中的行来表示每一个实体，列来表示某种属性，则n个实体，p个属性的集合可以用一个n×p维的矩阵来表示，第i个实体的第j个属性在矩阵中表示为xij，数据矩阵如下：

x11xijx1px21x22x2p

xn1xn2xnp

(2)相异度矩阵

相异度矩阵用来存储的是实体之间的差异性，n个实体的相异度矩阵表示为n×n维的矩阵，用d（A，B）来表示实体A与实体B的相异性，一般来讲，是一种量化的表示方式，则含有n个实体的集合X=x1,x2,xn的相异度矩阵表示如下:

0d(x,x)021d(x3,x1)d(x3,x2)0 d(xn,x1)d(xn,x2)0

在这里，d(xi,xj)为某种相似性度量函数，一般情况下为非负值。

2.3聚类算法的分类

现有的聚类算法中，没有任何一种算法可以普遍适用于揭示各式各样的数据集合的数据结构，目前存在众多的聚类算法，一般情况下我们根据所要进行聚类数据的数据类型、聚类的目的及其应用，可以选择不同的聚类算法。目前存在的聚类分析算法大致上可分为层次聚类算法、划分式聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法等，另外，根据类簇间的重叠程度可分为硬性聚类和模糊聚类。

3．K-均值聚类算法的研究与分析

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

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

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

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

输入:数据集X=x1,x2,xn，聚类数目k;

输出:k个类簇Cj，j=1，2，„,k，[stepl]令I=1，随机选取k个数据点作为k个类簇的初始簇中心，mj(I)，j=1，2，„，k;

[step2]计算每一个数据点与这k个簇中心的距离d(xi,mj(I))，i=1，2，„，n，j=1，2，„，k，如果满足

d(xi,mj(I))mind(xi,mj(I)),j1,2,k

则xiCj；

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

1mj(I1)Nji1

xiCjx,j1,2,k iNj

[step4]判断:若mj(I1)mj(I),j1,2,k,则I=I+1，返回step2;否则，算法结束。K-均值聚类算法在执行过程中还可以加入聚类准则函数来终止迭代过程，一般采用聚类误差平方和准则函数，即在上面算法流程中的step4中计算聚类误差平方和J，然后加入判断，若两次的J值没有明显变化，则说明J值已经收敛，结束算法，否则转入step2继续执行。

具体流程如下：

[Stepl][初始化]随机指定k个聚类中心m1,m2,mk；

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

1[SteP3][修正簇中心]重新计算各簇中心miNi

[Step4][计算偏差] Jx,i1,2,k； ijj1Nii1j1knixijmi； 2

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

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

3.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-均值聚类算法在待聚类数据量较大的时候并不适用。

4.总结及展望

本文简单介绍了数据挖掘中的聚类。聚类分析是数据挖掘领域的研究热点之一，主要用于发现数据之间的分布信息及内在结构，聚类分析既可以作为一个独立的分析数据的技术，又可以为其他数据挖掘算法完成数据预处理的步骤。因此，聚类分析是一项在实际应用中十分重要的研究课题。

还介绍了K-均值算法的一些研究分析。K-均值聚类算法是聚类分析算法中一种最常用的聚类方法之一。由于其算法思想简单，利用反复迭代的技术来得到最佳聚类中心，要注意，这里的“最佳”聚类中心往往只是局部最优解，K-均值聚类算法常常会陷入局部最优解而结束算法的迭代过程。

经典的K-均值聚类算法有需要改进之处，比如算法的伸缩性、算法如何能识别任意形状的簇，算法对于初始点的敏感性等等。在以后的工作中可以详细分析目前现有的改进算法加以研究，提取每种算法的创新之处。其次，在确定K值的问题上，还可以结合许多其它方法，来达到实现K值的目的，再应用K-均值聚类算法进行聚类。最后，可以尝试把算法应用到具体的实际问题中，扩展应用领域，来检验算法的可行性。