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

基于遗传算法的K-means聚类算法分析研究

作　者: 孙秀娟
导　师: 刘希玉
学　校: 山东师范大学
专　业: 计算机软件与理论
关键词: 数据挖掘 K-means聚类算法遗传算法
分类号: TP18
类　型: 硕士论文
年　份: 2009年
下　载: 422次
引　用: 12次
阅　读: 论文下载

内容摘要

近年来,随着信息技术的发展,信息资源的经济和社会价值越来越重要。通过数据挖掘,从大量的数据资料中发现有价值的、人们感兴趣的信息或知识,可以达到为科学决策提供支持的目的。聚类分析是数据挖掘的一项基本任务,是一种无监督的分类方法。聚类的目标是把一个无类别标记的数据集按某种准则划分成不同的簇,使相同簇中数据的相似性尽可能小,而不同簇间数据相似性尽可能大。聚类的应用非常广泛,无论是在商务领域,还是在Web文档分类、图像处理等其它领域,都得到有效的应用。目前聚类算法大体上分为基于划分的方法、基于层次的方法、基于模型的方法、基于网格的方法、基于密度的方法等。K-means算法是聚类分析的主要算法之一,是一种基于划分的聚类算法。该算法随机选取k个点作为初始聚类中心,通过一个迭代过程完成聚类。该算法有它固有的不足:它容易陷入局部极小值而得不到全局最优解;算法在进行聚类时要求有固定的K值,这对于没有经验的用户来说很困难;初始中心的选择对聚类结果有很大影响;一般的聚类算法对孤立点数据和噪声比较敏感。遗传算法是一种通过模拟自然进化过程搜索最优解的算法,它通过基因组合、交叉、变异、自然选择等一系列过程达到优化的目的。在这些过程中,通过“优胜劣汰”的原则淘汰掉解较差的基因,使得解朝着好的方向发展。它从一组初始可行解出发在只需要目标函数这一信息的条件下实现对可行域的全局高效搜索并以概率1收敛到全局最优解,具有隐含并行性和对全局信息的有效利用能力的显著特点,这种良好的特性使得遗传算法成为函数优化和组合优化的有力工具。因此,将遗传算法和K-means算法有效结合,充分发挥遗传算法的全局寻优能力和K-means算法的局部搜索能力,可以更好地提高聚类质量。针对传统遗传算法和聚类算法存在的缺陷,本文提出了一种改进的遗传k均值算法,该算法的改进之处:在遗传算法中采用自识别交叉算子和自适应变异算子,自识别交叉算子可以保证群体的优良模式遗传到下一代,加快了算法收敛速度,自适应变异算子扩大了搜索范围,增强了算法跳离局部最优解的能力;优化K-means聚类算法的初始中心,避免初始中心选择的随机性;根据适应度函数动态地确定合适的聚类数k值;使用了基于加权的K-平均的方法计算类中心,减小K-means算法对噪声和孤立点数据的敏感性。该文实验采用标准数据集来测试改进算法的有效性,设计了三套实验方案对改进算法和其它算法进行测试,并以图表和表格的形式对实验结果进行比较说明,得出了改进算法优于其它算法的结论。

全文目录

摘要  6-8
ABSTRACT  8-10
第一章绪论  10-16
  1.1 研究背景及选题意义  10-11
  1.2 国内外研究概况  11-14
    1.2.1 遗传算法的研究现状  11-12
    1.2.2 聚类的研究现状  12-14
    1.2.3 混合算法的研究现状  14
  1.3 论文的内容安排  14-16
第二章数据挖掘  16-21
  2.1 数据挖掘的基本概念  16
  2.2 数据挖掘的目的  16-17
  2.3 数据挖掘的分类  17-18
  2.4 数据挖掘的功能  18-19
  2.5 数据挖掘的应用、影响及意义  19-20
  2.6 本章小结  20-21
第三章聚类分析  21-34
  3.1 聚类分析的定义  21
  3.2 聚类分析的数据结构  21-22
  3.3 聚类分析中的相似度度量方法  22-25
  3.4 聚类准则函数  25-27
  3.5 聚类分析的方法  27-30
    3.5.1 划分方法  27-28
    3.5.2 BIRCH 算法  28-29
    3.5.3 DBSCAN 算法  29-30
    3.5.4 STING 算法  30
  3.6 聚类结果的评价  30-33
  3.7 本章小结  33-34
第四章基于遗传算法的改进K-means聚类分析  34-51
  4.1 简单遗传算法  34-40
    4.1.1 遗传算法的基本原理  34
    4.1.2 遗传算法的构成要素  34-37
    4.1.3 遗传算法描述  37-38
    4.1.4 遗传算法的优缺点  38-40
  4.2 K-means 算法  40-41
    4.2.1 K-means 算法的原理  40
    4.2.2 K-means 算法的优缺点  40-41
  4.3 基于遗传算法的K-means 聚类算法  41-45
    4.3.1 遗传K-means 算法的基本原理  41-44
    4.3.2 主控程序算法描述  44-45
  4.4 遗传算子的改进  45-46
    4.4.1 自识别交叉算子  45
    4.4.2 自适应变异算子  45-46
  4.5 K-means 初始中心的优化  46-47
  4.6 消除K-means 中的噪声和孤立点数据  47
  4.7 基于适值函数的K 值选择  47-48
  4.8 基于遗传算法的改进K-means 算法  48-50
  4.9 本章小结  50-51
第五章仿真实验的结果与评价  51-56
  5.1 实验设计  51
  5.2 方案一的实施  51-53
    5.2.1 测试函数  51-52
    5.2.2 测试结果与分析  52-53
  5.3 方案二的实施  53-54
    5.3.1 方案二的设计  53-54
    5.3.2 实验结果分析  54
  5.4 方案三的实施  54-55
    5.4.1 方案三的设计  54
    5.4.2 实验结果分析  54-55
  5.5 本章小结  55-56
第六章总结与展望  56-57
参考文献  57-60
攻读硕士学位期间发表的学术论文及参与的项目  60-61
致谢  61

基于遗传算法的K-means聚类算法分析研究

内容摘要

全文目录

相似论文