（计算机应用技术专业论文）时序基因表达数据的建模分析及应用.pdf

摘要 捅要 随着d n a 芯片技术的广泛应用，基冈表达数据分析已成为生命科学的研究热点。d n a 微阵列技术是一种磅究细胞中基匿表达模式的冀# 常有效的技术。这种技术两临的主要挑 战是如何分析由此产生的大量基因表达数据。最近，一种新的基因表达数据时序基 因表达数据受到了越来越多的重视。时序基因表达数据根据细胞循环过程，在不同时间 点对各基因采集相关数据。目前，虽然已有多种算法可以对时序基因表达数据进行聚类 分析( 如k 均值聚类方法、层次聚类方法，基于统计模型的聚类方法等) ，但这些方法 通常把时序基因表达数据看作是普通的多维空间向量，数据中时间上的自关联信息完全 被忽视，不能有效影响到聚类的最终结果。 本文研究霉的是为了探索新的时序基因表达数据聚类算法，并提出了一组基于自回 归模型的动念聚类算法。文中网顾了当前主要的聚类分析技术以及评价聚类效果的评价 算法，简要介绍了时序基因表达数据。本论文重点是： ( 一) 建立了一种改进的基于自 回归模型和贝叶斯后验概率的动态聚类分析算法，阐述了应用该算法进行时序基因表达 数据聚类分析的原理和方法；( 二) 建立了一种基于自回归模型的模糊动态聚类分析算 法，阐述了应用该算法进行时窿基因表达数据聚类分析的原理和方法。针对原始动态聚 类分析中仅利用类条件概率密度( 也称似然度) 的问题，根据贝叶斯理论，提出了改进 的基于贝叶斯后验概率的聚类算法。同时结合模糊理论，提出了模糊动态聚类分析算法， 利用模糊隶属度来调节自回归模型的动态预测过程，克服了原始聚类算法中自回归模型 中自回归阶数p = 1 的局限性。本文最詹还利用网归技术对时序基因表达模型做了一些 探讨。论文采用m a t l a l 3 来编穰实现了文中提出的算法，选取了一些数据集来进行实验。 实验结果表明，本文提出的方法是有效的、可行的，并且与现有的一些聚类分析方法相 比，更为有效。 关键字：时序基因表达数据；自回归模型；贝叶斯理论；动态聚类；模糊聚类；自相关 性。 a b s t r a c t a b s tr a c t a l o n gw i t ht h er e s e a r c ha n de x t e n s i v ea p p l i c a t i o n so fd n ab i o c h i pt e c h n o l o g y , g e n e e x p r e s s i o nd a t aa n a l y s i sh a sb e c o m eah o t s p o ti nl i f es c i e n c ef i e l d a sw ek n o w , d n a m i c r o a r r a yt e c h n o l o g yi sav e r yp o w e r f u lt o o lt oe x p l o r et h em o d eo fg e n e se x p r e s s e di na c e l l t h em a i nc h a l l e n g ei sh o wt oa n a l y z et h er e s u l t i n gl a r g ea m o u n t so fg e n ee x p r e s s i o nd a t a r e c e n t l y , an e wk i n do fg e n ee x p r e s s i o nd a t ac a l l e dt i m ec o u r s eg e n ee x p r e s s i o nd a t ah a s r e c e i v e dal o to fa t t e n t i o n t i m ec o u r s eg e n ee x p r e s s i o nd a t ai sg o tb yr e c o r d i n ge x p r e s s i o n l e v e l sa td i f f e r e n tt i m ep o i n t sd u r i n gat e m p o r a lc e l l u l a rp r o c e s s i np r e s e n t ，t h e r eh a v eb e e n m a n yc l u s t e r i n ga l g o r i t h m st oa n a l y z et i m ec o u r s eg e n ee x p r e s s i o nd a t a ，s u c ha sk m e a n s c l u s t e r i n g ，h i e r a r c h i c a lc l u s t e r i n g ，s t a t i s t i c a lm o d e lb a s e dc l u s t e r i n ga n ds oo n b u ti nt h e s e m e t h o d s ，t i m ec o u r s eg e n ee x p r e s s i o nd a t ai ss e e na sas i m p l ev e c t o ri nm u l t i d i m e n s i o n s p a c ea n ds e l f - r e l a t e d i n f o r m a t i o nb e t w e e nd i f f e r e n tt i m ep o i n t si nt h ed a t ai s i g n o r e d c o m p l e t e l ya n d s oc a n n o ti n f l u e n c et h ef i n a lc l u s t e r i n gr e s u l te f f e c t i v e l y t h i sp a p e ra i m st oe x p l o r en o v e lt i m ec o u r s eg e n ee x p r e s s i o nd a t ac l u s t e r i n ga l g o r i t h m s a n dt w oa u t o r e g r e s s i v em o d e l ( a r ) b a s e dd y n a m i cc l u s t e r i n gm e t h o d sa r ep r o p o s e d i nt h i s p a p e r , s o m ec u r r e n tc l u s t e r i n gt e c h n i q u e sa n dv a l i d a t i o nm e t h o d sa r er e v i e w e da n dt i m e c o u r s eg e n ee x p r e s s i o nd a t ai sb r i e f l yi n t r o d u c e d t h ee m p h a s i so ft h i sp a p e ri sa sf o l l o w s ： f i r s t l y , a ni m p r o v e da r m o d e la n db a y e s i a np o s t e r i o rp r o b a b i l i t yb a s e dc l u s t e r i n gm e t h o di s p r o p o s e da n dt h ep r i n c i p l ea n dw a yo fh o w t ou s et h i sm e t h o df o rc l u s t e r i n gt i m ec o u r s eg e n e e x p r e s s i o nd a t aa r ee l a b o r a t e d s e c o n d l y , a na rm o d e lb a s e df u z z yd y n a m i cc l u s t e r i n g a l g o r i t h mi sp r o p o s e da n da l s ot h ep r i n c i p l ea n dw a y o fh o wt ou s et h i sm e t h o df o rc l u s t e r i n g a r ee l a b o r a t e d a i m i n ga tu t i l i z i n go n l yt h ec l a s s - c o n d i t i o n a lp r o b a b i l i t yd e n s i t yo rc a l l e d l i k e l i h o o di nt h eo r i g i n a ld y n a m i cc l u s t e r i n gm e t h o d ，a n i m p r o v e db a y e s i a np o s t e r i o r p r o b a b i l i t yb a s e dc l u s t e r i n ga l g o r i t h mi sp r o p o s e d a n db yi n t e g r a t i n gf u z z yt h e o r y , af u z z y d y n a m i cc l u s t e r i n ga l g o r i t h mi sp r o p o s e d ，w h i c ha d j u s t st h ef o r e c a s tp r o c e s so f a rm o d e lb y f u z z ym e m b e r s h i pd e g r e e sa n dc o n s e q u e n t l yo v e r c o m e st h el o c a l i z a t i o no ft h eo r d e rp = 1 o fa rm o d e li nt h eo r i g i n a ld y n a m i ca l g o r i t h m a tl a s t ，s o m ed i s c u s s i o no nt i m ec o u r s eg e n e e x p r e s s i o nm o d e li sp r e s e n t e db a s e do nr e g r e s s i o nt e c h n i q u e s a n dm a t l a bi su s e dt o i m p l e m e n ta l lt h ea l g o r i t h m sa n de x p e r i m e n tr e s u l t so ns o m ed a t a s e t sd e m o n s t r a t et h e e f f e c t i v e n e s s ，f e a s i b i l i t ya n da d v a n t a g eo ft h ep r o p o s e dm e t h o d so v e rs o m ep r e s e n tc l u s t e r i n g m e t h o d s k e yw o r d s ：t i m ec o u r s eg e n ee x p r e s s i o nd a t a ；a u t o r e g r e s s i v em o d e l ；b a y e s i a nt h e o r y ； d y n a m i cc l u s t e r i n g ；f u z z yc l u s t e r i n g ；s e l f - r e l a t i o n s h i p 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签 名： 羽皴 日 期：砌g i 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 导师签名： 蜜鱼匦 咖鑫i g 日 期：切i & 第一荦绪论 第一章绪论 1 1 研究背景 生物信息学足计算机和网络大发展，各不e o , l i 物数据库迅猛增长形势下如何组织数 据，并从数据中提取生物学新知谚 的学问。生物信息学是一门交叉学科，它包含了生物 信息的获取、处理、存储、分配、分析和解释等在内的所有方面，它综合运用数学、计 算机科学和生物学的各种工具，来阐明和理解大量数据所包含的生物学意义。生物信息 学把d n a 、氨基酸序列，以及其它相关数据信息作为分析对象，力求揭示蛋白质和r n a 基因的编码区以及基因组中非编码区的信息实质。 生物的基因组是指该生物所有遗传物质的综合。生物的遗传物质是一类称为脱氧核 糖核酸( d n a ) 的生物大分子，它山四种核苷酸串组接而成，通常用字符a 、t 、g 、c 代表。生物的遗传密码就是这4 个字符连接起来的线状长链。由于生物的遗传密码往往 很长，例如人类的遗传密码就含有3 2 亿个字符，其中包含了生物的结构和功能以及生 命活动过程的所有信息，却仅仅由4 个字符组成，既无语法，又无句法，每一段看上去 都是相似的，因此，如何解读出生物的遗传密码是个极大的难题。基因组研究最终是要 把生物学问题转化成对数字符号的处理问题。要解决这样的问题就必须发展新的分析理 论、方法、技术、工具，就必须依赖计算机的信息处理。图卜l 为生物分子信息处理的 一般流程。 图1 - 1 生物分子信息处理的一般流程 目前归入生物信息学领域的大致有以下几个方面： 1 各种生物数据库的建立和管理。尽管已有大量的公共数据库系统( 如g e n b a n k 等) 可供世界范围内的研究者使用，但这些公共数据库在内容或数据综合、检索途径上 不定能满足实际研究的需要。因而，针对生物信息学特定的研究与开发工作，必须建 立自己的数据库或数据获取界面。 2 数据库接口和检索工具的研制。越来越多的数据库检索工具已投入实际应用。 l 江南人学倾i ：学位论文 其中，序列相似性检索软件应用最为广泛。开发和使用这些检索工具时，必须明确检索 目的、数据结构、结果显示等要素，同时应考虑检索效率等问题。 3 序列分析。分子序列分析是生物信息学的核心方法，包括从序列对位排列到序 列同源分析和进化分析，到基冈组分析和蛋白质组分析等。 4 d n a ：枣片和微阵列的发展。基因芯片技术以其可以同时、快速、准确的分析大 量基因组信息的特点在诸多领域得到应用。在生命科学领域中，基因芯片为分子生物学、 生物医学等研究提供了强有力的手段。 5 统计模型。越来越多的统计模型已用于生物信息学研究。例如，隐马尔可夫模 型在基于识别和药物设计中具有重要的应用价值；最大似然模型已成为序列分析的一种 常规方法。 6 算法研究。从各种图谱的分析，大量序列片段的拼接组装，寻找基因和预测结 构与功能，到数据和研究结果的可视化，无不需要高效率的算法和程序。另外，生物学 中的特殊问题也保持了计算机算法的发展，如遗传算法和人工神经网络的建立与发展。 这些算法反过来又可应用于生物信息学的研究。 目前，随着基因组信息的爆炸性增长，迫切需要对海量信息进行处理，考察基因之 间在位置、结构和功能上的相互关系。 1 1 1 基因芯片概述 基因芯片( g e n ec h i p ) 是今年来生命科学与微电子等学科相互交叉而产生的一向新 技术，在序列分析、基因表达、基因组研究及基因诊断等领域显示出重要的理论和实际 应用价值。基因芯片是生物芯片( b i o c h i p ) 的一种，有多种叫法，如d n a 芯片( d n ac h i p ) 、 d n a 微阵列( d n a m i c r o a r r a y ) 等。基因芯片技术是随着人类基因组计划的发展应运而 生的，初衷是为了研究更快的测序方法。基因芯片作为一门新兴技术，已经在生物医学 的各个领域得到了广泛的应用1 1 】【2 】，下面将做简单的介绍。 1 ) 基因测序和突变检测。d n a 芯片用于测试是基于杂交测序法( s b h ) 发展而来 的，该技术增加了微阵列中寡核苷酸的有效长度，从而增加了测序的准确性，可以对较 长的d n a 片段进行测序，另外也使用于对不同基因组同源区序列的比较及含有内部重 复序列d n a 片段的序列分析。 2 ) 致病微生物的快速诊断。a n t h o n y 等人建立了一个在4 小时以内便可检测和识别 出致病微生物的方法，该方法的具体过程是使用随机引物通过p c r 法扩增细菌核糖体 d n a ，后通过检测系统来识别。 3 ) 癌症的诊断和治疗。目前基因芯片技术已应用于癌相关基因突变的快速检测。 由于可以利用基因芯片对某一细胞的基因表达情况进行一个全面的了解，所以基因芯片 技术还可以进一步应用于癌症的精确诊断及治疗，利用该技术可对包括白血病、淋巴瘤、 皮肤黑色素瘤及乳腺癌等多种癌症的齐细胞亚群进行区分，还可利用它对治疗方案进行 评估和新药药效评价，此外还能对癌症的发生、发展和转归进行预测。此外，可利用基 因芯片技术观察药物对肿瘤细胞基因表达谱的影响，评估药物对肿瘤治疗的可行性，从 2 第一章绪论 中筛选出抗肿瘤候选药物，对肿瘤约物的研究和丌发提供了极具价值的参考资料。基因 芯片技术在癌症基因研究及临床治疗领域的应用将不但使我们能更快速可靠的对癌症 进行诊断，对其发生的内在分子机理也将有更深入的了解，同时也将为癌症治疗药物的 开发提供极大帮助。 4 ) 寻找新基因。定量检测大量基冈表达水平在阐述基因功能、探索疾病原因及机 理、发现可能的诊断及治疗等方面是很有价值的。基因芯片技术在发现新基因及分析各 个基因在不同时空表达方面是一项十分有用的技术，它具有样品用量极少，自动化程度 高等优点，便于大量筛选新基因。目前，大量人类e s t s 给c d n a 微阵列提供了丰富的 资源，数据库中4 0 0 0 0 0 个e s t s 代表了所有人类基因，成千上万的e s t s 微阵列将为人 类基因表达研究提供强有力的分析工具。这将大大地加速人类基因组的功能分析。 5 ) 后基因组研究。基因测序完成后，未知基冈的功能研究是一个十分诱人的后基 因组研究课题。斯坦福大学的d a v i s 研究小组的研究提示d n a 芯片技术将来可能应用 于人类基因则测序完成后阐明丌放读码框架o r f 生物学功能的研究，可能会对深刻认 识生命现象及药物设计带来重大影响。 此外，基因芯片还广泛的应用于药物筛选、药物作用机制研究、毒理学研究、基因 扫描、环境化学毒物的筛选、耐药菌株和药敏检测等多个应用领域。人们相信，在新的 世纪中，基因芯片将会在人类疾病的基因诊断中发挥巨大的作用，为整个世界带来巨大 的社会效益。 1 1 2 微阵列基因表达数据 目前，微阵列基因表达数据主要为数值型并以矩阵的方式存储，设为a ，行为一个 样本在不同环境条件下或不同时间点的表达，列是同一环境或时问所有样本的表达情 况。矩阵彳中数据点的数目等于n g n c ，其中c 为设置的实验条件数或时间点数，n g 为基因的数目( 微阵列上的样本点数) 。矩阵元素a 。是第f 个基因在实验条件t 下的相对 表达值，通常需要对得到的原始数据进行对数变换，经过变换后，上调的基因具有j 下值， 而下调的为负值。基因表达数据通常是多维的，根据样本数据是在不同环境条件下或不 同时间点得到的表达，基因表达数据可分为非时序基于表达数据和时序基因表达数据。 本文主要研究时序基因表达数据。 1 1 3 基因表达数据的分析 基因表达数据可在三个复杂性依次递增的层次上进行分析 3 1 ：第一个层次是单基因 层次，主要研究单个基因在处理条件和对照条件下是否有不同的表达；第二个层次是多 基因层次，主要从共同功能、相互作用、共调控等角度研究基因族；在第三个层次上， 人们试图推测隐藏在我们观察到的基因表达模式背后的基因或蛋白质调控网络。目前对 基因表达数据的研究主要集中于第二层，而第三层则是更深一步的研究目标。本文隶属 于第二层次方面的研究。 目前基因表达数据分析有两个主要的研究方向【4 】【5 】： 3 江雨人学坝i ：学位论文 ( 1 ) 分析基因或样本之问的相互关系，使用的方法主要是聚类分析。多种基因在 基因组表达水平上具有或强或弱的表达相关性，同一种样本在不同的生理和病理状态下 也具有基因表达的相关性，这些就是基因和样本间聚类分析的基础。在基因聚类中，聚 类在一起的是在多个样本中具有相似表达模式的基因，这些基因表达上的相似性可能是 由于其中一个基因引起其它基因的表达改变，或者这些基因在生理或病理条件下受相似 的基凶调节。 ( 2 ) 检测基因在不同组织样本中的表达差异，例如证常细胞和肿瘤细胞之间的差 异，若以某些在不同样本中表达差异显著的基因作为模板，则可以通过判别分析来建立 有效的疾病诊断模型。在最近的一项研究中，基因表达模式用来区分两个经常被误诊的 淋巴瘤( 弥漫型大b 细胞和滤泡型b 细胞淋巴瘤) ，带有来自6 8 1 7 条人类基因的微阵 列显示，这两种肿瘤有3 0 个基因的表达差异很大。通过综合考虑，根据这3 0 个基因 的表达模式的差异能够对7 7 列肿瘤中的7 1 例( 9 1 ) 进行正确分类，与细胞学方法相 比有了很大程度的提耐6 】。 本文将主要针对时序基因表达数据进行聚类分析的研究，接下来的两个小节将简单 介绍该领域的研究现状以及本文研究的目标和意义。 1 2 研究现状 现在已有多种聚类方法被应用于时序基因表达数据的分析，其中包括了基于距离或 相关性的聚类方法( 如k 均值聚类 7 1 、层次聚类 a l 和自组织映射 o l 等) 和基于静态模型的 聚类方法【1 0 1 1 1 1 1 1 2 l 。在这些方法中，基冈表达样本被看成是高维空间中的向量。基于距离 或相关性的聚类算法根据基因表达样本之间的距离或相关性来聚类。基于静态模型的聚 类算法根据基因表达数据是否可以通过一个多元正态分布来产生将基因赋予其中一类。 使用前面提到的算法，任意的改变时间点的序列顺序不会改变聚类的结果，所以时序基 因表达数据中的关于动态特性的重要信息被忽视了。 最近，一些基于动态模型的聚类算法被用来进行时序基因表达数据的分析，其中动 态模型是为了利用时序基因表达数据中的动态特性。如r a m o n i 等f 1 3 】提出了一种基于模 型的算法来对基因表达的动态特性进行聚类。其中，基因表达的动态特性通过自回归 ( a r ) 1 4 1 模型来表示，同时使用一个收敛的过程来搜索最有可能的聚类簇。因为可能 的聚类簇的数目随着观察到的时序基因表达数据的数目成指数增长，一个基于距离的启 发式搜索过程被设计来使方法成为可行的。然而，他们的方法存在一些缺点。第一，收 敛过程的使用将导致极大的计算复杂度，而基于距离的启发式搜索过程的使用意味着算 法将具有所有基于距离的层次聚类算法的固有缺点；第二，由一个p 阶自回归模型描述 的基因表达样本需要一些自回归参数和p 的初始值来确定。并且，算法也没有处理用于 a r 模型的p 个初始值。 为了改进上述算法的缺点，w h 等【1 5 1 提出了一种新的基于动态a r 模型的时序基因 表达数据聚类算法，其中每个聚类用一个阶数为p 的a r 模型来表示，并且a r 模型的p 个初始值被假设为服从p 元j 下态分布。该算法根据两个基因是否由同一个a r 模型产生 4 第一苹绪论 来衡量它们的相似性。动态模型聚类的任务是将一个给定的时序基冈表达数据集划分为 一定数量的不相交的子集( 即聚类) ，以便同一聚类中的时间序列数据可以由同一个a r 模型产生并且所有样本由一个带白回归的混合模型产生的似然度最大。最后，根据某一 a r 模型产生一个特定的时序基因表达数据样本的概率来决定基因表达数据样本的聚类 归属。同样，一些问题在算法中依然存在。第一，算法的目标函数中使用的是类条件概 率密度( 或称似然性) ，在判断样本的聚类归属时也是使用的类条件概率密度，根据贝 叶斯理论【16 】，这并不足最优的；第二，根据实验的结果，往往在a r 模型中的p 取1 时， 算法可以取到最好的结果，作者并没有给出合理的结实。其实，这和人的直观想法是极 为不协调的，一般情况下，为了预测时间序列的后续值，当然是已知道的时间点上的值 越多越好，即p 的值应该较大的时候算法可以取得较好的效果。 自回归( a r ) 模型是一种比较适合于处理有关时间序列的线性模型，可以通过已 知时间点数据对后续时i r j 点数据进行预测，在一定程度上利用到了时间序列内部的相关 信息。但由于a r 模型足线性模型，而且受到时间间隔和模型中阶数据选择的限制，难 免在对后续时间点数据进行预测的过程中带入新的误差。由些可见，这种新方法中仍有 很多可能改进的余地，给我们今后的研究带来了很多启示。 总的束说，对基因表达数据的分析是一项颇具挑战性的研究工作，目前对时序基因 表达数据的聚类分析是一个热点。 1 3 研究i f l 标与意义 通过前面的介绍，我们可以认识到，生物信息学足一个生物学和信息学相交叉、结 合的新兴学科，其主要任务就是运用数学、计算机科学和生物学的各种工具，来阐明和 理解大量基因组研究所获得的数据中所包含的生物学意义。生物信息学是当今国际上正 在迅速发展的自然科学领域的重要课题之一，它不公在人类认识生物体和生物信息的起 源、遗传、发育与进货的本质中发挥了重要作用，而且将为人类疾病的诊断和治疗开辟 全新的途径。 随着生物信息学的迅猛发展，各种基因组序列信息及蛋白质结构信息等数据的规模 日趋增大，为了对这些大量而复杂的基因数据进行统计分析，以提供更多有价值的信息 作为医学研究、工农业生产的重要依据，于是对应用于聚类分析大量基因数据的聚类算 法提出了新的要求。 从科研的长远利益出发，为了能够缩短相关科研项目的周期，使科研成果能及时应 用于实践，要求提高聚类精确度，减少聚类分析所耗费的时间，充分利用到数据中的有 价值信息无疑是一条首选的途径。因此，提出适应于特殊类型基因数据( 如带有时问自 相关性的时序基因表达数据) 的新型聚类算法，充分利用时序基因表达数据中的自相关 信息，对今后的研究有着重要意义。 本论文的目标和重点是： 1 根据贝叶斯理论，利用后验概率，提出一中改进的基于自回归( a r ) 模型和后 验概率的动态聚类算法。 5 江南人学坝i ：学位论义 2 引入模糊学习理论，提出了一种基于自凹归( a r ) 模型的动态模糊聚类算法， 克服了w u 等【1 5 】算法中自回归阶数p = 1 的局限性。 1 4 论文结构 本文由5 章构成，各章的主要内容安排如下： 第l 章为绪论，分为4 个小节。第1 小节介绍了课题研究的背景；第2 小节简要介 绍了课题研究相关内容的研究现状；第3 小节则介绍课题研究的意义和目标；第4 小节 则介绍了本文的章节安排。 第2 章是聚类分析及评价算法。这一章主要内容是较全面的总结和回顾各种聚类算 法和聚类结果评价算法。第l 小节主要介绍了聚类分析算法的各种类别，较详细的阐述 了一些具有代表性的算法；第2 小节回顾了一些聚类分析结果评价算法；第3 小节给出 了一种基于循环自助法的聚类评价算法。 第3 章是时序皋因表达数据。这一章主要介绍了和时序基因表达数据相关的内容。 第l 节主要介绍了时间序列以及基因表达时i 日j 序列的主要特征。第2 小节介绍了基因表 达时问序列的相似性问题。第3 小节介绍了时序基因表达数据的聚类及存在的问题。 第4 章足改进的基于自回归( a r ) 模型的动态聚类算法。在这一章中重点介绍了 自回归( a r ) 模型，并提出了一种改进的基于自凹归( a r ) 模型的动态聚类算法。第 1 小节介绍了自回归( a r ) 模型及单个时间序列的似然表示；在第2 小节中，提出了基 于贝叶斯理论的改进动态聚类算法；第3 小节罩，主要通过人工数据集和真实世界数据 集一卜的实验来验证提出的算法的有效性；第4 小节罩给出了本章的小结。 第5 章是基于自回归( a r ) 模型的模糊动态聚类算法。这一章里介绍了以模糊学 习理论和自回归( a r ) 模型为基础的聚类算法。在第1 小节罩，简单介绍了模糊聚类 算法的思想；第2 小节中，简单介绍了自回归( a r ) 模型；第3 小节中将第l 、2 小节 相结合，提出了基于自回归( a r ) 模型的模糊动态聚类算法；第4 小节里，主要通过 人工数据集和真实世界数据集上的实验来验证提出的算法的有效性；最后在第5 小节里 对这一章内容进行了总结。 第6 章为时序基因表达模型选择的其它探索。这一章中主要介绍了一些对时序基因 表达模型的探索。在第1 小节里，介绍了如何利用( 核) 最小二乘回归模型来表示时序 基因表达曲线，并提出基于该思想的时序基因表达数据聚类算法；第2 小节中，主要通 过四个数据集来验证算法的效果；最后在第3 小节中对这一章进行了总结，对存在的问 题和解决方法进行了探讨。 第7 章为总结与展望。在这一章里，主要是对本文进行了回顾总结，并对以后的工 作和方向进行了展望。 6 第一二章聚类分析及评价算法 第二章聚类分析及评价算法 模式识别包括监督模式识别和非监督模式识别。监督模式识别是指已知某些样本的 分类情况，用这些已知样本对分类系统进行学习( 训练) ( 如图2 - 1 ) ，使得分类系统能 够对这些己知样本正确分类，然后用己学习好的分类系统对末知样本进行分类。非监督 识别不需要知道学习样本的先验知识，也不需要获取训练样本。 图2 - 1 聚类训练的一般过程 数据挖掘是通过仔细分析大量数据来揭示有意义的新的关系、趋势和模式的过程。 其出现于2 0 世纪8 0 年代后期，是数据库研究中的一个很有应用价值的新领域，是一门 交叉学科，融合了人工智能、数据库技术、模式识别、机器学习、统计学和数据可视化 等多个领域的理论和技术。由于数据挖掘是数据库中知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ，k d d ) 的核心步骤，发现了隐藏的模式，所以从模式处理角度，许多人认为 两者是等同的。 数据挖掘的任务就是发现隐藏在数据中的模式，从大量的、不完全的、有i 噪声的、 模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用的 信息和知识的过程。 数据挖掘技术最初就是面向应用的，尤其是在银行、电信、保险、交通、零售( 如 超级市场) 等商业领域。另外数据挖掘在生物学以及工业领域也有很广泛的应用。 聚类是数据挖掘过程中最重要的任务之一，可以发现数据集中潜在的对象簇( 组) ， 找到感兴趣的分布或模式。聚类问题主要关于如何将一个给定数据集划分为不同的聚 类，使得在同一聚类内的点之间的相似度较和不同聚类间点之间的相似度大1 1 8 】。 在聚类的过程中，不存在任何预先定义好的类，并且也没有示例表明数据集上的何 种关系是合法的，这就是聚类为什么被称做一种非监督过程的原因【1 9 】。从另外一方面说， 分类是将数据样本指派给预先定义好的一些类的过程【2 0 1 。聚类产生初始的类别，随后分 类过程可以根据这个初始类别将一个数据集分类【2 l 】。 7 南 i 学论女 圆 圈2 - 2 聚类过程的基本步骤” 根据特定的聚类准则，聚类的过程可能导致数据集不同的划分。图22 显示了聚类 的基本步骤，可以概括如下i ”】： 1 ) 特征选择。目标是选择适合于聚类的特征，同时保留尽可能多的和我1 的工作 有关的信息。因此，数据预处理町以被看做聚炎工作的一个必需步骤。 2 ) 聚类算法选择。这一步主要指，根据一个数据集，选择一种c 以得到好的聚类 结果的算法。一个聚类算法及其聚类过稃a r 以由相似性度吊和聚类准则米决定。 i ) 相似性度量。相似性度量是衡量两个数据点的相似度的准则。在大多数的情况 下，我们必须确定所有被选择的特征对于相似性度量的计算的贡献是相等的，没有特征 占居优势地位。 i i ) 聚类准则。在这一步，我们必须决定聚类准则，它可以通过一个代价函数或别 的一些规则来表示。我们必须强调我们得考虑希望出现在数据集中的聚类的类型。这样， 我们可以定义一个好的聚类准则，从而可以得到一个和数据集拟合得较好的划分。 3 ) 聚类结果评价。聚类结果的正确性可以通过适当的准则和技术来评价。因为聚 类算法定义的聚类未知，所以在许多的应用中，对数据集的最终划分需要进行评价担2 】。 4 ) 聚类结果解释。在许多情况下，为了得出正确的结论，应用领域的号家必须将 聚类结果和其它的实验证据及分析结合起来。 聚类分析已经在商业和科学的许多领域中成为一个重要的工具。这里我们简要概括 一下聚类应用的基本方向p q ： 1 ) 数据压缩。聚类分析可以在压缩数据中包含的信息方面有所作为。在某些时候， 可以利用的数据量非常大，这样数据的处理就显得非常必要。聚类可以用来将数据集划 分为一些感兴趣的聚类。然后，我们将定义的聚类的代表作为我们要处理的数据而不是 将数据集的每个数据都作为一个要处理的元素。这样可以达到数据压缩的目的。 2 ) 假设推广。在这里，聚类被用来推测和数据相关的一些假设。比如，我们可能 b 第二审聚类分析及计价算法 可以从一个零售数据库中发现以年龄和购买时i 瑚为基础的两个重要的客户群。然后，我 们可以推测一些数据的假设，如“年轻人多在夜间购物”，“老年人多在早晨购物”。 3 ) 假设检验。在这方面，聚类分析被用来检查某一建设的合理性。比如，我们考 虑“年轻人多在夜f u j 购物”这个假设。一种用来检验这个假设是否f 确的方法是对一组 具有代表性的商店数据进行聚类分析。假设每个商店用顾客的一些详细情况( 如年龄、 工作等) 和交易时问来表示，在应用聚类分析后，一个和“年轻人多在夜间购物”的聚 类形成了，这样这个假设就被聚类分析所证实。 4 ) 根据聚类进行预测。聚类分析被应用于数据集，得到的聚类可以由属于那些聚 类的模式的特征来描述和定义。然后，未知的模式可以根据它们和聚类的特征的相似性 被划分到特定的聚类中。这样可以提取出和我们数据相关的有用知识。比如，假设聚类 分析被应用于一个病人患同样疾病的数据集。根据他们对于特定药物的反应，结果就产 生了一定数量的病人的聚类。然后，对于一个新的病人，我们找到一个她可以被划分进 去的聚类，并以此为基础来决定该别人的治疗方法。 特别的，聚类分析的一些典型的应用领域为【2 3 】： 1 ) 商业。在商业中，聚类可以帮助商人们发现客户中的重要群体，并且根据他们 的购买模式刻画他们。 2 ) 生物学。在生物学中，聚类分析可以被用来定义类别、根据相似的功能分类基 因以及深入了解人类的继承结构。 3 ) 空问数据分析。大量的空| 日j 数据可以从卫星图片、医疗设备、地理信息管理系 统( g i s ) 、图像数据库等得到，而让用户去详细检查空间数据是昂贵和困难的。聚类分 析可以帮助自动化分析和理解空间数据的过程，可以用来分辨和提取存在于大型空间数 据库中有兴趣的特征和模式。 囊 4 ) 网络挖掘。在这方面，聚类分析被用来在大量的半结构化的网页文本中发现重 要的群组。这种网页文本的分类可以对信息探索产生帮助。 总的来况，聚类分析可以被看做别的工作( 如分类) 的预处理步骤，而接下来的分 类则将在检测到的聚类上进行。下面我们将简要介绍聚类算法的分类以及一些具有代表 性的算法。 2 1 聚类算法 现今已经存在多种聚类算法，它们可以根据下面的准则进行分类： 1 ) 输入到算法中的数据类型： 2 ) 聚类准则定义的数据点之间的相似度； 3 ) 聚类分析技术基于的理论和基础概念( 如模糊理论f 17 1 、统计等) 。 这样，根据定义聚类的方法，算法可以被广义的分为如下几类 2 4 1 ：基于划分的聚类、 基于层次的聚类、基于密度的聚类和基于网格的聚类。 基于划分的聚类试图直接将数据集分解为一组不相交的子集聚类。更特别的是，这 类方法试图通过优化某一准则函数来确定一个整数个数的划分。而这个准则函数可能着 9 垩塑叁兰堡土兰篁堡文 重于数据的局部或者全局结构，并且优化过程通常是一个迭代过程。 层次聚类则不停的将小的聚类合并到大的旱面或者将大的聚类拆分开来。算法的结 果是称为系统树图的树聚类，其中系统树图显示了聚类之间的联系。通过在一个期望的 水平上剪切树图，就可以得到数据样本的一个不相交的子集聚类。 基于密度的聚类的最重要的思想就是，根据概率条件将数据集中邻近的样本放到相 同的聚类中去。 基于网格的聚类主要被用来处理空间数据挖掘。其主要特征是将空间划城一个有限 数目的单元格，然后在其中进行所有的操作。 对于上述的每个种类都存很多的子类别和不同的算法。根据数据中变量的类型，聚 类算法可分为【2 2 】f 2 5 1 1 2 6 l ：基于统计的聚类和基二r 概念的聚类方法。 基于统计的聚类以统计分析为基础，使用相似性度量来划分样本，并且该类方法局 限于数值数据。 基于概念的聚类主要被用来处理分类数据，根据样本所包含的概念来聚类。 另一种划分聚类算法种类的准则是处理聚类重叠时的不确定样本的方式，包括了模 糊聚类、硬聚类以及基于k o h o n e n 网络的聚类等。 模糊聚类使用了模糊技术，考虑了一个样本可能同时隶属于多于一个的聚类。因为 这类算法考虑了实际数据中的不确定因素，所以其聚类机制和平常的生活经验较一致。 其巾最重要的模糊聚类算法非f c m 2 7 1 莫属。 硬聚类算法考虑非重叠的划分，这意味着一个数据点或者完全属于一类或者不是。 大多数的聚类算法都会产生硬聚类，囚此都可以被归类为硬聚类算法。 基于k o h o n e n 网络的聚类算法以神经网络的概念为基础。k o h o n e n 网络分为输入层 和输出层。输入层每个节点代表记录的一个属性，并与输出层的每个节点相连。每个联 结都被赋予了一定的权重，决定了对应输出节点的位置。因此，对于一个算法，通过适 当的改变权重，输出节点就形成了聚类。 总的来说，聚类算法都是基于一个评估给定划分质量的准则，它们通常需要输入一 些参数( 如聚类个数、聚类的密度等) 并试图为给定的参数定义最好的划分。因此，聚 类算法总是根据某些假设来定义一个数据集的划分而不是无条件的定义适合于数据集 的必需最佳划分。下面，我们将较详细的介绍一些上述聚类算法种类中具有代表性的算 法。 2 1 1 基于划分的聚类算法 这一类算法中，k 均值聚类算法【2 8 l ( 也称为c 均值聚类) 使用最为普遍。k 均值聚 类算法的目标函数可简单描述如下： 厶一= d 2 研，) ( 2 1 ) i = ix c i 在上面的目标函数中，m ，是聚类g 的中心，而a ( x ，m i ) 为样本点工和m ；之间的欧氏 距离，即a ( x ，m ，) = 0 x - m 。0 。这样，准则函数k 试图通过最小化数据样本点到该样 1 0 本点隶属聚类的中心的距离来划分数据集。特别的，这个算法可以以初始化c 个聚类中 心为丌始。然后，根据样本点到各聚类中心的距离，将样本点归类到距离最近的中心代 表的聚类中，再重新计算聚类中心。这个过程一直重复持续到各聚类的中心不在改变或 目标函数的值的变化小于一个特定的域值。可见，在迭代的过程中需要计算聚类中心m ；， 可以根据函数极值的求法通过下列过程求得： 令竺乏= 0 ，即e ( x 一，z ，) = 0 ，这样聚类g 的中心掰，的计算公式为， 聊，2 丢荟x 弦2 ， 其中n ，为聚类c ，中的数据样本点的个数。这样，k 均值聚类算法的一般过程可以概 括如下： 1 ) 初始划分。可以选择任意随机的划分或某些启发式的方法来得到初始的划分。 初始划分的选择对整个k 均值聚类算法的最终结果的影响是比较大的。一个恰当的初始 划分可以得到好的聚类结果，反之亦然。 2 ) 样本点重新归类。即将数据样本点重归类到和其距离最近的中心代表的聚类中。 3 ) 重新计算各聚类中心m ，。可以使用公式( 2 2 ) 计算各聚类中心。 4 ) 若符合算法终止的条件，迭代结束；否则转步骤2 继续迭代。这罩的算法终止 条件可以有多种，包括了前面提到的各聚类中心不在改变和目标函数的值的变化小于一 个特定的域值等。 k 均值聚类算法也存在一些缺点，比如前面提到的对初始划分比较敏感，可能会收 敛到局部最优值，还有由于划分是通过点到聚类中心的距离来确定的，这个准则假设了 数据的聚类是成团状的。所以，总的来说，k 均值成聚类算法对于成团状聚类的数据集 效果较好，但是对初始划分比较敏感，可能会收敛到局部最小值。 另一个属于此类的算法为p a m ( p a r t i t i o n i n g a r o u n dm e d o i d s ) 。p a m 的目标是为每 个聚类确定一个具有代表性的样本( 中心点) ，也就是找到聚类中处于最中心的样本点。 算法首先为每个聚类选择一个样本作为中心点。然后，每个没有被选择的样本点根据其 和所有样本中心点的相似度来归类。p a m 将中心点和其它的没有被选择的样本点进行 交换直到所有的样本点都取得中心点的资格。显然，p a m 算法的计算复杂度极高，因 为为了找到中心样本点，每个样本必须和整个数据集进行比较【2 9 1 。 c l a r a ( c l u s t e r i n gl a r g ea p p l i c a t i o n s ) 是p a m 算法在数据集的一个子集上的一个 实现。该算法从数据集中选取多个