本科毕业论文 数据挖掘K均值算法实现

本科生毕业论文设计

数据挖掘K-均值算法实现

作者姓名： 郝蓓 指导教师： 郭瑞强

所在学院： 数学与信息科学学院 专业（系）： 计算机科学与技术 班级（届）： 2013届计算机班

二零一三年五月二日

目 录

中文摘要、关键字 .......................................................... 1 1 绪论 ................................................................... 3 1.1 本文研究的背景和意义 ................................................ 3 1.2 聚类分析国内外研究现状 .............................................. 5 1.3 本文所做的主要工作 .................................................. 7 2 聚类算法的分析与研究 ................................................... 8 2.1 数据挖掘简介 ........................................................ 8 2.2 聚类的基本知识 ...................................................... 8 2.2.1 类的定义及表示 ................................................... 8 2.2.2 聚类的相似度量方法 ............................................... 9 2.2.3 聚类间的距离测度函数 ............................................ 11 2.2.4 聚类分析的一般步骤 .............................................. 12 2.3 常用的聚类分析的方法介绍 ........................................... 13 2.3.1 基于划分的方法 .................................................. 13 2.3.2 基于密度的方法 .................................................. 13 2.3.3 基于层次的算法 .................................................. 13 2.3.4 基于模型的算法 .................................................. 14 2.3.5 基于网格的算法 .................................................. 14 2.4 常用的划分聚类算法的分析 ........................................... 14 2.4.1 K-均值聚类算法 .................................................. 14 2.4.2 K-中心聚类法 .................................................... 15 2.5 本章小结 ........................................................... 16 3 K一均值聚类算法的研究 ................................................ 17 3.1 K-均值聚类算法介绍 ................................................. 17 3.1.1 K一均值聚类算法基本思想 ........................................ 17 3.1.2 K一均值聚类算法主要流程 ........................................ 17 3.2 K-均值聚类算法的主要缺陷及分析 ..................................... 18 3.3 本章小结 ........................................................... 19 4 K-均值聚类算法的实验 .................................................. 20

4.1 实验结果分析 ....................................................... 20 4.2 本章小结 ........................................................... 25 5 总结与展望 ............................................................ 26 5.1 总结 ............................................................... 26 5.2 展望 ............................................................... 26 参考文献 ................................................................. 28 英文摘要、关键字 ......................................................... 31

论文题目：数据挖掘K均值算法实现

数学与信息科学学院 计算机科学与技术专业

指导教师：郭瑞强

作者：郝蓓

摘要：随着互联网技术的迅速发展，现在的人们每一天都会面临例如文本、图像、视频、音频等各种数据形式，这些数据的数据量的大小是很惊人的。怎样能够很快的并且高效地从这些大量数据中挖掘提炼出它所蕴含的价值，成为现在人们特别关注并且需要马上解决的问题。数据挖掘(Data Mining，DM)正是因为这个才慢慢诞生出来。数据挖掘经过一段时间的迅猛发展，诞生出了大量的理论结果和现实使用成果，它提供了许多工具和卓有成效的方法来解决问题。数据挖掘中有一项是很重要的研究领域，那就是聚类分析，这是一种对数据进行按照不同的依据将数据进行分组或者将数据进行划分的方式。聚类无论在生物科学研究，还是在商务贸易中、图像分析处理、网页内容分类等其他日常生活的领域都得到了很好的应用。

根据使用的数据类型、使用的功能的不同、聚类需求的不同，目前的聚类算法大概有以下几种：基于划分的算法、基于层次的算法、基于密度的的算法、基于模型的算法以及基于网格的算法。在这之中，基于划分的K-均值聚类算法是目前研究最成熟传统经典的算法。K-均值算法的应用领域特别广泛，覆盖范围涉及语音频率压缩还有图像及文本聚类，另外在数据预处理和神经网络结构的任务分解等也发挥其重要用途。本文所做的工作有：

本文第一部分：详细介绍了本次论文研究的背景和目的，以及所选题目的考虑思路，还有在当前国际形式下，聚类分析在国际上的地位及国内外研究成果综述，最后介绍了本论文算法实现的内容和论文整体布局安排。

第二部分：首先详细描述了数据挖掘的来源发展还有它的概念定义，下面主要介绍聚类分析，包括聚类的基本概念原理等基础性知识，介绍了聚类算法的内部特性，详细描述了几种目前聚类分析的方法，总结比较各个方法的特点及其长短处。最后对本论文所研究的基于划分的聚类算法进一步讨论都有哪几种算法。

