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

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

《java 基于遗传算法的中药药对挖掘系统的设计与实现.docx》由会员分享，可在线阅读，更多相关《java 基于遗传算法的中药药对挖掘系统的设计与实现.docx（30页珍藏版）》请在冰点文库上搜索。

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

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

论文作者姓名：

申请学位专业：

计算机科学与技术

申请学位类别：

工学学士

指导老师姓名（职称）：

论文提交日期：

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

摘要

用数据挖掘技术研究了中药方剂配伍的规律。

主要工作：

分析了关联规则存在的问题，引入双向关联规则的概念；介绍了遗传算法的基本原理，研究了遗传算法在数据挖掘中的应用；将方剂库转换为位图矩阵，大大提高搜索效率；开发了一个基于遗传算法的中药药对药组挖掘系统。

论文组织如下：

介绍了研究背景和意义；阐述了相关的理论基础；提出了系统的设计方案；详细展示了基于遗传算法的双向关联规则挖掘系统的实现过程，包括位图矩阵的实现，个体的编码方法，适应度函数的设计，规则的提取，选择、交叉、变异等遗传操作的实现等；利用脾胃类方剂库对系统进行了测试，并对测试结果进行了分析。

结果证明：

该系统能够快速高效地从方剂库中找出具有重要意义的药对药组，对中医药的研究发展有一定意义。

关键词：

数据挖掘；置信度；双向关联规则；遗传算法

TheDesignandImplementationofChineseMedicineGroupsMiningSystembasedonGeneticAlgorithm

Abstract

Thispaperresearchesthecompatibilityofchinesemedicineprescriptionsbydataminingtechniques.Themaincontributionsinclude:

analyzestheproblemsintheassociationrules,andintroducestheconceptofthebidirectionalassociationrule;presentsthefoundationprincipleofgeneticalgorithm（GA）,andstudystheapplicationofGAinthedatamining;convertschinesemedicineprescriptionsdatabasetoabitmapmatrix,whichgreatlyenhancestheefficiencyofsearch;developsachinesemedicinegroupsminingsystembasedonGA.Thepaperisorganizedasfollows:

Section1introducesthebackgroundandsignificance;Section2setsforththebasisoftherelevanttheories;Section3proposesthedesignprojectofthesystem;Section4detailedlyshowstheimplementationofthesystem,includingtheimplementationofbitmapmatrix,theindividualcodingmethod,thedesignoffitnessfunction,rulesoftheextraction,geneticoperations.Section5givesatestofthesystemontheprescriptionsdatabaseaboutspleenandstomach,andanalyzestheresults.ItisprovedthatthissystemcanfindimportantandsignificantChineseMedicineGroupsfromtheprescriptionsdatabase,andismeaningfulfortheresearchofChinesemedicine.

Keywords:

Datamining;Confidence;Bidirectionalassociationrule;Geneticalgorithm

目录

论文总页数：

24页

1引言1

1.1背景1

1.2意义1

2理论基础1

2.1关联规则及存在的问题1

2.2双向关联规则2

2.3遗传算法简介4

3需求分析及设计方案5

4基于遗传算法的双向关联规则挖掘算法具体流程及实现7

4.1位图矩阵实现7

4.2编码9

4.3适应度函数11

4.3.1适应度函数设计11

4.3.2适应度函数的实现11

4.4规则的提取14

4.5遗传操作15

4.6算法流程18

5测试18

结论21

参考文献22

致谢23

声明24

引言

1.1背景

我国作为最大的中药材资源国，有着传统中医药文明的发祥地的地位，但是如今正面临着诸多挑战。

我国，在世界的中药市场上却未能占有基本的主导地位。

反而日本、韩国等国家成功地利用现代数据挖掘科技把中药行业发展成现代产业，占据了国际市场相当的份额，因此，继承和发展中医药不仅是中医界也是全国其他科研院校和科研机构的重要课题。

