毕业论文（赵艳丽初稿）

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

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

摘 要

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

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

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

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

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

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

I

基于遗传算法的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

II

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

目 录

第一章 绪论 .................................................................................................................................................... 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

III

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

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

IV

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

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

V

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

VI

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

第一章 绪论

1.1课题研究背景与意义

1.1.1数据挖掘概述

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

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

1．数据挖掘的概念

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

(1) 数据源必须是真实的、大量的、含噪声的； (2) 发现的是用户感兴趣的知识；

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

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

1

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

2．数据挖掘的过程

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

预处数据理预处理转化转换后挖掘后数据的数据数据挖掘模式识别确定业务对象确定业务对象原数据选取目标数据模式知识数据准备图1-1数据挖掘的过程

解释和评估Fig.1-1 The Process of data mining

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

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

(3) 数据挖掘。该阶段首先根据第一步中对业务问题的定义明确挖掘的任务或目的，如分类、聚类、关联规则发现或序列模式发现等，选取合适的数据挖掘算法。选择实现算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求。然后运用选定的挖掘算法，对所得到的经过转换的数据进行挖掘，从数据库中发现有用的知识或模式。在这个阶段除了选择合适的挖掘算法外，其余一切工作都能自动地完成。

(4) 知识的解释和评估。数据挖掘阶段挖掘出来的模式，经过评估，可能存在冗余或无关的模式，这时需要将其剔出，也有可能模式不满足用户要求，这时则需要整个挖掘过程回退到前一阶段，如重新选取数据、采用新的数据变换方法、

2

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

设定新的参数值，甚至换一种算法等。另外，由于数据挖掘最终要面向用户，因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示。

3．数据挖掘的任务[9]

数据挖掘可以解决大量的商业问题。基于这些商业问题的性质，把这些问题分成下面几种数据挖掘任务。

(1) 分类

分类是指基于一个可预测性属性把事例分成多个类别。每个实例包含一组属性，其中有一个可预测性属性——类别(class)属性。分类任务要求找到一个模型，该模型将类别属性定义为输入属性的函数。分类数据挖掘中应用的最多的任务。

(2) 聚类

聚类也称细分，它基于一组属性对事例进行分组。在同一个聚类中的事例或多或少有相同的属性值。聚类是一种无监督的数据挖掘任务，没有一个属性用于指导模型的构建过程，所有的属性平等对待。后面本文将专门讨论数据挖掘中的聚类分析技术。

(3) 关联分析

关联分析又叫购物篮分析，它是当两个或多个数据项的取值之间重复出现且概率很高时，就表示这些数据项之间存在关联，可以建立起这些数据项的关联规则。一般用“支持度”和“置信度”两个阈值来淘汰那些没有用的关联规则。

(4) 时序模式

通过时间序列搜索出重复发生概率较高的模式，强调时间序列的影响。在时序模式中，需要找出在某个最小时间内出现概率一直高于某一最小百分比(阈值)的规则。

(5) 预测

预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据的种类、特征等。

(6) 偏差分析

偏差分析也叫孤立点(outlier)分析，它用来检测与前面观察的行为有重大改变的行为。数据库中的数据常有一些异常记录，从数据库中检测出这些偏差很有意义。偏差分析的基本方法是寻找观察结果与参照之间的差别，找出特殊的事例。最常用于信用卡欺诈行为检测和网络入侵检测。

4．数据挖掘的对象[10]

原则上讲，数据挖掘可以在任何类型的信息存储上进行，这包括关系数据库、数据仓库、事务数据库、WWW、面向对象数据库、对象-关系数据库、时间序列数据库、空间数据库、文本数据库、多媒体数据库等。挖掘的原始数据可以是结

3

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

构化的，如关系数据库、数据仓库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。

5．数据挖掘的应用

数据挖掘从理论研究到产品开发至用了短短数年，目前在国内外已经进入应用阶段。数据挖掘技术的应用十分广泛，在市场营销、保险、通信网络管理、科学研究、产品制造业、金融投资等行业都可以找到它的用武之地[11][12]。

(1) 零售业

零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买习性和趋向，对于零售商制定销售策略是至关重要的。销售分析人员运用关联规则挖掘技术对大量的销售数据进行分析，可以发现顾客购买模式和趋势，改进服务质量，取得更好的顾客保持力和满意程度，提高货品销售比率，设计更好的货品运输与分销策略，减少商业成本。购物篮分析是数据挖掘技术应用在零售业中的一种有效方式，可用于销售搭配、产品目录设计、产品定价和促销等。

(2) 保险业

保险是一项风险业务，保险公司的一个重要工作就是进行风险评估。通过研究证明，可以利用数据挖掘技术来进行风险分析，在保险公司建立的保单及索赔信息数据库的基础上，寻找保单中风险较大的领域，从而得出一些实用的控制风险的规则，以指导保险公司的工作。数据挖掘技术在保险业中的应用，有利于保险公司开展业绩评价、财务预算、市场分析、风险评估和风险预测等，大大提高企业防范和抵抗经营风险的能力和水平，也为管理人员提供科学的决策依据。

(3) 电信业

在电信企业，借助数据挖掘技术，可以帮助企业分析用户使用电信业务的情况，评估用户的行为，优化广告投入，提升企业客户洞察力，发掘客户需求，提升客户的满意度和忠诚度。

(4) 科学研究

在信息量极为庞大的天文、气象、生物技术等领域中，所获得的大量试验和观测数据已经使传统的数据分析工具难于对付，因此迫切要求功能强大的智能化自动分析工具。这种需求推动了KDD技术在科学研究领域的应用发展。

(5) 其他行业 例如在医药、司法、工业等部门也得到了应用。

尽管数据挖掘的应用领域相当广泛，就我国当前的应用来看，尚处于萌芽阶段，企业大规模地运用数据挖掘技术的尚不多。随着IT技术在社会经济生活中的广泛应用，海量数据的产生己成为必然现象，数据挖掘在各个行业的应用研究也必然成为现实。因此，未来数据挖掘应用领域的研究将更加广泛。

4

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

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

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

第二章 聚类分析

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

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

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

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

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

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

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

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

10

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

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

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

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

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

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

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

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

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

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

2.3.1聚类分析中的数据结构

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

1．数据矩阵

11

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

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

?x11??x21 ????xn1?x12x22?xn2????x1p??x2p?? (2-1) ??xnp??其中，每列代表对象的一个属性，每一行为一个元组，代表一个数据对象。 2．相似度矩阵

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

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

i和j越相似，则d(i,j)越接近于1；相反，对象i和j的差

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

异越大，则d(i,j)就越大。每个对象与自身的相似度最高，其值为d(i,i)?1。 2.3.2 聚类分析中的数据类型

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

1．数值属性

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

12

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

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

(1) 最大最小标准化

最大最小标准化方法是将属性A的值m映射到n且有n∈[new_minA,new_maxA]，具体映射计算公式如下：

n?m?minAmaxA?minA(new_maxA?new_minA)?new_minA

(2-3)

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

(2) 均值标准化

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

n?m?A?A (2-4)

其中，A和?A分别为属性A的均值和方差。这种规格化方法常用于属性A最大值与最小值未知。

(3) 基数变换标准化

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

n?m10j (2-5)

其中，j为使max?n??1成立的最小值。

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

2．二值属性

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