第三部分：这是本论文的重点，本论文所要讨论的K-均值算法，从它的概念基本思想算法流程等方面对K-均值算法进行详细系统的介绍，并且详细分析了它的优缺点。K- 1

均值算法对初始值的选取比较敏感和对数据的输入顺序不同也会影响聚类等问题，所以本文针对该问题进行了验证，通过实验证明了这两个因素对聚类结果会有哪些影响。实验表明，K-均值算法对初始值和数据输入顺序很敏感，但是这两个对聚类结果影响的方面不同。本文通过六个实验结果分析得出，改变初始点，对聚类结果的影响不大，只是会改变迭代次数，而且选取初始的连续的几个数据为初始点迭代次数最少，虽然中间间隔的几个数据作为初始点也出现了最小的迭代次数，但这对数据集来说有太多的不确定性，所以还是选择最开始那几个数据为数据聚类初始点；对于改变数据集的输入顺序，聚类结果与之前的有很大的改变，实验结果说明输入顺序不同既影响了聚类结果也影响了迭代次数。通过这些结论为以后用户使用K-均值算法提供了很好的帮助，也为该算法的改进提供了参考。

关键词：数据挖掘 聚类分析 K-means算法 实验验证

2

2.3 常用的聚类分析的方法介绍

目前聚类分析算法的应用技术日趋成熟，已经有很多的聚类算法被提出来，但是算法种类增多，同时这些算法的融合会越来越明显，使得各种算法的界限不明显，但是目前大家默认的有五种划分方法,分别是：以划分为基础的算法(Partitioning Methods)、以密度为基础的算法(Density．basedMethods)、以层次的为基础的算法(HierarchicalMethods)、以模型为基础的算法(Model．based Methods)、以网格为基础的算法(Grid．based Methods)。

2.3.1 基于划分的方法

划分算法[11]的基本思想就是通过迭代的方法将含有M个数据对象的数据集分成K个簇。具体步骤是，用户首先给定所要划分的簇的个数K，算法先进行初步划分为K组，然后用迭代的方法反复再进行分组，每次新得到的分组比前一次要优化，是否优化的判定标准是同组数据之间以及不同组数据之间的相似程度，同组相似程度越大组间相似程度越小分组越优化，目前常用的算法有K-means算法、K-medoid算法以及以它们为基础的算法的各种改进。以划分为基础的聚类算法将在后面的章节做重点介绍。

2.3.2 基于密度的方法

基于密度的算法[12]与其他的算法最大的不同在于不是以元素间的距离作为判断标准，而是根据数据对象的分布密度来判断，正因为如此该算法有助于发现数据集中的噪声数据，减少噪声数据对聚类结果的影响，所以密度的方法可以对任意形状的簇聚类，基本思想是将密度较大的区域识别出来，形成连在一起的密度域，并将他们归为一类。目前比较传统的的以密度为基础的聚类的方法有三种，这三种算法包括是：GDBSCAN算法、OPTICS算法、DENCLUE算法。其中OPTICS算法不是直接进行聚类，而是计算出一个簇的次序，以方便自动聚类和交互聚类分析。DBSCAN算法是检验数据对象周围的数据个数是否超过了用户规定的范围。DENCLUE算法是通过影响函数来判断空间密度的方法，这就对处理高维数据非常方便有效，所以该方法对用户的参数的个数与种类非常敏感。

2.3.3 基于层次的算法

层次聚类算法[1]有两种不同的分解形式，分别是分裂和凝聚，它们的区别是聚类的方向不同。其中分裂的层次算法也是一种自顶向下的聚类方法，顾名思义分裂的过程就是将一个分裂为多个，一开始是将所有的数据放进一个初始的簇中，对这个簇进行分

13

裂，每次迭代都会有一个更小的簇被分裂出来，最终结果是每个数据只单一的对应唯一的一个簇结束。而凝聚的层次算法正好与分裂相反，是自底向上将小的簇聚类为大的簇，在一开始的时候数据集中每一个数据对象为一个小的簇，逐步的与相邻的簇合并最终成为一个簇时终止。比较经常被使用的以层次为基础的的聚类算法有：BIRCH算法 、CURE算法 、ROCK算法、CHAMELEON算法等。

2.3.4 基于模型的算法

基于模型的聚类分析算法[1]中的模型指的是数学模型，该算法是将数据集与某种算法形成最佳的拟合，该算法能够利用统计学的方法，根据拟合的数据模型自动确定聚类的个数K，该算法的鲁棒性很强。基于模型算法包括神经网络方法[13]和统计方法，神经网络方法的思想是将每一个聚类描述为某个标本，通过度量函数的计算，将新的数据对象分到相对应的标本中，最终完成聚类。而统计方法将每一个聚类结果通过概率描述的方式表示出来，该方法比较适用于概念聚类。

