分类号:TP312 U D C:D10621-408-(2007) 5973-0
密 级:公 开 编 号:2003031286
成 都 信 息 工 程 学 院
学 位 论 文
基于遗传算法的中药药对挖掘系统的设计与实现
论 文 作 者 姓 名 :
吴 金 伟
申 请 学 位 专 业 :
计算机科学与技术
申 请 学 位 类 别 :
工学学士
指导老师姓名(职称):
曾令明(讲师)
论 文 提 交 日 期 :
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 背景
我国作为最大的中药材资源国,有着传统中医药文明的发祥地的地位,但是
如今正面临着诸多挑战。我国,在世界的中药市场上却未能占有基本的主导地位。
反而日本、韩国等国家成功地利用现代数据挖掘科技把中药行业发展成现代产业,
占据了国际市场相当的份额,因此,继承和发展中医药不仅是中医界也是全国其
他科研院校和科研机构的重要课题。中药对数据挖掘就是利用药对数据库从大量
的中药对中抽取隐含的、未知的、有意义的药物组配模式。中药对数据挖掘将为
中医方剂理论研究和中医临床用药研究提供重要模式参考,也为方剂配伍理论研
究,尤其是新药对、新药组发现研究提供新方法和现代技术手段。
1.2 意义
关联规则是数据挖掘中的重要技术之一,它能反映在事务数据库中数据项之
间同时出现的规律,并发现不同数据项之间的联系。关联规则通过量化的数字描
述数据项 A 的出现对数据项 B 的出现产生的影响。例如在大型商场中牛奶的销
售对面包的销售的影响,发现这样的规则不仅可以应用于商品货架设计、货存安
排,而且可以根据购买模式对用户进行分类,制定相应商务决策、销售策略。
由于关联规则挖掘具有重要的现实意义,吸引了许多学者的研究,提出了众
多的关联规则挖掘算法。目前,所有的关联规则挖掘算法都是基于支持度-置信
度框架理论,具有较多的局限性。本文通过分析这些不足之处,引入双向关联规
则的概念,实现了基于遗传算法的双向关联规则挖掘算法。
2 理论基础
2.1 关联规则及存在的问题
关联规则是形如 A=>B 的蕴涵式,挖掘关联规则分为两步:第一步是识别所
有的频繁项集,即支持度不小于用户指定的最小支持度的项集;第二步是从频繁
项集中构造其置信度不低于用户给定最小置信度的规则,即强规则。这种基于支
持度-置信度框架理论的关联规则挖掘方法存在如下问题:
(1)不能有效地发现低支持度高置信度的有趣规则
基于支持度-置信度框架理论的关联规则挖掘方法找到的强规则必须同时满
足最小支持度阈值和最小置信度阈值,但有时人们感兴趣的规则往往是低支持度
高置信度的[8]。例如,超市中两物品 A 和 B,它们的销售量虽然很低,但经常
是同时被顾客购买,管理人员希望将这种低支持度高置信度的规则找出来。
(2)不能确定“相互依赖”的规则
关联规则反映 A、B 同时出现的概率和 A 出现的条件下 B 出现的条件概率。
这样的规则只能确定 A 对 B 的“依赖”,不能同时确定 B 对 A 的“依赖”,但很