上海交通大学
学位论文原创性声明
本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。
学位论文作者签名：盛文峰
日期： 2007年2月6日
上海交通大学
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
保密□，在年解密后适用本授权书。
本学位论文属于
不保密√。
（请在以上方框内打“√”）
学位论文作者签名：盛文峰指导教师签名：饶若楠
日期：2007年2月 6日日期：2007年2月28日
摘要
在商务智能系统中，传统的聚类分析虽已广泛地应用，但还存在一些问题，例如处理大数据量时收敛较慢，以及容易陷入局部极小值，即早熟问题。针对这些问题，本文提出了一种基于改进型遗传算法的聚类分析方法，并应用于一种面向中小型企业的联机分析处理系统HBIOLAP，实验表明，该算法具有较好的聚类质量和综合性能。
首先，论文详细介绍了面向数据挖掘的相关技术，并对现有聚类分析技术进行了比较和说明。
其次，针对现有聚类分析的收敛慢和早熟问题，提出了基于改进型的遗传算法的聚类分析，包括染色体的编码，适应度的计算，交叉及变异算子，同时对该算法的性能与其他聚类分析算法做了比较，实验结果表明，该算法具有较好的聚类质量和综合性能。
最后，阐述了面向中小型企业的联机分析处理系统HBIOLAP的设计与实现，该系统包括了联机分析处理模块和聚类分析模块。并在具体的应用场景中，对超市销售数据进行挖掘，结果表明基于改进型的遗传算法的聚类分析在超市销售系统的实际应用中取得了良好的聚类效果。
关键词：聚类；联机分析处理；遗传算法；数据挖掘；改进型遗传算法；商务智能
Abstract
In Business Intelligence System the traditional cluster analysis has been widely used, but there are still some problems. When dealing with large data convergence, for example, it will sometime slower and more prone to local minimum problems. In view of these problems, the paper presents a cluster analysis method based on the improved genetic algorithms, an application-oriented small and medium-sized enterprises and business intelligence system for HBI. The design and implementation of online analytical processing subsystems, and experiments show that the clustering algorithm is better quality and performance.
The major work in this paper lists as follows：
First, the papers detail-oriented business intelligence systems and related technology Cluster analysis of the existing technologies.
Second, in response to the slow convergence, and cluster analysis of existing early, a cluster analysis based on the improved genetic algorithms, including chromosome coding meet the terms crossover and mutation. Meanwhile the performance of this algorithm are compared with other cluster analysis algorithm, the experimental results show that the clustering algorithm is better quality and performance.
Finally, described the business-oriented small and medium-sized enterprises in the online analytical processing subsystem HBI Intelligent
System Design and Implementation, The system include a data warehouse bottom-line analysis and cluster analysis platform module. Supermarket sales system and the specific scene of supermarket sales data mining, the results show that the genetic algorithm based on improved sales of the cluster analysis in the supermarket system have made the practical application of a good cluster effect.
Keywords: Data mining; Clustering; OLAP; Genetic algorithms; Improved Genetic algorithms; Business Intelligence
第一章绪论
1.1引言
随着人类社会进入信息时代，大规模存储设备和快速存取技术的迅猛发展，企业的信息化进程的飞速发展，积累了越来越多的关于目前客户和经营状况的数据。信息已经日益成为企业发展不可忽视的力量，尤其是信息产业，更需要及时准确的了解企业所有经营信息和所有客户信息，及时做出决策和对未来的预测，一方面帮助公司抓住机遇，快速决断，赚取更大的利润，另一方面针对当前出现的问题快速做出决策，防止更大损失。这就需要企业对所有信息进行汇总分析，挖掘出那些对公司有价值的信息和趋势，提高企业核心竞争力。随着知识经济时代的来临，记录客户与市场数据的信息和信息利用能力已经成为决定企业成败的关键因素，越来越多的国内外企业己经根据信息流和数据分析技术进行企业重整，传统的低效的数据记录方式无疑将被更先进的商务智能技术所代替。这就提出了商务智能(BI)及决策支持系统的概念，根据当前的数据所提供的信息，动态的调整公司战略战术，使企业处于不败的地位。
1.2课题研究的背景
在当今激烈的市场竞争中，企业的领导者经常需要商务智能系统的帮助，做出有效的决策，保持企业产品和服务的核心竞争力。无论企业决定如何竞争，都需要有一套完整商务智能系统，能够透过企业运营和用户的信息来确定潜在的机会与挑战并做出相应对策。BI这个词，起源涉及到经济学中的博弈论和统计学，也许还有仿生学。商务活动往往是多方的博弈，而不仅仅是两方，下棋时对弈双方均可以看到棋盘中的布局，不存在毫无戒备的突袭，失败仅来自于对手抢先的一步棋或者几步棋。而商务活动则相当于和多人下军棋，交战双方只能看到自己的损失，而不能看到详细的敌情。随时都有新产品和新的竞争对手出入市场，谁都不会预先把计划和打算通告给竞争对手，因此信息就变得非常宝贵。同时，棋手在下棋时通常需要考虑到第五、十甚至十五步棋的走法，与之类似，业务决策者也需要预见到后一个或后两个甚至后四个财务季度的行为，这种计算和预测比下棋更为复杂。
目前主要的BI相关产品厂商包括：Business Objects, IBM, Informix, Microsoft, Oracle，CA, SAS, Congo’s, Sybase，和NCR等公司。目前能提供全面解决方案的公司目前只有CA公司，其他的很多公司只能提供部分解决方案，需要与其他公司的产品联合起来使用。
图1-1：商务智能的基本系统框图
Fig1-1：The basic architecture diagram of Business Intelligence System CA以能够向用户提供完善的数据仓库构造咨询服务和全面的数据仓库产品系列。能够提供以“元数据”为核心的，结构化的，包容构造数据仓库各项技术的全面解决方案。它具有独特的元数据，管理与应用特性，具有用三维可视化技术解析处理的功能。CA解决方案提供ODBC接口，并将数据存储在第三方关系数据库(如Oracle, Sybase, SQL Server, Informix和IBMDB2等)中，其性能虽要打一些折扣，但提高了开放性。主要产品：Erwin, Decision Base, Info Pump, Info Beacon, Forest Trees, Repository, ProVisiona Cognos和Business Objects主要集中在数据查询，报表，OLAP和数据挖掘方面，并不提供数据仓库产品，严格意义上说只是前端工具，需要与其他厂商的数据库产品联合起来使用，对大多数的数据仓库都有很好的支持，支持Windows和多种Linux, Unix系统。这两个公司的产品以其易用性和通用性，几乎占据所有前端工具市场。其中Cognos的工具有：数据查询和即席报表生成工具一一Impromptu，数据挖掘工具一一Scenario。和在线分析处理(OLAP)工具一一Power Player Business Objects的工具有：集成查询，报表和分析工具一一Business Objects，世界上第一个通过Web进行查询、报表和分析的决策支持工具一一Web intelligence和面向主流商务用户的数据挖掘工具一一Business miner, Business miner可以实现深入的分析用以发掘深层次的数据之间的关系。
其他几个公司只提供部分解决方案，如IBM, Oracle, Informix, Sybase, NCR, SAS, Microsoft. Oracle公司的数据仓库解决方案包含了业界领先的数据库平台、开发工具和应用系统，它能够提供一系列的数据仓库工具集和服务。它具有多用户数据仓库管理能力，多种分区方式，较强的与OLAP工具的交互能力，及快速和便捷的数据移动机制等特性。但是Oracle的数据转移工具需手工编写SQL 脚本，在处理复杂的数据转换需求时困难很多。Oracle的前端工具易用性较差，需较多地依赖第三方产品。主要产品有：Oracle81是数据仓库的核心，Oracle Warehouse Builder集成数据建模、数据抽取、数据转移和装载、聚合、元数据的
管理等功能，Oracle Developer Server使企业级的应用系统开发工具，支持面向对象和多媒体，可同时生成Client/Server及Web下的应用，具有极高的开发效率及网络伸缩性，Oracle Discoverer是最终用户查询、报告、深入、旋转和WEB 公布工具，能够帮助用户快速访问关系型数据仓库，从而做出基于充分信息的决策，Oracle Darwin是基于数据仓库的数据挖掘工具，简单易用的图形化界面，提供决策树、神经网络等多种数据挖掘方法，支持海量数据的并行处理，分析结果可以和现有系统集成。
IBM公司提供了一套基于可视数据仓库的商务智能(B工)解决方案，具有集成能力强，高级面向对象SQL等特性。IBM公司自己并没有提供完整的数据仓库解决方案，但是它可以使用第三方的数据仓库工具。例如，查询工具使用Business Objects的Business Objects，统计分析工具使用SAS公司的SAS系统。IBM的主要工具有：Visual Warehouse, Essbase/DB2 OLAP Server, QUEST等。
Sybase公司提供的数据仓库解决方案以能够支持多种关系型数据库而受到业界推崇。它能够同时处理几十个即席查询，其Bit jisc技术和垂直数据存储技术使系统只访问特定的少量数据，使得查询速度比传统的关系型数据库管理系统快100倍。Sybase的Industry Warehouse Studio。包括相应行业所需的商务智能应用软件和数据分析模型，可以针对不同行业进行业绩分析、促销活动分析、用户群分析、销售分析和收益分析等，具有数据仓库设计、元数据管理等功能、支持广泛的应用软件和报表，并提供Warehouse Studio的设计工具、Warehouse Control Center等I具。 Informix公司日前发布了一个集成的、可伸缩的Fast Start 数据仓库解决方案，使用户能快速而便捷地设计开发具有可伸缩性的数据仓库或数据集市。采用ROLAP的星型模式与Informix IDS、IDS/AD紧密集成提供预先汇总、抽样、后台查询等性能优化手段。Informix产品能够集成Microsoft IIS 或Netscape Enterprise/Fast Track服务器，从而支持web访问。Informix没有提供自己的报表和数据挖掘工具，它可以集成第三方产品(例如结合Bri。的前端数据分析和报表功能，结合SAS的数据挖掘功能)。Informix并且向客户提供一套完整、使用的咨询服务包。采用Informix数据仓库解决方案可以使您的数据仓库系统具有高性能、高可扩展性，高开放性，可以自己进行定制等特性，同时，利用Informix的专业数据仓库咨询服务，将充分保证您的数据仓库系统建设快速、及时，保证您的数据仓库系统真正发挥作用。
在长期的实践过程当中，NCR形成了一套独特的数据仓库方法论和实施框架，这套理论被称为可扩展数据仓库(Scalable Data Warehouse,简称为SDW)oNCR 可扩展数据仓库的基本框架主要分成三个部分：数据装载、数据管理和信息访问。总的来看NCR的产品性能很好，但是，NCR产品的价格相对较高，中小企业用户难以接受。主要产品Teradata是高端数据仓库市场最有力的竞争者，主要运行在NCRWorldMarkSMP硬件的Unix操作系统平台上，提供交互分析、标准报告和多维度分析。为了开拓数据集市(DataMart)市场1998年，该公司也提供了基于Windows NT的TeradataoSAS数据仓库可以支持各种硬件平台、支持不同数据库之间数据的存取，它还可对不同格式的数据进行查询、访问和分析，SAS具有与目前许多流行数据库软件和老的数据文件的接口，并可在SAS环境中建立对应外部异构数据的统一的公用数据界面。总的来说，SAS系统的优点是功能强、性能高、特长突出，缺点是系统比较复杂，软件投资较高，而且每年都需交纳License费。主要产品：SAS/WA(Warehouse Administrator)，SAS/MDDB,SAS/AF,SAS/ITSV(IT Service Vision)。数据仓库是Microsoft公司刚
刚进入的一个全新领域，与该公司的传统产品差别较大。同时，Microsoft也缺少在数据仓库实施方面的咨询经验。
1.3课题研究的主要内容
本课题研究的目标就是在商务智能系统的背景下，从理论、算法和应用的角度对数据挖掘技术中的聚类算法进行了探索性的研究，主要研究内容有：
1)数据挖掘中的聚类算法分类研究。从聚类准则、聚类的表示、算法框架等不同角度来考察并区分这些算法，然后从混合聚类方法、增量聚类、自动化和可视化等技术方面对现有算法加以比较分析评价。分析了现有算法的优缺点，以利于进一步改进;通过对现有算法的性能评述，有利于数据挖掘用户能够针对特定的数据集选择正确的算法，以获得最优化的结果和性能;也可以为进一步的现有算法分类比较研究工作以及建立聚类基准的莫定基础。
2)聚类分析的遗传算法研究。讨论聚类问题的编码方式和适应度函数的构造方案与计算方法，分析不同遗传操作对聚类算法的性能和聚类效果的影响意义，并提出对聚类分析的遗传操作的改进和扩充方法。
3)基于GA的聚类算法及其应用研究。对传统GA算法进行改进，首次提出了基于自我调适GA的聚类算法。实验采用标准数据集将该算法与标准GA算法和平凡GA算法作了比较，证实了自我调适GA算法的有效性，并具有避免早熟和收敛较快的特点。
4)运用上述聚类算法对标准数据集进行分析，并利用图形工具对分析结果进行了展现，进而将分析结果用于商务智能中辅助决策。
1.4课题研究的意义
数据挖掘是随着数据库和知识发现等领域技术发展而逐渐出现的新技术，它的出现只是十年前的事情，而商务智能也只是最近几年才出现并且繁荣起来的。二者的结合是一个新的课题。根据企业的需求，建立面向商务智能的数据挖掘应用，有助于提高企业的竞争力。这在客观上将会推动商务智能的进一步发展。由于数据挖掘具有与应用背景紧密结合的特点，研究数据挖掘的一般方法和商务智能的特点，并分析面向商务智能的数据挖掘的一般特点和方法，对于如何实施商业智能、建立基于数据挖掘的客户关系管理具有重要的指导意义。
识别和分类是人类活动中最基本的一种，人们要通过分类来形成假设和建立概念也要通过分类来发现和总结规律，因此，分类问题的研究具有十分重要的意义。作为无监督分类的手段之一，聚类分析是用数学的方法研究分类问题的一门学科，它也经历了20多年的发展历程，尽管迄今为止对其研究从未间断过，也取得了颇为丰硕的成果，但聚类算法仍存在诸多不完善的地方，甚至还有严重的不足之处。对聚类算法的进一步优化研究就显得尤为迫切和必要。这不仅有助于算法理论的完善，更有助于算法的推广和应用。
数据挖掘中的聚类分析与分类模式不同，在分类模块中，对于目标数据库中存在那些类这一信息我们是知道的，在那里我们要做的就是将每一条记录分别属于哪一类标记出来：与此相似但又不同的是，聚类是在预先不知道目标数据库到底有多少类的情况下，希望将所有的纪录组成不同的类或者说“聚类”(cluster),
并且使得在这种分类情况下，以某种度量为标准的相似性，在同一聚类之间最小化，而在不同聚类之间最大化。事实上，聚类算法中很多算法中的相似性都是基于距离的，而且由于现实数据库中数据类型的多样性，关于如何度量两个含有非数值型字段的记录之间的距离的讨论有很多，并提出了相应的算法。在很多应用中，由聚类分析得到的每一个聚类中的成员都可以被统一看待。分类实际上是有教师的学习过程。它的特点是根据已经掌握的每类若千样本的数据信息，总结出分类的规律性，建立判别公式和判别规则。然后，当遇到新的样本点时，只需根据总结出的判别公式和判别规则，就能判别该样本点所属的类别。
在数据挖掘领域主要研究了一些面向大型数据库、数据仓库的高效和实用的聚类分析算法并得到了一定的实际应用。例如，在科学数据探测、信息检索、文本挖掘、WEB数据分析、客户关系管理(CRM)、医学诊断、生物学等方面的数据挖掘应用软件中，聚类分析技术都起着重要作用。在商业领域，聚类可以帮助市场分析人员从他们的消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯;在生物学中，它可以被用来辅助研究动、植物的分类，可以用来分类具有相似功能的基因，还可以又来发现人群中的一些潜在的结构等等：聚类还可以用来从地理数据库中识别出具有相似土地用途的区域;可以从保险公司的数据库中发现汽车保险中具有较高索赔概率的群体;还可以从一个城市的房地产信息数据库中，根据房型、房价及地理位置分成不同的类;还可以用来从万维网上分类不同类型的文档等。就数据挖掘功能而言，聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步的分析，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。
1.5课题研究取得的主要成果
本课题研究的成果主要体现在如下以下三个方面：
1)引入了从聚类准则、聚类的表示、算法框架等不同角度来分类现有算法的思想;提出了从混合聚类、增量聚类、自动化和可视化等技术方面对现有算法加以比较分析评价的方法;讨论了聚类分析的遗传算法和进化策略在聚类分析中的应用，给出了基于进化策略的聚类分析的算法思想。
2)提出了一种基于改进型遗传算法的聚类算法，并在此基础上对标准数据集进行分析，利用图形工具对分析结果进行了展现，进而将分析结果用于商务智能中辅助决策。
1.6论文的组织结构
商务智能是信息时代和知识经济时代的新产物，充满了无限活力。在信息爆炸的时代，客户关系管理(Customer Relation management CRM)变得至关重要，企业了解客户、与客户保持稳固的关系是企业竞争成功的关键。要想在种种挑战中获胜，企业必须对其中的成败要素进行动态分析、动态调整，化不利为有利。而数据挖掘是帮助企业进行分析的有力工具。
本文综述了商务智能、数据挖掘的概念、数据挖掘技术、基于遗传算法的聚类技术以及其应用，为商务智能中的数据挖掘及其应用提供理论依据。在此基础
上，重点讲述了一种基于改进型遗传算法的聚类分析技术，并运用上述聚类算法对标准数据集进行分析，利用图形工具对分析结果进行了展现，进而将分析结果用于商务智能中辅助决策。
全文组织如下：
第一章绪论：简要介绍了本论文的研究背景、研究意义、主要工作及组织结构等。第二、三章主要介绍了商务智能，数据挖掘及聚类分析技术等概念，在综述了数据挖掘技术的基础上，进一步地讨论了商务智能系统的体系结构、流程、难点以及应用等。第四章着重对传统的聚类分析技术中的遗传算法进行了改进，并对改进的遗传算法进行分析和试验对比。第五章则将改进后的聚类技术应用到商务智能系统的环境中，并对得出的结果进行了分析。第六章：总结与展望：对论文的工作进行总结并指出下一步的工作计划。
第二章相关技术基础
本章主要介绍课题研究的一些相关技术，如数据挖掘和聚类分析，遗传算法等。
2.1数据挖掘
数据仓库的最终应用是为了数据分析和数据挖掘，否则海量数据就是一堆无用的数据。下面介绍一下如何使用数据仓库进行数据分析和数据挖掘。
2.1.1数据挖掘概述
随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的数据量急剧增大，在大量的数据背后隐藏着许多重要的信息，如果能把这些信息从数据库中抽取出来，将创造很多潜在的利润，而这种从海量数据库中挖掘信息的技术，就称之为数据挖掘[1](Data Mining-DM)。1995年以来，国外在知识发现和数据挖掘方面的论文非常多，已形成了热门研究方向。
从广义上讲，数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。这个定义包括以下四个层次的含义：
(1)数据源必须是真实的、大量的、含噪声的；
(2)发现的是用户感兴趣的知识；
(3)发现的知识要可接受、可理解、可运用，最好能用自然语言表达发现结果；
(4)并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的，是有特定前提和约束条件、面向特定领域的。
从商业角度出发，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。
数据仓库和数据集市已在广泛的应用领域使用。几乎每个行业的商务管理人员都使用收集、集成、预处理和存储在数据仓库与数据集市中的数据，进行数据分析和决策。在许多公司，数据仓库用作企业管理的计划——执行——评估“闭环”反馈系统的一部分。数据仓库广泛用在银行、金融服务、消费物品和零售分配部门，以及诸如基于需求的产品生产。通常，数据仓库使用时间越长，它进化得越好。该进化进行多遍。开始，数据仓库主要用于产生报告和回答预先定义的查询。渐渐地，它用于分析汇总的和细节的数据，结果以报告和图表形式提供。稍后，数据仓库用于决策，进行多维分析和复杂的切片和切块操作。最后，数据仓库可能用于知识发现，并使用数据挖掘工具进行决策。在这种意义下，数据仓库工具可以分为存取与检索工具，数据库报表工具，数据分析工具和数据挖掘工具。
商业用户需要一种手段，知道数据仓库里有什么(通过元数据)，如何访问数
据仓库的内容，如何使用数据分析工具分析这些内容和如何提供分析结果。有三种数据仓库应用：信息处理、分析处理和数据挖掘。
.信息处理支持查询和基本的统计分析，并使用交叉表、表、图表或图进行报告。数据仓库信息处理的当前趋势是构造低代价的基于网络的存取工具，然后与网络浏览器集成在一起。分析处理支持基本的OLAP操作，包括切片与切块、下钻、上卷和转轴。一般地，它在汇总的和细节的历史数据上操作。与信息处理相比，联机分析处理的主要优势是它支持数据仓库的多维数据分析。
数据挖掘支持知识发现，包括找出隐藏的模式和关联，构造分析模型，进行分类和预测，并用可视化工具提供挖掘结果。“数据挖掘与信息处理和联机数据分析的关系是什么?”信息处理基于查询，可以发现有用的信息。然而，这种查询的回答反映直接存放在数据库中的信息，或通过聚集函数可计算的信息;它们不反映复杂的模式，或隐藏在数据库中的规律。因此，信息处理不是数据挖掘。联机分析处理向数据挖掘走近了一步，因为它可以由用户选定的数据仓库子集。在多粒度上导出汇总的信息。由于数据挖掘系统也能挖掘更一般的类/概念描述，这就有一个有趣的问题："OLAP进行数据挖掘吗?OLAP系统实际就是数据挖掘系统吗?”OLAP和数据挖掘的功能可以视为不交的：OLAP是数据汇总/聚集工具，它帮助简化数据分析;而数据挖掘自动地发现隐藏在大量数据中的隐含模式和有趣知识。OLAP工具的目标是简化和支持交互数据分析;而数据挖掘的目标是尽可能自动处理，尽管允许用户指导这一过程。在这种意义下，数据挖掘比传统的联机分析处理前进了一步。
另一种更广泛的观点可能被接受：数据挖掘包含数据描述和数据建模。由于OLAP系统可以提供数据仓库中数据的一般描述，OLAP的功能基本上是用户指挥的汇总和比较(通过上、下钻，旋转，切片，切块和其它操作)。这些尽管有限，但都是数据挖掘功能。同样根据这种观点，数据挖掘的涵盖面要比简单的OLAP 操作宽得多，因为它不仅执行数据汇总和比较，而且执行关联、分类、预测、聚类、时间序列分析和其它数据分析任务。
OLAP为交互式数据分析树立了一个好榜样，并为探测式数据挖掘做了必要的准备。例如，考虑关联模式的发现。应当允许用户沿着任意维上卷，而不是在原始的数据层，在事务间挖掘关联。例如，用户可能希望在item维上卷，由观察特定电视机的数据，到观察诸如索尼、松下等类电视机的数据。在搜索有趣的关联时，用户也可以由事务导航到顾客或顾客类型。这种OLAP风格的数据挖掘是OLAM的特点。在下一章研究数据挖掘原理时，我们特别强调OLAP挖掘。即强调数据挖掘与OLAP技术的集成。
2.1.2数据挖掘的组成
采用KDD的广义观点：KDD是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣、有意义的知识的过程。基于此观点典型的KDD系统主要由以下几个部分组成：
数据库、数据仓库或其他信息库：是进行数据挖掘的数据源，是一个或一组数据库、数据仓库、电子表格或其他类型的信息库。可以在他们的数据上进行数据清理和集成。
数据库或数据仓库服务器：根据用户的数据挖掘要求，数据库或数据仓库服务器负责提取相关的数据。
知识库：是特定的领域知识，用于指导搜索或评估结果模式的兴趣度。这种知识可能包括概念分层，用于将属性或属性值组织成不同的抽象层，其中用户确信方面的知识也可以包含在内，可以根据非期望性评估模式的兴趣度使用这种知识。领域知识的其他例子有兴趣度限制或阈值和元数据(例如，描述来自多个异种数据源的数据)。
数据挖掘引擎：是数据挖掘的最重要的基本部分。由一组功能模块组成，用于特征化、关联、分类、聚类分析以及演变和偏差分析。
模式评估模块：通常此成分使用兴趣度度量，并与数据挖掘模块交互，以便将搜索聚集在有趣的模式上。它可能使用兴趣度阈值过滤发现的模式。模式评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。对于有效的数据挖掘，应尽可能深地将模式评估推进到挖掘过程之中，以便将搜索限制在有兴趣的模式上。
图形用户界面：是在用户和数据挖掘系统之间通信，允许用户与系统交互、指定数据挖掘查询或任务、提供信息、帮助搜索聚焦、根据数据挖掘的中间结果进行探索式数据挖掘。此外，还允许用户浏览数据库和数据仓库模式或数据结构，评估挖掘的模式，以不同的形式对模式可视化。
2.1.3数据挖掘的一般过程
所有的数据挖掘系统都要有数据准备、执行挖掘算法和表达结果等几个阶段。数据挖掘过程细分为以下几个步骤[33]。
1.理解和定义问题
2.数据的搜集和抽取
3.数据净化
4.数据引擎
5.算法引擎
6.运行数据挖掘算法
7.评估结果
8.重新精化数据和问题
9.使用结果进行决策
上述的九个步骤在数据挖掘过程中要反复多次。见下图所示，其中，每个步骤都是必不可少。
图2-5：数据挖掘过程
Fig2-5：Data mining process
2.1.4数据挖掘的主要分析方法
数据挖掘通过预测未来趋势及行为，做出基于知识的决策。数据挖掘的目标是从数据库中发现隐含的、有意义的知识，主要可以分为六类分析方法：
（1）自动预测趋势和行为
数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它可预测的问题包括预报破产以及认定对指定事件最可能做出反应的群体等等。（2）关联分析[11，12]
关联分析就是从大量数据中发现项集之间有趣的关联或相关联系。若两个或多个数据项的取值重复出现且概率很高时，它就存在着某种关联，可以建立起这些数据项的关联规则，如“在购买面包和黄油的顾客中，有90%的人同时也买了牛奶”(面包+黄油+牛奶)。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。在大型数据库中，这种关联规则是很多的，一般用“支持度”和“置信度”两个阈值来淘汰那些没有用的关联规则。关联分析广泛应用于市场营销、事务分析等应用领域。
（3）分类[13，14]
分类(classification)是这样的过程，它找出描述并区分数据类或概念的模型(或函数)，以便能够使用模型预测类标记未知的对象类。导出模型是基于对训练数据集(即其类标记已知的数据对象)的分析。导出模型可以用多种形式表示，一般利用判定树归纳[15]、Bayes分类、神经网络[16，17]、k-最近邻[1]、遗传算法[18]、粗糙[19]等技术进行分类。分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可能希望预测某些空缺的或不知道的数据值，而不是类标记。当被预测的值是数值数据时，通常称之为预测(prediction)。尽管预测可以涉及数据值预测和类标记预测，通常预测限于值预测，并因此不同于分类。预测也包含基于可用数据的分布趋势识别。
（4）聚类
对一个数据对象的集合进行分析，将数据对象分组成为多个类或簇，在同一簇内的对象之间具有较高的相似度，而簇之间的对象差别较大。相似度是根据描述对象的属性值来计算的。距离是经常采用的度量方式。它的目的是使属于同一类别的个体之间的距离尽可能地小，而不同类别的个体间的距离尽可能地大。聚类的主要研究技术有划分方法(partitioning method)、层次方法(hierarchical method)、基于密度的方法(density-based method)、基于网格的方法(grid-based method)和基于模型的方法(model-based method)。
（5）概念描述[20，21]
一个概念常常是对一个包含大量数据的数据集合总体情况的概述。对含有大量数据的数据集合进行概述性(summarized)的总结工作并获得简明(concise)、准确(precise)的描述，这种描述就称为概念描述(concept description)。概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。
（6）偏差检测[22，23]
数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏
差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意义的差别
2.1.5数据挖掘的局限性和发展趋势
1.数据挖掘的局限性
数据挖掘是一个工具，而不是有魔力的权杖。它不会坐在数据库上一直监视数据库，然后当它发现有意义的模型时发一封电子邮件。他仍然需要了解业务，理解数据，弄清分析方法。数据挖掘只是帮助商业人士更深入、更容易地分析数据，它无法告诉某个模型对企业的实际价值，而且数据挖掘中得到的模型必须要在现实生活中进行验证。
注意数据挖掘中得到的预言模型并不会告诉一个人为什么会做一件事或采取某个行动，数据挖掘只会告诉使用者它会这么做，至于为什么它这样做则需要人去考虑。比如，数据挖掘可能会告诉你，如果这个人是男的、年收入在5万到6万之间，那么他可能会买你的商品或服务。你可能会利用这条规则，集中向这类人推销商品并从中获益，但是数据挖掘工具不会告诉你他们为什么会买你的东西，也不能保证所有符合这条规则的人都会买。
为了保证数据挖掘结果的价值，必须了解数据，这一点至关重要。数据挖掘不会在缺乏指导的情况下自动的发现模型。不能让数据挖掘工具帮我们提高直接邮件推销的影响率，而是应该让数据挖掘工具找对推销回应的人，或既回应又做了大量订单的人的特征。在数据挖掘中，寻找这两种模型是很不相同的。
虽然数据挖掘工具可以让使用者不必再掌握高深的统计分析技术，但使用者仍然需要知道所选用的数据挖掘工具是如何工作的，它所采用的算法的原理是什么。所选用的技术和优化方法会对模型的准确度和生成速度产生很大影响。
数据挖掘永远不会替代有经验的商业分析师或管理人员所起的作用，它只是提供一个强大的工具。每个成熟的、了解市场的公司都已经具有一些重要的、能产生高回报的模型，这些模型可能是管理人员花了很长时间，作了很多调查，甚至是经过很多失误之后得来的。数据挖掘工具要做的就是使模型得到得更容易、更方便，而且有根据。
2.数据挖掘的发展趋势
当前，数据挖掘和知识发现的研究方兴未艾，其研究与开发的总体水平相当于数据库技术在70年代所处的地位，迫切需要类似于关系模式、DBMS系统和SQL查询语言等理论和方法的指导。鉴于数据、数据挖掘任务和数据挖掘方法的多样性，给数据挖掘技术提出了许多挑战性的课题，这些课题包括：
(I)数据挖掘应用的探索;
(2)可伸缩的方法;
(3)交互式发现;
(4)与数据库系统、数据仓库系统和Web数据库系统的集成;
(S)数据挖掘语言的标准化;
(6)可视化数据挖掘;
(7)复杂数据类型挖掘;
(8)Web挖掘，隐私保护和信息安全等。
但是，不管怎样，需求牵引与市场推动是永恒的，DMKD将首先满足信息
时代用户的急需，大量的基于DMKD的决策支持软件产品将会问世。只有从数据中有效地提取信息，从信息中及时地发现知识，才能为人类的思维决策和战略发展服务。也只有到那时，数据才能够真正成为与物质、能源相媲美的资源，信息时代才会真正到来。
2.2数据挖掘中的聚类分析技术概述
聚类(Clustering)是物理的或抽象的对象集合无监督分组的过程。聚类生成的组称为簇(cluster),簇是数据对象的集合，通过进行聚类分析，能够有效地把数据划分到不同的组中，组之间的差别尽可能大，组内的差别尽可能小。聚类分析亦称群分析、簇群分析等，是数值分类学的一个分支。从学科的谱系图上看，聚类分析不过是信息科学这棵大树上非监督模式识别分支的一片树叶，它将多元统计的理论应用于分类，虽然在理论与方法上，它都还不很完善，但已应用于市场营销、顾客分类、模式识别、过程优化、数据挖掘、配方设计、空间分析、WEB 文档分类等许多领域中，并取得了可喜成绩，受到人们广泛重视。聚类就是按照一定的要求和规律对事物进行区分和分类的过程，在这一过程中没有任何关于分类的先验知识，没有教师指导，仅靠事物间的相似性作为类属划分的准则，因此属于无监督分类的范畴。聚类分析则是指用数学的方法研究和处理给定对象的分类。聚类分析是数据挖掘中很重要的一种挖掘算法，聚类(clustering)就是将数据对象分组成为多个类或簇(cluster)，在同一个簇中的对象之间具有较高的相似度，而不同簇之间的对象差别较大。相异度就是通过描述对象的属性值来计算的。距离是经常采用的度量方式，聚类分析源于许多研究领域，包括数据挖掘，统计学，生物学以及机器学习。在数据挖掘领域，研究工作己经集中在大型数据库的有效和实际的聚类分析寻找适当的方法。活跃的研究主题主要集中在聚类方法的可伸缩性，方法对聚类复杂形状和类型的数据的有效性，高位聚类分析技术以及针对大型数据库中的混合数值和分类数据的聚类方法。
2.2.1聚类分析的基本知识
聚类分析的目的是揭示样本点之间“簇成一团”的本质。要想定量地处理一批样本点，首先必须对这些样本点的性质进行定量的表示。领域专家确定采用哪些指标特征变量来精确刻画样本的性质，以及如何定义样本之间的相似性测度，需要确切地描述和度量有关属性，并从中比较对象间的相似程度，把最接近的对象归并成类。从统计学角度来盾，在聚类分析中常把对象称为样品或个体，把它们的属性称为定量或指标，变量的描述可以是定性或定量的。
样本类型。一般地，常用多个指标特征变量来描述一个样本点。指标特征变量可以分为以下3种，不同类型的指标特征变量有不同的处理策略。
间隔尺度：使用连续的实数来表示的数量信息，比如温度、浓度、长度等。
有序尺度：特征变量取离散值，没有数量信息，但是具有次序关系，比如成绩分为优、良、中、及格等。
名义尺度：特征变量取离散值，不仅没有数量信息，而且也没有次序关系，它仅仅是个名称而已。比如肤色分为黄、白、棕、黑等。对于间隔尺度的指标特征变量，一个样本点实际上就是R"空间中的一点，可以很方便地定义加、减、
乘、除以及各种复杂运算，它和我们的直观是很一致的。而对于名义尺度特征变量就没有这么便利了，因为对于这种特征变量无法定义合适的运算。所以，现在聚类分析的大部分研究都集中在间隔尺度特征变量上。
数据挖掘中对聚类算法的典型要求包括以下几点：可伸缩性：许多算法对于较小的数据集能够很好地进行聚类，但是，大型数据集中可能包含有几百万、几千万乃至更多的对象。虽然通过抽样可以减少要处理的数据量，但是抽样会对聚类的结果带来影响甚至会产生错误的结果。因此，可伸缩性好的聚类算法是很有必要的。能够处理混合型数据：许多算法是设计来对数值型(numerical)数据进行聚类的。然而，在许多应用中待聚类的数据可能是二值型(binary),枚举型(categorical或nominal),序数型(ordinal)，也可能是上述各种类型数据的混合。识别任意形状的聚类：很多聚类算法中采用了欧式距离(Euclidean distance)或街区距离(Manhattan distance)度量来确定聚类，而这些距离度量倾向于识别大小与密度都相差不大的球形聚类。然而，聚类可能是各种形状的，如线形、环形、凹形、及其他各种复杂不规则形状。这就要求聚类算法要能够识别任意形状的聚类。
在确定输入参数时需要的相关领域内的知识最少：许多聚类算法要求用户输入一定的参数(如类别数或一定的度量阀值等)，而聚类结果对输入的参数非常敏感。而这些参数往往很难确定，尤其对于高维数据集更是如此。这不仅对用户带来了难题，而且还使聚类的结果难以控制。能够处理噪声：现实世界的很多数据中都包含一些异常数据或错误数据，有些聚类算法对这些数据非常敏感，并可能会产生错误的聚类结果。对输入顺序不敏感：有些聚类算法对数据的输入顺序非常敏感，例如，对于同一个数据集，用不同的顺序输入到某个算法中，就可能会产生完全不同的聚类结果。对高维数据的处理：数据库或数据仓库中的数据可以有几十乃至成百上千个维度或属性。许多聚类算法只擅长处理低维数据，如二维或三维数据。在高维数据空间中，数据可能非常稀疏并且高度扭曲，因此，高维空间中数据的聚类是一个很大的挑战。带有约束条件的聚类：在现实世界中的一些应用中，可能需要在一些约束条件下来进行聚类分析。例如一个城市中自动柜员机位置的选择，就需要在对家庭分布进行聚类时，考虑城市中河流、公路网、每个地区消费者的需求等约束条件。可理解性和可用性：用户期望聚类的结果是可以解释、易于理解并具有可用性。也就是说，聚类可能需要与具体的语义解释和具体应用结合在一起，具体应用的特定目标可能会影响到聚类算法的选择。
2.2.2聚类算法的分类
目前存在很多的聚类算法，具体选用那个算法要根据数据的类型、聚类的目的和应用。可以对同一数据集运用多个聚类算法，发挥每个算法的优势，尽可能多的发现数据中隐藏的信息。目前主要的聚类算法有以下几类：
划分方法(partitioning method)
划分方法(partitioning method)：给定一个M个对象或元组的数据库，一个划分方法构建一个数据的K个划分，每个划分表示一个聚类，并且K<=M.K需要提前给定，划分算法根据K做一个初始划分。然后采用迭代的重定位技术，不断尝试目标对象在划分间移动改进划分。一个好的划分的一般判断标准是：在同一个类中的对象尽可能的相似，而不同划分中的对象要尽可能的不同，也可以用距离来说明，同一划分中的对象距离要尽量近，而不同划分中的对象间距离要尽量大。为找到最优划分，聚类会穷举所有可能的划分。绝大多数应用采用了比较
流行的启发式处理方法：1)k-平均算法，在该算法中，每个划分用划分中对象的平均值来表示。2)k-中心点算法，本算法中每个划分用接近划分中心的一个点表示。这些启发式聚类方法对中小型数据库中发现球状簇很有效，但对于大规模的数据或不规则图形的簇还需要扩展。
层次的方法(hierarchical method)
层次的方法(hierarchical method)：层次的方法对给定的数据对象集合进行层次的分解。根据层次的形成不同方式，分为自底向上(凝聚)和自顶向下(分裂)的方法，自底向上方法先把所有对象都放在不同的簇中，然后逐渐与距离比较近的对象或组合并形成更大的组，直到最终形成一个组或者达到中止条件;自顶向下方法是先把所有的对象放在同一个组中，然后逐渐把距离较远的对象剥离出去，形成新的组，直到每个对象独在一个组中或者达到中止条件。层次方法的缺点是不能回溯，一旦把对象放到一个组中就不能改变以前的决定，因而不能更正错误的决定。因而需要改进决定的正确性，以改进聚类的结果。有两种改进的
方法：1)在每层的划分时，仔细分析对象间的关系，正确每次都做正确的决定，从而减少了缺乏自我更正能力的缺陷。例如CUER和Chameleon算法。2)综合层次凝聚和迭代的重定位方法，首先采用自底向上的层次算法，然后采用迭代的重定位来改进聚类结果。例如BIRTH算法。
基于密度的算法(density-based method)
基于密度的算法(density-based method)：大多数的聚类算法都是基于对象间的距离进行聚类分析。这样的方法智能发现球状的聚类，对比较怪异的聚类图形则无能为力。随之提出了基于密度的聚类算法，其主要思想是只要临近区域的密度(对象的数据)超过某一阈值就继续聚类，也就是说一个参考对象周围必须包含一定的点才能继续聚类，否则该聚类停止聚类。基于密度的算法可以滤掉噪声的孤立点，可以发现任意形状的簇。DBSCAN是一个有代表性的基于密度的方法，它根据一个密度阈值来控制簇的增长。OPTICS是另一个基于密度的算法，它为自动的和交互的聚类分析计算一个聚类顺序。
基于网格的方法(grid-based method)
基于网格的方法(grid-based method)：基于网格的方法把对象空间量化为有限数据的单元，形成一个网格结构。所有的聚类操作都做这个网格结构上进行。这种方法的主要优点是处理速度快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。STING算法是基于网格的典型例子。CLIQUE 和Wave Cluster这两种算法既是基于网格的，又是基于密度的。
基于模型的方法(model-based method)
基于模型的方法(model-based method)：基于模型的方法为每个簇假定一个模型，寻找数据对给定的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度而产生健壮的聚类方法。有一些算法集成了很多种聚类方法的思想，所以有时将某个算法划分为某类是很困难的。比较新的聚类算法包括等密度线聚类算法，采用类似地理学等高线的方法，把相同密度的地方用闭合曲线标记出来，这种算法的好处是能识别不规则图形的聚类。
2.3遗传算法
遗传算法起源于生物系统进行的计算机模拟研究，它是模拟生物进化过程的计算模型，是自然遗传学和计算机相互结合、相互渗透而形成的新的计算方法，
从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。许多复杂的问题都可以用简单的位串编码表示，而且通过一些简单的变换规则可以逐步改进这些用二进制编码表示的结构，使之往好的方向进化。遗传算法就是用来完成这一进化过程的，在一定条件下，遗传算法可以在搜索空间中收敛到全局最优解。遗传算法的主要特点：
1)在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数连接性的约束，也没有优化函数导数必须存在的要求。
2)若遗传算法在每一代对群体规模为n的个体进行操作，实际上处理了大约O(n)个模式，具有很高的并行性，因而具有显著的搜索效率。
3)在所求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛到最优解或满意解，因而具有较好的全局最优解求解能力。
4)对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其他问题，或者加入特定问题的领域知识，或者与己有算法相结合，能够较好地解决一类复杂问题，因而具有较好的普遍适用性和易扩充性。
5)遗传算法的基本思想简单、运行方式和实现步骤规范，便于具体使用。由于遗传算法的上述特点，遗传算法己成为计算机技术中有重大影响的关键技术之一，成为一个多学科、多领域的重要研究方向。
2.3.1遗传算法的结构
1)染色体的编码与译码
许多应用问题结构很复杂，但可以化为简单的位串形式编码表示，我们将问题结构变换为位串形式编码表示的过程叫编码：而相反将位串形式编码表示变换为原问题结构的过程叫译码。位串形式的编码表示叫染色体，也叫个体。编码方法除决定了个体的染色体排列形式之外，还决定了个体从搜索空间的基因型变换到解空间的解fF-q.方法。编码方法也影响到交叉、变异等遗传操作的运算方法。因此编码方法在很大程度上决定了种群的遗传进化运算及运算效率。目前还没有一个严密、完整的编码理论及评价准则。一般地遵循两个原则：一是有意义积木块原则，即应使用与求问题相关的、低阶的、长度短的模式编码方案;二方是案最。小字符集原则，即应使用能自然表示或描述问题的最小编码字符集的编码传统的二进制编码是一种常用的编码方案，它使用的编码符号集是〔0,I)，构成的个体基因型是二进制编码的符号串，其串长与问题的求解精度有关。从理论上说，二进制编码最小字符集编码规则，而且编、解码简单易行、交叉变异操作便于实现、也便于利用定理对算法进行理论分析。还可利用Gray码、浮点数编码、符号编码、多参数级联编码、多参数交叉编码等其它编码方法。
2)适应度函数
在遗传算法中，模拟自然选择的过程是通过对个体适应度的评价来实现的。基本遗传算法按与个体适应度成正比的概率来决定当前群体中的每个个体是否能够遗传到下一代群体中。为正确计算这个概率，要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定处理负数目标函数值的方法。适应度函数要结合求解问题的要求而定。
3)遗传操作
《计算机科学与技术前沿》 课程论文 大数据背景下数据挖掘技术的应用 2016年1月7日 题目 学院 学号 姓名 指导老师 日期
大数据背景下数据挖掘技术的应用 摘要 当今社会是一个信息化社会的时代，同时又是一个大数据时代。随着互联网、物联网、云计算和人工智能等信息技术和计算机产业的不断发展和进步，使得数据的处理成为一个亟待解决的问题。因此在大数据的背景下,如何高效地从大量包含有用数据的库获得有用信息已成为企业和科研工作重点关注的点，而这一工作涉及的关键技术就是数据挖掘技术。总得说，数据处理的需要既给数据挖掘技术带来了机遇，于此同时带来了一系列的挑战。 本文分别从企业、图书管理和情报学领域三个方面阐述数据挖掘技术的应用，同时对它的发展现状、存在的问题和未来的发展趋势进行了一些阐述，从而加深了对数据挖掘技术的理解，以便更好地了解数据挖掘在各个领域的应用，最后对数据挖掘技术的应用进行一个整体的总结。 【关键字】：大数据；数据挖掘；数据挖掘的应用
Application of data mining technology in the context of data Abstract Today is the age of information society,but it is also an age of big data．With development and progress of information technology and the computer industry which include the Internet, the Internet of things, cloud computing and artificial intelligence, data processing has become an urgent problem．Therefore,in the context of big data,how to get useful information from a large library of useful data have become focuses of enterprises and scientific and research work．The work involved is the key technology of data mining．In General spedking, data processing needs for data mining technology, and at the same time poses a series of challenges． The paper aims to account the development present situation,existing problems,and developmenttrend in the future based on companies,library management and the field of information science development,so as to enhance understanding of the data mining technology ,to better understand data mining applications in various fields,and to draw an overall summary of the application of data mining technology． 【Key words】：Large amounts of data；Data mining；Application of data mining
毕业设计 遗传算法的研究及应用 摘要 本文分为三部分：第一部分：遗传算法的概述。主要介绍了遗传算法的基本思想、遗传算法的构成要素、遗传算法的特点、遗传算法的基本模型、遗传算法的应用情况及今后的研究方向等等的内容。第二部分：基于Matlab 7.0下的遗传算法求解函数最值问题。遗传算法作为一种新的优化方法，广泛地用于计算科学、模式识别和智能故障诊断等方面，它适用于解决复杂的非线性和多维空间寻优问题，近年来也得到了较为广阔的应用。本人选择了函数优化这个应用领域，按照遗传算法的步骤，即编码、解码、计算适应度（函数值）、选择复制运算、交叉运算和变异运算，对函数进行求解最值。第三部分：对遗传算法求函数最值问题的改进。这部分主要针对本文第二部分进行改进，通过改变基本遗传算法运行参数值，如改变交叉概率Pc值和变异概率Pm值，从而使最优值更加接近相对标准下函数的最值。 关键词：遗传算法适应度交叉概率变异概率
目录 1 前言 (1) 2 遗传算法概述 (1) 2.1生物进化理论和遗传学的基本知识 (1) 2.2遗传算法的基本思想 (3) 2.3遗传算法的构成要素 (3) 2.3.1 染色体编码方法 (3) 2.3.2 适应度函数 (4) 2.3.3 遗传算子 (4) 2.3.4 基本遗传算法运行参数 (5) 2.4遗传算法的特点 (6) 2.5遗传算法的基本模型 (7) 2.6遗传算法的应用 (8) 2.7遗传算法今后的研究方向 (10) 3 基于MATLAB 7.0下的遗传算法求解函数最值问题 (11) 3.1遗传算法的标准函数 (11) 3.2解题步骤说明 (12) 3.2.1 编码问题 (12) 3.2.2 选择运算 (12) 3.2.3 交叉运算 (13) 3.2.4 变异运算 (13) 3.3运行参数说明 (14) 3.4对遗传算法求得的最值的分析 (14) 3.5运行程序以及对其解释 (14) 3.6从数学的角度求解函数最优值 (18) 3.6.1 自变量x以0.2为步进单位 (18) 3.6.2 自变量x以0.1为步进单位 (19) 3.6.3 自变量x以更精确的数为步进单位 (21)
遗传算法应用的分析与研究 福州八中钱自强 【摘要】 随着科技水平的不断发展，人们在生产生活中遇到的问题也日益复杂，这些问题常常需要在庞大的搜索空间内寻找最优解或近似解，应用传统算法求解已经显得相当困难。而近年来，生物学的进化论被广泛地应用于工程技术、人工智能等领域中，形成的一类有效的随机搜索算法——进化算法，有效的解决了诸多生产生活中的难题而显得越来越流行。 本文的首先将介绍进化算法的原理以及历史使大家对进化算法有一个初步的了解，其次将详细介绍应用遗传算法解题的步骤，并提出有效改进和应用建议。紧接着通过一个NP难题的优化实例让大家对遗传算法有更深刻的了解，最后通过数据分析证明其方法的有效性。 【关键词】 人工智能；进化算法；遗传算法（GA）；多目标最小生成树 目录 一、进化算法理论 1．1进化算法概述－ 2－ 1．2遗传算法介绍－ 2－ 二、遗传算法 2．1遗传算法基本流程－ 3－ 2．2遗传算法中各重要因素分析－ 3－ 2．3重要参数设置－ 6－ 三、遗传算法在多目标最小生成树问题中的应用 3．1多目标最小生成树－ 7－ 3．2应用遗传算法解决多目标最小生成树－ 9－ 3．3测试－11－ 四、结束语－15－ 附录－16－
一. 进化算法理论 1．1进化算法概述 从远古时代单细胞开始，历经环境变迁的磨难，生命经历从低级到高级，从简单到复杂的演化历程。生命不断地繁衍生息，产生出具有思维和智能的高级生命体。人类得到生命的最佳结构与形式，它不仅可以被动地适应环境，更重要的是它能够通过学习，模仿与创造，不断提高自己适应环境的能力。 进化算法就是借鉴生物自然选择和遗传机制的随机搜索算法。进化算法通过模拟“优胜劣汰，适者生存”的规律激励好的结构，通过模拟孟德尔的遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。作为随机优化与搜索算法，进化算法具有如下特点：进化算法不是盲目式的乱搜索，也不是穷举式的全面搜索，它根据个体生存环境即目标函数来进行有指导的搜索。进化算法只需利用目标的取值信息而不需要其他信息，因而适用于大规模、高度非线性的不连续、多峰函数的优化，具有很强的通用性；算法的操作对象是一组个体，而非单个个体，具有多条搜索轨迹。 1．2遗传算法 遗传算法（Genetic Algorithm）是进化算法的一个重要分支。它由John Holland提出，最初用于研究自然系统的适应过程和设计具有自适应性能的软件。近来，遗传算法作为问题求解和最优化的有效工具，已被非常成功地应用与解决许多最优化问题并越来越流行。 遗传算法的主要特点是群体搜索策略和群体中个体之间的信息互换,它实际上是模拟由个体组成的群体的整体学习过程,其中每个个体表示问题搜索空间中的一个解点.遗传算法从任一初始的群体出发,通过随机选择，交叉和变异等遗传操作,使群体一代代地进化到搜索空间中越来越好的区域,直至抵达最优解点. 遗传算法和其它的搜索方法相比,其优越性主要表现在以下几个方面：首先,遗传算法在搜索过程中不易陷入局部最优,即使在所定义的适应度函数非连续.不规则也能以极大的概率找到全局最优解,其次,由于遗传算法固有的并行性,使得它非常适合于大规模并行分布处理,此外,遗传算法易于和别的技术(如神经网络.模糊推理.混沌行为和人工生命等)相结合,形成性能更优的问题求解方法.
本文来源于网络 综述数据挖掘技术在物流领域中的应用 2007级物流工程一班 200730611470欧阳家文 摘要：本文主要内容是综述数据挖掘技术在物流领域中的应用。文章首先对数据挖掘技术做一个简单的介绍，接着介绍数据挖掘在物流业中的应用过程，最后介绍物流中关于数据挖掘应用的管理问题。 关键词：数据挖掘数据仓库物流领域应用 1，应用背景 物流是现代商品流通系统的重要组成部分，物流业的发展程度，反映了一个国家和地区经济的综合配套能力与社会化服务程度，是其经济发展水平的集中体现。作为继劳动力和自然资源之后的“第三利润源泉”，现代物流产业的发展已经成为拉动我国经济发展的新增长点。与此同时，现代物流系统是一个庞大复杂的系统，特别是全程物流、包括运输、仓储，配送、搬运、包装和再加工等环节，每个环节的信息量非常大，使企业很难对这些数据进行有条理，有选择性的分析。如何将企业中积累的大量的原始客户数据转化成有用的信息为决策者提供决策支持，已经成为数据库研究中一个很有应用价值的新领域，数据挖掘技术由此应运而生。数据挖掘技术能帮助企业在物流信息管理系统中，及时、准确地搜集数据并对其进行分析。对客户的行为及市场趋势进行有效的分析，了解不同客户的爱好，从而为客户提供有针对性的产品和服务。提升企业的客户满意度，对公司的长远发展有着极大的促进作用。 2，什么是数据挖掘技术？ 数据挖掘技术是利用人工智能（AI）和统计分析等技术，在海量数据中发现模型和数据间的关系，自动地帮助决策者分析历史数据和当前的数据，并做出归纳性的推理， 从中挖掘出潜在的模式，从而预测客户的行为，帮助企业的决策者调整市场策略、减少风险、做出正确的决策。结合现代物流的特质和外部环境考虑，数据挖掘技术能够提供 越来越强大的支持功能。从商业的角度考虑，由于在商业行为中存在着大量的信息，而这些信息并不是都是所需要的，也就是，它是有噪声的，模糊的，随机的数据，必须通过某种技术对这些隐含在其中的，人们不知道的，但又是潜在有用的信息和只是的过程。只有通过类似于数据挖掘的这样的技术对商业数据库进行抽取，转换，分析等操作，才可以让这些埋藏着的金子发光发亮。 3，数据挖掘技术的特点 数据挖掘技术具有以下特点: ( 1) 处理的数据规模十分庞大, 达到GB、TB 数据级, 甚至更大。 ( 2) 查询一般是决策制定者提出的即时随机查询, 往往不能形成精确的查询要求, 需要靠系统本身寻找其可能感兴趣的东西。( 3) 在一些应用中( 如商业投资等) , 由于数据变化迅速,因此要求数据挖掘能快速做出相应反应以随时提供决策支持。 ( 4) 数据挖掘中, 规则的发现基于统计规律。因此, 所发现的规则不必适用于所有数据, 而是当达到某一临界值即认为有效。因此, 利用数据挖掘技术可能会发现大量的 规则。 ( 5) 数据挖掘所发现的规则是动态的, 它只找到了当前状态的数据库具有的规则, 随着不断地向数据库中加入新数据,需要随时对其进行更新。
数据挖掘在大数据时代下的应用 【摘要】数据挖掘一直是各个行业的关注的重点。 近几年，数据挖掘伴随着大数据的火热开始迎来更大的机遇。本文介绍了数据挖掘相关的概念，一些常用的数据挖掘的分析方法，最后介绍了数据挖掘技术几个常见的应用领域。 【关键词】数据挖掘分析方法应用 一、基本概念介绍 1、大数据。2011 年5 月，麦肯锡全球研究院在《大数据：创新、竞争和生产力的下一个新领域》中指出，大数据是一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具能力范围的数据集合，具有海量的数据规模、快速的数据流转、多样的数据类型和价值密度低四大特征。数据已经渗透到每一个行业和业务职能领域，逐渐成为重要的生产要素；而人们对于大数据的运用预示着新一波生产率增长和消费者盈余浪潮的到来。据估计，在未来，数据将至少保持每年50%的增长速度。 2、数据挖掘。数据挖掘是一门新兴的学科，它诞生于20 世纪80 年代，主要面向商业应用的人工智能研究领域. 从技术角度看，数据挖掘就是从大量的、复杂的、不规则的、随机的、模糊的数据中获取隐含的、人们事先没有发觉的、
有潜在价值的信息和知识的过程.从商业角度来说，数据挖掘就是从庞大的数据库中抽取、转换、分析一些潜在规律和价值，从中获取辅助商业决策的关键信息和有用知识。 二、数据挖掘的基本分析方法 分析方法是数据挖掘的核心工作，通过科学可靠的算法才能实现数据的挖掘，找出数据中潜在的规律。通过不同的分析方法，将解决不同类型的问题，在现实中针对不同的分析目标，找出相对应的方法。目前常用的分析方法主要有聚类分析、分类和预测、关联分析等。 1、聚类分析。聚类分析就是将物理或抽象对象的集合进行分组，然后组成为由类似或相似的对象组成的多个分类的分析过程，其目的就是通过相似的方法来收集数据分类。它是一种无先前知识，无监督的学习过程，从数据对象中找出有意义的数据，然后将其划分在一个未知的类。这不同于分类，因为它无法获知对象的属性。“物以类聚，人以群分”，通过聚类来分析事物之间类聚的潜在规律。聚类分析广泛运用于心理学、统计学、医学、生物学、市场销售、数据识别、机器智能学习等领域。聚类分析根据隶属度的取值范??可分为硬聚类和模糊聚类两种方法。硬聚类就是将对象划分到距离最近聚类的类，非此即彼，也就是说属于一类，就必然不属于另一类。模糊聚类就是根据隶属度的取值范围的大小差异来划分类。一个样本可能属于多个类。常见的聚类算法主
龙源期刊网 https://www.doczj.com/doc/8a18842424.html, 遗传算法的研究及应用 作者：彭志勇邓世权 来源：《计算机光盘软件与应用》2013年第07期 摘要：遗传算法是一种典型的优化搜索算法，它的构造是使用人工的方式，并对生物遗传学和自然选择机理来进行模仿，是一种典型的数学仿真，而这种数学仿真是通过生物进化的过程来进行的，它是进化计算的一种非常重要的形式，它可以应用与生活中的很多领域。 关键词：遗传算法；函数优化；生产调度；自动控制 中图分类号：TP183文献标识码：A文章编号：1007-9599 (2013) 07-0000-02 遗传算法是一种典型的优化搜索算法，它的构造是使用人工的方式，并对生物遗传学和自然选择机理来进行模仿，是一种典型的数学仿真，而这种数学仿真是通过生物进化的过程来进行的，它是进化计算的一种非常重要的形式。与传统的数学模型进行比较，遗传算法有很多的不同的地方，因为它能够解决很多复杂的问题，而传统的数学模型却没办法做到。 1遗传算法的理论研究 1.1遗传算法的由来。美国密西根大学的霍兰德（Holland）将该算法应用于自然和人工系统的自适应行为的研究之中，并且在二十世纪七十年代中期，出版他的第一部著作《自然与人工系统中的适应》。随后，Holland与他的学生们将该算法进行了大力的推广，并把它应用到优化及机器学习等问题之中，而且正式定名为遗传算法。 1.2遗传算法的发展。遗传算法的兴起于20世纪70年代，而到了20世纪80年代的时 候，它正好属于一个发展中的过程，到了20世纪90年代时，它已经发展到了颠疯时刻。为一种实用性较强而又很有效率的优化技术，遗传算法的发展还是非常迅速，在国内外已经造成了非常大的影响力。 1.3遗传算法的基本思想。遗传算法是从一个种群（population）开始的，而这个种群代表问题可能潜在解集的，一个种群是由经过基因（gene）编码（coding）的一定数目的个体（individual）所组成。染色体是遗传物质的主要载体，它是由多个基因的集合，其内部表现是某种基因组合决定的。自从初始种群产生以后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小来挑选（selection）个体，遗传算法是采纳了选择、交叉、变异、迁移、局域 与邻域等自然进化模型，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），从而产生出代表新的解集的种群。 遗传算法和传统搜索算法有很大的不同，它是通过一组随机产生的初始解开始搜索过程。染色体是类似于二进制串的一串符号，对于染色体的测量，我们通常是用适应度来它的好坏
遗传算法的基本理论 一、起源： 早在20世纪50年代和60年代，就有少数人几个计算机科学家独立地进行了所谓的“人工进化系统”研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏形，如大多数系统都遵循“适者生存”的仿自然法则，有些系统采用了基于群体（population）的设计方案，并且加入了自然选择与变异操作，还有一些系统对生物染色体编码进行了抽象处理，应用二进制编码。由于缺乏一种通用的编码方案，人们只能依赖变异而非交叉来产生新的基因结构，早期的算法收敛甚微。20世纪60年代中期，美国Michigan大学的John Holland在A.S.Fraser和H.J.Bremermann等人工作的基础上提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉（即杂交）操作。并且强调将交叉作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究中，并于1975年出版了其开创性著作“Adaption in Natural and Artificial System”。以后，Holland等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操作作为其广泛、成功地应用奠定了基础。Holland早期有关遗传算法的许多概念一直沿用至今，可见Holland对遗传算法的贡献之大。他认为遗传算法本质上是适应算法，应用最多的是系统最优化的研究。 二、发展： 年份贡献者内容 1962Holland程序漫游元胞计算机自适应系统框架 1968Holland模式定理的建立 1971Hollstein具有交配和选择规则的二维函数优化 1972Bosworth、Foo、Zeigler提出具有复杂变异、类似于遗传算法的基因操作1972Frantz位置非线性和倒位操作研究 1973Holland遗传算法中试验的最优配置和双臂强盗问题 1973Martin类似遗传真法的概率算法理论 1975De Jong用于5个测试函数的研究基本遗传算法基准参数 1975Holland 出版了开创性著作《Adaptation in Natural and Artificial System》 1981Bethke应用Walsh函数分析模式 1981Brindle研究遗传算法中的选择和支配问题 1983Pettit、Swigger遗传算法应用于非稳定问题的粗略研究1983Wetzel用遗传算法解决旅行商问题(TSP) 1984Mauldin基本遗传算法小用启发知识维持遗传多样性1985Baker试验基于排序的选择方法 1985Booker建议采用部分匹配计分、分享操作和交配限制法1985Goldberg、Lingle TSP问题个采用部分匹配交叉 1985Grefenstette、Fitzpattrick对含噪声的函数进行测试 1985Schaffer多种群遗传算法解决多目标优化问题1986Goldberg最优种群大小估计 1986Grefenstette元级遗传算法控制的遗传算法 1987Baker选择中随机误差的减少方法 1987Goldberg复制和交叉时最小欺骗问题(MDP) 1987Goldberg、Richardson借助分享函数的小生境和物种归纳法
遗传算法理论及其应用研究进展 摘要：本文阐述了遗传算法的基本原理以及求解问题的一般过程，讨论了遗传算 法存在的不足和针对其不足采取的弥补措施，概述了遗传算法常见的应用领域。最后，讨论了遗传算法的未来研究方向。 关键词：遗传算法；算子；优化 Development on Genetic Algorithm Theory And Its Application Liu Jun (201320620181) (College of Mecha ni cal Engin eeri ng of Un iversity of South Chi na Hen gya ng Hunan 421001) Abstract: This paper stated the basic theory of Genetic Algorithm (GA) and the process of sol ving the problem, discussed the weak ness of gen etic algorithm and the impro ving measures about gen etic algorithm. Then summarized the com mon applicati on fields of gen etic algorithm. Fin ally, poin ted out the gen etic algorithm ' research direct ions in the future. Keywords: gen etic algorithm (GA); operator; optimizati on 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。遗传算法是模拟自然界生物进化过程与机制求解极值问题的一类自组织、自适应人工智能技术，其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法，具有坚实的生物学基础；它提供从智 能生成过程观点对生物智能的模拟，具有鲜明的认知学意义；它适合于无表达或有表达的任何类函数，具有可实现的并行计算行为；它能解决任何种类实际问题，具有广泛的应用价值。因此，遗传算法广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科学等领域，适用于解决复杂的非线性和多维
2016年第17期 科技创新科技创新与应用 遗传算法的应用研究 赵夫群 （咸阳师范学院，陕西咸阳712000） 1概述 遗传算法（Genetic Algorithms，GA）一词源于人们对自然进化系统所进行的计算机仿生模拟研究，是以达尔文的“进化论”和孟德尔的“遗传学原理”为基础的，是最早开发出来的模拟遗传系统的算法模型。遗传算法最早是由Fraser提出来的，后来Holland对其进行了推广，故认为遗传算法的奠基人是Holland。 随着遗传算法的不断完善和成熟，其应用范围也在不断扩大，应用领域非常广泛，主要包括工业控制、网络通讯、故障诊断、路径规划、最优控制等。近几年，出现了很多改进的遗传算法，改进方法主要包括：应用不同的交叉和变异算子；引入特殊算子；改进选择和复制方法等。但是，万变不离其宗，都是基于自然界生物进化，提出的这些改进方法。 2遗传算法的原理 遗传算法是从某一个初始种群开始，首先计算个体的适应度，然后通过选择、交叉、变异等基本操作，产生新一代的种群，重复这个过程，直到得到满足条件的种群或达到迭代次数后终止。通过这个过程，后代种群会更加适应环境，而末代种群中的最优个体，在经过解码之后，就可以作为问题的近似最优解了。 2.1遗传算法的四个组成部分 遗传算法主要由四个部分组成[1]：参数编码和初始群体、适应度函数、遗传操作和控制参数。编码方法中，最常用的是二进制编码，该方法操作简单、便于用模式定理分析。适应度函数是由目标函数变换而成的，主要用于评价个体适应环境的能力，是选择操作的依据。遗传操作主要包括了选择、交叉、变异等三种基本操作。控制参数主要有：串长Z，群体大小size，交叉概率Pc，变异概率Pm等。目前对遗传算法的研究主要集中在参数的调整中，很多文献建议的参数取值范围一般是：size取20~200之间，Pc取0.5~1.0之间，Pm取0~0.05之间。 2.2遗传算法的基本操作步骤 遗传算法的基本操作步骤为： （1）首先，对种群进行初始化；（2）对种群里的每个个体计算其适应度值；（3）根据（2）计算的适应度，按照规则，选择进入下一代的个体；（4）根据交叉概率Pc，进行交叉操作；（5）以Pm为概率，进行变异操作；（6）判断是否满足停止条件，若没有，则转第（2）步，否则进入（7）；（7）得到适应度值最优的染色体，并将其作为问题的满意解或最优解输出。 3遗传算法的应用 遗传算法的应用领域非常广泛，下面主要就遗传算法在优化问题、生产调度、自动控制、机器学习、图像处理、人工生命和数据挖掘等方面的应用进行介绍。 3.1优化问题 优化问题包括函数优化和组合优化两种。很多情况下，组合优化的搜索空间受问题规模的制约，因此很难寻找满意解。但是，遗传算法对于组合优化中的NP完全问题非常有效。朱莹等[2]提出了一种结合启发式算法和遗传算法的混合遗传算法来解决杂货船装载的优化问题中。潘欣等[3]在化工多目标优化问题中应用了并行遗传算法，实验结果表明该方法效果良好。王大东等[4]将遗传算法应用到了清运车辆路径的优化问题求解中，而且仿真结果表明算法可行有效。 3.2生产调度 在复杂生产调度方面，遗传算法也发挥了很大的作用。韦勇福等[5]将遗传算法应用到了车间生产调度系统的开发中，并建立了最小化完工时间目标模型，成功开发了车间生产调度系统模块，并用实例和仿真验证了该方法的可行性。张美凤等[6]将遗传算法和模拟退火算法相结合，提出了解决车间调度问题的混合遗传算法，并给出了一种编码方法以及建立了相应的解码规则。 3.3自动控制 在自动控制领域中，遗传算法主要用于求解的大多也是与优化相关的问题。其应用主要分为为两类，即离线设计分析和在线自适应调节。GA可为传统的综合设计方法提供优化参数。 3.4机器学习 目前，遗传算法已经在机器学习领域得到了较为广泛的应用。邢晓敏等[7]提出了将遗传算子与Michigan方法和基于Pitt法的两个机器学习方法相结合的机器学习方法。蒋培等[8]提出了一种基于共同进化遗传算法的机器学习方法，该方法克服了学习系统过分依赖于问题的背景知识的缺陷，使得学习者逐步探索新的知识。 3.5图像处理 图像处理是一个重要的研究领域。在图像处理过程中产生的误差会影响图像的效果，因此我们要尽可能地减小误差。目前，遗传算法已经在图像增强、图像恢复、图像重建、图像分形压缩、图像分割、图像匹配等方面应用广泛，详见参考文献[9]。 4结束语 遗传算法作为一种模拟自然演化的学习过程，原理简单，应用广泛，已经在许多领域解决了很多问题。但是，它在数学基础方面相对不够完善，还有待进一步研究和探讨。目前，针对遗传算法的众多缺点，也相继出现了许多改进的算法，并取得了一定的成果。可以预期，未来伴随着生物技术和计算机技术的进一步发展，遗传算法会在操作技术等方面更加有效，其发展前景一片光明。 参考文献 [1]周明，孙树栋.遗传算法原理及应用[M].国防工业出版社，1999，6. [2]朱莹，向先波，杨运桃.基于混合遗传算法的杂货船装载优化问题[J].中国船舰研究，2015：10（6）：126-132. [3]潘欣，等.种群分布式并行遗传算法解化工多目标优化问题[J].化工进展，2015：34（5）：1236-1240. [4]王大东，刘竞遥，王洪军.遗传算法求解清运车辆路径优化问题[J].吉林师范大学学报（自然科学版），2015（3）：132-134. [5]韦勇福，曾盛绰.基于遗传算法的车间生产调度系统研究[J].装备制造技术，2014（11）：205-207. [6]黄巍，张美凤.基于混合遗传算法的车间生产调度问题研究[J].计算机仿真，2009，26（10）：307-310. [7]邢晓敏.基于遗传算法的机器学习方法赋值理论研究[J].软件导刊[J].2009，8（11）：80-81. [8]蒋培.基于共同进化遗传算法的机器学习[J].湖南师范大学自然科学学报，2004，27（3）：33-38. [9]田莹，苑玮琦.遗传算法在图像处理中的应用[J].中国图象图形学报，2007，12（3）：389-396. [10]周剑利，马壮，陈贵清.基于遗传算法的人工生命演示系统的研究与实现[J].制造业自动化，2009，31（9）：38-40. [11]刘晓莉，戎海武.基于遗传算法与神经网络混合算法的数据挖掘技术综述[J].软件导刊，2013，12（12）：129-130. 作者简介：赵夫群（1982，8-），女，汉族，籍贯：山东临沂，咸阳师范学院讲师，西北大学在读博士，工作单位：咸阳师范学院教育科学学院，研究方向：三维模型安全技术。 摘要：遗传算法是一种非常重要的搜索算法，特别是在解决优化问题上，效果非常好。文章首先介绍了遗传算法的四个组成部分，以及算法的基本操作步骤，接着探讨了遗传算法的几个主要应用领域，包括优化、生产调度、机器学习、图像处理、人工生命和数据挖掘等。目前遗传算法以及在很多方面的应用中取得了较大的成功，但是它在数学基础方面相对还不够完善，因而需要进一步研究和完善。 关键词：遗传算法；优化问题；数据挖掘 67 --
综述数据挖掘技术在物流领域中的应用 2007级物流工程一班 200730611470欧阳家文 摘要：本文主要内容是综述数据挖掘技术在物流领域中的应用。文章首先对数据挖掘技术做一个简单的介绍，接着介绍数据挖掘在物流业中的应用过程，最后介绍物流中关于数据挖掘应用的管理问题。 关键词：数据挖掘数据仓库物流领域应用 1，应用背景 物流是现代商品流通系统的重要组成部分，物流业的发展程度，反映了一个国家和地区经济的综合配套能力与社会化服务程度，是其经济发展水平的集中体现。作为继劳动力和自然资源之后的“第三利润源泉”，现代物流产业的发展已经成为拉动我国经济发展的新增长点。与此同时，现代物流系统是一个庞大复杂的系统，特别是全程物流、包括运输、仓储，配送、搬运、包装和再加工等环节，每个环节的信息量非常大，使企业很难对这些数据进行有条理，有选择性的分析。如何将企业中积累的大量的原始客户数据转化成有用的信息为决策者提供决策支持，已经成为数据库研究中一个很有应用价值的新领域，数据挖掘技术由此应运而生。数据挖掘技术能帮助企业在物流信息管理系统中，及时、准确地搜集数据并对其进行分析。对客户的行为及市场趋势进行有效的分析，了解不同客户的爱好，从而为客户提供有针对性的产品和服务。提升企业的客户满意度，对公司的长远发展有着极大的促进作用。 2，什么是数据挖掘技术？ 数据挖掘技术是利用人工智能（AI）和统计分析等技术，在海量数据中发现模型和数据间的关系，自动地帮助决策者分析历史数据和当前的数据，并做出归纳性的推理，从中挖掘出潜在的模式，从而预测客户的行为，帮助企业的决策者调整市场策略、减少风险、做出正确的决策。结合现代物流的特质和外部环境考虑，数据挖掘技术能够提供越来越强大的支持功能。从商业的角度考虑，由于在商业行为中存在着大量的信息，而这些信息并不是都是所需要的，也就是，它是有噪声的，模糊的，随机的数据，必须通过某种技术对这些隐含在其中的，人们不知道的，但又是潜在有用的信息和只是的过程。只有通过类似于数据挖掘的这样的技术对商业数据库进行抽取，转换，分析等操作，才可以让这些埋藏着的金子发光发亮。 3，数据挖掘技术的特点 数据挖掘技术具有以下特点: ( 1) 处理的数据规模十分庞大, 达到GB、TB 数据级, 甚至更大。 ( 2) 查询一般是决策制定者提出的即时随 机查询, 往往不能形成精确的查询要求, 需要靠系统本身寻找其可能感兴趣的东西。( 3) 在一些应用中( 如商业投资等) , 由 于数据变化迅速,因此要求数据挖掘能快速 做出相应反应以随时提供决策支持。 ( 4) 数据挖掘中, 规则的发现基于统计规律。因此, 所发现的规则不必适用于所有数据, 而是当达到某一临界值即认为有效。因此, 利用数据挖掘技术可能会发现大量的 规则。 ( 5) 数据挖掘所发现的规则是动态的, 它 只找到了当前状态的数据库具有的规则, 随着不断地向数据库中加入新数据,需要随 时对其进行更新。 4，数据挖掘的一般过程 数据挖掘过程可以大体分为四个步骤：数据准备，数据挖掘，结果的解释和评价，用户界面。如图1：
遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机
基本遗传算法及应用举例 遗传算法(Genetic Algorithms)是一种借鉴生物界自然选择和自然遗传机制的随机、高度并行、自适应搜索算法。遗传算法是多学科相互结合与渗透的产物。目前它已发展成一种自组织、自适应的多学科技术。 针对各种不同类型的问题，借鉴自然界中生物遗传与进化的机理，学者们设计了不同的编码方法来表示问题的可行解，开发出了许多不同环境下的生物遗传特征。这样由不同的编码方法和不同的遗传操作方法就构成了各种不同的遗传算法。但这些遗传算法有共同的特点，即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿来完成对最优解的自适应搜索过程。基于此共同点，人们总结出了最基本的遗传算法——基本遗传算法。基本遗传算法只使用选择、交叉、变异三种基本遗传操作。遗传操作的过程也比较简单、容易理解。同时，基本遗传算法也是其他一些遗传算法的基础与雏形。 1．1．1 编码方法 用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。 编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L 称为染色体的长度或称为符号串的长度。一般染色体的长度L 为一固定的数，如 X=1010100 表示一个个体，该个体的染色体长度L=20。 二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[a ，b]，我们用长度为L 的二进制编码符号串来表示该参数，总共能产生L 2种不同的编码，若参数与编码的对应关系为 00000000000……00000000=0 →a 00000000000……00000001=1 →a+δ ? ? ? ……=L 2-1→b 则二进制编码的编码精度1 2--= L a b δ 假设某一个个体的编码是kl k k k a a a x 21=，则对应的解码公式为 )2(121 ∑=---+=L j j L kj L k a a b a x 例如，对于x ∈[0,1023],若用长度为10的二进制编码来表示该参数的话，则下述符号串：
基于数据挖掘的遗传算法 xxx 摘要:本文定义了遗传算法概念和理论的来源，介绍遗传算法的研究方向和应用领域，解释了遗传算法的相关概念、编码规则、三个主要算子和适应度函数，描述遗传算法计算过程和参数的选择的准则，并且在给出的遗传算法的基础上结合实际应用加以说明。 关键词：数据挖掘遗传算法 Genetic Algorithm Based on Data Mining xxx Abstract：This paper defines the concepts and theories of genetic algorithm source, Introducing genetic algorithm research directions and application areas, explaining the concepts of genetic algorithms, coding rules, the three main operator and fitness function，describing genetic algorithm parameter selection process and criteria，in addition in the given combination of genetic algorithm based on the practical application. Key words: Data Mining genetic algorithm 前言 遗传算法(genetic algorithm，GAs)试图计算模仿自然选择的过程，并将它们运用于解决商业和研究问题。遗传算法于20世界六七十年代由John Holland[1]发展而成。它提供了一个用于研究一些生物因素相互作用的框架，如配偶的选择、繁殖、物种突变和遗传信息的交叉。在自然界中，特定环境限制和压力迫使不同物种竞争以产生最适应于生存的后代。在遗传算法的世界里，会比较各种候选解的适合度，最适合的解被进一步改进以产生更加优化的解。 遗传算法借助了大量的基因术语。遗传算法的基本思想基于达尔文的进化论和孟德尔的遗传学说，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。生物在自然界的生存繁殖，显示对其自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机制研究和行为模拟。通过仿效生物的进化与遗传，根据“生存竞争”和“优胜劣汰”的原则，借助选择、交叉、变异等操作，使所要解决的问题从随机初始解一步步逼近最优解。现在已经广泛的应用于计算机科学、人工智能、信息技术及工程实践。[2]在工业、经济管理、交通运输、工业设计等不同领域，成功解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。遗传算法作为一类自组织于自适应的人工智能技术，尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。 1.遗传算法的应用领域和研 究方向 1.1遗传算法的特点 遗传算法作为一种新型、模拟生物进化过程的随机化搜索方法，在各类结 构对象的优化过程中显示出比传统优 化方法更为独特的优势和良好的性能。 它利用其生物进化和遗传的思想，所以 它有许多传统算法不具有的特点[3]： ※搜索过程不直接作用在变量上，而是 作用于由参数集进行了编码的个体 上。此编码操作使遗传算法可以直接 对结构对象进行操作。 ※搜索过程是从一组解迭代到另一组 解，采用同时处理群体中多个个体的 方法，降低了陷入局部最优解的可能 性，易于并行化。