2.3.5 基于网格的算法

网格的算法[14]的基本思想是将数据空间划分为一定数量的格子，每次对数据的各种操作就在格子中进行操作，该算法的处理难易程度只与网格的数目有关，这是网格聚类算法的特点，常用的网格聚类算法有STING算法、WAVECLUSTER算法、CLIQUE算法。STING算法的主要思想是先在分层的结构中存储网格的统计信息，这些统计信息是提前计算出来的，数据对象的空间被分成许多格子，这些格子是按层次排列，高层的格子信息被划为许多低层次的格子信息。CLIQUE算法是网格与密度结合的算法，它的工作过程是将数据空间划分成不相关的网格，然后判断网格是否是密集的，判断标准是空间中的每一个维度，再将判断出来的属于密集的网格进行求交的操作，并检查这些交集是否连通良好，然后生成最小覆盖的簇。WAVECLUSTER算法是通过把数据比作信号来判断，多维数据对应的是多维的信号，首先要做的也是将数据空间划分为网格，该算法利用的是小波变换算法，使数据空间成为频域空间，在数据空间中利用某一函数对这些数据做卷积，最终就能得到聚类结果。

2.4 常用的划分聚类算法的分析

划分的算法中最常用的就是K-均值算法和K中心值聚类算法和基于它们的改进算法，分别详细介绍这两种算法，本章的距离函数选取的是使用目前最常用的欧氏距离。

2.4.1 K-均值聚类算法

14

K-均值算法是利用算法迭代的思想[15-16]，通过多次迭代改变不同簇的重心并将数据元素放到新的簇中，直到最终的聚类函数收敛时停止即可得到最终的聚类结果。本算法的计算公式表示为：

KM(X,C)=∑j=1∑xjcj||Xi-Wj||2(j<=k) ；……………………………………… (2.13) Wj=∑xj∈cj(xi/|cj|),j=1,2,…..,K；………………………………………………. (2.14) 这个定义的公式是假设每个数组只有唯一的数据型的属性值。该算法要用户期望的聚类结果的组数作为输入值K，而每个簇内的初始数据是根据电脑随机分配的，也可以依次取前K个元素，该迭代算法直到没有数据元素再被分到不同的组中时就是算法结束的时候。KM算法的时间复杂性为0(xKM),x表示本次实验一共迭代了多少次，K是聚类所生成的簇数，M是数据集的个数。因为该算法是定义在数值型的属性上的，对该数据集假如还有其他属性是不能识别的，所以该算法所得的并不是全局最优解，而是局部的，而且也不能处理其他形状的簇，只对凸形簇敏感。

K-均值算法多次迭代的最终结果就是使目标函数KM（）最小值，通过该公式我们发现该算法必须预先选好初始点，对初始点有很强烈的依赖性，如果该初始点选取不合适会影响整个结果，这是该算法的一个缺点，可以改进的地方是用层次聚类等方法能够提前计算出比较合适的初始点，再开始聚类。除此之外K-均值算法还有其他缺点，它在时间上并不具备高效性。为了找到全局最优解，必须谨慎选取初值和簇数，还可以计算簇内的方差，如果方差值很大就可以选择将该簇分裂为两个簇来提高有效性，方差值过小而且比设置的最小值还要小就要考虑合并两个簇。

2.4.2 K-中心聚类法

已经介绍过KM算法对簇中心的选取非常敏感，选取不恰当会对聚类结果产生影响，这是KM算法的缺陷，如果有一个与簇中心点相距很远的点被选为初始点就会非常明显的影响聚类质量。但是数据集中这种孤立点难免会出现，所以为了减少这种噪音数据对聚类结果的影响，K-中心聚类算法[17-20]出现，它与KM算法最大的区别是它是用最接近中心的那个数据对象来代表这个簇，而不是用所有数据对象的均值来代表该簇，这样有效的避免了噪音数据的干扰，这也是K-中心聚类算法与KM算法唯一的区别，其他的步骤大相径庭，没有太大的区别。它所用的目标函数公式是：

J=∑j=1∑x∈Wi||x-mj||…………………………………………… (2.15)

15

其中Wi表示数据集中的人一个对象，mj表示该簇的中心，该算法除了不受孤立点影响之外还不受数据输入顺序的影响。