设两个对象xi和xj，q是属性值在两个对象中都为1的属性个数，r是属性值在xi中为1而在xj中为0的属性个数，s是属性值在xi中为0而在xj中为1的

13

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

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

表2-1二值属性条件表

Table.2-1 Binary attribute conditions table

i j 1 0 合计 q s q+s r t r+t q+r s+t p 1 0 合计 度量上面两个变量的差异度可以由简单匹配系数(对称的情况)和Jaccard系数(非对称的情况)决定。

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

d(i,j)?r?sq?r?s?t (2-6)

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

d(i,j)?3．符号属性

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

d?p?mpr?sq?r?s (2-7)

(2-8)

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

4．序数属性

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

14

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

范围分为有限个组得到。一个序数变量可以映射到一个等级集合上。如：若一个顺序变量f包含M个状态，那么这些有序的状态就映射为1,2,?,M的等级。

5．混合类型属性

以上讨论了各种数据类型和它们差异度的计算方法，在实际数据库中，数据对象往往是由混合数据类型描述的。在实际聚类分析中，将不同类型的变量组合在同一个差异度矩阵中，并将它们所有有意义的值全部映射到[0,1]区间内。

设一个数据集包含m个不同类型的属性，对象i和j之间的差异度定义为：

m?? d(i,j)?p?1m(p)ijdij(p) (2-9)

(p)ij??p?1其中，如果：xip或xjp数据缺失(对象i或对象j的变量p无测量值)，或

xip?xjp?0(p)且变量p为非对称二值变量，则标记?ij(p)?0；否则?ij(p)?1。

(p)?ij表示变量p对对象i和对象j之间差异程序的贡献，dij可以根据其具体

变量类型进行相应计算。

若变量p为二值变量或符号变量，则：如果xip?xjp，那么dij(p)?0，否则

dij(p)?1。

xip?xjpmaxh若变量p为间隔数值变量，则d量p所有可能的对象。

(p)ij?xhp?minhxhp，这里的h为非空变

若变量p为序数变量，将其转化为数值变量来进行计算处理。

综上所述，即使在对象是由不同类型变量描述时，也能够计算相应每两个对象间的距离。

2.4聚类分析中的相似度度量方法

对象间的相似性是聚类的核心，而对相似性进行度量是用以区别对象的主要基础，传统的相似度度量方法有两类，即距离和相似系数。距离通常用于数值型数据，距离越接近0，相似性越大；相似系数通常用于分类型数据，相似系数越接近1，相似性越大[33]。

15

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

2.4.1距离

距离是聚类分析常用的分类统计量。假设每个对象有m个属性，可以把一个对象视为m维空间的一个点，n个对象就是m维空间的n个点。因此，很自然地想到用点之间的距离来衡量对象之间的相似程度。距离越小，对象间的相似度就越大。用dij表示对象xi和对象xj之间的距离，则距离应该满足一下四个性质：

(1) 非负性，即对所有的i和j，恒有dij?0。当且仅当xi?xj时，dij?0。 (2) 对称性，即对所有的i和j，恒有dij?dji。

(3) 三角不等式，即对所有的i，j，k，恒有dij?dik?dkj。 在聚类分析中，常用的距离公式有以下几个： (1) 明科夫斯基距离

1 dij????xik?xjk?k?1mp?pp>0 (2-10) ? ，?如果取q=1,2,∞时，则分别得到以下三个距离： (2) 曼哈顿距离

m dij??k?1xik?xjk (2-11)

(3) 欧氏距离

1 dij?m???xik?xjk??k?12?2? (2-12) ??(4) 切比雪夫距离

dij?maxxik?xjk (2-13)

1?k?m在以上的几种距离中，最常用的是欧式距离，其特点是对坐标系进行平移和旋转变换之后，欧氏距离保持不变，因此对象仍然保持原来的相似结构。

值得注意的是在采用明科夫斯基距离时，一定要采用相同量纲的变量。如果变量的量纲不同，测量值变异范围相差悬殊时，要先进行数据的标准化处理，然后进行计算距离。另外，明科夫斯基距离没有考虑变量的多重相关性。

16

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

2.4.2相似系数

相似系数体现对象之间的相似程度，相似系数越大，对象的相似性也越大。对于m维空间中的两个对象xi和xj，rij表示对象i和j之间的相似系数，rij则满足以下条件：

rij=1。(1) 绝对值不大于1，即对所有的i和j，恒有rij?1。当且仅当xi?xj时，

(2) 对称性，即对所有的i和j，恒有rij?rji。 常用的相似系数度量方法一般有以下几种形式：

m?x(1) 夹角余弦法：rij?k?1m2k?1ikxjk，用两个向量之间的余弦作为相似系

m2k?1(?xik)(?xjk)数，范围为[-1，1]，当两个向量正交时取值为0，表示完全不相似。

m?(x(2) 相关系数法：rij?k?1mik?xi)(xjk?xj)m，其中xi?jk1mm?x，，

ikk?1?(xk?1ik?xi)2?(xk?1?xj)2xj?1mm?x，计算两个向量之间的相关度，范围为[-1,1]，其中0表示不相关，

jkk?11表示正相关，-1表示负相关。

2.5聚类分析中的聚类准则函数[34]

在样本相似度量的基础上，聚类分析还需要一定的准则函数才能把真正属于同一类的样本聚合到一个类中，而把不同类的样本分离开。如果聚类准则选的好，聚类质量就会高。同时，聚类准则函数还可以用来评价聚类结果的质量，如果聚类质量不满足要求，就要重复执行聚类过程，以便优化聚类结果。

常用的聚类准则函数有如下几种： (1) 误差平方和准则函数Jc

这是一种最常用的聚类准则函数。混合样本集X??x1,x2,?,xn?，在某种相似性度量基础上，它被聚类成C个分离开的类X1,X2,?,XC，每个类分别包括

17

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

n1,n2,?,nc个样本。衡量聚类的质量误差平方和准则函数定义为：

Cnj2 JC???j?1k?1xk(j)?mj (2-14)

式中，mj(j=1,2,3,…,C)是C个聚类中心，取值为每一类中样本的均值，即

mjn?1?j??xj?，j=1,2,…,C。 ???nj?j?1?可以看出，JC是样本和聚类中的函数，在样本集X给定的情况下，JC的值取决于C个聚类中心。JC描述n个样本聚类成C个类型时所产生的总的误差平方和。若JC值越大，说明误差越大，聚类结果越不好。因此，应该寻求使JC最小的聚类结果，即在误差平方和准则下的最优结果。这种聚类通常称为最小方差划分。误差平方和准则函数适用于各类样本比较密集且样本数目悬殊不大的样本分布。当不同类型的样本数目相差较大时，采用误差平方和准则有时可能把样本数目多的类型分开，以便达到总的误差平方和最小。本文采用误差平方和准则函数来衡量聚类结果的好坏。

(2) 加权平均平方距离和准则Jj 加权平均平方距离和准则Jj定义为：

c Jj??j?1*pjsj (2-15)

*式中，sj是类内样本间平均平方距离，即

s?*j2nj(nj?1)??x?xix?xj*x?x*2 (2-16)

因此Jj以先验概率pj为加权的总类内平均平方距离之和，其中先验概率pj可以用各类样本数nj及样本总数n来估计，即

pj?njn,j?1,2,?C (2-17)

当各类样本数目悬殊比较大时，使用加权平均平方距离和准则比使用误差平

18

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

