基于模拟退火算法的聚类分析在数据挖掘中的应用

摘要

数据挖掘是近年来发展起来的新技术，通过数据挖掘，人们可以将知识发现的研究成果应用于实际数据处理中，为科学决策提供支持。目前数据挖掘逐渐发展成为一个多学科领域，涉及到多方面的技术，特别是和计算智能方法的结合越来越紧密。 聚类算法是数据挖掘中的核心技术之一，在整个数据挖掘过程中有着非常重要的作用。聚类算法的选择取决于聚类的数据、聚类的目的和应用。本文通过对数据挖掘技术中的常用聚类分析方法进行了详细的对比，并从综合评价聚类算法的5个方面对常用的聚类方法作了比较分析。 在对聚类算法进行比较分析的基础上，从聚类的本质特点出发，将计算智能中的模拟退火算法应用到数据聚类中。模拟退火算法是模拟物理退火过程的一种随机优化搜索算法。算法以优化过程的求解与物理退火过程的相似性为基础，通过接受准则和对下降温度的控制，能够有效的克服优化过程陷入局部极小从而获得全局最优解。因此，在解决多维，非线性的复杂组合优化问题中得到了广泛的应用。 本文针对标准的模拟退火算法的局限性，提出一种综合改进的模拟退火算法。算法对标准模拟退火算法的退火过程和抽样过程进行了修改。目的在于设计高效的退火历程，避免状态的迂回搜索。并将修改后的算法应用到聚类分析中进行验证。本文以中国股票市场从1992至2002年7月以来发行的一千多只股票在上市首日发行的各项相关数据为基础，利用综合改进后的模拟退火算法对其中的新股上市首日收益率进行聚类分析。分析结果表明大多新股在上市的首日便会有一个巨大的涨幅，由此产生远远高于市场平均回报的超额收益，同时结果表明改进的算法在保证聚类效果的前提下提高了算法的效率，整个过程算法的响应时间提高了近50％，具有较好的适用性。

目录

文摘

英文文摘

1绪论

1.1数据挖掘的兴起和发展

1.1.1数据挖掘起源

1.1.2数据挖掘研究现状

1.2计算智能的历史和国内外发展现状

1.2.1计算智能的历史渊源

1.2.2计算智能的发展状况

1.2.3模拟退火算法的提出及研究现状

1.3计算智能方法在数据挖掘中的应用

1.3.1数据挖掘过程计算智能方法的特点

1.3.2数据挖掘过程中计算智能方法的应用

1.4数据挖掘中的聚类分析

1.5本文的主要工作

2数据挖掘中聚类分析方法比较研究

2.1数据挖掘概述

2.1.1知识发现和数据挖掘的概念

2.1.2数据挖掘的任务

2.1.3数据挖掘的对象

2.1.4数据挖掘的方法和技术

2.1.5数据挖掘的知识表示

2.2聚类分析的发展研究现状

2.3常用聚类算法比较研究

2.3.1聚类方法的典型要求

2.3.2主要聚类方法的分类及比较标准

2.3.3数据挖掘领域中常用聚类方法的综合比较分析

3摸拟退火理论及其算法结构

3.1概述

3.1.1物理退火过程和Metropolis准则

3.1.2组合优化与物理退火的相似性

3.2 SA的算法结构及数学模型

3.2.1算法结构

3.2.2数学模型

3.3模拟退火的渐近行为

3.3.1平稳概率分布理论

3.3.2模拟退火的非时齐马氏链

3.3.3经典模拟退火算法的局限

4模拟退火算法的改进及其在聚类分析中的应用研究

4.1数据聚类中的传统模拟退火算法

4.2模拟退火算法关键参数和操作的设计

4.2.1状态产生函数

4.2.2状态接受函数

4.2.3起始温度的选取

4.2.4温度更新函数的确定

4.2.5内循环终止准则

4.2.6算法的终止准则(外循环终止准则)

4.3模拟退火算法的改进

4.3.1可行的改进方案

4.3.2两阶段的综合的改进策略

4.4模拟退火算法在新股上市首日收益率聚类分析中应用

4.4.1数据清理

4.4.2聚类实例分析

4.4.3算法性能分析

5结论与展望

致谢

参考文献