（计算机应用技术专业论文）关联规则挖掘及其在基因表达数据中的应用.pdf

摘要 关联规则挖掘是数据挖掘领域中一个重要的研究问题，从1 9 9 3 年a g r a w a l 等人提出 至今，一直是学术界和产业界广泛关注的热点。随着生物数据的快速增长，生物信息学 已成为关联规则挖掘最富有机遇与挑战性的应用领域之一。 本文围绕关联规则挖掘问题，对关联规则挖掘算法及其并行化、以及关联规则挖掘 在基因表达数据中的应用展开了较全面和深入的研究，其主要内容和贡献包括： ( 1 ) 基于f p t r e e 的最大频繁模式挖掘算法研究 由于最大频繁模式搜索空间是项目数的指数级，所以修剪策略在最大频繁模式挖掘 算法中一直是一个非常重要的技术。本文在分析研究了前人提出的最大频繁模式挖掘算 法f p m a x * 基础上，使用本文提出的完全子集修剪和起始项目集修剪策略，提出了进一 步优化的改进算法f p m a x * * 。实例分析表明，这两项修剪技术可进一步减少计算开销， 提高原f p m a x * 算法的性能。 ( 2 ) 基于f p t r e e 的频繁闭合模式挖掘并行算法研究 由于在频繁闭合模式挖掘过程中，除了判断模式的频繁性外，还必须判断模式的闭 合性，所以，频繁闭合模式挖掘的并行化相比频繁模式挖掘的并行化难度更大。本文在 研究了共享存储结构和分布式存储结构下的频繁模式挖掘与最大频繁模式挖掘并行算法 的基础上，明确提出了共享存储结构下的频繁闭合模式挖掘并行算法s l f p 和s p f p 算 法，以及分布式存储结构下的频繁闭合模式挖掘并行算法d l f p 和d p f p 算法。理论分 析表明，s l f p 算法与d p f p 算法具有处理器之间同步较少，并行度更高，i o 与通信 开销较小以及良好的负载平衡。 ( 3 ) 基于超链接结构的自底向上频繁闭合模式挖掘算法研究 针对已有面向基因表达数据集的频繁闭合模式挖掘算法多次扫描数据集转置表带来 巨大开销的缺陷，本文提出了基于超链接结构的频繁闭合模式挖掘算法h t c l o s e 。理论 分析表明，该算法的时间和空间性能比反复扫描转置表的算法有较大的提高；在真实数 据集上的实验结果表明，该算法普遍快于反复扫描转置表的算法，最高达1 个数量级以 匕。 关联规则挖掘及其在基因表达数据中的应用 耋望型茎垫娄奎耋堇圭耋丝篁圣窒圣垫茎 ( 4 ) 基于形式概念分析的自顶向下频繁闭合模式挖掘算法研究 针对已有面向基因表达数据集的自底向上频繁闭合模式算法无法充分修剪空间可能 遭遇计算开销过太的问题，本文提出了通过转换搜索空间自顶向下和直接自顶向下搜索 频繁闭合模式两种策略，并设计了相应的t p c l o s e 和t p + c l o s e 算法。理论上证明了这两 个算法的正确性；在真实数据集上的实验结果表日胃，一般情况下，它们具有良好的性能 和较好的可扩展性，比已有的自康向上频繁 司合模式挖掘算法最高快2 个数量级以上。 关键词：关联规则挖掘基因表达数据最大频繁模式频繁闭合模式并行算法 i r 装联规则挖掘段其在基因表选数据中的应用 a b s t r a c t a s s o c i a t i o nr u l e sm i n i n g ( a r m ) i sa ni m p o r t a n tp r o b l e mi nd a t am i n i n g s i n c et h e p r o b l e mw a si n t r o d u c e db ya g r a w a le ta 1 i n 19 9 3 ，i th a sa t t r a c t e dt r e m e n d o u si n t e r e s ta m o n g r e s e a r c h e r sa n dp r a c t i t i o n e r s w i t ht h eb i o l o g yd a t ag r o w t hr a p i d l y , b i o i n f o r m a t i c sp o s e da g r e a tc h a l l e n g ea n dc h a n c ef o ra r m t h i sd i s s e r t a t i o ne x t e n s i v e l ys t u d i e da l g o r i t h m sf o ra r m ，p a r a l l e la r ma n da r mi n g e n ee x p r e s s i o nd a t a t h em a i nc o n t e n t ，c o n t r i b u t i o na n di n n o v a t i o ni nt h ed i s s e r t a t i o na r e d e s c r i b e db e l o w ( 1 ) t h es t u d yo fa l g o r i t h m sf o rm i n i n gm a x i m a lf r e q u e n tp a t t e r n sb a s e do n f p t r e e d u et ot h es e a r c hs p a c ei s e x p o n e n t i a lo ft h en u m b e ro fi t e m s ，e f f i c i e n t l y p r u n i n gt e c h n i q u e sa r ev e r yi m p o r t a n tf o rm i n i n gm a x i m a lf r e q u e n tp a t t e r n b y i n v e s t i g a t i n gt h ef p m a x 木a l g o r i t h mf o rm i n i n gm a x i m a lf r e q u e n tp a t t e r nb a s e do n f p t r e e ，w ep r o p o s e da ni m p r o v e da l g o r i t h m ，f p m a x 木木f p m a x 木木u s e dt h ef u l l s u b s e tp r u n i n ga n dt h ef i r s ti t e m ss u b s e tp r u n i n gw h i c hw ep r e s e n t e d a ne x a m p l eo f f p m a x + + s h o w e dt h a tt h et w op r u n i n gt e c h n i q u e sc o u l dr e d u c e dt h ec o m p u t i n gc o s t a n di m p r o v e dt h ep e r f o r m a n c eo ff p m a x 奉 ( 2 ) t h es t u d yo fp a r a l l e la l g o r i t h m sf o rm i n i n gf r e q u e n tc l o s e dp a t t e r n sb a s e do n f p t r e e w h e nap a t t e r nw a sf r e q u e n tc l o s e d ，t h ep a t t e r nw a sn o to n l yf r e q u e n tb u ta l s oc l o s e d s o ， p a r a l l e lm i n i n gf o rf r e q u e n tc l o s e dp a t t e r n sw a sm o r ed i f f i c u l tt h a nf r e q u e n tp a t t e r n s a f t e r i n v e s t i g a t i n gt h ep a r a l l e la l g o r i t h m s f o rm i n i n gf r e q u e n tp a t t e m sa n dm a x i m a lf r e q u e n t p a t t e r n sb a s e do ns h a r e d - m e m o r ya n dd i s t r i b u t e dm e m o r ys y s t e m s ，w ep r e s e n t e dt w op a r a l l e l a l g o r i t h m ss l - f pa n ds p f pb a s e do ns h a r e d - m e m o r yf o rm i n i n gf r e q u e n tc l o s e dp a t t e r n s ， a n dt w op a r a l l e la l g o r i t h m sd l - f pa n dd p f pb a s e do nd i s t r i b u t e dm e m o r y t h ea n a l y s i si n t h e o r ys h o w e dt h a ts l - f pa n dd p f ps p e n tl e s si o ，d e m a n d e dl e s sc o m m u n i c a t i o n ，a c h i e v e d m a x i m u ma s y n c h r o n o u so p e r a t i o n sa n dh a dg o o dl o a db a l a n c i n g 关联规则挖掘及其在基因表达数据中的应用 i l i 耋里坠耋垫查查兰堡圭兰堡篁兰 薹塞塑矍 ( 3 ) t h es t u d yo fa l g o r i t h m sf o rm i n i n gf r e q u e n tc l o s e dp a t t e r n si ng e n ee x p r e s s i o n d a t a s e tb a s e do nh y p e r s t r u c t u r e f o rt h es a k eo fa v o i d i n gt h en u m e r o u sc o m p u t i n go v e r h e a dc a u s e db yp a s s i n gt h e t r a n s p o s e dt a b l eo fd a t a s e tm a n yt i m e s ，w ep r o p o s e dan e wa l g o r i t h mh t c l o s cf o rm i n i n g 矗e q u e n tc l o s e dp a t t e r n si ne x p r e s s i o nd a t a s e tb a s e d o nh y p e r s t r u c t u r e t h ea n a l y s i si nt h e o r y s h o w e dt h a th t c l o s eg r e a t l ye n h a n c e dp e r f o r m a n c ea g a i n s tt h ea l g o r i t h mp a s s e d t h e t r a n s p o s e dt a b l eo fd a t a s e tm a n yt i m e s s e v e r a le x p e r i m e n t so nr e a l - l i f eg e n ee x p r e s s i o n d a t a s e t ss h o w e dt h a th t c l o s ew a sf a s t e rt h a nt h el a t t e rb yu pt oo n eo r d e ro fm a g n i t u d e ( 4 ) t h es t u d yo fa l g o r i t h m sf o rm i n i n gf r e q u e n tc l o s e dp a t t e r n si l lg e n ee x p r e s s i o n d a t a s e tb a s e do nf o r m a lc o n c e p ta n a l y s i s t oa d d r e s st h ev a s tc o m p u t i n gc o s te n c o u n t e r e db yt h eb o t t o m - u ps e a r c hs t r a t e g yf o r m i n i n gf r e q u e n tc l o s e dp a t t e r n si ng e n ee x p r e s s i o nd a t a s e t ，w ep r o p o s e dt w os t r a t e g i e sb a s e d o i lt h ef o r m a lc o n c e p ta n a l y s i s o n es t r a t e g yw a st oc o n v e r tt h es e a r c hs p a c ef o rf r e q u e n t c l o s e dp a t t e r n si n t ot h es e a r c hs p a c ef o rf r e q u e n tc l o s e dt i d s e t s ，a n da n o t h e rs t r a t e g yw a st o s e a r c ht h ef r e q u e n tc l o s e dp a t t e r n sd i r e c t l yb yt o p * d o w n w ed e s i g n e dt p c l o s ea n dt p + c l o s e a l g o r i t h m sb a s e do nt h et w os t r a t e g i e s w ep r o v e dt h et w oa l g o r i t h m s c o r r e c ts e v e r a l e x p e r i m e n t so nr e a l 1 i f eg e n ee x p r e s s i o nd a t a s e t ss h o w e dt h a tt p c l o s e a n dt p + c l o s er e c e i v e d ag o o dp e r f o r m a n c ea n ds c a l a b i l i t y ，t h e yu s u a l l yo u t p e r f o r m e dt h ea l g o r i t h m sf o rm i n i n gt h e f r e q u e n tc l o s e dp a t t e r n si ng e n ee x p r e s s i o nd a t a s e tb a s e do nab o t t o m u ps e a r c hs t r a t e g yb y u pt ot w oo r d e r so fm a g n i t u d e k e y w o r d s ：a s s o c i a t i o n r u l e sm i n i n g ，g e n ee x p r e s s i o nd a t a ，m a x i m a lf r e q u e n tp a t t e r n ， f r e q u e n tc l o s e dp a t t e r n ，p a r a l ma l g o r i t h m i v关联规则挖掘及其在基因袭达数据中的应用 中圆科学技术大学学位论文相关声明 本入声羁所呈交靛学搜论文，是本人在导努指等下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 郄：学校有权按有关规定商国家有关部门或梳构送交论文的复e p 件和电子版，允诲论文被套阕和借嬲，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 恼，镪良 埘雩1 | ，雷 o 矽7 各- 舔 终考签名：盘盔二一 御零毒月耀e t 主曼丝量堡銮奎茎矍圭兰堡鎏兰篓! 兰丝篁 第1 章绪论 本幸概要作为本文后续章节研究内客的背景知识，奉章首先将简要介绍数据挖 掘、关联规则挖掘生物信息学，基因表达数据等相关概念和知识，然后给出整个论文 的主要研究内容接下来，提供一个简单的资源列表，供调研、学习和研究参考最后 给出全文的章节安排 1 1 数据挖掘 1 1 1 数据挖掘的概念 随着计算机和网络技术的飞速发展，人们产生和收集数据的能力快速提高，各行业 存储数据的爆炸性增长。已将人们淹没在数据的汪洋大海中但是，数据并不等于知识， 人们迫切需要新技术和自动工具将这些丰富的数据资源转换成信息和知识财富，从而帮 助人们科学地进行各种决策。正是在这种巨大的实际需求和数据库等相关技术的发展下， 数据挖掘技术才逐渐发展起来 数据挖掘出现于2 0 世纪8 0 年代末期，在9 0 年代有了突飞猛进的发展，是当前仍十 分活跃的前沿领域之一作为一个新兴的交叉学科，数据挖掘跨越了数据库技术、人工 智能、机器学习，神经网络、统计学，模式识别、高性能计算和数据可视化等多个学科 领域。 数据挖掘( 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 yi nd a t a b a s e s ，简称k d d ) ，有许多人将数据挖掘视为数据库中知识 发现的一个基本步骤。如图1 1 所示，知识发现过程主要由以下步骤组成l l - 3 】： ( 1 ) 数据选择( d a t as e l e c t i o n ) 。根据挖掘任务选择相关数据对象的描述特征或数据 仓库的维度； ( 2 ) 预处理( d a t ap r e p r o c e s s i n g ) ，包括数据清洗( d a t ac l e a n i n g ) 和数据转换( d a t a t r a n s f o r m a t i o n ) 等，数据清洗的作用是填补遗漏数据、消除异常数据和噪声数据等，数 据转换是将数据转换成适合数据挖掘的形式； ( 3 ) 数据挖掘算法选择( d a mm i n i n ga l g o r i t h ms e l e c t i o n ) ，根据挖掘任务选择合适的 挖掘算法，挖掘出模式或规律； ( 4 ) 模式评估( e v a l u a t i o np a t t e r n ) ，根据一定的评估标准从挖掘结果中筛选出有意义 的模式或规律； 关联规则挖掘及其在基因表达数据中的应用 中国科学技术大学j 撙士学位论文i i 数据挖掘 ( 5 ) 知识表示和解释( p r e s e t s f i o ua n dj m e r p r e t a t j o no f d i s c o v e r e dj ( n o w j e d g e ) ，利用 可视化和知识表达技术，向用户展示或解释所挖掘的相关知识。 由于人的需求和认识都是逐步加深的，所以知识发现过程是一个循环往复的交互过 程。 图1 1 知识发现过程 1 1 2 数据挖掘的任务 数据挖掘的主要任务包括：关联分析( a s s o c i a t i o na n a l y s i s ) 、分类与预测( c l a s s i f i c a t i o n a n dp r e d i c a t i o n ) 、聚类分析( c l u s t e r i n ga n a l y s i s ) 、异类分析( o u t l i e ra n a l y s i s ) ，演化分析 ( e v o l u t i o na n a l y s i s ) 等【i ，2 j 。 ( i ) 关联分析h 习 关联分析就是从给定的数据集中发现关联规m r ( a s s o c i a t i o nr u l e s ) ，这些规则展示了数 据集中属性值之间存在的某种关联关系。 关联分析广泛应用于购物篮分析、市场营销、医疗诊断、d n a 序列分析、股票分析、 设备故障监测和灾害天气预测等领域 ( 2 ) 分类与预测1 6 - q 分类( c i 髂s i 石c a t i o n ) 就是找出一组能够描述数据集台典型特征的分类模型( 或函数) ， 以便能够识别未知数据的类别( c l a s s ) 分类通常用于预测数据对象的归属类别( 有限离散值) ，当预测的不是类别而是某些 空缺或不知道的数据值( 连续数值) 时，则通常称之为预测( p r e d i c t i o n ) 分类与预测广泛应用于信用评估、医疗诊断、性能预测和市场营销等领域。 ( 3 ) 聚类分析i s , 9 1 2关联规则挖掘及其在基因表达数据中的应用 中国科学技术大学博上学位论文第l 童绪论 聚类分析就是根据“最大化类内的相似性、最小化类问的相似性”的原则将数据对 象划分为若干组( g r o u p s ) 或簇( c l u s t e r s ) 。在一个簇中的对象具有很高的相似性，不同簇之 间的对象相似性较小 聚类分析与分类分析明显的不同之处在于，分类属于有教师监督学习方法，它建立 分类预测模型使用的数据是已知类别归属( c l a s s 1 a b e l e dd a 啪。而聚类分析属于无教师监 督学习方法，所分析处理的数据事先并不存在类别归属 聚类分析是一种重要的人类行为，在人们的日常生活中常使用聚类方法将不同的事 物加以区别，如花、鸟、鱼、虫等。聚类分析已被广泛应用到许多领域，包括模式识别， 数据分析，图像处理和市场分析等 ( 4 ) 异类分析1 o 】 数据库中可能包含一些数据对象，它们与大多数数据对象构成的规律( 模型) 不一致。 这些数据对象就被称为异类( o u t l i e r ) 大部分数据挖掘方法都将异类视为噪声或异常而丢 弃。然而，在一些应用场合( 如欺诈行为检测) ，异常的事件可能比正常发生的更有趣。 对异类数据的分析处理就称为异类挖掘( o u t l i e rm i n i n g ) 异类挖掘用途很广，对于欺诈行为检测、市场营销定制和医疗分析等是非常有用的。 ( 5 ) 演化分析1 2 j 演化分析就是对随时问变化的数据对象的变化规律和趋势进行建模描述。建模方法 包括：概念描述、关联分析、分类分析，时间相关数据( t i m e r e l a t e d ) 分析等，其中时间 相关数据分析又包括时序数据( t i m e - s e r i e s ) 分析、序歹i j ( s e q u e n c e ) 或周期( p e r i o d i c ) 模式挖 掘、以及相似性搜索( s i m i l a r i t ys e a r c h ) 等。 演化分析在股票交易、商务贸易、生产过程监控以及电子商务等领域郡有广泛的应 用。 1 2 关联规则挖掘 1 2 1 关联规则挖掘问题 关联规则挖掘问题源于对购物篮数据的分析，1 9 9 3 年由r a g r a w a l 等人提出1 4 1 。人 们在分析零售店顾客购买的商品数据时发现，在顾客的购物篮中，有些商品经常被顾客 一起购买，例如，“8 0 的顾客在购买面包和黄油的同时也会购买牛奶”，“6 0 的顾客在 购买计算机的同时也会购买打印机”等等。如果商家通过分析顾客的购物习惯，找出顾 客购买商品之间的关联关系，那么商家就可以根据这种关系来指导进货，安排货架和制 定有针对性的营销策略等，从而扩大销售量。 如果将商场的所有销售商品看作是一个集合，每个商品看作是一个布尔型变量，所 有交易看作是一个交易数据库，那么顾客的购物模式就可用一条关联规则( a s s o c i a t i o n r u l e ) 来描述，例如：“6 0 的顾客在购买计算机的同时也会购买打印机”，用关联规则可 关联规则挖掘及其在基因表达数据中的应用 中国科学技术大学博士学位论文 2 关联规则挖掘 描述成： 购买c l 计算机) 等购买( z ，打印机) s u p p o r t = 1 0 ，c o n f i d e n c e = 6 0 这里，“购买( x ，计算机) ”称为关联规则的前件( a n t e c e d e n t ) ，“购买c l 打印机) ” 称为关联规则的后件( c o n s e q u e n t ) ，“s u p p o r t = l o ”是规则的支持度( s u p p o r t ) ， “c o n f i d e n c e = 6 0 ”是规则的可信度( c o n f i d e n c e ) 。支持度和可信度是两个反映规则有 趣度的度量，支持度描述了一条关联规则在交易数据库中成立的支持程度，反应的是规 则的频度( f r e q o e n c ”。例如，s u p p o r t = l o 表示在交易数据库中，有1 0 的交易是同时购 买了计算机和打印机可信度描述了一条关联规则在交易数据库中成立的可信程度，反 映的是规则的强度( s t r e n g t h ) 。例如，c o n f i d e n c e = 6 0 表示在购买计算机的交易中，有6 0 的交易也同时购买了打印机。 通常。并不是所有的关联规则都是用户感兴趣的，只有那些满足一定支持度阈值 ( s u p p o r tt h r e s h o l d ) 和可信度阙值( c o n f i d e n c et h r e s h o l d ) 的关联规则才认为是有趣的，这些 规则也称为强关联规则( s t r o n ga s s o c i a t i o nr u l e ) ，支持度阈值和可信度阈值可由专家或 用户来设置。 关联规则挖掘问题可描述为从给定的数据集中。找出所有满足最小支持度阅值 和最小可信度阈值的关联规则。 ( 1 ) ( 完全) 频繁模式挖掘 a g r a w a l 等人将关联规则挖掘问题分解为两个子问题f 4 1 ：( i ) 在数据集中找出所有 满足晟小支持度阚值( m i n i m a ls u p p o r t t h r e s h o l d ) 的模式，即频繁项目集( f r e q u e n t i t e m s e t ) 或频繁模式( f r e q u e n tp a t t e r n ) 挖掘；( i i ) 从所有频繁模式产生满足最小可信度阏值 ( m i n i m a lc o n f i d e n c e t h r e s h o l d ) 的关联规则。由于求解第1 个子问题的搜索空间是数据 集项目( 属性) 个数的指数级( 例如，当项目个数为n 时，可能有2 - 1 个频繁模式) ，而一 旦找出所有频繁模式及其支持度，求解第2 个子问题就变得较直接，因此，大部分研究 都集中在设计高效的频繁模式挖掘算法上【5 ”。1 然而，频繁模式( c o m p l e t ef r e q u e n t i t e m s e t s ) 的数量往往是巨大的，例如，一个长度为1 0 0 的频繁模式( a l ，a 2 ，a 1 0 0 ，包含 2 t 0 01 个频繁子集。所以，当频繁模式较长时，不管采用什么算法，遍历所有频繁模式 的计算代价都是非常高昂的。 ( 2 ) 最大频繁模式和频繁闭合模式挖掘 近年来，研究人员提出两种新颖的挖掘策略：挖掘最大频繁模式( m a x i m a lf r e q u e n t d a t t e r u ) 1 2 町或频繁闭合模式( f r e q u e n t c l o s e d p a t t e m ) f “。如果一个模式是频繁的，那么 其所有子集也是频繁的【”，因此只要找出所有最大的频繁模式，所有频繁子集便可由 此求出。最大频繁模式挖掘策略正是基于这样的思想，用挖掘所有最大频繁模式来代替 挖掘全部的频繁模式。显然，这样可以大大减少计算的代价。不过，一个频繁模式的支 持度与其子集的支持度可能是不同的，当由最大频繁模式集合求出全部频繁模式时，还 必需扫描数据集一次才能得到所有频繁模式的支持度 4 关联规剐挖掘及其在基因表达数据中的应用 中国科学技术大学博士学位论文第1 苹绪论 如果一个频繁模式不存在任何与其有相同支持度的超集，那么就称这种模式为频繁 闭合模式。由这样的频繁闭合模式，可以直接求出与它有相同支持度的子集，无需再扫 描数据集。因而，频繁闭合模式集合可看成是频繁模式集合的压缩形式频繁闭合模式 挖掘策略正是利用这一性质，用挖掘所有频繁闭合模式代替挖掘所有频繁模式。这样也 可以减少许多计算开销通常。一个数据集中，频繁闭合模式的个数比频繁模式的个数 要少许多。而最大频繁模式的个数比频繁闭合模式的个数又少几个数量级 尽管如此，最大频繁模式和频繁闭合模式挖掘算法的搜索空间仍然是项目个数的指 数级，随着数据集的大小和规模的增加，这些算法将可能面临着性能危机所以，提高 算法的性能，设计高效的最大频繁模式挖掘算法和频繁闭合模式挖掘算法仍然是数据挖 掘领域中一个非常具有挑战性的课题。 1 2 2 关联规则挖掘的延伸与扩展 自从关联规则挖掘问题被提出，就受到了学术界和产业界的广泛关注m2 6 。”，不 但对关联规则挖掘问题进行了大量研究，而且根据实际需要，在关联规则挖掘问题基础 上还延伸扩展出许多新的问题。以下列出了一些主要的扩展问题： ( 1 ) 量化关联规则挖掘阢”1 最初提出的关联规则只考虑值是布尔型的项目或属性之问的关联，即只考虑每个项 目在每个事务( 记录) 中是出现还是不出现。在实际当中，除了这种描述布尔型项目或属 性之间关联的布尔型关联规则( b o o l e a na s s o c i a t i o nr u l e ) 外，还需要能描述量化的项目或 属性之阃关联的规则，这种就称为量化关联规贝i | ( q u a n t i t a t i v ea s s o c i a t i o nr u l e ) ( 2 ) 多层次关联规则挖掘m 3 习 若一个关联规则的内容仅涉及单一层次的概念，则称为单层次关联规则( s i n g l e - l e v e l a s s o c i a t i o nr u l e ) 。若一个规则内容涉及多个不同抽象层次的概念，则构成多层次关联规 贝l j ( m u l t i p l e l e v e la s s o c i a t i o nr u l e ) 一般不特别说明时是指单层次关联规则。 ( 3 ) 多维关联规则挖掘1 3 6 1 如果关联规则中的项目或属性只涉及一个维( 谓词) ，则称为单维关联规则 ( 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 ) 如果规则涉及两个或两个以上的维数，则称为多维 关联规则( 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 nr u l e ) 在关联规则挖掘中，一般不特别说明时只 考虑单维情况。 ( 4 ) 带约束的关联规则挖掘 3 7 - 4 2 j 正如前面所述，并不是所有关联规则都是用户感兴趣的，所以，在关联规则挖掘中， 加入了支持度和可信度两个兴趣度约束( c o n s t r a i n t ) 尽管如此，所挖掘的关联规则可能 数量非常巨大，用户很难从中发现真正感兴趣的规则。因此，用户可能还需要提出其它 的兴趣度要求，或对规则的维数、层次，形式与个数等等提出约束，以聚焦到感兴趣的 规则上。加入这些约束的方式有两种：一种是在挖掘过程后使用约束对规则进行过滤。 这种方式不影响挖掘过程，可以满足不同用户的多种需求另一种方式是在挖掘过程中 关联规则挖掘及其在基因表达数据中的应用 5 中国科学技术大学博士学位论文1 2 关联规则挖掘 薯ir l|,i i i i _ _ _ _ 一 加入约束，以缩小规则搜索空间，加快搜索速度 ( 5 ) 模糊关联规则挖掘p 3 ，4 4 i 布尔型关联规则是描述二元值项目之间的关联关系，量化关联规则可以描述数值型 项目之间的关联关系。但是在实际生活中，当人们无法给出某个事物的精确数值时，往 往使用模糊术语。另外，人们对于有些知识的模糊表达理解起来可能感觉更加自然。模 糊关联规则( f u z z ya s s o c i a t i o nr u l e ) 在这种需求下便应运而生。 ( 6 ) 加权关联规则挖掘p 5 4 6 】 在关联规则中，每个项目都被看成是同等重要的，它们具有相同的权值。但是在实 际当中，每个项目所起的作用可能并不相同或用户对其的兴趣度不同。比如，零售业中， 有的商品利润可能比较高，而有的商品利润可能比较低，这时商家为了追求最大利润可 能需要给不同的商品赋予不同的权值这种能够描述带权项目之间关联关系的规则就称 为加权关联规则( w e i g h t e d a s s o c i a t i o nm 【e 1 ( 7 ) 保护隐私的关联规则挖掘【4 7 4 5 】 数据挖掘的特点是从大量数据中自动发现有价值的、未知的信息，但同时这也是数 据挖掘可能成为滥用工具的弱点保护个人隐私已成为当今全球最为关注的话题之一。 因此，研究既能挖掘项目之间的关联关系，又能保护个人隐私的关联规则挖掘( p r i v a c y p r e s e r v i n gm i n i n go f a s s o c i a t i o nr u l e s ) 是关联规则挖掘新的研究方向之一 ( s ) 关联规则的增量式更新i ”，5 0 1 在某些应用中，数据集的规模可能非常犬，所挖掘出的关联规则的数量可能也很庞 大数据库的更新( 增加数据或删除数据) 和参数的改变( 改变最小支持度或可信度) 都会使关联规则发现变化，如果每当这时都重新挖掘规则可能需要付出极高的代价。关 联规则的增量式更新( i n c r e m e n t a lu p d a t i n gt e c h n i q u e ) 便是研究随着时间的变化对发现的 关联规则进行维护和更新。 ( 9 ) 关联规则的并行与分布式挖掘 5 1 - s 3 l 尽管关联规则挖掘问题表述起来比较简单，但它是一个计算和输入，输出都非常密集 型的问题。随着数据集的规模变得越来越庞大，在这些大型数据集中执行基于单处理器 的关联规则串行挖掘算法将遭遇串行瓶颈问题，无法满足对大型数据集可扩放性和响应 时间的需求。因此，利用高性能的并行和分布式计算机强大的计算、存储和输入输出能 力是将关联规则挖掘问题从串行困境中解救出来的一个有效途径。 除了以上介绍的关联规则挖掘问题外，还有序列模式挖掘”、联机交互式关联规 则挖掘m ”1 、非冗余的关联规则挖掘【6 0 - “l 、以及在各种应用中的关联规则挖掘等。 1 2 3 关联规则挖掘的应用 关联规则挖掘具有广阔的应用前景，除了传统的购物篮分析“、市场营销【6 2 1 、股票 分析【6 3 l 等应用领域外，近年来，还在生物信息学【“。“，医疗诊断【8 “”、故障检测限。”、 灾害预测唧i 、商务管理【9 ，”1 、文本挖掘邮l 、信息检索m ”1 和体育比赛p 6 1 等多个领域获 6关联规则挖掘及其在基因袭达数据中的应用 中国科学技术大学博士学位论文第1 章绪论 得了广泛应用 随着近几年生物学实验技术的快速发展，人们积累的各种生物数据大幅度增加，除 了存储处理这些大量的生物数据外，还急需各种新的分析工具来帮助研究人员寻找发现 新的生物学知识和规律。因而，生物信息学已成为当前数据挖掘最具潜力也最具挑战性 的应用领域之一。关联规则挖掘在生物信息学中的应用日趋广泛，研究人员应用关联规 则挖掘技术去分析转录因子，或绑定位点之间的关系，从基因表达数据中寻找基因表达 的关联关系、或抽取保守的基因表达m o t i f , 研究蛋白质之间的相互作用网络、或探求蛋 白质序列m o t i f 之间的关系，以及为代谢路径和调控网络推导提供帮助和指导等 g r o w t ho fg e i l b a n kg r o w t ho f $ w i s s p r o t 舯 = ：5 0 = = 蚰 i = 加 暑 9 2 0 嚣 1 0 0 1 l 嘶l 螂l 卿l 9 9 7 枷32 0 0 6 ( a ) g c n b a n k 数据库 4 5 0 0 0 4 0 0 0 0 3 5 0 0 0 3 0 0 0 0 皇2 5 0 0 0 2 0 0 0 0 1 5 0 0 0 1 0 0 0 0 5 0 0 0 0 g r o w t ho fp d b ) s w i s s - p r o t 1 9 7 61 9 7 91 9 8 2 1 9 8 51 9 8 81 9 9 11 9 9 41 9 9 72 0 0 02 0 0 32 0 0 6 ( c ) p r o t e i nd a t ab a n k 数据库 翻1 2 三大数据库的数据量统计 1 3 生物信息学 传统的生物学( b i o l o g y ) 是一门实验科学，通过实验发现新的现象、新的生物学嫂 律，经过归纳，总结，提炼出新的生物学知识 9 7 1 随着计算机技术和生物科学技术的快 速发展，生物数据的积累迅速增加，图1 2 是根据分子生物学三大核心数据库公布的近 关联规则挖掘及其在基因表达数据中的应用 7 中国科学技术大学博士学位论文 13 生物信息学 t j - _ _ _ e | _ ；目_ _ _ ；_ _ _ 目t _ _ _ _ 一i _ _ _ _ _ _ _ _ _ _ ；_ _ _ e ；目= ；目i | j e 篇 二十多年的数据量绘制而成g e n b a n k 数据库是世界上最著名的核酸序列数据库之一， 收录了所有已知的公共核酸序列数据p ”s w i s s p r o t 数据库是一个著名的蛋白质序列数 据库。p d b ( p r o t e i nd a t ab a n k ) 数据库是个著名的生物大分子结构数据库【1 0 0 l 。从 图中三个数据库的数据量增长我们可以清楚地看到，近十年来的生物数据量几乎呈指数 增长，甚至超过了摩尔定律( 每1 8 个月翻一番) 。正是由于生物数据类型的不断增加和 数据量的不断膨胀，以及计算机在生物信息学中的广泛应用，从而促进了一门新的学科 生物信息学的诞生和发展。 要 苟 准 哥 = 焉 山 柑 ，0 蓦0 嚣3 詈= 嚣嚣尘墨器嚣嚣嚣暑= 嚣品譬嚣嚣等嚣嚣g 图1 3p u b m e d 中与生物信息学相关论文统计 作为一门由生物学、统计学和计算机科学等领域相互交叉形成的独立学科，生物信 息学始于2 0 世纪7 0 年代，在8 0 年代后期，随着一批生物信息服务机构( 如美国国家生 物技术信息中心n c b i 、欧洲分子生物学网络e m b n e t 等) 和生物信息数据库( 如蛋白 质数据库s w i s s - - p r o t 、核酸序列数据库d d b j 等) 的出现，生物信息学得到了快速 发展，特别是t 9 9 0 年被誉为生命科学的“阿波罗登月计划”一国际人类基因组计划的启 动，更加推动了生物信息学的迅猛发展。图1 3 p 1 描绘了1 9 7 3 年以来从生物医学文献数 据库p u b m e d 中搜集的与生物信息学相关论文的历年统计结果，从中不难看到生物信息 学大致的发展历程。 广义上说，生物信息学( b i o i n f o r m a t i c s ) 是指运用计算机技术收集、管理、分析和 处理生物分子数据，其目的是帮助生物学家揭示生物分子数据的内涵，获得深层次的生 物学知识和生物学规律，从而加深对生物世界的认识 生物信息学的研究范围十分广泛，涉及到生物学的方方面面，主要内容包括：生物 分子数据收集与管理( c o l l e c t i o na n dm a n a g e m e n t ) 、序列比较( c o m p a r i n gs e q u e n c e s ) 、 基因组信息分析( a n a l y z i n gg e n o m ei n f o r m a t i o n ) 、进化树构建( c o n s t r u c t i n ge v o l u t i o n a r y t r e e s ) 、蛋白质结构与功能预测( d e t e r m i n i n g p r o t e i ns t r u c t u r e sa n d f u n c t i o n ) 、基因表达数 据分析与处理( a n a l y z i n gg