基于文化免疫克隆算法的关联规则挖掘研究

杨光军

德州学院 机电工程系，山东 德州 253023

基于文化免疫克隆算法的关联规则挖掘研究

杨光军

德州学院 机电工程系，山东 德州 253023

1 引言

关联规则挖掘作为数据挖掘的重要任务之一，其目的是在数据集中发现项集之间关联性。主要的关联规则发现算法有Apriori算法及其改进算法、FP-growth等[1]，这些方法计算复杂度高、效率非常低。许多研究人员致力于将智能算法如遗传算法[2]、免疫算法[3]等应用于关联规则挖掘。其中人工免疫算法是一种多点和随机的搜索策略，为关联规则挖掘问题提供了一种新颖的解决方法，但其在进化过程中交叉变异的盲目性和随机性导致收敛速度较慢。而文化算法[4]可以将其他的群体算法融合在文化的框架内，能够使群体以一定的速度进化和适应环境，并互相弥补各传统算法的不足。

本文采用文化算法的框架结构，将免疫克隆算法嵌入其中，利用免疫克隆算法在数据库中迅速搜索关联规则，利用文化算法形成的公共认知信念指导和加速搜索。实验表明，该模型具有较快的收敛速度，所得关联规则的准确率较高。

2 免疫克隆算法

人工免疫是近几年在智能技术学科方面的研究较多的领域之一。免疫克隆算法[5]是诸多免疫优化算法之一，模拟人的免疫应答原理，具有免疫应答的基本特征，而且克隆操作使算法具有独特的收敛性，从而提高了算法的收敛速度。

免疫克隆算法的克隆算子包括：克隆、克隆交叉、克隆变异和克隆选择。抗体群的状态转移情况可以表示成如下的随机过程：

克隆算子能有效扩大群体的规模，每个抗体与抗原的亲合度越大，抗体的克隆规模也就越大。克隆交叉是指把两个抗体的部分结构加以替换重组而生成新抗体的操作。克隆变异对种群实施高频变异，提高种群中个体的多样性。克隆选择是从变异后的抗体中选择优秀的个体，形成新的种群。

3 文化算法

在人类社会中，个体所获得的知识以一种公共认知的形式影响着社会中其他的个体，加速社会整体的进化，帮助个体更加适应环境，从而形成文化。1994年Reynolds等人提出了文化算法[4]，模拟人类社会的文化进化过程，采用双层进化机制，在传统的基于种群的进化算法基础上，构建信念空间来提取隐含在进化过程中的各类信息，并以知识的形式加以存储，最终用于指导进化过程，后来学者们对文化算法进行了更系统的研究[6-7]。其基本结构如图1所示。

图1 文化算法基本结构

种群空间用于实现任何基于种群的进化算法，一方面通过objective（）函数对个体实现评价，使用generate（）函数生成下一代个体，select（）函数选择个体作为下一代群体，另一方面将优良个体作为样本通过accept（）函数传递到信念空间。信念空间在update（）函数的作用下提取样本个体所携带的隐含信息，以知识的形式加以描述和储存，再通过influence（）函数对种群空间中个体的行为规则进行修改，以使个体空间得到更高的进化效率。文化算法虽然增加了维护信念空间以及两空间信息映射和交互的开销，但其利用在进化过程中积累的知识指导进化，增强了搜索的目的性，其整体搜索效率高于单纯基于生物进化的优化算法[8]。

4 基于文化免疫克隆算法的关联规则挖掘算法设计

文化算法可以将其他的种群算法融合在文化的框架内，能够使种群以一定的速度进化和适应环境，将免疫克隆算法与文化算法相结合具有更稳定的全局收敛性能及较快的收敛速度[8-9]。本文基于文化算法的模型，建立免疫克隆算法的种群空间与信念空间的双重演化及互相影响，构成基于文化免疫克隆算法的关联规则挖掘算法MAR-CICA（Mining Association Rules based on Cultured Immune Clone Algorithm）。具体构造如下。

4.1 种群空间设计

种群空间进化操作采用免疫克隆算法。使用免疫克隆算法进行关联规则挖掘时，将数据库中的所有记录作为抗原，候选模式作为抗体。将抗体与抗原作比较，与较多抗原匹配程度高的抗体将获得更大的存活和克隆变异的机会。免疫学习的过程，便是个体亲合度提高的过程，同时也是频繁模式生成并通过免疫记忆机制得以保存的过程。最后，关联规则由记忆细胞群所代表的频繁模式生成。

（1）编码方案：该算法中采用二进制编码。在二进制串中1表示该值被选中，0表示该值未被选中。