K-中心算法中的最早的PAM算法只适用小规模数据集聚类的算法，该算法的主要的思想是电脑自动随机选出数据集中的K个数据对象为初始簇中的初始数据，然后根据距离函数计算剩余数据跟各个初始数据的距离，并挑选出距离最小的初始簇，将该点归入到该簇中，并计算新的簇代表，即迭代这些操作，持续到没有非代表的数据对象替换现在的簇代表对象为止，从而实现中心点聚类算法的聚类。

PAM算法对大数据集不具备高效性，一种新的算法也被人们提出来，它就是CLARA算法，该算法是对大的数据集进行N次的抽取小数据集样本，并依次对这些小的数据集使用PAM算法，充分发挥PAM算法的优势，得到N个聚类结果，然后再从这N个聚类结果中选择一个最优解作为最终整个数据集的结果。为了保证最终结果的可靠，抽样过程中必须遵循随机性，除此之外还要掌握好抽样的规模大小，要适度，不能盲目抽取浪费时间，把握效率和效果的充分平衡。

2.5 本章小结

本章详细介绍了聚类分析相关的基础知识，分析了它的定义，属性，表示方法，相似性测量度，距离函数等方面。并对常用的五种聚类分析的方法：划分的方法、密度方法、层次的方法、网格的方法、模型的方法，进行详细介绍，并简要叙述了各方法中常用算法的基本思想和优缺点，最后着重详细的介绍了基于划分的两种聚类分析算法：K-均值算法和K-中心值算法。

16

3 K一均值聚类算法的研究

3.1 K-均值聚类算法介绍

k-means算法[21-23]是在1967年MacQueen第一次发现并提出来的，也被称为K-平均或K-均值聚类算法。为应用最广泛的一种聚类方法。主要特点为将每个群集子集内的所有数据样本的平均值作为集群的代表点。算法的主要思想为通过采取一种反复的过程使数据集被分成不同的类别，进而使用评价结果的聚类性能标准的功能来实现的，从而使产生的每个群集的紧凑及独立。这种算法不适合处理离散属性，可是对于连续性具有较好的集聚效应。

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

K-means算法的工作原理可以总结为：首先，要从数据集中自动随机选择K个点作为初始聚类中心，然后分别将每种样品计算其与集群的距离，样品分类的标准为其与聚类中心的距离。利用距离函数计算出每一个新生成的所要作聚类的数据对象的平均距离值，并用这个平均距离值来作为新的聚类中心，倘若相邻两次计算所得到的聚类中心点并没有发生一点的改变，那么就能够证明样本调整过程就算完成了，也就是表示聚类准则函数目前达到了收敛。本算法有一个明显的特点，就是在迭代过程中要对每个样本的分类结果进行验证观察是不是正确。假如是不正确的，那么则需要对聚类进行调整。等所有的样本调整完成以后，然后下一步就是对聚类中心的修改，从而开始进入下一次迭代过程中去。倘若在某一次迭代算法过程中，所有样本的分类结果是正确的，无需调整，聚类中心也没会出现有一点任何变化，那么这表明该聚类函数收敛，从而算法就结束了。

3.1.2 K一均值聚类算法主要流程

输入：含有n个数据对象个数的数据库和所需要的簇的数目k。 输出：k个簇。平方误差准则达到最小。 算法描述：

（1） 从 n个数据对象中自动随机的选择 k 个对象来作为初始状态的的聚类中心； （2） 根据各个聚类对象的均值（即每个簇的中心点），来计算各个数据对象与所有中心对象之间的距离。并以最短距离的为依据要求对相应的对象进行再一次的划分；

（3） 重新计算各个发生了变化的聚类的均值（即距离中心对象）；

17

（4） 循环过程（2）到（3）直至各个聚类不再发生变化为止。 算法步骤：

1.为各个聚类确定一个初始的聚类中心，这样就可以产生K 个初始聚类中心。 2.按最小距离的原则把样本集中的样本分配到最邻近聚类。 3.把各聚类中的样本均值规定为新的聚类中心。 4.重复执行步骤2、3直至聚类中心不再发生变化。 5.结束过程，得到K个聚类。

3.2 K-均值聚类算法的主要缺陷及分析

主要优点：

（1）作为解决聚类问题而出现的一种传统经典算法，具有简单、快速的特点。 对于较大数据集的聚类分析来说，该算法相比较而言是可伸缩和高效率的。因为它的时间复杂度是0 (n k x ) 。其中, n 是所有对象的个数, k 是所需要的簇的个数, x 是迭代发生了多少次。通常情况下有k <

（2）当结果簇是密集的，而且簇与簇之间的区别较为明显时, 它的效果比较较好。 主要缺点：