方和准则容易得到正确的聚类结果。

(3) 类间距离和准则Jb

为了描述聚类结果的类间距离分布状态，可以利用类间距离和准则Jb1以及加权的类间距离和准则Jb2，它们的定义分别如下：

c Jb1??(mj?1cj?m)(mj?m) (2-18)

T Jb2??j?1pj(mj?m)(mj?m) (2-19)

T式中，mj为类cj的样本均值向量，m为全部样本的均值向量，而pj为类cj的先验概率。

类间距离和准则函数描述了不同类型之间的分离程度。显然，类间距离和准则函数的值越大，表示聚类结果的各类分离性越好，所以聚类质量就高。

2.6 聚类算法的分类及其典型算法

目前聚类的方法有很多，总的来说主要分为以下几种类型:划分方法、层次方法、密度方法、模型方法、网格方法、模糊聚类。 2.6.1基于划分的方法

对于给定的包含n个数据对象的数据库，通常基于划分的方法[35]要求用户给定构建数据的最终划分数目k，通过采用目标函数最小化策略，将数据分成k个簇。每个簇同时满足以下两个条件：(1)每个簇至少包含一个数据对象；(2)每个数据对象属于且唯一的属于一个簇(注意：但在某些模糊划分技术中第二个要求可以放宽)。给定划分数目k，算法首先创建一个初始划分，通常采用的方法是随机选取k个数据对象作为初始聚类中心点，然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分，使得每一次改进之后的分组方案都比前一次好，判断划分好坏的准则是：在同一个簇中的数据对象尽可能相似，不同的簇中的数据对象尽可能相异。

基于划分的聚类算法是一种基于爬山式的优化搜索算法，此法简单、快速而有效，但是此方亦存在不足之处，如：对初始值敏感；对输入顺序敏感；常陷入局部最优等等。根据对象在划分之间移动的衡量参数和簇的表示方法不同，基于

19

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

划分的方法主要包括有K-means算法，K-medoids算法、CLARANS算法、PAM算法等。第四章将对k-means算法做出详细介绍，这里不在叙述。 2.6.2基于层次的方法

层次的方法[36]按数据分层建立簇，形成一棵以簇为节点的树。根据层次形成方式，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称自底向上的方法，该方法从数据点作为个体簇开始，每一步合并两个最接近的簇，直到所有的簇合并为一个(层次的最上层)，或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，该方法从包含所有点的一个簇开始，每一步分裂一个簇，最终每个对象在单独的一个簇中，或者达到一个终止条件。层次聚类法与划分聚类法的区别在于，它并不试图寻找最优的聚类结果，而是按照一定的相似性判别标准，对最相似的部分进行合并。

层次法简单直接、易于理解和应用。它的缺陷在于，一旦一个步骤完成，它就不能被撤销，因此不能更正错误的决定。为改进层次方法的聚类质量，可以考虑将层次聚类与其他的聚类技术进行集成，形成多阶段聚类。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。 2.6.3基于密度的方法

很多算法中都使用距离来描述数据对象之间的相似性，前面提到的两种聚类方法就是基于这种相似性进行聚类，这样的聚类方法对球形簇的聚类效果较好，但对任意形状的簇聚类结果较差，甚至无法进行有效聚类，因此提出了基于密度的聚类方法[37]。其主要思想是：只要一个区域中的点超过某个阈值，就把它加到与之相近的聚类中去。该类算法的优点是：领域知识独立；可以发现任意形状的类；对初始值、数据输入顺序不敏感；能够有效去除噪声。典型的基于密度的聚类方法包括DBSCAN算法、OPTICS算法、DENCLUE算法和SUBCLUSTER算法。

2.6.4基于网格的方法

基于网格的方法[38]是把数据空间划分为有限数目的单元，形成一个网格结构，所有的聚类操作都以单个的单元为对象在这个网格结构上进行。这种方法的主要优点是处理速度很快，其处理时间与数据对象的数目无关，只与把数据空间分为多少个单元有关。基于网格的聚类方法符合一个好的聚类算法的许多标准：

20

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

能有效地处理大数据集；发现任意形状的簇；成功地处理孤立点；对输入顺序不敏感；不需要指定结果簇数目和领域半径等输入参数；而且能处理高维数据。代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法。 2.6.5基于模型的方法

基于模型的方法[39]为每个簇假定一个模型，然后寻找能够很好满足这一模型的数据集。一个基于模型的算法可能通过构建反映数据点分布的密度函数来定位聚类。基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性。这样的方法经常是基于这样的假设：数据是根据潜在的概率分布生成的。基于模型的方法主要分两类：统计学方法和神经网络方法。 2.6.6模糊聚类

以上介绍的几种聚类算法可以给出确定的聚类结果，即一个数据点必须属于且唯一的属于一个类。我们把这些聚类方法称为“确定性聚类”。然而，在大部分情况下存在着大量界限并不分明的聚类问题，随着模糊集理论[40]的提出，模糊聚类应运而生[41][42]。在模糊聚类中，每个样本不再仅属于某一类而是以一定的隶属度属于每一类。换句话说，通过模糊聚类分析，得到了样本属于各个类别的不确定性程度，即建立起了样本对于类别的不确定性描述，这样就更能准确地反映现实世界。常用的模糊聚类算法是模糊C-平均值算法(Fuzzy C-Means，FCM)[43]，该算法是在传统的k-means基础上引入了模糊理论。

FCM算法的正面特征是，它产生指示任意点属于任意簇的程度的聚类。FCM算法比k-means算法具有更好的可分离性。除此以外，它具有与k-means算法相同的优点和缺点。

2.7聚类分析在数据挖掘中的应用

聚类分析在数据挖掘中的应用主要有三个方面：

(1) 聚类分析可以作为其他算法的预处理步骤，首先用聚类算法生成一些簇，其它算法再在生成的簇上进行处理。譬如作为特征和分类算法的预处理步骤，也可以将聚类结果用于进一步关联分析。

(2) 可作为一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇做进一步分析。可用在市场细分、信息检索、文本挖掘、目标顾客定位、WEB数据分析、客户关系管理(CRM)、医学诊断、生物学等方面。例

21

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

如在CRM系统中，聚类分析可以帮助市场分析人员从客户基本信息库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在市场销售方面，帮助市场人员发现客户中的不同种群，并且概括出每一类消费者的消费模式即习惯，然后用这些知识制定出目标明确的销售方案。

(3) 聚类分析还可以完成孤立点挖掘。许多数据挖掘算法试图使孤立点影响最小化，或者排除他们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立点可能预示着欺诈行为的存在。

2.8本章小结

本章首先简要地介绍了一下数据挖掘的概况，然后详细介绍了聚类分析的有关知识，包括聚类分析的基本概念、数据挖掘对聚类算法的要求、聚类分析的数据结构和类型、相似度度量方法、聚类准则函数、主要算法及其在数据挖掘中的应用等。

22

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

第三章 遗传算法的基本原理

遗传算法(Genetic Algorithms, GA)是模拟自然界生物进化工程过程的随机化搜索算法，它以很强的解决问题能力和广泛的适应性渗透到研究与工程的各个领域，并得到了良好的效果。目前，GA的研究已成为国际学术界跨学科的热门话题之一。遗传算法作为一种高效的全局并行搜索优化算法，已经在优化、人工智能、过程控制和并行处理等领域得到了广泛的应用，在数据挖掘领域的应用也越来越得到重视。