中药对数据挖掘就是利用药对数据库从大量的中药对中抽取隐含的、未知的、有意义的药物组配模式。

中药对数据挖掘将为中医方剂理论研究和中医临床用药研究提供重要模式参考，也为方剂配伍理论研究，尤其是新药对、新药组发现研究提供新方法和现代技术手段。

1.2意义

关联规则是数据挖掘中的重要技术之一，它能反映在事务数据库中数据项之间同时出现的规律，并发现不同数据项之间的联系。

关联规则通过量化的数字描述数据项A的出现对数据项B的出现产生的影响。

例如在大型商场中牛奶的销售对面包的销售的影响，发现这样的规则不仅可以应用于商品货架设计、货存安排，而且可以根据购买模式对用户进行分类，制定相应商务决策、销售策略。

由于关联规则挖掘具有重要的现实意义，吸引了许多学者的研究，提出了众多的关联规则挖掘算法。

目前，所有的关联规则挖掘算法都是基于支持度-置信度框架理论，具有较多的局限性。

本文通过分析这些不足之处，引入双向关联规则的概念，实现了基于遗传算法的双向关联规则挖掘算法。

理论基础

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={i1,i2,…,im}是项的集合，任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得T

I。

每个事务有一个标示符，称作TID。

设A是一个项集，事务T包含A当且仅当A

T。

如果A

I，B

I，并且A∩B=，则形如AB的表达式称为双向关联规则。

显然双向关联规则是同时满足A=>B和B=>A的规则。

反过来也可以说同时满足A=>B和B=>A的规则是双向关联规则。

所有双向关联规则AB有两个置信度。

一个是关联规则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%的依赖。

双向关联规则AB的这两个置信度共同反映了A和B的相互依赖程度。

我们很多时候对相互依赖程度高的规则——即下面定义的强双向规则感兴趣。

定义2（强双向规则）：

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

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

定义3（n个项集的双向关联规则）：

设CiI（2

（2C2C3…Cn、C2=>C1C3…Cn、…、Ci=>C1C2…Ci-1Ci+1…Cn、…、Cn=>C1C2…Cn-1的规则，此时C1=>C2C3…Cn、C2=>C1C3…Cn、…、Ci=>C1C2…Ci-1Ci+1…Cn、…、Cn=>C1C2…Cn-1的置信度分别为：

Conf（C1=>C2C3…Cn）=P（C2C3…Cn|C1）=P（C1C2…Cn）/P（C1）

Conf（C2=>C1C3…Cn）=P（C1C3…Cn|C2）=P（C1C2…Cn）/P（C2）

……

Conf（Cn=>C1C3…C（n-1））=P（C1C2…C（n-1）|Cn）=P（C1C2…Cn）/P（Cn）

如果C1=>C2C3…Cn、C2=>C1C3…Cn、…、Ci=>C1C2…Ci-1Ci+1…Cn、…、Cn=>C1C2…Cn-1同时满足最小置信度阈值（min_conf），则项集C1、C2、…、Cn的双向关联规则是强双向规则。

项的集合称为项集（itemset），包含k个项的项集称为k-项集。

我们把上述概念用于k-项集，可得到如下定义：

定义4（项的置信度）：

设Tk={I1,I2,…,Ik}是一个k-项集，Ii（1≤I≤k）是Tk的一项，则k-项集Tk的项Ii的置信度conf（Ii,Tk）为事务数据库D中包含{Ii}的事务同时包含{I1,I2,…,I（i-1）,I（i+1）,…,Ik}的百分比，即：

Conf（Ii,Tk）=P（{I1,I2,…,I（i-1）,I（i+1）,,Ik}|{Ii}）=P（{I1,I2,…,Ii,…,Ik}）/P（{Ii}）

定义5（k-项集强双向规则）：

设Tk={I1,I2,…,Ik}是事务数据库D中一个k-项集，如果Tk的任一项的置信度都满足最小置信度阈值（min_conf），则称k-项集Tk为符合强双向规则的k-项集，简称k-项集强双向规则。