（1）K-均值算法只是在簇的平均值已经提前被定义了的情况时才能被使用，而这个前提对于处理符号属性的数据并不适用。在 K-means 算法中，首先要根据初始的聚类中心来确定一个适合的初始划分，接着要对初始划分开始进行进一步的优化操作。聚类结果对这个初始点的选择是相当敏感的。倘若初始值选择的不合适很可能造成不能得到准确的聚类结果的后果。这也是K-means算法目前存在的一个主要问题。对于该问题的解决，许多算法采用遗传算法——GA，例如可以采用遗传算法GA来进行初始化操作，而且内部聚类准则被当做评价指标。

（2）必须事先给出k值（想要生成的簇的个数）。并且对初值很敏感：不同的初始K值，也许将导致不同结果。在 K-means 算法中K值是要求提前必须给定的，但是这个值的选择是相当难以估计的。实际情况下大部分时候提前是并不能确定给定的数据集应划分成多少个类别才最适合这个数据集。这也是该算法的一个缺点。有的算法是通过采用类的自动识别它的初始数据集的分类和合并来得到较为合适聚类的簇数。例如 ISODATA 算法。对 K-means 算法中的聚类数目K 值的确定有很多方法，有的是根据方差分析理论结合应用混合 F 统计量来得到最合适分类数，并且采用模糊划分熵的方法来

18

验证其合理性。有的使用一种结合了全协方差矩阵的RPCL算法，而且逐步删去那些仅仅包含很少数据量的训练数据的类。还有的使用一种名为次胜者受罚的学习竞争规从而自动决定类的合理数目。它的思想为：对于每个输入来说，不但获胜单元的权值被加以修正以便适应输入值。而且对于次胜单元则采用惩罚的方法以使其远离输入值。

（3）该算法对“噪声数据”以及孤立的点数据是相当敏感的，即使少量的该类数据也可以对平均值产生相当大的影响。

（4）从 K-means 算法流程中可以清楚的看到，该算法的实现原理要求必须不断地对样本进行分类，并且必须不断地计算更新调整后的新的聚类中心。所以当数据量很大时，算法的时间复杂度是非常大的。因此需要对算法的时间复杂度时刻进行关注、审查以满足时间等的要求。例如可以利用一定的相似性准则来排除一些近似的聚类中心的侯选集。

3.3 本章小结

本章主要是针对K-均值算法作了系统的分析，介绍了它的基本定义、基本思想、主要流程，最后详细分析了该算法在实际应用中的优点和不足。K-均值算法是数据挖掘聚类划分算法中最基本的算法，虽然它本身在实际应用的过程中存在不足，但是我们不能忽视它本身对数据集聚类的优点，在有的实践应用中也取得了理想的效果，很多的算法也是以此为依据进行改进的，主要是对距离计算的改进，如P-CLUSTER算法，就是基于K-均值算法的一种改进，是启发知识来判断该数据集聚类对象M的最近的簇中心是否改变。

19

4 K-均值聚类算法的实验

4.1 实验结果分析

实验一：

本文测试采用的是从数据堂下载的c-fat500-10.txt数据集，对K-均值算法进行了验证，经过实验分别对150个数据的数据集选取不同初始点分别进行聚类，验证不同的初始条件对最终聚类结果的影响情况，得到的聚类结果分别如下图：

令前三个数据p[1]p[2]p[3]作为初始聚类中心，如图4.1所示：

图4.1 初始点为第1 2 3序号的聚类图

把第p[4]p[5]p[6]个数据作为初始聚类中心，得到的聚类结果如图4.2所示：

20

图4.2 初始点为第4 5 6序号的聚类图

把第p[100]p[101]p[102]个数据作为初始聚类中心，得到的聚类结果如图4.3所示：

图4.3 初始点为第100 101 102序号的聚类图

把第p[1]p[10]p[100]个数据作为初始聚类中心，结果如图4.4所示：

21

图4.4 初始点为第1 10 100序号的聚类

实验分析与结论：

分析：由以上聚类结果发现，不同的初始值的选取对聚类结果并不是造成很大影响，比较图4.1和图4.2可得，初始值选取的不同，只是造成聚类结果中极少数的数据发生变化，如数据20、27，聚类的迭代次数发生了改变由5次变为7次，还有不同点就是，聚类结果的输出顺序也发生了变化；对比图4.3和图4.2的聚类结果图可得，选择第100、101、102个数据与选择第4、5、6个数据作为初始点的聚类结果是一样的，不同之处就是数据聚类的输出顺序有所改变，可是图4.3的迭代次数又比图4.2的迭代次数增多，变为9次；前三次的实验是选取连续的数据作为初始点，在第四次的实验中，选取第1、10、100个数据不连续的这三个数据作为初始值，从结果图可以看出，本次实验与第一次的聚类结果和迭代次数都相同，只是数据输出顺序有所改变。