3.1遗传算法的历史与发展

遗传算法的研究历史可以追溯到六十年代，从六十年代到七十年代中期，是遗传算法的萌芽期。遗传算法的基本原理最早由美国科学家J.H.Holland在1962年提出[44]；1967年，J.D.Bagay在他的博士论文中首次使用了遗传算法这个术语；1975年，J.H.Holland在他出版的专著《自然界和人工系统的适应性》中详细地介绍了该算法，为其奠定了数学基础，人们常常把这一事件视为遗传算法正式得到承认的标志。它说明遗传算法已经完成蕴育过程，Holland被视作该算法的创始人。

从七十年代中期到八十年代，遗传算法得到了不断的完善，属于遗传算法的成长期。这一时期相继出现了有关遗传算法的博士论文，分别研究了遗传算法在函数优化，组合优化中的应用，并从数学上探讨了遗传算法的收敛性，对遗传算法的发展起到了很大的推动作用。20多年来，算法不论是实际应用还是建模其范围不断扩大，而算法本身也渐渐成熟，形成了算法的大体框架，其后出现的遗传算法的许多改进研究，大体都遵循了这个框架。

80年代末以来是遗传算法的蓬勃发展期，这不仅表现在理论研究方面，还表现在应用领域方面。随着遗传算法研究和应用的不断深入，一系列以遗传算法为主题的国际会议十分活跃：开始于1985年的国际遗传算法会议ICGA(International Conference on Genetic Alogrithms)每两年举办一次。在欧洲，从1990年开始也每隔一年举办一次类似的会议。这些会议的举办体现了遗传算法正不断地引起学术界的重视，同时这些会议的论文集中反映了遗传算法近年来的最新发展和动向。

随着计算速度的提高和并行计算的发展，遗传算法的速度己经不再是制约其应用的因素，遗传算法已在机器学习、过程控制、图像处理、经济管理等领域取

23

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

得了巨大成功，但如何将各专业知识融入到遗传算法中，目前仍在继续研究。

3.2遗传算法的基本术语[45]

由于遗传算法是自然遗传学和计算机科学相互结合渗透而成的新的计算方法，因此遗传算法中经常使用自然进化中有关的一些基本术语。了解这些用语对理解遗传算法是十分必要的。

1．染色体(chromosome)，又称为个体(individual)。

是由基因(gene)构成的位串，包含了生物的遗传信息。染色体对应的是数据或数组，通常是由一维的串结构数据来表示的。串上各个位置对应基因，而各位置上所取的值对应于基因取值。

2．编码(coding)。把解表示为位串的过程称为编码，编码后的每个位串就表示一个个体，即问题的一个解。

3．种群(population)。由一定数量的个体组成的群体，也就是问题的一些解的集合。种群中个体的数量称为种群规模。

4．适应度(fitness)。评价群体中个体对环境适应能力的指标，就是解的好坏，由评价函数F计算得到。在遗传算法中，F是求解问题的目标函数，也就是适应度函数。

5．遗传算子(genetic operator)。产生新个体的操作，常用的遗传算子有选择、交叉和变异等。

(1) 选择(selection)：以一定概率从种群中选择若干个体的操作。一般而言，该操作是基于适应度进行的，适应度越高的个体，产生后代的概率就越高。

(2) 交叉(crossover)：把两个串的部分基因进行交换，产生两个新串作为下一代的个体。交叉概率(Pc)决定两个个体交叉操作的可能性。

(3) 变异(mutation)：随机地改变染色体的部分基因，例如把0变1，或把1变0，产生新的染色体。

3.3遗传算法的特点[46]

遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，采用了许多独特的方法和技术，归纳起来，主要有以下特点:

(1) 遗传算法的处理对象是那些对参数集进行编码得到的个体，而不是参数本身。

(2) 具有并行性。遗传算法采用的是同时处理群体中多个个体的方法，及同

24

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

时对搜索空间中的多个解进行评估。这一特点使遗传算法具有较好的全局搜索性能，从而减少了陷入局部最优解的可能。

(3) 仅用适应度函数来指导搜索。以往很多的搜索方法都需要辅助信息才能正常工作，如梯度法需要有关导数的信息才能爬上当前的峰值点，这就要求目标函数可导。而遗传算法则不需要类似的辅助信息，为了有效的搜索越来越好的编码结构，它仅需要与该编码串有关的适应度函数即可。

(4) 内在启发式随机搜索特性。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。概率仅作为一种工具来引导其搜索过程朝着搜索空间的最优化的解区域移动。

(5) 遗传算法易于介入已有模型，具有可扩展性，易于同别的技术混合。本文正是遗传算法应用于计算机科学和管理科学的交叉学科——数据挖掘技术的一个典型例子。

3.4遗传算法的基本要素

遗传算法包含了如下5个基本要素：问题编码，初始群体的设定，适应度函数的设计，遗传操作设计，控制参数的设定。这5个要素构成了遗传算法的核心内容。

1．问题编码

编码机制是遗传算法的基础。通常遗传算法不直接处理问题空间的数据，而是将各种实际问题变换为与问题无关的串个体。目前遗传算法中最常用的是二进制编码，其次还有实数编码、字符编码、整数编码等多种编码方法。

2．初始群体的生成

遗传算法处理流程中，编码设计之后的任务是初始群体的设定，并以此为起点一代的进化直到按照某种进化终止准则终止，最常用的初始方法是无指导的随机初始化。

3．适应度函数(Fitness Function)的确定

在遗传算法中，按与个体适应度成正比的概率来决定当前群体中的每个个体遗传到下一代群体中的机会多少，一般希望适应值越大越好，且要求适应值非负。因此适应值函数的选取至关重要，它直接影响到算法的收敛速度及最终能否找到最优解。

适应度函数是根据目标函数确定的，针对不同种类的问题，目标函数有正有负，因此必须确定由目标函数值到适应度函数之间的映射规则，以适应上述的要求。

25

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

4．遗传操作

遗传操作主要包括：选择、交叉、变异三个算子。关于每个算子的作用前面己提及了，此处不在赘述。这里主要说一下每种算子常用的方法。

(1) 选择算子

在适应度计算之后是实际的选择，选择的目的是为了从当前群体中选出优良的个体，使它们作为父代进行下一代繁殖。采用基于适应度的选择原则，适应度越强被选中概率越大，体现优胜劣汰进化机制。可以挑选以下的算法：

①赌轮选择法。该方法中个体被选中的概率与其适应度大小成正比。 ②最优保存策略。群体中适应度最高的个体不进行交叉变异，用它替换下一代种群中适应度最低的个体。

③锦标赛选择法。随机从种群中选取一定数目的个体，然后将适应度最高的个体遗传到下一代群体中。这个过程重复进行完成个体的选择。

④排序选择法。根据适应度对群体中个体排序，然后把事先设定的概率表分配给个体，作为各自的选择概率。这样，选择概率和适应度无关而仅与序号有关。

选择算子确定的好坏，直接影响遗传算法的计算结果。如果选择算子确定不当，会导致进化停滞不前或出现早熟问题。选择策略与编码方式无关。

(2)交叉算子

交叉算子是遗传算法中最主要的遗传操作，也是遗传算法区别于其他进化运算的重要特征。通过交叉操作可以产生新个体。遗传算法的有效性主要来自选择和交叉操作，尤其是交叉操作，它决定遗传算法的收敛性和全局搜索能力。

