毕业论文(赵艳丽初稿)

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

摘要

数据挖掘是随着信息技术不断发展而形成的一门新学科，是信息处理和数据库技术领域的一个新兴的研究热点。数据挖掘的任务是从海量数据中发现隐含的有用知识，为科学决策提供支持。

聚类分析是数据挖掘的一个非常重要的研究分支。聚类是一种无监督的分类方法，目标是在没有任何先验知识的情况下，将数据集划分成不同的类，使得相同类中的对象尽可能相似，不同类中的对象尽可能相异。k-means算法作为聚类分析中的经典算法现已被广泛应用在商务、市场分析、生物学、文本分类等领域。然而，k-means算法具有对初始值敏感、易陷入局部极小值等缺点。因此，改进k-means算法以进一步提高聚类效果具有十分重要的意义。

本文首先详细地介绍了聚类分析技术，对现有的聚类算法进行了分类，分析了这些算法的优缺点，并在此基础上，重点研究了k-means算法。

其次，全面分析了数据挖掘中的一个重要算法——遗传算法。在此基础上，结合k-means算法的思想和特点，提出了一种改进的遗传k-means聚类算法，从编码方法、适应度函数的构造、交叉算子和变异算子的设计、k-means优化操作等方面进行了详细的讨论和分析。

最后，为了测试本文提出的聚类算法的性能，本文用k-means算法和改进的算法进行了三组实验，并对两种算法的聚类结果进行比较，实验结果表明本文算法能够有效地解决聚类问题。

关键词：数据挖掘聚类分析遗传算法k-means算法改进的遗传k-means算法

RESEARCH OF K-MEANS CLUSTERING IN DATA MINING BASED ON GENETIC ALGORITHM

ABSTRACT

Data mining is a new subject formed with the development of the information technology and is a new research point in the information and database technology. The purpose of data mining is to discovery hidden and useful knowledge from huge amounts of data, which can support the science decision.

Cluster analysis is one of the important themes in data mining. Clustering is a unsupervised classifying method, the goal of clustering is to partition data set into such clusters that objects within a cluster have high similarity in comparison to one another, but are very dissimilar to objects in other clusters without any prior knowledge. As a classical method of clustering analysis, k-means has been widely used in commerce, market analysis, biology, text classification and so on. However k-means has two severe defects—sensitive to initial data and easy to get into a local optimum. On this condition, improving k-means is an effective method to get better clustering result.

Firstly, the dissertation detailedly introduce clustering analysis technology, and most existing clustering algorithms are classified, analysis their advantages and disadvantages. On the basis, the dissertation chooses k-means as research target.

Secondly, analyzing an important method—genetic algorithms in data mining. On this basis, a new clustering method of k-means based on improved genetic algorithm is proposed. The dissertation discussers and analyses the new algorithms in detail from coding method, fitness function, selection operators, crossover operators, mutation operators, k-means operators and other aspects.

Finally, for testing the performance of the proposed algorithms, the dissertation gives three simulation experiments. Simulation results show that comparing with k-means method, the proposed can get a better clustering result.

KEY WORDS：Data mining Cluster analysis Genetic algorithm k-means

IGKA

目录

