本科生毕业论文设计
数据挖掘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