1、数据挖掘K均值算法实现本科生毕业论文设计数据挖掘K-均值算法实现作者姓名： 指导教师： 所在学院：数学与信息科学学院专业（系）：计算机科学与技术班级（届）：2013届计算机班二零一三年五月二日中文摘要、关键字 15 总结与展望 26英文摘要、关键字 31论文题目：数据挖掘K均值算法实现数学与信息科学学院 计算机科学与技术专业指导教师：郭瑞强作者：郝蓓摘要：随着互联网技术的迅速发展，现在的人们每一天都会面临例如文本、图像、视频、音频等各种数据形式，这些数据的数据量的大小是很惊人的。怎样能够很快的并且高效地从这些大量数据中挖掘提炼出它所蕴含的价值，成为现在人们特别关注并且需要马上解决的问题。数据挖
2、掘(Data Mining，DM)正是因为这个才慢慢诞生出来。数据挖掘经过一段时间的迅猛发展，诞生出了大量的理论结果和现实使用成果，它提供了许多工具和卓有成效的方法来解决问题。数据挖掘中有一项是很重要的研究领域，那就是聚类分析，这是一种对数据进行按照不同的依据将数据进行分组或者将数据进行划分的方式。聚类无论在生物科学研究，还是在商务贸易中、图像分析处理、网页内容分类等其他日常生活的领域都得到了很好的应用。根据使用的数据类型、使用的功能的不同、聚类需求的不同，目前的聚类算法大概有以下几种：基于划分的算法、基于层次的算法、基于密度的的算法、基于模型的算法以及基于网格的算法。在这之中，基于划分的K-
3、均值聚类算法是目前研究最成熟传统经典的算法。K-均值算法的应用领域特别广泛，覆盖范围涉及语音频率压缩还有图像及文本聚类，另外在数据预处理和神经网络结构的任务分解等也发挥其重要用途。本文所做的工作有：本文第一部分：详细介绍了本次论文研究的背景和目的，以及所选题目的考虑思路，还有在当前国际形式下，聚类分析在国际上的地位及国内外研究成果综述，最后介绍了本论文算法实现的内容和论文整体布局安排。第二部分：首先详细描述了数据挖掘的来源发展还有它的概念定义，下面主要介绍聚类分析，包括聚类的基本概念原理等基础性知识，介绍了聚类算法的内部特性，详细描述了几种目前聚类分析的方法，总结比较各个方法的特点及其长短处。
4、最后对本论文所研究的基于划分的聚类算法进一步讨论都有哪几种算法。第三部分：这是本论文的重点，本论文所要讨论的K-均值算法，从它的概念基本思想算法流程等方面对K-均值算法进行详细系统的介绍，并且详细分析了它的优缺点。K-均值算法对初始值的选取比较敏感和对数据的输入顺序不同也会影响聚类等问题，所以本文针对该问题进行了验证，通过实验证明了这两个因素对聚类结果会有哪些影响。实验表明，K-均值算法对初始值和数据输入顺序很敏感，但是这两个对聚类结果影响的方面不同。本文通过六个实验结果分析得出，改变初始点，对聚类结果的影响不大，只是会改变迭代次数，而且选取初始的连续的几个数据为初始点迭代次数最少，虽然中间间
5、隔的几个数据作为初始点也出现了最小的迭代次数，但这对数据集来说有太多的不确定性，所以还是选择最开始那几个数据为数据聚类初始点；对于改变数据集的输入顺序，聚类结果与之前的有很大的改变，实验结果说明输入顺序不同既影响了聚类结果也影响了迭代次数。通过这些结论为以后用户使用K-均值算法提供了很好的帮助，也为该算法的改进提供了参考。关键词：数据挖掘 聚类分析 K-means算法 实验验证1 绪论1.1 本文研究的背景和意义近年来，随着科技的进步以及互联网的普及，以计算机为代表的信息技术有了巨大发展，人们产生、发现、整理、利用数据的能力不断提升。到目前为止，数据在我们的日常生活中无处不在，它广泛应用于科学
6、研究、政府日常办公、军事力量分析、企业管理电子商务、统计学分析等等各个领域。虽然我们知道这些数据的重要性，但是随着时间越来越久，我们积累的数据量是不断地在加大，相应的我们分析处理这些数据的能力也要增加，但是后来数据量的增长速度已经超出了我们的能力范围，所以我们必将面临的严峻问题是数据爆炸。难道真的没有办法可以很科学的处理这些海量数据吗？事实并非如此，人类的智慧是无穷的，人们已经通过理性的思维和恰当的技术，将这些海量数据充分利用，使它们成为社会发展进步的强大的力量源泉。目前，广泛使用的数据库系统虽然具有高效率的录入所有数据查询所需数据统计数据类别等功能，但是并不能发现这些海量数据中蕴藏的内部关联
7、规则，也无法从当前现在的数据情况去预测未来的数据内容的发展趋势，更不可能做出决策判断，使得人们逼不得已去面对“数据丰富而知识缺乏”的困镜1。所以数据挖掘（Data Mining）技术因此就慢慢诞生了，并且快速的发展应用社会的各个领域，表现了其坚韧的生命力与适应力。该技术就是从“数据矿山”中发现“知识的宝藏”。数据挖掘（Data Mining），也被叫做在已知的数据库中对知识的发现（knowledge discovery ,KDD）,就是从数量巨大的、不完整的、有孤立点数据的、模糊的、随机的数据中，提取发掘出来隐含在当中的、人们在这之前不是特别了解的、但又是隐含有用的信息内容和知识内容的非平凡过
8、程2 。原始的数据类型可以是多样的，比如数据库中的数据结构化数据类型，那些图像图形资料及文字类资料是半结构化的数据类型，当然也包括网络互联网上的那些数据我们称它们为半结构化的数据类型。我们可以通过归纳演绎等方法来发现知识，也可以用统计学的数学或非数学的方法总结数据来得到我们想要的信息。这些我们得到的信息内容和知识内容的过程就是挖掘的一个过程，我们把挖掘的知识可以应用到我们的生活中，包括未来决策规划、优化信息管理方案、调整控制模式、改进查询方案等等来更好的维护和利用我们现有的数据。所以数据挖掘涉及到的学科很广泛，它是各个学科的交叉，它用到了人工智能数学统计学与数据库等技术来实现它自己的目的，需要
9、这些领域的工程技术人员来共同配合，尤其是数据库管理人员。现在的数据挖掘技术已经开始走向科技产品研发及技术应用，不再是之前的单纯的搞一下研究而已，我国市场经济制度在不断地完善与发展，经济实力也在不断进步，现在我们的社会对数据挖掘技术的需求越来越强烈，目前我国很多的有眼光的软件企业已经将目光聚集于此，来研发更多适应市场需求的数据挖掘软件产品，随着市场日趋成熟，广大消费者的应用需求也是慢慢变大，相信将来会有更多成熟的中国数据挖掘软件面向市场。聚类分析是数据挖掘的一个发现信息的方法，已经被人们深入的研究了很长时间，主要的是对基于距离的聚类分析的研究。聚类是一种无监督的学习，分类正好与它相反，分类是一种
10、有监督的学习，聚类主要是划分无标记的对象，使这些无标记的对象变的有意义，对预先定义的类与带类标记的训练实例不具有依赖性。所以聚类分析在我们的日常生活中的应用范围非常广泛： 在商业上，聚类可以根据消费者数据库里面所记录的数据信息，对消费者进行划分，根据各个消费者的特征，以帮助市场营销员按照市场需求及时调整货物的摆放次序等一系列营销计划的实施； 在社会学中，聚类用来发现目前社会结构组成中潜在的社会结构； 在网络挖掘中对互联网上批量的数据信息进行有效的划分与分类，实现信息的有效利用，对数据信息检索效率方面有显著提高； 在生物信息学中，在大量的基因群中发现功能相似的基因组，对基因因功能不同进行划分对其
11、固有的结构特征进行分析，来更好的为我们的医学发展提供有利条件； 在空间数据库领域，聚类分析能对相似地理特征区域及它们的人和环境的不同特征进行识别，来研究地域文化提供条件。本文主要选择聚类分析中基于划分的K-means算法并实现它的应用，对数据集的数据进行聚类分析。本文在实现它的基础上，对该算法对初始值和数据输入顺序敏感的问题进行了验证，通过六次试验，分别对这个两个方面进行验证，并对聚类结果进行分析比较，从而得出结论。本文通过对不同输入条件的实验验证，得出K-均值算法对初始值得选择和数据输入顺序是很敏感的结论，通过实验结果可得出在今后使用K-均值算法时我们应该怎样避免其聚类出不准确的聚类结果和今
12、后改进算法应该改进的方向等问题。1.2 聚类分析国内外研究现状目前，国内对于数据挖掘聚类分析的研究的集中部门还是科研单位和各大高校，国内还没有公司企业专门从事聚类分析的研究，相对于外国来说起步较晚。各大科研机构与高校对聚类的研究主要是对数据集聚类算法的设计并实现，以研究出来的算法为基础对算法改进。目前人们已经在统计分析软件中应用一些聚类分析工具，如SAS等软件。为大型的数据库寻求有效的聚类分析方法是目前聚类分析的主要研究工作，目前研究方向包括以下几个方向：（1）可伸缩性：目前的聚类算法针对小型数据库，数据量是几百范围内的，对于有很庞大数据量的数据库会造成结果的不稳定性，可伸缩性强的算法就亟待的
13、研发出来。（2）属性不同情况下的处理能力：现在开发出来的聚类算法所针对的数据类型都是数值型，但实际上的聚类类型的信息是不确定的，如二元数据、序数型的、分类型的等或者是所已知的各种数据类型的混合。（3）聚类形状：在欧几里得距离的基础上发现所得的簇的形状是球状簇，它们有相近的距离与密度，形成一个簇，但是我们更希望能够有一种算法实现各个不同形状的簇。（4）决定结果的输入参数：聚类算法的实现过程中相当多的是必须让用户提前输入想要聚类出来的簇数K，当前的算法对这些K的值是相当敏感的，大型的数据流对这些要求很严格，对结果的影响很明显，使用户在输入时加大了分析的工作难度，很难控制。（5）输入数据的顺序问题：
14、有的聚类算法对输入数据的顺序是有要求的，不同的输入次序会有不同的聚类结果，这就特别需要对数据顺序不敏感的算法开发出来，更好的适应人们的要求。（6）高维数据的处理：含有若干维数据属性的数据库是很常见的，但是擅长处理两维或三维的聚类算法才是目前成熟的应用的算法，一旦高维数据需要聚类处理，这就是一个难题，这就需要算法有很强的实用性。（7）污染数据的发现：数据是一个不确定而且无限性的群体，我们不能保证数据集中的数据是完全集中的，难免会有个别的孤立点造成污染数据，影响整个结果，应该开发出能智能识别这些孤立点的数据的算法，来优化聚类结果，目前大部分是通过对目前算法进行改进来实现。（8）有约束条件的聚类：实
15、际的聚类情况是有很多限制的条件的，在实现这些聚类时，既要按约束条件又要按聚类要求实现，是很有压力和挑战的一项任务。（9）可使用性和可解释性：大多情况下的聚类结果，对于客户来说都希望它们简单易懂，一目了然，所以我们要优化聚类结果界面的研究，选择适合每个客户需求的聚类方法来满足他们的需求。同时聚类分析算法主要着手于以下的几个问题的解决3：（1）初始值的选取及输入顺序对结果有何影响在数据挖掘的学科范围内寻找最优解的过程是通过迭代不同的初始值实现，但是这个办法不是很可靠，它的意思就是表示不能百分之百的确定找到最优解。其实寻找最优解就是在优化原来的聚类的结果，通过重复聚类找到所设计的目标函数的最优解，但
16、是这个目标函数一般都不是有最值的函数，所以它的最小值并不是很容易确定，因为它并不唯一，有可能找到的这个只是局部最小值，而不是全局最小，所以这种非完全单调函数的全局最小值的查找是目前最急着等待解决的问题。（2）以小波变换为基础的聚类算法因为当前主要是对均值算法与模糊算法的研究改进而得到的研究成果，这些研究成果使得目前的聚类分析算法提高了它的性能属性。小波变换聚类算法同样符合好的聚类算法的各项要求，目前对小波聚类的研究还有很大程度的空白，如果花大的精力进一步研究会有更加深入的突破。（3）算法的效率改善提高的问题聚类的效率问题是目前一个很棘手的问题，因为人类在进步，数据量会越来越庞大，应该增强目前聚
17、类算法对更大数据库的处理能力，即增量聚类，使聚类算法在聚类的数量上有更好的弹性，尽量减少在工作时对庞大数据库的扫描次数，进一步提高它的工作效率。（4）数据库类型目前，基于聚类算法的数据库比较单一，仅仅包括关系或事务数据库，应该着眼于其他数据库类型应用算法的研究，比如面向以属性为内容的数据库、以文本为内容的数据库、各个不同时态为内容的数据库、地理数据库多维数据库等的算法开发，这是一项非常艰巨而且有意义的研究任务。聚类分析中的算法有很多种，详细分析比较了各个算法的优缺点，本文着重介绍了K-均值算法，分析它本身的算法优点与不足，并对算法实现，着力于对影响该算法聚类结果的不同初始条件进行验证，以更好在
18、以后的实际应用中使用它。K-均值算法是聚类分析最常用的算法之一。K-均值算法的应用范围非常广泛，因为它的操作简单，适合处理庞大的数据集，但是它同时也暴露出自身的不足，如易陷入局部最优解的结果里面、需要用户提前输入参数、发现簇的形状比较单一等，已经有很多专家对这些问题进行了改进，文献4作者通过最大最小距离和DBI聚类指标解决了K-均值算法对初始值K的选择问题，能够确定出最佳的聚类数目。文献5的作者用K-均值算法与层次聚类算法进行混合出一种新的聚类算法，充分发挥了层次聚类的精确性和K-均值的高效性。文献6的作者对遗传算法提出一种改进算法，基于比变长编码，利用这种算法与K-均值结合解决了对初值选择的
19、敏感问题等等，目前已经有很多被发表出来的对K-均值的改进的算法。1.3 本文所做的主要工作首先对数据挖掘这门学科的背景和发展前景做了分析，本文主要研究数据挖掘的聚类分析，所以介绍了聚类分析目前国内外的地位与发展方向，以为下文展开作铺垫，这方面阅读了许多聚类相关文献，许多新的聚类分析方法先后被各国的科研工作者提出并应用，这些在本文有详细列举。除此之外本文对聚类分析中的常用的五种方法做了简要介绍，列举了五种方法中目前比较常用的算法，并分析了每个算法的适用领域与基本思想。本文着重讨论的是基于划分的聚类分析方法中的K-means方法，对KM方法进行了详细的介绍，包括基本思路工作流程等，本文通过分析KM
20、算法的缺点，通过实验验证了对初始点的选取和数据输入顺序敏感的验证，通过两个实验分别得出这两个因素对聚类结果产生怎样的影响并得出结论，实验表明初始点不同只是影响聚类迭代的次数，对聚类结果的影响不明显，只是少数数据的聚类结果发生改变；数据输入顺序的不同，不仅会改变数据聚类的迭代次数，也会让聚类的结果发生明显改变。2 聚类算法的分析与研究2.1 数据挖掘简介数据挖掘（Data Mining），也被叫做在已知的数据库中对知识的发现（knowledge discovery ,KDD）,就是从数量巨大的、不完整的、有孤立点数据的、模糊的、随机的数据中，提取发掘出来隐含在当中的、人们在这之前不是特别了解的、
21、但又是隐含有用的信息内容和知识内容的非平凡过程2。其实数据挖掘就是通过各种分析算法工具从巨大数量的数据中挖掘所需要的数据与模型两者关系的一个过程，可以通过得到的这些关系，对未来的数据与模型关系进行预测。通常根据不同用户的需求，和他们所提供的数据类型，数据挖掘的数据库的类型也是不一样的，通常包括关系数据库类型、事物数据库类型、多媒体数据库类型等。其中关系数据库实际上就是使用数学学科上的方法来处理数据之间的关系，我们生活中随处可见关系数据库，比如交通部的车辆数据库、银行的客户记录等。事务数据库一般是将几个事务数据库的数据一起导入到只能用来读数据的数据挖掘库中，做成一个数据集市，然后把其作为挖掘的对
22、象。多媒体数据库顾名思义就是包含大量视频音频文件，模式识别技术被用于该领域。数据挖掘包含很多类别，包括分类分析、聚类分析、关联分析孤立点分析等其他分析。其中分类分析包括分类和回归，分类分析是一种预测模型，通过现有数据预测将来的数据，如果预测的数据是离散的即叫做分类，如果是连续的即叫做回归。聚类分析则是将大量数据中形似的数据分到一组，一个数据集大概包括几组数据，聚类没有明显的属性目标，而是挖掘隐藏的属性来进行聚类，聚类分析中的基于划分的K-均值算法是本文的研究对象。关联分析分析数据与数据之间关联关系还有它与其他数据的派生关系。孤立点分析是针对那些远离数据集的点，对不同的客户，别人的孤立点可能对于
23、他来说是很重要的信息，孤立点分析就是对这些远离数据集中心的数据信息进行挖掘。孤立点的研究是将来我们必须重点研究的领域，因为几个孤立点就会影响全局的聚类结果，这是不容忽视的。2.2 聚类的基本知识2.2.1 类的定义及表示（1）类的定义要想聚类操作首先要明确类的定义。世界错综复杂事物存在的方式也不尽相同，所以类的定义并不唯一。以下将列举出常用的类的定义：设：含有K个样本的集合A，Mi是其中的某个样本，T和C是范围阀值，那么：如果任意的Mi，Mj A，都有D（Mi，Mj）T，则A称为一类；（2）类的表示；聚类的表示方法也是有不同的，一般用以下三种： 自然语言表示：直接用自然语言直观的描述出这些数据
24、是属于哪个簇的； DNF表示：用析取范式表示明了、简洁、易懂。例如：(36PT70)V(345AM1234)； 聚类谱系图：目前使用的聚类算法输出结果大部分都是这种，这种方法表示非常详细，它能表示出这些样本自成一类的所有中间情况，而且都会有各个类的平台高度，我们叫这种图为标度聚类谱系图。2.2.2 聚类的相似度量方法聚类分析按照数据样本性质的相似程度的大小进行划分，确定这些相似程度的大小必须有一个准则来判断它们的程度大小，这个判断准则叫做相似度方法，主要是在距离和相似系数的不同。距离：样本点之间的相似性我们就用某种距离函数表示，距离近的表示样本点相似，具体计算时可以把样本看做有M个属性的变量，
25、即这个样本就是在一个M维的空间中的一个点。距离函数：设P是所有样本集合的集合名称，如果满足： 正定性D(M，N)0，if MND(M，N)=0，if M=N 对称性D(M，N)=D(M，N) 三角不等式D(M,N)+D(N，L)D(M，L) 我们称它们为距离函数。聚类分析中经常使用的的距离函数有： 明氏(Minkowski)距离 (2.1)当m取1时，则表示绝对距离，当m取2时就表示欧式(Euclid)距离，当m取无穷大时就表示切比雪夫(Chebyshev)距离。 如：欧氏距离 (2.2) 马氏(Mahalanois)距离 (2.3) 其中 S 是由样品集N（）算得的协方差矩阵： (2.3.1
26、)样品聚类一般情况下被叫做Q型聚类，是以距离矩阵为出发点的。明氏距离改进后得到了马氏距离，所有的线性变换对于马氏距离来说是不变的，多重相关性马氏距离也把它克服了。 方差加权距离 (2.4)其中 . (2.4.1)在聚类分析中除了对样本点聚类，对特征变量也要根据实际情况进行聚类，所以对于特征向量而言，不必非用距离函数来确定它们的相似测度，还可以用相似系数。相似系数：当对含有k个指标的变量的数据集进行聚类时，就用相似系数来作为判断所有变量之间的相似程度（或关联程度）的标准指标。一般地，若表示Cab变量Xa,Xb之间的相似系数，应满足：1）| Cab|1且Cab=1；2）Cab=1或Cab=1Xa=
27、CXb；3）Cab=Cba；Cab的绝对值越与1接近，越说明变量Xa,Xb之间的关联性越大。相似系数中相关系数和夹角余弦是目前最经常被使用的。（1）相关系数变量之间的相关系数我们可以这样定义为：. (2.5)实际上，只是变量之间的观测值之间的相关系数而已。相关系数表示两个向量的相关程度是多少。（2）夹角余弦变量的观测值 ，其夹角余弦我们可以这样定义为： (2.6)变量聚类一般情况下被叫作为 R 型聚类。一般R 型聚类，相似系数矩阵 C 是数据集聚类的出发点，相似系数矩阵不仅能够使用相关矩阵，而且能够使用夹角余弦矩阵。2.2.3 聚类间的距离测度函数对于不同的两个类，如果他们之间距离可定义，那么
28、就用如下几种定义方式来定义他们的距离：（1）最短距离法：顾名思义它表示两个类中的元素，相离最近的两个元素的距离来表示这两个类之间距离，公式表示为： (2.7)（2）最长距离法：跟最短距离法类似，表示两类之间距离的是两类中距离最远的元素，公式为： . (2.8)（3）类平均法：求出两个类中任意两个数据的平均距离，用求出来的这个数据来表示这两个类的平均距离，这就是类平均法，我们可以用下面的公式来表示： (2.9)（4）重心距离法：它的定义表示两个类之间重心相邻的距离为类距离,公式表示为： (2.10)其中类的重心公式为： （也就是各元素的平均向量之间的距离）（5）离差平方和距离：用类中各元素的离差
29、平方和的总和得到两个类Gr和Gk的直径分别是Dr和Dk,类Gr+k=Gr Y Gk,用这种方法尽量让类间的离差平方和大，而类内部的元素间的值小，公式表示为： . (2.11)其中类直径：有的把类中相距最远的两个元素的距离作为直径，也有的将类中各元素指标的离差平方和的和作为直径，离差平方和的计算公式为： (2.12)2.2.4 聚类分析的一般步骤聚类分析的步骤大体可以分为四步9-10：（1）数据的预处理：就是在拿到一个数据集的时候，首先分析对这个数据的聚类分析要求，并根据这个要求对现在的数据集做降维或者特征标准化等初步的处理操作，也就是去掉没用的特征值。（2）特征的选择及提取：对于第一步得到的信
30、息，进一步细分，就是将预处理后的信息再选择最有效的特征，并将选择出来的特征用向量的方法转换成新的有效突出特征，以供聚类分组时作为分组判定的条件。（3）聚类：这就要用到前面的相似性度量函数，选择距离函数还是选择相似系数等方法来度量选出来的有效特征值的相似度，进而完成对该数据集的聚类分析。（4）评估结果：结果进行分析，看有没有完成预定的要求，并根据聚类方法的评价标准对结果进行科学评估，即聚类分析的九个方面的要求是否满足，然后根据评估结果判断是否对本次的分析过程进行改进，以及怎样改进。2.3 常用的聚类分析的方法介绍目前聚类分析算法的应用技术日趋成熟，已经有很多的聚类算法被提出来，但是算法种类增多，
31、同时这些算法的融合会越来越明显，使得各种算法的界限不明显，但是目前大家默认的有五种划分方法,分别是：以划分为基础的算法(Partitioning Methods)、以密度为基础的算法(DensitybasedMethods)、以层次的为基础的算法(HierarchicalMethods)、以模型为基础的算法(Modelbased Methods)、以网格为基础的算法(Gridbased Methods)。2.3.1 基于划分的方法划分算法11的基本思想就是通过迭代的方法将含有M个数据对象的数据集分成K个簇。具体步骤是，用户首先给定所要划分的簇的个数K，算法先进行初步划分为K组，然后用迭代的方法反复再进行分组，每次新得到的分组比前一次要优化，是否优化的判定标准是同组数据之间以及不同组数据之间的相似程度，同组相似程度越大组间相似程度越小分组越优化，目前常用的算法有K-means算法、K-medoid算法以及以它
