基于改进遗传算法的关联挖掘方法研究

郑玉柱 李 建 李 珂

(西南石油大学计算机科学学院， 成都 610500)



基于改进遗传算法的关联挖掘方法研究

郑玉柱 李 建 李 珂

(西南石油大学计算机科学学院， 成都 610500)

数值型关联规则挖掘是最优化问题而不是简单的离散问题，在大型数据库中挖掘数值型属性的关联规则具有一定的难度。为解决该问题，提出一种基于改进遗传算法的数据挖掘方法。针对数值型属性和布尔型属性的混合数据，设计一种分类并分界的编码方法；适应度函数采取范围收缩的策略，使属性边界向更精确的方向逼近；在此基础上设计出相应的交叉和变异算法，避免遗传算法的局部收敛和早熟问题；最后通过实例检验该算法的可行性。

数据挖掘； 关联规则； 数值型属性； 遗传算法； 适应度函数

数据挖掘(data mining, 简称DM)是一个新兴的人工智能与机器学习技术的研究领域，旨在通过发现隐藏在大量数据中的有用知识模式和有效信息，帮助人们进一步认识数据[1]，数据挖掘在决策系统、数据分析等方面有着广阔的应用前景。数据挖掘的一个研究方向是在数据库大量的数据中发现有意义的关联规则，即关联挖掘，最早由Agrawal等人提出，现在是数据挖掘领域中非常流行的研究热点。

遗传算法(genetic algorithm,简称GA)是一种基于生物进化理论的随机搜索算法，由于其具有很强的鲁棒性、适应性和隐式并行性，能够快速有效地进行全局优化，在数据挖掘技术中占有很重要的地位，早就被应用于人工智能领域的多个方面，是进行数据挖掘和知识发现的重要方法之一[2- 3]。该算法是一种全局优化算法，一般应用于在一个问题集中查找最优解的情况，特别适合解决多目标优化问题。借鉴生物进化论，遗传算法将要解决的问题模拟成为一个生物进化的过程，使用适应度值标识个体的进化能力，通过选择交叉和变异等操作产生下一代的解，并在进化过程中逐步淘汰适应度函数值较低的解，增加适应度函数值高的解。经过多次递归循环，进化一定阶段后就很有可能会进化出适应度函数值最高的个体。在这个方面，遗传算法体现了自然界中“物尽天择、适者生存”的进化过程。

设I={i1,i2,…,iM}是一组项目集合，又称项集。令与业务相关的数据库事务为集合D，其中包括了事务项T(T≠Ø)，且T⊆I。设A是一个项集，当且仅当A⊆T时，事务T包含A。关联规则便是形如A⟹B的事务关系，其中A⊂I，B⊂I，A≠Ø，B≠Ø且A∪B=Ø[5]。一般地，形如A⟹B的关联规则中左边的部分A被称为先导(Antecedent)，右边的部分B被称为后继(Consequence)[6]。在数据D中，规则A⟹B包含以下度量：

支持度(Support)是在数据D中包含A∪B集合的概率，表示为

Support(A⟹B)=P{A∪B}

(1)

置信度(Confidence)是在数据集D中包含A的同时又包含B的条件概率，表示为

Confidence(A⟹B)=P{B|A}

(2)

即

(3)

关联规则有2个评价指标：最小支持度(Suppmin)，最小置信度(Confmin)。如果某条规则满足：(1)支持度大于最小支持度阈值，(2)置信度大于最小置信度阈值，则这条关联规则就被认为是强关联规则，而关联挖掘中的主要工作，便是挖掘出数据集D中的强关联规则[7]。

本次研究提出一种基于遗传算法的关联挖掘算法，针对数据库中布尔型和数值型数据进行改进，为避免群体早熟和局部收敛做了适当优化。

1 基于改进遗传算法的关联挖掘方法设计

基于已有研究成果，本次研究提出一种基于改进遗传算法的关联挖掘方法(简称GAMAR)。与一般关联挖掘算法不同，关联规则直接由算法得出，而不用先寻找所有频繁项集。算法的流程图如图1所示。

图1 GAMAR算法流程图

