（电路与系统专业论文）dna数据库中的关联规则挖掘.pdf

摘要 随着人类基因组计划的顺利完成和各种后基因组计划的开始实施，涌现出海 量的生物分子数据。充分利用这些数据，揭示这些数据的内涵，得到对人类有用 的生物信息，是科学家们所面临的一个严峻的挑战。虽然生物信息学中已经提出 了大量有积极意义的方法，但目前大部分的方法还不能获得最优的模式、最准确 的预测。 本文根据数据挖掘中的关联规则挖掘算法，提出了一种在支持度一匹配度框 架下、挖掘基因d n a 序列数据库中非公共的闭合频繁序列之间的关联规则的新型 算法。本文使用了来自美国n c b i 中r a ka l p h a 和h b s a g 基因数据，以实例的形 式说明和分析了算法。分析表明，这种算法不仅可以准确、快速的找到所有的 d n a 序列模式，还可以更好的发现这些模式之间隐含在序列结构中的生物学信 息。并且利用这种算法在基因d n a 序列数据得到的规则，可以准确的预测新的基 因d n a 数据的种类和功能。 关键词：数据挖掘；关联规则；d n a 序列数据库；a p r i o r i 算法 a b s t r a c t a f t e rt h eh u m a ng c n o m ep r o j e c tw a sc o m p l e t e di n 2 0 0 3 ，t h ee r ao fp o s th u m k n g e n o m ei sc o m i n g v a r i o u sp o s tg e n o m ep r o j e c t sa r eb e i n gp l a n n e da n dp u t t i n gi n t o p r a c t i c e 。w h i c hh a ss p a r k e do f fv a s ta m o u n to fb i o l o g i c a lm o l e c u l a rd a t a t oe x p l o i t s u c hi n v a l u a b l ed a t aa n dd i s c o v e ri n h e r e n tb i o l o g i c a li n f o r m a t i o nf r o mt h ed a t ai s f r o ma l la s p e c t si m p o r t a n ta n do fs c i e n t i f i cv a l u ef o rh u m a nb e i n g r e s e a r c h e r sf a c e d w i t ht h ec h a l l e n g eo fa d d r e s s i n gr e l a t e dw o r k sa r ed e v o t i n ga l lo ft h e i re f f o n st ot h e s t u d i e so fu n c o v e r i n gb i o l o g ys e c r e t sf r o mt h ed a t a u pt on o w ，m a n ym e a n i n g f u l m e t h o d sa n dt o o l sh a v eb e e nd e v e l o p e da n di m p l e m e n t e df o rm a n i p u l a t i n gg c ：f l o r a e d a t a ，h o w e v e r ，t h er e s u l t so fd i s c o v e r e dp a t t e r n sa n dp r e d i c t i o nt n mt ob eo u to ft h e e x p e c t s h e n c e ，r e s e a r c h e r ss t i l lh a v eal o n gw a yt og o b a s e do nt h ef r a m eo fs u p p o r t m a t c h ，i nt h i sp a p e r ，t h ea u t h o ri m p r o v e dt h e o r i g i n a la l g o r i t h mf o rm i n i n ga s s o c i a t i o nr u l e s ，a n dp r o p o s e da ne n h a n c e da l g o r i t h m f o rm i n i n gc l o s e df r e q u e n tp a t t e r n sf r o md n a s e q u e n c e s r a ka l p h ag e n ea n dh b s a g g e n eo fd n as e q u e n c ed a t af r o mn c b lw e r eu s e di nt h ep a p e r t h er e s u l t so f a n a l y s i ss h o wt h a tt h ep r o p o s e dm e t h o di sc a p a b l eo ff i n d i n ga l ip a t t e r n so fd n a s e q u e n c e sf a s ta n da c c u r a t e l y , 豁w e l la st h ei n h e r e n tb i o l o g i c a ll i n k a g ea m o n gt h e s e p a t t e r n s f u r t h e r m o r e ，a s s o c i a t i o nr u l e sm i n e df r o mt h ep a t t e r n sc a nb ee m p l o y e df o r c l a s s i f y i n gd i f f e r e n tt y p e so fg e n e sa n dc o n s e q u e n t l yf o rd i s t i n g u i s h i n gd i f f e r e n tt y p e s o f d i s e a s e s k e yw o r d s ：d a t am i n i n g ；a s s o c i a t i o nm l e ；d n as e q u e n c ed a t a b a s e ；a p r i o r l a l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得东北师范大学或其他教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 学位论文作者签名：塾经日期；2 竺2 z ：堡 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论 文的规定，即：东北师范大学有权保留并向国家有关部门或机构送 交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权东 北师范大学可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：址指导教师签名：厘坌塑望 日 期：砰1 日1 3 叠日期：砷私鼋朔 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 第一章引言 1 1 生物信息学简介 1 1 - l 生物信息学研究的背景和意义 随着人类基因组计划的顺利实施和各种后基因组计划的开始，涌现出海量的 生物分子数据。充分利用这些数据，揭示这些数据的内涵，得到对人类有用的信 息，是科学家们所面临的一个严峻的挑战。生物信息学就是为迎接这种挑战而发 展起来的一门新型学科，它是由生物学、数学和计算机科相互交叉所形成的学科， 是当今生命科学和自然科学的重大前沿领域之一“1 。 生物信息学是一个新型的交叉学科，是以计算机、网络为工具，利用数学和 信息学的理论、方法和技术去研究生物大分子，研究生物分子的信息组织和表达 的规律。生物分子至少携带着3 种重要的信息，即遗传信息、与功能有关的结构 信息以及进化信息。通过生物信息学对生物分子的分析和研究，可以认识生物分 子的作用，探索人类生老病死的原因，了解生命的起源和进化，进而加深对生物 世界的认识。目前，生物信息学研究的重点主要是d n a 分子和蛋白质两个方面， 其中包括研究它们的序列、结构、和功能，并以系统的观念去分析它们之间的相 互作用。 1 1 2 生物信息学的主要方法 生物信息学的核心是序列的比较。这包括同一个序列内不同片段的比较， 以及两个或多个序列的比对。比较的内容：从序列的组分变化、寻找特殊的字段、 到序列问字母的对应。比较的主要目的在于阐明序列之间的同源关系，以及从己 知序列预测新序列的结构和功能。当然还有其他如蛋白质结构和功能预测等。 模式发现是生物信息学的一个重要研究方向，但目前的大部分算法还不能保 证获得最优的模式。所谓模式( m o t i f ) 就是指d n a 序列中保守的序列片段。通常 人们认为d n a 序列总是处于不断的突变过程中，而其中的某些区域，比如启动子 区域，由于对生物体的生存具有至关重要的意义，因而在进化的过程中更保守一 些，并表现为d n a 序列中的模式。另一方面，一个保守的序列片段往往意味着一 个重要的功能区域，它们通常对应着d n a 序列中重要的功能性或结构性元素。从 d n a 序列中发现这些模式的过程就是模式发现( m o t i ff i n d i n g ) ，它是生物信息 学的一个重要研究内容。模式发现有助于决定序列的功能和阐明序列之间的进化 关系，并且在识别d n a 序列的调控信号方面有着重要的应用0 1 。 模式发现的问题可以描述为“3 ：给定一组( n 个) d n a 序列( 称为样本) ，每个序 列的长度为n ，寻找一个长度为了1 的序列片段( 模式) ，它至少在k 个样本中出 现，在每次出现中最多可以有d 个不匹配的碱基。这样的序列片段称为( 1 ，d ) 一k 模式，它在样本中的出现称为实例。 当我们从一组序列中寻找一个模式的时候，我们实际寻找的是它在每个序列 中的实例，之后再从这些实例中恢复出这个模式。例如，对一个( 1 ，d ) 一k 的模式 发现问题( 样本集合为n 个长度为n 的序列) ，我们首先从k 个不同的样本中选择 k 个长度为1 的子序列( 这k 个子序列称为一个子序列组，或者简称为一个组) ， 然后尝试恢复出一个模式，使得每个子序列与该模式之间不超过d 个不匹配的碱 基( 也称为两者的距离不超过d ) ，如果能够恢复出这样的一个模式，那么这个组 就是有效的。从样本序列中找出所有的有效组是模式发现问题的关键，一旦某个 模式的有效组被找到，就可以采用一些简单的方法( 比如位置权重矩阵) 来恢复这 个模式。 1 1 3 国内外研究的现状 很明显，最简单也是最直接的方法是测试所有可能的子序列组，但这一算法 的复杂度是样本数日的指数函数，因而是不现实的。实际上，在通常的模式发现 问题中，绝大多数的子序列组是无效的，它们不可能被用于恢复出一个模式，这 就需要一种能够及早判断出无效子序列组的方法，它可以在完全列出一个子序列 组之前就判断出它是否有效，从丽提高算法的效率。 近年来，关于模式发现问题，科学家已经进行了大量的研究工作，得到了 了很多有意义的方法和算法。晟简单的模式发现算法是基于模式的算法“1 ( p a t t e r nd r i v e na l g o r i t h m ，p d a ) ，它依次检验所有的4 1 个长度为l 的序列片 段，对它们在d n a 序列中出现的实例给出得分，从而找出其中具有较高得分的模 式。由于p d a 的计算复杂度是l 的指数函数，因此，对于较大的1 ，这样的算法 是不现实的。在p d a 的基础上，人们又提出了基于样本的算法嘲( s a m p l ed r i v e n a l g o r i t h m ,s d a ) 。其基本思想是对样本中的每个长度为l 的序列片段，计算出 它的满足一定条件的相邻序列片段集合，并在这个集合中进行搜索。由于此时的 搜索空间( 相邻片段集合) 远远小于基于模式的算法的搜索空间，因而能够获得高 得多的计算效率。目前较为有效的算法都利用了这一思想，只不过在减小搜索空 间的策略上各不相同，比如随机投影算法就是采用的随机性优化过程，而 p a t t e r n b r a n c h i n g ”1 算法采用的是启发式的优化过程，肼i t r a 则是采用s d a 进行 穷举搜索的一个例子“1 。但是，p e v z n e r 和s z e 嘲的工作表明，这些算法的执行效 果都不是很理想，不能准确快速的找到具有意义的模式。因此，需要提出一种新 型的、准确快速的算法来解决这些问题。1 。 2 用于序列比对的算法和程序的开发是一个很活跃的领域，目前最常用的比对 算法是渐进比对算法。t h o m p s o n 等在1 9 9 4 年开发的基于渐进比对算法的多序列 比对程序c l u s t a lw 脚使多序列比对达到一个新的高度，成为应用最为广泛的比 对程序。但对多序列算法的研究并没有停止，渐进比对算法因其本身固有的缺陷 使其比对精度不能达到足够高。在最近的几年里，又出现了基于渐进式算法的改 进算法。它们在不同程度上弥补了渐进比对算法的缺陷，在速度和精度上都取得 了一定的提高，其中比较有代表性和影响力的有基于迭代细化策略的p r r n p r r p “，基于傅立叶变换的m a f f t “、基于多重迭代的m u s c l e s “”和t - c o f f e e “”。 i i 4 利用关联规则挖掘d n 数据库 作为生物信息学研究的重点的d n a 和蛋白质序列分析，我们需要关注的是如 何有效发现d n a 和蛋白质序列中那些具有生物学意义的模式。这些模式应当既具 有生物学上的意义( 重要性) ，又具有数学上的重要性( 可发现性) ，这样得到 的结论，将更加有助于从生物数据中发现生命中的规律、解释生命中的现象。而 这些要求却是作为生物信息学基础的序列比对，比较以及相似序列的数据库搜索 等技术不能完全达到的。关联规则挖掘算法是实现上述目标的有效手段，它具有 概率七的理论依据，同时其方法简单有效，并且得到的关联规则易于从实际的角 度给以解释。关联规则中已经有许多有意义的序列模式分析方法和相似检索技术 n 删，这些方法与技术成为d n a 数据库分析中强有力的工具。 近年来，随着数据挖掘技术的逐步完善和应对生物信息学的要求，一些关联 规则的挖掘方法逐渐的应用到了生物信息学当中。1 删，但是这些研究都存在着一 些缺点和不足： ( 1 ) 只考虑了某些d n a ( 蛋白质) 序列与其特有的模式( 基因片段) 之间的关 系，因此不具有普遍性。 ( 2 ) 没有考虑到模式与模式之间、多个模式与d n a ( 蛋白质) 序列之间存在的 关联规则。 ( 3 ) 没有考虑到模式( 基因片段) 在d n a ( 蛋白质) 序列结构中隐含的关联规 则。 ( 4 ) 没有考虑到公共模式( 被多个序列包含) 对d n a ( 蛋白质) 序列估计的影 响，造成预测准确率偏低。 本文就以上问题，提出了一种新型的在d n a 序列数据库中挖掘关联规则的算 法。这种算法能在支持度一匹配度框架下，快速的找到所有满足最小支持度的非 公共的模式，并根据这些模式在d n 序列中的位置，挖掘其中隐含的、具有结构 特性的关联规则。并可以根据在学习数据库中挖掘的关联规则，很好的预测新的 d n a 数据的种类和功能。 3 1 2 数据挖掘及关联规则的简单介绍 数据挖掘( d a t a m i n i n g ) 简称咖，又称数据库中的知识发现( k d d ：k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) ，是从大量的、不完全的、有噪声的、模糊的、随机的 实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 息和知识的过程。 数据挖掘是近年兴起的一项新的技术，它在许多领域中取得了成功的应用。 作为一个新兴的领域，数据挖掘还不成熟，其应用还有很大的局限性。数据挖掘 还面临着许多挑战和未解决的问题，如在高抽象层次上获得多类知识的挖掘算法 研究，而向对象数据库、多媒体数据库、i n t e r n e t 信息系统中数据挖掘等算法 的研究，数据挖掘中私有数据安全性的研究等。另外，由于现实世界的复杂性、 数据的多样性和不同的应用目标，还不能形成一个通用的数据挖掘系统适应于所 有的情况，对于不同的应用要建立不同的数据挖掘系统。对于同一个应用，不同 的数据挖掘系统可能产生不同的结果，对其的评价有赖于实际经验，还没有一个 较完善的理论体系。不管如何，作为适应时代需要而产生的一项新技术，数据挖 掘技术在理论和实际应用上还有待于进一步的发展和完善，其在生产决策、经营 管理、金融预测、工业控制等许多领域都有着广泛的应用价值和理论研究前景。 关联规则作为数据挖掘的主要内容，涌现出了很多挖掘频繁项集的高效研 究。关联规则数据挖掘首先由a g r a w a l ，i m i e h s k i 和s w a m i ”1 提出，著名的 a p r i o r i 算法由a g r a w a l 和s r i k a n t 提出，使用类似的剪枝方法的算法变形由 m a n n i l a 。t o i v o n e n 和y e r k a m o 研究。在最低支持度比较高和模式搜索空间比 较松散的条件下，这些算法可以有很好的性能。但是，在相反的条件下，即当最 低支持度降低时，频繁项集的数目将会急剧的增长，也因此造成算法的效率逐步 恶化：并且算法挖掘结果的有效性也随着大量冗余模式的产生而下降。对于一个 长度为l 的频繁模式，其本身将会有产生2 l 1 个频繁模式，当l 足够大时，这 个数字将是灾难性的，整个挖掘效率将会大大降低。近几年来，为了解决以上问 题，提出了很多深层次的挖掘频繁闭合项集的算法，比如a - c l o s e 、c l o s e t 嘲、 m a f i a 啪、c h a r m 。还有综合性较强的c l o s e t + ，t o p - k 嘲1 等。他们采用挖掘频 繁闭合项集的方法，其挖掘对象仅仅为没有相同支持度超集的频繁项集。在保证 信息完整性的情况下，其产生的结果只是全体频繁项集的一个很小的子集，并且 闭合项集可以方便得出所有的频繁项集。尤其是x i f e n g y a h 等人0 3 年提出的， 在序列数据库中发现所有的闭合频繁序列的c l o s p a n 算法“”，使得关联规则挖掘 在序列数据库中的应用得到了很大的提高。 4 1 3 论文的内容 全文分为五章，主要内容如下 第一章为绪论，概述了本文选题的背景与依据、研究目的、内容以及组织结 构等。 第二章为数据挖掘的相关知识，介绍了数据挖掘及关联规则的基本概念，详 细的阐述了支持度一匹配度框架对比支持度一置信度框架的优点。介绍了 a p r i o r i 算法并举例说明了算法具体的步骤，分析了a p r i o r i 算法在处理数据时 的局限性。 第三章首先介绍了序列数据库和在序列数据库中的关联规则挖掘技术，接着 说明了在o n 数据库上的关联规则挖掘的特点和本文所采用的方法： ( 1 ) 利用序列数据库上关联规则挖掘的方法，快速的找到所有的闭合频繁 序列模式。 ( 2 ) 在支持度一匹配度框架下，删除公共闭合频繁序列( 公共模式) 。 ( 3 ) 如何对a p r i o r i 算法进行优化，使其可以在序列数据上挖掘关联规则。 最后说明了本文所采用的d n a 数据的来源，基本特征和数据的研究内容。 第四章详细的说明了在支持度一匹配度框架下利用优化的a p r i o r i 算法的挖 掘非公共的闭合频繁序列结构的新算法的具体步骤，并在3 2 介绍的基因数据库 中，采用“余一”法( l o o c v ) 对挖掘的规则加以验证。 第五章是总结和展望，最后是参考文献和后记。 5 第二章关联规则挖掘和a p r io ri 算法的简单介绍 2 1 关联规则的简单介绍 关联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) 是数据挖掘研究领域的一个重要分 支，在很多挖掘领域中占据着重要的地位。关联规则挖掘于1 9 9 3 年由a g r a w a l 2 4 l 在对市场购物篮问题( m a r k e tb a s k e ta n a l y s i s ) 逆e 行 分析时首次提出，用以发现商 品销售中的顾客购买模式。关联规则挖掘可以发现存在于数据库中的项i ；l ( i t e m s ) 或属性( a l 埘b u t 酷) 间的有趣关系，这些关系是事先未知的且隐藏的，也就是说不 能通过数据库的逻辑操作( 如：表的联接) 或统计的方法得出。这说明它们不是基于 数据自身的固有属性( 例如函数依存关系，f u n c t i o n a ld e p e n d e n c yr e l a t i o n s h i p ) ， 而是基于数据项的同时出现特征( c h a r a c t e r i s t i e s o f c o - o c c u r r e n c e o f d a t a i t e m s ) 。 所发现的关联规则可以辅助人们进行市场运作( m a r k e t i n g ) 、决策支持( d e c i s i o n s u p p o r t ) 、商业管理( b u s i n e s sm a n a g e m e n t ) 和网站设计( w e bs i t ed e s i g n ) 等 关联规则是数据挖掘的热点之一，是近年来主要的研究方向。关联规则反映 一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存 在一定的关联关系，那么其中一个事物就能够通过其他事物预测到。简单的说， 关联规则就是给定一组项目( i t e m ) 和一个记录集合，通过分析记录集合，推导出 项f l ( i t e m ) f i | 的相关性。关联规则广泛地应用于商业界、医疗保险、金融业、司 法部门等，因此对它的研究有着极其重要的意义。 a g r a w a l 等人首先定义了在事务数据库中挖掘关联规则的问题1 1 1 ： 设i 一饥，f ：，i 3 ，j 是由m 个不同的项目组成的集合( 习惯上我们还称， 为项集) 。设任务相关的数据d 是数据库事务的集合，其中每个事务t 是项的集 合，使得r ，。每一个事务有一个标识符，称作t i d 。设a 是一个项集，事务r 包含a ，当且仅当a t 。关联规则是例如a b 的蕴含式，其中a c ，口c i ， 并且a n b - g 。规则彳j b 在事务集d 中成立，具有支持度s ，其中s 是d 中 事务包含彳u b ( e p 彳和口二者) 的百分比。它是概率p ( a u b ) 。规则一 b 在事务集d 中具有置信度c ，如果d 中包含a 的事务同时也包含口的百分比为“ 这是条件概率p ( bi a ) 。其中支持度，置信度定义为： 6 s u p p o r t ( a j 口) - p u 口) c o n 膨e , , c e ( a b ) 一e ( al 冷 从某种意义上说，支持度能反映关联规则中a 和口的关系是否是普遍规律； 而置信度则反映了在这种情况下的关系方向，即是从a 到曰，还是从口到a 。但 随着关联规则研究的深入，我们发现置信度的描述不够完善，不足以表达项集之 间的相关程度。下面从理论上分析支持度置信度框架。支持度代表项目集出现 的频度，只有项目集频繁出现，我们才能比较准确地找出其中的规律。如果项目 集出现不够频繁，则很难从其中找到规律；置信度表示某些项目集的出现会导致 其他项目集的出现。但是我们看到关联规则a 命b 的置信度只考虑了a 出现时b 出现的可能性，而没有考虑到a 不出现时b 出现的可能性，以及a 和b 是否相 关。所以使得挖掘出的许多关联规则是无效的。在文献【3 l 】中，作者利用匹配度 取代置信度来产生关联规则。匹配度的定义为： m a t c h p ( a b ) - p ( a ) p ( b ) p ( 彳x 1 一删) ) 匹配度( m a t c h ) 的取值范围是【- 1 ，1 1 。从公式中可以看出：若m a t c h o ，则 p ( a b p ( a ) p ( b ) ，这可以说明a ，b 具有正相关性，具有研究价值。若m a t c h 0 ， 则p ( a b ) b ) = p ( b 脚= 0 5 6 ，a 和b 之间的匹配度m a t c h - - - 0 1 7 。我 们可以看出，a 与b 之间其实是无关的，但是支持度却给出了较高的规则，不 能正确的反应出他们之问的关系。而匹配度却能j f 确的反映出他们之间是无关的 这一规则。支持度一匹配度框架可以删除像a 这样频繁出现的，易产生负相关 的项集，从而得到更有意义的强关联规则。 关联规则的挖掘过程通常分为两步：因此匹配度相比于置信度更有利于关联 规则的提取。 第一步，挖掘所有频集，找到所有大于用户制定的最小支持度的项目集 ( i t e m s e t ) 。 第二步。由频集找出所有关联规则。在关联规则挖掘中，如果一个项目集的 支持度不小于用户定义的最小支持度( m i n s u p ) ，则称为频繁项目集；反之则称 为非频繁项目集。如果一个频繁项目集的所有超集( 即包含该项目集的所有项目 集) 都是非频繁项目集，则称该频繁项目集为最大频繁项目集 对每一最大项目集a 找到a 的所有非空子集a 7 果s u p p o r t ( a ) s u p p o r t ( a ) ：em i n c o n f u t e n c e 就生成关联规则口一0 一口) 。使用最大频繁项目集和最小支持度，最小置信 度的模式挖掘关联规则，可以显著的压缩挖掘所产生的频繁项集数。如果某一频 繁项集包含k 个项，则称为频繁k 项集，用厶代表。 2 2a p r i o r i 算法 对于事务数据库的关联规则算法研究目前有很多，但其中以a p d o f i 算法最 为著名，其他算法或是它的扩展，或是它的变种。这一小节我们主要介绍a p r l o r i 算法。 a 呻嘶算法是挖掘产生布尔关联规则所需频繁项集的基木算法，它是一个很 有影响的关联规则挖掘算法。a p d o d 算法就是根据有关频繁项集特性的先验知 识( p r i o rk n o w l e d g e ) 而命名的。该算法利用了一个层次顺序搜索的循环方法来完 成频繁项集的挖掘工作：这一循环方法就是利用k 项集来产生( 1 【+ 1 ) 项集。在 a p r i o r i 算法中，寻找最大项目集的基本思想是：算法需要对数据集进行多步处理。 第一步，简单统计所有含一个元素项目集出现的频率，并找出那些不小于最小支 持度的项目集，即一维最大项目集。从第一步开始循环处理直到再没有最大项目 集生成。循环过程是：第k 步中，根据第k - 1 步生成的( k 1 ) 维最大项目集产生k 维候选项目集，然后对数据库进行搜索，得到侯选项目集的项集支持度，与最小 支持度比较，从而找到k 维最大项目集。为方便后文叙述，现约定如下： 1 、数据库事务中的项目都是以字母顺序排列的，每个项目用t i d i t e m 标识， 这里1 1 d 表示相应事务的标识符，i t e m 则表示项目名称。 2 j 每个项目集的项目数称为该项目集的s i z e 。当项目集的s i z e = k 时，称 k - i t e m s e t 。下面是一个例子： 表2 - 2 数据库实例 皿i t e m i t e m ( 不含非频集) 1 a , c ，d ，f , g , i ，m ，pa , c , f , m ，p 2 a , b ，c , f , l ，m ，oa b c , f , m 3 b ，f , h , j ，0 b ，f 4 b ，c ，l p ，sb ，c , p 5 a , c ，e ，f , l ，m ，n ，pa , c ，f , m ，p 给定事务数据库如表所示，支持度为5 0 ( a p 支持度计数为3 ) 。求所有的频 8 集。 a p r i o r i 算法挖掘频集的过程如下： ( 1 ) ，扫描事务数据库一次，找到所有的1 项频繁集，即至少出现3 次的项 目。1 - 频繁集有：a ，b ，c 工m ，p 。它们组成了频繁1 项集，即l l 。 ( 2 ) 候选2 项集，记为q ，由l l 生成。这里，我们使用a p f i o r i 先验性质对 候选集剪枝。只有那些由频集组成的候选集才有可能是频繁的。当且仅当 x ，y e i ，项目集邪c ：。因此，候选2 - 项集的个数为：e 6 = 1 5 。 ( 3 ) 再一次扫描数据库计数c ：中的每一个项目集的支持度。由c ：中支持度大 于支持度阈值的项目集组成的集合称为频繁2 项集。记为k 。在这个例子中， k 包含项目集a c , a f , a m d , c m 和缸。 ( 4 ) 由k 得到候选3 - 项集。由a p r i 硎先验性质，只有所有子集( 2 项) 包含在 l 2 ( b p 是频繁的) 才有资格成为候选3 项集。例如，a c f 是一个长度为3 的候选集， 因为a c , a f 和c f 都包含在k 。具体的流程如图2 - 1 ； l lqk c 3 s l l i t j p o r t a 3 t b 3 ( c t 4 母 4 m 3 p 3 s u p p o r t a ，岛母 3 a 南m 3 a m 3 c ，m 3 i t e m s 曲 a ，c 蚺 a ，m a p b ，c b f ) b ，m ) b p c ，母 c ，m c ，p m p m ，p ， 9 i r e m s u l ，p o r l a c 3 a ，毋 3 a , m 3 c f 3 c ，i n 3 o p 3 m 3 图2 - 1 利用a p r i o r i 算法挖掘简单数据库的流程图 对事务数据库进行再一次扫描，所有支持度大于给定的支持度阈值的候选3 - 项集组成成频繁3 项集，记为b 。上述操作继续，直到不能产生新候选集或所 有侯选集都是非频繁的。 a d i o r i 算法虽然可以有效的挖掘事务数据库中的关联规则，但是却没有考虑 到项集之阃的先后顺序，不能 ：导到数据结构中隐含的关系。因此这种算法不适合 在有结构特征的序列数据库中挖掘关联规则。 第三章序列数据库中的关联规则挖掘 在关联规则挖掘应用中，序列数据库中的关联规则挖掘是关联规则研究所要 面对的一个新的问题。由于序列数据库中数据结构的特点，存在关联关系的不是 组成序列的项，而是在数据中由这些项组成的子序列，因此不能使用通常的关联 规则挖掘算法( 例如a p r i o r i 算法) ，在序列数据库中挖掘关联规则。在2 2 中已 经介绍了，使用a p r i o r i 算法挖掘数据库的前提是数据库事务中的项目都是以字 母顺序排列的，这是由于算法的局限性造成的。因为该算法在生成候选项集、扫 描数据库时只考虑了组成项集的项，而忽略这些项在数据的结构中是否存在着关 系。同时，我们还要注意到，在序列数据库中寻找最大频繁项目集已经没有什么 意义，我们要找的是“最长的频繁子序列集”。为了使a p d o d 算法能够在序列数 据库中挖掘关联规则，我们必须对其进行一定的修改。 3 1a p r i o r i 算法在序列数据库的应用 首先，我们给出序列数据库中的关联规则挖掘的描述：设序列数据库d - - 冬。，s ：，s ，s 。 ，是由序列组成的。每一个序列s i 有一个标识符，称作i 。i d l 代表数据库d 中序列的个数。在数据库d 中，一个序列a 的支持度是包含a 的 序列s 的个数，s u p p o r t ( a ) = s ls ed a n da t _ s 。由所有满足最小支持度阈值的序列 a 组成的集合称为频繁序列模式集f s ( t h es e to ff r e q u e n ts e q u e n t i a lp a t t e r n ) 。闭 合频繁序列模式集c s ( t h es e to fc l o s e df r e q u e n ts e q u e n t i a lp a t t e r n ) 定义为， c s = a i a e f s 并且不存在b e f s ，使得a c b 并且s u p p o r t ( a ) - - s u p p o r t ( b ) 。田合序 列挖掘就是发现满足最小支持度阈值的闭合频繁序列模式集 1 4 1 。然后用闭合频 繁模式集代表数据库中的每一条数据，再在闭合频繁序列模式集中挖掘关联规 则。 通过序列数据库中的关联规则挖掘的描述，我们可以了解到，在序列数据库 中，首先要找到所有满足最小支持度阈值的所有闭合频繁序列，然后再在这些闭 合序列之间挖掘关联规则。为了使a p r i o r i 算法能够在序列数据库中寻找闭合频 繁序列，这就要求从1 项频集生成2 项候选集开始，生成的候选集是序列的集 合，而不是项集的集合。同时在扫描数据时，搜索的是数据的子序列而不是原来 的项集。通过这样的办法，使得a p d o d 算法能够适用于序列数据库中的关联规 则的挖掘。 1 1 序列数据库的主要代表是生物信息学研究的d n a 数据库。由生物学知识我 们知道，在d n a ( 脱氧核糖核酸，d e o x y r i b o n u c l e i ca c i d ) 分子中只有4 种不 同的碱基：鸟嘌呤，腺嘌呤，胸腺嘧啶和胞嘧啶( g ，a ，t 和c ) 。d n a 分子以特 定的核苷酸的序列( s e q u e n c e ) 携带遗传信息。 比较生物信息学中计算的方法，关联规则挖掘有着速度快、占用的资源少的 优点。在基因d n a 数据库中进行关联规则挖掘，我们可以很方便的找至q 所有满足 最小支持度的基因片段( 闭合频繁序列) 。这些频繁出现的基因片段可能是某 模式或是某一模式的一部分，同时我们也注意到，它们作为基因中的保守部分， 在基因中有其确定的位置，而这些基因片段的位置关系体现了基因的结构信息。 利用优化的经典a p r i o r i 算法，可以找到所有的满足最小支持度的由基因片段组 成的序列结构。通过这些序列结构，我们就可以从己知基因序列预测新基因序列 的结构和功能。 但是，我们也要看到，由于关联规则挖掘的特点，满足最小支持度的基因片 段的长度( 含有碱基的个数) 是不定的，有的可能很长，有的却很短。对于长基 因片段来说，由于其出现在其他基因的概率小，所以由长基因片段中得到的生物 学信息更可靠。而短基因片段在其他基因中出现的概率高，对于挖掘生物学信息 没有太大的意义。因此，我们需要剪枝掉这些在其他基因中也频繁出现的基因片 段，得到更有意义的生物学信息。在2 1 中已经介绍了在支持度一匹配度框架下 挖掘关联规则的方法可以删除那些频繁出现，并且容易产生关联规则的闭合频繁 序列，得到有意义的规则。 3 2 本文所采用的基因数据的简单介绍 本文选用的两类基因数据来t ln c b i ，即美国国立生物技术信息中心，它是 在n i h 的国立医学图书馆( n l m ) 的一个分支。n l m 是因为它在创立和维护生物 信息学数据库方面的经验被选择的，而且这可以建立一个内部的关于计算分子生 物学的研究计划。n c b i 的任务是发展新的信息学技术来帮助对那些控制健康和 疾病的基本分子和遗传过程的理解。本文选用了其中的”r a ka l p h a 9 基因和 ”h b s a g ”基因数据库。 3 2 1r a ka l p h a 基因 r a ka l p h a 基因是一种和癌基因组有关一个基因。最早是在乳腺癌和子宫癌 基因组前发现其存在的。r a ka l p h a 基因已经被证明了1 0 0 出现在与恶性癌症有 关的基因组d n a 序列案例中、2 5 的可能出现在良性卵巢癌中，4 0 的可能出现在 子宫癌中。因此可以寻找r a ka l p h a 基因来准确的诊断和预测癌症o “。本文研究 的r a ka l p h a 基因包括了n c b i 中全部2 2 条d n a 序列数据( 每条数据大概包含 1 2 1 5 0 个碱基) 。来源为：h i v - l i k eh u m a nc a n c e rv i r u s ，数据名称h i v - l i k eh u m a n c a n c e rv i r u si s o l a t i o n - s o u r c ep a t i e n tx ( n u m b e r ) p r o s t a t e c a n c e r a s s o c i a t e da n t i g e n ( r a ka l p h a ) g e n e ，c o m p l e t es e q u e n c e 。 3 2 2 哪s a g 基因 乙肝病毒表面抗原( h b s a g ) 是乙型肝炎病毒( h b v ) 的外膜蛋白，由h b v 的s 区所编码( s b v 的基因组为部分双链环状d n a ，约3 2 k b ，至少有4 个开放 阅读框架( o r f ) 称为c 、p 、x 、s ) ，s 区又分为s 基因、p r e s l 基因和p r e s 2 基 因3 段。s 基因区所编码的产物除了在病毒及亚病毒颗粒的装配中作为主要成分 外，还刺激机体产生中和性抗体或称为保护性抗体。因此研究h b s a g 基因的结构 和功能，有利于乙型肝炎病毒的基因工程疫苗的研究。相对于血源性乙肝疫苗 ( p d v ) ，基因工程乙肝疫苗更安全、价格更便宜、更适合于工业化的生产。n c 8 i 数据库中关于乙型肝炎病毒的序列数据有近1 7 ，0 0 0 多条。本文研究的h b s a g 基 因数据共有4 5 条d n a 序列数据( 每条数据大概包含5 2 5 - 6 8 1 个碱基) ，来源于： h e p a t i t i sbv i r u s 、数据名称h e p a t i t i sbv i r u sh b s a gg e n ef o rs u r f a c e a n t i g e n ，p a r t i a lc d s ，i s o l a t e ：p a t i e n tx ( p a t i e n tn u m b e r ) 。丽其他大量 非此名称的序列没有选用。 第四章在基因数据库中挖掘关联规则的算法以及实例 4 1 一种新型的挖掘基因数据库的关联规则算法 本章借鉴关联规则的a p r i o r i 算法和序列数据库挖掘闭合频繁序列的算法， 提出了一种新型的可以挖掘序列数据库中的闭合频繁序列之问的关联规则算法。 该算法可以准确、快速的找到所有的满足最小支持度闭合频繁序列，并在此基础 上挖掘闭合序列之间隐含的关联规则，这是一种针对利用关联规则挖掘d n a 序列 数据库中生物学信息的一种新的尝试。为了便于介绍算法，本文设计了一个简单 的数据库，如下表4 一l ： 表4 - 1 简单d n a 数据库 序号d n a 序列 基因名称 1舭碍c f j a 4 c , c ，g c a 五| 辱霉c c g e n e l 2碍碍g c c f 辱4 c c c c 4 强碍t , c ，g c g c n c l 3 霉霉g c 石石霉a c c g c 霉g g 写c 耳cg c n c l 4 c c g c it ，c a c ，c c c ，c g a , g , t , c , c , t , g e n e l s 鹰4 a 互 4 鹰c c c , c a , t , g c , a , t , a , c g e n e 2 6 g g j ； 】二a g c c c ，c 4 霉q c a , t , g e g e n c 2 7 霉互霉a 写冉4g c c c ，c 霉g g c a 石刀c窖蛐e 2 8 c 互 j l t c g c c c c c z g c a , t , c a g e n e 2 这是一个由8 条基因序列数据组成的d n a 数据库，每条数据表达了一种基因 中碱基排列情况，共两种基因( g e n e l 、g e n e 2 ) ，它们来自不同的人。每条数据 包含2 0 个碱基和一个与这个d n a 序列的基因名称。虽然由于交异，在不同人的 同类基因中的碱基排列情况不同，但是它们包含了大量的相似的基因片段。 4 1 1 编码 为了便于程序实现，首先对数据进行编码；a 一1 ，g 之，g 3 ，l - 4 ，g e n e l - - 5 ，g e n e 2 - - 6 。同时，由于同一个基因所包含的碱基个数也不是确定的，为了 方便程序的读取，把基因编码放到数据的最前面。这样上面的简单数据表示为， 如表4 2 ： 表4 -