交叉算子的设计与实现与所研究的问题密切相关，一般要求它既不要破坏原个体的优良性，又能够产生出一些较好的新个体，而且，还要和编码设计一同考虑。目前适合于二进制编码的个体和浮点数编码的个体的变异算法主要有：单点交叉、两点交叉与多点交叉、均匀交叉、算术交叉。

(3) 变异算子

选择和交叉算子基本上完成了遗传算法的大部分搜索功能，变异操作只是对产生的新个体起辅助作用，但是它必不可少，因为变异操作决定了遗传算法的局部搜索能力。变异算子与交叉算子相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而增加遗传算法找到接近最优解的能力。

目前适合于二进制编码的个体和浮点数编码的个体的变异算法主要有：基本位变异、均匀变异、非均匀变异、边界变异、高斯近似变异等等。

5．控制参数

控制参数主要有群体规模、迭代次数、交叉概率、变异概率等，对此基本的遗传算法都需要提前设定：

26

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

N：群体大小，即群体中所含个体的数量，如果群体规模大，可提供大量模式，使遗传算法进行启发式搜索，防止早熟发生，但会降低效率；如果群体规模小，可提高速度，但却会降低效率。一般取为20～100。

T：遗传运算的终止进化代数，一般取为100～500。

Pc：交叉概率，它影响着交叉算子的使用频率，交叉率越高，可以越快地收敛到全局最优解，因此一般选择较大的交叉率。但如果交叉率太高，也可能导致过早收敛，而交叉率太低，可能导致搜索停滞不前，一般取为0.4～0.99。

Pm：变异概率，变异率控制着变异算子的使用频率，它的大小将影响群体的多样性及成熟前的收敛性能。变异率的选取一般受种群大小、染色体长度等因素影响，通常选取很小的值。但变异率太低可能使某基因值过早丢失、信息无法恢复；变异率太高，遗传算法可能会变成了随机搜索。一般取为0.0001～0.1。

这四个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在实际应用中，常常需要经过多次实验后才确定参数或其范围。

3.5遗传算法的描述及流程

3.5.1 遗传算法的描述[47]

现在，我们引用上面的术语来描述遗传算法的基本思想。遗传算法首先将问题的每个可能的解按某种形式编码成个体，然后随机选取N个个体构成初始种群，再根据预定的适应度函数计算每个个体的适应值。选择适应值高的染色体作为父代，在通过交叉、变异，来产生一群新的更适应环境的个体，形成新的种群。这样一代一代不断繁殖、进化，最后收敛到一个个体上，该个体很有可能代表着问题的最优或次优解。

基本遗传算法的伪代码描述如下： Procedure SGA

