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