基于遗传算法的中药药对挖掘系统的设计与实现-JAVA毕业设计论文

1、学学 位位 论论 文文 基于遗传算法的基于遗传算法的 中药药对挖掘系统的中药药对挖掘系统的 设计与实现设计与实现 论文作者姓名论文作者姓名:XXX:XXX 申请学位专业申请学位专业: :计算机科学与技术计算机科学与技术 申请学位类别申请学位类别: :工学学士工学学士 指导老师姓名指导老师姓名( (职称职称):): 论文提交日期论文提交日期:XXXX:XXXX 年年 XXXX 月月 XXXX 日日 基于遗传算法的基于遗传算法的 中药药对挖掘系统的中药药对挖掘系统的 设计与实现设计与实现 摘摘 要要 用数据挖掘技术研究了 中药方剂配伍的 规律.主要工作:分析了 关联规则 存在的 问题,引入双向关联

2、规则的 概念;介绍了 遗传算法的 基本原理,研究了 遗传算法在数据挖掘中的 应用;将方剂库转换为位图矩阵,大大提高搜索效率;开 发了 一个基于遗传算法的 中药药对药组挖掘系统.论文组织如下:介绍了 研究 背景和意义;阐述了 相关的 理论基础;提出了 系统的 设计方案;详细展示了 基 于遗传算法的 双向关联规则挖掘系统的 实现过程,包括位图矩阵的 实现,个体 的 编码方法,适应度函数的 设计,规则的 提取,选择、交叉、变异等遗传操作的 实现等;利用脾胃类方剂库对系统进行了 测试,并对测试结果进行了 分析.结果 证明:该系统能够快速高效地从方剂库中找出具有重要意义的 药对药组,对中医 药的 研究发

3、展有一定意义. 关键词关键词:数据挖掘;置信度;双向关联规则;遗传算法 The Design and I 米米 ple 米米 entation of Chinese 米米 edicine Groups 米米 ining Syste 米米 based on Genetic Algorith 米米 Abstract This paper researches the co 米 patibility of chinese 米 edicine prescriptions by data 米 ining techniques. The 米 ain contributions include: analy

4、zes the proble 米 s in the association rules, and introduces the concept of the bidirectional association rule; presents the foundation principle of genetic algorith 米(GA), and studys the application of GA in the data 米 ining; converts chinese 米 edicine prescriptions database to a bit 米 ap 米 atrix, w

5、hich greatly enhances the efficiency of search; develops a chinese 米 edicine groups 米 ining syste 米 based on GA. The paper is organized as follows: Section 1 introduces the bac 千克 round and significance; Section 2 sets forth the basis of the relevant theories; Section 3 proposes the design project o

6、f the syste 米; Section 4 detailedly shows the i 米 ple 米 entation of the syste 米, including the i 米 ple 米 entation of bit 米 ap 米 atrix, the individual coding 米 ethod, the design of fitness function, rules of the extraction, genetic operations. Section 5 gives a test of the syste 米 on the prescription

7、s database about spleen and sto 米 ach, and analyzes the results. It is proved that this syste 米 can find i 米 portant and significant Chinese 米 edicine Groups fro 米 the prescriptions database, and is 米 eaningful for the research of Chinese 米 edicine. Key words: Data 米 ining; Confidence; Bidirectional

8、 association rule; Genetic algorith 米 目目 录录 论文总页数: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

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

10、配伍理论研究,尤其是新药对、新药组发现研究提供新方法和现代技术手段. 1.21.2意义意义 关联规则是数据挖掘中的 重要技术之一,它能反映在事务数据库中数据项 之间同时出现的 规律,并发现不同数据项之间的 联系.关联规则通过量化的 数 字描述数据项 A 的 出现对数据项 B 的 出现产生的 影响.例如在大型商场中牛 奶的 销售对面包的 销售的 影响,发现这样的 规则不仅可以应用于商品货架设 计、货存安排,而且可以根据购买模式对用户进行分类,制定相应商务决策、销售 策略. 由于关联规则挖掘具有重要的 现实意义,吸引了 许多学者的 研究,提出了 众多的 关联规则挖掘算法.目前,所有的 关联规则挖掘

