（应用数学专业论文）基于遗传算法的数据挖掘方法研究.pdf

论文题目: 基于遗传算法的数据挖掘方法研究 专 业: 应用数学 硕 士 生: 安 娜 （签名） 指导教师: 丁正生 （签名） 摘 要 随着生产、生活节奏的加快和信息技术的进步，数据信息量以指数形式增长。数据 挖掘技术具有强大的数据分析处理能力，能为决策者提供重要的、极有价值的信息或知 识， 从而产生不可估量的效益。 因此数据挖掘方法的研究具有很重要的理论和现实意义。 聚类分析是数据挖掘的主要任务之一，k 均值算法是最常用的聚类方法。k 均值 算法的局部搜索能力强、收敛速度快，且聚类结果不受样本数据输入顺序的影响。但 该算法对初始聚类中心的选取非常敏感，极易陷入局部极小值。遗传算法具有强大的全 局寻优能力，运算过程不依赖于梯度信息或其它辅助知识，只需确定目标函数和适 应度函数，被广泛用于解决各类优化问题。因此，将遗传算法与 k 均值算法相结合， 既能发挥遗传算法强大的全局寻优能力，又能兼顾 k 均值算法较强的局部搜索特点。 如何将遗传算法与 k 均值算法更好的结合，优势互补，提高聚类算法效率，是本文 研究的主要内容。针对聚类问题，本文对标准遗传算法进行改进。首先，遗传算法采用 浮点数编码方法，在保持交叉、变异后的搜索空间不变的基础上，缩短了染色体编码长 度；其次，采用基于最短距离基因匹配的算术交叉算子和均匀变异算子，保证产生有意 义的新染色体；再次，用父代种群参与竞争的策略代替经常使用的最优保存策略，提高 算法的收敛速度；最后，用两种停止准则结合使用的方法，控制遗传算法的运算过程， 有效缩短了算法的运行时间。这两种停止准则分别是：种群的进化代数达到指定的终止 代数t，遗传算法停止；连续多次迭代的种群个体的平均适应度值之间差异小于某一极 小阈值，遗传算法停止。若两种准则满足其一，遗传算法停止。 本文提出了一种改进的遗传 k 均值聚类算法（igk） ，就是将改进的遗传算法与 k 均值算法相结合，先用改进的遗传算法对初始聚类中心进行优化，再执行 k 均值算法。 测试结果证明，igk 算法可以避免聚类算法陷入局部极小值，算法的稳定性高，收敛速 度快。 关 键 词：数据挖掘；遗传算法；k 均值算法；聚类分析 研究类型：应用研究 subject : research in data mining method based on genetic algorithms specialty : applied mathematics name : an na (signature) instructor : ding zhengsheng (signature) abstract with the development of the social production and the pace of life, the information technology advances quickly, which leads to the amount of the data information increase exponentially. data mining technology has powerful data analysis and processing capabilities, provides important and valuable information or knowledge to make decision, and brings immeasurable value to society. therefore, the study of data mining methods has important theoretical and practical significance. clustering analysis is one of the main tasks of data mining. k-means algorithm is the most commonly used clustering method. k-means algorithm possesses strong local search capability and rapid convergence capability, and the clustering result is independent of the order of the sample data. however, the algorithm is very sensitive to the initial cluster centers, and easily falls into local minimum. genetic algorithm has strong ability of global query optimization and is widely used to solve various optimization problems. in computation, we needs to determine the objective function and fitness function, and gradient information and other auxiliary knowledge are not necessary. therefore, combining genetic algorithm and k-means algorithm not only have strong capability of global query optimization of the genetic algorithm but also maintains strong local search capability of k-means algorithm. this dissertation mainly focuses on making a better combination of genetic algorithm and k-means algorithm to complement each other and improve the efficiency of clustering algorithm. specially, to the clustering problem the standard genetic algorithm is improved. the main details are as following: firstly, on the basis of remaining the search space unchanged after maintaining crossover and mutation and applying floating-point number coding method to the genetic algorithm, the chromosome encoding length reduced; secondly, using arithmetic crossover operator and uniform mutation operator of the shortest distance gene matching obtains a meaningful new chromosomes; thirdly, parent population competing strategy is employed to replace the usual optimal preservation strategy , and then to improve the algorithm convergence speed. finally, combing the used method with two kinds of stopping criterion, the running time of the algorithm is effectively shortened by controlling the computing process. the two stopping criterions: genetic algorithm stops when the evolution algebra of populations reaches the specified termination algebra; genetic algorithm stops when the difference between the average fitness values of the population individuals of the successive iterations is less than a minimum threshold. if one of the two kinds of criteria is satisfied, the genetic algorithm stops. this dissertation presents an improved genetic k-means algorithm (igk), which is used to make a combination of the improved genetic algorithm and the k-means algorithm. an improved genetic algorithm is utilized to optimize the initial cluster centers, and then the k-means algorithm is carried. test results show that igk algorithm can avoid clustering algorithm to reach a local minimum. further, the algorithms stability is high and convergence speed is fast. key words : data mining genetic algorithm k-means algorithm cluster analysis thesis : applied research 1 绪论 1 1 绪论 1.1 选题背景及研究意义 数据挖掘（data mining）正以一种全新的概念改变着人类利用数据的方式，被称为 未来信息处理的骨干技术之一。20 世纪，数据库技术取得了决定性的成果，得到了广泛 的应用。但是，数据库技术作为一种基本的信息存储和管理方式，仍然以联机事务处理 （on-line transaction processing，oltp）为应用核心，缺少对决策、分析、预测等高 级功能的支持机制。众所周知，随着科学技术的迅猛发展，数据库技术的应用规模、范 围不断扩大， 可获得的数据量越来越大， 数据的种类也日益繁多。 特别是数据仓库 （data warehouse）以及 web 等新型数据资源的日益普及，联机分析处理（on-line analytic processing，oltp） 、决策支持（decision support）以及分类（classification） 、聚类 （clustering）等复杂应用成为必然。面对挑战，数据挖掘技术应运而生，并显示出强大 的生命力。 数据挖掘使数据处理技术进入了一个更高级的阶段。 它不仅能够对数据进行低层次 的联机查询操作，而且能对这些数据进行微观、中观乃至宏观的统计、分析、综合和推 理，发现数据之间的潜在关系，从而帮助管理者做出更有利的决策、预测未来的发展趋 势等。通过数据挖掘，有价值的知识、规则或高层次的信息就能从数据库的相关数据集 合中抽取出来，从而使大型数据库作为一个丰富、可靠的资源为知识的提取服务。特别 需要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简 单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推 理。 数据挖掘是一个多学科交叉的研究领域。它融合了数据库技术、人工智能、机器学 习、统计学、知识工程、面向对象方法等众多领域的知识，受到来自各种不同领域的研 究学者的关注，因此有很多不同的术语名称，例如：数据库中知识发现（knowledge discovery in databases，简称 kdd） 、知识抽取（knowledge extraction） 、信息发现 （information discovery） 、数据考古学（data archaeology） 、数据捕捞（data dredging） 等等1。数据挖掘技术的迅速发展，得益于目前全世界所拥有的巨大数据资源以及对将 这些数据资源转换为信息和知识资源的巨大需求， 这些需求来自各行各业， 从商业管理、 生产控制、市场分析到工程设计、科学探索等。数据挖掘具有十分重要的理论及现实意 义和广泛的应用前景，国内外许多研究工作者对此领域投入了极大的热忱。 西安科技大学硕士学位论文 2 1.2 国内外研究现状 1.2.1 数据挖掘研究现状 机器学习就是萌芽时期的数据挖掘。机器学习是用计算机模拟人类学习的一门科 学，始于 20 世纪 60 年代末，真正的发展是在 20 世纪 80 年代初。1980 年，第一届国际 机器学习研讨会在美国召开。1984 年， 机器学习杂志正式出版。在机器学习发展过 程中，不同时期的研究途径与目的也不全相同，一般而言大致可分为三个阶段：神经模 型和决策理论、概念符号获取及知识加强、领域专用学习。80 年代末，随着数据在日常 决策中的重要性和对数据处理技术要求的提高，人们需要对数据进行深层次的处理，以 获得数据的总体特征以及对相应发展趋势的预测。然而，这些功能对传统的数据库管理 系统来说是无法做到的， 同时数据量的爆炸性增长也使得传统的处理方法变得不切合实 际。因此，需要一种自动化功能更强、效率更高的数据处理方法来帮助人们进行数据分 析。正是由于实际工作的需要以及相关技术的发展，将机器学习应用于大型数据库的知 识发现技术才逐渐发展起来2。 1989 年 8 月，在美国底特律召开的第十一届国际人工智能联合会议的专题讨论会 上，首次出现 kdd 这个术语。随后 1991 年、1993 年和 1994 年都举行了 kdd 专题讨 论会，来自各个领域的研究人员和应用开发者汇集一堂，集中讨论数据统计、海量数据 分析方法、知识表示、知识运用等问题。随着参与人员的不断增多，kdd 国际会议发 展为年会。1995 年，第一届知识发现与数据挖掘国际学术会议在加拿大召开。从此，数 据挖掘技术开始流行，国外掀起了研究的热潮。 目前，数据挖掘技术在国外十分流行。国际商业机器（ibm）与高性能计算研究院 （institute of high performance computing）携手合作，建立了知识探索中心（knowledge discovery center） ，专门提供商业数据挖掘方面的服务。ibm 董事经理洪铭文说，新成 立的“知识探索”中心综合了国际商业机器先进的硬件、软件及人力资源，以及高性能 计算研究院的巨型计算机设备和高档次的运作经验， 能够更好的为本地企业和政府机构 提供数据挖掘等商业智能服务，有助于进一步增强本地企业在全球范围的市场竞争力， 增加商业回报。 与国外相比，国内对数据挖掘的研究稍晚。目前，国内的许多科研单位和高等院校 竞相开展知识发现的基础理论及应用研究， 数据挖掘也从单纯的研究走向产品的开发和 技术的应用。国内的数据挖掘市场需求正在高速增长，国产的数据挖掘商业软件研究却 刚刚起步，但发展速度还是很快的，相信不久的将来会出现大量的国产数据挖掘软件。 1 绪论 3 1.2.2 遗传算法研究现状 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种全局优化概率 搜索算法。它最早由美国的密执安大学的 holland 教授提出3，兴起于 20 世纪 80 年代 末和 90 年代初期，历史起源可追溯到 60 年代初期。遗传算法早期的研究大多以对自然 遗传系统的计算机模拟为主，侧重于对一些复杂操作的研究，像自动博弈、生物系统模 拟、模式识别和函数优化等。总的来说，这是一个无明确目标的发展时期，缺乏指导性 的理论和高效的计算工具。70 年代，de jong 利用计算机进行了大量的纯数值函数优化 计算实验，树立了遗传算法的工作框架。80 年代，在前人一系列研究工作的基础上， goldberg 出版了专著 搜索、 优化和机器学习中的遗传算法 （genetic algorithms in search, optimization and machine learning） 4。该书全面总结了遗传算法的主要研究成果，系 统论述了遗传算法的基本原理及应用。此书奠定了现代遗传算法的科学理论基础。 随着遗传算法研究和应用的不断发展， 一系列以遗传算法研究和应用为主题的国际 会议十分活跃。从 1985 年开始，国际遗传算法会议，即 icga（international conference on genetic algorithm）每两年举行一次。在欧洲，从 1990 年开始也每隔一年举办一次类 似会议，即 ppsn（parallel problem solving from nature）会议。另外，以研究遗传算法 的理论基础为中心的学术会议 foga（foundation of genetic algorithm） ，也是从 1990 年开始举办的，每两年召开一次。 遗传算法提供了一种求解复杂系统优化问题的通用框架，不依赖于问题的具体领 域，被广泛应用于很多学科领域。目前，遗传算法所涉及的主要领域有自动控制、规划 设计、组合优化、图像处理、信号处理、人工生命等。可见，遗传算法的应用研究已从 初期的组合优化求解拓展到了许多更新、更工程化的应用方面。 1.3 遗传算法与数据挖掘 经过多年的研究，数据挖掘在继承和发展相关基础学科（如机器学习、统计学等） 方面取得了可喜的进步，探索出了许多独具特色的理论体系。但是，这绝不意味着挖掘 理论的探索已经结束，恰恰相反它留给了研究者丰富的理论课题：一方面，在这些大的 理论框架下有许多面向实际应用目标的挖掘理论等待探索和创新；另一方面，随着数据 挖掘技术及其相关技术的发展，新挖掘理论的诞生是必然的。新理论的发展必然促进新 的挖掘算法的产生，这些算法将会大大提高数据挖掘的有效性，如针对数据挖掘的某些 阶段、某些数据类型、大容量源数据集等方面更有效，也可能更好的融合特定的应用目 标。 遗传算法作为一种有效的全局并行优化搜索工具，具有简单通用、鲁棒性强、适于 并行处理以及高效、实用等显著特点。在解决以混沌、随机和非线性为典型特征的问题 西安科技大学硕士学位论文 4 上，遗传算法为其它科学技术难以解决的复杂问题提供了新的计算模型。特别的，遗传 算法能够有效解决大量嘈杂无序的数据问题，因此，它在数据挖掘方面的应用得到了研 究者极大的重视5。 聚类分析是数据挖掘的主要任务之一。常规聚类方法不能有效地处理局部极值问 题，因此当初始聚类中心在整个样本空间不平衡时，很难将这种不平衡纠正过来，从而 导致聚类结果对初始聚类中心的选取有着很大的敏感性，容易陷入局部极小值。若将遗 传算法与数据挖掘中传统的聚类方法相结合， 用遗传算法的全局搜索能力来优化这些容 易陷入局部最优的数据挖掘模型，就能够使这些模型跳出局部最优值并找到全局最优 解。实践证明，这是一种合理而高效的途径。 1.4 本文研究内容及论文安排 数据挖掘技术是目前国内外研究的一个热点，对于这一课题的方法研究，前人已经 得出很多的理论成果。本文主要研究遗传算法在数据挖掘的聚类分析方面的应用，如何 将遗传算法与 k 均值算法更好的结合，充分发挥两种算法的优点，弥补相互的不足。论 文的具体安排如下： 第一章是绪论，概述了论文的选题背景、研究意义及国内外研究现状，分析了遗传 算法用于数据挖掘技术的可能性。 第二章介绍数据挖掘的基本理论和应用领域，以及数据挖掘所面临的问题与挑战。 第三章详细介绍遗传算法的编码方式、适应度函数的构造、遗传算子的设计、控制 参数的选择及算法流程等基本原理与方法，并给出了标准遗传算法构成的基本要素。 第四章概述数据挖掘中的聚类分析方法的基本理论， 着重介绍 k 均值算法的基本思 想、数学优化原理，以及使用遗传算法改进 k 均值算法的必要性。详细论述本文提出的 igk 算法，并画出算法流程图。 第五章测试算法的性能， 用 iris 数据集和 wine 数据集分别对 k 均值算法、 gk 算法、 igk 算法进行测试，比较测试结果。最后将该算法应用于实例，对某一超市的会员信息 数据进行聚类。 第六章总结本文研究的内容，并指出进一步研究的问题。 2 数据挖掘概述 5 2 数据挖掘概述 数据挖掘（data mining） ，就是从大量的、不完全的、有噪声的、随机的数据中， 提取隐含在其中的、有效的、新颖的、潜在有用的、最终可理解的模式或知识的复杂过 程。数据挖掘的广义观点：数据挖掘就是从存放在数据库、数据仓库或其它信息库中的 大量的数据中“挖掘”有用知识的过程6。因此，数据挖掘又称为数据库中知识发现。 经过十几年的研究和实践，数据挖掘技术已经吸收了许多学科的最新研究成果，从 而形成独具特色的研究分支。正如其它新技术的发展历程一样，数据挖掘也必须经过概 念提出、概念接受、广泛研究和探索、逐步应用和大量应用等阶段。从目前的现状看， 数据挖掘仍然处于广泛研究和探索阶段。 2.1 数据挖掘的起源 数据挖掘的思想来自如下一些领域： （1）统计学的抽样、估计和假设检验； （2）人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论。 数据挖掘也迅速地接纳了来自其它领域的思想，这些领域包括最优化、进化计算、 信息论、信号处理、可视化和信息检索等。一些其它领域也起到重要的支撑作用，特别 地，需要数据库系统提供有效的存储、索引和查询处理支持。源于高性能的并行计算技 术在处理海量数据集方面是非常重要的。分布式技术也能帮助处理海量数据，并且当数 据不能集中到一起处理时更是至关重要7。数据挖掘与其它领域之间的联系如图 2.1 所 示。 图 2.1 数据挖掘与其它领域之间的联系 2.2 数据挖掘研究的理论基础 谈到数据挖掘， 必须进一步阐述其研究的理论基础问题。 坚实的理论是研究、 开发、 评价数据挖掘方法的基石。经过多年的探索，一些重要的理论框架已经基本形成，并且 数据库技术、并行计算、分布式计算 数据挖掘 ai、 机器学习和 模式识别 统计学 西安科技大学硕士学位论文 6 吸引着众多的研究者为此进一步努力，向着更深的方向发展。 数据挖掘方法可以是基于数学理论的，也可以是非数学的；可以是演绎的，也可以 是归纳的。从研究的历史看，它们可能是数据库、人工智能、数理统计、计算机科学以 及其它方面的学者和工程技术人员在数据挖掘的探讨性研究过程中创立的理论体系。 1997 年，mannila 对当时流行的数据挖掘理论框架给出了综述。结合最新的研究成果， 有下面一些重要的理论框架可以帮助我们准确的理解数据挖掘的概念与技术特点8。 （1）模式发现（pattern discovery）架构 在模式发现架构理论框架下， 数据挖掘技术被认为是从源数据集中发现知识模式的 过程。这是对机器学习方法的继承和发展，是目前比较流行的数据挖掘研究与系统开发 架构。按照这种架构，可以针对不同知识模式的发现过程进行研究。目前，关联规则、 分类模型、聚类模型、序列模式（sequence model）以及决策树（decision tree）归纳等 模式发现的技术与方法上已经取得了丰硕的成果。 （2）规则发现（rule discovery）架构 agrawal 等学者综合机器学习与数据库技术，将三类数据挖掘目标即分类、关联及 序列作为一个统一的规则发现问题来处理， 并综合给出了统一的挖掘模型和规则发现过 程中的几个基本运算， 解决了数据挖掘问题如何映射到模型和通过基本运算发现规则的 问题。这种基于规则发现的数据挖掘构架也是目前数据挖掘研究的常用方法。 （3）基于概率和统计理论 在基于概率和统计理论框架下， 数据挖掘技术被看作是从大量源数据集中发现随机 变量的概率分布情况的过程。例如，贝叶斯置信网络模型等。目前，这种方法在数据挖 掘的分类和聚类研究的应用中取得了很好的效果。 这些技术和方法可以看作是概率理论 在机器学习方面应用的发展和提高。统计学作为一门古老的学科，已经在数据挖掘中得 到广泛应用。例如，传统的统计回归法在数据挖掘中的应用。特别是最近十几年，统计 学已经成为支撑数据仓库、数据挖掘技术的重要理论基础。 （4）微观经济学观点 在微观经济学观点理论框架下，数据挖掘技术被看作一个问题的优化过程。1998 年，kleinberg 等人建立了在微观经济学框架里判断模式价值的理论体系。他们认为，如 果一个知识模式对一个企业是有效的话， 那么它就是有趣的。 有趣的模式发现是一个 新 的优化问题， 可以根据基本的目标函数， 对被挖掘数据的价值提供一个特殊的算法视角， 导出优化的企业决策。 （5）基于数据压缩（data compression）理论 在基于数据压缩理论框架下，数据挖掘技术被看作是对数据的压缩过程。按照这种 观点，关联规则、决策树、聚类等算法实际上都是对大型数据集的不断概念化或抽象的 压缩过程。按 chakrabarti 等人的描述，最小描述长度（minimum description length）原 2 数据挖掘概述 7 理可以评价一个压缩方法的优劣， 即最好的压缩方法应该是对概念本身的描述和把它作 为预测器的编码长度都最小。 （6）基于归纳数据库（inductive database）理论 在基于归纳数据库理论框架下，数据挖掘技术被看作是对数据库的归纳问题。一个 数据挖掘系统必须具有原始数据库和模式库， 数据挖掘的过程就是对归纳的数据查询的 过程。这种构架也是目前研究者和系统研制者倾向的理论框架。 （7）可视化数据挖掘（visual data mining） 1997 年，keim 等对可视化数据挖掘的相关技术进行了综述。虽然可视化数据挖掘 必须结合其它技术和方法才有意义，但是，以可视化数据处理为中心来实现数据挖掘的 交互式过程以及更好的展示挖掘结果等已成为数据挖掘中的一个重要方面。 当然，上面所述的理论框架不是孤立的，更不是互斥的。对于特定的研究和开发领 域来说，它们是相互交叉并且有所侧重的。从上面的叙述中，可以看出数据挖掘的研究 是在相关学科充分发展的基础上提出并不断发展的，其概念和理论仍在发展中9。 2.3 数据挖掘的任务、方法和过程 2.3.1 数据挖掘的任务 数据挖掘的功能大致有两种，预测检验功能和描述功能10。数据挖掘的任务主要有 4 项： （1）概念描述，即对数据进行浓缩，给出某类对象内涵的紧凑表示。 （2）发现关联规则，通过分析给出两个或多个变量间存在的相关性规律。 （3）聚类，即簇聚同类对象，使在抽象空间中属于同一类别的个体距离尽可能小， 反之尽量大。 （4）偏差检测，寻找观察结果与参照值之间的差别，这些偏差往往包含很多潜在有 价值的知识信息。 2.3.2 数据挖掘的方法 数据挖掘的研究涉及众多科学领域，挖掘的方法更是有很多种。常用的数据挖掘的 方法有11,12,13： （1）遗传算法。其基本原理是：模拟达尔文生物进化论的自然选择和遗传学机 理的生物进化过程的计算模型，是一种通过模拟自然进化过程来搜索最优解的方 法。 （2）粗糙集方法。其基本原理是：建立在分类机制的基础上，将分类理解为在特定 空间上的等价关系，而等价关系构成了对该空间的划分。粗糙集理论的主要思想是将不 西安科技大学硕士学位论文 8 精确或不确定的知识用已知的知识库中的知识来近似刻画。它能够有效地分析不精确、 不一致、不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的 知识，揭示潜在的规律。 （3）决策树方法。决策树方法是以信息论原理为基础，利用信息论中互信息（信息 增益）寻找数据库中具有最大信息量的字段，建立决策树的一个结点。然后再根据字段 的不同取值建立树的分支，在每个分支上集中重复建立树的下层结点和分支。这种方法 实际上是依循信息论原理对数据库中存在的大量数据进行信息量分析， 在计算数据特征 的互信息或信道容量的基础上提取出反映类别的重要特征。 （4）神经网络方法。其原理是：模拟人脑的神经元结构，以 mp 模型和 hebb 学习 规则建立起前馈式网络、反馈式网络和自组织网络 3 大类神经网络模型。神经网络方法 用于非线性数据和含噪声的数据时具有更大的优越性， 比较适合于市场数据库的分析和 建模，为工作人员提供顾客、用户、市场状况和市场走势等方面的分析结果。 采用上述技术的某些专门的数据分析工具已经发展了十几年的历史， 但这些工具所 能分析的数据量通常较小。现在，这些技术已经被直接集成到许多大型的工业标准数据 仓库和联机分析系统中去了。 2.3.3 数据挖掘的过程 数据挖掘是一个动态、交互的过程。从大的方面可以包括数据准备、挖掘操作和结 果解释几个主要部分。数据挖掘的流程图如图 2.2 所示。 图 2.2 数据挖掘的流程图 数据准备主要包括数据的集成、清理、变换与归约四个阶段。 数据集成即把多个数据源的数据结合起来存放到一个统一的数据存储中， 比如数据 仓库中，源数据可能包含多个数据库、数据立方体或文件。搜索所有与业务对象有关的 内部和外部数据信息，从中选择出适用于数据挖掘应用的数据。研究数据的质量，为进 知识 模型或规则 预处理后数据 目标数据 数据源 结果解释 挖掘操作 数据变换与 归约 数据集成与 清理 数据准备 挖掘操作 结果解释 2 数据挖掘概述 9 一步的分析做准备，并确定将要进行的挖掘操作的类型。数据清理清除掉噪音数据、空 值数据、不一致数据和不完整数据。 数据变换是指将数据转换成可供挖掘操作的形式； 数据归约技术可以用来得到数据 集的归约表示，但仍接近于保持数据的完整性。在归约后的数据上挖掘将更有效，可以 产生相近的分析结果。将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立 的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 数据预处理的结果直接影响到挖掘算法的性能。常用的技术有分箱、数据直方图、 概念树、主成分分析等。 对所得到的经过转换的数据进行挖掘，除了选择合适的挖掘算法外，其余一切工作 都能自动地完成。 解释并评估结果，将分析所得到的知识集成到业务信息系统的组织结构中去。其使 用的分析方法一般应视数据挖掘操作而定。 2.4 数据挖掘的应用领域 数据挖掘在许多领域得到了广泛的应用。它不仅是面向数据集的简单检索调用，而 且要对这些数据进行微观和宏观的统计、分析、综合和推理，以指导求解实际问题，企 图发现事件间的相互关联，甚至利用已有的数据对未来的活动进行预测14。 （1）市场营销方面是数据挖掘技术应用最早也是最重要的领域。将数据挖掘用于顾 客购物篮的分析，可以协助商场工作人员更好的布置货架，合理的安排促销活动时间、 促销商品组合以及了解滞销和畅销商品状况等商业活动。 通过对一种厂家商品在各连锁 店的市场共享分析， 客户统计以及历史状况的分析， 可以确定销售和广告业务的有效性。 （2）在天文学方面，有一个非常著名的数据挖掘应用系统 skicat（sky image cataloging and analysis tool） ，天文学家用它来发现遥远的类星体。skicat 的任务是构 造星体分类器对星体进行分类，使用决策树方法来构造分类器，结果使得能分辨的星体 较以前的方法在亮度上要低一个数量级之多，而且效率提高了 40 多倍。 （3）在生物学上，数据挖掘的应用主要集中于分子生物学，特别是基因工程的研究 上。数据挖掘在分子生物学上的工作主要有两方面：一是从各种生物的 dna 序列中定 位出具有某种功能的基因串； 二是在基因数据库中搜索与某种具有高阶结构或功能的蛋 白质相似的高阶结构序列。 （4） 在体育竞技中， ibm 公司开发的数据挖掘应用软件 advanced scout 被美国 nba 教练广泛应用于比赛中。advanced scout 帮助魔术队成功分析了不同队员布阵的相对优 势，并找到了战胜迈阿密热队的方法。 （5）银行和商业上经常发生诈骗行为，如恶性透支等。hnc 公司开发的 falcon 系统可用于探测可疑的信用卡交易。fais 金融交易系统可利用一般的政府单据，来识 西安科技大学硕士学位论文 10 别与洗钱有关的不法行为。 （6）在信息安全方面，数据挖掘可以从海量的安全事件数据中提取出尽可能多的隐 藏的安全信息，抽象出有利于进行判断和比较的与安全相关的普遍特征，从而发现未知 的入侵行为。因此，信息安全专家利用数据挖掘技术，以一种自动和系统的手段建立起 一套自适应的、具备良好扩展性的入侵检测系统，克服传统方法的缺点，提高了检测的 效率和速度。 （7） 在电信行业， 数据挖掘技术可以帮助电信企业制定合理的电话收费和服务标准、 针对客户群的优惠政策，防止费用诈骗等。 当然，数据挖掘还有许多应用领域，这里不能一一列举。分析这些应用领域的目的 是为了说明它的高可用性以及高挑战性。 数据挖掘必须和实际应用领域结合研究才有生 命力。 2.5 数据挖掘面临的问题与挑战 虽然数据挖掘技术已经在许多领域得到了广泛的应用， 但数据挖掘的研究并不是很 成熟，在实际应用性方面还有很大的局限性。正是这些局限性，促使数据挖掘的研究进 一步发展。数据挖掘面临的挑战主要表现在下述几个方面： （1）可伸缩性。由于数据产生和收集技术的进步，数吉字节、数太字节甚至数拍字 节的数据集越来越普遍。如果数据挖掘算法要处理这些海量数据集，则算法必须是可伸 缩的。许多数据挖掘算法使用特殊的搜索策略来处理指数型搜索问题。可伸缩还需要实 现新的数据结构以有效的方式访问个别记录。 （2）高维性。现在常常遇到具有数以百计或数以千计属性的数据集，而不是数十年 前常见的具有少量属性的数据集。在生物信息学领域，微阵列技术的进步已经产生了涉 及数千特征的基因表达数据。具有时间或空间分量的数据集也趋向于具有很高的维度。 （3）异种数据和复杂数据。随着数据挖掘在商务、科学、医学和其它领域的作用越 来越大，非传统的数据类型也越来越多。这些非传统的数据类型的例子包括含有半结构 文化和超链接的 web 页面集、具有序列和三维结构的 dna 数据、包含地球表面不同位 置上的时间序列测量值（温度、气压等）的气象数据。为挖掘这种复杂对象而开发的技 术应当考虑数据中的联系。 （4）数据所有权与分布。有时，需要分析的数据并非存放在一个站点或归属一个单 位，而是地理上分布在属于多个机构的资源中，这就需要开发分布式数据挖掘技术。分 布式数据挖掘算法面临的挑战主要有三个：一是如何降低执行分布式计算所需的通信 量； 二是如何有效地统一从多个资源得到数据挖掘结果； 三是如何处理数据安全性问题。 （5）非传统数据分布。传统的统计方法基于一种假设检验模式，但是这一过程费 力劳神。当前的数据分析技术任务常常需要产生和评估数以千计的假设，人们希望能够 2 数据挖掘概述 11 有一种可以自动地产生和评估假设的新型数据处理技术， 这就促进一些了数据挖掘技术 的开发。此外，数据挖掘所分析的数据集通常是代表数据的实际性样本，而且常常涉及 非传统的数据类型和数据分布。 2.6 本章小结 本章主要介绍了数据挖掘技术的基本概念、理论基础、任务和方法，主要过程及应 用领域，分析了数据挖掘面临的问题与挑战，从而使我们对数据挖掘技术有了全面、细 致的了解。 西安科技大学硕士学位论文 12 3 遗传算法的基本原理与方法 遗传算法（ga）是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。 由美国 j.holland 教授提出，基本原理是模拟达尔文的遗传选择和自然淘汰的生物进化 过程，建立计算模型，对相关问题进行优化计算15。该算法主要特点是群体搜索策略和 群体个体之间的信息交换，搜索不依赖于梯度信息。其简单通用，鲁棒性强，尤其适用 于处理传统搜索方法难以解决的复杂和非线性问题，可广泛用于组合优化、机器学习、 自适应控制、规划设计和人工生命等领域。 遗传算法是进化计算的一个重要分支。它在解决优化问题时，首先随机生成问题的 一组可能解，并对每个可能解进行编码。这组可能解的集合被称为种群，种群中的每个 可能解被称为染色体。每条染色体都有一个与之相对应的适应度值，适用度值越大的染 色体所代表的可能解越优。该算法模拟自然选择机制中的“适者生存”原理，根据适应 度值的大小，从初始种群中选择若干个较优的染色体，参与交叉、变异操作，这些操作 经过若干次迭代或者执行到满足特定的终止准则，最后得到优化问题的最优解。 3.1 编码方式 使用遗传算法解决问题时，首先需要对问题的可能解进行编码，即将问题的可行解 通过变换映射到基因空间，即遗传算法的搜索空间。反之称为解码，即将遗传算法的解 空间转换为问题空间。 针对一个具体应用问题， 如何设计一种完美的编码方案一直是遗传算法的应用难点 之一。目前还没有一套完整且严密的理论来指导人们设计编码方案。 de jong 曾提出了两条操作性较强的实用编码原则16： （1）有意义积木块编码规则：应使用能易于产生与所求问题相关的，且具有低阶、 短定义长度的编码方案； （2）最小字符集编码原则：应使用能使问题得到自然表示或描述的，具有最小编码 字符集的编码方案。 第一个编码原则适用于生成适用度较高的个体的编码方案， 第二个编码原则适用于 遗传算法在确定规模的群体中能够处理最多的模式。 该原则仅仅给出了一个设计编码方 案的指导性大纲，并不完全适用于任何问题。对于具体问题，应具体分析，找出对此问 题描述的最为方便，效率最高的编码方案。迄今为止人们常用的编码方案大体可以分为 三类：二进制编码方法、浮点数编码方法、符号编码方法。 3 遗传算法的基本原理与方法 13 3.1.1 二进制编码方法 二进制编码方法是遗传算法中最常用的一种编码方法， 它将问题的可能解映射成有 限个二进制符号0和1组成的符号串，即染色体。二进制符号串的长度与问题的求解精 度有关。假设某一参数的取值范围是 minmax ,uu，若用长度l的二进制编码符号串来表 示该参数，则总共能产生2l种不同的编码。若使用该参数编码时的对应关系如下： min min max 00000000000000000 0000000000000001 1 111111111111111121 l u u u l l mmmmm l 则二进制编码的编码精度为： maxmin 21 l uu （3.1） 假设某一个体的编码是： 1221lll xb bbb b l： 则对应的解码公式为： 12 2 minmax 1 1 min l l i i i uu bux （3.2） 例如：对于0,1023x，若用 10 位长的二进制编码来表示该参数的话，则下述符 号串： : 0 01 01 01111x 就可以表示一个个体，它所对应的参数值是175x ，此时的编码精度为1。 二进制编码方法具有的优点如下： （1）编码、解码操作简单易行； （2）交叉、变异等遗传操作便于实现； （3）符合最小字符集编码原则； （4）便于利用模式定理对算法进行理论分析。 二进制编码存在着连续函数离散化时的映射误差，如果个体串编码长度过短，则可 能达不到精度要求。个体串编码长度较长，虽然能提高精度，但却使得算法的搜索空间 过大，效率不高。二进制编码不便于反应所求问题的特定知识，不便于开发针对问题专 门知识的遗传算子， 人们在一些经典优化算法的研究中所总结出的宝贵经验也就无法在 这里加以利用。 西安科技大学硕士学位论文 14 3.1.2 浮点数编码方法 为改进二进制编码方法的缺点，人们提出了浮点数编码方法17，也叫做真值编码。 浮点数编码是指个体的每个基因值用某一范围内的一个浮点数 （也就实数） 来表示， 个体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实 值，所以也叫做真实值编码方法。 例如：若某个优化问题有 5 个变量1, 2,3,4,5 i ix，每个变量都有其对应的上下限 maxmin, ii uu，则 :x 5.80 6.90 3.50 3.80 5.00 就表示一个个体的基因型，其对应的表现型是： 5.80, 6.90, 3.50, 3.80, 500 t x 在浮点数编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中所使 用的交叉、 变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区 间限制范围内。 使用浮点数编码方法编码，可以克服二进制编码方法的缺点，并能直接对问题的可 能解进行遗传操作。通常，大部分数值优化问题采用浮点数编码比二进制编码方法的效 率高。 浮点数编码有下面几个优点： （1）适合于在遗传算法中表示范围较大的数； （2）适合于精度要求较高的遗传算法； （3）便于较大空间的遗传搜索； （4）改善了遗传算法的计算复杂性，提高了运算效率； （5）便于遗传算法与经典优化方法的混合使用； （