基于遗传算法的大数据分析技术研究

基于遗传算法的大数据分析技术研究

南钰 冯明 杨鹏 秦泽华 王宏研

国网河南省电力公司开封供电公司 河南省开封市 475000

摘 要：本文对遗传算法在数据挖掘中的应用进行了广泛的研究，阐明了数据挖掘的定义和常用技术，对遗传算法在数据挖掘领域中实现的原理和目前应用进行了详细阐述，并讨论了遗传算法在数据挖掘中所面临的问题。

关键字：遗传算法；数据挖掘

1. 引言

近年来，数据挖掘（Data Mining）已成为企业热门的话题。简单来说数据挖掘就是在庞大的数据库中寻找出有价值的隐藏信息。更广义的说法是：数据挖掘意味着在一些事实或观察数据的集合中寻找模式的决策支持过程。在当今这样一个数据爆炸但知识相对贫乏的时代，如何解决数据过多造成的问题，此时就需要用到数据挖掘技术。然而在各种数据挖掘方法中，都有其自身的局限性。遗传算法是基于生物进化原理的一种自适应优化方法。将数据挖掘技术与遗传算法相结合，可以使其更有效的发挥二者各自的特点，弥补彼此的不足，并把遗传算法运用在数据挖掘系统中能够较好地解决数据挖掘技术中出现的问题。

2. 概述

2．1 数据挖掘的含义

从技术上讲，数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又有潜在有用的信息与知识的过程。这个定义包含了数层含义：数据源必须是真实的、大量的、含噪声的；知识发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问题。这里所指的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。事实上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。它最好能用自然语言表达所发现的结果。

从商业角度讲：数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析以及其他模型化处理，从而提取出辅助商业决策的关键性数据。因此，数据挖掘又可以描述为：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。

2．2 数据挖掘常用的技术方法

1. 统计分析

统计分析方法使利用统计、概率的原理对关系中各属性进行统计分析，从而找出他们之间的关系和规律。

2. 人工神经网络

神经网络是模拟人类的形象直觉思维，在生物神经网络研究的基础上，根据生物神经元和神经网络的特点，通过简化、归纳，提炼总结出来的一类并行处理网络。电脑常识

3. 决策树

决策树利用树型结构来表示决策集合，这些决策集合通过对数据集的分类而产生规则。首先，利用训练集生成一个测试函数，根据不同取值建立树的分支，在每个分支子集中建立下层节点和分支，生成一棵决策树；然后对决策树进行剪枝处理；最后把决策树转换为规则，并且利用这些规则对新事例进行分类。 SAAS

4. 聚类算法

聚类算法是通过对变量的比较，把具有相似性特征的数据归为一类。因此，通过聚类算法以后，数据集就转化为类集。在类集中，同一类数据具有相似的变量值，而不同类数据的变量值不具有相似性。聚类算法主要用于描述和发现数据库中以前未知的数据类别。

5. 可视化技术SOA

可视化技术是通过直观的手段来交互的分析数据关系，采用图形方式将信息模式、数据的关联或趋势呈现给用户。例如，把数据库中的多维数据编程多种图形，揭示数据的状况、内在本质及规律。

6. 遗传算法

遗传算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法。它在形式上是一种迭代方法。从选定的初始解出发，通过不断迭代逐步改进当前解，直至搜索到最优解或满意解。本文就是采用遗传算法在数据挖掘中的应用进行研究分析。

2.3 遗传算法

遗传算法（Genetic Algorithm，缩写为GA）也称为进化算法，从字面上看是继承生物学的，根据达尔文的“自然选择，优胜劣汰”学说，随着外界环境的变化，生物适应环境的特征被子代继承下来，不适应环境的特征被淘汰。从形象上理解生物正不断向最优的方向进化^[1]。当基因从一代传递到下一代时，经过选择、交叉和变异，持续不断的改进群体的适应度。在特定多代之后——典型的是数十或数百代——群体进化接近最优。遗传算法并不总是产生精确的最优解，但是能够非常的接近最优解。在数据挖掘中，精确的方案未必可行，接近最优解仍然可以产生可操作的结果。在计算机科学中主要用于解决最优化问题。

3. 数据挖掘技术中遗传算法的实现

在数据挖掘的处理流程中，遗传算法主要用于对数据的挖掘处理。在整个进化的过程中遗传操作是随机的，但它所呈现出的特性并不是完全随机搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点集。这样一代代地不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。其实现步骤如下所示：

在确定了问题的参数集后，首先要针对数据挖掘面临的问题选择合适的编码策略，必须在目标问题实际表示与遗传算法的染色体之间建立联系，也就是确定编码和解码运算。一般来说参数集及适应函数与实际问题是密切相关的，往往需要用户斟酌。