{ Initialize P(0); /*初始化群体*/

t=0; /*t为进化代数计数器*/ While (t

Evaluate fitness of P(t); /*计算第t代群体中个体适应度值*/ End for

For i=1 to M do

27

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

Select operation to P(t); /*进行选择操作 */ End for

For i=1 to (M/2) do

Crossover operation to P(t); /*进行交叉操作*/ End for

For i=1 to M do

Mutation operation to P(t); /*进行变异操作*/ End for

For i=1 to M do

P(t+1)=P(t); /*生成新的群体*/ End for t=t+1; end while

}

3.5.2遗传算法的执行过程

根据上面遗传算法的思想，遗传算法的基本处理过程可描述如下： 输入参数：种群规模M、交叉概率Pc、变异概率Pm 。

(1) 编码：遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，即从表现型映射到基因型X；

(2) 初始化。随机选择N个初始点构成初始种群P(0)，设置进化代数计数器t=0，设置最大进化代数T；

(3) 适应度评价。根据确定的适应度函数，计算群体P(t)中每个个体的适应值； (4) 选择。将选择算子作用于群体； (5) 交叉。将选择算子作用于群体； (6) 变异。将变异算子作用于群体；

种群经过选择、交叉、变异操作之后得到下一代种群P(t+1)。

(7) 终止条件判断。若t?T，则t?t?1，并转向(3)；若t?T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。

具体的流程图如图3-1所示。

28

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

实际问题编码成位串种群p(t)计算适应度值输出适应度最优个体是是否满足终止条件否选择操作交叉操作变异操作遗传算子t=t+1产生新一代种群p(t+1)图3-1遗传算法的流程图

Fig.3-1 The flow chart of genetic algorithms

3.6遗传算法的应用

遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题具体的领域，对问题的种类有很强的鲁棒性，所以广泛应用与许多学科。下面列出遗传算法一些主要的应用领域。

(1) 函数优化

函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。可以用各种各样的函数来验证遗传算法的性能。对一些非线性、多模型、多目标的函数优化问题，使用遗传算法可得到较好的结果。

(2) 组合优化

随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的

29

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

计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类问题，人们已意识到应把主要精力放到寻求其满意解上，而遗传算法就是寻求这种满意解的最佳工具之一。时间证明，遗传算法对于组合优化中的NP完全问题非常有效。

(3) 生产调度问题

采用遗传算法能够解决复杂的生产调度问题。在单间生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。

(4) 自动控制

在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步应用，并显示出了良好效果。例如，基于遗传算法的模糊控制器优化设计，用遗传算法进行航空控制系统的优化，使用遗传算法设计空间教会控制器等。

(5) 机器学习

基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属函数等。基于遗传算法的机器学习可用于调整人工神经网络的连接权，也可用于神经网络结构的优化设计。分类器系统在多机器人路径规划系统中取得了成功的应用。

(6) 图像处理

图像处理是计算机视觉中的一个重要领域，在图像处理中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理的优化计算方面找到了用武之地。

(7) 机器人学

机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要领域。例如，遗传算法已经在移动机器人路径规划、机关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。

3.7本章小结

本章详细介绍了遗传算法的有关知识，包括遗传的历史与发展、基本术语、遗传算法的基本要素、算法的特点、算法思想及其执行过程、应用等。

30

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

第四章 一种改进的遗传k-means聚类算法

k-means算法是一种重要的聚类算法，算法简单、收敛速度快，被广泛地应用于各个领域。虽然k-means算法具有较强的局部搜索能力，但因对初始聚类中心敏感，容易陷入局部最优，从而影响聚类结果。遗传算法是一种高效的全局搜索方法，但其局部搜索能力较差。若将k-means算法与遗传算法相结合，互相取长补短，既通过遗传算法保证获取全局最优解，又利用k-means算法兼顾局部寻优能力，提高收敛速度，从而达到理想的聚类效果。基于这种思想，本文在简单遗传算法的基础上进行了一些改进，提出一种改进型遗传k-means聚类方法(Improved Genetic k-means Algorithm，IGKA)。

4.1 k-means算法的思想与流程

k-means算法是由J.B.MacQueen[48]于1967年提出的，目前是用于科学和工业应用的诸多算法中的一种极有影响力的技术。k-means算法属于聚类分析中的划分算法，它是一种己知聚类类别数的算法。由于本文重点研究基于遗传的k-means聚类方法，因此必须详细掌握k-means算法的基本原理。 4.1.1 k-means算法思想[49]

对于给定的包含n个数据对象的数据集，k-means算法首先要求用户指定最终划分类别数目为k，然后随机选取k个点作为聚类中心，计算剩余数据对象到各聚类中心的距离，利用距离最近原则，把数据对象归到离它最近的那个聚类中心所在的类中去，聚类结果由k个聚类中心来表达，基于给定的聚类目标函数(或者说是聚类效果判别准则)，算法采用迭代更新的方法，每一次迭代过程都是朝目标函数值减小的方向进行。

k-means算法以相邻两次的聚类中心没有任何变化，数据对象调整结束，聚类准则函数J收敛作为终止准则。该算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确，若不正确，就要调整。在全部数据调整完后，再修改聚类中心，进入下一次迭代。如果在一次迭代算法中，所有的数据对象被正确分类，则不会有调整，聚类中心也不会有任何变化，这标志着J己经收敛，至此算法结束。

31

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

k-means算法的最终聚类结果是使目标函数值取得极小值，使得类内对象的相似性最大，类间对象的相似性最小。因此k-means算法通常采用欧几里德距离作为衡量相似性的指标，则评价划分质量的目标函数J的可定义为：

knij2 J???wi?1j?1dij

(4-1)

其中，k为分类数，n为样本点总数，dij?xj?zi为欧式距离，表示原始的

样本点xj到类Ci的中心zi的距离，zi是类Ci中所有数据对象的平均值，wij表示数据对象隶属于哪个类。该目标函数又称为误差平方和准则函数。

wij???1?0若第j个对象属于第否则Ci个类 (4-2)

聚类结果用隶属矩阵W?[wij]表示。该式保证一个类中至少有一个对象且一个对象仅属于一个类。 k-means算法伪代码描述如下：

//输入 数据库中的n个样本{x1,x2,?,xn}，要划分的类别数k； //输出 使目标函数最小化的k个类； 初始化k个聚类中心； Repeat

For(对每一个样本xi，i=1,2,?,n) 计算xi与每个聚类中心之间的距离； 将xi分配给距离最近的类Cj； For(对划分好的类别Cj，j=1,2,?,k) 计算每个类中所有样本的平均值；

计算目标函数J；

用当前Cj中所有样本的平均值替代上一次的聚类中心； Until J不再明显变化或者聚类中心不再改变。 4.1.2 k-means算法流程

k-means算法的具体过程描述如下：

(1) 给定样本数据集?x1,x2,x3,?xn?、类别数k，并从中随机选择k个点

c1,c2,c3,?ck作为k个聚类类别的中心点。

32

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

(2) 计算每个数据对象与聚类中心的距离D(xi,cj)，i=1，2，3，?，n，j=1，2，3，?k，如果满足

D(xi,ck)?min{D(xi,cj)，i?1,2,3,?n;j?1,2,3,?k} (4-3)

则将xi划分到类Ck中。

***(3) 根据划分后各集合中的点计算新的聚类中心c1*,c2计算公式为： ,c3,?,ck，

c*j?1nj?x j=1,2,3,?k (4-4)

mxm?Cj其中nj为类Cj中点的个数。

(4) 判断：如果cj?c*j，则算法结束当前中心点为最终的聚类划分结果；否则令cj??c*j，返回(2)继续执行。

为防止步骤(4)的终止条件不能满足而出现的无限循环，通常在算法执行时给出一个固定的最大迭代次数。

4.2 k-means算法的特点

k-means算法是解决聚类问题的一种经典算法。它最大的特点是采用两阶段反复循环结构，算法结束的条件是不再有数据元素被重新分配；两个阶段分别是：(1) 指定聚类。即指定数据xi到某一聚类，使得它与这个聚类中心的距离比它到其他聚类中心的距离要近。(2)修改聚类中心。

该算法的主要优点是算法简洁、计算速度快、资源消耗小。如果结果簇是密集的，簇与簇之间明显分离时，它的聚类效果最好，而且对于处理大数据集，这个算法是相对可伸缩和高效的。

其缺点主要包括以下四方面：

(1) 对初始聚类中心和样本的输入顺序敏感，不同的初始聚类中心或是样本的输入顺序不同产生的聚类结果差别很大；

(2) 该算法采用一个类中所有对象的平均值作为中心，比较容易发现球状簇，而不容易发现其他形状的簇，而且它对于“噪声”和孤立点数据是敏感的，少量的孤立点数据会对计算平均值产生很大的影响，这会使平均值得到很大的偏离。

(3) 在k-means算法中常采用误差平方和准则函数作为聚类准则，一旦选择

33

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

了准则函数，聚类问题就成为一个定义明确的优化问题，即使得准则函数取极值。所以在运用误差平方和准则函数测度聚类效果时，最佳聚类结果对应于目标函数的极值点，由于目标函数存在着许多局部极小点，而算法的每一步都是沿着目标函数减小的方向进行，若初始化落在了一个局部极小点附近，就会造成算法在局部极小处收敛。

(4) 从k-means算法流程可以看出，该算法在运行过程中需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心。因此，当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。

针对以上的局限性，所以考虑对k-means算法进行改进或将它与其他全局搜索算法结合起来用于聚类分析当中。

4.3基于k-means的改进聚类算法

由于k-means算法在实际应用中易于实现而且其复杂性相对较小，所以目前对k-means算法的研究已非常深入，其中已作出的主要研究成果有：

(1) 将模拟退火运算用于聚类之中[50]，采用模拟退火算法对k-means算法的分类矩阵进行退火优化运算，易于找到全局最优解。

(2) 基于遗传算法的k-means聚类方法，用遗传算法指导聚类问题[51][52][53]。 (3) 用Tabu搜索算法求解k-means聚类问题[54]，它通过对划分矩阵的随机搜索以获得全局最优解。

(4) 用k-means算子代替遗传算法中的交叉算子[55]，设计出一种混合遗传算法，并根据Guter引入的有限状态齐次马尔科夫链方法证明了该方法以概率1收敛到全局最优点。

(5) 将普利姆算法思想引入到k-means初始中心选择的过程中[56]，降低k-means算法对初始中心的敏感。

由于人工模拟，遗传算法,免疫算法，进化策略等随机搜索算法可以避免收敛到局部最优解，并能找到一个全局最优解，于是我们考虑用这些算法来弥补传统k-means算法的缺点。本文重点研究遗传算法结合k-means算法的方法，下面的章节将对这种思想给予详细的描述。

4.4聚类分析中的遗传算法

遗传算法作为一种有效的全局并行优化搜索工具早已被众多应用领域所接

34

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

受，它在数据挖掘方面的应用也得到了极大的重视。遗传算法应用于决策树、关联规则、聚类分析等方面的文献不断涌现，遗传算法已是数据挖掘领域的一个重要课题。遗传算法效仿了生物的进化过程，通过种群一代又一代地繁殖和交换，它能搜索到多个局部极值，从而增加了找到全局最优解的可能行。将遗传算法引入到聚类中，可以提高聚类算法的找到全局最优的可能性。

用遗传算法求解聚类问题，首先要解决三个问题： (1) 如何将聚类问题的解编码到个体中；

(2) 如何构造适应度函数来度量每个个体对聚类问题的适应程度，即如果某个体的编码代表良好的聚类结果，则其适应度就高；反之，其适应度就低。适应度函数类似于有机体进化过程中环境的作用，适应度高的个体在一代又一代的繁殖过程中，产生出较多的后代，而适应度低的个体则逐渐消亡；

(3) 如何选择各个遗传操作以及如何确定各控制参数的取值。

解决了这些问题后就可以利用遗传算法来求解聚类问题，这也显示了遗传算法与求解问题无关的强大通用性。

4.5改进的遗传k-means算法(IGKA)

为了能够让遗传算法和k-means算法的结合更好地弥补它们各自的缺陷，同时提高算法的收敛速度并改善聚类结果，本文算法主要从四个方面对传统遗传算法聚类做了改进[57]：

首先，采用了把聚类中心作为染色体的浮点数编码方式，这样既使大数据集的编码过程得到了简化，又减少了整个算法的运算量；

其次，为了保证进化过程中每一代当前最优个体不被遗传操作破坏，采用了轮盘赌和最优保存策略相结合的混合遗传算子；

再次，在交叉操作中，为了减少无意义个体的产生，先对交叉个体进行了基于最短距离的基因匹配，然后再运用算术交叉来增强遗传算法的局部搜索能力；

最后，为了提高遗传聚类的收敛速度，在每一代遗传操作结束之后对要进入下一代的群体进行k-means优化操作。 4.5.1 IGKA算法流程

通过上面的描述可知，与基本遗传算法的总体运行过程相比，IGKA算法也是从随机产生的初始群体开始全局最优解的搜索过程，只不过它在进行遗传操作后，再对生成的种群中的每个个体进行一步k-means优化操作，然后将优化后的

35

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

结果作为下一代的种群。这个过程反复迭代进行，直到达到最大代数或者结果符合要求为止。

改进的遗传k-means算法流程描述如下：

(1) 参数设置：样本数N，聚类数K，种群大小Psize，最大迭代次数T，交叉概率Pc，变异概率Pm。

(2) 种群初始化：从样本中随机选取K个点作为聚类中心并进行编码，重复Psize次，产生初始种群。

(3) 对种群中的个体进行适应度计算；

(4) 根据计算处的适应度值，对种群进行选择操作。 (5) 对选出的个体进行交叉操作。

(6) 对交叉后的个体进行变异操作，产生新的种群。

(7) 对产生的新种群中的每个个体执行k-means操作，将其优化为以该个体为初始值的k均值问题的局部最优解。

(8) 产生出新一代的种群。

(9) 判断结束条件，当条件满足时结束操作，输出结果；否则，转向第(3)步。 改进型遗传k-means的伪代码描述为： Procedure IGKA

{ Initialize /*初始化*/ 聚类样本集X，聚类数K

初始种群大小Psize，交叉概率Pc 变异概率Pm，最大迭代次数Tmax；

t=0； /*t为进化代数计数器*/ 初始化种群P(0)； While (t

计算第t代种群中各个体的适应度； End for

For i=1 to Psize do

对P(t)代种群进行选择、交叉、变异操作；

对遗传操作后的种群进行k-means优化，产生新的种群P(t+1); End for

End while }

输出末代的最优个体。

36

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

改进型遗传k-means算法的流程图如下：

输入参数,数据集将聚类中心编码成位串生成初始种群P(t)对种群个体进行适应度计算选择操作交叉操作t=t+1变异操作k-means优化操作产生新一代种群P（t+1)是否满足终止条件是输出最佳聚类中心否

图4-1改进型遗传k-means算法的流程图

Fig.4-1 The flow chart of Improved genetic k-means algorithm

4.5.2目标函数

改进型遗传k-means聚类算法(IGKA)目标与k-means聚类算法是一致的，即将包含n个对象的集合划分为k个类，每个对象都是d维向量，最终使目标函数最小化。因此IGKA算法的目标函数采用k-means算法的聚类目标函数式(4-1)，

37

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

又可表示为：

k2 J???i?1xj?Cixj?zi (4-6)

4.5.3编码方法

按照遗传算法的程序流程，用遗传算法求解问题，首先要解决的问题是如何确定编码和解码运算，编码形式决定了交叉算法和变异算子的操作方式，对于算法的性能如搜索能力和计算效率等影响很大。

常用的编码方案有浮点数编码和二进制编码。浮点数编码方法又叫真值编码方法，它是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数，具有适合于大空间搜索、局部搜索能力强、不已陷入局部极值、收敛速度快的特点。由于聚类样本具有多维性、数据量大的特点，如果采用传统的二进制编码染色体的长度会随着维数的增加或精度的提高而显著增加，从而使得搜索空间急剧增大，大大降低了计算效率。基于上面分析，这里采用浮点数编码。

在遗传聚类问题中，可采用的染色体编码方式有两种：一是按照数据所属的聚类划分来生成染色体的整数编码方式；一是把聚类中心(聚类原型矩阵)作为染色体的浮点数编码。聚类问题的解是各聚类中心，因此本文采用基于聚类中心的浮点数编码。

所谓的将聚类中心作为染色体的浮点数编码，就是把一条染色体看成由K个聚类中心组成的一个串。具体编码方式如下：对于D维样本数据的K类聚类分析，基于聚类中心的染色体结构为：

S??x11,x12,?,x1d,x21,x22,?,x2d,?,xk1,xk2,?,xkd?

即一条染色体是一个长度为k?d的浮点基因串。这种编码方式意义明确、直观，避免了二进制编码在运算过程中反复进行译码、解码以及长度受限等问题。 4.5.4 种群初始化

确定了编码方式之后，接下来要进行种群初始化。初始化的过程是随机产生一个初始种群的过程。首先从样本空间中选K个个体，K值由用户自己来指定，每个个体表示一个聚类中心，根据我们所采用的编码方式把这组个体(聚类中心)编码成一条染色体。然后重复进行Psize次染色体初始化，Psize为种群大小。

38

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

4.5.5适应度函数的设计

适应度函数是用来评价个体的适应度，区别群体中个体优劣的标准。由于聚类问题实际上是找到一种划分，也就是要使待聚类数据集的目标函数J达到最小化。遗传算法在处理过程中对每个染色体，采用与k-means算法相同的方式进行类别划分和重新计算各聚类中心，k-means算法是根据式(4-1)每个聚类中的点与相应聚类中心的距离作为判别聚类划分质量好坏的准则函数J，J越小表示聚类划分的质量越好。

遗传算法的目的是搜索使目标函数J值最小的聚类中心，因此可借助目标函数来构造适应度函数如下式：

f?4.5.6选择操作

在生物的遗传和自然进化的过程中，对生存环境适应度较高的物种将有更多的机会遗传到下一代；而适应度较低的物种遗传到下一代的机会就相对较少。遗传算法中的选择操作体现了这一“适者生存”的原则：适应度越高的个体，参与后代繁殖的概率越高。遗传算法中的选择操作就是用来确定如何从父代群体中按照某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。选择操作是建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。

为了保证适应度最好的染色体保留到下一代群体而不被遗传操作破坏掉，根据目前已有的选择方法，本文采用了轮盘赌和最优策略保存法相结合的混合选择算子。该选择算子具体操作如下：

(1) 首先在计算完当前种群的适应度后，记录下其中适应度最大的个体； (2) 再根据各个体的适应度值f(Si)，i?1,2,?,Psize计算各个体的选择概率： Pi?f(Si)Psize11?J (4-7)

(4-8)

?j?1Psizef(Sj)式中，Psize为种群大小,

?j?1f(Sj)为所有个体适应度的总和。

(3) 根据计算出的选择概率，使用轮盘赌法选出个体；

39

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

(4) 被选出的个体参加交叉、变异操作产生新的群体；

(5) 计算出新群体中的各条染色体的适应度值，用上一代中所记录的最优个体替换掉新种群中的最差个体，这样产生了下一代群体。

这种遗传操作既不断提高了群体的平均适应度值，又保证了最优个体不被破坏，使得迭代过程向最优方向发展。 4.5.7交叉操作

交叉操作是把两个父个体的部分结构加以替换重组而产生新个体的操作，也称为基因重组。交叉的目的是为了能够在下一代产生新的个体，因此交叉操作是遗传算法的关键部分，交叉算子的还坏，在很大程度上决定了算法性能的好坏。

由于染色体以聚类中心矩阵为基因，造成了基因串的无序性，两条染色体的等位基因之间的信息不一定相关，如果采用传统的交叉算子进行交叉，致使染色体在进行交叉时，不能很好的将基因配对起来，使生成的下一代个体的适应值普遍较差，影响了算法的效率。为了改善这种情况，又因为本文所使用的是浮点数编码方式，本文采用了一种以算术交叉为基础的混合交叉算子，即基于最短距离基因匹配的算术交叉算子[58]。

算术交叉是指由两个个体的线性组合而产生出两个新的个体。假设在两个个体X1和X2之间进行算术交叉，则交叉后产生的新个体为：

???X1??X2?(1??)X1 ?? (4-9)

??X2??X1?(1??)X2其中，?为一个参数，当?为常数时，则交叉运算为均匀交叉，否则，为非均匀交叉。

假设待交叉的两条染色体为S1?x1(1)x2(1)?xk(1)和S2?x1(2)x2(2)?xk(2)(其中

xi(i?1,2?k)为一个聚类中心)，则该混合交叉算子具体操作如下：

(1) 首先比较染色体S1?x1(1)x2(1)?xk(1)的第一个基因x1(1)与S2?x1(2)x2(2)?xk(2)上的每个基因的距离；

(2) 将S2上与x1(1)距离最近的基因xi(2)选出，并放在一条与S2等长的空染色

?上； 体S2(3) 按照上面方法依次比较S1上其他基因与S2上剩余基因的距离，并把每次

40

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

?上，生成了一条与S1相配对的染色体选出的基因按顺序放在S2??x1S2(2)?x2(2)??xk(2)?

?进行算术交叉得到下(4) 根据交叉概率随机选取一个交叉位置j，对S1和S2一代个体S1*和S2*。

最近邻基因匹配的算术算子能够尽量保证产生有意义的新个体，以提高遗传算法的收敛速度。 4.5.8变异操作

在生物的自然进化的过程中，其细胞分裂的过程可能会出现某些差错，导致变异情况的发生。变异操作就是模仿这种情况产生的。所谓变异操作，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位来替换，从而形成一个新的个体。变异的目的有二：一是增强算法的局部搜索能力；二是增加种群的多样性，改善算法的性能，避免早熟收敛。变异操作既可以产生种群中没有的新基因又可以恢复迭代过程中被破坏的基因。

常用的变异算子有基本位变异、均匀变异、边界变异、非均匀变异和高斯近似变异。均匀变异是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码操作中各个基因座上的原有基因值。而对于浮点数编码的个体，若某一变异点处的基因的取值范围为[Umin,Umax]，变异操作就是用该范围内的一个随机数去替换原基因值。针对本文所使用的是浮点数编码方式，这里采用均匀变异算子来完成变异操作。

假设一条染色体为S?x1x2?xi?xk，则均匀变异的具体操作过程如下： (1) 依次指定个体编码串中的每个基因座为变异点，并确定每个基因点的取值范围[Umin,Umax]；

(2) 对每一个变异点，以变异概率Pm从对应基因的取值范围内取一个随机数来代替原有值。其中变异点的新基因值为：

xi?Umin?r(Umax?Umin) (4-10) 式中，r为[0,1]范围内符合均匀概率分布的一个随机数。

? 41

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

4.5.9 k-means优化操作(KMO)

由于k-means是一种局部搜索能力强的算法，本算法在每一代执行完遗传操作后引入了k-means算法中的一个操作步骤k-means操作，对新生种群中的每个个体进行k-means优化，优化后的群体作为下一代种群进入演化。这样不仅可以提高混合算法的局部搜索能力，同时又有利于提高其收敛速度。具体的优化操作如下：

(1) 根据遗传操作产生的新种群中每条染色体的聚类中心编码值，按照等式(4-3)对样本进行划分，计算出各自的分类矩阵U；

(2) 根据分类矩阵U，按照式(4-4)计算新的聚类中心并进行编码；

(3) 对新的聚类中心重新计算适应度值，找出当前种群中的最差个体，用选择操作所记录的上一代的最优个体替换掉它。

经k-means优化操作后产生新一代种群开始下一轮遗传操作。 4.5.10算法终止条件

算法终止条件如下：

(1) 算法迭代次数超过设定的最大迭代次数T；

(2) 运行过程中得到相同最优个体的适应度值次数连续出现超过某一阈值。 只要满足以上两个条件中的任何一个条件则算法结束。在每次进行选择、交叉、变异、优化操作之后，记录当前子代中适应度最高的个体，算法运行结束后，适应度最高的个体为聚类问题的最优解。

4.6本章小结

本章首先对k-means算法思想进行了详细的描述，分析了k-means算法的优点和缺点。然后，针对算法的特点进行了讨论，并给出了一些现有的改进方法。最后，将k-means算法和遗传算法相结合并加以改进，提出了改进型遗传k-means算法，并给出了改进算法策略以及算法流程。

42

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

第五章 实验结果与比较分析

5.1实验平台

为了检测本文提出的改进型遗传k-means聚类算法的有效性，我们在一定的环境下对算法进行了仿真实验。实验硬件环境是Intel(R) Pentium(R) D CPU 2.8G，512M内存，160G硬盘；软件环境是Windows XP操作系统，Matlab7.0。

5. 2 实验结果和分析

下面通过三组实验对k-means算法、改进的遗传k-means算法的算法性能进行测试和比较。每组实验都给出了最终的聚类结果图，聚类正确率，目标函数最小值。 5.2.1实验一

在本实验中，用给定的一组包含两类的数据集作为测试样本。该数据集共包含20个数据点，具体数据如下表所示。对于该数据集，聚类数k的取值为2。

表5-1测试数据1 Table.5-1 Test data1

数据标号 1 2 3 4 5 6 7 8 9 10 x 1.0 1.5 1.5 2.0 1.5 2.0 1.0 2.0 1.0 8.0 y 2.0 0.5 1.0 1.5 2.0 0.5 1.0 2.5 2.5 7.0 数据标号 11 12 13 14 15 16 17 18 19 20 x 7.0 8.0 9.0 9.0 7.0 8.0 9.5 9.0 9.5 8.0 y 8.0 8.0 8.0 6.0 7.0 9.0 7.0 7.0 8.0 6.0 本次实验中，改进算法的有关参数设置如下：初始种群Psize=20，交叉概率

43

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

Pc=0.9，变异概率Pm=0.01，最大迭代次数为T=100，聚类个数K=2。k-means算法的迭代次数T=100。图5-1为原始数据集1，图5-2为k-means算法聚类的结果，图5-3为IGKA算法的聚类结果。

图5-1 原始数据分布图 Fig.5-1 Initial data scattergram

图5-2 k-means算法聚类结果

Fig.5-2 The clustering result of k-means methods

44

本文来源：https://www.bwwdw.com/article/3m2r.html