（计算机应用技术专业论文）基因表达数据关联规则挖掘算法研究.pdf

硕士学位论文 摘要 随着人类基因组研究的重点向功能基因组转化，基因表达数据分析成为目前 生物信息学研究的热点和重点之一。关联分析是基因表达数据分析的一种重要手 段，通过关联规则挖掘可揭示不同基因或环境与基因表达之间在生物学相关的联 系，进而帮助鉴定人类疾病基因。本文着重研究基因表达数据的关联规则挖掘算 法。 a p r i o r i 算法是关联规则挖掘的经典算法，然其效率有待改善。基于a p r i o r i 算法原理，提出了完全连接的概念并给出一种有效的完全连接条件，在频繁2 卜 项集的集合进行自身a p r i o r i 连接得频繁( 2 6 - 1 ) 一项集的同时，自身完全连接产生 未剪枝的候选4 卜项集；对频繁( 2 k + 1 ) 一项集的集合，直接对其项集进行自身完全 连接产生未剪枝的候选( 4 k + 2 ) 一项集。改进的算法减少了连接的比较次数、迭代运 算次数。实验表明该算法在保证无遗漏的情况下有效地提高了挖掘速度。 采用a p r i o r i 等传统算法对基因表达数据进行关联规则挖掘时，在将基因表达 矩阵转换为布尔矩阵之后，还需将布尔矩阵转化为交易数据的形式进行挖掘，没 有充分利用布尔矩阵本身的特点。针对这些缺点，本文提出了一种不生成候选项 集的“与运算”直接对布尔矩阵进行挖掘，且采用分段求与的方法提高“与运算” 的算法效率。实验证明该算法能更快速有效的挖掘出关联规则。 针对目前基因表达数据的关联规则挖掘所采用的都是将其转换成布尔关联规 则进行挖掘，忽略了基因表达数据是数值型这一问题，本文提出了使用充分利用 基因表达值的模糊方法挖掘基因表达数据的关联规则，并且通过使用模糊c 均值 聚类算法代替隶属函数，将每个基因划分为3 个模糊集，确保挖掘结果的正确性。 关键词：基因表达数据；关联规则；a p r i o r i 算法；与运算；模糊关联规则挖掘 基因表达数据关联规则挖掘算法研究 a b s t r u c t a st h ef o c u so fh u m a ng e n o m ep r o j e c tt u r n st of u n c t i o n a lg e n o m i c s ，a n a l y z i n g t h eg e n e e x p r e s s i o nd a t a i so n eo ft h eh o tp r o b l e m si nb i o i n f o r m a t i c ss c i e n c e s a s s o c i a t i o nr u l em i n i n gi so n eo ft h ei m p o r t a n tm e t h o d sf o ra n a l y s i n gt h eg e n e e x p r e s s i o nd a t a a s s o c i a t i o nr u l e sc a nr e v e a lb i o l o g i c a l l yr e l e v a n ta s s o c i a t i o n sb e t w e e n d i f f e r e n tg e n e so rb e t w e e ne n v i r o n m e n t a le f f e c t sa n dg e n ee x p r e s s i o n ，a n dt h e nh e l pt o i d e n t i f yd i s e a s eg e n e i nt h i sp a p e r ，t h ea l g o r i t h mo fa s s o c i a t i o nr u l e sm i n i n gi nt h e e x p r e s s i o nd a t ai ss t u d i e d a p r i o r ii st h ec l a s s i c a la r i t h m e t i co fa s s c i a t i o nr u l em i n i n g b a s e do nt h ep r i n c i p l e o fa p r i o r i ，w ep r e s e n t sac o n c e p t i o nw h i c hc a l l e da b s o l u t e l yj o i n ，a n dg i v ea ne f f e c t i v e q u a l i f i c a t i o no fa b s o l u t e l yj o i n ，i nw h i c ht h ec a n d i d a t e4 k - i t e m s e t sw a sb u i l td i r e c t l y w i t ha b s o l u t e l yj o i nw h i l ec r e a t et h ec a n d i d a t e ( 2 七+ 1 ) - i t e m s e t sf r o mt h em u s t e ro f f r e q u e n t2 k - i t e m s e t s ；a n do n l yu s et h ea b s o l u t e l yj o i nf o rt h em u s t e ro ff r e q u e n t ( 2 针1 ) 一i t e m s e t st oc r e a t et h ec a n d i d a t e ( 4 k + 2 ) 一i t e m s e t s t h i sa l g o r i t h md e c r e a s e st h e t i m e so fi t e r a t i o na n dt h ec o m p a r e t h ee x p e r i m e n tr e s u l t ss h o wt h a tn of r e q u e n t i t e m s e t si sm i s s e da n dw h a t sm o r et h es p e e do ft h em i n i n gi se f f e c t i v e l yi m p r o v e di n t h i sa l g o r i t h m w h e nw eu s et h et r a d i t i o n a r ya l g o r i t h ms u c ha sa p r i o r it om i n i n gg e n ee x p r e s s i o n d a t a ，t h eg e n ee x p r e s s i o nm a t r i xs h o u l df i r s tc h a n g ei n t ot h eb o o l e a nm a t r i x ，a n dt h e n t r a n s f o r m e dt h ed a t ai n t ot h ef o r mo fb u s i n e s sd a t ab a s e do nt h eb o o l e a nm a t r i x w h i c h i g n o r e dt h ec h a r a c t e r i s t i co ft h eg e n ee x p r e s s i o nd a t aa n d a c c o r d i n gt ot h o s ef l a w s ， t h i sp a p e rp r o p o s e sa n “a n do p e r a t i o n a l g o r i t h mw h i c hm i n i n gr u l e sd i r e c t l yo n b o o l e a nm a t r i xa n dw o n tt r e a tc a n d i d a ti t e m s e t s ，f u r t h e rm o r e ，t h r o u g ho p e r a t i o ni n s u b s e c t i o nt oi m p r o v et h ee f f i c i e n c yo f “a n do p e r a t i o n ”a l g o r i t h m t h ee x p e r i m e n t r e s u l t ss h o wt h a tt h ea l g o r i t h mc a nm i n ef r e q u e n ti t e ms e t sm o r ee f f e c t i v e l ya n df a s t e r a tp r e s e n t ，t h em e t h o df o ra s s o c i a t i o nr u l em i n i n go fg e n ee x p r e s s i o nd a t ai st u r n i tt ob o o l e a na s s o c i a t i o nr u l e sm i n i n g ，i ti g n o r e dt h ec h a r a c t e r i s t i ct h a tt h ee x p r e s s i o n d a t ai sn u m e r i c a lv a l u e s o ，b a s e do nt h i sp o i n t ，t h i sp a p e ri n t r o d u c et h ef u z z ym e t h o d t om i n i n gq u a n t i t ya s s o c i a t i o nr u l e so fg e n ee x p r e s s i o nd a t a ，a n dt h o u g hu s i n gt h e f u z z yc m e a n sr e p l a c em e m b e r s h i pf u n c t i o nt op a r t i t i o ne a c hg e n et ot h r e em u s t e r s b a s e do nt h ee x p r e s s i o nv a l u e ，w h i c hi n s u r et h ea s s o c i a t eo fg e n ei sa c c u r a t e i i 硕士学位论文 k e y w o r d s ：g e n ee x p r e s s i o nd a t a ；a s s o c i a t i o nr u l e s ；a p r i o r i ；a n do p e r a t i o n ； m i n i n gf u z z ya s s o c i a t i o nr u l e s n 1 基因表达数据关联规则挖掘算法研究 插图索引 图1 1 全文结构图 图2 1 数据挖掘中知识发现的核心过程 图2 2 基因表达数据截图 图2 3a p r i o r i 算法挖掘过程示图 图2 4 存放压缩的频繁模式信息f p 树一 图2 5 布尔矩阵的生成 图3 1a p r i o r i 与n e w a r p i o r i 算法运行时间比较一 图4 1m = 1 6 的分解示图 图4 2m = 1 7 的分解示图 图4 3 结果频繁项集截图 图4 4 算法挖掘时间比较图 图4 5 事务数为3 0 时运算次数比较 图4 6 事务数为7 0 时运算次数比较 一om挖h筋如如如驺弘弘 硕士学位论文 附表索引 表3 1 结合完全连接a p r i o r i 算法与a p r i o r i 算法效率对比2 4 表3 2 基因表达实验数据2 4 表3 3 基因表达布尔矩阵2 5 表3 4 输入表达数据格式2 5 表5 1 模糊化后的基因表达数据一4 l 表5 2 删除正常表达基因后的表达数据一4 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： j 耖u 日期：彤年；，月q 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密耐。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 主未砂日期：肋2 年每月明日 日期：诊占年专月叼日 _ _ _ _ - _ _ _ _ _ _ _ _ _ - - _ _ _ _ _ - _ _ _ _ _ _ _ _ i _ - l _ l - _ _ _ _ _ _ _ _ - _ _ _ 。一。 第1 章绪论 随着人类基因组计划的深入，产生了海量的基因数据，如何分析这些具有丰 富内涵的数据并从中获得有关生物结构和功能的信息，从中得到对人类有益的信 息，是目前生物信息学研究的重点。数据挖掘是一项很重要的数据分析工具，为 基因和蛋白信息的分析和提取提供了强有力的手段，逐渐成为生物信息学研究领 域的重要方法之一。 1 1 选题的背景与意义 生命科学近年来获得突破性进展“，随着生物学和医学的迅速发展，生物数 据呈指数级增长，无论是在数量上还是在质量上都极大的丰富了生物科学的数据 资源，提供了揭开生命奥秘的数据基础。然而生物数据种类丰富，高通量，维数 高，本质上具有异质性与网络性，远远超出传统的分析方法的能力和速度，其处 理、挖掘、分析和理解日益迫切。如何分析这些具有丰富内涵的数据并从中获得 有关生物结构和功能的信息，从中得到对人类有益的信息，是生物研究的瓶颈， 是当前研究所面临的一个严峻挑战。生物信息学。是在此背景下发展起来的综合运 用生物学、数学、信息学以及计算机科学等诸多学科理论方法的崭新交叉学科， 是在生命科学的研究中，以计算机科学知识为辅导工具对生物信息进行储存、检索 和分析的科学，是当今生命科学和自然科学的重大前沿领域之一。它包含两方面 的内容，一方面是对海量数据的搜索、管理、服务，即“管好数据”；另一方面 从中发现规律，即“读懂”数据。 随着人类基因组计划的完成，生物信息学的研究重点已经从开始的序列分析、 数据库查询逐渐向生物信息的挖掘、表达、数据多样性分析的方向发展，基因表 达数据”1 分析成为目前生物信息学研究的热点和重点。基因表达数据是通过一些实 验测量技术得到的，这些数据往往包含几千个基因或基因片断和几十个属性。基 因表达数据，无论是转录水平上还是蛋白质水平上，其中都蕴含着丰富的生物学 知识，可以帮助我们理解基因、理解生物、理解细胞等等，例如某疾病是由什么 基因引起的、细胞是处于正常还是恶化状态、药物对肿瘤细胞是否有效等。由于 越来越多基因表达数据得以公开，人们迫切希望通过数据挖掘技术在这些具有丰 富内涵的海量数据中获得有益的信息。对基因表达数据的分析可以获取基因功能 和基因表达调控信息，这是生物信息学的重大挑战之一，也是d n a 微阵列能够在 生物医学领域中广泛应用的关键原因之一，它们在医学临床诊断、药物疗效判断、 揭示疾病发生机制等方面有重要的应用。 数据挖掘“”是新兴的一种科学计算技术与数据分析方法，它能够有效地从存 基囡表达数据关联规则挖掘算法研究 有海量信息的数据库中提取隐含的、事先未知的潜在的和有用的信息和知识，经 过多年的研究与发展，它已经成为一项很熏要的数据分析工具。作为一种以数据 库、统计学和人工智能学为基础的新兴技术，数据挖掘给基因组学家们提供了前 所未有的数据分析工具，为基因和蛋白信息的分析和提取提供了强有力的手段。 生物信息学、数据挖掘两者的结合，不论是现在还是将来，不论在理论上还是应 用上都具有十分重要的意义。因此生物数据挖掘日益重要，逐渐成为生物信息学 研究领域的关键。 关联规则挖掘是数据挖掘的重要模式之一“。”，它用于发现大量数据中项集之 间有趣的关联或相关联系主要用于顾客交易数据库中发现各个项目之间的关系。 同时，它也是基因表达数据的一种重要分析方法。通过关联规则挖掘可揭示不同 基因间或环境与基因表达之词在生物学相关的联系。它通过分析在同一环境下各 个基因的关联度，发现基因之间的关联水平，可以帮助鉴定人类复杂疾病基因8 1 “， 同时它也是基因表达数据聚类分析、分类分析研究的辅助方法“”1 ，逐渐成为基 因表达数据的重要分析工具n ，。 1 2 本文研究的目的 基因表达数据分析是目前生物信息学研究的热点和重点“1 ，作为基因表达数据 分析的主要方法之的关联分析也倍受关注。关联分析韵目的在于发现数据中项 集之间的规则，因而发现规则的挖掘算法成为研究的关键。经典的关联规则算法 a p r i o r i 算法是基因表达数据关联规贝畦挖掘的常用算法“，然而众所周知，可能产 生大量的候选集以及可能需要重复扫描数据库是a p r i o r i 算法的两大缺点“”，其 挖掘效率有待提高。为减少a p r i o r i 算法的挖掘时间，提高其挖掘效率，需要对 a p r i o r i 算法进行改进，更快速有效地挖掘出关联规则。在研究分析a p r i o r i 算法的 优缺点的基础上对其进行改进，得到改进的a p r i o r i 算法是本文研究的目的之一。 目前对于基因表达数据的关联规则挖掘研究还处于起步阶段“，采用与交易 数据相同的方法对其进行挖掘t 然而由于生物体中的细胞种类繁多，同时基因表 达具有时空特异性，基因表达数据和通常的数据相比，其数据量、数据的复杂程 度都是其它数据无法比拟的。从分析基因表达数据的特点上讲，更需要一些新的、 更好的、更适合的算法0 1 。因此从基因表达数据韵特点出发，为基因表达数据的关 联规则挖掘提供新方法是本文研究的关键。 1 3 本文主要工作 本文主要研究的是基因表达数据关联规则挖掘。以现有的基因表达数据关联 规则挖掘算法为出发点，本文在a p r i o r i 的基础上提出了基于完全连接的改进 a p r i o r i 算法；继而在分析基因表达数据韵数据形式以及挖掘目的的基础上提出了 硕士学位论文 基于分段与运算算法；然后根据基因表达数据为数值型这一特点对基因表达数据 进模糊量化关联规则挖掘。又因为关联规则挖掘的关键技术主要集中在如何减小 关联规则挖掘算法实现的时间复杂度，如何确保算法所挖掘出来的规则的j 下确率 ，故本文通过实验比较了算法的挖掘时间，验证了新算法的正确性。论文主要工 作如下： 一、基于完全连接的改进a p r i o r i 算法 在研究分析基因表达数据关联规则挖掘算法a p r i o r i 算法的基础上，从连接步 着手，提出了完全连接的概念并给出了一种有效的完全连接的条件，改进了a p r i o r i 算法，然后通过实验比较了该算法与a p r i o r i 算法的性能。主要完成以下几个工作： 1 设计实现已有的关联规则挖掘算法a p r i o r i 算法。 2 对已有关联规则经典算法a p r i o r i 算法进行改进，提出了基于完全连接的改进 a p r i o r i 算法。 3 通过实验对a p r i o r i 算法和新算法的挖掘结果、挖掘时间进行比较。 二、基于分段与运算的关联规则挖掘 在研究分析基因表达矩阵特点的基础上，本文提出使用“与运算”挖掘基因 表达数据频繁项集，并且通过分段求与提高“与运算”的算法效率，该算法能充 分利用基因表达矩阵所特有的形式且不会产生候选频繁项集。然后通过实验对该 算法与已有算法的性能进行了对比。主要完成以下几个工作： 1 设计实现基于分段与运算的关联规则挖掘方法。 2 通过实验对已有算法和基于分段与运算的频繁项集挖掘算法的挖掘结果、挖掘 时间进行比较。 三、基于模糊c 均值的基因表达数据模糊关联规则挖掘 在研究基因表达数据以及量化关联规则挖掘的基础上，基于基因表达数据为 数值型的特点，提出使用模糊量化关联规则代替传统的布尔关联规则挖掘基因表 达数据，并根据基因表达数据关联规则挖掘的需要，使用模糊c 均值聚类算法代 替隶属函数，将每个基因划分为3 个模糊集。主要工作有： 1 设计实现基于模糊c 均值的模糊关联规则挖掘算法。 2 对新算法进行算法分析。 1 4 本文组织结构 全文分为五章，主要内容如下： 第一章为绪论，概述了本文选题的背景与依据、研究目的、内容以及组织结 构等。 第二章为相关知识，详细介绍了生物数据挖掘，基因表达数据以及关联规则 的基本概念、主要算法及国内外研究进展情况，最后介绍了基因表达数据关联规 鏊困表达数撼荚联瓶瑟# 挖稼舅法研究 则挖掘的方法步骤。 第三章，在分辑经典关联褒则挖獬算法a p r l o r i 算法豹基戳上，铮对冀审不足， 提出了一种耨的关联规则挖掘算法种结合宠垒连接豹改进a p r i o r i 算法，并 对两算法结果进行比较。 第四章，分析基因表达数据的形式的基础上，提出使用分段与运算撼掘基因 袭这数蠢关联筑爨，势冬已有算法透葶亍逡较。 第五章，基于基因激达数据是数值型这一特点，提出馊用模糊方法挖掘基因 表达数据关联规则，并鼠使用模糊c 均值聚类冀 去代替隶属瞰数确保了挖掘结果 瓣正壤蠖。 最后总缩全文。文露结构如图1 1 。 第1 章绪论 第2 章 基因巍然数据关联规划 捆燕研究 第3 章 一种站台完全连接的潋 避a p r i o r i 算法 1 5 小结 第4 章 基于分段与运算的篓鞠 表达数据燕联规则挖懈 第5 章 基于横蝴c 均值的基因 表达数撼量化关联规劓 第6 章牯论 翟l 。 垒室壤辘瓣 本章必论文静绪论，奔绍了零突戆选题背爨与意义、磷究露鲍、主燮王传淡 及全文静缀织结构。 第一节介绍了选题的背景与意义； 第二节简单介绍本文的研究目她； 第三繁攘述了本文豢簧王箨； 第四节为全文的组织结构。 硕士学位论文 第2 章相关知识 随着后基冈时代的到来，基因表达数据分析成为目前生物信息学研究的热点 和重点，人们迫切希望能在这些具有丰富内涵的海量数据中获得有益的信息。关 联规则挖掘是数据挖掘的重要模式之一，也是基因表达数据的一种重要分析方法， 可揭示不同基因间或环境与基因表达之问在生物学相关的联系。 2 1 生物数据挖掘 数据库中发现知识( k d d ) 一词首次出现是在1 9 8 9 年举行的第十一届国际联 合人工智能学术会议上，它泛指所有从源数据中发掘模式或联系的方法。数据挖 掘( d m ) “”的本质就是知识发现，是数据库知识发现的精髓，指的是从存有海 量信息的数据库中识别出新颖有效、潜在有用的并最终可理解的非平凡知识的过 程“”。这些数据可以是结构化的，如关系数据库中的数据，也可以是半结构化的， 如文本，图形，图像数据，甚至是分布在网络上的异构型数据。发现了的知识可 以被用于信息管理、查询优化、决策支持、过程控制等，还可以进行数据自身的 维护。数据挖掘借助了多年来数理统计技术和人工智能以及知识工程等领域的研 究成果构建自己的理论体系，是一个交叉学科领域，可以集成数据库、人工智能、 数理统计、可视、并行计算等技术。它融合了数据库技术、智能技术、模式识别 和统计学等众多学科领域的理论与方法，形成了完整的数据集成、知识挖掘、模 式评价和验证理论与方法。文献 1 5 对数据挖掘的基本过程和主要步骤进行了详 细的介绍( 图2 1 ) 。 图2 ，1 数据挖掘中知识发现的核心过程 数据挖掘技术己被应用到生物信息学领域并取得了相当大的成功“，k d d 2 0 0 1 年b i o k d d 的主题就是生物信息挖掘“。在生物信息处理领域中，可以发现的知识 模式主要有：概念类别描述、关联分析、分类和预测、聚类分析、孤立点分析以 及演变分析“”。我们可以从以下几个方面看出： 及演变分析“”。我们可以从以下几个方面看出： 基因表达数据关联规则挖掘算法研究 ( 1 ) 在d n a 数据分析中，由于广泛多样的d n a 数据高度分散，随机地生成与使 用，对这种异构和广泛分布的基因数据库的语义集成就成为一项重要任务，以便 于对d n a 数据库进行系统而协同的分析而数据挖掘中的数据清理和数据集成方 法将有助于基因数据集成和用于基因数据分析的数据库的构建“。 ( 2 ) 可视化工具和遗传数据分析：基因的复杂结构和序列模式通常可以由各种 可视化工具以图、树、晶格和链的形式展现，这种可视化的结构和模式方便了模 式理解、知识发现和数据交换，日前有许多学者从事这方面的研究“。 ( 3 ) 聚类分析：对于采集到的生物信息进行处理的一个重要模块就是断症，也 就是聚类，即把数据划分为一系列有意义的子集。聚类技术主要包括传统的模式 识别方法和数学分类法，如决策树归纳、贝叶斯分类、神经网络技术、k 一中心聚 类、基于知识的案例推理、遗传算法、粗糙集和模糊逻辑技术等“。斯洛文尼亚 的m i l a n z o r m a n 和m a s u d ag 等人在用数据挖掘技术对基因数据库进行详细分析的 同时还专门探讨了从这类缺乏先验知识的海量数据中采用决策树和关联规则算法 的效率及其改进方法“。 ( 5 ) 数据挖掘中的关联分析是目前糖尿病数据库这类多维数据分析课题中应 用最广泛和有效的强有力的工具”“。 ( 4 ) 目前蒸因表达是研究热点，尤其是那些多基因联合控制的性状受到了人们 更多的关注，因为大部分致病因索不是由单一基因引起的，而是多基因组合起来 共嗣作用的结果。关联分析方法可用于帮助确定在目标样本中同时出现的基因种 类4 】。 2 2 基因表迭数据 随着c d n a ( c o m p l e m e n t a r yd n a ) 微阵列和寡核督酸芯片( 统称为d n a 微阵 列) 等高通量检测技术的发展，我们可以从全基因组水平定量或定性检测基因转 录产物m r n a 。基因表达数据。1 指基于d n a 徽阵列实验得到的反映m r n a 丰度的 数据，这些数据往往包含几千个基因或基因片断和几十个属性。基因表达数据的 实验铡量技术最常用的有四种“1 t 哈佛大学提出的c d n a m i c r o a r r a y 技术、基因芯 片技术、序列分析基因表达技术( s a g e ，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 ) 、 实时p c r 技术。大量基于d n a 微阵列实验的基因表达数据是公开发布在i n t c m e t 网上的，尤其是学术机构在发表论文时所用的实验数据都可以免费提供给全世界 的研究人员下载使用。目前，收集、存贮微阵列基因表达数据的最有影响的数据 库和网站是g e 0 、a 1 1 r a y e x p r e s s 和8 m d 。 图2 2 是一段基因表达数据的片断，列是同一环境下所有基因的表达情况。 通常的基因表达数据是高维的，一般至少有八，九维，甚至多达一百维。 硕士学位论文 n a m e y h r 0 5 1 w y k l l 8 1 w y h r l 2 4 w y h l 0 2 0 c y g r 0 7 2 w 一0 1 7 0 1 0 - 0 3 8 s p o r u l a t i o n3 0 m - 0 3 8 - 0 6 4 - 0 4 7 0 0 1 - 0 0 2 s p o r u l a t i o n2 h - 0 4 5 - 0 7 9 - 0 7 9 - 0 6 0 1 4 2 图2 2 基因表达数据截图 基因表达数据反映的是直接或间接测量得到的基因转录产物m r n a 在细胞中 的丰度，这些数据可以用于分析哪些基因的表达发生了改变，基因之间有何相关 性，在不同条件下基因的活动是如何受影响的。它们在医学临床诊断、药物疗效 判断、揭示疾病发生机制等方面有重要的应用。由于生物体中的细胞种类繁多， 同时基因表达具有时空特异性，因此，基因表达数据与基因组数据相比，要更为 复杂，数据量更大，数据的增长速度更快。如何充分利用这些数据，在这些具有 丰富内涵的海量数据中获得有益的信息，是当前研究所面临的一个严峻挑战，也 是d n a 微阵列能够在生物医学领域中广泛应用的关键原因之一。因此数据挖掘技 术正逐渐成为生物信息学研究领域的关键。 一次微阵列实验能获得细胞在某一条件下的全基因组表达数据，包含成千上 万个基因在细胞中的相对或绝对丰度，不同条件( 细胞周期的不同阶段、药物作 用时间、肿瘤类型、不同病人等) 下的全基因组表达数据就构成了一个g x n 的数 据矩阵m ，通常情况下g ，其中元素并“表示第f 个基因在第，个条件下的表 达水平值，行向量算尸0 1 1 尚2 ，j 舢代表基因f 在不同条件下的表达水平，列向量 x f u , x z i * oo j g ，) 代表某一条件下的各基因的表达水平。本文其它关于基因表达数 据的描述都以矩阵m 为例。 m = 葺1 x 1 2 。x , n x 2 1x 2 2。x ：n x mx 6 2 x g n 按行来分析，关系可以表示为r ( g i 盔x i l ，坼2 ，x l ) ，其中，g i d 表示的是标识 不同基因的基因名，x ，l 1 2 ，# ，则表示不同基因在不同实验环境中的值。比较矩 阵行的相似性或差别，如果发现两个行相似，我们可以推测它们对应的基因具有 协同调节和功能相关性。聚类和分类分析正是基于行进行分析o “。 按列分析，关系可以表示为r ( t i d ，x l j ，x 2 j ，x a j ) ，其中，t i d 表示不同的环境 的标识，而x y , x 2 j ，j 西则表示在环境t i d 下各个基因的表达水平。通过分析在同 一环境下各个基因的关联度，发现基因之间的关联水平。对基因表达数据进行关 联规则挖掘多是基于列进行分析。 o 蠹 加 吨 吨 0 印 蒸因表这数据荚联蕊戴携援雾浃赣究 市场分析研究的数据集可以描述为露( t i d ，i l , f 2 ，f 。) ，其中t i d 是交易的标识， i l ，赴，& 表示的是属性，也就是扶商场购买的物品。这与基因表达数据的模式不同 之筵在予i l ，i 2 ，毛是耪赫名，其有麴哭程不魏买之分；丽x i j , x 2 j ，加，是各个基因 的表达水平，是有一定数值的。目前对基因表达数据进行关联规则挖掘采用将基 趿表达数据离散化成为布尔值，采用岛分析市场数据相同的算法进行挖掘。第四 警鲶出关联缀甄挖掘蓦爨袭达数据戆莎辕详缀奔缁。 2 3 关联规则 r 。a g r a w a l 等人最先携氆了关联羧爨| l 强”，势簸鼙摄爨了关联矮赠挖撼冀法一一 a p r i o r i 算法珏“3 ，它是k d d 研究串一个重要的研究课题，用予发蕊大量数瓣中项 熊之间有趣的关联或相关联系。关联规则目- 前主毅用于顾客交舄数据库中发现各 个矮基之掘的关系，铡如，买西包的蹶容有9 0 靛人还买牛奶，这是一条关联媲 簧| j 。若蠢癌率将瑟毯稳警疑藏在一起镄售，籍会援麓宅餐静镑爨。在丈墅簸据疼 中，这种关联规则是很多的，需要进行筛选，一般用“支持发”和“可信縻”两 个阀值来淘汰那些无用舶必联规则。“支持度”表示该规则所代表的事例( 元组) 基全部事爨( 嚣缝) 茨蠢分魄。魏买嚣键叉买孛辫靛鬏窖占全部颧窖靛吾分院。“霹 储度”表示谈规鲻所代表群钢占满跫箭提条件事钢的百分毙。如买强毯义买牛奶 构顾客占买嬲包顾客中的9 0 ，可信成为9 0 。黻着大量数据不停的收集和存储， | 警多业界人士对于从他们的数据库中挖握关联挠则越来魅感必趣。扶大量赣务事 务记录孛笈璃有趣豹关联荚系，胃弦帮韵诲多裔务块策垂冬潮窝，魏分类竣诗、交 叉购物和贱爨分析。关联规则挖掘酌一个典型例乎就是购物熬分析。该过程通过 了解哪些商晶频繁地被顾客同事购哭，帮助制定凿锆策略。关联规则挖掘辣法就 怒找寻数鬃澜荚联羲方法。 2 3 1 关联规则的概念 设l = f b 坟，k 是项的集合，任务相关的数据n 是事务檠，其中每个事务t 怒瑗集，後褥室l 。每一令事务骞一令糠疆羚，称终t 辩。设a 是一令瑗繁，事 物t 包含a 当且仅当a 誊t 。关联规则是形如ta 潍b 的蕴撼式，其中a c l ，b c l ， 鼠a nb = 零。规则a j n 在事务d 中成立，具有支持度s ，其中8 是d 中搴务包 禽a u b ( 鼯a 移b 二誊) 豹酉分比。它鲍概率怒p 溶u 黝。龆聚d 中惫食a 豹 攀务同时也包含b 豹西分院是e ，羽线瓣a 等b 或事务d 孛舆有置信度c 。这是 条件概率p ( ba ) 。即是：关联规则飙有支持度s 和置信度c 这两个重要的润值： s u p p o r t ( a 肆b ) = p ( a u b ) ，即a 瓤珏这两个项榘在事务集d 中周时出现的概 率； c o n f i d e n c e ( a = ，b ) - - p ( bia ) ，即猩出现项集a 的事务集d 中。项集b 谯同时 出现的概率。 硕士学位论文 同时满足用户给定的最小支持度阈值( m i n 和最小置信度阈值_ s u p ) ( r a i n _ c o n f ) 的规则称为强规则。 项的集合称为项集( i t e m s e t ) 。包含k 个项的项集称为t 项集。项集的出现频 率是包含项集得事务数。如果项集的出现频率大于或等于m i ns u p 与d 中事务总 数的乘积，则项集满足最少支持度m i ns u p ，称它为频繁项集( f r e q u e n ti t e m s c t ) 。 频繁k 项集的集合通常记做k 。 关联规则”1 的挖掘就是找出强规则的过程，分两步进行： 1 找出所有的频繁项集。这些项集出现的频繁性至少和预定义的最小支持度 一样。 2 由频繁项集产生强关联规则。这些规则必须满足最小支持度和最小置信 度。 其中第一个问题是关键问题，也是决定关联规则挖掘算法性能的问题。 根据不同的标准，关联规则可以分成若干类型“1 ，如： l 、基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的 关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字 段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值 型关联规则中也可以包含种类变量。 例如：性别= “女”= 职业= “秘书”，是布尔型关联规则；性别= “女”= a v g ( 收 入) = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 2 、基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同 的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则；台式 机= s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 3 、基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而 在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联 规则是处理单个属性中的一些关系：多维关联规则是处理各个属性之间的某些关 系。 例如：啤酒= 尿布，这条规则只涉及到用户的购买的物品；性别= “女”= 职业 t 秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 2 3 2 国内外研究现状 目前，基因表达数据分析方法仍处于起步阶段，对基因表达数据的关联规则 挖掘多采用将基因表达数据转换成与市场分析模式相同的模式，通过传统关联规 基因表运载搭荚联蕊羹垂笼黼冀法疆究 j _ _ - - _ i ii ii - - _ _ - _ _ - _ - _ _ _ - - 则挖掘算法对其进行挖掘，有采用a p r i o r i 算法及其改进算法对其进行关联规则挖 糖”“1 ，有采鼹频繁模式增长( f p 增长) 算法及箕政进算法慰纂困表达数据进行 挖掘”3 “，苏下对基因袭这数据关联规剐挖掘算法进行详细攒述。 a p r i o r i 辣法是一种辙有影响的挖掘布尔关联飒则的算法”1 。a p r i o r i 算法分两 步完成，酋先找出所有的频集，这些颂集出现的频繁性至少和预定义的最小支持 瑾一转。然纛瘗频集产黧强关联囊戴，这些援鬟| j 妊矮漩是最拳支持凌襄鬏小胃羡 度。挖掘关联规则的总体性能由第一步决定，第二步相对容易实现。而生成所有 绷集。采用丁一种称作逡鼹援索的迭代方法，b 项祭用于探索( “1 ) 项集；首先， 找出频繁l - 矮集懿集会，褰会记作五l ；j 用于残频繁2 顼纂熬集合王2 l 互2 翅子找 奶，妇魏下去，壹到青菜个，篷使褥。为空，魏辩算法箨正。然而，这个方法要 求多次扫描w 能很大的燮翁数据库。即如果频集最多包含1 0 个项，那么就霈要扫 描交易数据嬲l o 遍，这靛娶报大的i 0 负载。可熊产生大量纳候选集，以及可能 鼹要重复摇撬数据痒，爨a p r i o r i 髯法鹣蘸大臻熹。嚣2 。3 是一令a p r i o r i 翡蒸髂翻 予，描述a p r i o r i 算法寻拽事务集n 巾的频繁项巢，其中最小支持度计数为2 。 d i r t o 壤l 翻蝈雕 鬟 t i t t j 2 l l , l j t 2 l l 媳h 1 3 臻口 - t 4i l i a j 4 十， ” 1 1 , 1 3 t i n 执姐 t 7h nt t j t 2 t 啦 ! 9 | l 嚣罄 c l 帮 1 1 1 2 一一h 臻j m b ； _ - 一 臻量 ：l t 鼻l 诗蠢 l l l 器 ， ；l 稳 ， l l j 4 l 。2 ， i i j ，l 2 t 现h ， l 琏秘 i 瑶芦 2 ； 1 3 d ： 啼 岛岛 妻触 l 瑗羹 秘t l i t j 梢 3 l i l 嚣b 吣 j ( n , t 鼍t j l 2 l ! l 瑚辩 ： “ 筏琏罄 2 支挎 堆囊j 羹计 i 一 ：曼点叫! 一j 琏嚣 l ， l l l 捌| li l l 刀i 2 l i 珊l ， l n 瓣l j ：l 鳓l2 1 1 3 1 4 ) 1 0 ： ：j ，ji 2 ， l 珥1 0 羹掩壤 囊羹 蠛 ( i i , 1 2 , d 3 t i l 。l 玉吣 ， 1 1 1 辽u l ： ( 1 l j ) , l j ) 聋 琏毡罄 i c c l 一熏一j e 巨霉一叠e 巨固 麓：塑i：! ! i j 登趁i! 誓! 兰蝥跫|：i 刚2 3a p r io r i 算法挖撼过程示豳 焉墨糌墨怒罂 瑟型 硕士学位论文 为了提高算法的效率，针对a p r i o r i 算法的两大缺点，通过引入各种优化措施， 许多专家已经提出了改进算法，以下对各种引入优化措施的改进算法分别进行介 绍。r a g r a w a l 提出了a p r i o r i t i d 。4 1 的基本思想，它根据一个事务不包含长度为k 的大项集，则必然不包含长度为抖1 的大项集这一原理，删除这些事务，减少用 于未来扫描的事务集的大小，提高算法的效率。p a r k 等人提出来的d h p 算法”“， 使用h a s h 技术有效地改进了备选集的产生过程，利用寻找频繁项集主要的计算是 在生成频繁2 项集2 t 上这个性质引入杂凑技术来改进产生频繁2 项集的方法，对 每个事务产生所有的2 项集，将它们散列到散列表结构的不同桶中，并增加对应 的桶计数，在散列表中对应的桶计数低于支持度阀值的2 项集不可能是频繁2 一项 集，因而当由候选项集中删除。这样可以大大压缩频繁2 项集。s a v a s e r e 等”明设 计了一个基于划分( p a r t i t i o n ) 的算法，这个算法先把数据库从逻辑上分成几个互不 相交的块，每次单独考虑一个分块并对它生成所有的局部频繁项集，然后把产生 的局部频繁项集合并，用来生成所有可能的频集，最后计算这些项集的支持度。 这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次， 而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。并且 上述算法是可以高度