（计算机应用技术专业论文）基于som基因聚类的基因数据组织样本聚类.pdf

摘要 摘要 随着dn a 芯片技术的广泛应用，基因表达数据分析已成为生命科学的研究 热点。样本聚类分析能根据基因表达谱的相似程度把样本归纳成类，有助于对未 知功能的基因进行研究，是目前各种基因表达分析研究的重要基础。但由于基因 微阵列是只有少量样本的高维基因数组，传统聚类方法进行组织样本聚类受到大 量无关基因的干扰。本文提出一种基于基因聚类进行样本聚类的方法。先提出一 种基于环状结构自组织图( s o m ) 的基因聚类方法，由于基因类在s o m 输出层的位 置能反映基因类之间的相似程度，这样就得到了基因闯关系的些有用信息。根 据这些信息作者利用敏感程度来进行特征基因选择，从而达到降维的目的。最后 在只有特征基因组成的低维空间中对样本聚类。本文的新算法深入挖掘基因信息， 在增加对基因认识的基础上对样本聚类，明显优于传统样本聚类方法。利用真实 微阵列数据进行的实验证明了新算法的可行性和高效性。在此基础上，本文深入 研究脉冲耦合神经网络，并把它应用于组织样本聚类，脉冲耦合神经网络具有高 度的并行性，能够快速准确的取得聚类结果。实验证实了算法的有效性。 关键字：基因聚类样本聚类敏感程度自组织网脉冲耦合神经网络 目录 a b s t r 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 e a t i o no fd n ac 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 v e b e c o m eah e t s p o ti nl i f es c i e n c ef i e l d 他s u e c l u s t e r i n g ， t h ep r o c e s so fg r o u p i n gr e l a t e ds a m p l o sa c c o r d i n gt og e n ee x p r e s s i o nl e v e l s ，i sv e r y u s e f o lt ot h er e s e a r c ho fg e n cu n k n o w nf u n c t i o n s ，a n di so n eo ft h em o s ti m p o r t a n t f o u n d a t i o no fm i e r o a r r a ys t u d y m i c r o a r r a yd a t ah a ss u c haf e a t u r et h a ti th a saf e w t i s s u es a m p l e sb u te a c hc o r r e s p o n d st oe x p r e s s i o nl e v e l so fah l g en u m b e ro fg e n e s ，i n w h i c hal o ti n t e r f e r et h eg r o u p i n gs t r u c t a r eo ft h ed a t aa n db o t h e rt h ef e a s i b l e c l u s t e r i n go f t h et i s s u e s i nt h i sp a d e r ，w e p r e s e n tat i s s u ec l u s t e r i n gm c t h o d b a s e do n t h ef a c tt h a to n l yaf e wn u m b e ro fg e n e s ，i e ，t h ec o n t r i b u t i v eg e n e s ，a r ef i r s ts e l e c t e d f r o mt h eh u g en u m b e ro fg e n e s ，a n dt h et i s s u es a m p l e sa r ee l u s t e r e dw i t ho n l yt h e e x p r e s s i o n l e v e l so ft h e s ec o n t r i b u t i v eg e n e s i no u rm e t h o d ，t h ec o n t r i b u t i v eg e n e sa r e s e l e c t e dv i aac i r c u l a r - s t r u c t u r e ds o m ，i nw h i c ht h em o r ed i s t a n ts o m et w og e n e si nt h e s o m ，t h em o r ei n d e p e n d e n tt h e yf u n e t i o nf o rc l u s t e r i n g ，t 1 l es e n s i t i v i t yo fag e r ei s d e f i n e df o rt h em e a s u r e m e n to ft h ec o n t r i b u t i o no ft h eg e n ef o rg e n es e l e c t i o nf r o mt h e o u t p u to ft h e s o m ，a n db o t hk - m o a n sm e t h o da n ds o mm e t h o da l eu s e df o rt i s s u e c l u s t e r i n g o u re x p e r i m e n t a lr e s u l to n r e a lm i c r o a r r a ys h o w st h eg r e a te f f e c t i v e n e s sa n d e f f i c i e n c yo f t h em e t h o d p r e s e n t e d i nt h ep a p e r 0 nt h i sb a s i sf u r t h e rs t u d yi sm a d eo n t h ef e a t t i r e so fp u l s ec o u p l e dn e u r a ln e t w o r k t h e nac l u s t e r i n ga l g o r i t h mb a s e do na p c n ni sp r e s e n t e d ，w h i c hi so fh i g hp a r a l l e l i s ma n dc a ng e tt h ec l u s t e r i n go u t c o m e f a s t e ra n dm o r ee x a c t l yt h a no t h e rm e t h o d s 弧ee x p e r i m e n t a lr e s n l t sp r o v ei t sg r e a t a d v a n t a g e o v e ro t h e r s k e yw o r d s ：g e n ec l u s t e r i n g , t i s s u ec l u s t e r i n g ，s e n s i t i v i t y ，s e l f - o r g a n i z i n gm a p s ，p u l s e c o u p l e d n e u r a ln e t w o r k - 创新性声明 v6 9 5 5 1 6 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：刁j 2日期逝皇：f ：堡 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本人签名：冱f 圣 导师签名：匦 日期迦：! ：翌 日期3 丛1 。竺 第一蕈绪论 第一章绪论 1 1 微阵列与基因表达研究概况 基因芯片( g e n ec h i p ) 是近年来生命科学与微电子等学科相互交叉产生的一项 新技术，在序列分析、基因表达、基因组研究及基因诊断等领域显示出重要的理 论和实际应用价值。基因芯片是生物芯片( h i o c h i p ) 的一种，有多种叫法，如d n a 芯片( d n ac h i p ) 、d n a 微阵歹i j ( d n am i c r o a r r a y ) 等。基因芯片技术是随着人类基因 组计划的发展应运而生的，初衷是为了研究更快的测序方法。1 9 9 6 年，美国 a f f y m e t r i x 公司充分结合照相平板印刷、计算机、半导体、激光共聚焦扫描、d n a 合成、荧光标记、探针杂交及其他分子生物学技术，创造了世界上第一块基因芯 片。基因芯片作为一门新兴技术，已经在生物医学的各个领域得到广泛应用”1 ，简 介如下。 1 ) 基因测序和突变检测。d n a 芯片用于测试是基于杂交测序法( s b h ) 发展而来 的，该技术增加了微阵列中寡核苷酸的有效长度，从而增加了测序的准确性，可 对较长的d n a 片段进行测序，另外也适用于对不同基因组同源区序列的比较及含 有内部重复序列d n a 片段的序列分析。 2 ) 致病微生物的快速诊断。a n t h o n y 等人建立了一个在4 4 , 时以内便可检测和 识别出致病微生物的方法，该方法的具体过程是使用随机引物通过p c r 法扩增细菌 核糖体d n a ，后通过检测系统来识别。 3 ) 癌症的诊断及治疗。目前基因芯片技术已应用于癌相关基因突变的快速检 测。由于可以利用基因芯片对某一细胞的基因表达情况进行一个全面的了解，所 以基因芯片技术还可进一步应用于癌症的精确认断及治疗，利用该技术可对包括 白盘病、淋巴瘤、皮肤黑色素瘤及乳腺癌等多种癌症的癌细胞亚群进行区分，还 可利用它对治疗方案进行评估和新药药效评价，此外还能对癌症的发生、发展和 转归进行预测。此外，可利用基因芯片技术观察药物对肿瘤细胞基因表达谱的影 响，评估药物对肿瘤治疗的可行性从中筛选出抗肿瘤候选药物，对肿瘤药物的 研究和开发提供了极具价值的参考资料。基因芯片技术在癌症基因研究及临床治 疗领域的应用将不但使我们能更快速可靠地对癌症进行诊断，对其发生的内在分 子机理也将有更深入的了解，同时也将为癌症治疗药物的开发提供极大帮助。 4 ) 寻找新基因。定量检测大量基因表达水平在阐述基因功能、探索疾病原因 及机理、发现可能的诊断及治疗等方面是很有价值的。基因芯片技术在发现新基 因及分析各个基因在不同时空表达方面是一项十分有用的技术，它具有样品用量 极少，自动化程度高等优点，便于大量筛选新基因。目前，大量人类e s t s 给c d n a 微阵列提供了丰富的资源，数据库中4 0 0 0 0 0 个e s t s 代表了所有人类基因，成千上 !基于s o m 基因聚类的基因数据组织样本聚类 万的e s t s 微阵列将为人类基因表达研究提供强有力的分析工具。这将大大地加速 人类基因组的功能分析。 5 ) 后基因组研究。基因组测序完成后，未知基因的功能研究是一个十分诱人 的后基因组研究课题。斯坦福大学的d a v i s 研究小组的研究提示d n a 芯片技术将来 可能应用于人类基因组测序完成后阐明开放读码框架o r f 生物学功能的研究，可 能会对深刻认识生命现象及药物设计带来重大影响。 此外，基因芯片还广泛地应用于药物筛选、药物作用机制研究、毒理学研究、 基因扫描、环境化学毒物的筛选、耐药菌株和药敏检测等多个应用领域。人们相 信，在新的世纪中，基因芯片将会在人类疾病的基因诊断中发挥巨大的作用，为 整个世界带来巨大的社会效益。 1 2 基因表达聚类分析技术的现状 目前所知，基因表达数据至少可以从以下三个逐渐复杂的层次上进行分析p 1 ： 第一，分析单条基因的表达水平，此时人们着眼于一定实验条件下每条基因的表 达是否与对照不同；第二，考虑基因组合，将基因分成不同的类别以研究基因的 共同功能、相互作用以及协同调控等；第三，尝试推断潜在的调控区域及基因网络， 以从机理上解释观察到的图谱。目前对基因表达数据的研究主要集中于第二层， 而第三层则是更深一步的研究目标。 已有多种数据挖掘和信息处理技术被应用于基因表达数据分析，主要包括： 聚类分析、多元统计、模式识男g 及神经网络等几大类。功能相关的基因通常共同 表达，检测具有相似表达谱的基因群是研究基因功能的一种有效方法。因此，基 因表达数据分析的一类重要方法就是聚类分析h 。聚类分析是指将一组个体按其相 互间的相似程度归入几个子类，根本思想是确定类群，使同一类内的各个体间差 异最小，而不同类间的差距最大。基因表达数据的聚类问题包括两个方面：基因 聚类( g o n ec l u s t r i n g ) f f 0 维织样本聚类( t i s s u ec 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 ) 州、k - 均值法( c - m e a n s ) 1 、和自组织 ( s e l f - o r g a n i z i n gm a p s ) 1 等；组织样本聚类主要用于肿瘤分型，由于 基因生物知识的缺乏，徽阵列数据过于复杂等原因，组织样本浆类研究远远落后 于基因聚类研究分类研究。文献中难得见到组织样本聚类的研究成果，只有一些 科学家对样本运用监督分类取得一些成果：g o l u b 掣叫利用基因表达谱对人白血病 第一章绪论 3 进行了分类；x i o n g 等p 1 采用了主成分分析与f i s h e r 判别分析方法相结合的办法， 对结肠癌数据进行了分类研究，结果显示：采用7 个主成分可以获得精度为8 7 的 判别结果。2 0 0 2 年l i w j l l u 采用f i s h e r 方法与逐步优化过程相结合的办法，只用5 6 个基因，预测精度就可达到大约9 5 。从结果看，一是有些算法分类的精度还不 够高：二是有些算法用特征提取降维，不能直接对基因功能提供说明，所以引入 高精度能得出特征基因的聚类算法在基因数据处理中十分必要的。长远来看，生 物学越来越成为可以量化的学科，今后基因表达数据分析方法将会有很好的发展。 1 3 脉冲耦合神经网络简介 神经网络( n e u r a ln e t w o r k ) 是近年来再度兴起的一个高科技研究领域，是信 息科学、脑科学、神经心理学等多种学科近年来研究的一个热点。人工神经网络h 是指模拟人脑神经网络的结构和功能，运用大量的处理部件，由人工方式建立起 来的网络系统。它是在生物神经网络研究的基础上建立起来的，人脑是人工神经 网络的原型，人工神经网络是对脑神经系统的模拟。人工神经网络能在定程度 上模仿生物神经系统的智慧和功能，它在信息处理和智能科学中有着极其重要的 地位，作为人工神经网络的典型模型之一，多层前向神经网络及反馈型人工神经 网络( 以h o p f i e l d 网络为代表) ，是在模式识别和分类等方面发展的最早、研究人员 最多、应用最为广泛的人工神经网络模型，对促进人工神经网络研究在8 0 年代的 复苏起了重要的作用。在这些网络中的神经元是静态的，实现的是非线性映射功 能( 最为典型的为类s i g m o i d 函数) 。随着生物神经学的研究和进展，一种被称为第 三代人工神经网络的新型人工神经网络模型_ 脉冲耦合神经网络模型伊。州一 p l l l s ec o u p l e dn e u r a l n e t w o r k ) 的研究在国外悄然* 起，而猫视觉皮层中同步脉冲 发放现象的发现则促使了这种被称为第三代人工神经网络的新型人工神经网络模 型脉冲耦合神经网络模型( p c i 悄呻】i s ec o u p l e dn e u r a ln e t w o r k ) 的研究热 潮的兴起。这种网络由变阈值非线性动态神经元组成，具有许多独特的优良特性： 时空总和特性、动态脉冲发放特性和同步脉冲发放引起的振动与波动等特性，正 是由于p c n n 的这些特性，使得对p c n n 的研究不仅具有熏要的理论意义，而且 具有非常广泛的应用前景，其应用领域涉及到强时变信号处理( 如运动目标识别) 、 图像处理( 滤波、分割、融合等) 、图像目标识别、图像理解、人工生命、注意、决 策优化、通讯等，并且这些应用受到国外的广泛重视和研究。国际上关于人工神 经网络的专门刊物i e e et r a n s o nn e u r a ln e t w o r k s 还于1 9 9 9 年5 月出版了p c n n 的专辑。 e u g e n em i z h i k o v i c h 将p c n n 放在一个较为严格的数学框架下加以分析，证 明了实际的生物细胞模型与p c n n 模型是一致的，所不同的只是变量的坐标；给 出了分析神经动力学的新方法，它将神经元跌射成基于耜位的摸型，指出脉冲频 4 基于s o m 基因聚类的基因数据组织样本聚类 率有时也不携带信息，只是传输通道的一种标识字，而携带信息的是相位调制， 这是一个崭新的概念，其应用将远远超出神经网络领域，对于通信路由选择及并 行计算机的构造具有指导意义。其它有关的研究包括：p l e s s e r 和g e r s t n e r 在2 0 0 0 年第二期出版的i e e et r a n s o nn e u r a ln e t w o r k s 上研究了噪声对时变信号的 p c n n 响应的影响。k i s t l e r 和l e o 在同一期中提出了一种便于对两个邻接神经元 点火特性的相关性进行分析的神经元模型：b r e s s l o f f 和c o o m b e s 对具有强耦合的 p c n n 的动态行为进行了研究，指出在弱耦合情况下稳定的相位锁定状态是如何随 着耦合强度的增加而进入不稳定的；h u i n g 、g l u d e r 和p a l m 提出了一种对p c n n 的无监督学习规则，a h i s s a r 给出了通过神经元的相位锁定环实现时序编码到频率 编码的方法，b u r k i t t 和c l a r k 给出了神经网络中神经元群体的同步行为与其平均 作用水平的关系，d e c o 和s c h f i n n a n n 给出了分析p c n n 网络神经元点火概率分布 的一种新方法，b u r k i t t 和c l a r k 提出了一种基于信息论准则的p c n n 学习的框架。 总之，关于p c n n 的研究应用，现有的文献显示比较狭隘，有的如基于p c n n 的 图像凹点( f o v e a t i o np o i n t ) 搜索，图像分割，目标检测，最短路求解，目标检测中 的图像融合，听觉图像分析及语音信号分离，t s p 问题求解等等。没有人把p c n n 应用到生物基因研究中，国内本来基因研究这方面的工作开展得就很少，挤出更 薄弱。而将p c n n 应用于基因数据聚类方面，这是前人未曾尝试过的，在这个方 面仍是一片空白。因此对于我们来说，有必要从理论以及实验的角度去论证前人 所提方法的优点和不足，并继续探索基于p c n n 的其它应用领域。 1 4 本文工作与结构 作者在前人研究基因微阵列数据处理的基础上，对基因表达数据的基因聚类 和组织样本聚类问题进行了深入的研究，深入分析了s o m 网络和基因表达谱的特 性，分析组织样本聚类和基因聚类的内在联系，在此基础上提出了新的组织样本 聚类方法并把它运用于肿瘤分型。而且还仔细研究了一种新的神经网络p c n n ，提 出了把p c n n 神经网络用于基因数据组织样本聚类的方法。 具体章节的内容安排如下： 第一章简单介绍了基因微阵列以及p c n n 的兴起和研究现状； 第二章介绍了自组织神经网络的基本模型和概念，分析了s 0 1 1 的工作原理、 运行行为及其基本特性，并介绍了基于自组织神经网络的聚类和几种经典的数据 聚类方法； 第三章重点讲述了基于自组织神经网络基因聚类的组织样本聚类方法，改进 了s o m 结构并提出敏感强度作为基因选择的指标，进行了一系列的实验； 第四章介绍了p c n n 神经网络的结构和特点，并使用p c n n 聚类算法实验组 织样本聚类。 第一章绪论 第五章总结本论文的主要研究成果及意义，同时也指出了研究工作中存在的 不足和进一步的解决思路。 本论文的研究工作在国家自然科学基金资助项目( n o 6 0 0 7 1 0 2 6 n o 6 9 9 7 1 0 1 8 ) 、国防科技预研跨行业基金资助项目( n 沁o o j l 4 4 d z 0 1 0 6 ) 、信息处理 与智能控制教育部重点实验室开放基金资助项目0 帕t k i j 0 0 0 5 ) 的支持下完成。 6 基于s o m 基因聚类的基因数据组织样本聚类 第二章基于自组织神经网络的聚类 聚类分析h 是模式识别理论的一个重要组成部分，人们先后提出了实现聚类的 多种方法，例如有谱系聚类法、c 均值法、模糊c 一均值法和神经网络法等。8 0 年代以来，由于目标函数法具有设计简单，解决问题的范围广，并且最终可以归 结为优化问题的优点，已成为聚类分析的主流方法。由于该方法采用数值迭代算 法，因此在大数据量聚类中，运算速度较慢。到8 0 年代后期和9 0 年代，由于神 经网络的兴起，利用神经网络实现基于目标函数的聚类取得了许多成果。自组织 神经网络是一种常用的神经网络，具有强自学习能力、并行分布式信息存储与快 速识别等优点，特别是自组织网具有临近相似性，在实现基因数据聚类方面有着 不同一般的效果。 。 2 1 聚类分析的概念及任务 在很多实际应用中由于缺少形成模式类的知识，或者由于实际工作中的困难 ( 例如卫星遥感照片上各像元的分类闯题) ，我们往往只能用没有类别标签的样本 集进行工作。这就是通常所说的非监督学习方法。般来说非监督学习方法可以 分成两大类，即基于概率密度函数的直接方法和基于样本间相似性度量的间接聚 类方法。不论哪种方法，再把样本集划分为若干子集( 类别) 后，我们或者直 接用它解决分类问题，或者把它作为训练样本集进行分类器设计。 2 1 1 聚类分析的基本思想 聚类分析的基本思想非常朴素、直观和简单，它是根据各个待分类的模式特 征相似程度进行分类的，相似的归为一类，不相似的作为另一类。简单的说，相 似就是两个特征矢量之间各分量分别比较接近。聚类分析包括两个基本内容：模 式相似性的度量和聚类算法。由于在分类中不需要用训练样本进行学习和训练， 故此方法称为无监督分类。 2 1 。2 方法的有效性 基于模式相似准则而建立的分类方法的有效性，从根本上讲，首先取决于模 式特征点在特征空间的分布情况。如果同类的横式特征点密集，不同类的模式特 征点相距较远，即特征点按类群聚，一般的分类方法通常是有效的；反之，如果 不同类的模式特征点混杂散步，许多分类方法往往无效或效果不佳既然某些对 象属于不同的类别，它们之间必然有一些重要特征显著不同，之所以出现上述特 点混杂情况，原因是特征选得不当，可能是对于所选取的特征，不同类的模式的 特征值差别不大，换句话说，有显著差别的特征没有选取。这时应该重新提取特 征，选取它们之间显著不同的特征而产生新的特点。另一个可能的原因是，虽然 各分量满足上述要求，但它们组合起来未必能使这些特征点按群秉类。从技术上 第二章基于自组织神经网络的聚类 7 讲，方法的有效性取决于分类算法和特征点的分布情况的匹配。在本论文中，我 们主要讲述和讨论聚类算法。 2 2 传统聚类算法介绍刚 2 2 1 聚类的技术方案 聚类分析有许多具体的算法，有的比较简单，有的相对复杂和完善，从算法 的基本策略上看，可以分为如下三种： 1 根据相似性阙值和最小距离的简单聚类方法。针对具体问题确定相似性闽 值，将模式到各聚类中心间的距离与闽值比较，都大于阈值时该模式就作为另 类的类心，小于阈值时按最小原则将其分划到某一类中。这类算法运行中模式的 类别及类的中心一旦确定下来将不会改变。 2 按最小距离原则不断进行两类合并的方法。首先视各类模式自成一类，然 后将距离最小的两类合并成一类，不断的重复这个过程，直到成为两类为止。这 类算法运行中，类心不断的修正，但模式类别一旦指定后就不再改变，就是说模 式一旦划为一类后就不再被划开。这类方法称为谱系聚类方法。 3 依据准则函数动态聚类法。设定一些分类的控制参数，定义一个能表征聚 类过程或结果优劣的准则函数，聚类过程就是使准则函数去极值的优化过程。算 法运行中，类心不断的修正，各模式的类别的指定也不断的更改。 2 2 2c 一均值算法( c m e a n s 算法) 1 条件及约定 设待分类的模式特征矢量集为“，z ：，h ) ，类的数目c 是事先取定的。 2 基本思想 该方法取定c 类和选取c 个初始聚类中心，按最小距离原则将各模式分配到c 类中的某一类。之后不断地计算类中心和调整各模式的类别，最终使各模式到其 判属类别中心的距离平方和最小。 3 算法步骤 ( 1 征选c 个模式特征矢量作为初始聚类中心：上：o ) 。z ? ，z t a 。) ，令k 0 。 ( 2 ) 将待分类的模式特征矢量集瓴 中的模式逐个按最小距离原则分划给c 类 中的某一类，即 如果甜- m 扣鼢) j ，j - 1 , 2 , ，n ( 2 - d 则判 工f 埘p “) 。 式中d g 表示一和r 的中心z r 的距离，上角标表示迭代次数。于是产 生新的聚类脚“( j l 2 ，c ) 。 !基于s o m 基因聚类的基因数据组织样本聚类 ( 3 ) 计算重新分类后的各类心 z 严“_ 方。毒+ 。，h 2 ，c t 式中n 譬“为n ，“类中所含模式的个数。 因为这一步采取平均的方法计算调整后各类的中心，且定为c 类，故称c 一均 值法。 ( 4 ) 如果z # + u z 1 ( j = 1 ，2 ，c ) ，则结束，否则，七一k + l 转至( 2 ) 。 4 性能 c 均值法是以确定的类数及选定的初始聚类中心为前提，使各模式到其所判 属类别中心距离( 平方) 之和最小的最佳聚类。显然，该算法的分类结果受到取 定的类别数目及聚类中心的初始位置的影响，所以结果只是局部最优的。但其方 法简单，结果尚令人满意，故应用较多。如模式分布呈现类内团聚状，该算法是 能达到很好聚类结果的。在实际应用中需要试探不同的c 值和选择不同的聚类中心 初始值，以进一步达到更大范围的最优结果上述算法的特点是所有待分类模式按 最小距离原则分划类别之后，再计算各类的中心，这称为按批修改法另一种方法是 每向算法输入一个模式后就将它进行分类，并计算该模式所进入类的类心，这称为 逐个修改法，因而其还受模式读入次序的影响按批修改和逐个修改方式的动态聚 类法的收敛性已于1 9 7 4 年和1 9 6 9 年分别给出了严格证明 2 2 3 模糊c 一均值法 在上一节介绍的c - m e a n s 聚类法的目的是把一个样本划分到c 个类别中的一个 中，使各个样本与其所在类均值的误差平方和最小。在本小节中，我们讨论如何 将这种硬分类变为模糊分类，从而得到模糊c 一均值法。 将问题的有关符号规定如下：仉，i - 1 2 ，玎 是h 个样本组成的样本集合，c 为 预定的类别数目，m ；，i 一1 ，2 ，c 为每个聚类的中心，一；“) 是第f 个样本对于第j 类的隶属度函数。用隶属度函数定义的聚类损失函数可以写成为： - ，。耋砉凶，“) ，k m ( z 一。) 其中，b ，1 是一个可以控制聚类结果的模糊程度常数。 在不同的隶屑度定义方法下最小化( 2 - 3 ) 的损失函数，就得到不同的模糊聚 类方法。其中最有代表性的是模糊c - 均值法，它要求一个样本对于各个聚类的隶 属度为1 ，即 善乒j 健) 州啦，卅( 2 - 4 ) 第二章基于自组织神经网络的聚娄 9 在条件式( 2 4 ) 下求式( 2 3 ) 的极小值，令，对m ，和肛f “) 的偏导数为0 ，可 z k ，纯) _ f x ， 埘，= 艺_ _ _ ，j l 2 ，c ( 2 - 5 ) 艺k ，“) ， ，。；，一器，z-l毛，订；，一lz，c c z e ， 用迭代方法求解式( 2 5 ) 和( 2 6 ) ，就是模糊c 一均值法。算法步骤如下： ( 3 ) 重复下面的运算，直到各个样本的隶属度值稳定： 用当前的聚类中心根据式( 2 - 6 ) 计算隶属度函数； 用当前的隶属度函数按式( 2 5 ) 更新计算各类聚类中心。 当算法收敛对，就得到了各类的聚类中心和各个样本对于各类的隶属度值， 模糊集理论是为了表达人的自然语言和推理中的不明确方面而提出的，因此 其应用中往往不可避免的带有一定的主观因素，比如隶属度函数的选取等。模糊 2 2 4 分级聚类法【1 1 ( h l e r a 托h i 恤ic 嘶托r h 堰m e m o d ) 这种方法是效果较好、经常使用的方法之一，国内外研究的较为深入，有不 设待分类的模式特征矢量集为 _ ，工：，h ，掣表示第| 次合并时的第f 类。 首先视n 个模式各自成为类，然后计算类与类之间的距离，选择距离最小 的一对合并成一个新类，计算在新的类别分划下备类之间的距离，再将距离最近 ( 1 ) 初始分类。令七- 0 ，每个模式自成一类，即卵- “ ( f l 2 ，) 。 ( 2 ) 计算各类间的距离岛，由此生成一个对称的距离矩阵d - ( p 口) 。，m 类 ( 3 ) 找出前步求得的矩阵d ( 中的最小元素，设它是g r 和g ( i 问的距离，将 旦 基于s o m 基因聚类的基因数据组织样本聚类 g j 和g5 两类合并成一类，于是产生新的聚类g f “，g ，”，令k 一七+ 1 ， m - m 一1 ，m 为矩阵的行列数。 ( 4 ) 检查类的个数。如果类数m 大于2 ，转至( 2 ) ；否则，停止。 如果某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类 对可以同时合并。上述算法步骤给出了从类至2 类的聚类过程，在实际应用中 该算法也可将类间距离门限r 作为停止条件，当d ( 中最小阵元大于t ( 即d ( 七中 的任一元大于t ) 时，聚类过程停止；该算法也可将预定的类别数目作为停止条件， 在类别合并过程中，类数等于预定值时，聚类过程停止。 上述算法在归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如 果有单调不减关系则称类间距离对并类具有单调性。最近距离法、最远距离法、 平均法及离差平方和法等定义的类间距离都具有这个性质，而重心法没有这个性 质。该算法的特点是在聚类过程中类心不断地调整，但一些模式一旦分划到某 聚类中就不再分划开。这类技术的另一个算法和上述算法过程相反，依据类的离 差平方和递推公式按1 类至类进行分解，这里不作介绍了。聚类过程可以表示 成一个树图。 2 3 基于自组织神经网络的聚类算法 人脑是由大量的神经元组成的，它们并非都起着同样的作用，处于空间不同 部位的区域分工不同，各自对输入模式的不同特征敏感。t k o h o n e n 认为：神经网 络邻近的各个神经元通过侧向交互作用彼此相互竞争，自适应地发展成检测不同 信号的特殊监测器，这就是自组织特征映射的含义。1 9 8 1 年，k o h o n e n 提出了模 拟大脑神经系统自组织特征映射的人工自组织映射网络，人工白组织映射与大脑 映射有许多共同特征，通常又称作自组织映射神经网络或简称s o m 网络“。s 伽 网络可以作为一种神经网络聚类方法，它以无监督的方式进行网络训练，能自动对 输入模式进行聚类。 2 3 1 自组织神经网络结构 自组织映射网络是一种竞 争式学习网络，在学习中能无 。 监督地进行自组织学习。输出 岫 层的类神经元们彼此竞争，以 争取学习的机会。基于竞争方 式的s o m 网络基本结构如图 嬲 2 1 所示。 i 图2 1 中，输出层有f 1 个 输出神经元；输入层是任意一 i ， o ，吐 图2 1 自组织网的基本结构 第二章基于自组织神经网络的聚类 个1 。维的输入x ：啦是一个l x m 维的向量，表示第i 个输出神经元与输入之间的 链接权值。对于每一个输入x ，都只有一个输出神经元竞争胜利，这个胜利神经元 即图2 1 中的w i n n e ro u t p u t ，胜者获得了学习的机会，可以修改对应的链接权值 晰。 然而，s o m 网络与一般竞争式学习神经网络稍微有些不同。依据生理学和解 剖学所得到的证据显示，通常在许多生物的脑部组织中，会有大量的神经元，彼 此之间有侧向联接，而侧向联接的强度与神经元间的距离有关，由观察发现，侧 向联结的强度通常可以以“墨西哥帽函数”来表示。自组织网与通常竞争式学习 神经网络的不同是其采用的“有福同享”的竞争方式，不是“赢者全拿”。也就是 说，自组织网在竞争后，不只获胜神经元有权学习，它周围的神经元也可以学习， 这种学习就遵循所谓的“墨西哥 帽”侧向作用函数。一种典型的 侧向作用函数如图2 2 所示。 如图2 2 所示，我们可以发现侧 向联结作用的三个不同区域： l 、对邻近神经元具有较强正向 刺激作用的区域，即图中标示为 0 的区域。 2 、对较远神经元具有较强负向 抑制作用的区域即图中标示为 0 的区域。 “i l 。 j 。 yo 、f k t 。母t 朔 啪 图2 2 侧向作用函数的基本形式 3 、对更远神经元具有强度较小的正向刺激作用的区域，即图中标示为0 的区域。 所以，s o m 网络实际上是遵循“墨西哥帽”侧向作用函数作用的竟争神经网络。 顺便提及，“墨西哥帽”侧向作用函数的国区刺激作用远大于其它两个区域，为了 简化问题，一般只考虑区的正向刺激作用。 2 3 2 s o m 网络的工作原理 s 0 m 网络的工作原理是将任意维输入模式在输出层映射成一维或二维离散图 形，并保持其拓扑结构不变。此外，两络通过对输入模式的反复学习，可以使权 重向量空间与输入模式的概率分布趋于一致，即权重向量空间能反映输入模式的 统计特征。这种自组织聚类过程是系统自主、无监督的条件下完成的 s o m 网络的竞争层各神经元竞争对输入模式的响应机会，最后仅一个神经元成 为竞争的胜者，并对那些获胜神经元有关的各权重朝着更有利于它竞争的方向调 整，即以获胜神经元为中心，对近邻的神经元表现出正向刺激侧反馈。这样，应 用侧反馈原理， 在每个获胜神经元附近形成一个“聚类区”，学习的结果总是 旦基于s o m 基因聚类的基因数据组织样本聚类 使聚类区内各神经元的权重向量保持与输入向量逼近的趋势，从而使具有相近特 性的输入向量聚集在一起。 2 3 3 自组织神经网络的聚类算法 自组织网( s o m ) 学习算法具体步骤如下： ( 1 ) 初始化s 伽网络。 随机初始化网络的链接权向量嘶，注意所有的n 个链接值初始向量应各不相 同，n 是神经元的个数；确定学习率参数t 7 的初始值；确定领域m 的初始值。领域 m 是指以步骤( 3 ) 确定的获胜神经元七为中心，包含若干神经元的区域范围。 ( 2 ) 任选一个输入模式z ，提供给输入层。 ( 3 ) 以最小欧氏距离( 输入样本归一化后) 或最大相关的方式找出输入j ，后的 得胜神经元，如式( 2 7 ) 。 k a z g d ( ，x f ) ) ( 2 7 ) 其中，啦为输入与第i 个神经元的链接权值，z f 为输入样本，k 为胜利者。 ( 4 ) 以式( 2 8 ) 调整所有神经元的链接值向量 = 黑叼蝇删善盖 s ， 其中，t 为学习迭代次数，叩为学习率参数，m 是得胜者神经元的邻域，后两 者都是学习迭代次数t 的函数。 ( 4 ) 重复步骤2 至步骤4 ，直到学习次数达到预先指定数目为止。 2 3 3 自组织神经网络聚类算法的参数说明 一、学习率参数呀的设定；用来调整链接权值向量的学习率参数应该随着时间 而调整。举例来说，在开始的1 0 0 0 次学习循环中，学习率参数应相当接近l ，然 后随着时问增加慢慢减小，但仍需保持在0 1 以上，学习率参数的变化形式，可 以是线性地递减、指数递减、或是和时间t 成反比等都可以，此时的学习循环，可 以视为是算法的“排列阶段”( o r d e r i n gp h a s e ) 。往后其余的学习循环主要的 日地是细部地调整特征映像图，因此称之为算法的“收敛阶段”( c o n v e r g e n c e p h a s e ) ，收敛阶段时的学习率参数，应保持在相当小的数值( 如0 0 1 或更小) ， 而且收敛阶段通常需要大约数千次的学习循环。 二、邻域m 邻域函数通常采用包围着得胜者类神经元的正方形型式。而邻近 区域函数也可以采用其它的型式，如线形输出层中优胜者的两边、或是平面输出 层中六边形的型式、或是高斯函数的型式等；然而不管采用何种型式，邻域的设 定应于一开始时先包含了全部或较大范围的类神经元，然后随着时间的增加而慢 慢缩减邻近区域的大小。举例来说，在“排列阶段”时。邻域可以线性地随着时 第二章基于自组织神经弼络的聚类 间t 缩减至一相当小的范围；在“收敛阶段”时，邻域应保持只包含一个或两个类 神经元，甚至不需要邻近区域里的类神经元，只针对得胜者类神经元调整其链接 权值即可。 2 4 本章小结 本章首先介绍了聚类分析的概念、任务、其在模式识别中的地位，以及聚类 分析中的一些基本概念。接着，对一些传统的聚类算法加以阐述，并分析了其优 缺点。然后详细介绍了基于s o m 的聚类思想，分析了它临近相似性特性，给出了 s o m 参数的设定说明。在下文中可以看到，具有临近相似特性的s o m 聚类算法对 于基因聚类有特别突出的意义。 基于s o m 基因聚类的基因数据组织样本聚类 第三章基于s o m 神经网络的基因聚类算法 随着人类基因组计划饵g p ) 的开展和深入，产生了海量的基因组序列数据和信 息。如何利用这些研究成果进行基因功能的解析和开发，已成为功能基因组学研 究的重要任务。基因芯片技术给基因功能研究一个全新的契机。它自1 9 8 9 年由 s o u t h e r n 提出后，即受到多方重视和广泛应用，被评为2 1 世纪最有发展前途的2 0 项高新技术之一。利用这一技术，可以同时观察成千上万个基因在不同状态下的 表达水平( 即基因表达谱) ，由此不仅将基因的功能信息比较完整地展现出来，也可 以在基因水平上探讨样本的特征，如肿瘤发生、细胞分化等生命现象，并在此基 础上进行样本分型等研究。目前，基于基因表达谱的样本分型研究主要应用于肿 瘤方面，事实上，与基于形态学或组织学的肿瘤分型相比，基于基因表达谱的肿 瘤分型研究更能触及肿瘤的本质，并可同时找出与肿瘤相关的基因群；然而，基 因芯片所提供的只是庞大的数据集即基因表达矩阵，所蕴藏的用于肿瘤分型的基 因信患并非一目了然，相反，需要复杂的统计学方法从中挖掘相关的生物信息。 这里的统计学方法是指使用模式识别方法处理数据的方法。我们在生活中时 时刻刻都在进行模式识别，我们能认出周围的物体是桌子、椅子，能认出对面的 人是张三、李四，能区分是汽车驶过还是玻璃破碎，是猫叫还是人语。潜意识中 我们已将人类的这种能力看作是想当然的。但是随着计算机的出现，当人们希望 计算机能够像人一样识别各种各样的物体时，才发现让计算机具备这些人类甚至 更低级的动物都具备的能力是一件多么困难的事情。这时研究者们开始广泛关注 如何使计算机能够识别环境，能够将感兴趣的事物从其背景中提取出来，能够对 事物的属性和种类做出正确的合理的判断等，种种类似的问题归结在一起即是我 们今天所称的模式识别。模式识别已经历了5 0 多年的发展，目前为止研究者已经 积累了大量的知识。把模式识别运用到基因数据处理中，必将发挥巨大的作用， 指导和检验生物科学的研究进展本章就是在这背景下，运用聚类方法对肿瘤 样本进行分型。模式识别系统的基本构成如图3 1 所示，由图3 1 得知一个模式 识别系统大致包括：预处理、特征提取和分类器等三部分，而本章的工作重心为 特征基因选择和组织样本聚类，属于后两部分。接下来我们将详纲阐述基因数据 硼螺垃程 图3 1 模式识别系统的基本构成 第三章基于s o m 神经网络的基因聚类算法 处理的发展现状以及我们在此方面已经取得的成果。 3 1 基因芯片原理 微阵列( m i c r o a r r a y ) 又称d n a 芯片、基因芯片( g e n ec h i p ) ，是9 0 年代兴起 的一种对成百上千甚至上万个基因同