在准备阶段的时候为该算法设置初始运行参数，参数的设定对本算法的运行性能有非常大的影响。初始参数包括传统遗传算法中的种群大小、交叉概率、变异概率、终止代数，以及关联挖掘技术中的最小支持度Suppmin和最小置信度Confmin。

(1)种群大小(PopSize)。群体大小表示的是群体中所含个体的数量，也叫种群规模。当种群大小的取值较小时，可以提高遗传算法的运算速度，但同时降低了群体的多样性，造成遗传算法的早熟现象；当种群大小的取值较大时，遗传算法的运算效率便会降低。所以在选取种群大小的时候，需要综合考虑这2个方面。

(2)交叉概率(CrossoverRate)。遗传算法中新个体的产生主要靠交叉操作，若取值较小，产生新个体的速度会变慢，所以一般情况下交叉概率选取的值都比较大。但也应注意，若取值过大，就会破坏群体中的优良模式，对进化运算产生不良影响。

(3)变异概率(MutateRate)。变异概率决定了物种的多样性。若取值过大，虽然能产生较多的新个体，但很有可能会破坏掉很多较好的模式，使遗传算法的性能近似于完全随机搜索算法的性能；若取值较小，则变异操作产生新个体与抑制早熟现象的能力就较差。

(4)终止代数(Iterations)。本算法的终止条件是种群进化至指定的终止代数，并将当前群体中的最佳个体作为最优解输出。当终止代数取值较小时，算法运算结束时种群中还未进化出最优个体；当终止代数取值较大时，运算到一定阶段种群进化已经趋于停滞，此时继续运算已没有必要。

1.2 编码方法

在确定了目标数据库之后，首先对数据库中采集到的数据进行编码，使数据离散化且便于进行数据挖掘，可根据具体问题选择采用二进制或者十进制编码方法，编码方法确定后便确定了个体的编码长度。鉴于需要挖掘的数据既有数值型数值，又有布尔型数值，所以挖掘目标是包含2种数值属性的混合型关联规则。鉴于此，本算法采用十进制编码方法。

在种群中的每一条染色体均表示一条确定的规则，规则中包含了确定的条件属性(先导，antecedent)和决策属性(后继，consequent)。在染色体中的每一个基因段表示一个确定属性，在每一个基因段中包含3个与属性相关联的信息：第一部分指示了该属性的类型，可以有3个可能的取值，分别为0,1,2，0表示该属性为前驱，1表示该属性为结果，2表示该属性不参与算法运算过程，不用考虑[9]；第二部分指示基因段的下限；第三部分指示基因段的上限。因此第二和第三部分可以看成是一个整体，在表示数值型属性时，2个部分大小不同的值表示该属性取值的上下限；在表示布尔型数值属性时，2个部分取相同的值，以指示该属性的真实取值。1条染色体的编码规则如图2所示。

图2 染色体编码规则图

1.3 适应度函数

适应度函数决定了种群中每个个体的适应度值的大小，也指引着种群进化的方向，由适应度函数确定的每一条染色体的适应度值，区分了普通染色体与最优染色体之间的差距。在关联挖掘中，设计出的适应度函数需要能表现最小支持度和最小置信度的限制作用，所以本次研究希望挖掘出支持度和置信度均大于各自阀值的强关联规则，即：

Support(A⟹B)≥Suppmin

(4)

且

Confidence(A⟹B)≥Confmin

(5)

由式(1)和式(3)，式(5)可转变为：

(6)

进而有：

Support(A⟹B)-Confmin·Support(A)≥0

(7)

所以在规则的置信度大于最小置信度阀值时，式(7)的左式可作为种群的适应度函数，这样设计是为了整合规则的置信度和支持度值，并且也是为满足适应度函数必须为正数的要求，即：

FitnessFunction(A⟹B)=Supp(A⟹B)-

Confmin·Support(A)

(8)

利用式(8)便可以求出染色体的适应度值，但是在评价某条规则时，还需要满足式(4)。为了保持适应度函数的独立，本次研究对支持度小于最小支持度阀值的规则做惩罚，使得不满足规则的更容易被淘汰。此外，对于数值型属性，数值的取值范围越狭小，规则越精确。因此需要提高这类规则的适应度值，使得其更容易在进化过程中生存下来。