其次，定义适应函数f(x)。在遗传算法中，问题空间被表示成染色体位串空间，为了执行适者生存的原则，必须对个体位串的适应性进行评价。适应函数就是个体是否适应环境的决定因素。一般来说，好的染色体位串结构具有比较高的适应函数值，也就是说可以获得较高的评价，具有较强的生存能力。由此可见，适应值是群体中个体生存机会选择的惟一标准，所以适应函数的形式直接决定着群体的进化行为。

第三，确定遗传策略，包括选择群体大小，选择、交叉、变异方法，以及确定交叉概率、变异概率等遗传参数。

其中，“选择”有时也称作复制，它是从当前群体中选择适应值高的个体以生成交配池的过程。现在常选取的是精英保留策略。

“交叉”是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下代个体，并生成包含更复杂基因结构的新个体。一般交叉操作分三步完成。

1. 从交配池中随机取出要交配的一对个体。

2. 根据染色体位串长度L，对要交配的一对个体，随机抽取[1，L—1]中一个或多个的整数作为交叉位置。

3. 根据交叉概率实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，从而形成新的一对个体。

“变异”是模拟自然界生物进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。在遗传算法中，变异算子通过按变异概率随机反转某位二进制字符值来实现。

第四，随机给定一组初始解；生成初始化群体。

第五，依据适应函数计算给定群体适应值。

第六，评价这个群体的性能，判断它是否能满足某一指标。若满足，则结束；若不满足，则依据评价结果，从当前群体中选择一定数量的个体作为基因操作的对象。

第七，对所选择的个体依据遗传策略进行基因操作得到一个新的群体。将其返回到第五步继续迭代进行，直到群体进化到最优解为止。

算法流程如图3.1所示。

图3-1 遗传算法流程图

4. 遗传算法在数据挖掘中的研究与应用

遗传算法应用到数据挖掘的时间虽说不是很久，但是由于遗传算法自身的优越性和数据挖掘技术的美好前景，使遗传算法在数据挖掘的实际应用中得到了巨大发展。

4．1 理论研究

当前,研究最为突出的就是将遗传算法与其它算法的结合应用于数据挖掘技术上。这一研究的主要目的是既发挥遗传算法的全局性优点，又能发挥某类特定算法对于数据挖掘问题的有效性的特长，且能快速稳定地搜索到问题的全局最优解。目前，应用于数据挖掘的混合方法主要有：遗传算法与关联规则分析相结结合，遗传算法与BP神经网络，基于遗传算法的分类规则，遗传算法与模糊集理论的结合，基于遗传算法和粗糙集联系度的数据挖掘，遗传算法与聚类算法结合的数据挖掘等。

4．2 应用方面

随着人们对遗传算法在数据挖掘领域研究的深入，遗传算法在数据挖掘领域有了广泛的应用：

1. 教育领域：

在学校教育中，可通过遗传算法与关联规则的结合对学生数据库进行挖掘，例如可以挖掘历年来的学习成绩与科目数据库中的数据，通过分析可能会发现学科之间的关系，从而加强对一些难度较大的学科的研究与教学；把这样的结果用于学生的教育和培养。将会促进学校教育水平的提高。

2. 经济领域

在商业交易中对客户关系进行发现补充，在销售分析、金融信贷风险分析、物流货源分析等挖掘出潜在的商业机会，从而实现商业利益的最大化。

3. 医学领域

利用遗传算法可以对病历数据库进行数据挖掘发现某一类病的发病情况。

4. 工业领域

在工业界，车间调度问题越来越受到人们的关注，从大量的车间作业调度中抽取一些有价值的信息或知识，然后对这些知识应用数据挖掘算法从车间作业调度最优方案(基于遗传算法的求解结果)中抽取调度方案的一些模式知识，然后基于这些模式知识发展一些规则集来支持车间作业调度。

5. 计算机科学领域

遗传算法与聚类、关联规则相结合应用于Web行为的数据挖掘，利用遗传算法找出最佳聚类，避免局部最优，并给出可靠的聚类评估，然后再利用遗传算法与关联规则的结合挖掘出未来将产生的关联规则，并将这些规则可以为基于数据挖掘的智能Web系统提供进一步的知识支持。

5. 结束语

虽然遗传算法不是数据挖掘的核心，但是它能协助数据挖掘进行优化，从而可以更好的进行数据挖掘。这也正是遗传算法有着强有力的优化技术的突出表现。遗传算法在数据挖掘中已经得到了很广泛的应用, 并取得了很好的计算结果。但遗传算法本身也有自身的缺点，例如一般遗传算法缺乏广泛而完整的遗传算法收敛性理论,有时产生早熟现象和欺骗问题, 搜索效率及其时间复杂性问题等。随着人们对遗传算法在数据挖掘中研究与应用的加深，遗传算法在数据挖掘中将会有更加广泛的应用。

5