结论：首先对比四个图的聚类结果，并没有因为初始点选取的不同而发生大的改变，只是改变了迭代次数，其中选取最前面的三个数据和后面某一不连续的数据为初始点时迭代次数最少。实验表明：K-均值算法对初始值得敏感体现在对聚类结果的迭代次数上，选取合理的初始点有助于我们高效率的完成聚类工作，用最少的时间完成我们所需要的结果为我们更好的应用在实际生活上。因此，从这此实验我们得到的结论是：

22

（1）尽量选择数据最开始的连续的点作为初始点，这样可以用最少的迭代次数完成聚类；

（2）改变K-均值算法的初始点可以影响数据集的迭代次数，对聚类结果影响不大；

（3）每次初始值的改变也会造成数据输出顺序的改变，即使是在聚类结果不变的情况下。

实验二：

本次试验是验证不同的数据输入顺序，对聚类结果的影响，实验的数据集为了更具说服力，还是用实验一中的数据，不同之处是，此次实验只是将数据集中的后75个数放到前面，也就是与前75个数调换一下顺序，本次试验只是验证数据集输入顺序的改变对聚类结果的影响，所以只选取两种初始值进行验证，与实验一进行对比，可得实验结果如下：

令前三个数据p[1]p[2]p[3]作为初始聚类中心，如图4.5所示：

图4.5 数据输入顺序改变聚类图1

把第p[4]p[5]p[6]个数据作为初始聚类中心，得到的聚类结果如图4.6所示：

23

图4.6 数据输入顺序改变聚类图2

实验分析与结论：

分析：本次实验主要是与之前的数据顺序不同时所得的聚类结果，由图4.5与图4.1，图4.6与图4.2的对比结果可得出，改变了数据的输入顺序，造成聚类结果有很大的改变，同时迭代次数也增加了，这说明K-均值算法对数据输入顺序的敏感性不仅体现在迭代次数上，而且更会改变数据的迭代次数。另外，再对比图4.5与图4.6的结果，虽然两次的聚类结果是一样的，但是迭代的次数当选取第4、5、6个数据为初始点比选取第1、2、3个数据为初始点迭代次数有所增加，聚类结果的输出顺序也有所改变，同时也验证了实验一的结论。

结论：由实验可得K-均值算法对数据集的输入顺序也是敏感的，不同的的顺序会有不同的聚类结果，这也是今后改进算法可以尝试的方向，也可以在应用该算法时，通过改变数据集的输入顺序来适当提高聚类效果。本次试验改变了输入顺序反而使迭代次数增加，很可能再次改变输入顺序会让迭代次数减少，这些都说明K-均值算法对数据输入顺序特别敏感，因此我们得到的结论是：

（1）当我们聚类数据集迭代次数很多时，我们可以适当改变一下数据的输入顺序； （2）K-均值算法的聚类结果对数据输入顺序很敏感，与之前没有改变顺序之前的聚类结果差距很明显，所以不要轻易变动数据集的输入顺序；

24

4.2 本章小结

本章主要是实现K-均值算法，并且在实现该算法的基础上，对影响K-均值聚类效果的两方面因素初始点的选择和数据输入顺序两个方面的因素对聚类结果的影响情况进行验证。通过两个实验，实验一有4个运行结果，实验二有2个运行结果，比较充分的验证了这两方面的因素对聚类结果的影响，并通过对比试验结果，得到结论：初始点选取的不同会影响数据集的迭代次数，不会特别明显的影响聚类结果，而不同的数据输入顺序，会对聚类结果造成明显的影响，同时也会改变迭代次数，这些结论为用户在将来使用传统K-均值算法的时候提供一些降低因K-均值算法的缺陷带来的损失和避免造成不必要麻烦的建议。

25

5 总结与展望

5.1 总结

本文主要介绍了数据挖掘中的聚类分析，对聚类分析中的K-均值算法进行了探索研究，主要是对影响K-均值算法的聚类效率因素的探究。

首先，介绍了本文的研究背景与本文的研究意义，简单介绍了数据挖掘的背景，着重介绍了聚类分析目前研究的国内外现状，主要是对聚类分析的应用领域与研究方向进行了探讨，并分析了目前聚类分析还有哪些亟待解决的问题。

其次，对数据挖掘中聚类分析进行了系统与完整的分析，主要是对聚类的定义及表示、聚类的相似测量函数、距离测量函数和聚类的五个常用算法的介绍，着重研究划分聚类算 法。