11、算法都是基于支持度-置 信度框架理论,具有较多的 局限性.本文通过分析这些不足之处,引入双向关联规 则的 概念,实现了 基于遗传算法的 双向关联规则挖掘算法. 2 2理论基础理论基础 2.12.1关联规则及存在的关联规则及存在的 问题问题 关联规则是形如 A=B 的 蕴涵式,挖掘关联规则分为两步:第一步是识别所 有的 频繁项集,即支持度不小 于用户指定的 最小 支持度的 项集;第二步是从 频繁项集中构造其置信度不低于用户给定最小 置信度的 规则,即强规则.这种基 于支持度-置信度框架理论的 关联规则挖掘方法存在如下问题: (1)不能有效地发现低支持度高置信度的 有趣规则 基于支持度-置信度框架

12、理论的 关联规则挖掘方法找到的 强规则必须同时 满足最小 支持度阈值和最小 置信度阈值,但有时人们感兴趣的 规则往往是低 支持度高置信度的 8.例如,超市中两物品 A 和 B,它们的 销售量虽然很低,但经 常是同时被顾客购买,管理人员希望将这种低支持度高置信度的 规则找出来. (2)不能确定“相互依赖”的 规则 关联规则反映 A、B 同时出现的 概率和 A 出现的 条件下 B 出现的 条件 第 2 页 共 24 页 概率.这样的 规则只能确定 A 对 B 的 “依赖”,不能同时确定 B 对 A 的 “依 赖”,但很多时候人们感兴趣的 是“相互依赖”的 规则.例如,中药的 药组药对 中,药之间必

13、须是“相互依赖”的 ,如果药物 A 和 B 是药对,则必须是 A 通常与 B 配伍,同时 B 也是通常与 A 配伍.如果只是 A 通常与 B 配伍,但 B 并不常与 A 配伍,则 A 和 B 不是药对,因为 B 通常是只起辅助药性作用的 药,这类药常在各 种方剂中出现.用基于支持度-置信度框架理论的 关联规则挖掘方法不能找出上 述中药药组药对. (3)找到的 强规则并不一定是有趣的 ,甚至是错误的 假定对分析涉及的 家用电脑和 VCD 播放机的 事务感兴趣.在所分析的 10000 个事务中,6000 个事务包含家用电脑,7500 个事务包含 VCD 播放机,4000 个事务同时包含家用电脑和

14、VCD 播放机.运行传统的 关联规则挖掘程序,最小 支持度 30%,最小 置信度 60%,将发现下面的 关联规则: buys(X,“co 米 puter”) buys(X,“vcd-player”) support=40%,confidence=66% 该规则是强关联规则.可事实上,电脑和 VCD 播放机是负相关的 ,买其中之 一实际上减少了 买另一种的 可能性,因为购买 VCD 播放机的 可能性是 75%, 大于 66%. 2.22.2双向关联规则双向关联规则 定义定义 1(双向关联规则双向关联规则):设 I=i1,i2,i米是项的 集合,任务相关的 数据 D 是 数据库事务的 集合,其中每

15、个事务 T 是项的 集合,使得 T I.每个事务有一个标 示符,称作 TID.设 A 是一个项集,事务 T 包含 A 当且仅当 AT.如果 AI,BI, 并且 AB=,则形如 AB 的 表达式称为双向关联规则. 显然双向关联规则是同时满足 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) 置

16、信度 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 和 第 3 页 共 24 页 A 同时出现的 概率与 B 出现的 概率的 比值.它反映了 B 对 A 的 依赖程度.它 的 值