2.3遗传算法简介

遗传算法（GeneticAlgorithm,GA）是近几年发展起来的一种崭新的全局优化算法。

1962年霍兰德（Holland）教授首次提出了GA算法的思想，它借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。

从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。

这一点体现了自然界中"物竞天择、适者生存"进化过程。

与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价,把问题的解表示成染色体，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。

在算法中也即是以二进制编码的串。

并且，在执行遗传算法之前，给出一群染色体，也即是假设解。

然后，把这些假设解置于问题的“环境”中，也即一个适应度函数中来评价。

并按适者生存的原则，从中选择出较适应环境的染色体进行复制,淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染色体群。

对这个新种群进行下一轮进化，至到最适合环境的值。

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

一、染色体（Chromosome）

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

二、基因（Gene）

基因是串中的元素，基因用于表示个体的特征。

例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。

三、适应度（Fitness）

各个个体对环境的适应程度叫做适应度（fitness）。

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

四、种群（population）

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

该集合个体数称为种群个体的大小。

需求分析及设计方案

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

遗传算法是数据挖掘技术中的一个重要算法。

这是由于它具有快捷、简便、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各类结构对象的优化过程中显示出明显的优势。

它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。

其中，选择、交叉和变异构成了遗传算法的遗传操作；初始种群编码、初始群体个数的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

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

（1）搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。

此编码操作，使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作。

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

（3）采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。

对搜索空间没有任何特殊要求，只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。

中国自古以来就有着传统中医药文明的发祥地的地位,中药是我国特有的资源，但是中国本土中医学长期以来的发展并不是很大，在国际医学界就更不具有很强的地位。

多年的时间过去了，中药方剂的更新和发展并没有很大的变化，很多都还建立在很久以前就有的方剂基础之上，没有出现比较多的较新的方剂，应用遗传算法的数据挖掘系统在此情况下可以发挥着及其重要的作用。

通过数据系统能够在药对数据库的大量数据中，找到很多隐含的、未知的、并很有应用价值的药对药组以及很多的有意义的药物组配的规则和模式。

中药对数据挖掘还将为中医方剂理论研究和中医临床用药研究提供重要模式参考，也为方剂配伍理论研究，尤其是新药对、新药组发现研究提供新方法和现代技术手段。

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

下面是对位图矩阵模型的描述。

用Ik（k为自然数）表示事务数据库中的一项，I1、I2、…、Ik、…、In表示事务数据库中的所有项。

用Tj（i1,i2,…,ik,…,in）表示事务数据库中的一个事务，ik对应Ik，占用1位（bit）,当事务Tj含有Ik这项时，Tj的ik位为1,否则为0，所以事务Tj可以用位图i1i2…ik…in来表示。

T1、T2、…、Tj、…、Tm表示事务数据库中所有的事务，T1、T2、…、Tj、…、Tm都可以用位图i1i2…ik…in来表示，这样所有这些位图就构成了事务数据库的位图矩阵。

1

1

0

1

0

0

1

0

0

1

1

0

1

1

0

1

1

1

0

1

1

0

1

0

0

1

1

0

0

1

0

1

0

1

0

图1就是一个位图矩阵。

该位图矩阵对应的事务数据库含I1、I2、I3、I4、I5共5个项，含T1、T2、T3、T4、T5、T6、T7共7个事务。

事务T1的位图为11010，所以含I1、I2、I4三个项；事务T2的位图为01001，所以含I2、I5两个项；事务T3的位图为10110，所以含I1、I3、I4三个项；事务T4的位图为11101，所以含I1、I2、I3、I5四个项；事务T5的位图为10100，所以含I1、I3两个项；事务T6的位图为11001，所以含I1、I2、I5三个项；事务T7的位图为01010，所以含I2、I4两个项。

得到事务数据库的位图矩阵后，就很容易求出某双向关联规则的支持度计数。