（2）亲合度计算：亲合度函数f是评价抗体与抗原联系的量化反映，它的选取对于挖掘结果具有举足轻重的作用。亲合度函数定义为：f(X⇒Y)=supp(X⇒Y)+conf(X⇒Y)，其中supp(X⇒Y)表示X⇒Y的支持度，conf(X⇒Y)表示X⇒Y的置信度。

f(X⇒Y)表明只有支持度和置信度都高才有可能生存下来。

（3）进化操作过程：①随机在解空间产生N个抗体形成初始抗体群Α0。种群的规模为N。初始记忆细胞群为空。进化代数k=0。②计算抗体亲合度。从数据库中随机抽取M条记录，根据公式计算抗体群Α中的抗体和M条记录的亲合度。从种群中根据亲合度的大小选取亲合度较大S个抗体组成作为记忆细胞加入记忆细胞群Pk。③根据亲合度和抗体规模，进行克隆操作，错位交叉操作，高频变异操作，选择操作，获得新的抗体群Αk+1。④判断循环条件，若条件满足，终止循环；不然，k=k+1，转入步骤②。

4.2 信念空间设计

随着文化算法的发展，研究人员先后提出五类信念空间的知识描述方式[6]，包括标准知识、状况知识、拓扑知识、领域知识和历史知识。这五类知识记录的信息不同，对算法具有不同的引导作用，适用于不同场合。本文算法需要保存进化过程中的较优个体，并且为了加快收敛速度，该算法需要监控算法的搜索过程，所以该算法的信念空间采用状况知识和历史知识，即信念空间的结构采用 ＜E，H＞结构，其中E=＜E1，E2，…，En＞为状况知识，Ei为第i个较优个体，n为状况知识容量；H=＜H1，H2，…，Hm＞为历史知识，Hj表示记录的第j个重要事件，m为历史知识容量。

（1）状况知识：在该算法中，状况知识用于记录进化过程中的较优个体，而进化过程中的优秀个体保存在免疫克隆算法的记忆细胞群中，因此状况知识就是免疫克隆算法的记忆单元，即状况知识的结构为＜X1，X2，…，Xn＞，其中Xi是记忆细胞群中的优秀个体。状况知识的更新规则为：

（2）历史知识：免疫克隆算法在进化过程中常出现的问题是早熟，陷入局部最优解，该算法利用历史知识监控算法的收敛情况，设计一种变异算子，自适应调节变异的尺度，引导算法的搜索方向。

4.3 接受操作

该算法用接受操作将种群空间的免疫克隆算法的优秀个体更新信念空间。在种群空间的免疫克隆算法的演化过程中，每运行ΑcceptStep代时，用记忆细胞群中当前的最优个体来替换信念空间中最差的个体。本文取ΑcceptStep=8。

4.4 影响操作

4.5 算法流程

本文提出的基于文化免疫克隆算法的关联规则挖掘算法MAR-CICA的算法流程如下：

（1）初始化种群空间和信念空间，并设置最大进化代数、选择概率、交叉概率、变异概率、状况知识容量和历史知识容量等参数。

（2）种群空间演化：计算亲合度、克隆、交叉、变异和选择。

（3）通过Update（）来更新信念空间的状况知识和历史知识。

（4）根据信念空间的个体通过Influence（）影响种群空间。

（5）判断是否满足终止条件，若条件满足则终止；否则k=k+1，转入步骤（2）。本文设定最大进化代数Gmax作为判断条件，当进化代数大于Gmax时终止程序。

5 实验结果及分析

本文分别选用通用的人工合成标准数据库（IBM QUESΤ[10]中的代码生成，记为D1）和UCI机器学习数据库中的mushroom数据集（http：//archive.ics.uci.edu/ml/datasets.html，记为D2）仿真实验，在数据集上分别实现了基于免疫克隆的关联规则挖掘算法[11]和本文算法MAR-CICA，以检验所提出算法的性能。取支持度为0.2%，置信度为60%。实验数据集特性和实验结果分别如表1和表2所示。

表1 实验数据集

表2 实验结果

从表2的实验数据可以看出，基于文化免疫克隆算法的关联规则挖掘算法MAR-CICA用时少而规则提取率高。这是因为在文化算法的信念空间各种知识结构的指导下，减弱了免疫克隆算法在计算过程中的盲目性和随机性，提高了收敛速度和搜索效率，从而促进进化过程。特别是在数据集较大的时候，这种优势更加明显。