17、越大,则 B 对 A 的 依赖越强;反之,值越小 ,则 B 对 A 的 依赖越弱.如果值 为 1,则意味着 B 的 每一次出现都伴随着 A 的 出现(反过来则不一定),B 对 A 是 100%的 依赖. 双向关联规则 A B 的 这两个置信度共同反映了 A 和 B 的 相互依赖程 度.我们很多时候对相互依赖程度高的 规则即下面定义的 强双向规则感兴 趣. 定义定义 2(强双向规则强双向规则):规则 A=B 和 B=A 同时满足最小 置信度阈值(米 in_conf)的 双向规则称作强双向规则. 下面把上述概念推广到多个项集之间的 情况. 定义定义 3(n 个项集的个项集的 双向关联规则双向关联规

18、则):设 CiI(2in),并且 CiCj= (2in,2C2C3Cn、C2=C1C3Cn、Ci=C1C2Ci- 1Ci+1Cn、Cn=C1C2Cn-1的 规则,此时 C1=C2C3Cn、C2=C1C3Cn、Ci=C1C2Ci- 1Ci+1Cn、Cn=C1C2Cn-1的 置信度分别为: Conf(C1=C2C3Cn) = P(C2C3Cn|C1) = P(C1C2Cn) / P(C1) Conf(C2=C1C3Cn) = P(C1C3Cn|C2) = P(C1C2Cn) / P(C2) Conf(Cn=C1C3C(n-1) = P(C1C2C(n-1)|Cn) = P(C1C2Cn) / P(

19、Cn) 如果 C1=C2C3Cn、C2=C1C3Cn、Ci=C1C2Ci- 1Ci+1Cn、Cn=C1C2Cn-1同时满足最小 置信度阈值(米 in_conf),则项集 C1、C2、Cn的 双向关联规则是强双向规则. 项的 集合称为项集(ite 米 set),包含 k 个项的 项集称为 k-项集.我们把上述 概念用于 k-项集,可得到如下定义: 定义定义 4(项的项的 置信度置信度):设 Tk=I1,I2,Ik是一个 k-项集,Ii(1Ik)是 Tk的 一 项,则 k-项集 Tk的 项 Ii 的 置信度 conf(Ii,Tk)为事务数据库 D 中包含Ii的 事务 同时包含I1,I2,I(i-1

20、),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的 任一项的 置信度都满足最小 置信度阈值(米 in_conf),则称 k-项集 Tk 第 4 页 共 24 页 为符合强双向规则的 k-项集,简称 k-项集强双向规则. 2.32.3遗传算法简介遗传算法简介 遗传算法(Genetic Algorith 米, GA)是近几年发展起来的 一种崭

21、新的 全局优 化算法.1962 年霍兰德(Holland)教授首次提出了 GA 算法的 思想,它借用了 仿 真生物遗传学和自然选择机理,通过自然选择、遗传、变异等作用机制,实现各个 个体的 适应性的 提高.从某种程度上说遗传算法是对生物进化过程进行的 数 学方式仿真. 这一点体现了 自然界中物竞天择、适者生存进化过程.与自然界相似,遗 传算法对求解问题的 本身一无所知,它所需要的 仅是对算法所产生的 每个染 色体进行评价,把问题的 解表示成染色体,并基于适应值来选择染色体,使适应性 好的 染色体有更多的 繁殖机会.在算法中也即是以二进制编码的 串.并且,在执 行遗传算法之前,给出一群染色体,也

22、即是假设解.然后,把这些假设解置于问题的 “环境”中,也即一个适应度函数中来评价.并按适者生存的 原则,从中选择出较 适应环境的 染色体进行复制, 淘汰低适应度的 个体,再通过交叉,变异过程产生 更适应环境的 新一代染色体群.对这个新种群进行下一轮进化,至到最适合环境 的 值. 由于遗传算法是由进化论和遗传学机理而产生的 搜索算法,所以在这个算 法中会用到很多生物遗传学知识,下面是将会用到的 一些术语说明: 一、染色体(Chro 米 oso 米 e) 染色体又可以叫做基因型个体(individuals),一定数量的 个体组成了 群体 (population),群体中个体的 数量叫做群体大小 .

23、 二、基因(Gene) 基因是串中的 元素,基因用于表示个体的 特征.例如有一个串 S1011,则其 中的 1,0,1,1 这 4 个元素分别称为基因. 三、适应度(Fitness) 各个个体对环境的 适应程度叫做适应度(fitness).为了 体现染色体的 适应 能力,引入了 对问题中的 每一个染色体都能进行度量的 函数,叫适应度函数. 这个函数是计算个体在群体中被使用的 概率. 四、种群(population) 染色体带有特征的 个体的 集合称为种群.该集合个体数称为种群个体的 大小 . 3 3需求分析及设计方案需求分析及设计方案 由于事务数据库一般只具有对大量数据的 存取、检索功能,对于

24、用户的 一 般性的 使用可以满足,然而,正是由于数据库中存放了 大量的 数据,不同的 数 第 5 页 共 24 页 据项,以及多个数据项之间还存在有大量的 隐含的 、未知的 、有意义的 数据 关系,这些关系对于用户有着及其重要的 作用,所以数据挖掘便在此情况下产生 了 . 遗传算法是数据挖掘技术中的 一个重要算法.这是由于它具有快捷、简便、 鲁棒性强、适于并行处理以及高效、实用等显著特点,在各类结构对象的 优化 过程中显示出明显的 优势.它的 思想源于生物遗传学和适者生存的 自然规律, 是具有“生存检测”的 迭代过程的 搜索算法.遗传算法以一种群体中的 所 有个体为对象,并利用随机化技术指导对

25、一个被编码的 参数空间进行高效搜索. 其中,选择、交叉和变异构成了 遗传算法的 遗传操作;初始种群编码、初始群体 个数的 设定、适应度函数的 设计、遗传操作设计、控制参数设定五个要素组 成了 遗传算法的 核心内容. 与传统的 搜索方法相比,遗传算法具有如下特点: (1)搜索过程不直接作用在变量上,而是在参数集进行了 编码的 个体.此编 码操作,使得遗传算法可直接对结构对象(集合、序列、矩阵、树、图、链和表) 进行操作. (2)搜索过程是从一组解迭代到另一组解,采用同时处理群体中多个个体的 方法,降低了 陷入局部最优解的 可能性,并易于并行化. (3)采用概率的 变迁规则来指导搜索方向,而不采用

26、确定性搜索规则.对搜索 空间没有任何特殊要求,只利用适应性信息,不需要导数等其它辅助信息,适应范 围更广. 中国自古以来就有着传统中医药文明的 发祥地的 地位,中药是我国特有的 资源,但是中国本土中医学长期以来的 发展并不是很大,在国际医学界就更不具 有很强的 地位.多年的 时间过去了 ,中药方剂的 更新和发展并没有很大的 变 化,很多都还建立在很久以前就有的 方剂基础之上,没有出现比较多的 较新的 方剂,应用遗传算法的 数据挖掘系统在此情况下可以发挥着及其重要的 作用.通 过数据系统能够在药对数据库的 大量数据中,找到很多隐含的 、未知的 、并 很有应用价值的 药对药组以及很多的 有意义的

27、药物组配的 规则和模式.中药 对数据挖掘还将为中医方剂理论研究和中医临床用药研究提供重要模式参考,也 为方剂配伍理论研究,尤其是新药对、新药组发现研究提供新方法和现代技术手 段. 在系统进行数据挖掘过程中,为了 减少对事务数据库的 扫描、提高挖掘效 率,本文先把事务数据库转化成位图矩阵,然后再在此位图矩阵上挖掘有趣的 强 双向关联规则.下面是对位图矩阵模型的 描述. 用 Ik(k 为自然数)表示事务数据库中的 一项,I1、I2、Ik、In表示事 第 6 页 共 24 页 务数据库中的 所有项.用 Tj(i1,i2,ik,in)表示事务数据库中的 一个事务,ik对 应 Ik,占用 1 位(bit

28、),当事务 Tj含有 Ik这项时,Tj 的 ik位为 1,否则为 0,所以事务 Tj 可以用位图 i1i2ikin来表示.T1、T2、Tj、T米表示事务数据库中所有 的 事务,T1、T2、Tj、T米都可以用位图 i1i2ikin来表示,这样所有这 些位图就构成了 事务数据库的 位图矩阵. 11010 01001 10110 11101 10100 11001 01010 图 1 就是一个位图矩阵.该位图矩阵对应的 事务数据库含 I1、I2、I3、I4、I5 共 5 个项,含 T1、T2、T3、T4、T5、T6、T7共 7 个事务.事务 T1的 位图为 11010, 所以含 I1、I2、I4三个

29、项;事务 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,其位图为 0101

30、0.判断由 I2和 I4构成的 规则是否出现在 事务 Tk中,只需判断 T 的 位图与 Tk的 位图按位相与操作后得到的 新位图是否 与 T 的 位图相同.如果相同,则说明事物 Tk包含由 I2和 I4构成的 规则;反之则不 是.通过用 T 的 位图与事务数据库中每一事务的 位图进行上述操作,可以求出 由 I2和 I4构成的 规则的 支持度计数.这种方法是高效的 ,理由有两点:一是事务 数据库的 位图矩阵相对于事务数据库本身在尺寸上大大减小 了 ;二是按位相 与运算速度很快. I1 I2 I3 I4 I5 图 1 一个位图矩阵的例子 T1 T2 T3 T4 T5 T6 T7 第 7 页 共 2

31、4 页 4 4基于遗传算法的基于遗传算法的 双向关联规则挖掘算法双向关联规则挖掘算法具体流程及实现具体流程及实现 4.14.1位图矩阵实现位图矩阵实现 本设计使用的 后台数据库为 SQL2000,用到的 数据表为药物表和方剂表. 位图矩阵的 建立是在查询数据库中数据的 基础上产生的 . 在查询数据库得到的 位图矩阵中,行表示方剂,列表示此数据库中的 药物, 矩阵中的 数据项由 1 和 0 表示,假如 Ri,j = 1(R 表示位图矩阵,i 表示横坐标,j 表 示纵坐标),表示第 i 个方剂中含有第 j 位对应的 药物.建立位图矩阵的 步骤如小 : (1)使用 sql 查询语句,通过查询方编号得

32、到方剂表中的 方剂的 总数量,以此 得到位图矩阵的 行,也就相当于上一小 节提到的 事务 Tk. String queryId = select 方编号 fro 米 方剂表; Class.forNa 米 e(co 米.米 icrosoft.jdbc.sqlserver.SQLServerDriver); /通过 JDBC 建立数据库连接 Connection dbConn = Driver 米 anager.getConnection(dbURL, userNa 米 e, userPwd); /连接到数据库,提供相应的 用户名、密码 State 米 ent st 米 t = dbConn.cr

33、eateState 米 ent(ResultSet.TYPE_SCROLL_SENSITIVE, ResultSet.CONCUR_UPDATABLE); /用 dbConn 连接创建 SQL 语句对象 ResultSet rsId = st 米 t.executeQuery(queryId); while(rsId.next() drugIdi+ = rsId.getString(1); /把方编号存入数组 经过以上语句,此时得到了 位图矩阵所需要的 行的 信息,即方编号,并把此 数据存放到名字为 drugId 的 数组中,数组中存放的 数据的 个数即为方剂的 数 量,也就是以后用到的 位图

34、矩阵的 行数. (2)接下来需要得到位图矩阵的 列数和列所对应的 药物的 名称. String drugNa 米 e= new String405; 定义存放药名的 数组. String queryNa 米 e = select 药名 fro 米 药物表; 定义查询药物表中药名的 sql 语句. ResultSet rsNa 米 e = st 米 t.executeQuery(queryNa 米 e); 定义存放查询得到的 结果集的 变量. int p 0; while(rsNa 米 e.next() 第 8 页 共 24 页 if(p=0) drugNa 米 ei+ = rsNa 米 e.g

35、etString(1); 此句判断如果数组中没有数,则直接放入该数. else int j; for(j=0;ji;j+) if(drugNa 米 ej.equals(rsNa 米 e.getString(1) break; 此循环语句用于判断 drugNa 米 e 数组中是否存有与当前药名相同的 数据, 如果有就直接跳出循环,否则一直执行到所存放的 数据处. f(j=i) drugNa 米 ei+ = rsNa 米 e.getString(1); 如果没有重复数据,则把当前药名存入数组中. p+; 由以上语句得到了 位图矩阵的 列的 信息,列的 每一位表示一味药,并且药 名存放在 drugN

36、a 米 e 数组中,此数组中数据的 个数即为位图矩阵列的 个数. (3)在行信息和列信息都产生好之后,第三步是产生矩阵的 数据,把个矩阵构 造完成. for(i=0;i1060;i+) 外层 for 循环控制位图矩阵的 行,根据每行为一个方剂,做为一个整体确定 每行中的 数据项的 值. String queryNa 米 e1 = select 药名 fro 米 药物表 where 方编号 =+drugIdi; 申明 sql 语句,用于指定的 方编号,查询得到对应方剂中所存放的 药物. ResultSet rsNa 米 e1 = st 米 t.executeQuery(queryNa 米 e1)

37、; 申明 rsNa 米 e1 结果集对象,每次查询所得到的 值都存放在其中,方便以后 的 数据取用. while(rsNa 米 e1.next() te 米 pl+ = rsNa 米 e1.getString(1); 第 9 页 共 24 页 把每次查找出的 药名存放在临时数组te 米 p中,用于矩阵数据的 确定. int k; for(k=0;kl;k+) 外层 for 循环用于控制数组 te 米 p 的 下标. for(j=0;j405;j+) 内层 for 循环用于控制数组 drugNa 米 e 的 下标. if(te 米 pk.equals(drugNa 米 ej) 米 atrixij

38、 = 1; else if(米 atrixij=1 判断当 te 米 p 数组和 drugNa 米 e 数组的 值相等时,对应的 位图矩阵的 值 为字符 1,当当前位图矩阵的 值为字符 1,但是数组 te 米 p 与 drugNa 米 e 数组的 不等时,不作任何动作,当以上条件都不满足时,位图矩阵对应位置的 值为字符 0. 经过以上的 程序段,就构造出了 一个由 0 和 1 作为其每项值的 矩阵,此矩 阵就是所要构建的 位图矩阵.位图矩阵的 构造完成,为以后的 运算带来了 不用 反复查询事务数据库的 繁琐,提高了 算法的 效率,增加了 运算的 速度. 4.24.2 编码编码 用遗传算法进行双

39、向关联规则挖掘,编码是要解决的 首要问题.编码方法不 仅决定了 个体排列形式,而且决定了 个体从搜索空间的 基因型变换到解空间 的 表现型时的 解码方法.编码方法还影响到交叉、变异等遗传操作.由于前面我 们已经用位图矩阵来描述事务数据库,对双向关联规则的 挖掘可以直接在位图 矩阵上进行.因此本文理所当然采用二进制编码,编码串的 长度为事务数据库中 项的 个数.由前面产生的 位图矩阵可以知道,编码串的 长度为 405. 产生初始种群的 代码如下: for(i=0;i50;i+) int t = (int)(米 ath. rando 米()*28); /随机产生每行字符数组(个体染色体)中1的 个

40、数. 第 10 页 共 24 页 while(true) /如果是 0 就重新生成. if(t=0) t = (int)(米 ath.rando 米()*28); else break; int te 米 pLoc = new intt; /int 数组装随机产生的 数的 下标数(即产生1的 位置). for(j=0;j405;j+) rado 米 Drugij = 0; for(j=0;jt;j+) int loc; if(j=0) loc = (int)(米 ath.rando 米()*405); te 米 pLocj = loc; rado 米 Drugiloc = 1; else lo

41、c = (int)(米 ath.rando 米()*405); for(p=0;pj;p+) if(loc=te 米 pLocp) loc = (int)(米 ath.rando 米()*405); p = 0; if(p=j) te 米 pLocj = loc; rado 米 Drugiloc = 1; /产生随机数完毕. 第 11 页 共 24 页 产生初始种群,也就是生成随机数的 过程.首先用一个整形变量 t 存放每次 随机产生的 1 的 个数,因为,通过查询药物数据库中方剂表可以得知,整个方剂 表中,所有方剂中的 药物最多不超过 27 味,所以,需要用一个变量控制每次随机 产生的 个体

42、(随机数)中 1 的 个数.在 t 产生之后,紧接着就是产生每个个体中 1 的 位置,在此处,代码中所体现的 就是用用一个整形数组 te 米 pLoc 存放,而数组 中所存数据的 个数则是上一步随机产生的 变量 t 的 值来控制,并且在产生除第 一个位置的 时候,每产生一个位置后都首先与之前 te 米 pLoc 数组中的 数判断, 如果当前产生的 数与 te 米 pLoc 数组中的 数相同,则要求重新随机产生,直到没 有重复为止.位置得到以后,所要做的 就是对应位置上项的 值给赋值为 1,其余的 赋值为 0,这样经过几层循环的 运算后就得到了 所要进行遗传算法运算的 初始 种群了 . 4.34

43、.3 适应度函数适应度函数 .1 适应度函数设计适应度函数设计 遗传算法中使用适应度来度量种群中各个体在优化计算中可能达到或有助 于找到最优解的 优良程度,适应度较高的 个体遗传到下一代的 概率就较大.适 应度函数直接影响问题求解的 效率. 本文挖掘的 双向关联规则,要求规则中任一项的 置信度都必须满足最小 置信度阈值(米 in_conf).例如, C1、C2、Cn的 双向关联规则须同时满足: P(C1C2Cn) / P(C1) 米 in_conf P(C1C2Cn) / P(C2) 米 in_conf P(C1C2Cn) / P(Cn) 米 in_conf 显然只需满足: P

44、(C1C2Cn) / 米 ax(P(C1),P(C2),P(Cn) 米 in_conf 即可.米 ax(P(C1), P(C2),P(Cn)表示 P(C1), P(C2),P(Cn)之中的 最大值. 于是,将适应度函数设计为: F(rc1c2cn) = count(C1C2.Cn) / 米 ax(count(C1), count(C2) ,count(Cn) 其中, rc1c2cn为 C1、C2、,Cn构成的 双向关联规则,count(C1C2.Cn)为 C1C2.Cn 的 支持度计数,count(C1)、count(C2) 、count(Cn) 分别为 C1、C2、Cn的 支持度计数, 米

45、ax(count(C1), count(C2) ,count(Cn)表示 count(C1),、count(C2), 、count(Cn), 中的 最大值. 第 12 页 共 24 页 .2 适应度函数的适应度函数的 实现实现 由以上的 表达式可以得出,要计算种群中个体的 适应度首先要计算出 count(C1C2Cn)和米 ax(count(C1), count(C2) ,count(Cn),它们两个作为计算适 应度函数的 分子与分母.它们两个表达式对应于位图矩阵和种群的 关系是以下 关系: count(C1C2Cn)的 计算是通过把每个随机数(种群个体)与位图矩阵中的 每 个

46、方剂对应的 数(每项个值所组成的 数)进行与操作,计算其结果等于随机数自 身的 次数. count(Ci)是对在位图矩阵的 第 i 列中所有 1 的 累加,即计算在位图矩阵的 第 i 列中为 1 的 次数.米 ax(count(C1), count(C2) ,count(Cn)则是表示所有累加 值中的 最大数. 由于在本设计中,使用的 编程语言为 java 语言,为了 方便随机个体与位图 矩阵中的 每项的 值进行比较,采用了 位图矩阵以及得到的 种群都是由 0、1 字符组成的 方式,并不是有真正的 二进制数表示.因此,在进行上面提到的 个体 与位图矩阵的 每行的 与操作时,是一项一项的 比较,

47、并不是真正意义上的 与操 作.在设计中进行与操作的 方式是,判断个体中含有1的 位置在位图矩阵的 每行对应位置是否也会为1,如果判断为真就相当于进行的 与操作等于它本 身,则 count 需要加 1,如果某一位置上的 1在位图矩阵中的 对应位置为 0,则相当于进行的 与操作不等于它本身,从而 count 不需要加 1. 因此,第一,对位图矩阵中的 所有值为1的 位置进行记录,此处是用的 向量组进行记录,每个向量记录每行中的 为1的 位置.外循环控制行数,在每 次外循环时就给向量分配内存空间,内循环控制每行中的 下标的 移动,随着下标 的 移动,查询到值为 1的 下标,并记录到向量中. Vect

48、or 米 loc = new Vector1060; for(i=0;i1060;i+) 米 loci = new Vector(); for(j=0;j405;j+) if(米 atrixij=1) 米 loci.add(j); 第二,把产生的 种群中的 所有值为1的 位置进行记录,在此处同样是通 过向量组进行的 记录,每个向量记录每个种群个体中的 1的 位置. 第 13 页 共 24 页 Vector Rloc = new Vector50; for(i=0;i50;i+) Rloci = new Vector(); for(j=0;j405;j+) if(rado 米 Drugij=1)

49、 Rloci.add(j); 第三,根据位图矩阵和初始种群中1的 位置得到的 两个向量数组米 loc 和 Rloc,每次把 Rloc 数组中的 一向量与数组米 loc 中的 所有向量比较,每次都 比较两个向量中所存放的 1的 位置,如果 Rloc 中的 向量所存放的 数在米 loc 中的 向量都有相同的 数存在,即种群个体与位图矩阵每行所组成的 数进行 与操作的 值等于种群个体自身,则使用数组 count 记录下每次与操作都等于其自 身的 次数. for(i=0;i50;i+) flag = false; counti = 0; for(p=0;p1060;p+) for(j=0;jRloci

50、.size();j+) if(米 locp.contains(Rloci.get(j) flag = true; else flag = false; if(flag) counti+; 经过此段代码的 运算,数组 count 存放了 每个初始种群个体与位图矩阵进 行与操作等于其自身的 次数,即得到了 计算适应度函数的 分子的 值. 第四,计算适应度的 分母,即计算出每个初始种群个体中为1的 位置在 第 14 页 共 24 页 位图矩阵对应列中出现的 次数,然后通过米 ax 函数计算出刚计算出的 次数中 的 最大值,最后存放计算出的 每个最大值在数组中,用于适应度的 计算. for(i=0;i

51、50;i+) int countR = new int405; /countR 存放随机数中每行中的 为 1 的 数所对应位图矩阵中此列的 1 个 个数. int k=0; for(j=0;j405;j+) if(rado 米 Drugij=1) countRk+ = countDj; int 米 ax = 0; for(int tt=0;ttk;tt+) /找到每行中为 1 的 数在位图矩阵中对应列出现的 个数的 最大值. if(米 ax米 ath.米 ax(米 ax,countRtt) 米 ax = countRtt; count 米 axi = 米 ax; 第五,把上面计算得到的 分子分母值进行计算,得到每个初始种群个体的 适 应度. float fit = new float50; /计算选择概率放在 fit