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

基于遗传算法的k-means聚类方法的研究

作　者: 金微
导　师: 陈慧萍
学　校: 河海大学
专　业: 通信与信息系统
关键词: 数据挖掘聚类遗传算法 k-means算法基于遗传算法的k-means聚类方法
分类号: TP18
类　型: 硕士论文
年　份: 2007年
下　载: 640次
引　用: 10次
阅　读: 论文下载

内容摘要

近年来数据挖掘引起了信息产业界的广泛关注，其主要原因是存在大量的可用数据，并且迫切需要将这些数据转换成有用的信息和知识。通过数据挖掘，可以将知识发现的研究成果应用于实际数据处理中，为科学决策提供支持。聚类分析是数据挖掘的一项基本任务，是一个无监督的学习过程，聚类的目标是在没有任何先验知识的前提下，将数据聚集成不同的类，使得相同类中的对象尽可能相似，不同类中的对象差别尽可能大。通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的相互关系。在聚类分析中，k-means算法可以说是应用较为广泛的一种算法，但它的一个致命弱点是对初始值非常敏感而且容易陷入局部极小值，而遗传算法是一种通过模拟自然进化过程搜索最优解的方法，其显著特点是隐含并行性和对全局信息的有效利用能力，因此产生了基于遗传算法的k-means聚类方法(GKA)，它既能发挥遗传算法的全局寻优能力，又能兼顾k-means算法的局部搜索能力，从而更好地解决聚类问题，但其收敛速度与k-means算法相比就比较慢。本文以进一步提高算法收敛速度为目的，提出了一种改进的遗传k-means遗传算法。该算法是以GKA算法为基础，在允许个体包含空类的前提下对算法的各项操作作出改进；同时添加了增量式操作，对类中心和目标函数可以增量式计算，使算法的收敛速度得到了提高。本文还设计了一个聚类分析系统，利用该系统，经过实验验证基于遗传算法的k-means聚类方法的收敛效果要优于k-means算法；改进的GKA算法要比原GKA算法的收敛速度快，特别是当输入的变异概率比较小的时候，这种优势更明显。另外本文还提出将改进的GKA算法用于Web日志挖掘的用户聚类系统中。利用该算法对Web用户进行聚类可以避免初始值对聚类结果的影响，并且能搜索到全局最优解，更好的为用户提供个性化服务以及对Web站点进行改进优化。

全文目录

摘要  8-9
ABSTRACT  9-10
第一章绪论  10-20
  1.1 数据挖掘概述  10-16
    1.1.1 数据挖掘的产生背景  10
    1.1.2 数据挖掘的定义  10-11
    1.1.3 数据挖掘的任务  11-12
    1.1.4 数据挖掘的处理过程  12
    1.1.5 数据挖掘的主要技术  12-13
    1.1.6 数据挖掘的应用  13-15
    1.1.7 数据挖掘的研究现状和发展趋势  15-16
  1.2 聚类分析概述  16
    1.2.1 聚类分析的基本概念  16
    1.2.2 聚类分析的研究现状  16
  1.3 遗传算法概述  16-18
    1.3.1 遗传算法的基本思想  16-17
    1.3.2 遗传算法的研究现状  17-18
  1.4 课题研究的主要内容和文章的组织  18-20
第二章聚类分析  20-30
  2.1 聚类的形式化描述  20
  2.2 聚类分析的应用  20
  2.3 数据挖掘对聚类算法的要求  20-21
  2.4 聚类算法的基本数据结构类型  21-22
  2.5 相似度度量方法  22-23
    2.5.1 距离公式  22
    2.5.2 相似系数  22-23
  2.6 聚类分析中的聚类准则函数  23-25
  2.7 主要聚类算法  25-26
  2.8 K-MEANS算法及其改进算法  26-29
    2.8.1 k-means算法描述  26-28
    2.8.2 基于k-means算法的改进聚类算法的描述  28-29
  2.9 本章小结  29-30
第三章基于遗传算法的聚类分析  30-39
  3.1 遗传算法的特点  30-31
  3.2.遗传算法的组成结构  31-32
  3.3 遗传算法的基本过程  32-33
  3.4 用遗传算法进行聚类时要解决的问题  33
  3.5 基于遗传算法的K-MEANS聚类方法  33-38
    3.5.1 目标函数  34-35
    3.5.2 GKA算法步骤  35-37
    3.5.3 GKA算法的处理流程及伪代码  37-38
  3.6 本章小结  38-39
第四章改进的遗传K-MEANS聚类算法  39-49
  4.1 目标函数  39-40
  4.2 初始化  40
  4.3 适应度函数  40
  4.4 选择  40-41
  4.5 变异  41-42
  4.6 K-MEANS操作  42
  4.7 增量式优化操作  42-43
  4.8 改进的GKA算法的处理流程及伪代码  43-48
  4.9 本章小结  48-49
第五章实验结果与比较分析  49-63
  5.1 实验平台  49
  5.2 聚类分析系统  49-51
    5.2.1 系统的体系结构  49-50
    5.2.2 系统的可视化界面  50-51
  5.3 算法性能测试  51-61
    5.3.1 实验一  52-53
    5.3.2 实验二  53-55
    5.3.3 实验三  55-57
    5.3.4 实验四  57-58
    5.3.5 结果分析1  58-59
    5.3.6 实验五  59-60
    5.3.7 实验六  60-61
    5.3.8 结果分析2  61
  5.4 本章小结  61-63
第六章基于遗传K-MEANS聚类算法的WEB日志挖掘  63-67
  6.1 WEB日志挖掘分析  63
  6.2 WEB日志挖掘系统  63-66
    6.2.1 Web日志挖掘系统的介绍  63-64
    6.2.2 数据采集  64-65
    6.2.3 数据预处理  65
    6.2.4 Web用户聚类的实现  65-66
  6.3 本章小结  66-67
第七章结论与展望  67-69
  7.1 本文总结  67
  7.2 未来工作的展望  67-69
参考文献  69-72
致谢  72-73
发表论文清单  73

基于遗传算法的k-means聚类方法的研究

内容摘要

全文目录

相似论文