通过实验的结果分析，可以发现基于文化免疫克隆算法的关联规则挖掘算法具有收敛速度快的特点，具有较好的全局及局部搜索能力，还可以得到更多的符合条件的关联规则。

6 结论

针对传统关联规则挖掘过程中出现的计算量大，效率低下的问题，本文提出了一种基于文化算法和免疫克隆算法的关联规则挖掘算法，这种方法有以下特点：

（1）将免疫克隆算法与文化算法相结合，采用双层进化机制，利用免疫克隆算法的智能搜索能力和文化算法信念空间知识的指导来挖掘规则。

（2）根据免疫克隆算法的特点，重新给出了文化算法中状况知识和历史知识的描述，并设计了一种变异算子，能够自适应调节变异尺度。

（3）挖掘过程也不需生成大量的频繁项目集，提高了关联规则挖掘的效率。

但如何设置各种参数使免疫克隆算法与文化算法有效结合起来，真正获得对种群进化起促进作用的“文化”，以便于更好地进行关联规则挖掘是今后进一步研究的工作。

[1]Han J W，Kamber M.数据挖掘：概念与技术[M].北京：机械工业出版社，2006.

[2]符保龙.基于混合遗传克隆算法的关联规则挖掘[J].计算机工程，2009，35（22）：216-220.

[3]朱玉，张虹，孔令东.基于人工免疫的多维关联规则挖掘及其应用研究[J].计算机科学，2009，36（8）：239-242.

[4]Reynolds R G.An introduction to cultural algorithms[C]//Proc of the 3rd Annual Conf on Evolution Programming.[S.l.]：World Scientific Publishing，1994：131-136.

[5]焦李成，刘芳，缑水平，等.智能数据挖掘与知识发现[M].西安：西安电子科技大学出版社，2006.

[6]刘纯青.文化算法及其应用研究[D].哈尔滨：哈尔滨工程大学，2007.

[7]Peng B.Knowledge and population swarms in cultural algorithms for dynamic environments[D].USA：Wayne State University，2005.

[8]覃晖，周建中，李英海，等.基于文化克隆选择算法的梯级水电站联合优化调度[J].系统仿真学报，2010，22（10）：2342-2346.

[9]郭一楠，王辉，程健.自适应免疫克隆选择文化算法[J].电子学报，2010，38（4）：966-972.

[10]Agrawal R，Imielinski Τ，Swami A.Mining association rules between sets of items in large databases[C]//Proceedings of the ACM SIGMOD，Washington D.C.，1993.

[11]羌亮.基于人工免疫的关联规则挖掘算法的研究[D].南京：东南大学，2006.

YANG Guangjun

Mechanical Electronic Engineering Department,Dezhou University,Dezhou,Shandong 253023,China

For the association rules mining,a method of mining association rules based on cultured immune clone algorithm is proposed.Τhis method uses two-layer evolutionary mechanism and embeds the immune clone algorithm in the culture algorithm framework.It uses the intelligent searching ability of the immune clone algorithm and the commonly accepted knowledge in the culture algorithm to guide the rules mining.Τhe situational knowledge and history knowledge in the culture algorithm are redefined,and a new mutation operator is put forward.Τhis operator has the adaptive adjustment of mutation measure to improve the global search ability of immune clone algorithm.Τhe experiments show that the new algorithm is superior to immune clone algorithm in performance speed and the rules’accuracy.

association rules;immune clone algorithm;culture algorithm;self-adaptive mutation operator;two-layer evolutionary mechanism

针对关联规则挖掘问题，给出一种基于文化免疫克隆算法的关联规则挖掘方法，该方法将免疫克隆算法嵌入到文化算法的框架中，采用双层进化机制，利用免疫克隆算法的智能搜索能力和文化算法信念空间形成的公共认知信念的引导挖掘规则。该方法重新给出了文化算法中状况知识和历史知识的描述，设计了一种变异算子，能够自适应调节变异尺度，提高免疫克隆算法全局搜索能力。实验表明，该算法的运行速度和所得关联规则的准确率优于免疫克隆算法。

关联规则；免疫克隆算法；文化算法；自适应变异算子；双层进化机制

A

ΤP311

10.3778/j.issn.1002-8331.1112-0043

YANG Guangjun.Mining association rules based on cultured immune clone algorithm.Computer Engineering and Applications,2013,49（15）：113-115.

杨光军（1977—），男，讲师，主要研究领域为数据库技术，数据挖掘。E-mail：guangjun_yang@126.com

2011-12-05

2012-01-13

1002-8331（2013）15-0113-03

CNKI出版日期：2012-05-21 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120521.1142.086.html