| 【中文题名】 | 一种基于变长编码的遗传K均值算法研究 |
| 【英文题名】 | A Research of Genetic K-Means Algorithm Based on Variable Length Encoding |
| 【学科专业】 | 软件工程 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-6-26 |
| 【中关键词】 | 数据挖掘,知识发现,遗传算法,变长编码,聚类,K均值 |
| 【英关键词】 | Data Mining,KDD,GA,variable-length encoding,clustering,K-Means,Business Intelligence, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
数据之间复杂的联系使数据背后隐藏着的模式难以被人们发现，数据所表征的对象的归类就是这样一种模式。当前，数据挖掘理论已经发展了种类繁多的聚类分析算法用于分析这一模式，它们各有其利弊，同时也有不少算法已经付诸实践。K均值就是其中一种简便易行的算法，但是它却存在着很多弊端。为了使K均值更加有效，许多学者都提出了K均值的改进型算法。
遗传算法在求解组合优化和函数最值等问题方面，被证明是行之有效的。遗传算法的机理同样适用于改进K均值聚类分析。虽然已有许多遗传算法被提出来用于优化K均值聚类的初始中心选择，或用于学习最佳的聚类数K，但都没能使二者完美地结合在一起。受到这些算法的启发，文中提出了一种基于变长编码的遗传机制将二者有机地结合起来，并取得了良好的效果。
基于变长编码的遗传K均值算法，不但能够优化聚类的初始中心，根据适值动态地学习K值，而且有时候还能够识别一些孤立点，有效地减轻了孤立点对K均值算法的影响。这都有赖于良好的K值学习机制，以及良好的适值度量函数的选取。关于K值的学习，本文提出了向“榜样”个体看齐的思想，使得K值动态地变化，摆脱了K值必须由用户指定的弊端。
为了更好地理解这... |
| 【论文题纲】 |
|
摘要 |
3-4 |
|
Abstract |
4-9 |
|
第1章 绪论 |
9-11 |
|
1.1 引言 |
9 |
|
1.2 数据挖掘的概念与起源 |
9-10 |
|
1.3 数据挖掘的应用、影响及意义 |
10 |
|
1.4 本文的主要研究成果 |
10-11 |
|
第2章 数据挖掘与知识发现原理简介 |
11-17 |
|
2.1 数据挖掘的环境 |
11-13 |
|
2.1.1 数据源 |
11-13 |
|
2.1.2 数据挖掘工具 |
13 |
|
2.2 数据挖掘的过程与方法论 |
13-16 |
|
2.2.1 数据挖掘的过程 |
13-15 |
|
2.2.2 聚类分析 |
15 |
|
2.2.3 关联分析 |
15-16 |
|
2.2.4 分类和预测 |
16 |
|
2.2.5 数据挖掘方法的综合 |
16 |
|
2.3 本章小结 |
16-17 |
|
第3章 聚类分析的K均值算法 |
17-23 |
|
3.1 聚类问题的模型 |
17-19 |
|
3.2 K均值算法 |
19-22 |
|
3.2.1 K均值算法的原理 |
19-20 |
|
3.2.2 K均值算法的收敛性分析 |
20-21 |
|
3.2.3 K均值算法与其他聚类算法相比的优缺点 |
21-22 |
|
3.3 本章小结 |
22-23 |
|
第4章 基于变长编码的遗传K均值算法 |
23-40 |
|
4.1 简单遗传算法 |
23-29 |
|
4.1.1 简单遗传算法的原理 |
23-26 |
|
4.1.2 遗传算法的模式定理与积木块假设 |
26-28 |
|
4.1.3 简单遗传算法的不足与改进 |
28-29 |
|
4.2 基于变长编码的遗传K均值聚类分析 |
29-39 |
|
4.2.1 问题的分析 |
29-31 |
|
4.2.2 染色体的编码与译码 |
31 |
|
4.2.3 适值函数的设计 |
31-34 |
|
4.2.4 遗传算子的设计 |
34-38 |
|
4.2.5 关于算法的进一步说明 |
38-39 |
|
4.3 本章小结 |
39-40 |
|
第5章 算法编码实践 |
40-51 |
|
5.1 面向对象的方法论与设计模式 |
40-42 |
|
5.2 测试数据的生成 |
42-43 |
|
5.3 原型系统的结构 |
43-50 |
|
5.3.1 软件的整体框架 |
43 |
|
5.3.2 模型描述模块 |
43-45 |
|
5.3.3 算法模块 |
45-49 |
|
5.3.4 数据库相关模块 |
49-50 |
|
5.3.5 其他模块 |
50 |
|
5.4 本章小结 |
50-51 |
|
第6章 仿真实验的结果及评价 |
51-56 |
|
6.1 实验的设计 |
51-52 |
|
6.2 实验结果的分析 |
52-54 |
|
6.2.1 方案1的实验结果 |
52-53 |
|
6.2.2 方案2的实验结果 |
53 |
|
6.2.3 方案3的实验结果 |
53-54 |
|
6.3 实验结果的评价 |
54-55 |
|
6.4 本章小结 |
55-56 |
|
第7章 总结和展望 |
56-57 |
|
附录A UML类图 |
57-59 |
|
附录B 仿真实验结果图 |
59-68 |
|
参考文献 |
68-70 |
|
致谢 |
70 |
|
| 【DOI】 | LunWen.ID:2.2008.388574 |
