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

分类号 分类号 TP312TP312 U U D D C C D10621 408 2007 D10621 408 2007 5973 05973 0 密密 级 公级 公 开开 编编 号 号 20030312862003031286 成成 都都 信信 息息 工工 程程 学学 院院 学学 位位 论论 文文 基于遗传算法的中药药对挖掘系统的设计与实现基于遗传算法的中药药对挖掘系统的设计与实现 论论文作者姓名 文作者姓名 吴吴 金金 伟伟 申申请请学位学位专业专业 计计算机科学与技算机科学与技术术 申申请请学位学位类别类别 工学学士工学学士 指指导导老老师师姓名 姓名 职职称 称 曾令明 曾令明 讲师讲师 论论文提交日期 文提交日期 2007 年年 06 月月 10 日日 基于遗传算法的中药药对挖掘系统的设计与实现基于遗传算法的中药药对挖掘系统的设计与实现 摘摘 要要 用数据挖掘技术研究了中药方剂配伍的规律 主要工作 分析了关联规则 存在的问题 引入双向关联规则的概念 介绍了遗传算法的基本原理 研究了 遗传算法在数据挖掘中的应用 将方剂库转换为位图矩阵 大大提高搜索效率 开发了一个基于遗传算法的中药药对药组挖掘系统 论文组织如下 介绍了研 究背景和意义 阐述了相关的理论基础 提出了系统的设计方案 详细展示了 基于遗传算法的双向关联规则挖掘系统的实现过程 包括位图矩阵的实现 个 体的编码方法 适应度函数的设计 规则的提取 选择 交叉 变异等遗传操 作的实现等 利用脾胃类方剂库对系统进行了测试 并对测试结果进行了分析 结果证明 该系统能够快速高效地从方剂库中找出具有重要意义的药对药组 对中医药的研究发展有一定意义 关键词 关键词 数据挖掘 置信度 双向关联规则 遗传算法 The Design and Implementation of Chinese Medicine Groups Mining System based on Genetic Algorithm Abstract This paper researches the compatibility of chinese medicine prescriptions by data mining techniques The main contributions include analyzes the problems in the association rules and introduces the concept of the bidirectional association rule presents the foundation principle of genetic algorithm GA and studys the application of GA in the data mining converts chinese medicine prescriptions database to a bitmap matrix which greatly enhances the efficiency of search develops a chinese medicine groups mining system based on GA The paper is organized as follows Section 1 introduces the background and significance Section 2 sets forth the basis of the relevant theories Section 3 proposes the design project of the system Section 4 detailedly shows the implementation of the system including the implementation of bitmap matrix the individual coding method the design of fitness function rules of the extraction genetic operations Section 5 gives a test of the system on the prescriptions database about spleen and stomach and analyzes the results It is proved that this system can find important and significant Chinese Medicine Groups from the prescriptions database and is meaningful for the research of Chinese medicine Key words Data mining Confidence Bidirectional association rule Genetic algorithm 目目 录录 论文总页数 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 页 共 24 页 1 1引言引言 1 11 1背景背景 我国作为最大的中药材资源国 有着传统中医药文明的发祥地的地位 但 是如今正面临着诸多挑战 我国 在世界的中药市场上却未能占有基本的主导 地位 反而日本 韩国等国家成功地利用现代数据挖掘科技把中药行业发展成 现代产业 占据了国际市场相当的份额 因此 继承和发展中医药不仅是中医 界也是全国其他科研院校和科研机构的重要课题 中药对数据挖掘就是利用药 对数据库从大量的中药对中抽取隐含的 未知的 有意义的药物组配模式 中 药对数据挖掘将为中医方剂理论研究和中医临床用药研究提供重要模式参考 也为方剂配伍理论研究 尤其是新药对 新药组发现研究提供新方法和现代技 术手段 1 21 2意义意义 关联规则是数据挖掘中的重要技术之一 它能反映在事务数据库中数据项 之间同时出现的规律 并发现不同数据项之间的联系 关联规则通过量化的数 字描述数据项 A 的出现对数据项 B 的出现产生的影响 例如在大型商场中牛奶 的销售对面包的销售的影响 发现这样的规则不仅可以应用于商品货架设计 货存安排 而且可以根据购买模式对用户进行分类 制定相应商务决策 销售 策略 由于关联规则挖掘具有重要的现实意义 吸引了许多学者的研究 提出了 众多的关联规则挖掘算法 目前 所有的关联规则挖掘算法都是基于支持度 置 信度框架理论 具有较多的局限性 本文通过分析这些不足之处 引入双向关 联规则的概念 实现了基于遗传算法的双向关联规则挖掘算法 2 2理论基础理论基础 2 12 1关联规则及存在的问题关联规则及存在的问题 关联规则是形如 A B 的蕴涵式 挖掘关联规则分为两步 第一步是识别 所有的频繁项集 即支持度不小于用户指定的最小支持度的项集 第二步是从 频繁项集中构造其置信度不低于用户给定最小置信度的规则 即强规则 这种 基于支持度 置信度框架理论的关联规则挖掘方法存在如下问题 1 不能有效地发现低支持度高置信度的有趣规则 基于支持度 置信度框架理论的关联规则挖掘方法找到的强规则必须同时满 足最小支持度阈值和最小置信度阈值 但有时人们感兴趣的规则往往是低支持 度高置信度的 8 例如 超市中两物品 A 和 B 它们的销售量虽然很低 但经 常是同时被顾客购买 管理人员希望将这种低支持度高置信度的规则找出来 2 不能确定 相互依赖 的规则 第 2 页 共 24 页 关联规则反映 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 22 2双向关联规则双向关联规则 定义定义 1 双向关联规则 双向关联规则 设 I i1 i2 im 是项的集合 任务相关的数据 D 是数据库事务的集合 其中每个事务 T 是项的集合 使得 T I 每个事务有 一个标示符 称作 TID 设 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 的依赖 第 3 页 共 24 页 置信度 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 并且 Ci Cj 2 i n 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 项 第 4 页 共 24 页 集 Tk为符合强双向规则的 k 项集 简称 k 项集强双向规则 2 32 3遗传算法简介遗传算法简介 遗传算法 Genetic Algorithm GA 是近几年发展起来的一种崭新的全局优 化算法 1962 年霍兰德 Holland 教授首次提出了 GA 算法的思想 它借用了仿 真生物遗传学和自然选择机理 通过自然选择 遗传 变异等作用机制 实现 各个个体的适应性的提高 从某种程度上说遗传算法是对生物进化过程进行的 数学方式仿真 这一点体现了自然界中 物竞天择 适者生存 进化过程 与自然界相似 遗传算法对求解问题的本身一无所知 它所需要的仅是对算法所产生的每个染 色体进行评价 把问题的解表示成染色体 并基于适应值来选择染色体 使适应 性好的染色体有更多的繁殖机会 在算法中也即是以二进制编码的串 并且 在执行遗传算法之前 给出一群染色体 也即是假设解 然后 把这些假设解 置于问题的 环境 中 也即一个适应度函数中来评价 并按适者生存的原则 从中选择出较适应环境的染色体进行复制 淘汰低适应度的个体 再通过交叉 变异过程产生更适应环境的新一代染色体群 对这个新种群进行下一轮进化 至到最适合环境的值 由于遗传算法是由进化论和遗传学机理而产生的搜索算法 所以在这个算 法中会用到很多生物遗传学知识 下面是将会用到的一些术语说明 一 染色体 Chromosome 染色体又可以叫做基因型个体 individuals 一定数量的个体组成了群体 population 群体中个体的数量叫做群体大小 二 基因 Gene 基因是串中的元素 基因用于表示个体的特征 例如有一个串 S 1011 则其中的 1 0 1 1 这 4 个元素分别称为基因 三 适应度 Fitness 各个个体对环境的适应程度叫做适应度 fitness 为了体现染色体的适应能 力 引入了对问题中的每一个染色体都能进行度量的函数 叫适应度函数 这 个函数是计算个体在群体中被使用的概率 四 种群 population 染色体带有特征的个体的集合称为种群 该集合个体数称为种群个体的大 小 3 3需求分析及设计方案需求分析及设计方案 由于事务数据库一般只具有对大量数据的存取 检索功能 对于用户的一 般性的使用可以满足 然而 正是由于数据库中存放了大量的数据 不同的数 第 5 页 共 24 页 据项 以及多个数据项之间还存在有大量的隐含的 未知的 有意义的数据关 系 这些关系对于用户有着及其重要的作用 所以数据挖掘便在此情况下产生 了 遗传算法是数据挖掘技术中的一个重要算法 这是由于它具有快捷 简便 鲁棒性强 适于并行处理以及高效 实用等显著特点 在各类结构对象的优化 过程中显示出明显的优势 它的思想源于生物遗传学和适者生存的自然规律 是具有 生存 检测 的迭代过程的搜索算法 遗传算法以一种群体中的所有 个体为对象 并利用随机化技术指导对一个被编码的参数空间进行高效搜索 其中 选择 交叉和变异构成了遗传算法的遗传操作 初始种群编码 初始群 体个数的设定 适应度函数的设计 遗传操作设计 控制参数设定五个要素组 成了遗传算法的核心内容 与传统的搜索方法相比 遗传算法具有如下特点 1 搜索过程不直接作用在变量上 而是在参数集进行了编码的个体 此 编码操作 使得遗传算法可直接对结构对象 集合 序列 矩阵 树 图 链 和表 进行操作 2 搜索过程是从一组解迭代到另一组解 采用同时处理群体中多个个体 的方法 降低了陷入局部最优解的可能性 并易于并行化 3 采用概率的变迁规则来指导搜索方向 而不采用确定性搜索规则 对 搜索空间没有任何特殊要求 只利用适应性信息 不需要导数等其它辅助信息 适应范围更广 中国自古以来就有着传统中医药文明的发祥地的地位 中药是我国特有的资 源 但是中国本土中医学长期以来的发展并不是很大 在国际医学界就更不具 有很强的地位 多年的时间过去了 中药方剂的更新和发展并没有很大的变化 很多都还建立在很久以前就有的方剂基础之上 没有出现比较多的较新的方剂 应用遗传算法的数据挖掘系统在此情况下可以发挥着及其重要的作用 通过数 据系统能够在药对数据库的大量数据中 找到很多隐含的 未知的 并很有应 用价值的药对药组以及很多的有意义的药物组配的规则和模式 中药对数据挖 掘还将为中医方剂理论研究和中医临床用药研究提供重要模式参考 也为方剂 配伍理论研究 尤其是新药对 新药组发现研究提供新方法和现代技术手段 在系统进行数据挖掘过程中 为了减少对事务数据库的扫描 提高挖掘效 率 本文先把事务数据库转化成位图矩阵 然后再在此位图矩阵上挖掘有趣的 强双向关联规则 下面是对位图矩阵模型的描述 用 Ik k 为自然数 表示事务数据库中的一项 I1 I2 Ik In表示事 务数据库中的所有项 用 Tj i1 i2 ik in 表示事务数据库中的一个事务 ik对 第 6 页 共 24 页 应 Ik 占用 1 位 bit 当事务 Tj含有 Ik这项时 Tj 的 ik位为 1 否则为 0 所以事 务 Tj可以用位图 i1i2 ik in来表示 T1 T2 Tj Tm表示事务数据库 中所有的事务 T1 T2 Tj Tm都可以用位图 i1i2 ik in来表示 这 样所有这些位图就构成了事务数据库的位图矩阵 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三个项 事务 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 4基于遗传算法的双向关联规则挖掘算法基于遗传算法的双向关联规则挖掘算法具体流程及实现具体流程及实现 4 14 1位图矩阵实现位图矩阵实现 本设计使用的后台数据库为 SQL2000 用到的数据表为药物表和方剂表 I1 I2 I3 I4 I5 图 1 一个位图矩阵的例子 T1 T2 T3 T4 T5 T6 T7 第 7 页 共 24 页 位图矩阵的建立是在查询数据库中数据的基础上产生的 在查询数据库得到的位图矩阵中 行表示方剂 列表示此数据库中的药物 矩阵中的数据项由 1 和 0 表示 假如 R i j 1 R 表示位图矩阵 i 表示横坐 标 j 表示纵坐标 表示第 i 个方剂中含有第 j 位对应的药物 建立位图矩阵的 步骤如小 1 使用 sql 查询语句 通过查询方编号得到方剂表中的方剂的总数量 以此得到位图矩阵的行 也就相当于上一小节提到的事务 Tk String queryId select 方编号 from 方剂表 Class forName com microsoft jdbc sqlserver SQLServerDriver 通过 JDBC 建立数据库连接 Connection dbConn DriverManager getConnection dbURL userName userPwd 连接到数据库 提供相应的用户名 密码 Statement stmt dbConn createStatement ResultSet TYPE SCROLL SENSITIVE ResultSet CONCUR UPDATABLE 用 dbConn 连接创建 SQL 语句对象 ResultSet rsId stmt executeQuery queryId while rsId next drugId i rsId getString 1 把方编号存入数组 经过以上语句 此时得到了位图矩阵所需要的行的信息 即方编号 并把 此数据存放到名字为 drugId 的数组中 数组中存放的数据的个数即为方剂的数 量 也就是以后用到的位图矩阵的行数 2 接下来需要得到位图矩阵的列数和列所对应的药物的名称 String drugName new String 405 定义存放药名的数组 String queryName select 药名 from 药物表 定义查询药物表中药名的 sql 语句 ResultSet rsName stmt executeQuery queryName 定义存放查询得到的结果集的变量 int p 0 while rsName next if p 0 drugName i rsName getString 1 第 8 页 共 24 页 此句判断如果数组中没有数 则直接放入该数 else int j for j 0 j i 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 循环控制位图矩阵的行 根据每行为一个方剂 做为一个整体确 定每行中的数据项的值 String queryName1 select 药名 from 药物表 where 方编号 drugId i 申明 sql 语句 用于指定的方编号 查询得到对应方剂中所存放的药物 ResultSet rsName1 stmt executeQuery queryName1 申明 rsName1 结果集对象 每次查询所得到的值都存放在其中 方便以后 的数据取用 while rsName1 next temp l rsName1 getString 1 把每次查找出的药名存放在临时数组 temp 中 用于矩阵数据的确定 int k 第 9 页 共 24 页 for k 0 k l k 外层 for 循环用于控制数组 temp 的下标 for j 0 j 405 j 内层 for 循环用于控制数组 drugName 的下标 if temp k equals drugName j matrix i j 1 else if matrix i j 1 判断当 temp 数组和 drugName 数组的值相等时 对应的位图矩阵的值为字 符 1 当当前位图矩阵的值为字符 1 但是数组 temp 与 drugName 数组的不等 时 不作任何动作 当以上条件都不满足时 位图矩阵对应位置的值为字符 0 经过以上的程序段 就构造出了一个由 0 和 1 作为其每项值的矩阵 此矩 阵就是所要构建的位图矩阵 位图矩阵的构造完成 为以后的运算带来了不用 反复查询事务数据库的繁琐 提高了算法的效率 增加了运算的速度 4 24 2 编码编码 用遗传算法进行双向关联规则挖掘 编码是要解决的首要问题 编码方法 不仅决定了个体排列形式 而且决定了个体从搜索空间的基因型变换到解空间 的表现型时的解码方法 编码方法还影响到交叉 变异等遗传操作 由于前面 我们已经用位图矩阵来描述事务数据库 对双向关联规则的挖掘可以直接在位 图矩阵上进行 因此本文理所当然采用二进制编码 编码串的长度为事务数据 库中项的个数 由前面产生的位图矩阵可以知道 编码串的长度为 405 产生初始种群的代码如下 for i 0 i 50 i int t int Math random 28 随机产生每行字符数组 个体染色体 中 1 的个数 while true 如果是 0 就重新生成 if t 0 第 10 页 共 24 页 t int Math random 28 else break int tempLoc new int t int 数组装随机产生的数的下标数 即产生 1 的位置 for j 0 j 405 j radomDrug i j 0 for j 0 j t j int loc if j 0 loc int Math random 405 tempLoc j loc radomDrug i loc 1 else loc int Math random 405 for p 0 p j p if loc tempLoc p loc int Math random 405 p 0 if p j tempLoc j loc radomDrug i loc 1 产生随机数完毕 产生初始种群 也就是生成随机数的过程 首先用一个整形变量 t 存放每 次随机产生的 1 的个数 因为 通过查询药物数据库中方剂表可以得知 整个 第 11 页 共 24 页 方剂表中 所有方剂中的药物最多不超过 27 味 所以 需要用一个变量控制每 次随机产生的个体 随机数 中 1 的个数 在 t 产生之后 紧接着就是产生每 个个体中 1 的位置 在此处 代码中所体现的就是用用一个整形数组 tempLoc 存放 而数组中所存数据的个数则是上一步随机产生的变量 t 的值来控制 并 且在产生除第一个位置的时候 每产生一个位置后都首先与之前 tempLoc 数组 中的数判断 如果当前产生的数与 tempLoc 数组中的数相同 则要求重新随机 产生 直到没有重复为止 位置得到以后 所要做的就是对应位置上项的值给 赋值为 1 其余的赋值为 0 这样经过几层循环的运算后就得到了所要进行遗传 算法运算的初始种群了 4 34 3 适应度函数适应度函数 4 3 14 3 1 适应度函数设计适应度函数设计 遗传算法中使用适应度来度量种群中各个体在优化计算中可能达到或有助 于找到最优解的优良程度 适应度较高的个体遗传到下一代的概率就较大 适 应度函数直接影响问题求解的效率 本文挖掘的双向关联规则 要求规则中任一项的置信度都必须满足最小置 信度阈值 min conf 例如 C1 C2 Cn的双向关联规则须同时满足 P C1C2 Cn P C1 min conf P C1C2 Cn P C2 min conf P C1C2 Cn P Cn min conf 显然只需满足 P C1C2 Cn max P C1 P C2 P Cn min conf 即可 max P C1 P C2 P Cn 表示 P C1 P C2 P Cn 之中的最大值 于是 将适应度函数设计为 F rc1c2 cn count C1C2 Cn max count C1 count C2 count Cn 其中 rc1c2 cn为 C1 C2 Cn构成的双向关联规则 count C1C2 Cn 为 C1C2 Cn 的支持度计数 count C1 count C2 count Cn 分别为 C1 C2 Cn的支持度计数 max count C1 count C2 count Cn 表示 count C1 count C2 count Cn 中的最大值 4 3 24 3 2 适应度函数的实现适应度函数的实现 由以上的表达式可以得出 要计算种群中个体的适应度首先要计算出 count C1C2 Cn 和 max count C1 count C2 count Cn 它们两个作为计算 第 12 页 共 24 页 适应度函数的分子与分母 它们两个表达式对应于位图矩阵和种群的关系是以 下关系 count C1C2 Cn 的计算是通过把每个随机数 种群个体 与位图矩阵中 的每个方剂对应的数 每项个值所组成的数 进行与操作 计算其结果等于随 机数自身的次数 count Ci 是对在位图矩阵的第 i 列中所有 1 的累加 即计算在位图矩阵的第 i 列中为 1 的次数 max count C1 count C2 count Cn 则是表示所有累加值中 的最大数 由于在本设计中 使用的编程语言为 java 语言 为了方便随机个体与位图 矩阵中的每项的值进行比较 采用了位图矩阵以及得到的种群都是由 0 1 字符 组成的方式 并不是有真正的二进制数表示 因此 在进行上面提到的个体与 位图矩阵的每行的与操作时 是一项一项的比较 并不是真正意义上的与操作 在设计中进行与操作的方式是 判断个体中含有 1 的位置在位图矩阵的每行 对应位置是否也会为 1 如果判断为真就相当于进行的与操作等于它本身 则 count 需要加 1 如果某一位置上的 1 在位图矩阵中的对应位置为 0 则相当于进行的与操作不等于它本身 从而 count 不需要加 1 因此 第一 对位图矩阵中的所有值为 1 的位置进行记录 此处是用的 向量组进行记录 每个向量记录每行中的为 1 的位置 外循环控制行数 在 每次外循环时就给向量分配内存空间 内循环控制每行中的下标的移动 随着 下标的移动 查询到值为 1 的下标 并记录到向量中 Vector Mloc new Vector 1060 for i 0 i 1060 i Mloc i new Vector for j 0 j 405 j if matrix i j 1 Mloc i add j 第二 把产生的种群中的所有值为 1 的位置进行记录 在此处同样是通 过向量组进行的记录 每个向量记录每个种群个体中的 1 的位置 Vector Rloc new Vector 50 for i 0 i 50 i Rloc i new Vector 第 13 页 共 24 页 for j 0 j 405 j if radomDrug i j 1 Rloc i add j 第三 根据位图矩阵和初始种群中 1 的位置得到的两个向量数组 Mloc 和 Rloc 每次把 Rloc 数组中的一向量与数组 Mloc 中的所有向量比较 每次都 比较两个向量中所存放的 1 的位置 如果 Rloc 中的向量所存放的数在 Mloc 中的向量都有相同的数存在 即种群个体与位图矩阵每行所组成的数进行与操 作的值等于种群个体自身 则使用数组 count 记录下每次与操作都等于其自身 的次数 for i 0 i 50 i flag false count i 0 for p 0 p 1060 p for j 0 j Rloc i size j if Mloc p contains Rloc i get j flag true else flag false if flag count i 经过此段代码的运算 数组 count 存放了每个初始种群个体与位图矩阵进 行与操作等于其自身的次数 即得到了计算适应度函数的分子的值 第四 计算适应度的分母 即计算出每个初始种群个体中为 1 的位置在 位图矩阵对应列中出现的次数 然后通过 max 函数计算出刚计算出的次数中的 最大值 最后存放计算出的每个最大值在数组中 用于适应度的计算 for i 0 i 50 i 第 14 页 共 24 页 int countR new int 405 countR 存放随机数中每行中的为 1 的数所对应位图矩阵中此列的 1 个个 数 int k 0 for j 0 j 405 j if radomDrug i j 1 countR k countD j int max 0 for int tt 0 tt k tt 找到每行中为 1 的数在位图矩阵中对应列出现的个数的最大值 if max Math max max countR tt max countR tt countMax i max 第五 把上面计算得到的分子分母值进行计算 得到每个初始种群个体的 适应度 float fit new float 50 计算选择概率放在 fit 数组中 int fitD new int 50 计算适应度 并保存在 fitD 数组中 for i 0 i 50 i fit i float count i float countMax i fitD i int fit i 100 System out print fit i fitD i 计算出随机数的置信度 4 44 4 规则的提取规则的提取 由于挖掘的双向关联规则只要满足最小置信度阈值就是需要的规则 因此 在每一代种群计算适应度后 将其中适应度大于或等于 min conf 则把该个体放 入规则库中 放入时判断规则库中是否已存在该个体 如果存在 则不放入 在设计中 min conf 是通过输入框输入的到 并把值存放到变量 getV 中 for i 0 i getV 第 15 页 共 24 页 if z 0 for j 0 j 405 j rule h j radomDrug i j rfitD h fit i h else int k for k 0 k 50 k for j 0 j h j if gener k equals ruleStr j false continue else break if j h for j 0 j 405 j rule h j radomDrug i j rfitD h fit i h 4 54 5 遗传操作遗传操作 遗传操作主要包括选择 交叉和变异 1 选择 selection 本文的选择操作采用轮盘赌选择法 将个体的适应度与种群的总适应度 种群所有个体的适应度之和 相比 得到该个体的相对适应度 所有个体的 第 16 页 共 24 页 相对适应度之和为 1 使用个体的相对适应度来作为其在选择操作中被选中的 概率 每一轮选择产生一个 0 1 均匀随机数 将该随机数作为选择指针来确定 被选个体 适应度大的个体被选中的概率大 参与复制 交叉生成新一代种群 的机会就大 反映了自然界生物进化 物竞天择 适者生存 的自然法则 在本设计中 轮盘赌选择法的实现方式是 首先计算出总的适应度的和 sum 然后随机产生 1 到 sum 之间的数 根据产生的随机数得到对应的种群个 体 此方式正是模拟了遗传的特点 适应度大的被选中的几率就大 反之被选 中的几率就小 下面此循环就是计算适应度的总和 for i 0 i 50 i sum fitD i 以下代码则是轮盘赌算法的实现 for i 0 i n break else m j gener i Ch m 最后 把根据轮盘赌算法选中的种群个体存放到 gener 数组中 2 交叉 crossover 实际应用的事务数据库中项的个数往往比较大 即编码串比较长 为了促 进解空间的搜索 防止过早地收敛 本文交叉操作的交叉点数由 确定 其中的 n 为遗传算法的一个输入参数 在运行时设置 可以设置为 10 20 等 交叉位 随机产生 例如 图 1 所对应的事务数据库 如果 n 设置成 10 则为单点交叉 对于父代个体 1 11010 和父代个体 2 01001 若随机产生的交叉点是 3 则交叉后产生的子代个体 1 和子代个体 2 分别为 11001 01010 染色体的交叉的实现代码如下 第 17 页 共 24 页 while i jcha 2 m int Math random 50 选择进行交换的两个体的下标 m n int ra int Math random 50 n m ra 50 p int Math random 405 p 值为染色体交换位 CharSequence rt1 gener m subSequence p gener m length 第 p 位后的染色体交换 CharSequence rt2 gener n subSequence p gener n length gener m gener m replace gener m subSequence p gener m length rt2 gener n gener n replace gener n subSequence p gener n length rt1 i 3 变异 mutation 因为初始种群的产生是随机的 所以事务数据库中所有的项并不一定都出 现在初始种群中 这会造成部分规则的遗漏以及过早收敛 因此本文进行变异 操作时 先以一概率随机选择个体 选中后 随机产生变异位 对变异位作翻 转操作 变异的实现 在本设计中是通过随机产生需要进行变异的种群个体和选中 个体中需要变异的的染色体位置 然后把此位置对应的值进行翻转 把 1 变 成 0 或者把值为 0 的变成 1 for j 0 j byg j p int Math random 405 个体中染色体变异 for k 0 k 10 k p1 k int Math random 405 p 405 int p2 int Math random 50 产生变异的个体的位置 char bianyi gener p2 toCharArray for k 0 k 10 k if bianyi p1 k 1 bianyi p1 k 0 else 第 18 页 共 24 页 bianyi p1 k 1 for k 0 k 405 k 变异后再转换成字符串 if k 0 gener p2 String valueOf bianyi k else gener p2 String valueOf bianyi k 4 64 6 算法流程算法流程 5 5测试测试 本论文将上述方法用于中药配伍规律的研究中 从大量古今中药方剂中挖 掘药对药组 药对是临床上相对固定的两味药物的配伍形式 是中药配伍中的 N 开始 产生初始种群 计算适应度 把符合要求的个体放入规则 库 达到预设世代数 选择 交叉 变异 结束 Y 图 2 基于遗传算法的双向关联规则挖掘算法流程图 第 19 页 共 24 页 最小单位 药组是临床上相对固定的两味药物以上的配伍形式 也可以把它看 作不限于两味药物的特殊药对 这些药对药组对于研究中药配伍规律具有重要 意义 本文实验基于脾胃类方剂库 该方剂库含 1060 首方剂 涉及 405 味药 实 验采用了基于遗传算法的双向关联规则挖掘算法来寻找药对药组 此系统具有的数据挖掘功能 其中有两个选择的模式 一是一般模式状态 下的双向关联规则挖掘 用户可以输入相应的最小置信度和遗传的代数 二是高级设置模式下的双向关联规则挖掘 用户可以输入初始种群个数 遗传 代数 最小置信度和变异率四个参数 图 3 一般模式状态下的双向关联规则挖掘界面 图 4 高级设置状态下的双向关联规则挖掘界面 第 2