学位论文 > 优秀研究生学位论文题录展示

K-means算法的改进研究

作　者: 汤叶青
导　师: 陈明
学　校: 首都师范大学
专　业: 计算机软件与理论
关键词: 聚类分析 K-means算法遗传算法改进K-means算法
分类号: TP311.13
类　型: 硕士论文
年　份: 2012年
下　载: 2次
引　用: 0次
阅　读: 论文下载

内容摘要

在当代，随着计算机网络与数据库技术的发展，信息量变的越来越大，如何在海量的数据中找到有用的信息成为了一个非常重要的课题，数据挖掘技术在这种背景下应运而生。数据挖掘就是从大量的数据资料中发现有用的信息或知识，为科学决策提供依据。聚类分析技术是数据挖掘的一个重要的分析手段，是一种无监督的分类方法。聚类分析是在没有先验知识的情况下，将一个数据集划分成几个簇，使得相同簇中的数据特征尽可能相同，不同簇间的数据特征尽可能相异。目前聚类的算法很多，其中K-means算法因为思想简单，算法简洁，收敛性好成为应用最广最受欢迎的方法之一。然而K-means算法也有很多不足，如聚类结果对初始中心敏感，k值无法确定等。针对以上缺点，本文提出了一种改进的K-means算法和一种K值学习算法。改进的K-means算法是为了解决传统K-means算法的聚类结果对初始聚类中心敏感这一问题，同时提高算法的性能。改进算法主要是针对聚类数已知的聚类问题，只需用户输入k值就能执行。算法通过计算数据集中的各个数据点到原点的距离，然后按照距离大小排序，将数据集平均分成k组，之后将每组的中间的数据点选为初始中心。在将数据分配到各簇的操作中，通过优化处理大大减少了算法的时间复杂度。K值学习算法是为了解决传统K-means算法不能确定k值的缺点。在该算法中，引入了遗传算法。遗传算法是一种通过模拟自然界生物进化过程的随机化搜索方法，根据适应度函数，通过自然选择，交叉重组以及变异等遗传操作不断迭代更新种群以搜索到最优解。在本文的K值学习算法中，使用二进制编码，让每个个体代表一个k值，根据适应度函数，不断通过遗传操作进行迭代找到最佳聚类数。本算法采用了自适应的交叉概率和变异概率以加快算法的收敛性。最后通过两组实验分别测试改进K-means算法和K值学习算法的有效性。在第一组实验中，对五组数据分别执行传统K-means算法和改进K-means算法，从聚类结果和所耗时间上对两种算法进行比较；在第二组实验中对五组数据分别执行K值学习算法。实验表明改进K-means算法能够以更少的时间得到更好的聚类结果，通过K值学习算法寻找最佳聚类数非常可行。

K-means算法的改进研究

内容摘要

全文目录

相似论文