由此，设计出的适应度函数算法FitnessFunction的伪代码如算法1所示。

1.4 遗传算子

1.4.1 交叉算子

在传统的遗传算法中，交叉算子将2个同源染色体通过交叉算法，例如单点交叉，重组形成新的染色体。在单点交叉中，交叉算子随机选择2个待交叉染色体，通过随机确定的交叉点，互换2个个体的一部分基因。在本算法中，交叉算子随机确定2个染色体，在每个基因处，根据交叉概率随机地交换父代的2个基因的上下限，生成2个新的基因段，新生成基因段中的上下限有4种可能的取值。算法的交叉过程如图3所示。

图3 交叉操作过程图

1.4.2 变异算子

为防止种群出现局部收敛或者早熟的现象，同时为了保证种群一定程度的多样性，需要变异算子对某个染色体上某个基因位的基因进行变异操作。对于二进制编码来说，变异操作只需将随机的基因位上的二进制基因值取反即可。针对本算法所采用的混合型编码方法，首先在种群中随机确定一个染色体，在每一个基因段上分别根据变异概率随机进行变异操作，基因段的上下限单边地增大或者减小随机宽度，但不超过基因段取值范围的领域边界值(Uppermax,Lowermin)，最后生成一个新的基因段。算法的变异过程如图4所示。

图4 变异操作过程图

1.4.3 选择算子

遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选择哪些个体遗传到下一代群体中。为了保障群体能够收敛到最优个体，本算法采用精英选择方法，该方法的思路是将每一代最佳的一部分个体，直接复制到下一代，替代下一代群体中最差的相应数量的个体。从遗传算法的选择策略考虑，精英选择是群体收敛到最优解的一种基本保障[10]。

1.5 初始种群设置

初始种群作为原始的搜索空间，是整个算法的开端。为了使得算法的搜索目标在一个较大的领域内，按照如下方式生成初始种群：染色体的每个基因段各自覆盖该属性的取值范围，即上限取最大边界值(Ui=Uppermax)，下限取最小边界值(Li=Lowermin)。这样设置会使得初始种群拥有足够的多样性，避免进化早熟现象。随着进化代数的增大，染色体中基因段的覆盖范围会趋于狭小，直到规则满足最小支持度的要求，最后得到更精确的关联规则。

1.6 规则模板的设置

利用遗传算法进行关联挖掘时，期望得到形如A⟹B的关联规则，而算法自身并不知道哪部分属性属于规则的先导，哪部分属性属于后继。此外，在确定了先导和后继的范围后，才可以由式(1)和式(2)求取规则的支持度和置信度。因此，在挖掘阶段之前，需要人为设置一个规则模板(Ruletemplate)，模板指定规则的格式，如式(9)所示：

Ruletemplate={属性1，属性2}⟹{属性3，属性4}

(9)

模板确定后将作为算法的一个输入条件，伴随整个算法的运行。

1.7 数据挖掘阶段

本次设计的GAMAR算法可以根据用户指定的规则模板，随机搜索目标数据集，挖掘出满足最小置信度和最小支持度的关联规则。

在运行之前，需要在目标数据库中查询出必要的数据，并对查询结果做相关的数据清洗处理，使待挖掘数据集中的各属性值为布尔型或者数值型数据，以便于进行关联规则的挖掘。

GAMAR算法的伪代码如算法2所示。

2 数据挖掘实例

本次研究利用中国石油天然气集团公司某钻探队现场施工数据进行关联挖掘实验，从数据库中获得的数据经过数据清洗及预处理后，得到表1所示的数据表结构。

表1 事故隐患元数据表

表1记录了各项隐患指标(A1～A32)在一段时间内每天发生的次数(0～n)，均为数值型数据。在此基础上进行关联挖掘，希望找到各项指标之间发生次数的关系。

为了使算法能更有效地得到强关联规则，经过多次实验对比参数选择，算法的各项输入参数选择如下：PopSize=500,CrossoverRate=0.5,MutateRate=0.3,Iterations=100，Suppmin=0.1,Confmin=0.4。为找到对施工影响最大的指标A32与其他指标的关系，设置规则模板如下：

