基于遗传算法的中药药对挖掘系统的设计与实现

1 引言

1.1 背景

我国作为最大的中药材资源国，有着传统中医药文明的发祥地的地位，但是如今正面临着诸多挑战。我国，在世界的中药市场上却未能占有基本的主导地位。反而日本、韩国等国家成功地利用现代数据挖掘科技把中药行业发展成现代产业，占据了国际市场相当的份额，因此，继承和发展中医药不仅是中医界也是全国其他科研院校和科研机构的重要课题。中药对数据挖掘就是利用药对数据库从大量的中药对中抽取隐含的、未知的、有意义的药物组配模式。中药对数据挖掘将为中医方剂理论研究和中医临床用药研究提供重要模式参考，也为方剂配伍理论研究，尤其是新药对、新药组发现研究提供新方法和现代技术手段。

1.2 意义

关联规则是数据挖掘中的重要技术之一，它能反映在事务数据库中数据项之间同时出现的规律，并发现不同数据项之间的联系。关联规则通过量化的数字描述数据项A的出现对数据项B的出现产生的影响。例如在大型商场中牛奶的销售对面包的销售的影响，发现这样的规则不仅可以应用于商品货架设计、货存安排，而且可以根据购买模式对用户进行分类，制定相应商务决策、销售策略。

由于关联规则挖掘具有重要的现实意义，吸引了许多学者的研究，提出了众多的关联规则挖掘算法。目前，所有的关联规则挖掘算法都是基于支持度-置信度框架理论，具有较多的局限性。本文通过分析这些不足之处，引入双向关联规则的概念，实现了基于遗传算法的双向关联规则挖掘算法。

2 理论基础

2.1 关联规则及存在的问题

关联规则是形如A=>B的蕴涵式，挖掘关联规则分为两步：第一步是识别所有的频繁项集，即支持度不小于用户指定的最小支持度的项集；第二步是从频繁项集中构造其置信度不低于用户给定最小置信度的规则，即强规则。这种基于支持度-置信度框架理论的关联规则挖掘方法存在如下问题：

（1）不能有效地发现低支持度高置信度的有趣规则

基于支持度-置信度框架理论的关联规则挖掘方法找到的强规则必须同时满足最小支持度阈值和最小置信度阈值，但有时人们感兴趣的规则往往是低支持度高置信度的[8]。例如，超市中两物品A和B，它们的销售量虽然很低，但经常是同时被顾客购买，管理人员希望将这种低支持度高置信度的规则找出来。

（2）不能确定“相互依赖”的规则

关联规则反映A、B同时出现的概率和A出现的条件下B出现的条件概率。这样的规则只能确定A对B的“依赖”，不能同时确定B对A的“依赖”，但很多时候人们感兴趣的是“相互依赖”的规则。例如，中药的药组药对中，药之间必须是“相互依赖”的，如果药物A和B是药对，则必须是A通常与B配伍，同时B也是通常与A配伍。如果只是A通常与B配伍，但B并不常与A配伍，则A和B不是药对，因为B通常是只起辅助药性作用的药，这类药常在各种方剂中出现。用基于支持度-置信度框架理论的关联规则挖掘方法不能找出上述中药药组药对。

（3）找到的强规则并不一定是有趣的，甚至是错误的

假定对分析涉及的家用电脑和VCD播放机的事务感兴趣。在所分析的10000个事务中，6000个事务包含家用电脑，7500个事务包含VCD播放机，4000个事务同时包含家用电脑和VCD播放机。运行传统的关联规则挖掘程序，最小支持度30%，最小置信度60%，将发现下面的关联规则：

    buys(X,“computer”)Þ buys(X,“vcd-player”)

    [support=40%,confidence=66%]

该规则是强关联规则。可事实上，电脑和VCD播放机是负相关的，买其中之一实际上减少了买另一种的可能性，因为购买VCD播放机的可能性是75%，大于66%。   

2.2 双向关联规则

定义1（双向关联规则）：设I={i₁,i₂,…,i_m}是项的集合，任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得T I。每个事务有一个标示符，称作T_ID。设A是一个项集，事务T包含A当且仅当 AT。如果AI，BI，并且A∩B=Æ，则形如AóB的表达式称为双向关联规则。

显然双向关联规则是同时满足A=>B和B=>A的规则。反过来也可以说同时满足A=>B和B=>A的规则是双向关联规则。所有双向关联规则Aó B有两个置信度。 一个是关联规则A=>B的置信度：

conf(A=>B) = P(B|A) = P(AB) / P(A)

另一个是关联规则B=>A的置信度： 

conf(A=>B) = P(A|B) = P(AB) / P(B) 

置信度conf(A=>B)表示A出现的条件下B出现的条件概率，也就是A和B同时出现的概率与A出现的概率的比值。它反映了A对B的依赖程度。它的值越大，则A对B的依赖越强；反之，值越小，则A对B的依赖越弱。如果值为1，则意味着A的每一次出现都伴随着B的出现（反过来则不一定），A对B是100%的依赖。

置信度conf(B=>A)表示B出现的条件下A出现的条件概率，也就是B和A同时出现的概率与B出现的概率的比值。它反映了B对A的依赖程度。它的值越大，则B对A的依赖越强；反之，值越小，则B对A的依赖越弱。如果值为1，则意味着B的每一次出现都伴随着A的出现（反过来则不一定），B对A是100%的依赖。

双向关联规则A óB的这两个置信度共同反映了A和B的相互依赖程度。我们很多时候对相互依赖程度高的规则——即下面定义的强双向规则感兴趣。

定义2（强双向规则）：规则A=>B和B=>A同时满足最小置信度阈值（min_conf）的双向规则称作强双向规则。

下面把上述概念推广到多个项集之间的情况。

