基于禁忌搜索和相似度的聚类算法研究

摘要

在这个“信息爆炸”的时代，人们经常面对着海量的数据，例如海量文本数据、Web数据、多媒体数据等，而这些数据中隐藏着大量的对人们有用的重要信息，如何用某种有效手段，从这些海量数据中提取出这些潜在有用的、可以用于提供决策支持的信息，数据挖掘便应运而生了。聚类作为数据挖掘的一个重要分支，对人们的日常生活都产生非常重要的影响。现在聚类主要的技术可以分为:划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法。
　　本文的主要研究工作包括下面两个方面;
　　1.从基于划分的K-medoids聚类算法的理论基础入手，探讨K-medoids算法的不足，提出了一种基于改进禁忌搜索的K-medoids聚类算法。禁忌搜索算法是模拟人类短暂记忆的一种优化算法，具有很强的全局搜索能力。针对禁忌搜索算法比较依赖初始解的缺点，将粒计算和最大距离积算法相结合，将改进后的禁忌搜索算法提高了K-medoids聚类的准确率，有较强的稳定性。通过仿真实验，验证了该方法的可行性。
　　2.根据高维空间数据的特性，传统的低维的距离计算相似性的方法不合适用在高维空间中，提出了一种新的相似性度量方法。通过计算对象之间的相似度得到相似矩阵，结合层次聚类的思想，自底向上的对数据进行聚类分析。通过有效性分析，论证了该方法可行性。

目录

声明

摘要

第一章 绪论

1．1．研究的背景与研究的意义

1．2．数据挖掘的理论和应用

1．2．1．数据挖掘的发展背景

1．2．2．数据挖掘的研究现状

1．2．3．聚类的研究现状

1．2．4．聚类面临的挑战

1．2．5．禁忌搜索的研究现状

1．3．本文的组织和研究内容

第二章 聚类分析

2．1．聚类的形式化描述和过程

2．2．基本的聚类算法概述

2．3．聚类算法性能的比较

2．4．聚类分析中数据属性

2．5．相似性度量方法

2．5．1．距离度量

2．5．2．相似性度量

2．6．K-medoids聚类算法介绍

2．7．高维空间聚类概述

2．8．本章小结

第三章 基于改进禁忌搜索的K-medoids聚类算法

3．1 禁忌搜索算法基本理论

3．1．1 禁忌搜索的提出

3．1．2 禁忌搜索相关的概念

3．1．3 禁忌搜索算法的描述

3．2 最大距离积算法

3．3 相关定义

3．4 改进的禁忌搜索算法

3．5 算法设计

3．5．1 聚类的评价

3．5．2 算法描述

3．5．3 时间复杂度分析

3．6 仿真实验结果以及分析

3．7 本章小结

第四章 基于高维度数据相似性度量聚类方法

4．1 相似性函数设计

4．2 算法描述

4．3 时间复杂度分析

4．4 有效性分析

4．5 算例分析

4．6 仿真实验

4．7 本章小结

第五章 结论与展望

5．1 结论

5．2 展望

参考文献

致谢

攻读学位期间所发表的学术论文