第一章绪论 (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.1 K-MEANS算法的思想与流程 (31)

4.1.1 k-means算法思想[49] (31)

4.1.2 k-means算法流程 (32)

4.2 K-MEANS算法的特点 (33)

4.3基于K-MEANS的改进聚类算法 (34)

4.4聚类分析中的遗传算法 (34)

4.5改进的遗传K-MEANS算法(IGKA) (35)

4.5.1 IGKA算法流程 (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.9 k-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)

第一章绪论

1.1课题研究背景与意义

1.1.1数据挖掘概述

近年来，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，加上使用先进的数据采集工具，人们积累的数据知识越来越多[1]。人们希望将这些数据转换成有用的信息和知识，以便更好地利用这些数据，用于决策。目前的数据库系统已经可以高效地实现海量数据的录入、查询、统计等功能，可以忠实地完成作为记录者的任务，但是却无法发现隐藏在这些数据背后的有用信息和知识[2]，如关系和规则，更不能根据现有数据预测未来的发展趋势。由于缺乏挖掘数据背后隐藏的知识的有力手段，从而导致“数据爆炸但知识缺乏”的现象。面对“被数据淹没，却饥饿于知识”的挑战，数据挖掘应运而生，并得以蓬勃发展，越来越显示出其强大的生命力[3][4][5]。

数据挖掘是一种能够智能地、自动地把数据转换成有用信息和知识的技术[6]，它不但可以帮助人们从数据库，特别是数据仓库的相关数据中提取出感兴趣的知识、规律或更高层次的信息，而且也可以帮助人们从不同角度上去分析它们，从而更有效地利用数据。它不仅可以用于描述过去数据的发展过程，而且还能进一步预测未来的发展趋势。因此，数据挖掘正在成为一个崭新的、日益受到重视的热点研究领域。

1．数据挖掘的概念

数据挖掘(Data Mining, DM)指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用信息和知识的过程[7]。这个定义包括以下四个层次的含义：

(1) 数据源必须是真实的、大量的、含噪声的；

(2) 发现的是用户感兴趣的知识；

(3) 发现的知识要可接受、可理解、可运用，最好能够用自然语言来表达发现结果；

(4) 并不是要求发现放之四海皆准的知识，是有特定前提和约束条件、面向特定领域的。

2．数据挖掘的过程

数据挖掘是指一个指根据对数据分析建立对数据的特性以及数据之间关系描述的模式的过程。从工程角度来讲，数据挖掘过程并不是线性的，为了得到好的结果需要经过多次反复地重复挖掘步骤。目前人们对整个数据挖掘过程并没有给出非常清楚的划分，一般来说主要有以下几个步骤[8]，见图1-1。

图1-1数据挖掘的过程

Fig.1-1 The Process of data mining

(1) 确定业务对象。明确应用领域，清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。在这个步骤中，数据挖掘人员必须和领域专家以及最终用户紧密协作，明确实际工作对数据挖掘的要求。后续的数据准备和挖掘算法选择都是在此基础上进行的。

(2) 数据准备。数据准备又可分为三个子步骤：数据选取(Data Selection)、数据预处理(Data Preprocessing)和数据变换(Data Transformation)。数据选取的目的是确定发现任务的操作对象，即目标数据，它是根据用户的需要从原始数据库中抽取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换等。当数据挖掘的对象是数据仓库时，一般来说，数据预处理已经在生成数据仓库时完成了。数据变换的主要目的是减少数据量或降低数据的复杂性，即从初始特征中找出真正有用的特征，以减少数据挖掘时要考虑的特征或变量个数。

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

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

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遗传算法研究现状

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

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

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

(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

算法的效率，还能运行多个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) 基于遗传算法的聚类算法研究。

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

1.4本文章节安排

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

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

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

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

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

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

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

第二章聚类分析

人类认识世界的一种重要方法是将认识的对象按照类别进行划分。同一事物往往具有更多的近似特征，因此分门别类地对事物进行研究远比在一个混杂多变的集合中研究更清晰、细致。“人以群分，物以类聚”，聚类作为一种重要的分类工具，在今天基于海量数据的分析中起着很大的作用。随着相关研究的开展，聚类分析被纳入数据挖掘范围，并成为数据挖掘中的一项核心技术。

2.1聚类分析的基本概念[30]

所谓聚类(Clustering)就是将物理对象或抽象对象的集合分成由相似对象组成的多个类。也就是说由聚类生成的簇是一组数据对象的集合，簇必须同时满足以下两个条件：(l)每个簇至少包含一个数据对象；(2)每个数据对象必须属于且唯一的属于一个簇。同一个簇中的数据对象尽可能相似，不同的簇中的数据对象尽可能相异。在许多应用中，可以将一簇中的数据对象作为一个整体来对待。

聚类就是按照一定的要求和规律对事物进行区分和分类的过程。在这一过程中没有任何关于分类的先验知识，也没有教师的指导，仅靠事物间的相似性作为类属划分的准则，因此属于无监督分类的范畴。

聚类分析(Cluster Analysis)则是指用数学的方法研究和处理给定对象的分类。它主要是从数据集中寻找数据间的相似性，并以此对数据进行分类。使得不同类别中的数据尽可能相异，而同一类数据之间尽可能相似，从而发现数据其中隐含的、有用的信息。

2.2数据挖掘对聚类算法的要求

聚类分析是数据挖掘中的一项重要功能，而聚类算法是目前聚类挖掘领域研究的核心。聚类算法的质量取决于算法对相似性的判别标准，算法的具体实现以及算法发现隐藏模式的能力。由于大型数据库、数据仓库十分复杂，数据挖掘中的聚类算法必然要面对由此产生的计算要求，具体要求如下：

(1) 可伸缩性：可伸缩性是指算法不仅对小数据集有效，对大数据集也应同样有效。目前许多聚类算法在小于200个数据对象的小数据集合上工作的很好，但是一个大规模的数据库可能包含几百万个对象，在这样的大数据集合样本上进

行聚类可能会导致有偏差的结果，我们需要有高度可伸缩性的聚类算法。可伸缩性算法应该随着数据库大小的变化，其运行时间也应该线性变化。

(2) 处理不同类型属性的能力：算法不仅要能处理数值型的数据，还要有处理其他类型字段的能力，如布尔型，枚举型、序数型，或者这些数据类型的混合。

(3) 发现任意形状的簇：许多聚类算法基于欧氏距离或曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球形簇，但现实数据库中的聚类可以是任意形状，因此，研究能发现任意形状的簇的算法是很重要的。

(4) 输入参数对领域知识的弱依赖性：在聚类分析当中，许多聚类算法都要求用户输入一些参数，例如需要发现的聚类数。聚类结果通常都对用户输入这些参数十分敏感，并且对高维数据，这些参数有时相当难以确定的。这样不仅加重了用户的负担，也使得聚类质量难以保证。

(5) 能够处理异常数据：现实数据库中常常包含有异常数据，例如孤立点、未知数据、数据空缺或包含错误数据。有一些聚类算法可能会对这些数据很敏感，从而导致低质量的分析结果。我们希望聚类算法能够在聚类过程中检测到这些异常数据，然后删除它们或消除它们的负面影响。

(6) 对输入记录的顺序不敏感：有些算法对记录的输入顺序很敏感，对同一个数据集，当以不同的顺序输入时，用同一个算法处理可能得到不同的聚类结果，这是应当避免的。

(7) 满足约束条件：在实际应用当中，聚类可能会在有各种约束的情况下进行。对于聚类算法来说既满足约束条件，又取得好的聚类结果是非常具有挑战性的。在这种受约束的情况下我们希望聚类算法仍有好的表现。

(8) 可解释性和可用性：聚类的结果最终是面向用户的，因此其结果应当是容易解释和理解的，并且是可应用的。这要求聚类算法必须与一定的语义环境及语义解释相关联。领域知识如何影响聚类分析算法的设计是很重要的一个研究方面。

2.3聚类分析中的数据结构和类型

2.3.1聚类分析中的数据结构

在聚类分析中，许多基于内存的聚类算法一般会选择如下两种有代表性的数据结构[31]：

1．数据矩阵

数据矩阵又称为“对象—属性”结构，类似于关系表的形式，它表示具有p 个属性的n 个对象(例如：人可以用年龄、身高、体重、性别、等属性来描述)可以用如下p n ?(n 个对象?p 个变量)的矩阵来表示：

???

??????

?????np n n p p x x x x x x x x x 212222111211 (2-1) 其中，每列代表对象的一个属性，每一行为一个元组，代表一个数据对象。

2．相似度矩阵

相似度矩阵又称为“对象—对象”结构。主要用来存储n 个对象两两之间的相似度，表现形式是n n ?维矩阵：

???

??????????

?1)2,()1,(),2(1)1,2(),1()2,1(1

n d n d n d d n d d (2-2) 其中),(j i d 是对象i 和j 之间相似性的量化表示，通常为非负数，且

),(),(i j d j i d =。对象

i 和j 越相似，则),(j i d 越接近于1；相反，对象i 和j 的差异越大，则),(j i d 就越大。每个对象与自身的相似度最高，其值为1),(=i i d 。

2.3.2 聚类分析中的数据类型

数据挖掘的对象复杂多样，这就要求聚类分析的方法不仅能够处理属性为数值类型的数据，还能够处理其他类型的数据。一般而言，在数据挖掘中，对象属性经常出现的数据类型有:数值型，二值型，符号型、顺序变量型以及混合类型[32]。不同类型的数据有不同的性质，在计算时所采用的处理手段是不同的。

1．数值属性

属性值用实数表示，典型的例子则包括重量、高度和温度等。为了将数据集进行分类，必须定义相异性和相似性的测度来度量同一类别数据的相似性和不同类别数据之间的相异性。如果数据的多个属性采用的测量单位不同，则会对聚类分析产生影响。往往一个较小的测量单位就会使得它所表示的属性取值范围变大，从而对聚类结果产生较大影响。为了避免属性对测量单位的依赖，所以在计算数据的相似性之前先要对数据进行标准化。

标准化就是将一个属性取值范围投射到一个特定的范围之内，以消除数值型属性因测量单位大小不一而造成聚类结果的偏差。对于基于距离计算的聚类挖掘，规格化方法可以帮助消除因属性取值范围不同而影响挖掘结果的公正性。下面介绍三种标准化方法。

(1) 最大最小标准化

最大最小标准化方法是将属性A 的值m 映射到n 且有n ∈

[new_minA,new_maxA]，具体映射计算公式如下：

A new A new A new A A A

m n min _)min _max _(min max min +---= (2-3)

最大最小标准化保留了原来数据中存在的关系。但若将来遇到超过目前属性A 取值范围的数值，将会引起系统出错。

(2) 均值标准化

该方法是根据属性A 的均值与偏差来对A 进行标准化。属性A 的m 值可以通过以下计算公式获得其映射值n 。

A A

m n δ-= (2-4) 其中，A 和A δ分别为属性A 的均值和方差。这种规格化方法常用于属性A

最大值与最小值未知。

(3) 基数变换标准化

该方法是通过移动属性A 值的小数位置来达到标准化目的。

j m

n 10= (2-5)

其中，j 为使()1max

数据标准化处理以后就可以进行由数值属性所描述对象之间的差异(或相似)程度的测量，经常通过计算相应两个对象之间距离来确定，常用的距离有明考夫斯基距离、欧式距离、曼哈顿距离等。

2．二值属性

一个二值变量只有两个取值：0或1，其中0代表所表示的状态不存在，1代表相应的状态存在。二值变量又分为对称二值变量和不对称二值变量，如果0和1所表示的状态重要性相同，则称其为对称的二值属性。

设两个对象i x 和j x ，q 是属性值在两个对象中都为1的属性个数，r 是属性

值在i x 中为1而在j x 中为0的属性个数，s 是属性值在i x 中为0而在j x 中为1的

属性个数，t 是属性值在两个对象中都为0的属性个数。如果认为所有的二值属性的权值均相同，那么就能得到一个2×2条件表，如图示：

表2-1二值属性条件表

Table.2-1 Binary attribute conditions table

度量上面两个变量的差异度可以由简单匹配系数(对称的情况)和Jaccard 系数(非对称的情况)决定。

简单匹配系数的计算公式如下：

t s r q s

r j i d ++++=),( (2-6)

如果一个二值属性取0或1所表示内容的重要性是不一样的，那么二值属性就是非对称的，如果认为取1值比取0值重要，描述对象i 和对象j 之间差异参数就是Jaccard 相关系数，它的具体定义描述如式3－7。

s r q s r j i d +++=

),( (2-7) 3．符号属性

符号属性是二值属性的一个推广，符号属性可以对两个以上的状态进行描述，状态之间是无序的。例如，头发的颜色是一个符号变量，具有少量可能的值{黑色，金色，棕色，白色，灰色，……}。对于符号变量，最常用的计算对象i 与对象j 之间差异的方法就是简单匹配方法，具体公式如下：

p m

p d -= (2-8)

其中，m 表示对象i 和对象j 中取同样状态的符号变量的个数，p 为所有符号属性的个数。

4．序数属性

一个离散序数变量属性与一个符号变量属性相似，不同的是它的各个状态是有意义的序列。序数变量在描述难以用客观方法表示的主观质量评估时是非常有用的。序数变量的数值常常是通过对间隔数值的离散化获得，也就是通过将取值