定义3（n个项集的双向关联规则）：设CiÌI(2<i≤n),并且C_i∩C_j=ÆÆ

(2<i≤n，2<j≤n,i≠j)，n项集C₁、C₂、…,C_n的双向关联规则为同时满足C₁=>C₂C₃…C_n、C₂=>C₁C₃…C_n、…、C_i=>C₁C₂…C_i-1C_i+1…C_n、…、C_n=>C₁C₂…C_n-1的规则，此时C₁=>C₂C₃…C_n、C₂=>C₁C₃…C_n、…、C_i=>C₁C₂…C_i-1C_i+1…C_n、…、C_n=>C₁C₂…C_n-1的置信度分别为：

Conf(C₁=>C₂C₃…C_n) = P(C₂C₃…C_n|C₁) = P(C₁C₂…C_n) / P(C₁)

Conf(C₂=>C₁C₃…C_n) = P(C₁C₃…C_n|C₂) = P(C₁C₂…C_n) / P(C₂)

……

Conf(C_n=>C₁C₃…C_(n-1)) = P(C₁C₂…C_(n-1)|C_n) = P(C1C₂…C_n) / P(C_n)

如果C₁=>C₂C₃…Cn、C₂=>C₁C₃…C_n、…、Ci=>C₁C₂…C_i-1C_i+1…C_n、…、C_n=>C₁C₂…C_n-1同时满足最小置信度阈值（min_conf），则项集C₁、C₂、…、C_n的双向关联规则是强双向规则。

项的集合称为项集(itemset)，包含k个项的项集称为k-项集。我们把上述概念用于k-项集，可得到如下定义：

定义4（项的置信度）：设T_k={I₁,I₂,…,I_k}是一个k-项集，I_i（1≤I≤k）是T_k的一项，则k-项集T_k的项Ii的置信度conf(Ii,T_k)为事务数据库D中包含{I_i}的事务同时包含{I₁,I₂,…,I_(i-1),I_(i+1),…,I_k}的百分比，即：  

Conf(Ii,T_k) = P({I₁,I₂, …,I_(i-1),I_(i+1), ,I_k}|{Ii})=P({I₁,I₂, …,I_i, …,I_k})/P({Ii})

定义5（k-项集强双向规则）：设T_k={I₁,I₂,…,I_k}是事务数据库D中一个k-项集，如果T_k的任一项的置信度都满足最小置信度阈值(min_conf)，则称k-项集T_k为符合强双向规则的k-项集，简称k-项集强双向规则。

2.3 遗传算法简介

遗传算法（Genetic Algorithm, GA）是近几年发展起来的一种崭新的全局优化算法。1962年霍兰德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。

这一点体现了自然界中"物竞天择、适者生存"进化过程。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价,把问题的解表示成染色体，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群染色体，也即是假设解。然后，把这些假设解置于问题的“环境”中，也即一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染色体进行复制, 淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化，至到最适合环境的值。

由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是将会用到的一些术语说明：

一、染色体(Chromosome)

染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。

二、基因(Gene)

基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。

三、适应度(Fitness)

各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数. 这个函数是计算个体在群体中被使用的概率。

四、种群（population）

染色体带有特征的个体的集合称为种群。该集合个体数称为种群个体的大小。

3 需求分析及设计方案

由于事务数据库一般只具有对大量数据的存取、检索功能，对于用户的一般性的使用可以满足，然而，正是由于数据库中存放了大量的数据，不同的数据项，以及多个数据项之间还存在有大量的隐含的、未知的、有意义的数据关系，这些关系对于用户有着及其重要的作用，所以数据挖掘便在此情况下产生了。

遗传算法是数据挖掘技术中的一个重要算法。这是由于它具有快捷、简便、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各类结构对象的优化过程中显示出明显的优势。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；初始种群编码、初始群体个数的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

与传统的搜索方法相比，遗传算法具有如下特点：

（1）搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作。

（2）搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。

（3）采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。对搜索空间没有任何特殊要求，只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。

中国自古以来就有着传统中医药文明的发祥地的地位,中药是我国特有的资源，但是中国本土中医学长期以来的发展并不是很大，在国际医学界就更不具有很强的地位。多年的时间过去了，中药方剂的更新和发展并没有很大的变化，很多都还建立在很久以前就有的方剂基础之上，没有出现比较多的较新的方剂，应用遗传算法的数据挖掘系统在此情况下可以发挥着及其重要的作用。通过数据系统能够在药对数据库的大量数据中，找到很多隐含的、未知的、并很有应用价值的药对药组以及很多的有意义的药物组配的规则和模式。中药对数据挖掘还将为中医方剂理论研究和中医临床用药研究提供重要模式参考，也为方剂配伍理论研究，尤其是新药对、新药组发现研究提供新方法和现代技术手段。

在系统进行数据挖掘过程中，为了减少对事务数据库的扫描、提高挖掘效率，本文先把事务数据库转化成位图矩阵，然后再在此位图矩阵上挖掘有趣的强双向关联规则。下面是对位图矩阵模型的描述。

用I_k(k为自然数)表示事务数据库中的一项，I₁、I₂、…、I_k、…、I_n表示事务数据库中的所有项。用T_j(i₁,i₂,…,i_k,…,i_n)表示事务数据库中的一个事务，i_k对应I_k，占用1位(bit),当事务T_j含有I_k这项时，Tj的i_k位为1,否则为0，所以事务T_j可以用位图i₁i₂…i_k…i_n来表示。T₁、T₂、…、T_j、…、T_m表示事务数据库中所有的事务，T₁、T₂、…、T_j、…、T_m都可以用位图i₁i₂…i_k…i_n来表示，这样所有这些位图就构成了事务数据库的位图矩阵。