基于改进型数据挖掘模型的研究

奚中阳

摘 要：近年来在人工智能领域极具突出研究价值的是数据挖掘技术。数据挖掘技术就是从大量的无规则的数据中提取出潜在的人们感兴趣的知识。提取出的知识表现形式可以为概念、规则、规律、模式等等。目前数据挖掘算法有许多种，如经典的Apriori算法，FP-Tree等。而遗传算法自1975年由J.Holland提出以来，因其结构简单，采用模拟自然选择，适用于解决非线性问题，对于解决存在大量的无序的数据中的挖掘，遗传算法有独特的优势。本文基于遗传算法的优势，采用遗传算法进行关联规则的挖掘。

关键词：数据挖掘；关联规则； 遗传算法

1 相关概念

1.1 关联规则

关联规则是用来发现一组数据中同时发生的概率。假定是数据项的集合。给定一个交易数据库D，定义支持度（support）为D中事务同时包含事件A与事件B的百分比；定义置信度（confidence）为D中事务在已经包含事件A的情况下，包含Y的百分比，即条件概率。如果满足设定的最小支持度阈值和最小置信度阈值，则认为所得到的规则是潜在有用的。

1.2 关联规则挖掘的过程

关联规则的挖掘可以分为两部分：

（1）找出所有频繁项集：即找出所有支持度大于设定的最小支持度阈值的项目集。

（2）由频繁项集产生强关联规则；即通过第一步中得到的频繁项集中选取置信度大于给定的最小置信度阈值。

1.3 遗传算法

遗传算法是一种模拟生物优胜劣汰自然选择与遗传机理的随机搜索算法。相比于传统的搜索算法，遗传算法随机产生一组称为种群的初始解。种群中的每个个体都是问题中的一个解，称为染色体。染色体通过不断的选择，交叉，变异等操作产生优良个体。这样，经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。遗传算法的结构如图1所示：

图1

3 算法实现

3.1 编码策略

对于参数比较多的问题，我们可以采用多参数编码技术，其基本思路：把每个参数先进行编码得到子串，再把这些子串连成一个完整的染色体，一个染色体代表一个关联规则，作为数据挖掘的对象。 在此采用了二进制编码技术。

3.2 适应度函数的设计

由于遗传算法的针对性很强，每一个遗传算法的实现都是基于某一个具体的问题，在遗传算法总的框架不变的情况下，针对这个具体的问题采用构造一个“好”的适应度函数至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。

对于关联规则挖掘，首先要形成频繁项集，衡量的标准只有支持度。支持度是覆盖项集的事务的数目在事务数据库所有事务数目中所占的比例。

一个项集是否频繁项集的唯一标准是：项集的支持度要大于用户所给的最小支持度阈值（MinSupp）。因此适应度函数中最好包含项集的适应度和MinSupp，最好通过函数计算能分辨出支持度和MinSupp的大小关系。因此拟定群体中个体适应度函数为：

Fitness（X） = X代表项集的支持度/最小支持度阈值MinSupp。

3.3 选择算子、交叉算子、变异算子的确定

选择算子最常用的是基于适应度比例的选择，如赌轮选择。而根据赌轮选择的特点，个体被选中的概率与其适应度占群体适应度总和的比例成正比，那么就有可能出现这样一种情况：初始群体中少数适应度较大的超级个体，在下一代中会得到较高的复制概率，它们在随后进化的少数几代内将会统治整个群体。赌轮选择在进化开始时的选择压力过大是导致遗传算法早熟的一个主要原因。另外，当进化终了时，同一群体中不同个体之间的适应度差异变得很小，其选择概率相近，使得选择趋于随机选择，可能使遗传算法失去进化能力。具体对于关联规则的挖掘，两个适应度很高的个体，未必会繁殖出一个高适应度的个体。所以，虽然赌轮盘选择是遗传算法中非常常用的一种选择算子，但并不适合于本文的问题求解。

因此拟采用的选择操作是将适应度值大于1的规则都遗传下来，也就是说，只要满足要求的规则都将被保留下来。这与一般的选择方法有所区别，这里并没有使用选择概率，而是只要超过用户规定阈值的规则都会被选择。

交叉算子及变异算子由于采用动态参数时导致计算量大，故采用经验值，从而减少算法运行时间。

4 应用实例

实验数据来源于农业气象数据库，该数据库信息如表1所示。

对于表 1 中的几个属性，季节分别用 1，2，3，4 表示；平均气温这一属性，分别用 1～8 对应 8 个不同的等级（酷寒，严寒，寒冷，凉，凉爽，温暖，炎热，高温），其中每个等级均在一定的温度范围内；降雨量分别用 1～3 对应 3 个不同的等级（小，中，大）；日照分别用 1～3 对应 3 个不同的等级（短，中，长）；而灾害分别用 1～5 对应 5 种不同的自然灾害（正常，干旱，涝，重涝和冷冻）。转换后并利用前面提出的算法，在农业气象数据库的基础上对气候与自然灾害间的关系进行了挖掘，挖掘产生的部分规则如下：

<0031>∥><4>（21% support，100% confidence）

即：<降雨量：大，日照：短>∥> <自然灾害：重涝>，其含义为：降雨量大且日照时间短的地区中有21%地区容易发生涝灾。

<071>∥><02>（18% support，90% confidence）

即：<温度：炎热，降雨量：小>∥> <自然灾害：干旱>，其含义为：天气炎热并且降雨量非常少的地区中有 18%容易发生干旱现象。

<140>∥><05>（30% support，90% confidence）

即：<季节：冬季，温度：凉>∥><自然灾害：冷冻>，其含义为：在冬季并且地面温度在 0 度以下的地区中有 30%容易发生冷冻灾害。通过对农业气象数据库关联规则的挖掘，可以发现大量有价值的信息，将其应用于农业气象灾害的分析中，从而能够提前防灾减灾，加大物资投入力度，以达到高产高效益的目的。

5 结束语

本文对关联规则的挖掘算法进行研究，提出了将遗传算法应用于关联规则的提取，并结合具体的实例提出了基于遗传算法的关联规则的提取算法。 并将其应用到农业气象数据库的灾害分析中，得到了较好的应用。