（计算机应用技术专业论文）关联规则在生物信息学应用研究.pdf

摘要 随着生物信息学的发展，数据挖掘技术为其提供了越来越重要的 技术支持，而关联规则挖掘技术是数据挖掘领域中的重要组成部分。 但在应用过程中由于生物数据的特点，传统算法需要进一步改进或重 新提出新的算法以满足生物信息学的研究要求。 本文首先提出了一种在分布式环境下挖掘项约束多层关联规则 的有效算法：基于a p r i o r i 算法的m l a c d 算法。该算法适用于对通信 性能要求不高的分布式数据库，能够实现对基因表达谱数据在不同层 次上进行关联规则挖掘。 针对基因表达谱数据每个样本项非常多的特点，本文提出了一个 新颖的挖掘频繁闭合模式的算法r e m f o r ，该算法在闭合模式概念和 行枚举思想的基础上，采用垂直数据结构和f p t r e e 技术，对行集建 立行f p t r e e 来挖掘频繁闭合模式。通过实例和实验证明该算法在处 理基因表达谱数据集或行数远小于样本项个数的数据集时具有很高 的效率。 本文采用兴趣规则组概念得到关联规则并以关联规则建立分类 器，并对基因表达谱数据样本进行了预测实验。我们首先对基因表达 数据集提取特征基因并采用了兴趣规则组的上边界模式做为建立分 类器的分类关联规则，在r e m f o r 算法的基础上提出了算法f e a l l ， 实现了分类预测功能。实验证明，该算法在规则挖掘效率和预测准确 率方面获得很好的效果。 关键词数据挖掘，关联规则，基因表达谱，闭合模式，分类 a b s t r a c t b yt h ed e v e l o p m e n to fb i o i n f o r m a t i c s ，d a t am i n i n gt e c h n i q u ep l a y s am o r ea n dm o r ei m p o r t a n tr o l ei nt h er e s e a r c h a n da s s o c i a t i o nr u l e s m i n i n gi st h ek e yr e s e a r c hp o i n to fd a t am i n i n g b e a c a u s eo ft h ec h a r a c t e r o fb i o l o g i c a ld a t a ，w eh a v et oi m p r o v et r a d i t i o n a la l g o r i t h m so rp r o p o s e n e w a l g o r i t h m st os a t i s f yt h ed e m a n d so f b i o i n f o r m a t i c sr e s e a r c h i nt h i sa r t i c l e ，a na l g o r i t h mf o rd i s t r i b u t e dm i n i n gm u l t i p l e l e v e l a s s o c i a t i o nr u l e sw i t hi t e mc o n s t r a i n t sc a l l e dm l a c di sf i r s td e v e l o p e d ， w h i c hi sb a s e do na p r i o r ia l g o r i t h m m l a c di sa na l g o r i t h mt h a tc a n m i n em u l t i l e v e la s s o c i a t i o n si n g e n ee x p r e s s i o nd a t a s e ta n ds u i t s t h e s y s t e mo f l o wc o m m u n i c a t i o n r e q u i r e m e n t e x p e r i m e n t ss h o wt h a t m l a c d a l g o r i t h mi sf i g h ta n de f f i c i e n t a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fg e n ee x p r e s s i o nd a t a s e tt h a th a s m a n yi t e m s ，an o v e la l g o r i t h mc a l l e dr e m f o ri sp r o p o s e d ，w h i c hi s b a s e do nt h ec o n c e p t i o no fc l o s e dp a t t e r na n dr o we n u m e r a t i o ns t r a t e g y i t e m p l o y s v e r t i c a ld a t as t r u c t u r et e c h n i q u ea n db u i l d sr o wf p t r e et o m i n i n gf r e q u e n tc l o s e dp a t t e r n i ti sp r o v e dt h a ta l g o r i t h mr e m f o r i so f h i g he f f i c e n c yw h e ni ti sa p p l i e dt ot h ed a t a s e tw h i c hr o wn u m b e ri sf a r s m a l lt h a nt h en u m b e ro f i t e mn u m b e ro far o w b a s e do nt h ea l g o r i t h mo fr e m f o r ，u s i n gt h e c o n c e p t i o n o f i n t e r e s t i n gr u l eg r o u p ，a na l g o r i t h mn a m e df e a l li sp r o p o s e d ，w h i c h s e l e c tf e a t u r eg e n e sf r o mg e n ee x p r e s s i o nd a t a s e tb e f o r eu p p e rb o u n d so f i n t e r e s t i n gr u l eg r o u p s a r em i n e d t h e ni tb u i l d sc l a s s i f i e rb yu p p e r b o u n d so fi n t e r e s t i n gr u l eg r o u p st oc l a s s i f y i n gu n k n o w nc l a s se x a m p l e s e x p e r i m e n t ss h o w t h a ti td o e sw e l lo nt h ea s p e c t so fe f f i c i e n c yo fm i n i n g a s s o c i a t i o nr u l e sa n da c c u r a c yo fc l a s s i f y i n gu n k n o w nc l a s se x a m p l e s k e yw o r d sd a t am i n i n g ，a s s o c i a t i o nr u l e s ，g e n ee x p r e s s i o n ，c l o s e d p a t t e r n ，c l a s s i f i c a t i o n i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。 作者签名：! 垫盟日期：鎏型l 年上月竺日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者虢阻翩签名趁日期过年旦月丝日 硕士学位论文第一章绪论 1 1 引言 第一章绪论 随着数据库技术和网络的迅速发展，数据库中存储的数据爆炸性的增长。 如果能把隐藏在这些数据后面的重要信息从数据库中抽取出来，将会创造大量潜 在的利润，而这种从海量数据库中挖掘信息的技术，就称之为数据挖掘。在商业 应用里，它就表现为在大型数据库里面搜索有价值的商业信息。 数据挖掘是一门广义的交叉学科，它汇聚了不同领域的技术，其中包括数据 库、人工智能、数理统计、可视化、并行计算和机器学习等。通过数据挖掘，可 以从数据库中提取有趣的知识、规则和高层信息，并可以从不同角度观察和浏览。 发现的知识可以用于决策、过程控制、信息处理和查询处理等。因此，数据挖掘 被信息产业界认为是数据库系统最重要的前沿之一，是信息产业最有前途的交叉 学科。同时数据挖掘技术可以应用于许多领域，如商业市场决策、科学研究、 生物信息学数据的处理、分析和预测、临床医学研究等等。 1 2 数据挖掘概述 数据挖掘技术是在八十年代末产生并迅速发展起来的新兴的研究领域。从数 据库中发现知识( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，简称k d d ) 一词首次出现 在1 9 8 9 年举行的第十一届国际人工智能学术会议上。1 9 9 5 年，首届k d d d a t a m i n i n g 的国际性会议在加拿大的蒙特利尔召开。到目前为止，由美国人工智能 协会主办的k d d 国际研讨会已经召开了多次，规模由原来的专题讨论会发展到国 际学术大会，研究重点也逐渐从发现方法转向系统应用。1 9 9 7 年亚太地区在新 加坡组织了第一次规模较大的p a k d d 学术研讨会。此外，数据库、人工智能、信 息处理、知识工程等其它领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。 i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术 专刊。不仅如此，在i n t e r n e t 上还有不少k d d 电子出版物和论坛，人们可以免 费订阅和交流热点问题。从九十年代开始，我国的许多科研单位和院校都开始对 k d d 的基础理论和应用进行广泛的研究，也取得了一定的成果。 1 2 1 数据挖掘的定义 一般认为数据挖掘是k d d 中的一个很重要的步骤。从1 9 8 9 年至今，k d d 的 定义随着人们研究的不断深入也在不断地完善，目前比较公认的定义是f a y y a d 硕士学位论文 第一章绪论 等给出的：k d d 是从数据集中识别出有效的、新颖的、潜在的、有用的以及最终 可理解模式的高级处理过程。1 。k d d 的过程一般包括数据清理、数据集成、数据 选择、数据变换、数据挖掘、模式评估、知识表示。从广义的观点看，数据挖掘 是从存放在数据库、数据仓库或其它信息库中的大量数据中挖掘有趣知识的过 程。简单地说，数据挖掘是从大量数据中提取或挖掘知识“3 。 1 2 2 数据挖掘技术 最常用的数据挖掘技术有： 1 关联分析( a s s o c i a t i o na n a l y s i s ) 关联分析用于发现关联规则，这些规则展示属性一值频繁地在给定数据集中 一起出现的条件。关联分析广泛用于购物篮或事务数据分析。 2 分类和预测( c l a s s i f i c a t i o na n dp r e d i c t i o n ) 分类是这样的过程，它找出描述并区分数据类或概念的模型( 或函数) ，以 便能够使用模型预测类标记未知的对象类。导出模型是基于对训练数据集( 即其 类标记已知的数据对象) 的分析。在某些应用中，人们可能希望预测某些空缺的 或不知道的数据值，而不是类标记。当被预测的值是数值数据时，通常称之为预 测。预测也包含基于可用数据的分布趋势识别。常用的分类和预测技术包括决策 树、简单贝叶斯和神经网络等。 3 聚类分析“1 ( c l u s t e r i n ga n a l y s i s ) 与分类和预测不同，聚类分析数据对象，而不考虑已知的类标记。对象根据 最大化类内的相似性、最小化类间的相似性的原则进行聚类或分组。即对象的簇 ( 聚类) 这样形成，使得在一个簇中的对象具有很高的相似性，而与其他簇中的 对象很不相似。所形成的每个簇可以看作一个对象类，由它导出规则。 4 孤立点分析( o u t l i e ra n a l y s i s ) 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这 些数据对象是孤立点。孤立点可以使用统计试验检测。它假定一个数据分布或概 念模型，并使用距离度量，到其他聚类的孤立点数据分析称作孤立点挖掘。 5 可视化”。( v i s u a l i z a t i o n ) 即采用直观的图形方式来将信息模式、数据的关联或趋势呈现给决策者，决 策者可以通过可视化技术来交互分析数据关系。可视化技术主要包括数据、模型 和过程3 方面的可视化。 1 3 关联规则描述 关联规则挖掘是数据挖掘中的一个重要研究内容，用于发现给定数据集中项 硕士学位论文第一章绪论 之间的有趣联系。关联规则挖掘首先由a g r a w a l ，i m i e l i n s k i ，s w a m i “1 提出。关 联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中 不同商品之间的联系，分析顾客的购买习惯。例如，在同一次去超级市场，如果 顾客购买牛奶，他也购买面包的可能性有多大? 其直观的意义是顾客在购买某些 商品的时候有多大倾向会购买另外一些商品。这些信息可以引导销售“1 。 1 3 1 关联规则的基本概念 设i = i 。，i ：，i 。 是项的集合。设任务相关的数据d b 是数据库事务的集 合，其中每个事务t 是项的集合，使得t i 。每一个事务有一个标识符，称作 t i d 。一个项目集合称为项集，在一个项集中项目的数量称为项集的长度，一个 长度为k 的项集称为k 一项集。设x 是一个项集，事务t 包含x 当且仅当x c t 。 关联规则是形如x j y 的蕴含式，其中x 匕i ，v c i ，x n y = f l 。规则x j y 在事 务集d b 中成立，具有支持度s ，s 是d b 中事务包含x u y ( 即x 和y 二者) 的百 分比。规则x j y 在事务集d 中具有置信度c ，c 是d b 中包含x 的事务也包含y 的百分比。满足最小支持度阈值m i n s u p 的项集称为频繁项集。 挖掘关联规则就是在给定的交易集合中产生所有满足最小支持度闽值 ( m i ns u p ) 和最小置信度( m i n c o n f ) 的强规则。关联规则的挖掘是一个两步 的过程：找出所有频繁项集；由频繁项集产生强关联规则。第2 步相对来说比较 简单。挖掘关联规则的总体性能由第1 步决定。 1 3 2 典型的关联规则挖掘算法简介 1 a p ri o ri 算法及其改进算法 a p r i o r i 算法“1 是一种最有影响的挖掘布尔关联规则频繁项集的方法。 a p r i o r i 使用一种称为逐层搜索的迭代方法，k 一项集用于探索( k + 1 ) 一项集。 一旦由数据库d b 中的事务找出频繁项集，由它们产生强关联规则是直截了 当的( 强关联规则满足最小支持度和最小置信度) 。 由于a p r i o r i 算法存在候选项集的数目较大和需多次扫描数据库等缺陷，因 此不少学者提出了许多改进算法，其主要途径包括：减少候选项集的数目；尽可 能减少数据库的扫描次数；改进候选项集的计数方法。其中，有代表性的算法包 括d h p 算法”1 、p a t i t i o n 算法”1 和s a m p l i n g 算法。1 等。 2 f p g r o w t h 算法 h a n 等提出的f p g r o w t h ( 频繁模式增长) 算法。1 是一种不产生候选的挖 掘频繁项集方法，它通过逐步构造频繁模式树( f pt r e e ) 来生成全部高频项 硕士学位论文 第一章绪论 集，只需2 次扫描数据库，避免了高代价的候选项集产生；避免了a p r i o r i 类 算法中不可避免的会产生大量的候选项集问题；对于挖掘海量数据中的频繁项 集，f p - g r o w t h 算法都是有效的和可伸缩的，并且大约比a p r i o r i 算法快一个 数量级。 3 基于约束的关联规则挖掘算法 在实际的挖掘过程中，用户往往希望参与到挖掘的全过程中，以便对挖掘过 程进行指导和控制；在基于约束的挖掘中，挖掘在用户提供的各种约束的指导下 进行。在数据挖掘中常使用的几种约束“1 包括：知识类型约束：指定要挖掘的知 识类型；数据约束：指定与挖掘任务相关联的数据集；维层约束：指定数据库 或数据仓库中所用的数据维层：规则约束：指定对要挖掘的规则的具体约束。 规则约束可以分为5 类：反单调约束、单调约束、简洁性约束、可转变的约束和 不可转变的约束：兴趣性约束：指定规则兴趣度阈值或统计度量，如支持度和置 信度。此外，项约束的应用也比较广泛。典型的基于约束的关联规则挖掘算法包 括： ( a ) 项约束关联规则挖掘算法 m u l t i p l e j o i n s 、r e o r d e r 和d i r e c t “”是3 种不同的项约束关联规则挖掘算 法。这三种算法均能够接受布尔表达式作为约束，在发现频繁项集的同时删除不 满足约束的频繁项集。 ( b ) c a p 算法 n g ，l a k s h m a n a n ，h a n 和p a n “”根据反单调约束和简洁性约束的特点提出了 c a p 算法。c a p 算法在a p r i o r i 算法”1 的基础上实现了约束关联规则的挖掘算法。 ( c ) 约束频繁模式增长 无论是c a p 算法，还是m u l t i p l e j o i n s 等项约束关联规则挖掘算法均属于 a p r i o r i 类算法，存在生成的候选频繁项集数目较大和需要重复扫描数据库等缺 陷。p e i 和h a n 提出了一种基于f p - g r o w t h 算法。1 的约束关联规则挖掘架构c f g - 约束频繁模式增长“”( c o n s t r a i n e df r e q u e n tp a t t e r ng r o w t h ) ，能够将多种约 束( 包括反单调约束、单调约束、简洁性约束和可转变的约束) 整合到挖掘过程 中。 约束关联规则挖掘算法能够加强人对挖掘过程的导向与控制，提高挖掘性能 及效率。但是，现有的约束关联规则挖掘算法仍然有许多不完善的地方，存在一 些需要解决的问题，主要包括： 1 通用性和普遍性 目前，当约束条件为反单调的、单调的、简洁的和可转变的约束时，已有的 约束关联规则挖掘算法均能够有效解决。但对于不可转变的约束问题，研究的还 4 硕士学位论文第一章绪论 比较少。此外，对于查询语言和具体的交互性数据挖掘系统的研究还有待加强， 只有将约束关联规则挖掘算法的理论与应用相结合，才能发挥更大的作用。 2 扩展性 已有的约束关联规则挖掘算法多是基于单个数据库的。随着数据库技术和计 算机网络的蓬勃发展，将约束关联规则挖掘扩展到多层、多维、分布式以及异构 数据库中变的日益重要。 3 完全性 关联规则的挖掘是一个两步的过程，越来越多的研究集中在约束频繁集的挖 掘上，对于规则的产生关注不够。如何能够有效地生成约束关联规则也是一个十 分重要的课题。 另外，提高挖掘效率、充分利用系统资源也是约束关联规则挖掘算法所应关 注的问题。如何能够将用户的要求高质、高效地完成，是约束关联规则挖掘中一 个非常重要的课题。 4 并行及分布式关联规则挖掘算法 随着数据库规模的不断增大，数据属性向高维发展，传统的顺序挖掘算法很 难适应大规模、可扩展的挖掘需要，发展高性能的并行和分布式算法是解决这一 问题的关键。 基于并行环境下的关联规则挖掘算法主要包括：c d 算法3 、d d 算法。”、c a d 算法“2 1 和p d m 算法“”等。c d 算法目标是减少通信量获得较好的任务分布性，使 各处理器只对本地数据并行地进行处理。但算法的i 0 量较重，数据结构重复， 没有有效利用整个内存。d d 算法目标是尽量减小计算冗余，充分利用各节点之 间的带宽。它在节点问分割当前最大频繁项集的候选项集，然而要获得全局支持 度，各处理器必须搜索整个数据库，通信量较大。上述两种算法每次搜索结束时， 都要求所有处理器必须同步。与d d 算法相似，c a d 算法也是在各节点间分配候 选集，但它有选择地对数据库进行分割，使每个节点可以根据本地的数据来处理 它的候选项集，减少处理器之间对数据和各候选项集的依赖，从而减少同步，减 少通信量。 当前几乎所有并行算法都存在的主要局限性是：它们都重复访问驻留磁盘的 数据库分区，这就导致了大量t o 开销。此外，这些算法因涉及到在每次迭代过 程中候选支持度计数或远程数据库分区的交换，导致了大量的通信和同步性的开 销。基于此，就需要更有效、实用的分布式算法来解决这类问题。目前，常用的 分布式关联规则挖掘算法包括f d m 算法“、d m a 算法 1 5 jd d m 算法“6 1 和d - s a m p l in g 算法m 1 等。 硕士学位论文第一章绪论 1 4 生物信息学概叙及研究现状 生物信息学是包含了生物信息的获取、处理、存储、分发、分析和解释的所 有方面的- - f 学科，它综合运用数学、计算机科学和生物学的各种工具进行研究， 目的在于了解大量数据的生物学意义“。2 0 世纪8 0 年代末，人类基因组计划 ( h u m a ng e n o m ep r o j e c t ，h g p ) 的启动推动了生物信息学的产生和蓬勃发展。 人类基因组计划的直接结果是获得了大量不连续的数据。这些数据的收集、存储， 并进行分析、解释，从中获取有用的生物学信息，成为生物信息学迫切要解决的 问题。作为一种重要的数据处理分析技术，数据挖掘技术因其在大规模数据处理 方面的卓越能力而在生物信息学领域具有良好的研究与应用前景。生物信息学中 的数据挖掘研究仍然处于起步阶段，有很多问题需要解决。如何将众多的数据挖 掘技术应用于生物信息分析是当前的研究热点，包括适合生物信息处理的数据挖 掘体系架构、算法的开发、新的数据挖掘分析功能研究等。在后基因组时代，生 物信息学的研究内容主要可分为两个重要组成部分：基因组信息学和蛋白质组信 息学。基因表达数据的关联分析与处理和蛋白质的结构预测分别是上述2 种信息 学中最重要的研究课题之一。 生物信息学是生物遗传密码与电脑信息相结合，通过电脑的各种程序软件将 已知的大量的核酸、蛋白质等生物大分子的核苷酸序列进行分析、计算，揭示遗 传信息；通过对生物信息的查询、搜索、比较、分析，从中获取基因编码、基因 调控、核酸和蛋白质结构功能及其相互关系等理性知识，推断已知序列的功能； 在大量信息和知识的基础上，探索生命起源、生物进化以及细胞、器官和个体的 发生、发育、病变、衰亡等生命科学中重大问题，在研究清楚它们的基本规律和 时空联系的基础上，建立“生物学元素周期表”。简言之，生物信息学有两 个重要任务，一是管理好海量生物信息数据，二是用好这些数据，从中发现新的 规律，造福人类。数据挖掘技术是处理海量生物信息的强有力工具，它能够从大 量数据中提取潜在的信息和知识。近几年来，计算机工作者与生物学家在生物信 息领域进行了广泛的合作和研究，提出了一系列的挖掘算法和挖掘模式，并应用 于生物数据，取得了传统生物计算技术无可比拟的效果。 1 5关联规则在生物信息学中的作用 目前的基因组信息学研究集中在功能基因组和比较基因组方面。功能基因组 的研究是在全基因组水平上对基因或其表达产物进行全面分析，目的是探究基因 的时空差异表达情况。在研究层次上，它主要侧重于从基因的转录水平进行研究； 在研究内容上，它包括基因功能发现、基因表达分析及突变检测；在分析手段上， 6 硕士学位论文第一章绪论 目前主要使用基因表达的系统分析( s e r i a la n a l y s i so fg e n ee x p r e s s i o n ，s a g e ) 、 c d n a 微阵列( c d n am i c r o a r r a y ) 和d n a 芯片( d n ac h i p ) 等分析技术。其中， 如何快速有效地对微阵列数据进行分析已经成为当前生物信息学的一项重要任 务。c d n a 微阵列技术可以得到包含多个基因( 甚至整个基因组，如酵母) 在不 同生理过程中( 如代谢，应激，癌变和发育等) 的一组表达数据，称为大规模基 因表达谱。它为我们提供了细胞在某个特定过程中m r n a 表达水平的快照“。 大规模基因表达谱蕴含丰富的信息，但并非简单地就能发现，而是需要人们 不断进行挖掘。目前这方面的研究工作主要集中于对基因表达数据的聚类分析 ”“2 “。聚类通过把目标数据放入少数相对同源的组或“类”( c l u s t e r ) 里分析 表达数据。聚类方法有两个显著的局限：首先，要聚类结果要明确就需分离度很 好( w e l 卜s e p a r a t e d ) 的数据。几乎所有现存的算法都是从互相区别的不重叠的 类数据中产生同样的聚类。但是，如果类是扩散且互相渗透的，那么每种算法的 结果都将会不同。第二个局限由线性相关产生。上述的所有聚类方法分析的仅是 简单的一对一的关系，忽视了生物数据多因素和非线性的特点。熊等提出用递归 区分法( r e c u r s i v ep a r t i o n i n g ) 方法”分析d n a 微阵列或芯片技术产生的基因 表达数据，并运用于癌组织的鉴别分型，这种分析法最早应用于健康学的研究方 面”，是以分类树为基础来预测类别。类似的具有这种“学习能力”的d n a 微阵 列数据的分析方法还包括g o l u b 等提出的改进区分判别法( d e r i v e d d i s c r i m i n a n td e c i s i o nr u l e ) 。“，b r o w 等提出的支持向量器( s u p p o r tv e c t o r m a c h i n e ) 方法“，x i o n g 等提出的f i s h e r 线性判别式。”等。 基因组学和分子生物学研究的飞速发展使人们已经不再满足于孤立地研究 单个基因，而是希望能同时研究多个基因及它们之间的相互关系。”。关联分析方 法有助于发现基因组和基因对之间的交叉与联系，帮助确定在目标样本中出现的 基因种类。关联规则可以揭示出一些使用聚类技术所不能显现的模式。与聚类不 同的是：在关联规则中，一个基因可以属于多个规则，而不局限某一条规则。关 联规则可以描绘出一个基因表达是如何与整个基因表达集关联的。如果某一个关 联存在，则可以很容易推测出该关联中包括的基因必是存在于某个基因网络中。 通常基因表达数据可以排列成二维实数矩阵形式，矩阵第i 行对应于第i 个 基因，第j 列对应于第j 个样品，而矩阵的每个元素a 。，纪录了第i 个基因在第j 个样品中的m r n a 表达水平。因此非常适合数据挖掘的应用。目前，对于基因表 达数据的关联规则挖掘研究还处于起步阶段。 1 6 传统的关联规则挖掘算法的局限性和解决方法 由于基因表达数据项多的特点( 往往包含上万个基因) 决定了使用传统的层 硕士学位论文第一章绪论 次关联规则挖掘方法，如a p r i o r i 算法，会带来算法执行时间长、产生的关联规 则多等缺点。这是因为进行频繁项集的挖掘时，一个长度为l 的频繁模式意味 着有2 l 一1 个频繁子模式需要逐一搜索，将消耗大量的时间产生数目巨大的规 则，而且有相当多的规则是冗余的或价值不大。 为解决这一问题，通过许多研究者的努力，提出了两类解决方案：挖掘最大 频繁项集( m a x i m a li t e m s e t s ) 或以p a s q u i e r 等人提出的频繁闭合模式的概念为基础 进行关联规则挖掘。在这两个方案的基础上并提出了垂直数据结构和位图结构而 不是传统的水平结构来保存待挖掘的数据集，垂直结构和水平结构都是一个两列 的表的形式，只是水平结构表示的数据库第一列是交易d ，第二列存放的是此 交易的商品集合或项集，而垂直结构相反，第一列存放的是商品名称或项，第二 列是该项对应的行的集合。垂直结构通常性能较水平结构高，尤其表现在计算支 持度方面，它不需整个扫描数据库，只需要对对应的项的行集进行交集运算。位 图结构则由项和行d 组成位图矩阵，也是一种效率较高的数据结构，v i p e r 和 m a f i a 算法采用了压缩的位图结构。 最大模式( m a x i m a lp a t t e r n ) 的定义是：若项集i 是频繁的并且不存在频繁项集 k 使得i 是k 的真子集，则i 为最大模式或最大项集。挖掘最大项集的算法有 d b u r d i c k 等人提出的m a f i a 算法以及其它一些算法【2 8 芦3 0 ，3 1 “，可以大量减 少项集的产生，减少算法的执行时间。b u r d i c k 等人提出的深度优先搜索算法 m a f i a 采用垂直二迸制位图表示模式支持集，当项目平均支持率低于1 3 2 时， 存储效率远低于数组表示法，并且重建、计数和预处理开销很高。虽然只挖掘最 大项集具有效率高的优势，但这类算法会导致信息丢失，因此这类算法比较适合 于仅研究长的频繁项集的情况。 而以闭合模式概念为基础的频繁模式挖掘算法可以在避免信息丢失的同时 获得较高的算法效率，因此近年来在许多研究者的努力下提出了一些高性能的闭 合频繁模式挖掘算法。 1 7 闭合模式的概念及其主要算法 当前闭合模式算法可以分为两大类：项枚举和行枚举。项枚举算法的核心思 想是将所有项的可能组合列举出来，同时采用一系列的优化剪枝策略来挖掘闭合 的频繁模式。这类算法主要有如下几个： p a s q u i e r 等人提出的a - c l o s e 算法。“，p e ij i a n 等人提出的算法c l o s e t “3 ， z a k i 等人提出的c h a r m 。”算法等等。这些算法各有其优劣之处，因此可以将这 些挖掘算法进行整合，相互启发，以期得到更好的性能，j i aw e ih a n 等人综合 了上述算法提出了一个新的算法c l o s e t + 。”。 硕士学位论文第一章绪论 以上算法采取的是项枚举的思想，而g a oc o n g 等人另辟蹊径，提出了行枚 举的思想，提出了c a r p e n t e r 。”算法以及其扩展算法f a r m e r “。但当行的数量也 较大时，c a r p e n t e r 算法的性能有一定幅度的降低，同时行枚举和项枚举算法在 建立枚举树的过程中，数据本身的特点会随着挖掘的进行而发生变化，即在挖掘 的某时刻原本适合采用项枚举算法但随着挖掘的进行会变为适合行枚举算法，反 之亦然：为了解决这个问题，g a o c o n g 等提出了改进算法c o b b l e r “：将项枚举 和行枚举进行结合，通过被挖掘的数据的特点，而动态决定采用行枚举算法或项 枚举算法，从而获得最佳性能。虽然行枚举类算法在挖掘闭合模式方面具有一定 的优势，但当前这些算法在效率方面仍然存在一些不足之处，有待进一步提高。 目前国内外对于基因表达谱数据进行关联规则挖掘和分类算法的研究还处 在初级阶段，许多算法需要根据生物数据的特点进行改进或提出新的算法，在作 者能够检索到的知名学术会议论文集和公开发表的刊物上，发现针对这一方向的 研究成果比较少。本文针对基因表达谱数据的特点对关联规则的挖掘和分类预测 问题进行了研究和探讨。研究的主要内容如下： 1 针对分布式多层基因表达谱数据库和项约束条件的特点，研究基于项约 束条件的分布式多层关联规则的挖掘问题。 2 将关联规则挖掘应用于生物信息学基因数据，针对基因表达谱数据样本 项特别多的特点研究基于闭合模式的关联规则挖掘算法。 3 针对基因表达谱数据，将关联规则挖掘与分类技术相结合，进行分类算 法研究。 最后对全文进行了总结，对今后的工作进行了展望。有关以上工作的详细讨 论将在本文第2 章到第5 章中给出。 1 8 论文组织 本文由以下章节组成： 第1 章是绪论，描述了数据挖掘的定义和常用的数据挖掘技术，并对生物信 息学及关联规则在生物信息学中的应用进行了介绍。 第2 章介绍了在分布式环境下对基因表达数据挖掘多层约束性关联规则的 有效算法：基于a p r i o r i 算法的m l a c d 算法。并进行了实例验证和测试分析，指 出了这种算法的优缺点及适用条件。 第3 章介绍了基于闭合模式的关联规则挖掘算法。针对基因表达谱数据的特 点，充分利用了闭合模式的概念理论和行枚举算法的特点，提出了行f p t r e e 的 数据结构，提出了一个能够高效挖掘基因表达谱数据关联规则的算法r e m f o r 。 最后并给出了实验结果和分析，指出其优缺点和适用的条件。 硕士学位论文 第一章绪论 第4 章介绍了一种新的实现对基因表达谱数据进行分类预测的方法：使用关 联规则进行分类预测，提出了一种有效算法一- - f e a l l 算法。本算法使用信噪比 对基因表达谱数据进行过滤，采用兴趣规则组的概念进行关联规则的挖掘，最终 建立分类器并获得了较高的关联规则挖掘效率和预测准确度。 第5 章对全文进行了总结，并对今后的工作进行了展望。 1 0 硕士学位论文第二章分布式挖掘项约束的多层关联规则 第二章分布式挖掘基于项约束的多层关联规则 项约束条件是一种重要的约束条件，是要求关联规则中至少包含用户定义的 个项集中的某个项。发现满足项约束条件的关联规则的算法称为项约束关联规 则挖掘算法。本章主要研究挖掘分布在不同数据站点上的基因数据的关联规则问 题。在挖掘的过程中可以和用户进行交互，加入项约束。 基因表达数据中蕴含着基因活动的信息，可以反映细胞当前的生理状态，并 且由于基因表达具有时空特异性，因此，基因表达数据比较更为复杂，数据大， 数据的增长速度快，所以我们可以将基因表达谱数据进行分层处理，根据需要在 不同层次上进行关联规则挖掘。本章提出了在分布式环境下挖掘约束性多层关联 规则的有效算法：基于a p r i o r i 算法的m a l a c d 算法。讨论了算法的原理和具体 实现方法。本章最后通过实例分析和仿真测试验证，指出了算法的优缺点及适用 条件。 2 1 引言 目前，对基因表达数据的分析主要是在三个层次上进行： l 、分析单个基 因的表达水平，根据在不同实验条件下，基因表达水平的变化，来判断它的功能， 2 、考虑基因组合，将基因分组( 分层) ，研究基因的共同功能、相互作用以及协 同调控等。3 、尝试推断潜在的基因调控网络，从机理上解释观察到的基因表达 数据。基于约束的关联规则挖掘能够实现用户指导和控制挖掘过程，同时关联规 则挖掘使用原始数据表示，支持率低，表达普遍的数据关联关系比较困难，而项目 通常是分类的，且具有层次关系，如上述第二个研究层次就需要进行分层研究。因 此挖掘多层的关联规则能进一步帮助发现更具有聚焦性和更有意义的规则。对基 因表达数据的分析可以获取基因功能和基因表达调控信息，这是生物信息学的重 大挑战之一，也是d n a 微阵列能够在生物医学领域中广泛应用的关键原因之一。 所以研究分布式环境下基于约束的多层关联规则挖掘可以对生物信息学的研究 提供有力的支持，具有很高的价值。 目前，许多研究者已经提出多种传统的关联规则的挖掘方法。其中快速挖掘 算法有a p r i o r i 算法、d h p 算法、p a r t i t i o n 算法和f p 一增长算法。约束性关 联规则挖掘算法有m u l t i p l e j o i n s 算法、r e o r d e r 算法和d i r e c t 算法。典型的 并行算法有c d 算法和p d m 算法，分布式关联规则挖掘算法有d m a 算法。 当前分布式约束性关联规则挖掘算法和分布式多层关联规则挖掘算法的研 硕士学位论文 第二章分布式挖掘项约束的多层关联规则 究也有了一定发展，出现了一些相关算法。如挖掘多层关联规则的m l f d m 算法和 挖掘基于项约束的d m c a 算法“。但对于分布式环境下约束性多层关联规则挖掘 算法还比较少见。本文提出了一个有效的算法m l a c d 算法来解决分布式环境下约 束性多层关联规则挖掘问题。 m l a c d 算法是一种基于a p r i o r i 算法的分布式多层约束性关联规则挖掘算 法。根据d i r e c t 算法来产生候选项集，采用了逐层搜索的方法，在l 层挖掘过 程中，k 项集用于搜索( k + 1 ) 项集。在第k 次迭代中，首先找出各站点上满足项 约束条件的候选k 项集，并计算候选k 项集的局部支持度计数：然后将本数据站 点上的支持数向其它站点广播，算出完整的候选k 项集支持数；最后根据最小支 持度阈值计算全局频繁( k + 1 ) 项集。 2 2 问题描述 设d b 是有d 个交易的数据库，存放在分布式系统p ( p 1 ，p2 ，pn ，n 是站点数) 上。各站点上的数据分别为 d b l ，d b 2 ，d b n ) 。给定l 层最小支 持度阈值m i n s u p l ，用r 1 ，k 表示d b 上1 层的满足约束b 全局频繁k 一项集，因 此分布式挖掘约束的多层关联规则的目标是多个节点在各个层次上协调产生满 足b 且支持度和可信度不小于给定的最小支持度和可信度的关联规则。 本文所讨论的约束条件为项约束，即要求关联规则中至少包含用户定义的一 个项集中的某个项。设给定项约束条件b ，b 为i 上的一个布尔表达式。假设b 已经转变为d n f 形式：d - v d z v v d 。，其中每个d i 形如：a i 。八a 。2 八八a i n o 2 3 分布式挖掘项约束多层关联规则算法- - m l a c d 算法 m l a c d 算法是一种基于a p r i o r i 算法的分布式项约束多层关联规则挖掘算 法。算法采用了逐层搜索的迭代方法，k 一项集用于搜索( k + 1 ) 项集。在第k 次迭 代中，首先找出各站点上满足项约束条件的候选k 一项集，并计算候选k 一项集的 局部支持度计数：然后将本数据站点上的支持数向其它站点广播，算出完整的候 选k 一项集支持数；最后根据最小支持度阈值计算全局频繁( k + 1 ) 一项集。算法根 据d i r e c t 算法来产生候选项集。 2 3 1 相关技术 1 分布式挖掘关联规则 c d 算法是一种通信模式简单、行之有效的并行关联规则挖掘算法。它的目 标是减少通信量获得较好的任务分布性，使各处理器只对本地数据并行地进行处 理。c d 算法可用做分布式关联规则挖掘算法。 硕士学位论文第二章分布式挖掘项约束的多层关联规则 m l a c d 算法中采用c d 算法的分布式设计与通信思想：在f 层，当k = 1 时， 各站点共同计算并交换数据得到全局的频繁满足约束的1 项集l b ( 1 和频繁1 项 集f 。当k l 时，各站点都根据相同的全局频繁的满足约束b 的k - 1 项集l b 【k 1 产生全局k 项候选项集c 。：然后计算全局候选项集c 。在本地数据分区上的支持数， 并将本数据站点上的支持数向其它站点广播，算出c 。中完整的候选项目集支持 数，在这一步，各站点被强制同步；最后各站点用c 。计算全局频繁的满足约束b 的k 项集l b 【( k 】，各站点独立地决定是否终止或继续进行下一次搜索，由于所有 的站点p i 都有同样的l b 【( k 】，所以每个站点的决定是相同的。 2 层次编码 挖掘多层关联规则有其特点，需要某种方式来表示项目的层次关系，并且各 层的最小支持度可能不同。可以采用有向无环图来对交易数据库中的信息建立层 次编码，表示项的层次关系。本文对于各处理节点，同一层采用相同的最小支持 女 为了方便解释对项建立层次编码，我们采用服装举例，建立一个有向无环图 来表示项目的分类层次，建立交易编码表。如下图2 1 ： 图2 - 1 具有分类信息的编码项目树 图中每个节点是一个项目或项目种类，如果从项目p 有边到项目c ，则称项 目p 是c 的父亲，而c 是p 的孩子，即上层是下层的父亲或祖先。每个项目用一 个编码串来表示，如1 1 1 表示夹克。若下层项目集是频繁的，则其相应的祖先必 然是频繁的，本文对各层采用各自合适的最小支持度。一个数据挖掘查询往往仅 涉及交易数据库中的部分数据，因此，在挖掘中应对交易数据库进行预处理。同 时，还要对编码交易表进行频繁项集的修剪，以减少编码交易表的交易条数和交 易的长度。因为支持度计数所需要的代价与交易表的大小和每条交易的长度有 关。 硕士学位论文 第二章分布式挖掘项约束的多层关联规则 3 约束条件的多层处理 本文讨论的是项约束，用户可以控制约束项属于各个不同的层上，因此 在进行每一层挖掘时，要对约束条件进行处理，使约束项的形式和挖掘层一致。 如，对于约束项1 2 3 ，在进行第一、二、三层挖掘时，将约束项分别处理为1 一、 1 2 、1 2 3 的形式，若约束项在挖掘层的上层时，比如约束为1 2