内容发布更新时间 : 2024/4/28 6:30:04星期一 下面是文章的全部内容请认真阅读。

青岛科技大学研究生学位论文

1.1.2数据挖掘中聚类分析

聚类分析[13]是数据挖掘中一种非常重要的技术，是分析数据并从中发现有用信息的一种有效手段，它涉及到许多研究领域，包括数据挖掘、统计学、人工智能以及机器学习等。基于“物以类聚”的朴素思想，聚类按照一定的聚类准则将数据对象分组成为若干个类或簇，使得在同一类中的对象之间尽可能相似，而不同类中的对象尽可能相异，通过聚类，人们能够识别密集和稀疏的区域，发现全局的分布模式以及数据属性之间有趣的相互关系。由于符合人类认知世界的思维模式，聚类分析广泛应用于很多方面，例如文本挖掘、信息检索、地质学、图像分割、客户关系管理和市场分析等等。随着数据库中存储的数据越来越多，聚类分析已经成为数据挖掘中一个非常活跃的研究课题。 1.1.3遗传算法与数据挖掘

遗传算法[14] (Genetic Algorithms, GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种全局随机搜索算法。它从一组初始可行解出发，在不需要除适应度函数之外的其它信息的条件下，对多个个体组成的种群进行选择、交叉、变异等操作，使个体间的信息得到交换，实现群体中的个体一代一代的演化并逐步逼近全局最优解。这种算法的主要特点[15]是简单、通用、鲁棒性强和适合并行处理，群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息，只需少量结果就可以反映探索空间较大的区域，便于实时处理，而且具有较强的稳健性，可避免陷入局部最优。这种良好的特性使它成为组合优化和函数优化的有利工具，并成为计算智能领域的研究热点。

数据挖掘是一门新兴的数据处理技术,涉及数据库技术、人工智能、机器学习、神经网络等学科。遗传算法作为一种模拟自然进化思想的启发式全局寻优算法，是进化计算的杰出代表，也是机器学习的重要方法。基于遗传算法的上述特点，将遗传算法引入数据挖掘领域越来越受到学术界的重视[16]，国外已经有不少成功的范例，如：将遗传算法与数据挖掘中的聚类算法相结合，借助遗传算法启发式全局寻优和并行模式处理技术等优势，克服传统聚类算法的一些缺点，获取与客观事实相容的问题的解，从而提高聚类分析的效率和准确性。因此，本课题具有实用价值和理论意义。

5

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

1.2国内外研究现状

1.2.1数据挖掘的研究现状

自1989年8月在第11届国际联合人工智能学术会议上首次提出数据挖掘一词以来，经过近二十年的努力，数据挖掘技术的研究已经取得了丰硕的成果，许过软件公司研制出的数据挖掘软件已经在北美、欧洲等国家得到了较为广泛的应用。如，SAS公司的Enterprise Miner、IBM公司的Intelligent Miner和Quest、SGI公司的SetMiner、SPSS公司的Clementine、Sybase公司的Warehouse Studio等等。

与国外相比，我国的数据挖掘研究开展较晚，直到1993年国家自然科学基金才首次支持该领域的研究项目。90年代中后期才有一批研究成果(学术论文)逐渐发表在《计算机学报》、《软件学报》、《人工智能与模式识别》等刊物上，研究重点也从数据挖掘算法转向系统的实际应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透，但是研究内容还是以学术研究为主，实际应用研究虽然也在不断加强，却仍没有形成整体力量。

最近，Gartner Group的一次高级技术调查将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。 1.2.2聚类分析研究现状

目前对聚类分析所涉及的研究领域很多，针对海量数据的有效和实用的聚类算法是聚类分析研究的主要内容。传统的聚类算法大多局限于统计学和机器学习领域，本质上也都属于局部搜索算法，是采用一种迭代的爬山技术来寻找最优解。因此，传统的聚类算法存在着两个致命的问题：一是在处理大规模数据的问题时，原有算法失效或耗费大量时间，二是容易陷入局部极小值。如何利用并改进传统的聚类算法使之在处理大规模数据时能够得到有用的信息，越来越受到人们的重视。

1.2.3遗传算法研究现状

目前遗传算法的大体框架已经形成，人们所做的主要工作集中在算法的理论基础、算法设计、执行策略和应用领域的拓展。其中遗传算法的理论基础研究主要集中在对其搜索机理、收敛性、收敛速度、有效性等基本问题的探索，其目的

6

青岛科技大学研究生学位论文

是从理论上阐明工作原理与性能，为算法的发展、比较与应用提供理论基础。

基本遗传算法存在过早收敛于局部最优解的缺陷。此外，遗传算法的收敛速度比较慢，在实际应用方面受到了一定的限制。所以，针对传统的遗传算法的缺点，目前的研究热点有：

(1) 改进遗传算法的组成成分或使用技术，如选用适合问题特性的编码方式、改进遗传操作或通过增加一些全新的操作数来提高遗传算法的搜索能力；

(2) 将遗传算法与其它技术 (如：模拟退火算法、神经网络、粗糙集、免疫算法、小生境技术等)相结合构成混合遗传算法，使算法间相互取长补短。同时弥补原有算法的缺陷。

(3)由于遗传算法具有隐含并行性，可以使用并行遗传算法来解决问题，现在越来越多的学者致力于研究该课题，其发展潜力不容忽视。 1.2.4遗传聚类研究现状

众所周知，数据挖掘与其它传统聚类分析不同[17]，数据挖掘经常要处理大量高维数据集，通常包含几百万个由几十、几百甚至几千种特征或变量描述的目标。然而，当应用于大量数据集时，数据挖掘中使用的现有的大多数聚类算法都不能很好的奏效，同时，数据挖掘中的数据通常既包含数值特征又包含类属特征。大多数现有的聚类算法或者能分析这两种数据类型，但不能处理大数据集，或者能有效处理大数据集，但仅限于数值型。聚类分析作为数据挖掘的一种重要手段和工具，其快速有效的算法研究越来越受到人们的重视。

遗传算法作为一种模拟自然进化思想的启发式全局寻优算法，其简单、通用、鲁棒性强和并行处理等特点使得它比盲目搜索的效率高很多，将遗传算法引入数据挖掘中的聚类领域越来越引起学术界的重视。国内外学者花费大量的时间和精力研究遗传算法在聚类中的应用，其中不断有人提出基于遗传算法的聚类方法，并做着各种改进，来提高算法的效率，例如：

1992年刘健庄等人提出了基于遗传算法的k-means算法和模糊c-均值算法

[18][19]

；1993年Falk提出了分组遗传算法(Grouping Genetic Algorithm, GGA)[20]，

他致力于设计适当的染色体编码来表示问题的解，并应用于各种分组、分割以及聚类问题；1999年Krishma以k-means算子代替交叉算子，设计了一种混合遗传算法[21]，并根据Gunter引入的有限状态齐次马尔科夫链方法证明了该算法以概率1收敛到全局最优点；2000年Manlik采取聚类中心的浮点数编码方式[22]，设计了浮点数交叉、变异操作，从而提高了遗传算法的搜索效率；2002年Cristofor.D将遗传算法与k-means结合起来，并且使用变长基因编码，不仅提高了k-means

7

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

算法的效率，还能运行多个k-means算法以确定合适的k值[23]；Sarafis则将遗传算法应用于k-means的目标函数构建中，提出了一个新的聚类算法[24]；2005年武兆慧等人提出了一种基于模拟退火遗传算法的聚类分析算法[25]；2006年赵峰等人提出了基于复合型遗传算法的k-means优化聚类方法[26]，通过引入复合形法改善遗传算法种群的质量，克服遗传算法和k-means算法的缺点，同时提高了收敛速度；2008年王艳华等人提出了一种基于免疫遗传的k-means聚类算法分析[27]，克服了传统k-means局部最优的缺点和简单遗传算法聚类后即收敛速度慢、易陷入早熟的缺点；2008年贾兆红等人提出了一种基于混合遗传算法的聚类方法[28]，通过引入禁忌搜索提高了遗传聚类的收敛速度；2008年廖喜讯等人提出了基于小生境遗传算法的层次聚类算法[29]，等等。

随着数据挖掘应用领域的不断拓展，将遗传算法引入数据挖掘中聚类分析中，为数据挖掘提供了一个崭新的思考模式，指出了一个新的研究方向。

1.3本课题主要研究内容

通过大量搜集和阅读国内外文献资料，本课题在理解数据挖掘的概念、掌握数据挖掘技术的应用步骤的背景下，从理论、算法和应用的角度对数据挖掘中的聚类分析做进一步的探讨和研究。主要研究内容包括：

(1) 数据挖掘技术的研究

在数据挖掘相关概念的基础上，对数据挖掘的过程、任务、对象、做了简单的归纳和总结。同时，对数据挖掘的研究现状和发展趋势也进行了客观的分析。

(2) 聚类分析技术的研究

在理解了聚类分析基本概念的基础上，根据数据挖掘对聚类算法的要求，从聚类分析的对象、聚类相似度度量、聚类准则函数等不同的角度对聚类分析中的算法进行全面考察，并对现有的算法进行了分类，分析了各类算法的优缺点，以及针对这些缺点对这些算法所做出的改进；通过对现有算法的性能比较，有利于数据挖掘用户根据自己的要求选择合适的聚类算法，以获得较好的聚类结果。对其核心算法—k-means算法进行了重点研究，详细研究和分析了k-means算法的思想原理和过程，以及目前存在的问题和已有的解决方案。

(3) 遗传算法的研究

介绍遗传算法的基本概念和基本思想，分析了遗传算法中编码方案、适应度函数构造以及遗传算子的设计和改进方法，同时对遗传算法的应用流程和算法思想也做了分析研究。

(4) 基于遗传算法的聚类算法研究。

8

青岛科技大学研究生学位论文

在数据挖掘、聚类分析和遗传算法的分析研究的基础上，论述了应用遗传算法进行聚类分析的算法思想，讨论了聚类问题的编码方式和适应度函数的构造方案，分析了不同遗传操作对聚类效果的影响。在此基础上提出了一种改进的遗传k-means聚类方法，并通过相关实验证明了算法的有效性和可行性，实验效果良好。

1.4本文章节安排

本文共分五章，具体安排如下：

第一章，介绍了本课题的研究背景和科学意义，分析了国内外对遗传聚类挖掘的研究，概括了本课题的主要研究内容以及论文章节安排。

第二章，详细介绍了聚类分析的概念、数据挖掘对聚类算法的要求，聚类分析中的数据结构和类型，相似度度量方法、聚类准则函数、主要的聚类算法以及聚类在数据挖掘中的应用。

第三章，简单介绍了遗传算法基本概念以及特点，重点介绍了遗传算法的基本要素，并对遗传算法思想和应用流程进行了描述。

第四章，介绍了聚类分析中的k-means算法，提出了一种改进的遗传k-means聚类算法，对此算法进行了全面描述。

第五章，为了验证本文提出算法的有效性进行测试实验，根据试验结果并对几种方法进行了对比分析，证实了该方法的可行性和有效性，取得了良好的效果。

最后，对本文的研究工作做了总结，并对未来工作进行了展望。

9