例如，要求出图1所对应事务数据库中I2和I4同时出现的次数。

先设计只包含I2、I4两个项的事物T，其位图为01010。

判断由I2和I4构成的规则是否出现在事务Tk中，只需判断T的位图与Tk的位图按位相与操作后得到的新位图是否与T的位图相同。

如果相同，则说明事物Tk包含由I2和I4构成的规则；反之则不是。

通过用T的位图与事务数据库中每一事务的位图进行上述操作，可以求出由I2和I4构成的规则的支持度计数。

这种方法是高效的，理由有两点：

一是事务数据库的位图矩阵相对于事务数据库本身在尺寸上大大减小了；二是按位相与运算速度很快。

基于遗传算法的双向关联规则挖掘算法具体流程及实现

4.1位图矩阵实现

本设计使用的后台数据库为SQL2000，用到的数据表为药物表和方剂表。

位图矩阵的建立是在查询数据库中数据的基础上产生的。

在查询数据库得到的位图矩阵中，行表示方剂，列表示此数据库中的药物，矩阵中的数据项由1和0表示，假如R[i，j]=1（R表示位图矩阵，i表示横坐标，j表示纵坐标）,表示第i个方剂中含有第j位对应的药物。

建立位图矩阵的步骤如小：

（1）使用sql查询语句，通过查询方编号得到方剂表中的方剂的总数量，以此得到位图矩阵的行，也就相当于上一小节提到的事务Tk。

StringqueryId="select方编号from方剂表";

Class.forName（"com.microsoft.jdbc.sqlserver.SQLServerDriver"）;

//通过JDBC建立数据库连接

ConnectiondbConn=DriverManager.getConnection（dbURL,userName,userPwd）;

//连接到数据库，提供相应的用户名、密码

Statementstmt=dbConn.createStatement（ResultSet.TYPE_SCROLL_SENSITIVE,ResultSet.CONCUR_UPDATABLE）;

//用dbConn连接创建SQL语句对象

ResultSetrsId=stmt.executeQuery（queryId）;

while（rsId.next（））{

drugId[i++]=rsId.getString

（1）;//把方编号存入数组

}

经过以上语句，此时得到了位图矩阵所需要的行的信息，即方编号，并把此数据存放到名字为drugId的数组中，数组中存放的数据的个数即为方剂的数量，也就是以后用到的位图矩阵的行数。

（2）接下来需要得到位图矩阵的列数和列所对应的药物的名称。

StringdrugName[]=newString[405];

定义存放药名的数组。

StringqueryName="select药名from药物表";

定义查询药物表中药名的sql语句。

ResultSetrsName=stmt.executeQuery（queryName）;

定义存放查询得到的结果集的变量。

intp＝0；

while（rsName.next（））{

if（p==0）{

drugName[i++]=rsName.getString

（1）;

}

此句判断如果数组中没有数，则直接放入该数。

else{

intj;

for（j=0;j

if（drugName[j].equals（rsName.getString

（1）））

break;

}

此循环语句用于判断drugName数组中是否存有与当前药名相同的数据，如果有就直接跳出循环，否则一直执行到所存放的数据处。

f（j==i）{

drugName[i++]=rsName.getString

（1）;

}

如果没有重复数据，则把当前药名存入数组中。

}

p++;

}

由以上语句得到了位图矩阵的列的信息，列的每一位表示一味药，并且药名存放在drugName数组中，此数组中数据的个数即为位图矩阵列的个数。

（3）在行信息和列信息都产生好之后，第三步是产生矩阵的数据，把个矩阵构造完成。

for（i=0;i<1060;i++）{

外层for循环控制位图矩阵的行，根据每行为一个方剂，做为一个整体确定每行中的数据项的值。

StringqueryName1="select药名from药物表where方编号="+drugId[i];

申明sql语句，用于指定的方编号，查询得到对应方剂中所存放的药物。

ResultSetrsNa