（计算机应用技术专业论文）关联规则算法研究及其在中医药数据挖掘中的应用.pdf

硕士论文关联规则算法研究及其在中医药数据挖掘中的应用 摘要 数据挖掘可以发现蕴藏在海量数据中的潜在知识，是当今最活跃的研究应用领域。 关联规则是数据挖掘中的一个主要研究分支，侧重于寻找数据之间的依赖关系。关联规 则挖掘的核心问题是如何提高挖掘算法的效率，以及如何更好的应用于特定领域中。 中国传统医学是我国优秀的民族文化遗产，中医理论在长期的医疗实践中积累了大 量数据信息，挖掘出其中蕴含的宝贵经验，是一项极有价值的研究工作。 本文重点是对关联规则挖掘算法的研究，基于直接频繁闭超集改进算法的设计以及 在中医药数据挖掘领域中的应用。论文研究的主要问题及相关成果如下： 在算法研究方面，本文研究了频繁项集和频繁闭项集的挖掘算法。频繁项集的算法 研究中，分析并实现了关联规则频繁项集挖掘的算法一a p r i o r i 算法和f p g r o w t h 算法。 针对频繁项集挖掘效率低且数量大的问题，研究了频繁闭项集的挖掘算法，并引入直接 频繁闭超集的概念，在c h a r m 算法的基础上，设计了一种能够快速检测候选频繁闭项 集闭合性的改进算法c 认b d 算法，最后在标准数据集上进行实验比较，表明了 c i a b d 算法的快速有效性。 在算法应用方面，利用中医疫病医案信息资源，经过数据预处理，分别采用关联 规则中频繁项集与频繁闭项集算法进行中医药挖掘实验，发现频繁闭项集算法在中医药 数据挖掘中相对更有优势。通过对关联规则结果的分析，表明挖掘的结果符合中医相关 理论，具有较好的临床参考价值。 关键词：数据挖掘，关联规则，中医药，频繁项集，频繁闭项集，直接频繁闭超集 垒竺塑竺一一 堡圭丝塞 _ - 一一一 一。r u a b s t r a c t d a t am i n i n gc a l lf i n do u tt h ep o t e n t i a lv a l u a b l ei n f o r m a t i o nf r o mm a s s i v ed a t a i ti so n e o ft h em o s ta c t i v er e s e a r c hf i e l d s a s s o c i a t i o nr u l ei sam a i nb r a n c hi nt h ed a t a m i n i n gf i e l d ， w h i c hf o c u s e so nf i n d i n gi n t e r e s t i n gd e p e n d e n tr e l a t i o n sb e t w e e n i t e m so fd a t a b a s e t h em a i n i s s u e so fa s s o c i a t i o nr u l ea r eh o wt oi m p r o v et h ee f f i c i e n c yo f m i n i n ga l g o r i t h m sa n dh o wt o a p p l yi ti ns p e c i f i ca p p l i c a t i o na r e a t r a d i t i o n a lc h i n e s em e d i c i n e ( t c m ) i st h eo u t s t a n d i n gc u l t u r a lh e r i t a g eo ft h ec h i n e s e n a t i o n , c o n t a i n i n gv a l u a b l ee x p e r i e n c ea n dt h e o r e t i c a lk n o w l e d g e c h i n e s em e d i c i n et h e o r y h a sa c c u m u l a t e dal a r g ea m o u n to fd a t ai n f o r m a t i o ni nl o n g t e r mm e d i c a lp r a c t i c e i t ，sv e r y m e a n i n g f u lt om i n et h ep r e c i o u sc l i n i c a lk n o w l e d g eb ya p p l y i n gd a t am i n i n gi n t oa b o v ed a t a t h i sp a p e rs t u d i e st h ea l g o r i t h m sf o rm i n i n ga s s o c i a t i o nr u l e s ，d e s i g n saf a s t e ra n d m o r e e f f i c i e n ta l g o r i t h mb a s e do nd i r e c tf r e q u e n tc l o s e ds u p e r s e t s ，a n da p p l i e sa s s o c i a t i o nr u l e si n t h ef i e l do ft c m m a i nw o r ki sa sf o l l o w s ： f o ra l g o r i t h mr e s e a r c h , t h i sp a p e ra n a l y z e sa l g o r i t h m sf o rm i n i n gf r e q u e n ti t e m s e t sa n d f r e q u e n tc l o s e di t e m s e t s f i r s t l yc o m p a r et w oc l a s s i c a la l g o r i t h m sf o r m i n i n gf r e q u e n t i t e m s e t s ，n a m e l ya p f i o r ia l g o r i t h ma n df p - g r o w t ha l g o r i t h m a n dt h e na n a l y z em i n i n g a l g o r i t h m sf o rm i n i n ga l lf r e q u e n tc l o s e di t e m s e t s i no r d e rt oi m p r o v et h ep e r f o r m a n c eo f c h a r m a l g o r i t h m ，d e s i g nan e wa l g o r i t h mn a m e dc i a b d a l g o r i t h mb yu s i n gt h ec o n c e p t o fd i r e c tf r e q u e n tc l o s e ds u p e r s e t s c i a b da l g o r i t h mc a n r a p i d l yc h e c kw h e t h e rc a n d i d a t e f r e q u e n t i t e m s e t sa r e c l o s e d f i n a l l y ，c i a b da l g o r i t h mi sc o m p a r e dw i t hc h a r m a l g o r i t h mo nt h es t a n d a r dd a t as e t s ，a n dt h er e s u l t sd e m o n s t r a t et h a tc i a b d a l g o r i t h mi s f a s t e ra n dm o r ee f f i c i e n t f o ra p p l i c a t i o n ，a l g o r i t h m sb a s e do nf r e q u e n ti t e m s e t sa n df r e q u e n tc l o s e di t e m s e t sa r e u s e dt of i n do u tt h ea s s o c i a t i o no ft r a d i t i o n a lc h i n e s em e d i c i n e e x p e r i m e n t sa r ec a r r i e do n t h ed a t a s e to fe p i d e m i cd i s e a s ec a s e s a l g o r i t h mb a s e do nf r e q u e n tc l o s e di t e m s e t ss h o wi t s a d v a n t a g eo v e rm i n i n gi nt c m b ya n a l y z i n gt h em i n e dr u l e s ，s o m ev a l u a b l ea n dp r e c i o u s t r e a t m e n te x p e r i e n c e0 ft c mc a nb eo b t a i n e d , w h i c hh a sg o o dc l i n i c a lr e f e r e n c ev a l u e s k e yw o r d ：d a t am i n i n g ，a s s o c i a t i o nr u l e s ，t r a d i t i o n a lc h i n e s em e d i c i n e ，f r e q u e n t i t e m s e t s ，f r e q u e n tc l o s e di t e m s e t s ，d i r e c tf r e q u e n tc l o s e ds u p e r s e t s 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 銎函辞叫年6 月汀日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 协 j 年6 月n 日 硕士论文关联规则算法研究及其在中医药数据挖掘中的应用 1 绪论 1 1 论文的研究背景和意义 在数据不断积累增加的今天，我们已经不再为海量数据的存储、统计和查询而大伤 脑筋，伴随着人们的是对数据的理解度的降低，如何对数据进行更高层次的分析、理解 和利用，成为了人们的强烈需求。我们对数据的了解掌握永远无法赶上数据升级的速度， 隐藏在这些数据后的是信息具有潜在价值的信息，这些信息如何被显现出来或者被 开发利用，正逐渐引起人们的重视。 信息的需求带来了对数据分析工具的需求，采用数据挖掘工具进行数据分析，可以 发现重要的数据模式。知识发现( k d d ) 和数据挖掘( d a t am i n i n g ) 技术应运而生并蓬勃发 展，填平了数据和信息之间的鸿沟。数据挖掘是适应信息处理新需求和社会发展各方面 的迫切需要而发展起来的一种新的信息分析技术，可以根据现有的数据预测未来的发展 趋势，智能地、自动地将待处理数据转化为对用户有价值的信息和知识。 数据挖掘所采用的方法包括关联规则、分类预测、聚类分析、趋势分析、孤立点分 析、演变分析和偏差分析等【l 】。其中，挖掘关联规则在商业等领域的成功运用，使关联 规则成为数据挖掘中最成熟、最主要、最活跃的研究内容。关联规则是数据挖掘中的一 个主要研究分支，用于表示数据库中诸多事务属性间隐含的有趣联系。而关联规则挖掘， 则是利用数据，通过关联规则算法寻找数据之间的依赖关系。高效的关联规则挖掘算法 能较快地找出数据集合中全部依赖关系，以便挖掘所需要的关联规则，目前大多数的关 联规则研究都集中在算法研究和算法应用上。 中国传统医学是我国一项优秀的民族文化遗产，其历史悠久，理论独特，疗效卓著， 其承载着中华民族几千年的宝贵经验和理论知识。中医理论在长期的医疗实践中积累了 大量的数据信息，其中蕴含着丰富的医学宝藏，对这些精髓的总结不仅能丰富中医理论 体系，更是推动中医学术发扬光大的有效手段，也必将更多地发挥其对全人类医疗保健 的重要作用。在当前高速信息化的时代背景下，如何将现代信息技术与中医信息资源相 结合，探索中医信息中的奥妙，为人们提出了新的研究方向。 数据挖掘所擅长的正是从海量的数据中寻找有意义的模式、知识，完成普通人不能 完成的任务，是分析中医海量数据所需要的技术。利用数据挖掘技术，对中医数据进行 科学的处理，运用其相关算法对中医中理法方药进行挖掘，将进一步加速中医知识更 新的步伐，为构建现代中医学理论体系奠定坚实的基础。 “十一五 期间，在国家科技支撑计划的指导下，我们与南京中医药大学合作承担 了国家科技攻关计划“基于信息挖掘技术的中医临床诊疗经验及传承方法研究”的分课 题“中医临证经验分析挖掘方法研究 ( 编号：2 0 0 4 b a 7 2 l a o l h 0 4 ) 。对于中医的病案， l i 绪论硕士论文 首先采用基于关联规则的方法，分析挖掘了症状一方药之间、基本症状一证型之间、证 型一方药之间以及中药配伍之间的多重关联关系，分析结果与中医的经验的吻合度；其 次，采用基于偏差检测的方法，挖掘中医具有特色的个性化诊断经验；最后，采用隐结 构模型模拟老中医诊断。本论文正是基于研究关联规则的方法，分析中医药存在的关联 关系。 中医药领域的数据挖掘是一个有着美好前景又充满挑战的研究方向，应用数据挖掘 技术进行中医药方面的研究，不仅能够加速中医药知识的更新和创新，更能推进中医药 的产业化和国际化进程【4 引。相信随着数据挖掘技术的广泛应用，研究方法的不断改进， 数据挖掘在中医药领域的应用将更为广泛和深入。 1 2 国内外的研究发展现状 1 2 1 数据挖掘技术发展现状 在1 9 8 9 年举行的第1 1 届国际联合人工智能学术会议上，知识发现( k d d ) 和数据挖 掘( d m ) 的概念被首次提出。数据挖掘是知识发现的有效手段，是从大量数据中提取出可 信的、新颖的、有效的，并能被人理解的模式的高级处理过程。数据挖掘要经过数据采 集、预处理、数据分析、结果表示等一系列过程，如图1 1 所示： 图1 1 数据挖掘的处理过程 数据挖掘是一个跨学科研究领域，它的研究涉及广泛，如图1 2 所示，包括数据库 技术、人工智能、机器学习和统计分析等学科。同时，哲学、心理学等学科也为数据挖 掘的发展导引方向。数据挖掘采用的技术十分广泛，如神经网络、模糊集理论、知识表 示、归纳逻辑程序设计和高性能计算等。对于不同数据类型或不同应用，数据挖掘系统 还可集成空间数据分析、信息提取、模式识别、图象分析、信号处理、计算机图形学、 w e b 技术、经济、商业、生物信息学和心理学等领域的技术。因此，数据挖掘被认为是 信息产业最有前途的交叉学科【j j 。 2 硕士论文关联规则算法研究及其在中医药数据挖掘中的应用 数据挖掘是一个年轻而又活跃的应用领域【2 】【3 】，它的发展得益于各行各业对信, g 矢l l 识资源的巨大需求，从商业管理、生产控制、市场分析至l l l - 程设计、科研探索等等。数 据挖掘的应用从商业零售业开始，以银行、保险等金融领域为主，现阶段已扩展到网站 的生物医学信息、网络搜索引擎、文本数据挖掘等广阔的应用领域中。 藩、 震、 一萋 篓妻望翌赫 鍪要篓! 嵩垂袁； 图1 2 数据挖掘的学科领域 由于挖掘任务和挖掘方法的多样性，数据挖掘提出了许多新的挑战性的课题。设计 标准化的数据挖掘语言，开发高效有用的数据挖掘方法，建立交互集成的数据挖掘环境， 解决大型数据挖掘技术应用问题，是目前数据挖掘研究和开发人员所面临的主要问题。 数据挖掘被认为是最重要的前沿学科之一，它引起了人们的广泛关注，对它的研究正在 蓬勃发展。针对数据挖掘现在面临的主要问题，数据挖掘的研究应用最主要有以下几个 方向【4 】： ( 1 ) 与数据仓库等技术结合。数据仓库从多个数据源收集信息存储，存放在一个一 致的模式下，可以为数据挖掘提供经过滤化的、完整的数据资源。与数据仓库相结合， 数据挖掘能够深入到多维数据的任意一维，从而在不同的抽象层上找到用户感兴趣的形 式，由此增加了数据挖掘与数据仓库系统的用途。 ( 2 ) 数据挖掘语言的标准化和形式化。标准的数据挖掘语言和数据挖掘的标准化工 作将有助于数据挖掘的系统化开发，改进多个数据挖掘系统和功能间的互操作，促进数 据挖掘系统的发展。 ( 3 ) 复杂数据类型挖掘。复杂数据类型的挖掘是挖掘中的一项非常重要而极富挑战 性的课题，比如地理空间挖掘、多媒体挖掘以及文本挖掘等等。虽然目前已取得了一些 成果，但是它们与实际应用的需要仍存在很大的距离，需要进一步的研究，尤其是把针 对复杂数据类型的现代数据分析技术与数据挖掘方法集成起来研究。 ( 4 ) 高性能的数据挖掘。在传统数据挖掘方法的基础上，高效性和可伸缩性是目前 数据挖掘算法的焦点，随着数据量不断地激增，并行的、分布式的以及增长式的数据挖 掘技术的发展，研究高性能的数据挖掘这种趋势将会得到有效发展。 3 1 绪论 硕士论文 ( 5 ) 可视化数据挖掘。数据内容和挖掘结果的可视化有助于用户理解和评估挖掘结 果，从而对数据挖掘进行相应的调整。对交互式的挖掘来说，开发易用与易看的挖掘工 具是一个很有发展空间的领域。 ( 6 ) 数据挖掘的应用。将数据挖掘技术应用于现实世界，是一个非常重要的课题。 1 2 2 数据挖掘在中医药应用领域研究现状 新世纪的到来，中医药学要现代化、国际化，其前提是对已有的中医药理论和经验 科学地继承、更好地发扬。其中当代中国名老中医的诊疗经验，是他们在临床实践中与 中医学理论结合、突破、创新的结果，包含了中医基础理论的原则和中医的独创心得或 见解，是发展中医药学的宝贵财富。因此当代中医学术思想临证经验的继承不仅能丰富 中医药学的理论体系，还能对整个医学科学的发展产生巨大的推动作用。现阶段，数据 挖掘在中医药领域中的研究主要有以下几方面【5 】【4 3 】【删： ( 1 ) 研究中医药信息化； ( 2 ) 研究中医药专家系统； ( 3 ) 研究中医药基础理论现代化； ( 4 ) 研究中药材的开发； 除了在上述方面的中医药研究领域中应用，数据挖掘技术在研究中医药信息数据仓 库的开发，中医病证与复方组方的关系，以及中医症候与现代医学临床表现之间关联的 关系研究等方面都可以得到广泛的应用。 应用数据挖掘中最常用的关联规则技术，挖掘数据间的有趣联系或相关关系，也是 今年来中医药数据挖掘领域中的热门。应用关联规则进行中医药数据挖掘的主要研究 有： ( 1 ) 中医药文献挖掘； ( 2 ) 中医证候分析； ( 3 ) 中药复方挖掘； ( 4 ) 药物配伍规律； ( 5 ) 功效分类； 1 3 论文的研究内容和组织结构 本论文的研究工作重点是研究关联规则挖掘算法，探讨算法优化问题，并实现关联 规则挖掘算法在中医药数据挖掘领域中的应用。本文主要由以下几个章节组成： 第一章绪论。介绍了本论文的研究意义和相关背景，以及论文相关的国内外研究 发展现状，最后给出了论文的整体组织结构。 第二章数据挖掘及关联规则技术。论述了数据挖掘和关联规则技术的相关内容， 4 硕士论文 关联规则算法研究及其在中医药数据挖掘中的应用 并针对中医药数据挖掘进行了研究。 第三章频繁项集挖掘算法及分析。首先论述了频繁项集挖掘算法的发展状况，然 后分析实现- j a p r i o r i 算法和f p g r o w t h 算法，并客观分析了频繁项集在中医药数据挖掘中 的应用情况。 第四章基于直接频繁闭超集的改进算法及分析。研究了关联规则挖掘中频繁闭项 集及其挖掘算法，在介绍了频繁闭项集基本概念的基础上，详细研究了c h a r m 算法及 其优化，然后引入直接频繁闭超集的概念，设计了c i a b d 算法，最后通过实验客观分 析了算法的性能。 第五章关联规则在中医药领域中的应用。运用关联规则的挖掘算法对中医疫病医 案进行挖掘，得到有价值的关联规则结果，并对结果进行了分析，展示了数据挖掘中的 关联规则与中医药理论的结合应用。 第六章总结与展望。对论文的工作进行了总结，并对未来研究发展做了展望。 5 2 数据挖掘及关联规则技术硕士论文 2 数据挖掘及关联规则技术 2 1 数据挖掘概述 2 1 1 数据挖掘的概念 数据挖掘( d a t am i n i n g ，d m ) 又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，k d d ) ，是从大量数据中提取或“挖掘有趣知识的过程【lj 。 从技术上来讲，数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的数 据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程【5 】。 这个定义包含以下四个层次的含义【8 l ： ( 1 ) 原始数据必须是真实的、大量的； ( 2 ) 发现的知识是用户感兴趣的、潜在有用的； ( 3 ) 发现的知识要可接受、可理解、可运用； ( 4 ) 发现的知识并不是要求放之四海皆准，所有发现的知识都是相对的，是有特定 前提和约束条件的，是面向特定领域的。 从商业角度来看，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据 进行探索和分析，揭示隐藏的、未知的或验证己知的规律性，并进一步将其模型化，以 获得辅助商业决策的关键性数据的方法。 数据挖掘是利用各种分析方法和分析工具在大规模海量数据中建立模型并发现数 据间关系的过程，这些模型和关系可以用来做出决策和预测。通过数据挖掘，可以从数 据中提取有趣的知识、规律或高层信息，并可以从不同角度观察或浏览。发现的知识可 以用于决策支持、信息管理、过程控制、查询优化等等。简而言之，数据挖掘是一类深 层次的数据分析过程。 2 1 2 数据挖掘功能 数据挖掘从数据分析入手，通过预测未来趋势及行为，做出前瞻的、基于知识的决 策。数据挖掘功能用于在指定的数据挖掘任务中寻找模式类型。目前数据挖掘功能及可 发现的模式类型有以下六个方面【1 】【9 】。 ( 1 ) 概念描述 数据的特征化( d a t ac h a r a c t e r i z a t i o n ) 和数据区分( d a t ad i s c r i m i n a t i o n ) 均为数据的概 念描述( c o n c e p td e s c r i p t i o n ) ，就是用汇总的、简洁的、精确的方式描述每个类对象。数 据特征化是对目标数据的一般特征或特性的汇总，用于描述某类对象的共同特征。数据 区分是将目标对象的一般特性与一个或多个对比类对象的一般特性比较，用于描述不同 类对象之间的区别。 6 硕士论文关联规则算法研究及其在中医药数据挖掘中的应用 ( 2 ) 关联规则 关联规贝j j ( a s s o c i a t i o nr u l e ) 是指从大量数据中发现项集之间有趣的联系、相关关系 或因果结构，以及项集的频繁模式。关联规则目的是找出数据库中隐藏的关联网，展示 了属性值频繁地在给定数据集中一起出现的条件。 数据集中存在着非常多的关联规则，人们可以结合专业领域知识，选取适当挖掘方 法抽取那些满足一定的支持度和置信度的关联规则。人们津津乐道的“啤酒和尿布 的 故事就是从超市购物篮中分析出的关联规则。 ( 3 ) 分类和预测 分类( c l a s s i f i c a t i o n ) 是找出一组能够描述数据集合典型特征的模型或函数，以便能够 识别未知数据的归属或类别【l o l 。分类实际上是从数据对象中发现共性，将数据对象分成 不同类别的过程。通过对训练数据进行分析，使用这些数据的某些特征属性，给出每个 类别的准确描述，然后利用这些分类规则对其他数据进行分类。 预测( p r e d i c t i o n ) 是利用历史数据等训练样本建立模型，再运用最新数据作为输入值， 获得未来变化的趋势或评估给定样本可能具有的属性值或值的范围。 ( 4 ) 聚类分析 聚类分析( c l u s t e r i n ga n a l y s i s ) 是将物理或抽象对象的集合分组成为由类似的对象组 成的多个类的过程【l o l 。简单地说，就是识别出一组聚类规则，将数据聚合成若干类，各 类间数据对象相似程度很低，但在某一类内部，数据的相似性很高。 ( 5 ) 孤立点分析 孤立点( o u t l i e r ) 是指一些与数据的一般行为或模型不一致的对象。大部分的数据挖 掘方法将孤立点视为噪声或异常而丢弃，但是对于某些应用( 如欺骗检测) ，罕见的事 件可能比正常出现的事件更有趣，孤立点的数据可能更具有价值，更需要进行孤立点数 据分析。 ( 6 ) 演变分析 演变分析( e v o l u t i o na n a l y s i s ) 描述事件或对象的行为随时间变化的规律或趋势，并 对此来建模。根据时间相关数据的特征化、区分、关联、分类或聚类分析的不同特点， 它主要包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 2 2 关联规则技术 关联规贝j j ( a s s o c i a t i o nr u l e ) 是数据挖掘研究领域的一个重要分支，是发现大量数据 中项集之间有趣的关系或相关联系的技术方法。该问题由r a g r a w a l 等人【1 1 j 于1 9 9 3 年 在对市场购物篮问题进行分析时首次提出，用以发现商品销售交易中的顾客购买模式。 医学研究者可以从成千上万份病例中找出某些疾病的共同特征，或发现某位著名老医生 的治病思路，从而为治愈疾病提供帮助。 7 2 数据挖掘及关联规则技术硕士论文 关联规则是反映项集之间的依赖或相互关联，若两项或多项属性之间存在关联，那 么其中某项的属性值就能够依据其他属性值进行预测。在商业应用中关联规则最典型的 例子是“啤酒与尿布 的故事。某家超市将尿布和啤酒赫然摆在一起出售，这个奇怪的 举措使尿布和啤酒的销量双双增加，这是由于一些年轻的父亲在为小孩子买尿布时随手 带回了他们喜欢的啤酒。按常规思维，购买尿布与购买啤酒毫不相关，若不是借助关联 规则技术对大量交易数据进行挖掘分析，是不可能发现隐藏在数据内这一有价值的规律 的。通过发现放入购物篮中的不同商品之间的关系，分析顾客的购买习惯，了解哪些商 品频繁的被顾客同时购买，这种关联的发现可以有助于零售商制定营销策略，进行市场 运作，以刺激内需，促进经济。 目前，广大学者和研究人员对关联规则挖掘进行大量研究，大致涉及经典频繁项集 挖掘的高性能算法的研究，以及拓展关联规则的概念和应用范围等，也已经取得了不少 的研究成果。关联规则形式简洁，易于理解并且可以有效的发现数据间的重要关系，因 此，从大型数据库中挖掘关联规则的问题已经成为近年来数据挖掘研究领域的热点问 题。 2 2 1 关联规则的定义 ( 1 ) 项集( i t e m s e t ) 。( 七= 1 , 2 ，m ) 称为数据项，数据项集是由数据库中m 个不同项 组成的集合，即i = i if 2 ，) 。包含k 个数据项的项集称为k 一项集，k 表示项集中项 的数目。 ( 2 ) 事务。d 为事务数据库，t 。( k = 1 , 2 ，刀) 称为事务，每项事务是由数据项集中的 若干项组成的集合，即“= 饥。气：，k ) ci ，每一个事务有一个唯一的标识符，耐与之 对应。 ( 3 ) 关联规则。若z ，y 为项集，关联规则是形如xjy 的蕴涵式，其中xci ， yci ，并且xn y = f 2 j 。表示项集x 在某一事务中出现时，一定程度上也会导致项集y 在同一事务中出现。 ( 4 ) 支持度( s u p p o r t ) 。关联规则的支持度是表示规则模式出现可能性的度量，反映 了规则的支持率。事务数据库d 中支持项目集x u 】，的事务数称为关联规则xjy 的支 持度，它可以等价于项集在数据集中出现的频率。即： s u p p o r t ( xjy ) = p ( x u y ) ( 5 ) 置信度( c o n f i d e n c e ) 。置信度表示规则的可信赖程度，即正确程度。表示为在出 现x 的事务中， 】，也出现的条件概率。即： c o n f i d e n c e jy ) ：p ( i xu d x1 0 0 = p ( y ix ) p aj 一般的，挖掘系统所生成的关联规则要计算支持度和置信度，且用一个蕴含式和两 8 硕士论文 关联规则算法研究及其在中医药数据挖掘中的应用 个值来唯一标识特定的关联规则。 ( 6 ) 强关联规则。为了挖掘出有意义的关联规则，一般需要用户给定两个阈值：最 小支持度阈值( m i n s u p ) 和最小置信度阈值( m i n c o n f ) 。设关联规则xjy ，若 s u p p o r t ( xjy ) m i n s u p 且c o n f i d e n c e ( xjy ) m i n c o n f 成立，即规则同时满足最小 支持度和最小置信度阈值，则称工jy 为强关联规则。 ( 7 ) 频繁项集( f r e q u e n ti t e m s e t ) 。频繁项集是在数据集中出现频率较高的项集，可以 使用最小支持度度量，即支持度不小于最小支持度阈值的项集称为频繁项集。 2 2 2 关联规则的分类 对于关联规则，可以根据不同的标准从不同的角度进行分类，常见的有以下几种分 类方法： ( 1 ) 根据规则中所处理的变量的类型分类，关联规则可分为布尔型和量化型。布尔 型关联规则是指关联规则处理的变量值都是离散的、种类化的。量化型关联规则是指规 则对数值量化的字段进行处理，描述量化的项与属性之间的关联。例如： 症状= “脉细，苔薄舌暗红 j 中医辨证= “肝肾亏虚，是布尔型关联规则。 年龄= “6 0 钙摄入量= “4 0 0 m g 天j 病症= “骨质疏松，是量化型关 联规则。 ( 2 ) 根据规则中涉及的数据的维数分类，关联规则可分为单维关联规则和多维关联 规则。如果关联规则中的项或属性每个只涉及一个维，那么它是单维关联规则 ( s i n g l e d i m e n s i o n a la s s o c i a t i o nr u l e ) 。例如症状= “发热 j 症状= “汗出”，是一个单维 关联规则，因为它只涉及一个维症状。 如果规则涉及两个或多个维，则它是多维关联规贝, l j ( m u l t i d i m e n s i o n a la s s o c i a t i o n r u l e ) 。如第一条中的量化关联规则同时也是一个多维关联规则，因为它涉及年龄、摄入 量、病症三个维。 ( 3 ) 根据规则中数据的抽象层次分类，可以分为单层关联规则和多层关联规则。有 些挖掘关联规则的方法可以在不同的抽象层发现规则。例如，假定挖掘的关联规则集包 含下面规则： 病症= “外感发热 方剂= “桂枝汤 病症= “外感发热j 方剂= “桂枝1 5 6 9 + 炙甘草1 0 4 9 + 生姜1 5 6 9 在这两个例子中，购买的商品涉及不同的抽象层( 即“桂枝汤 在比“桂枝1 5 6 9 + 炙甘草1 0 4 9 + 生姜1 5 6 9 高的抽象层) ，我们称所挖掘的规则集由多层关联规则 ( m u l t i l e v e la s s o c i a t i o nr u l e ) 组成。反之，如果在给定的规则集中，规则不涉及不同抽象层 的项或属性，则该集合包含单层关联规贝, u ( s i n g l e 1 e v e la s s o c i a t i o nr u l e ) 。 ( 4 ) 根据规则所挖掘的模式类型分类，可以分为频繁项集挖掘、序列模式挖掘和结 9 2 数据挖掘及关联规则技术硕士论文 构模式挖掘。 ( 5 ) 根据挖掘模式的完全性分类，可以挖掘频繁项集的完全集、闭频繁项集和极大 频繁项集，也可以挖掘被约束的频繁项集、近似的频繁项集、接近匹配的频繁项集、最 频繁的k 个项集，等等。 2 2 3 关联规则挖掘的过程 一般来说，关联规则的挖掘过程可以看作包含两个阶段的过程： ( 1 ) 第一阶段是找出所有的频繁项集，即找出所有支持度大于或等于预定义的最小 支持度阈值的项集。 ( 2 ) 第二阶段是由频繁项集产生所期望的关联规则，即找出满足最小支持度阈值和 最小置信度阈值的规则。在支持度。置信度框架之外，也可以使用附加的兴趣度( 相关度) 等来发现相关联的项之间的关联规则。 第一步的任务是在事务数据库中高效地找出全部频繁项集，它要面对巨大的数据 量，直接处理事务数据库，此步骤决定着挖掘过程的整体性能，也是关联规则挖掘的核 心。第二步任务相对较为直观容易，且开销远低于第一步。现阶段大量关联规则的研究 工作都集中在第一步过程上，大部分的算法及改进算法也都是针对第一步提出的。挖掘 过程见下图所示： f 二卜一1 i 事务数据l 频繁项集l 薹壁堡 搜索算法i 土 1 频繁项集 _ 。_ 一 关联规则i置信度 产生算法r 一 关联规则k 用 户 图2 1 关联规则的基本挖掘过程 在关联规则的挖掘过程中搜索频繁项集和产生关联规则是最主要的两个步骤，此 外，还应注意以下几点： ( 1 ) 充分理解数据； ( 2 ) 挖掘目标明确； ( 3 ) 充分的数据准备工作； ( 4 ) 选取恰当的最小支持度和最小可信度； ( 5 ) 很好的解释关联规则结果。 1 0 硕士论文关联规则算法研究及其在中医药数据挖掘中的应用 2 3 中医药数据挖掘研究 2 3 1 中医药数据挖掘的定义 中医药数据挖掘就是利用中医药数据库从大量中医医案中抽取隐含的、未知的、有 趣的中医药知识。中医药数据挖掘针对中医药知识进行挖掘，是获取中医药知识的现代 技术方法，将为中医药理论研究和中医药临床诊疗提供重要的科学依据。 2 3 2 中医药数据特点 医学信息蕴含了医疗过程的全部数据资源，既有有关临床的医疗信息又有医院管理 的信息。由于数据来源的广泛和容量的庞大，医学数据具有以下几个特点【1 2 】： ( 1 ) 医学数据的异质性。医学数据汉语表达灵活，一词多义或者一义多词的特点使 其很难标准化。医学数据的低数学特性，很难定量或用公式来描述。 ( 2 ) 医学数据的多样性。由于医学数据是从实验数据、医生个人诊断以及医生与病 人的交流中获得的，所以原始的医学数据具有多种形式。医学数据包括纯数据、文字影 像、信号等。医学数据的多样性是它区别于其他领域数据的最显著特征。 ( 3 ) 医学数据的不完整性。医学数据的搜集和处理过程经常相互脱节，搜集是以治 愈患者为直接目的，而处理是以寻找某种疾病的一般规律为目的，因此搜集的信息可能 无法涵盖研究需要的所有信息。病例和病案的有限性使医学数据库不可能对任何一种疾 病信息都能全面地反映。 ( 4 ) 医学数据的隐私性。医学数据不可避免地涉及到患者的一些隐私信息，医学数 据挖掘者有义务和职责在保护患者隐私的基础上进行科学研究，并且确保这些医学数据 的安全性和机密性。 ( 5 ) 医学数据的关联性。几乎在所有的有效病案中，数据之间都具有一定的关联性， 例如症状与证型之间、证型与治法、症状与方药、方药与方药。这些数据之间的关联性 实际上就是医学的治疗经验。 ( 6 ) 医学数据的重复性。医学数据库是一个庞大的数据资源，每天都会有大量的病 案记录，在很多病案之间都存在一定的信息重复。比如对于一类病证，病人表现出的症 状、拟定的治法、选用的方药都有一致之处。这样就为我们利用数据挖掘进行规律性探 讨打下了基础。 原始收集到的病案数据虽然存在有噪声、有缺省、不一致等情况，甚至有些病案只 有寥寥数语，这在一定程度上加大了数据挖掘的难度。但是，经过数据预处理后仍适用 于数据挖掘。中医药数据挖掘中对数据的规范化、标准化、结构化要求很高，数据的预 处理将直接关系到挖掘的结果。 2 3 3 中医药数据挖掘的过程 2 数据挖掘及关联规则技术 硕士论文 数据挖掘是与应用领域高度相关的，不同领域的挖掘过程有所不同，在中医药数据 挖掘中，是要有效地利用数据挖掘技术进行中医药的知识发现，其挖掘过程为： ( 1 ) 设定明确的中医药数据挖掘的目标； ( 2 ) 充分理解中医药数据特点并对数据进行适当的预处理； ( 3 ) 确定合适的数据挖掘方法和算法； ( 4 ) 对挖掘结果进行中医药专业的分析和评价； ( 5 ) 验证挖掘出的中医药知识，并通过使用反馈下一步的数据挖掘。 由于中医药独特的数据特点，中医药数据挖掘与传统的数据挖掘有所不刚乃j ，这是 数据挖掘技术与中医药共同发展的机遇，是一个有着美好前景又充满挑战的研究方向。 2 3 4 关联规则在中医药挖掘领域中的评价 本论文研究的关联规则基本算法在中医药数据挖掘领域中能够挖掘出有效的关联 规则知识，具体实验见第五章。目前，在中医药数据挖掘领域中，关联规则挖掘取得了 不少的研究成剁州。姚美村、艾路等应用数据挖掘技术中的关联规则分析技术，对治疗 消渴病的中药复方配伍的科学内涵进行探索性分析研究l l 引。李惠琴、蒋永光利用频繁模 式数据挖掘技术，对慢性乙型肝炎近十年的资料进行处理分析【l5 1 。何前锋等运用高频集 挖掘的方法，把高频用药组合与经验药对进行比较分析，提示可能成为新药对的组合【1 6 j 等等。 但是关联规则在中医药领域中的挖掘现在仍处于起步阶段，依旧有许多不足之处有 待改进。中医数据资源丰富，但是有效完整的数据源较少，且数据源稀疏，在较少的中 医药数据上进行挖掘，难免有没被发现的遗漏结果。例如一些有意义的数据频繁模式， 由于无法满足参数的要求而没被发现。充实中医药数据资源是中医药数据挖掘发展的首 要条件。另外现有的中医药挖掘方法，大都是基于传统的挖掘算法，不利于快速有效地 挖掘中医药知识。例如在挖掘关联规则频繁模式中，当最小支持度阈值设置过低时，会 产生大量的频繁模式，不宜于中医专家的分析评价，另外由于频繁模式数据集比较大， 算法的运行时间也较慢。若增大最小支持度阈值，则要求的模式出现概率较高，既不符 合中医药的实际情况，又将漏掉有意义的关联规则。所以运用新的规则算法是中医药数 据挖掘的趋势。 2 4 本章小结 本章论述了数据挖掘的概念、数据挖掘的功能和主要任务，分析了关联规则技术的 相关内容，并针对中医药数据挖掘方面，研究了其定义、特点和过程。 1 2 硕士论文关联规则算法研究及其在中医药数据挖掘中的应用 3 频繁项集挖掘算法及分析 3 1 频繁项集挖掘算法的发展 自关联规则概念提出后，众多研究人员对关联规则挖掘问题进行了大量的研究，其 中1 9 9 3 年r a g r a w a l 和r s r i k a n t 提出了著名的关联规则挖掘频繁项集的经典算法一 a p r i o r i 算、法【1 7 】，此算法采用逐层迭代的方法挖掘频繁项集。a p r i o r i 算法需要反复扫描 数据库且生成大量候选项集，因而时间和空间效率有很大局限，许多后续的研究工作都 是围绕提高这个算法的效率进行的。 在a p r i o r i 算法的基础上，p a r k 等提出了基于h a s h 产生频繁项集的算法- d y n a m i e h a s h i n ga n dp r u n i n g ( d h p ) 算法【1 8 i ，s a v a s e r e 等设计了基于划分的算法叫a r t i t i o n 算法 1 1 9 1 ，t i o v e n e n 等提出了基于采样的s a m p l i n g 算法【2 0 1 ，另外还有基于动态项集计数的 d y n a m i ci t e ms e tc o u n t i n g ( d i c ) 算法等。 除了基于a p f i o f i 算法的改进之外，许多学者还探索出基于不同思想或数据表示方 法的关联规则挖掘方法。有h a r tj i a w e i 等提出的一种基于f p t r e e 的关联规则算法一 f p g r o w t h 算法【2 l j ，此外还有纵向数据库表示的v i p e r 算法，基于字典树的t r e e p r o j e c t i o n 算法【捌，基于差集的d i f f s e t 算法【2 3 】等等，这些算法都取得了相当好的挖掘效果【2 4 1 。 3 2 频繁项集挖掘算法 3 2 1a p r i o r i 算法 a 研嘶算法使用一种称作逐层搜索的迭代方法，即基于k 项集来搜索( k + 1 ) 项集。 首先找出频繁1 项集的集合，记作厶。然后由厶生成频繁2 项集的集合厶，三：用于找 厶，如此下去，直到不能再找到频繁k 项集厶为止。具体来讲，a p r i o d 算法第一步是 扫描数据库d ，统计含一个元素的项出现的频率，收集满足最小支持度阈值的项，来确 定频繁1 项集；第一步之后的第k 步分两个阶段，先是调用a p r i o