最后，对基于划分的聚类算法中的K-均值算法进行了探究，在详细的介绍了K-均值算法的定义、基本思想、算法流程等方面对该算法进行了分析，并对该算法的特点进行研究，分析了它的长处和不足，并根据该算法本身存在的问题，对应该算法自身不足的因素进行了探究与实验，经过实验表明，初始值的选取不当和数据输入顺序的改变都会影响聚类结果，但是初始值的改变对聚类结果的影响不明显，对于不同的初始值会有不同的迭代次数，而数据输入顺序的改变，对聚类结果造成的影响很大。因此我们在实际应用中应该注意这方面的不同因素，会对聚类结果造成哪些影响，通过本次试验，也可以为希望出现的聚类结果提供改进算法的思考方向，使该算法能够更好的为我们服务。

5.2 展望

通过实验证明的结论并未对更多的数据集进行验证，还不能验证出更多的影响K-均值聚类算法的因素对聚类结果会造成怎样的影响，这部分工作应该进一步深入下去，可以通过对更大更多类型的数据集验证其他不同因素改变所得结果进行比较，来得出各个因素影响K-均值算法的聚类结果的哪些方面，得出K-均值算法最敏感的初始条件，比较出哪些条件在实际应用中最容易得到优化，这样就会使得之前提出的改进的K-均值算法得到优化，更好的有的放矢，为将来该算法和该算法的改进后的算法更加灵活的应用到现实的生活中去。

26

目前已经存在了很多中改进的算法，以后的工作是我们应该对多种算法通过相同的数据集进行全方位的对比，通过对比得出的结果往往更加明确，从而分析出各个算法的因各个因素的不同受影响的范围与程度，并将这些结论利用大量的数据集进行验证，来作为每一个新的算法使用帮助，有助于用户对大量算法的选择起一个指导性的作用，更加方便我们使用。当然没有一种算法是完美无缺的，再优秀的算法设计也会有它不能很好聚类的数据领域，这就要我们在实际应用中，扎实我们自身的算法知识的积累，要灵活的选取不同的算法为我们服务，不要拘泥于过分复杂算法，有的时候简单的算法也有它的自身优势，比如本文介绍的K-均值算法，总之，知识不但要积累，还要灵活使用，才能发挥科学最大的力量。

27

参考文献

[1]T Zhang．R．Ramakrishnan and M．ogihara．An efficient data clustering method

for

very

largedatabases．In

Pror．1996

ACM-SlGMOD

hat．Conf．Management of Data，Montreal.Canada，June 1996：103．114. [2]邵峰晶，于忠清，王金龙，孙仁城 数据挖掘原理与算法（第二版） 北京：科学出版社 ,2009, ISBN 978-7-03-025440-5.

[3]张建辉．K-meaIlS聚类算法研究及应用：[武汉理工大学硕士学位论文]．武汉：武汉理工大学，2007.

[4]冯超．K-means 类算法的研究：[大连理工大学硕士学位论文]．大连：大连理工大学，2007.

[5]曾志雄．一种有效的基于划分和层次的混合聚类算法．计算机应用，2007，27(7)：1692．1695.

[6]范光平．一种基于变长编码的遗传K-均值算法研究：[浙江大学硕士学位论文]．杭州：浙江大学，2007.

[7]孙士保，秦克云．改进的K-平均聚类算法研究．计算机工程，2007，33(13)：200．202.

[8]孙可，刘杰，王学颖．K均值聚类算法初始质心选择的改进．沈阳师范大学学报，2009，27(4)：448-450.

[9]Jain AK，Duin Robert PW，Mao JC．Statistical paaern recognition：A review．IEEE Trans．Actions on Paaem Analysis and Machine Intelligence，2000，22(1)：4-37.

[10]Sambasivam S，Theodosopoulos N．Advanced data clustering methods ofmining web documents．Issues in Informing Science and Information Technology，2006，8(3)：563．579.

28

[11]Z．Huang．Extensions to the K-means algorithm for clustering large data sets with categorical values．Data Mining and Knowledge discovery,1998，(2)：283-304.

[12]M．Ester,H，P．Kriege．A density-based algorithm for discovery clusters in large spatial databases．In Proc．1996 Int．03n￡Knowledge Discovery and Data Mining Portland． Aug 1996：226-2311

[13]毛国君，段丽娟，王实，等．数据挖掘原理与算法(第二版)．北京：清华大学出版社，2007.

[14] Wang,J．\and R．Muntz．A statistical information grid approach to spatial data mining．In Proc．1997 Int．Conf．Very Large Databases，Athens，Greece，Aug．1997：186-195.

