基于遗传算法的K-MEANS聚类挖掘算法的研究毕业论文.doc
《基于遗传算法的K-MEANS聚类挖掘算法的研究毕业论文.doc》由会员分享，可在线阅读，更多相关《基于遗传算法的K-MEANS聚类挖掘算法的研究毕业论文.doc（67页珍藏版）》请在冰点文库上搜索。
基于遗传算法的k-means聚类挖掘算法的研究
摘要
数据挖掘是随着信息技术不断发展而形成的一门新学科，是信息处理和数据库技术领域的一个新兴的研究热点。
数据挖掘的任务是从海量数据中发现隐含的有用知识，为科学决策提供支持。
聚类分析是数据挖掘的一个非常重要的研究分支。
聚类是一种无监督的分类方法，目标是在没有任何先验知识的情况下，将数据集划分成不同的类，使得相同类中的对象尽可能相似，不同类中的对象尽可能相异。
k-means算法作为聚类分析中的经典算法现已被广泛应用在商务、市场分析、生物学、文本分类等领域。
然而，k-means算法具有对初始值敏感、易陷入局部极小值等缺点。
因此，改进k-means算法以进一步提高聚类效果具有十分重要的意义。
本文首先详细地介绍了聚类分析技术，对现有的聚类算法进行了分类，分析了这些算法的优缺点，并在此基础上，重点研究了k-means算法。
其次，全面分析了数据挖掘中的一个重要算法——遗传算法。
在此基础上，结合k-means算法的思想和特点，提出了一种改进的遗传k-means聚类算法，从编码方法、适应度函数的构造、交叉算子和变异算子的设计、k-means优化操作等方面进行了详细的讨论和分析。
最后，为了测试本文提出的聚类算法的性能，本文用k-means算法和改进的算法进行了三组实验，并对两种算法的聚类结果进行比较，实验结果表明本文算法能够有效地解决聚类问题。
关键词：
数据挖掘聚类分析遗传算法k-means算法改进的遗传k-means算法
RESEARCHOFK-MEANSCLUSTERINGINDATAMININGBASEDONGENETICALGORITHM
ABSTRACT
Dataminingisanewsubjectformedwiththedevelopmentoftheinformationtechnologyandisanewresearchpointintheinformationanddatabasetechnology.Thepurposeofdataminingistodiscoveryhiddenandusefulknowledgefromhugeamountsofdata,whichcansupportthesciencedecision.
Clusteranalysisisoneoftheimportantthemesindatamining.Clusteringisaunsupervisedclassifyingmethod,thegoalofclusteringistopartitiondatasetintosuchclustersthatobjectswithinaclusterhavehighsimilarityincomparisontooneanother,butareverydissimilartoobjectsinotherclusterswithoutanypriorknowledge.Asaclassicalmethodofclusteringanalysis,k-meanshasbeenwidelyusedincommerce,marketanalysis,biology,textclassificationandsoon.Howeverk-meanshastwoseveredefects—sensitivetoinitialdataandeasytogetintoalocaloptimum.Onthiscondition,improvingk-meansisaneffectivemethodtogetbetterclusteringresult.
Firstly,thedissertationdetailedlyintroduceclusteringanalysistechnology,andmostexistingclusteringalgorithmsareclassified,analysistheiradvantagesanddisadvantages.Onthebasis,thedissertationchoosesk-meansasresearchtarget.
Secondly,analyzinganimportantmethod—geneticalgorithmsindatamining.Onthisbasis,anewclusteringmethodofk-meansbasedonimprovedgeneticalgorithmisproposed.Thedissertationdiscussersandanalysesthenewalgorithmsindetailfromcodingmethod,fitnessfunction,selectionoperators,crossoveroperators,mutationoperators,k-meansoperatorsandotheraspects.
Finally,fortestingtheperformanceoftheproposedalgorithms,thedissertationgivesthreesimulationexperiments.Simulationresultsshowthatcomparingwithk-meansmethod,theproposedcangetabetterclusteringresult.
KEYWORDS：
DataminingClusteranalysisGeneticalgorithmk-meansIGKA
目录
第一章绪论 1
1.1课题研究背景与意义 1
1.1.1数据挖掘概述 1
1.1.2数据挖掘中聚类分析 5
1.1.3遗传算法与数据挖掘 5
1.2国内外研究现状 6
1.2.1数据挖掘的研究现状 6
1.2.2聚类分析研究现状 6
1.2.3遗传算法研究现状 6
1.2.4遗传聚类研究现状 7
1.3本课题主要研究内容 8
1.4本文章节安排 9
第二章聚类分析 10
2.1聚类分析的基本概念[30] 10
2.2数据挖掘对聚类算法的要求 10
2.3聚类分析中的数据结构和类型 11
2.3.1聚类分析中的数据结构 11
2.3.2聚类分析中的数据类型 12
2.4聚类分析中的相似度度量方法 15
2.4.1距离 16
2.4.2相似系数 17
2.5聚类分析中的聚类准则函数[34] 17
2.6聚类算法的分类及其典型算法 19
2.6.1基于划分的方法 19
2.6.2基于层次的方法 20
2.6.3基于密度的方法 20
2.6.4基于网格的方法 20
2.6.5基于模型的方法 21
2.6.6模糊聚类 21
2.7聚类分析在数据挖掘中的应用 21
2.8本章小结 22
第三章遗传算法的基本原理 23
3.1遗传算法的历史与发展 23
3.2遗传算法的基本术语[45] 24
3.3遗传算法的特点[46] 24
3.4遗传算法的基本要素 25
3.5遗传算法的描述及流程 27
3.5.1遗传算法的描述[47] 27
3.5.2遗传算法的执行过程 28
3.6遗传算法的应用 29
3.7本章小结 30
第四章一种改进的遗传K-MEANS聚类算法 31
4.1k-means算法的思想与流程 31
4.1.1k-means算法思想[49] 31
4.1.2k-means算法流程 32
4.2k-means算法的特点 33
4.3基于k-means的改进聚类算法 34
4.4聚类分析中的遗传算法 34
4.5改进的遗传k-means算法（IGKA） 35
4.5.1IGKA算法流程 35
4.5.2目标函数 37
4.5.3编码方法 38
4.5.4种群初始化 38
4.5.5适应度函数的设计 39
4.5.6选择操作 39
4.5.7交叉操作 40
4.5.8变异操作 41
4.5.9k-means优化操作（KMO） 42
4.5.10算法终止条件 42
4.6本章小结 42
第五章实验结果与比较分析 43
5.1实验平台 43
5.2实验结果和分析 43
5.2.1实验一 43
5.2.2实验二 45
5.2.3实验三 47
5.2.4结果分析 51
5.3本章小结 52
总结与展望 53
参考文献 55
致谢 58
攻读学位期间发表的学术论文 59
21
第一章绪论
1.1课题研究背景与意义
1.1.1数据挖掘概述
近年来，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，加上使用先进的数据采集工具，人们积累的数据知识越来越多[1]。
人们希望将这些数据转换成有用的信息和知识，以便更好地利用这些数据，用于决策。
目前的数据库系统已经可以高效地实现海量数据的录入、查询、统计等功能，可以忠实地完成作为记录者的任务，但是却无法发现隐藏在这些数据背后的有用信息和知识[2]，如关系和规则，更不能根据现有数据预测未来的发展趋势。
由于缺乏挖掘数据背后隐藏的知识的有力手段，从而导致“数据爆炸但知识缺乏”的现象。
面对“被数据淹没，却饥饿于知识”的挑战，数据挖掘应运而生，并得以蓬勃发展，越来越显示出其强大的生命力[3][4][5]。
数据挖掘是一种能够智能地、自动地把数据转换成有用信息和知识的技术[6]，它不但可以帮助人们从数据库，特别是数据仓库的相关数据中提取出感兴趣的知识、规律或更高层次的信息，而且也可以帮助人们从不同角度上去分析它们，从而更有效地利用数据。
它不仅可以用于描述过去数据的发展过程，而且还能进一步预测未来的发展趋势。
因此，数据挖掘正在成为一个崭新的、日益受到重视的热点研究领域。
1．数据挖掘的概念
数据挖掘（DataMining,DM）指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用信息和知识的过程[7]。
这个定义包括以下四个层次的含义：
（1）数据源必须是真实的、大量的、含噪声的；
（2）发现的是用户感兴趣的知识；
（3）发现的知识要可接受、可理解、可运用，最好能够用自然语言来表达发现结果；
（4）并不是要求发现放之四海皆准的知识，是有特定前提和约束条件、面向特定领域的。
2．数据挖掘的过程
数据挖掘是指一个指根据对数据分析建立对数据的特性以及数据之间关系描述的模式的过程。
从工程角度来讲，数据挖掘过程并不是线性的，为了得到好的结果需要经过多次反复地重复挖掘步骤。
目前人们对整个数据挖掘过程并没有给出非常清楚的划分，一般来说主要有以下几个步骤[8]，见图1-1。
图1-1数据挖掘的过程
Fig.1-1TheProcessofdatamining
（1）确定业务对象。
明确应用领域，清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。
在这个步骤中，数据挖掘人员必须和领域专家以及最终用户紧密协作，明确实际工作对数据挖掘的要求。
后续的数据准备和挖掘算法选择都是在此基础上进行的。
（2）数据准备。
数据准备又可分为三个子步骤：
数据选取（DataSelection）、数据预处理（DataPreprocessing）和数据变换（DataTransformation）。
数据选取的目的是确定发现任务的操作对象，即目标数据，它是根据用户的需要从原始数据库中抽取的一组数据。
数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换等。
当数据挖掘的对象是数据仓库时，一般来说，数据预处理已经在生成数据仓库时完成了。
数据变换的主要目的是减少数据量或降低数据的复杂性，即从初始特征中找出真正有用的特征，以减少数据挖掘时要考虑的特征或变量个数。
（3）数据挖掘。
该阶段首先根据第一步中对业务问题的定义明确挖掘的任务或目的，如分类、聚类、关联规则发现或序列模式发现等，选取合适的数据挖掘算法。
选择实现算法有两个考虑因素：
一是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求。
然后运用选定的挖掘算法，对所得到的经过转换的数据进行挖掘，从数据库中发现有用的知识或模式。
在这个阶段除了选择合适的挖掘算法外，其余一切工作都能自动地完成。
（4）知识的解释和评估。
数据挖掘阶段挖掘出来的模式，经过评估，可能存在冗余或无关的模式，这时需要将其剔出，也有可能模式不满足用户要求，这时则需要整个挖掘过程回退到前一阶段，如重新选取数据、采用新的数据变换方法、设定新的参数值，甚至换一种算法等。
另外，由于数据挖掘最终要面向用户，因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示。
3．数据挖掘的任务[9]
数据挖掘可以解决大量的商业问题。
基于这些商业问题的性质，把这些问题分成下面几种数据挖掘任务。
（1）分类
分类是指基于一个可预测性属性把事例分成多个类别。
每个实例包含一组属性，其中有一个可预测性属性——类别（class）属性。
分类任务要求找到一个模型，该模型将类别属性定义为输入属性的函数。
分类数据挖掘中应用的最多的任务。
（2）聚类
聚类也称细分，它基于一组属性对事例进行分组。
在同一个聚类中的事例或多或少有相同的属性值。
聚类是一种无监督的数据挖掘任务，没有一个属性用于指导模型的构建过程，所有的属性平等对待。
后面本文将专门讨论数据挖掘中的聚类分析技术。
（3）关联分析
关联分析又叫购物篮分析，它是当两个或多个数据项的取值之间重复出现且概率很高时，就表示这些数据项之间存在关联，可以建立起这些数据项的关联规则。
一般用“支持度”和“置信度”两个阈值来淘汰那些没有用的关联规则。
（4）时序模式
通过时间序列搜索出重复发生概率较高的模式，强调时间序列的影响。
在时序模式中，需要找出在某个最小时间内出现概率一直高于某一最小百分比（阈值）的规则。
（5）预测
预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据的种类、特征等。
（6）偏差分析
偏差分析也叫孤立点（outlier）分析，它用来检测与前面观察的行为有重大改变的行为。
数据库中的数据常有一些异常记录，从数据库中检测出这些偏差很有意义。
偏差分析的基本方法是寻找观察结果与参照之间的差别，找出特殊的事例。
最常用于信用卡欺诈行为检测和网络入侵检测。
4．数据挖掘的对象[10]
原则上讲，数据挖掘可以在任何类型的信息存储上进行，这包括关系数据库、数据仓库、事务数据库、WWW、面向对象数据库、对象-关系数据库、时间序列数据库、空间数据库、文本数据库、多媒体数据库等。
挖掘的原始数据可以是结构化的，如关系数据库、数据仓库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。
5．数据挖掘的应用
数据挖掘从理论研究到产品开发至用了短短数年，目前在国内外已经进入应用阶段。
数据挖掘技术的应用十分广泛，在市场营销、保险、通信网络管理、科学研究、产品制造业、金融投资等行业都可以找到它的用武之地[11][12]。
（1）零售业
零售业是数据挖掘应用较为活跃的一个领域。
了解客户的购买习性和趋向，对于零售商制定销售策略是至关重要的。
销售分析人员运用关联规则挖掘技术对大量的销售数据进行分析，可以发现顾客购买模式和趋势，改进服务质量，取得更好的顾客保持力和满意程度，提高货品销售比率，设计更好的货品运输与分销策略，减少商业成本。
购物篮分析是数据挖掘技术应用在零售业中的一种有效方式，可用于销售搭配、产品目录设计、产品定价和促销等。
（2）保险业
保险是一项风险业务，保险公司的一个重要工作就是进行风险评估。
通过研究证明，可以利用数据挖掘技术来进行风险分析，在保险公司建立的保单及索赔信息数据库的基础上，寻找保单中风险较大的领域，从而得出一些实用的控制风险的规则，以指导保险公司的工作。
数据挖掘技术在保险业中的应用，有利于保险公司开展业绩评价、财务预算、市场分析、风险评估和风险预测等，大大提高企业防范和抵抗经营风险的能力和水平，也为管理人员提供科学的决策依据。
（3）电信业
在电信企业，借助数据挖掘技术，可以帮助企业分析用户使用电信业务的情况，评估用户的行为，优化广告投入，提升企业客户洞察力，发掘客户需求，提升客户的满意度和忠诚度。
（4）科学研究
在信息量极为庞大的天文、气象、生物技术等领域中，所获得的大量试验和观测数据已经使传统的数据分析工具难于对付，因此迫切要求功能强大的智能化自动分析工具。
这种需求推动了KDD技术在科学研究领域的应用发展。
（5）其他行业例如在医药、司法、工业等部门也得到了应用。
尽管数据挖掘的应用领域相当广泛，就我国当前的应用来看，尚处于萌芽阶段，企业大规模地运用数据挖掘技术的尚不多。
随着IT技术在社会经济生活中的广泛应用，海量数据的产生己成为必然现象，数据挖掘在各个行业的应用研究也必然成为现实。
因此，未来数据挖掘应用领域的研究将更加广泛。
1.1.2数据挖掘中聚类分析
聚类分析[13]是数据挖掘中一种非常重要的技术，是分析数据并从中发现有用信息的一种有效手段，它涉及到许多研究领域，包括数据挖掘、统计学、人工智能以及机器学习等。
基于“物以类聚”的朴素思想，聚类按照一定的聚类准则将数据对象分组成为若干个类或簇，使得在同一类中的对象之间尽可能相似，而不同类中的对象尽可能相异，通过聚类，人们能够识别密集和稀疏的区域，发现全局的分布模式以及数据属性之间有趣的相互关系。
由于符合人类认知世界的思维模式，聚类分析广泛应用于很多方面，例如文本挖掘、信息检索、地质学、图像分割、客户关系管理和市场分析等等。
随着数据库中存储的数据越来越多，聚类分析已经成为数据挖掘中一个非常活跃的研究课题。
1.1.3遗传算法与数据挖掘
遗传算法[14]（GeneticAlgorithms,GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种全局随机搜索算法。
它从一组初始可行解出发，在不需要除适应度函数之外的其它信息的条件下，对多个个体组成的种群进行选择、交叉、变异等操作，使个体间的信息得到交换，实现群体中的个体一代一代的演化并逐步逼近全局最优解。
这种算法的主要特点[15]是简单、通用、鲁棒性强和适合并行处理，群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息，只需少量结果就可以反映探索空间较大的区域，便于实时处理，而且具有较强的稳健性，可避免陷入局部最优。
这种良好的特性使它成为组合优化和函数优化的有利工具，并成为计算智能领域的研究热点。
数据挖掘是一门新兴的数据处理技术,涉及数据库技术、人工智能、机器学习、神经网络等学科。
遗传算法作为一种模拟自然进化思想的启发式全局寻优算法，是进化计算的杰出代表，也是机器学习的重要方法。
基于遗传算法的上述特点，将遗传算法引入数据挖掘领域越来越受到学术界的重视[16]，国外已经有不少成功的范例，如：
将遗传算法与数据挖掘中的聚类算法相结合，借助遗传算法启发式全局寻优和并行模式处理技术等优势，克服传统聚类算法的一些缺点，获取与客观事实相容的问题的解，从而提高聚类分析的效率和准确性。
因此，本课题具有实用价值和理论意义。
1.2国内外研究现状
1.2.1数据挖掘的研究现状
自1989年8月在第11届国际联合人工智能学术会议上首次提出数据挖掘一词以来，经过近二十年的努力，数据挖掘技术的研究已经取得了丰硕的成果，许过软件公司研制出的数据挖掘软件已经在北美、欧洲等国家得到了较为广泛的应用。
如，SAS公司的EnterpriseMiner、IBM公司的IntelligentMiner和Quest、SGI公司的SetMiner、SPSS公司的Clementine、Sybase公司的WarehouseStudio等等。
与国外相比，我国的数据挖掘研究开展较晚，直到1993年国家自然科学基金才首次支持该领域的研究项目。
90年代中后期才有一批研究成果（学术论文）逐渐发表在《计算机学报》、《软件学报》、《人工智能与模式识别》等刊物上，研究重点也从数据挖掘算法转向系统的实际应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透，但是研究内容还是以学术研究为主，实际应用研究虽然也在不断加强，却仍没有形成整体力量。
最近，GartnerGroup的一次高级技术调查将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。
1.2.2聚类分析研究现状
目前对聚类分析所涉及的研究领域很多，针对海量数据的有效和实用的聚类算法是聚类分析研究的主要内容。
传统的聚类算法大多局限于统计学和机器学习领域，本质上也都属于局部搜索算法，是采用一种迭代的爬山技术来寻找最优解。
因此，传统的聚类算法存在着两个致命的问题：
一是在处理大规模数据的问题时，原有算法失效或耗费大量时间，二是容易陷入局部极小值。
如何利用并改进传统的聚类算法使之在处理大规模数据时能够得到有用的信息，越来越受到人们的重视。
1.2.3遗传算法研究现状
目前遗传算法的大体框架已经形成，人们所做的主要工作集中在算法的理论基础、算法设计、执行策略和应用领域的拓展。
其中遗传算法的理论基础研究主要集中在对其搜索机理、收敛性、收敛速度、有效性等基本问题的探索，其目的是从理论上阐明工作原理与性能，为算法的发展、比较与应用提供理论基础。
基本遗传算法存在过早收敛于局部最优解的缺陷。
此外，遗传算法的收敛速度比较慢，在实际应用方面受到了一定的限制。
所以，针对传统的遗传算法的缺点，目前的研究热点有：
（1）改进遗传算法的组成成分或使用技术，如选用适合问题特性的编码方式、改进遗传操作或通过增加一些全新的操作数来提高遗传算法的搜索能力；
（2）将遗传算法与其它技术（如：
模拟退火算法、神经网络、粗糙集、免疫算法、小生境技术等）相结合构成混合遗传算法，使算法间相互取长补短。
同时弥补原有算法的缺陷。
（3）由于遗传算法具有隐含并行性，可以使用并行遗传算法来解决问题，现在越来越多的学者致力于研究该课题，其发展潜力不容忽视。
1.2.4遗传聚类研究现状
众所周知，数据挖掘与其它传统聚类分析不同[17]，数据挖掘经常要处理大量高维数据集，通常包含几百万个由几十、几百甚至几千种特征或变量描述的目标。
然而，当应用于大量数据集时，数据挖掘中使用的现有的大多数聚类算法都不能很好的奏效，同时，数据挖掘中的数据通常既包含数值特征又包含类属特征。
大多数现有的聚类算法或者能分析这两种数据类型，但不能处理大数据集，或者能有效处理大数据集，但仅限于数值型。
聚类分析作为数据挖掘的一种重要手段和工具，其快速有效的算法研究越来越受到人们的重视。
遗传算法作为一种模拟自然进化思想的启发式全局寻优算法，其简单、通用、鲁棒性强和并行处理等特点使得它比盲目搜索的效率高很多，将遗传算法引入数据挖掘中的聚类领域越来越引起学术界的重视。
国内外学者花费大量的时间和
升级会员 