{A1,A2,…,A31}⟹{A32}

对于此元数据，挖掘出的结果可能会出现某个指标值的上下标均为0的情况，表示该项指标不影响结果发生，在最终关联规则中将这种模式的指标值忽略不考虑。

经过100次种群进化，最终得到如表2所示的强关联规则(取最优2条)。

表2 算法挖掘结果

3 结 语

基于遗传算法的关联挖掘算法首先改进了原有的数据编码方式，能够更准确地表示元数据中数值类型的结构；其次提出了适应新编码形式的交叉和变异算法，在提高算法挖掘关联规则能力的同时，能够更好地避免遗传算法的局部收敛和早熟现象；最后提出了使用模板来指导数据挖掘的搜索方向，使得用户可以指定挖掘规则的模式。该方法可以有效地解决大数据量下挖掘数值型属性关联规则的问题。

[1] Zhang S C, Wu X D. Fundamentals of Association Rules in Data Mining and Knowledge Discovery [J]. Wiley Interdiscip Rev-Data Mining Knowl Discov, 2011, 1(2): 97-116.

[2] Nedic V, Cvetanovic S, Despotovic D, et al. Data Mining with Various Optimization methods [J]. Expert Syst Appl, 2014, 41(8): 3993-3999.

[3] Tan J S, He W, Qing Y. Application of Genetic Algorithm in Data Mining [C].Proceedings of the Education Technology and Computer Science, 2009 ETCS '09 First International Workshop on, 2009: 353-356.

[4] Goren H G, Tunali S, Jans R. A Review of Applications of Genetic Algorithms in Lot Sizing [J]. J Intell Manuf, 2010, 21(4): 575-590.

[5] Han J, Kamber M, Pei J. Data Mining: Concepts and Techniques, Third Edition [M].[s.l.]: Morgan Kaufmann, 2011.

[6] Shah R A, Asghar S. Privacy Preserving in Association Rules Using a Genetic Algorithm [J]. Turk J Electr Eng Comput Sci, 2014, 22(2): 434-450.

[7] Alhajj R, Kaya M. Multi-objective Genetic Algorithms Based Automated Clustering for Fuzzy Association Rules Mining [J]. Journal of Intelligent Information Systems, 2008, 31(3): 243-264.

[8] Kotsiantis S, Kanellopoulos D. Association Rules Mining: A Recent Overview [J]. GESTS International Transactions on Computer Science and Engineering, 2006, 32(1): 71-82.

[9] Alatas B, Akin E, Karci A. Modenar: Multi-objective Differential Evolution Algorithm for Mining Numeric Association Rules [J]. Appl Soft Comput, 2008, 8(1): 646-656.

[10] Gosselin L, Tye-Gingras M, Mathieu-Potvin F. Review of Utilization of Genetic Algorithms in Heat Transfer Problems [J]. Int J Heat Mass Transf, 2009, 52(910): 2169-2188.

Association Mining Method Based on Improved Genetic Algorithm

ZHENGYuzhuLIJianLIKe

(School of Computer Science, Southwest Petroleum University, Chengdu 610500, China)

In this paper a genetic-based association rule mining algorithm is proposed to deal with the problem of mining quantitative association rule in large database, because it is an optimization problem rather than a simple discretization one. First, we designed an encoding method for classification and division based on the blended data from boolean and quantitative attributes. Then the attributes′ amplitudes are shortened by the search strategy of fitness function when the boundary is droven more accurate. It is designed to avoid the local convergence and premature problems with appropriate crossover and mutate methods. Finally, the efficiency of the algorithm is validated by the test upon real database.

data mining; association rules; quantitative (numeric) attributes; genetic algorithm; fitness function

2015-01-30

国家科技重大专项“钻井工程设计和工艺软件”(2011ZX05021-006)

郑玉柱(1989 — )，男，西南石油大学2012级在读硕士研究生，研究方向为数据仓库与数据挖掘。

TP311

A

1673-1980(2015)05-0072-05