[15]Wu K L，Yang M S．Alternative fuzzy c-means clustering algorithaL Pattern Recognition.2002，35：2267—2278．

[16]Hammerly G.Elkan C．Alternatives to the k-means algorithm that find better clusterings，in：Proc．of the 1 lth Int．Conf．on Information and Knowledge Management，2002：600—607．

[17]Alsabti K，Ranka S，Singh K．An Efficient K-Means Clustering AlgorithnL In：Proceedings of PPS／SPDP Workshop on High performance Data Mining.1997：34—39．

[18]Lozano J A，Pena J M，Larranaga P．An empirical comparison of four initialization methods for the k-means algorithm.Pattern Recognition，1999，20：1027—1040．

29

[19]Likas A，Vlassis N，Verbeek J J．The global k-means clustering algoritl卫L Pattern Recognition，2003，36：451—461．

[20]Kiri W，Claire C，Stefan S．Constrained K-means Clustering with Background Knowledge．Proceeding of the Eighteenth Internat ional Conference on Machine Learning.2001：577-5841．

[21]Ng A Y，Jordan M I，Weiss Y．On spectral clustering：Analysis and an algorittms InAdvances in Neural Information Processing Systems，2001，14：849—856．

[22]Higham D，Kibble K．A Unified view of spectral clustering．Technical Report 02。University of Strathclyde， Department of Mathematics，2004．

[23]Alpert C，Eahng A，Yao S．Spectral partitioning：The more eigenvectors，the better．Di screte Applied Math，1999，90：3—26．

30

Implement of K-means algorithm

Abstract:With the rapid development of Internet technology, now people every day will face such as text, images, video, audio and other data in the form, the size of these data the amount of data it is amazing. How quickly and efficiently from these a large number of data mining to extract the value of the implication of its particular concern and the need to immediately solve the problem. Data Mining (Data Mining, DM) It is for this guess is born out slowly. Data mining after a little time the rapid development of the birth of a large number of theoretical results and practical use of results, it provides a number of tools and effective way to solve the problem. A data mining is a very important area of research, that is, clustering analysis, which is a data in accordance with the type based on the data packet or data framing. Clustering in terms of biological research, or in the business trade, image analysis, web content classification and other areas of daily life have been a very good application.

Depending on the data type, the use of different functions, and clustering the different needs of the clustering algorithm is probably the following: Partition-based algorithm, level-based algorithm, based on the density of the algorithm, the model-based algorithm and grid-based algorithm. In this, the present study the most mature classic K-means clustering algorithm based on partition algorithm. The field of application of the K-means algorithm is particularly extensive coverage involves voice frequency compression as well as images and text clustering, the other to play its important use in data preprocessing and neural network structure of the task decomposition. The work done in this article:

The first part of this article: Details of the background and purpose of the thesis, and I selected topic ideas to consider, as well as in the current international form of cluster analysis in our international status and Summary of the research results at home and abroad, and finally the contents of the realization of this thesis and papers overall layout arrangements.

Part II: the first detailed description of the source of development of data mining as well as its definition of the concept, the following describes the cluster analysis, basic knowledge of basic concepts such as clustering principle, the internal characteristics of the clustering algorithm, described in detail Several current method of cluster analysis, summary comparison of the characteristics and weaknesses of

31

each method. Finally, the paper studied the clustering algorithm based on partition for further discussion which has several algorithms.

Part III: This is the focus of this paper, the K-means algorithm to be discussed in this paper, the basic idea of the algorithm process from the concept of K-means algorithm detailed introduction and a detailed analysis of its flaws. K-means algorithm select the initial worth more sensitive and a different order of data input will also affect the clustering problem, we solve the problem verified, maybe factors which affect the clustering result will be proved by experiments. The experiments show that the K-means algorithm is very sensitive to the initial value and the data input sequence, but maybe a different impact on the clustering results. In this paper, six experimental results analyzed, to change the initial point, has little effect on the clustering results, but will change the number of iterations, and select the initial continuous data for at least the number of iterations of the initial point, an interval of a few data appears as an initial point of the smallest number of iterations, but the data and there is too much uncertainty, so choose the best start that several data for data clustering initial point; for changing the input of the data set order, clustering results before a big change, say the name of the input sequence only affects the clustering results also affected the number of iterations. These conclusions for future users using the K-means algorithm provides a good help for this algorithm provided the reference.

Keywords: data mining ,cluster analysis,K-means algorithm ,experimental verification

32

本文来源：https://www.bwwdw.com/article/3zn7.html