（计算机科学与技术专业论文）聚类分析研究及其在生物数据分析中的应用.pdf

硕士学位论文 摘要 生物信息学是一门交叉科学，它包含了生物信息的获取、处理、存储、分发、 分析和解释等在内的所有方面，它综合运用数学、计算机科学和生物学的各种工 具，来阐明和理解大量数据所包含的生物学意义。这里重点讨论了聚类分析研究 及其生物数据分析中的应用。 聚类度量是特征提取的重要工具。本文首先概括了以往的聚类度量方法，并 提出了一种新的基于信息论的聚类度量，用来对聚类对象的信息分布进行相异性 分析。同时证明了新度量满足非负性、对称性、极值性、肯定性等。 其次，利用基于信息论的方法进行序列比较。本文提出了一种新的基于信息 论的序列比较方法。与传统的方法相比，此方法不需要序列比对，没有主观因素 干涉，不会破坏数据的原始状态。实验选取了2 0 种胎生哺乳动物的线粒体全基 因序列，分别使用基于信息论方法进行全基因序列比较和新方法进行片段基因序 列比较，再利用n e i g h b o r 法构建系统树。由实验结果可知，新方法用较少时 间构建的系统树完全不逊色于以往的方法，并且新方法有较好的健壮性。这为研 究分子序列的差异性提供了一种新方法。 最后，利用基于信息相异性的模糊聚类构建系统树。根据物种进化的模糊关 系和序列之间的信息分布的差异性，本文提出了基于信息相异性的模糊聚类的系 统树构建方法。将生物序列转化为信息集，利用基于信息论的新度量计算序列之 间的隶属度，结合模糊等价关系的聚类分析进行聚类，分析物种在不同时期的类 别划分情况，推断出物种的系统发生树。实验结果表明，这种方法构建的系统树 是值得可信的。 关键词：聚类分析；信息熵；模糊聚类：系统树 i i 聚类分析研究及j 在生物数据分析中的7 j i 矸1 a b s t r a c t b i o i n f b r m a t i c si sa n i n t e r d i s c i p l i n a r y s c i e n c e i t c o m p r i s e st h eo b t a i n i n g ， p r o c e s s i n g ，s t o r a g e ， d i s t r i b u t i o n ， a n a l y s i s a n di n t e r p r e t a t i o no fb i o i n f o r m a t i o n m a t h e m a t i c s ，c o m p u t e rs c i e n c ea n db i o l o g ya r eu s e dt oi l l u m i n a t ea n dc o m p r e h e n d t h eb i o l o g i c a lm e a n i n g so ft h el a r g ea m o u n to fd a t a t h ee n l p h a s e sh e r ea r et h e a p p l i c a t i o n so fc l u s t e ra n a l y s i si nb i o - m o l e c u l a rs e q u e n c es t u d y c l u s t e r i n gm e a s u r ei sa ni m p o r t a n tt o o lf o rf e a t u r ee x t r a c t i o n f i r s t l y ，t h i st h e s i s o u t l i n e st h em e a s u r e m e n tm e t h o do ft h ep r e v i o u sc l u s t e ra n dp r o p o s e san e w c l u s t e r i n gm e a s u r eb a s e do ni n f o r m a t i o nt h e o r y ，w h i c ha r eu s e dt oa n a l y s ed i s t a n c eo f t h ei n f o r m a t i o nd i s t r i b u t i o n n e wm e a s u r es a t i s f i e sn o n n e g a t i v e ，s y m m e t r y ，e x t r e m e ， a n dc e r t a i n l y ，a n ds oo n s e c o n d l y ， t h i st h e s i su s e si n f o r m a t i o n t h e o r y b a s e dm e t h o dt o s e q u e n c e c o m p a r i s o n i n t h i st h e s i s ，an e wi n f o r m a t i o nt h e o r yb a s e dm e t h o d so fs e q u e n c e c o m p a r i s o ni sp r o p o s e d c o m p a r e dw i t ht r a d i t i o n a lm e t h o d s ，t h i sm e t h o dd o e sn o t r e q u i r es e q u e n c ea l i g n m e n t ，t h e r ei sn oi n t e r f e r e n c eo fs u b j e c t i v ef a c t o r s ，t h ed a t a w o u l dn o tu n d e r m i n et h eo r ig i n a ls t a t e 2 0k i n d so fv i v i p a r o u sm a m m a l s m i t o c h o n d r i a lg e n e s e q u e n c e s a r es e l e c t e di nt h ee x p e r i m e n t ， w h i c ha r eu s e d i n f o r m a t i o nt h e o r yb a s e dm e t h o d st oc o m p a r et h ew h o l eg e n o m es e q u e n c ea n dt h e n e wm e t h o dt oc o m p a r eg e n es e q u e n c ef r a g m e n t s ，a n dc o n s t r u c t e dp h y l o g e n e t i ct r e e b yn e i g h b o r i ta p p e a r sf r o mt h er e s u l t so ft h ec o m p a r i s o n ，t h en e wm e t h o dw i t h l e s st i m ec o n s t r u c t st h ep h y l o g e n e t i ct r e ew h i c hd o e sn o tl a gb e h i n dt h ep r e v i o u s m e t h o d ，a n dt h en e wm e t h o dh a sg o o dr o b u s t n e s s f i n a l l y ，t h i st h e s i su s e sf - u z z yc l u s t e r i n gb a s e do nd i s c r e p a n c yo ft h ei n f o r m a t i o n d i s t r i b u t i o nt ob u i l dp h y l o g e n e t i ct r e e b a s e df u z z yr e l a t i o n s h i po fe v o l u t i o na n d d i s c r e p a n c yo fi n f o r m a t i o nd i s t r i b u t i o n ，t h i st h e s i sp r e s e n t san e w m e t h o dt oc o n s t r u c t p h y l o g e n e t i ct r e e b i o l o g i c a ls e q u e n c e sa r et r a n s l a t e di n t o i n f o r m a t i o ns e t s ，n e w i n f o r m a t i o nt h e o r yb a s e dm e a s u r e sc a l c u l a t em e m b e r s h i pd e g r e eb e t w e e ns e q u e n c e s ， a n df u z z yc l u s t e ra n a l y s e sc l u s t e ro fs p e c i e sa td i f k r e n tt i m e s ，s oi tm a yb ei n f e r r e d p h y l o g e n e t i ch i s t o r yo fs p e c i e s t h ee x p e r i m e n t a lr e s u l ts h o w st h a tp h y l o g e n e t i ct r e e b u i l tb yt h i sm e t h o di sc r e d i b l e k e yw o r d s ：c l u s t e ra n a l y s i s ；i n f o r m a t i o ne n t r o p y ；f u z z yc l u s t e r i n g ；p h y l o g e n y i i i 硕i j 学位论文 插图索引 图4 1f e r u n g u l a t e s 、p r i m a t e s 、r o d e n t s 、o u t g r o u p 三种可能的进化关系3 2 图4 2l = 6 时由新度量计算的距离矩阵3 3 图4 3l = 6 时由k l 计算的距离矩阵3 3 图4 4l = 6 时由f d o d 计算的距离矩阵3 4 图4 5 新方法构造的树3 4 图4 6f d o d 构造的树3 4 图4 7k l 构造的树3 4 图4 8 新方法l = 3 的树3 5 图4 9 新方法l = 4 的树3 5 图4 1 0 新方法l = 5 的树3 5 图4 1 l 前半序列的树一3 5 图4 1 2 第2 3 段序列的树3 5 图4 1 3 第4 5 段序列的树3 5 图4 1 4 大多数学者支持的进化关系3 6 图5 1 动态聚类算法流程3 8 图5 2 动态聚类算法一4 l 图5 3 聚类算法流程图4 3 图5 4 模糊相似矩阵一4 4 图5 5 传递闭包矩阵4 4 图5 6 模糊聚类推断的系统树4 6 聚类分析研究及! e 在生物数据分析中的应用 附表索引 表3 1 均值相同的二值变量17 表3 2 一个包含许多二值属性的关系数据表示描述1 7 表4 12 0 种胎生哺乳动物分别在g e n b a n k 中的索取号3 2 表4 2 计算距离矩阵的运行时间3 4 表5 1 不同阈值的模糊聚类情况4 5 v i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：茄惠牛 日期：矽护产易月午日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 拍意七 旃攻 日期：2 弓年 日期： 0 7 年 d 月斗目 6 月中 日 硕十学位论文 第1 章绪论 1 1 选题背景和意义 随着生物学数据库规模的大量增长，人们越来越多的利用计算机程序自动进 行分类处理。生物信息学给人类带来了巨大的希望，同时也为数据分析家带来机 遇和挑战。上百亿的数据涌入公共数据库，依靠实验的方法分析这些数据既费时 且昂贵。于是，找到有效快速的计算方法自动分析这些数据十分必要。庞大的生 物信息数据库对数据挖掘技术提出了许多颇具挑战性的问题，也提供了广阔的机 遇。聚类分析技术是数据挖掘中重要而且常用的技术，应用聚类技术分析生物数 据，可以帮助我们研究基因、蛋白质的性质功能，为探索生物的奥秘提供帮助。 聚类技术在生物信息学中的应用主要包括两个方面：蛋白质序列数据聚类和 基因表达数据的聚类。结构相似的蛋白质，他们的功能也相似，所以我们把具有 相似功能的蛋白质聚为一类，为生物学家研究蛋白质的功能提供了帮助。蛋白质 序列数据聚类最基本的方法是计算每两个蛋白质序列的比对相似度，然后使用层 次聚类方法来计算求得结果。因为生物功能的相关性通常伴随表达行为的相似性 ( 反之亦然) ，或所研究的过程可能设计多个基因或者蛋白质，因此有可能依据表 达谱相似程度( 即根据某种距离函数，一些表达矢量相互间足够接近) 找出特定的 亚群或簇。具有相似表达谱的基因被称为共表达基因。反之，观察到基因共表达 现象对推断这些基因的生物学功能有重要意义。例如，某一功能未知基因与功能 已知基因位于同一类中，对推断未知基因功能有重要指导作用。并且，共表达基 因很可能具有相似的调控机制。聚类分析即是将一组个体按其相互间的相似程度 归入几个子类，其基本原则是确定类群，使同一类内的各个体间差异最小，而不同 类间差异最大。聚类分析的首要目标是将表达谱相似的基因归纳成类，然后聚焦 于那些可能参与某些生物过程的基因群，对这些类进行生物学注释，同时获得新 的生物学知识。 聚类分析方法已被成功地应用于生命科学中各领域的研究，如有效地将不同 的基因序列集进行有效的划分、功能基因识别、推断出物种的系统发育树、对蛋 白质物理化学性质进行聚类可以预测其功能等，成为后基因组时代功能基因研究 的重要工具由于其应用的广泛性，出现了大量可用的聚类分析软件更加方便了其 推广和应用。应该看到，虽然聚类分析是目前生物信息中使用广泛，但它主要基 于统计学的理论而很少利用到生物领域的知识。这既使结果由于缺乏领域内知识 的约束而可能出现不合理性，同时又失去了利用领域内知识优化算法的好处。聚 聚类分析研究及j e 在生物数据中的应用 类分析算法的改进应该充分考虑到这一点，充分利用基因的生物学意义。可喜的 是越来越多人已经在往这方面发展了。另外，如何有效地对大数据集进行聚类分 析也值得特别关注【1 ，2 1 。 1 2 研究内容 1 ) 基于信息论的聚类度量研究。 聚类的过程，就是从大量、不完全、有噪声、模糊、随机的数据中，提取隐 含在其中人们事先不知道的有价值的信息和知识的过程。而这一过程正好与通信 传输过程类似，如果将数据源看作是信源，将聚类的结果看作是信宿，则聚类的 过程可以看作是信宿接受信源发出的信息的过程。在这一过程中，对先验不确定 性的消除直接影响到聚类的质量。由于聚类的过程与通信传输过程的相似性，信 息论方法也可应用于聚类分析。 本文将对基于信息论的聚类度量进行研究，提出了一种新的基于信息论的聚 类度量。度量是衡量聚类对象之间相异性或相似性的尺度。它要对聚类对象属性 之间的差异性进行量的分析，从中挖掘它们的潜在信息。度量是聚类最关键的工 具，是聚类质量的决定因素。基于信息论的聚类度量是对聚类对象的信息分布进 行相异性分析。 2 ) 基于信息论度量的生物序列比较。 生物序列的比较一直是计算分子生物学的重大课题。过去二十年间出现许多 用于比较生物序列的计算和统计法。传统的方法计算序列之间距离需要序列比对， 当人们要用更大的物种信息集( 比如全基因组序列) ，多序列比对就困难了。因为 全基因组序列的碱基数目往往达到几百万甚至是几十亿b p 的量级，并且基因重组 现象广泛存在于不同物种的全基因组序列中，使用者就需要设定参数、罚分、插 入空位，因而引入了主观因素，破坏数据的原始状态，导致计算结果因人而异。 本文将应用基于信息论的聚类度量对生物序列进行比较，这是种不需要序 列比对的序列比较方法，不需要任何的主观因素的介入，不会破坏数据的原始状 态，完全是基于统计学和信息论的方法。此方法主要是通过对序列信息的统计， 把序列转化为信息集，然后利用基于信息论的聚类度量计算序列之间的信息相异 性，从而可推测物种之间的进化关系。 3 ) 基于信息相异性的模糊聚类构建系统树。 在传统的聚类分析中，类别之间是清晰的，分类集合中的任意两个元素要么 等价，要么不等。但在很多情况下，事物的属性不是离散的，或者不是明确的， 而是连续的、模糊的，很多事物并不是绝对的属于这一类或者那一类。这样，对 于这种界限不分明的事物，仅利用传统的聚类方法就难以解决问题了。z a d e h 提 出的模糊集理论为解决这种问题提供了有力的分析工具，将模糊理论运用到聚类 2 硕：l ：学位论文 分析技术中来，产生了模糊聚类技术。模糊聚类是一种软划分，不像普通聚类方 法那样将每个数据样本分为一类，而是采取模糊分割的方法，任何给定的数据样 本不再仅仅属于一个类别、和其他类别毫无关系，而是可属于不同的分类类别并 有不同的隶属程度。模糊聚类方法建立起了样本对于类别的不确定性的描述，能 更客观地反映出现实世界。 由于生物进化有双向选择性，所以物种的进化关系就是一种模糊的关系，这 样就可以利用模糊聚类方法对物种进行聚类，分析物种在不同时期的类别划分情 况，从而可以推断物种的系统发育史。本文将生物序列转化为信息集的情况下， 利用基于信息论的度量计算序列之间的隶属度，最后利用模糊聚类分析划分各个 物种在不同时期的分类情况。 1 3 本文的章节安排 全文主要包含五个部分，各部分内容安排如下： 第1 章绪论 主要内容包括：介绍课题相关背景与意义、本文主要研究内容。 第2 章聚类分析及其在生物信息中的应用 主要内容包括：聚类分析的概述，聚类分析在基因表达数据、蛋白质序列、 构建系统发生树的应用。 第3 章基于信息论的聚类度量研究 主要内容包括：聚类分析中的数据类型及度量、基于信息论的相似度量、提 出了一种新的基于信息理论度量法并证明其一些重要的属性。 第4 章基于信息论度量的生物序列比较 主要内容包括：传统的非比对度量方法介绍、新的基于信息论度量的生物序 列比较、新的和传统的基于信息论度量在生物序列比较实验。 第5 章基于信息相异性的系统发生树构建 主要内容包括：模糊聚类分析的原理、基于模糊等价关系的聚类分析、基于 信息相异性的模糊聚类构建系统树。 聚炎分析研究及其钥：生物数据巾的应用 第2 章聚类分析及其在生物信息中的应用 2 。1 引言 人类基因组计划和因特网的发展促进了生物信息学的诞生。生物信息学囊括 了核苷酸组成及序列分析、基因的识别、蛋白质空间结构预测及模拟、基因调控 元件分析、重复序列鉴定、物种相似性分析及同源关系比较、进化程度分析、药 物设计、基因芯片检测结果分析等各个研究领域，是以数学、信息学、计算机科 学为主要手段，以计算机硬件、软件和计算机网络为主要工具的一个新兴科学。 对生物数据的聚类和预测是生物信息学的两个重要任务。聚类分析是数据挖 掘研究领域中一个非常活跃的研究课题。与分类不同，聚类不依赖预先定义的类 和带标号的训练实例。聚类将数据对象分组成多个类或簇，在同一个簇中的对象 之间具有较高的相似度，而不同的簇中对象差别较大。距离是常用的度量相似度 的方式。 本章对聚类算法进行了综述，从聚类( 无监督聚类) 的角度在生物信息学的一 些热点研究方向进行了算法综述。研究对象的范围有基因表达数据、蛋白质序列、 系统发育树的聚类分析。 2 2 聚类分析 2 2 1 聚类分析的概念 “物以类聚，人以群分”，聚类是人类一项最基本的认识活动。通过适当聚类， 事物才能便于研究，事物的内部规律才可能为人类所了解掌握。 聚类是一个将数据集划分为若干组或若干类的过程，并使得同一个组内的数 据对象具有较高的相似度，而不同组之间的数据对象相似度却很小。相似或不相 似度是基于数据对象描述的取值来确定的。通常就是利用各对象间的距离来进行 描述。将一群具体的或抽象的对象，根据它们之间的相似程度，分为若干组，其 中相似的对象构成一组，这一过程就称为聚类过程。一个类，又称一个簇，就是 由彼此相似的一组对象所构成的集合。不同类中的对象通常是不相似的，在许多 应用中，一个类中所有对象常常被当作一个对象来进行处理或分析。 聚类分析是按照不同对象之间的差异，根据每个样本对象的各种特征，通过 无监督训练将样本按相似性分类，把相似性大的样本归为一类，并占据特征空间 的一个局部区域，每个局部区域的聚合中心又起着相应类型代表的作用。聚类分 析是一种典型的组合优化问题。通常用于将某些具有一定特征的各个个体进行分 类。聚类分析的数学模型如下： 4 硕上学位论文 己知模式样本集 x ) 有n 个样本和k 个模式分类 ，= 1 ，2 ，k ) ，每个样本 有d 个特征指标，由此得到一个样本矩阵x 如下： x = 工2 五2 x n 2 x i d x 2 d x i d 为了对它们进行分类，矩阵x 中，每一行为一个样本，。，置：，为第i 个样本的d 个特征指标，以每个模式样本到各自聚类中心的距离之和达到最小为 标准，其目标函数为： r = 皿n 忙一一 ( 1 2 ) 厶一一 ， 、 = l 爿蕊 = _ 置 ( 1 3 ) 8 1 f = l 其中k 为聚类数目，表示第j 类样本( s j ) 的均值向量，均= l ，表示 j - l 模式样本i 只能分配给一个聚类中心。其设置规则为：若模式样本i 分配第j 聚类 中心，则= l ，否则，虼= o 。 聚类分析是一种重要的人类行为。早在孩童时期，一个人就是通过不断完善 潜意识中的分类模式，来学会识别不同物体，如：猫和狗，动物和植物等。聚类 分析己被应用到许多领域，其中包括：模式识别、数据分析、图象处理和市场分 析等。通过聚类，人可以辨识出空旷和拥挤的区域，进而发现整个的分布模式， 以及数据属性之间所存在有价值的相关联系【”。 2 2 2 聚类分析的研究意义 数据聚类正在蓬勃发展，有贡献的领域包括数据挖掘、统计学、机器学习、 空间数据库技术、生物学，以及市场营销。由于数据库中收集了大量的数据，聚 类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题【4 1 。 在数据挖掘领域，研究工作集中在为大型数据库有效和实际的聚类分析寻找 适当的方法。活跃的研究主题集中在聚类方法可伸缩性、方法对聚类复杂形状和 类型的数据的有效性、高维聚类分析技术，以及针对大型数据库中混合数值和分 类数据的聚类方法。 聚类分析作为统计学的一个分支，已被广泛地研究了多年，主要集中在基于 距离的聚类分析。例如：基于k 均值、k m e t h o d ( k 中心点) 【5 1 和其他一些方法的 聚类分析工具已经被加入到许多统计分析软件包或系统中，例如s 。p l u s ，s p s s ， 聚类分析研究及其和：生物数据中的应用 以及s a s 。在机器学习领域，聚类是无指导学习的一个例子。与分类不同，聚类 和无指导学习不依赖预先定义的类和带类标号的训练实例。由于这个原因，聚类 是观察式学习，而不是示例式学习。在概念聚类中，一组对象只有当它们可以被 一个概念描述时才形成一个簇，这不同于基于几何距离度量相似度的传统聚类。 在已有的应用中，随着涉及领域和问题的深入，对不同空间分布数据的研究 也己十分广泛，如何应用到具体的领域中并带来良好的效果，成为现实不可忽视 的问题。因而，基于理论的研究成果，在不同领域的实施、改进和创新也在进行 当中。 2 2 3 聚类分析的步骤 一般来说，聚类分析主要分成以下三个步骤：特征提取、聚类算法选择、参 数设置i 6 | 。 1 ) 特征提取。对于聚类分析来说，我们主要是根据样本所展现出来的不同特 征，来对样本进行聚类分析计算。特征选取的是否合理，将会直接影响聚类的结 果。合理的特征选取应该使分类结果中同类样本聚类较小，异类样本距离较大， 如果我们一开始就选择了与聚类要求无关紧要的特征，即使我们后面的操作步骤 多么正确，也将会得到错误的聚类结果，正所谓“差之毫厘，谬以千里”。另一 方面，由于每个特征都有个自鲜明的个性和不同的衡量标准，所以每个特征的数 据具有不同的量纲和量纲单位，为了消除量纲和量纲单位不同所带来的不可公度 性，聚类之前首先应将特征指标做标准化处理。一般来说，必须把这些特征按某 种效用函数归一化到某一无量纲区间，目前效用函数通常采取 0 ，l 】区间法，采 用这种标准化后的数据一般是一个标准的样本矩阵x ，它是一个n 木d 矩阵，即n 个样本，每个样本含有d 维特征。矩阵中的元素均是介于 0 ，1 】之间的数据： x = 墨2 五2 咒： 其中o 玛l ( 1 4 ) 2 ) 聚类算法选择。根据不同的聚类需要，我们要选择不同的聚类算法。目前， 聚类分析算法多达一千多种，但很多算法仍不成熟、不完善，特别是对于聚类样 本较大的时候，很多算法的劣势就会明显的表现出来，比如算法时间、聚类效果 等。所以，选取何种聚类分析算法，将直接影响聚类的效果和结果。 3 ) 参数设置。由于我们对样本进行聚类一般都具有现实的意义，参数的选择 往往需要领域专家经验和领域知识，结合具体情况和应用领域决定参数的大小。 没有领域专家的参与，仅仅依靠算法本身，则不能得到令人满意的结果。领域专 家结合领域知识往往可以进一步分析数据，加深对样本的了解。 6 硕j j 学 t ：) = 论文 2 2 4 聚类分析算法 聚类分析算法的选择取决于数据类型、聚类目的和应用领域。由于聚类分析 是一种富有挑战性的研究领域，因此它的一些应用对聚类分析算法提出了很多特 殊的要求，主要有以下几点1 7 j ： 1 ) 可伸缩性。指算法除了能够处理小数据量之外，同样能够处理大数据量的 数据库对象，因此，这就要求算法的时间复杂度不能太高。 2 ) 处理不同类型数据的能力。指算法不仅能够处理数值型数据，同时也要能 够处理其他非数值型的数据如二元类型、序数类型、枚举类型等。 3 ) 能发现任意形状的聚类。数据库中的聚类可能是任意形状的，因此要求算 法有能够发现任意形状的聚类的能力。 4 ) 参数的弱依赖性。很多聚类算法都要求用户输入一些参数，如：聚类数目、 支持度等。这些参数的值对聚类分析的结果影响很大。然而，另一方面，这些参 数又很难确定。一个好的算法应该对参数设置有一个比较好的解决办法。 5 ) 能够处理噪声数据。现实中的数据库大部分都包含有孤立点、空缺、未知 数据或者错误的数据，一个好的聚类分析算法应该尽量避免对这些数据的敏感性， 从而得到好的聚类结果。 6 ) 输入记录的顺序无关性。不管输入记录的顺序如何，一个好的算法应该能 够得到相同的结果。 7 ) 高维性。一个好的算法不仅对二维，三维数据能够得到较好的聚类结果， 在高维空间中聚类数据对象是非常有挑战性的，也应该能够得到较好的结果。 8 ) 基于约束的聚类。在算法的具体应用中往往都有很多额外条件约束，一个 好的聚类算法能够在考虑这些约束的情况下，依然有较好的表现。 9 ) 可解释性和可用性。聚类的结果最终都是要面向用户的，而用户希望聚类 结果是可解释的、可理解的、可用的。因此，聚类可能需要和特定的语义解释和 应用相联系。 聚类分析算法有很多，主要可以分成以下几大类：划分法、层次法、基于密 度的方法、基于网格的方法、基于模型的方法和模糊聚类算法等： 1 划分法 给定一个有n 个对象或元组的数据集，划分法将构造k 个分组，每一个分组 就代表一个聚类，k n 。而且k 个分组满足下列条件：( 1 ) 每个分组至少包含一个 数据纪录：( 2 ) 每个数据纪录属于且仅属于一个分组。对于给定的k ，算法首先给 出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每次改进之后 的分组方案都较前一次好。一个好的划分的一般标准是：同一分组中的对象尽可 能“接近或“相关 ，而不同分组中的对象尽可能“远离”或“无关 。使用 7 聚类分析研究及j e 在生物数据中的膨用 这个基本思想的算法主要有k 一均值算法( 也叫k m e a n s 算法) ，k 一中心点 c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e du p o nr a n d o m i z e ds e a r c h ) 算法等启 发式划分方法【5 1 。 2 层次法 层次的方法对给定数据对象集合进行层次的分解，直到某种条件满足为止。 根据层次的分解如何形成，层次的方法可以分为凝聚法和分裂法。凝聚法，也称 为自底向上的方法，一开始将每个对象作为一个单独的分组，在接下来的迭代中， 相继地合并相近的对象或分组，直到所有的分组合并为一个，或者达到一个终止 条件为止。分裂法，也称为自顶向下的方法，一开始将所有的对象置于一个分组 中，在迭代的每一步中，一个分组分裂为更小的组，直到最终每个对象在单独的 一个分组中，或者达到一个终止条件为止。代表算法有：b i r c h ( b a l a n c e di t e r a t i v e r e d u c i n g a n d c l u s t e r i n gu s i n gh i e r a r c h i e s ) 5j 、 c u r e ( c l u s t e r i n gu s i n g r e p f e s e n t a t i v e s ) 【9 1 、c h a m e l e o n 【10 1 、r o c k 【1 1 1 等。b i r c h 算法是自上而下的算 法，c u r e 算法是自下而上的算法。 3 基于密度的方法 绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状 的分组。基于密度的方法与其它方法的根本区别是：它不是基于各种各样的距离 的，而是基于密度的。这样就能克服基于距离的算法只能发现“球形”聚类的缺 点。这个方法的指导思想是，只要一个区域中的点的密度大过某个阀值，就把它 加到与之相近的聚类中去，继续进行聚类。d b s c a n ( d e n s i t y b a s e ds p a t i a l c l u s t e r i n go f a p p l i c a t i o n sw i t hn o i s e ) 【12 1 、o p t i c s 【13 1 、d e n c l u e 【1 4 】等算法。是其 中比较有代表性的算法。 4 基于网格的方法 基于网格的方法首先将数据空间划分成为有限个数目的单元，形成一个网格 结构，所有的处理都是以单个的单元为对象，在这个网格结构上进行。这样处理 的突出的优点就是处理速度很快，其处理时间与目标数据库中记录的个数无关的， 它只与量化空间中某一维的单元数目有关。代表算法有：s t i n g 【15 1 、c l i q u e 【16 1 、 w a v e c l u s t e r 【1 7 】等算法。 5 基于模型的方法 基于模型的方法给每一个聚类假定一个模型，然后去寻找能很好满足这个模 型的数据集。这个模型可能是数据点在空间中的密度分布函数或者其它，也可能 是基于标准的统计数字自动决定聚类的数目，考虑“噪声数据或者孤立点，从 而产生健壮的聚类方法。它潜在的假定就是：目标数据集是由一系列的概率分布 所决定的。基于模型的方法一般有两种尝试方向：统计的方案和神经网络的方案。 代表算法有：基于神经网络模型的聚类算法【”】。 8 硕士学位论文 6 模糊聚类算法 传统的聚类算法可以导出确定的类，也就是说，一个数据点或者属于一个类， 或者不属于一个类，而不存在重叠的情况。我们可以称这些聚类方法为“确定性 分类 。然而在客观世界中大量存在着界限并不分明的聚类问题，在这种没有确 定支持的情况中，聚类可以引入模糊逻辑的概念。模糊聚类扩展了传统聚类的思 想，通过使用隶属函数，使得可以把每个数据分配给所有的聚类；不同与传统聚 类方法的是，对于模糊集来说，一个数据最终可能是以一定程度属于某个聚类， 也可能同时以不同的程度属于几个聚类。常用的模糊聚类算法是模糊c 均值 f c m ( f u z z yc m e a n s ) 聚类算法1 1 9 j 。 2 3 聚类分析在生物信息方面的应用 生物信息学是一门生物学与信息科学交叉而形成的年轻学科，旨在运用信息 学、物理学、化学、数学、计算机科学、系统科学的理论和方法来研究生物系统 和生物过程的信息量和信息流，包含着基因组信息的获取、存储、分配、分析和 解释的所有方面。庞大的生物信息数据库对数据挖掘技术提出了许多颇具挑战性 的问题，也提供了广阔的机遇。应用数据挖掘中的聚类技术分析生物数据，可以 帮助我们研究基因、蛋白质的性质功能，为探索生物的奥秘提供帮助【2 0 1 。 2 3 1 聚类基因表达数据 与一次只能分析几十个基因的传统方法相比，微阵列技术可以同时测量上千 个基因的表达水平。微阵列技术是研究丰富多彩生物系统的一个有效工具。聚类 是分析微阵列数据重要的任务之一，它用于辨别有相似表达的基因组。聚类可以 减少研究单个基因的开销，更重要的是它可以揭示基因中的功能组，通常认为表 达模式相近的基因具有相近或相关的功能。已经有很多聚类算法，如层次聚类方 法、基于主要成分分析的方法、遗传算法、神经原网络方法，被用于聚类基因表 达数据，近期又提出很多算法。这些算法都是串行的，由于基因表达数据的数据 量较大，串行聚类算法运行时间较长、空间要求较大。并行技术可以有效地解决 串行算法运行时间长、对空间要求大的问题。例如，d a v i dw i l d 提出应用b a y e s i a n 方法【2 1 j 进行蛋白质聚类基因表达聚类的目标是将表达模式相近的基因聚在一起。 由于基因表达数据的特点：数据量大、数据维数高，而且要求聚类结果易于理解， 现有的方法都是针对这三个特点来设计的。a g g a r w a l 首先提出了p r o j e c t e d c l u s t e r i n g 的概念【2 2 1 ，它的目的是在低维子空间中分组高维数据，每个不同的簇投 影高维数据点到不同的低维子空间中，在维减小的过程中最小化信息的丢失。随 后就出现了很多寻找p ro j e c t e dc l u s t e r i n g 的算法，这些算法都可以用来聚类基因 表达数据。如c c a g g a r v a l 和p s y u 的0 r c l u s 算法【2 3 】；c m p r o c o p i u c 和 9 聚类分析研究及其n ：生物数据中的应用 p k a g a r w a l 提出的d o c 和f a s t d o c 算法【2 4 】； p a b l ot a m a y o 等人把神经网络中 的s o m 算法应用到了聚类基因表达数据中，由于s o m 适用于高维空间数据，计 算时间复杂度是线性的而且计算结果易于解释等特点令s o m 非常适合聚类和分 析基因表达数据。d o n g g 和l i j 提出了e m e r g i n gp a t t e m 的概念和计算方法【2 5 】。 e m e r g i n gp a t t e r n s 是数据集中属性的集合，这些属性集满足从一类数据到另一类 数据的变化率大于给定的阀值，使用这个方法得到的聚类结果易于理解。e m e r g i n g p a t t e r n s 可以从数据中捕获重要的生物信息，如仅在癌组织中存在而不在正常组织 中存在的e p s 可能是引发癌证的基因。j i n y a nl i 和l i m s o o nw o n g ，l a r r yt h y u 和f u l a ic h u n g 提出的e p p c 算法都是应用e m e r g i n gp a t t e m s 方法来聚类基因表 达数据。h a i x u nw a n g 和p h i l i ps y u 等人提出了p c l u s t e 算法【26 1 ，该算法的作用 是只要两个对象在维的子维上展现一个变化致的模式，那么这两个对象就是相 似的。 2 3 2 聚类蛋白质序列 近年来，蛋白质序列数据量快速增长。聚类蛋白质序列数据可以帮助我们确 定哪些序列具有相似的功能。过去，开发了很多计算蛋白质序列聚类的方法。最 基本的方法是计算每两个蛋白质序列的比对，然后使用层次聚类方法计算求得结 果，例如k r a u s e ，v i n g r o n 提出的s y s t e r s 算法【2 。7 】和e n r i 曲t ，o u z o u n i s 提出的 g e n e r a g e 算法【2 引。这种方法虽然简单易行，但这种方法的时间复杂度接近 r 2 。b o l t e n e 等人提出一个基于有向图聚类蛋白质序列数据的算法【29 1 。图中的 顶点是蛋白质序列，图中的边的权值是相应序列之间距离的值，删除权值小于特 定阀值的边。计算该图的所有强连通分量，所得的强连通分量就是我们要求的聚 类结果。近年来又提出了一些新的方法。v a l e r i eg u r a l n i k 和g e o r g ek a r y p i s 提出 了一个和以前多对多序列分析完全不同的f b 方法，这个方法具有接近线性的时 间复杂度。f b 方法的主要思想是首先找到序列特征集，应用局部裁减方法裁减特 征集，用剩余的特征建立新空间，数据序列在新空间中投影，建立序列的相似矩 阵，最后使用k 。m e a n s 方法对相似矩阵进行聚类【3 0 ，3 。 2 3 3 构建系统发育树 系统发生( 或种系发生、系统发育) 是指生物形成或进化的历史。系统发生 学研究物种之间的进化关系，其基本思想是比较物种的特征，并认为特征相似的 物种在遗传学上接近。系统发生研究的结果往往以系统发生树表示，用它描述物 种之间的进化关系。通过对生物学数据的建模提取特征，进而比较这些特征，研 究生物形成或进化的历史。在分子水平上进行系统发生分析具有许多优势，所得 到的结果更加科学、可靠。分子系统发生分析主要分成三个步骤：分子序列或特 征数据的分析、系统发生树的构造以及结果的检验f 3 2 】。 l o 硕j 二学位论支 事实上，分子系统发生分析就是一个聚类分析的过程，将分子序列或特征数 据转化为聚类分析的数据类型，即系统发生分析的步骤一，再次分别在物种不同 是时期对物种进行聚类，得到物种各个进化阶段的聚类情况，从而就可以知道系 统的进化史，即系统发生分析的步骤二。步骤三也就是从统计学的角度来验证聚 类的结果。 构建系统发生树的聚类方法很多种。根据所处理数据的类型，可以将系统发 生树的构建方法大体上分为两大类。一类是基于距离的构建方法，这类方法大多 数是属于层次聚类算法，利用所有物种或分类单元间的进化距离，依据一定的原 则及算法构建系统发生树。基本思路是列出所有可能的序列对，计算序列之间的 遗传距离，选出相似程度比较大或非常相关的序列对，利用遗传距离预测进化关 系。这类方法有连锁聚类方法、非加权分组平均法、邻近归并法、f i t c h m a r g o l i a s h 法、最小进化方法等。另一类方法是基于离散特征的构建方法，利用的是具有离 散特征状态的数据，如d n a 序列中的特定位点的核苷酸。建树时，着重分析分 类单位或序列问每个特征( 如核苷酸位点) 的进化关系等。属于这一类的方法有 最大简约法、最大似然法、进化简约法、相容性方法等【3 3 35 1 。 2 4 本章小结 本章综述了聚类分析及其在生物信息方面的应用。聚类分析是按照不同对象 之间的差异，根据每个样本对象的各种特征，通过无监督训练将样本按类似性分 类，把相似性大的样本归为一类。数据聚类正在蓬勃发展，有贡献的领域包括数 据挖掘、统计学、机器学习、空间数据库技术、生物学，以及市场营销。聚类分 析的主要步骤为：一、特征提取；二、聚类算法选择；三、参数设置。聚类分析 算法主要