（计算机应用技术专业论文）基因表达数据的聚类分析.pdf

摘要随着人类基因组计划的进展，对于基因的功能和基因组内各基因的研究逐步深入。研究基因在不同时间和条件下的表达情况，是认识基因功能的一个主要途径。c d n a 微阵列技术可以同时测量全基因组的基因的表达情况，是生物学家认识基因的重要工具。微阵列技术产生了大量基因表达数据，要从中提取有价值的信息，采用数据挖掘的技术是十分必要的。功能相近的基因其表达模式相似，通过发现相似的表达模式可以预测未知基因的功能。数据挖掘中的聚类算法是按照数据的相似性进行划分，实现物以类聚的思想。本文采用聚类技术对基因表达数据进行处理，可以把表现模式相近的基因聚集到一起，这种划分有助于专业人员发现基因功能和遗传模式。要通过研究表达数据得到基因的功能和调控关系，需要找到恰当的分析方法。本文介绍分析了常用于生物数据分析的聚类算法，其中层次聚类、自组织特征映射网络、模糊平均值法各具特色。聚类中较为重要的一个问题是距离测度的选择，本文采用了欧式距离和相关系数，两者分剐适用于空间分布较近和里线性关系的数据聚类。所有的聚类算法都在网上公布的酵母基因表达数据上进行了实验分析，其中模糊平均值法效果最好。实验使用的是小规模的数据集，采用的聚类算法可以有效的对线性相关的数据进行划分。但是基因之间具有复杂的调控关系，有些是问接的和非线性的，所以在这个领域的研究还需要不断深入下去。关键词：基因表达数据，模糊聚类，生物信息学，数据挖掘a b s t r a e ta st h eh u m a ng e n o m ep r o j e c td e v e l o p i n g ，t h er e s e a r c ho nt h eg e n e s f u n c t i o na n dr e l a t i o n s h i po fg e n e si ng e n o m ep r o g r e s sg r a d u a l l y a n a l y z i n gt h ee x p r e s s i o no fg e n e si st h em a i na p p m a c ht of i n do u tf u n c t i o n so f g e n e s e d n am i c r o a r r a yt e c h n i q u ep r o v i d e sb i o l o g i s t sw i t ht h ea b i l i t yt om e a s u r et h ee x p r e s s i o no ft h o u s a n d so fg e n e si nas i n g l ee x p e r i m e n t a sd a t af r o mm i c r o a r r a yt e c h n i q u ea c c u m u l a t e sa n dd i f f e r e n te x p e r i m e n t sh a v et ob ec o m p a r e d ，i tw i l lb ee s s e n t i a lt oh a v ed a t am i n i n gt e c h n i q u et oe x t r a c tb i o l o g i c a ls i g n i f i c a n c e g e n e sw i t hs i m i l a rf u n c t i o nh a v es i m i l a re x p r e s s i o n w ec a l la n t i c i p a t eg e n e s f u n c t i o n sb ya n a l y z i n gg e n e sw i t hs i m i l a re x p r e s s i o n c l u s t e r i n ga l g o r i t h mp a r t i t i o n sd a t aa c c o r d i n gt ot h e i rs i m i l a r i t y t h r o u g hc l u s t e r i n g ，s i m i l a re x p r e s s i o ng e n e sc a nb ec l u s t e r e di n t ot h es a m eg r o u pt h a ti sh e l p f u lf o rb i o l o g i s t st of i n do u tg e n e t i cp a t h w a y s i ti sn e c e s s a r yt oa d o p tp m p e ra n a l y z i n ga l g o r i t h mt od e a lw i t hc o m p l e xg e n ee x p r e s s i o nd a t a i nt h i st h e s i s ，s e v e r a lr e p r e s e n t a t i v ec l u s t e r i n ga l g o r i t h m sa r ei n t r o d u c e ds u c ha sh i e r a r c h i c a la l g o r i t h m s ，s e l f - o r g a n i z i n gf c a t h e rc o m p e t i t i v en e t w o r k ，a n df u z z yc - m e a n sa l g o r i t h m ：i m p o r t a n tf o ra l lc l u s t e r i n gt e c h n i q u e si st h ed i s t a n c eo rs i m i l a r i t yu s e d i nt h i st h e s i s ，d i s t a n c em e 删e sc o n s i s tt h ee u c l i d e a nd i s t a n c ea n dc o r r e l a t i o n e a c ha p p l i e st on e a rd i s t r i b u t e da n dl i n e a rr e l a t e dd a t a a l lt h ea l g o r i t h m si m p l e m e mo ne x p r e s s i o nd a t ao f y e a s tg e n e s t h er e s u l to f f u z z ye - m e a n si st h eb e s to f a l l s m a l ld a t as e ti su s e di ne x p e r i m e n t sa n dt h ec l u s t e r i n ga l g o r i t h mc a np a r t i t i o nl i n e a rr e l a t e dd a t ae f f e c t i v e l y b u tr e l a t i o n s h i p so fg e n e sa r ec o m p l e xs u c ha sn o n l i n e a ro ri n d i r e c t ，f u r t h e rr e s e a r c hw o r ki nt h i sf i e l ds h o u l db ed o n e k e y w o r d s ：g e n ee x p r e s s i o nd a t a ，f u z z yc l u s t e r i n g ，b i o i n f o r m a t i c s ，d a t am i n i n g第一章序言1 1 研究背景第一章序言c d n a 微阵列技术是获取关于遗传变异或基因功能的高通量方法，一个显微玻片包括成百上千固定的d n a 点。通过这种技术可以获得基因在不同时段和实验条件下的大量表达值。但随着这种试验的不断进行产生了大量的数据，而h 彳；同试验设计所产生的结果也需要比较，所以急需采用精确有效的方法从这些数据中提取生物学的联系，给基因分派功能和揭示生物遗传方式。了解基因功能和生物遗传方式有助于我们理解正常与非正常条件下基因的功能机制。通过这些知识，可以预测特定条件下可能发生的疾病，从而做到增强疾病预防能力，改善诊断过程等。所有这些都能够有效的提高医护质量。对基因表达数据进行分析组织，通常会想到的方法是运用聚类算法把表达模式相似的基因进行分组，从聚类结果推断基因的特定功能和基因间的相互调控作用。1 2 研究内容分析微阵列数据，比较几种聚类算法在处理基因微阵列数据方面的性能，也就是产生聚类结果的好坏程度。为了评价其质量，使用已知类别的数据集，这样产生的聚类结果可以得到较客观的评价。本文比较以下的聚类算法：1 层次化聚类算法，根据所采用的不同连接方式可以分为：单连接，完全连接，平均连接，中点连结和w a r d 连接；2 k o h o n e n 自组织特征映射网络；3 模糊c 平均值算法；每个算法都可以用来做基因聚类分析( 例如基因在某些条件下的遗传方式)或者特征标签聚类分析( 例如对试验抽样进行分类) 。第一章序言1 3 论文的结构第二章简介微阵列技术和基因表达数据，第三章解释所用算法和应用背景第四章是算法的实现，第五章是实验目标和结果分析，第六章是结束语。第二章微阵列技术与基因表达数据第二章微阵列技术与基因表达数据2 1 微阵列技术要度量基因表达数据，应该完成一系列要求。首先，能够探澳蛭u 基因的所有一般特征；其次，用少量的生物材料，就可以较高精度的在核酸级别发现基因间的特征差异；最后要求有较快的反应速度。微阵列技术可以说是一个令人兴奋的技术，这种技术可以大规模的并行扫描整个的基因组，通过扫描所有由参考样本和待测样本相互作用而产生的d n a 斑点，可以得到待测样本的基因表达数据。现在描述一下微阵列技术是如何工作的。用红色荧光标记参考样本，绿色荧光标记测试样本。当两种样本的材料被混合在一个点时，就捕捉该处的荧光。通过荧光的颜色可以看出其中的哪一个有较高的表达：如果颜色是红的，那么参照样本有更高的表达，如果是黄色，两神表达相接近，如果颜色是绿的，那么测试样本有较高的表达。在颜色和亮度这两个指标中，我们更关心颜色的值。颜色可以取从纯红到纯绿的连续值。使用微阵列扫描器，这些颜色可以被量化并自动存储为正负实数，就是下一部分要用到的表达矩阵中以的值。d n a 微阵列技术使生物学家能够在一次试验中通过测量显示的荧光颜色来度量成千条基因的表达值。这些值可以用来标明测试样本和参考样本的相对表达值，对其进_行标准化，可以通过减去平均值然后除以标准协方差，作为数学聚类过程的输入。2 2 基因表达数据基因的表达是通过合成不同的蛋白质实现的。时间、环境等因素都对基因的表达有影响。用微阵列技术可以同时处理成百上千条基因，所得到的数据也就是这些基因在一定实验条件下一段时间内的表达情况。把这些表达量化成实数就产生的微阵列数据也就是基因表达数据，在本文中两者表达的是一个概念。第二章徽阵列技术与基因表达数据基因表达分子生物学中心法则微阵列数据可以被表示成以下的表：s 1s 2一s mg ira l l8 1 2 a l t o9 2i 锄1 ；：i i ：蜘| 口n 1 - - m制过程蛋白质其中i = 1 ，一，= 1 ，。，m ，其中表示表达值，行g ，表示基因列置表示所考虑的样本条件。从表中可以看到，基因和样本被考虑成门m 的实数向量( 表示表达的相对量和荧光的颜色) 。2 3 聚类技术的应用微阵列分析能够检测不同条件下的基因转录变化，能够显示反映特征组织类型、发育阶段、环境条件应答、遗传改变的基因谱。当芯片数据大量出现，产乍了新的问题：如果将所有获得的数据集中起来我们能否将未知功能f 内新錾因归类到已知功能分类中? 能否将基因表达与基因功能联系起来? 能否发现新类型的共调控基因? 能否从芯片表达数据中得出完整的基因调控网络? 这些唯有通过计算的方法。基因制图及测序所面临的问题与大规模基因表达分析的数学问题相比要小的多。这种新类型的表达数据使我们直接面对生物系统和基因组水平功能的复杂性，从生物系统单个成分的定性发展到完整生物系统行为的4第二章微阵列技术与基因表达致据描述上来，这方面困难很多，目前只有很少的分析工具。选择分析方法的基本标准：能够简化原始数据，结果直观，使研究者能在海量基因表达数据中解析出正确的基因表达谱和功能信息。一个理想的分析方法是建立在合理的算法基础之上的，应该能全面综合并直观地解析原始数据，修正已有数据，并从结构、序列、功能之间找到新联系。目前已有报道用于微阵列数据分析的方法主要是聚类分析：聚类分析聚类通过把目标数据放入少数相对同源的组或“类”( c l u s t e r ) 里。分析表达数据，( 1 ) 通过一系列的检测将待测的一组基因的变异标准化，然后成对比较线性协方差。( 2 ) 通过把用最紧密关联基因进行样本聚类，例如用简单的层次聚类( h i e r a r c h i c a lc l u s t e r i n g ) 方法。这种聚类亦可扩展到每个实验样本，利用一组慕因总的线性相关进行聚类。( 3 ) 多维等级分析( m u l t i d i m e n s i o n a ls c a l i n ga n a l y s i s m d s ) 是一种在二维e u c l i d e a n “距离”中显示实验样本相关的大约程度。( 4 ) k m e a n s 方法聚类，通过重复再分配类成员来使“类”内分散度最小化的方法。聚类方法有两个显著的局限：首先，要聚类结果要明确就需分离度很好( w e l l ，s e p a r a t e d ) 的数据。几乎所有现存的算法都是从互相区别的不重叠的类数据中产生同样的聚类。但是，如果类是扩散且互相渗透，那么每种算法的的结果将有所不同。结果，每种算法界定的边界不清，每种聚类算法得到各自的最适结果，每个数据部分将产生单一的信息。为解释因不同算法使同样数据产生不同结果，必须注意算法采用的不同的方式。对遗传学家来说，正确解释来自某一算法的聚类试验的结果是困难的( 特别是边晃) 。较为客观地解释源于经验和专业领域的知识，同时通过序列比较来指导。第二个局限由线性相关产生。上述的所有聚类方法分析的仅是简单的一对一的关系。因为只是成对的线性比较，可以减少发现表达类型关系的计算量，但忽视了生物系统多因素和非线性的特点。第三章几种典型聚类算法的分析第三章几种典型聚类算法的分析3 1 数学背景知识在聚类过程中一个重要的问题是选择什么距离或相似度作为标准。很明显，聚类结果的质量主要依赖于估计个体元素间相似度和差异的测度。所以并不是所有的聚类方法可以使用所有的聚类测度。每个具体算法都有相应的距离或相似度的描述。3 1 1 距离和范数下面是距离和范数的数学定义：距离v 是一组对象的集合，函数d ：v x v 哼i 在集合y 中定义了其中任意两个元素p 和g 到实数集的某种函数关系为d ( p ，q ) 。当满足以下4 条规则时，函数d被称为距离或几何距离：d ( p ，q ) o ，印，q y ；d ( p ，口) = 0 p = g ；d ( p ，g ) = d ( q ，p ) ，v p ，q 矿；d ( p ，q ) + d ( g ，) d ( p ，) ，v p ，q ，v 以上规则表明距离永远不会为负，对象和自己之间的距离为零，两个不同对象之间的距离大于零，距离测度是对称的。最后一个属性被称为三角不等性，就是说通过第三点的两点距离不小于两点的直接距离。范数范数常被定义在一个向量空间中。满足以下限制的集合v 被称为一个向量空间：1 如果甜和v 是v 中的元素，那么“+ v 也是y 中的元素，满足：6第三章几种典型聚类算法的分析“+ v = v + “，v u ，v v ；“+ + w ) = 0 + v ) + w ，v u ，v ，w y ；y 中存在一个表示o 的元素，就是v + 0 = v ，v v 矿；v v v ，j 元素一v ，有v + ( 一v ) = o 2 如果a j ，v e v ，那么2 v 是v 中的元素，满足：a ( “+ v ) = ；t u + 丑v ， x 2 j ， x u ，v e 矿；丑+ ( v ) = a + a , v ，v 五，p j ，v v y ；丑( ) = ( 缸) v ，姒，i ，v v e 耽v 中存在表示1 的元素v ，有1 v = v ，v v v 向量空间矿上的范数常表示为| | | | ，并且是从y 到i 的一个函数l i d o ，v v y ；l i v l l = o 营v = o ；l l 旯v i l = l a l l l v l l ，v a i ，v y ；f u l l + l l v i i l l u + v l l ，v u ，v 矿；向量的范数可以被解释成为向量的长度。范数的概念和距离是紧密相关的。范数的概念限于向量空间，每个范数l j j j 在向量空间y 定义了函数d ，如下：d ( u ，v ) - - i l u - v l l ，v u ，vev 欧拉距离最常用的是一种2 维范数。有如下定义，向量v = ( v 1 ，v 2 ，k ) l ”i ：= 砰+ 嵋+ + e另一个常用的范数是一维范数：删。= h + h + t + 川。第三种范数是最大范数，或无穷范数：。= m a x v i ，v 2 ，) 以上所有范数构成了p 维范数集，1 p 0 0 ：州i 。= ( v f + 噬+ + 嵋) 形3 1 2 相似度在某些情况下，相似或不相似的测度比距离测度更适用。比如要发现变化第三章几种典型聚类算法的分析模式一致的向量，那么讨论向量之间的相关性比只考虑距离的远近程度更有意义。这是由采用算法的目的和所处理数据的特性决定的。另外一个原因是，相似度比距离测度限制性更为宽松。比如，相似度测度具有正值和负值以适应不同聚类的要求，而距离则不具备这种特性。一个常用的相似度测度是相关系数。在相关系数这部分主要是从数学角度进行分析的。要通过公式计算得到相关系数，首先要计算协方差。两个随机变量间的协方差或者c o v ( - x ，y ) ，定义如下：d j r = c o v ( x ，y ) = e 【( x - p ) ( y - p r ) 1其中u 表示随机变量的平均值。为了计算g ( x - u d ( r 一所) ，( 其中e 代表期望值) 公式可以简化成g ( x - a 。) ( y 一所) 】- e x y 一以所。x 和y 之间的相关系数p 或者c o r r ( x ，y ) 被定义为：p = 肋= c o 吣姐【哔) 学】，其中“是变量的平均值，盯是变量的标准方差。如果利用协方蓑计算相关系数，公式可以被简化为：p ：c o y ( x , y ) ，( 3 1 )6 x o y通过对随机变量的向量进行处理可以构成对应的协方差矩阵和相关系数矩阵。其公式化的定义分别为3 2 和3 3 。在相关矩阵的公式中，酽表示变量i 的标准协方差的平方。c o y ( x ) =q 一吧。m吒2( 3 2 )klol蠢o 砰m 第三章几种典型聚类算法的分析c o r r ( x ) =12岛l1mmp n ip n 2n p 2 。ml( 3 3 )这两个矩阵是对称的，i 和j 的协方差和相关系数等同于j 和i 的。任何元素和它自己的相关系数都是1 。这就是对于对角线上的元素，其分子和分母是相同的( 砰= q + c r , ) 。相关系数是协方差的一种标准化的形式。事实上，元素和它自己的相关系数是1 ，这表示一种最大线性相关性。相关系数的范围是1 到+ 1 。确切地说这也是使用相关度作为相似性测度的原因。对于相关系数的取值，具有以下含义：0 表示线性不相关，1 表示最大负相关而1 表示最大正相关。其它的取值则在 1 ，+ 1 】这个区间之中。对于协方差来说，很难断定值的大小，它的值域和每个向量的值域相关。3 2层次方法3 2 1 过程描述层次聚类的技术可以分成汇聚的和分裂式的方法。汇聚的方法是通过不断的类间聚合分裂的方法则是通过连续的类间划分。当然，问题的困难性在于所考虑的问题到底有多少类。层次划分可以用家族树和反转树的结构表示每个分析阶段所j m 生的聚合成分裂结果。算法是从距离或相似度的定义丌始进行的，首先计算出来元素间距离或相似度的矩阵，它们是符合在3 1 节所提到测度的数学定义。在本文中层次聚类所使用的是相关系数矩阵。每个阶段，把最相近或撤舯l 似晌个体聚介。木文所考虑n 勺聚仓式层次划分筲法竹以下儿种类1 】的连接方式：1 近邻或单连接算法；2 远邻或完全连接算法；3 平均连接算法；9第三章几种典型聚类算法的分析4 中心点连接算法：5 w a r d 算法。总结如下，其中弓，= n ，n 一1 ，c 表示数据的分区，q ，= 1 ，2 一c 是类，n 是所要聚类对象的个数，q ，= 1 ，n 是对象本身( 2 2 节中的行列) ，c是聚类的个数，k 是要的重复次数：初始化r = ( c i ，c 2 ，c ) ；q = q ) j = 1 ，2 ，；k = 1 ：当前的步骤w h i l eks n cd os e l e c tc i ，c ，晶m l 符合以下规则c n + k = c 。u c | ；晶一t = ( r m lu c n + ) ) 、 c f ，q ；k = t + 1 ：e n dw h i l e算法有局部性的特点，以前的步骤无需进行记忆；通过当前状态的信息就可决定先聚合哪个类。在这里，要被更新的相似度嚷u ( 任意类q 和聚合的类g u c ，之间)定义为如下公式：d k ，l u = 呸如+ g j d j k + 办+ 占1 如一嗽1 ，( 3 4 )其中矗表示聚类i 和聚类j 之间的相似度，那么每次被各种方法聚合的类是那些对应相似度最小更新的或者相似度最大更新的。当然，对于每种方法都要给瑾，口，和万指定特定的值。这些值在表3 1 中给出。表中符号lc l l 表示类别c f 的势( 元素个数) 。1 0第三章几种典型聚类算法的分析堂墅垒坐盥望!s h a g l el i n k a g e1 21 20- l ，2c o m p l e t e 轴妇嚣1 21 20l ，2表3 1 更新后公式中的系数3 2 2 特定算法的描述在这部分考虑的是对类间距离的定义，不同的层次化技术都要使用距离这个概念。在公式3 4 中所用的参数解释了要先聚合哪两个类。从本质上解释了这些算法。为了能够度量类间元素的距离( 或相似性) ，就需要定义个体之间的距离( 或相似度) 。本节主要讲距离和相似度的问题。实现中，使用相关矩阵来描述元素间的距离。为了具有可读性，在下一节中使用的“距离”表明( 严格的) 距离或不相似度。单连接在单连接算法中，类的聚合是基于两个类中相距最近的两个元素之间的距离。首先聚合的类是相互间有最小距离的类。从规模为1 的类开始，随着每次聚合类的个数都递减。全连接全连接算法使用的是最远元素之间的距离来决定哪两个类最靠近，应该首先被聚合。平均连接两个类之间的距离被定义为它们每个元素之间的平均距离。中心点方法在中心点方法中，类被认为是存在于欧式空间中，在聚类过程中，类被其中点或中心所代替。一个类的中心是类中所有元素的平均向量。这些中心点的 睁轫；川水i ：| 掉卅i i i i j 类之m 的距离。中点方法第三章几种典型聚类算法的分析中点聚类分析去除了中心点方法的明显缺陷：如果任意两个组它们的大小相差很多，新类的中心点和原来规模较大类的中心点很接近而且仍在大类其中。小类的属性就会丢失。采用的策略是假定要进行聚合的类是大小相等的而不考虑类的实际大小。w a r d 方法这种方法所采用的思想是如果要聚合两个类，其结果所损失的信息可以被度量出来。这是通过计算每个点和所属聚类中t h , 点的方差平方和( t o t a ls h t l lo fs q u a r e dd e v i a t i o n st s s ) 来实现。类的聚合结果中t s s 增长最小的被再次聚合。在图3 1 中两个类问的距离以图形化的方式表示出来。i ai i cd图3 1 ：两个类之间距离的图形化表示：a 单连接算法，b 完全连接算法，c 平均连接算法，d 中心点和中点方法。对于c 要计算所有线距离的平均值。对于d 的不同之处在于中心点位置的计算。第三章几种典型聚类算法的分析3 2 3 优点和缺点以上提到的层次化算法有如下的优点和不足。优点包括：运行机制易于理解，类间融合所要遵循的标准比较清晰；相对容易实现，特别是带有参数的公式( 公式3 4 )当然也有不足之处：局部决策不可回溯( 如果在稍后的阶段要评价决镣) ；对聚类的形态有一定的假设，比如假想为圆形或椭圆的类：类的个数必须作为输入量或者随后应该被估计，比如在聚类过程中要产生一些评价标准的图形。基于此图可以从类的个数得到结论。这些方法主要应用于具有明显层次结构系统( 如进化树) ，可能并不适用于所有的数据集。最后，一些层次化聚类算法( 如单连接和中点方法) 有“链”式效应。就是说算法要把所有的类通过中点的链连接在一起。为了避免这种情况的发生，边界点应该被剔除。3 3 自组织竞争网络算法3 3 1 神经网络的简介感知器这部分是对神经网络的最一般化描述。最基本的神经网络包含一个神经元称为感知器。图3 2 是感知器结构的一个例子。从图中可以看到，每个输入值置，= 1 ，雅和其自身的权重h ，= l ，n 相乘。矗。蔓三兰些苎壅型壅茎墨鎏塑坌塑1上e图3 2 ：感知器结构然后把所有的乘积求和，再加上一个偏移量0 ，这个0 是通过另外一个途径输入，输入值恒定为1 ，权重为0 。然后将转移函数f 作用于这个值。输出值等与转移函数对特定输入作用所产生的结果。这个输出可以作为其他神经元的输入，见图3 3 。这是一个有两个输入神经元和一个输出神经元系统的例子。图3 3 ：几个互联的感知器更一般的系统可以具有输入、隐含、和输出神经元。隐含神经元不接受从外界来的输入。这些神经元可以组织成层，这就意味着有一个输入层，一个或多个1 4第三章几种典型聚类算法的分析隐含层和一个输出层。自组织竞争网络自组织神经网络( s e l f - o r g a n i z i n gn n s ) 是无教师学习网络，模拟人类根据过去经验自动适应无法预测的环境变化。因为没有教师，这类网络通常利用竞争的原则进行网络的学习。在网络结构上，自组织竞争人工神经网络一般是由输入层和竞争层构成的两层网络。网络没有隐含层，两层之间各神经元实现双向连接，有时竞争层各神经元之间还存在横向连接。在学习算法上，模拟生物神经系统依靠神经元之间的兴奋、协调与抑制、竞争的作用进行信息处理的动力学原理，指导网络学习和工作。其基本思想是：网络竞争层各神经元竞争对输入模式的响应机会，最后仅有一个神经元成为竞争的胜者，并对那些与获胜神经元有关的各连接全朝着更有利于它竞争的方向调整，这样获胜神经元就表示对输入模式的分类。当然，除了竞争方法外，还有通过抑制手段获胜的方法，即网络竞争层各神经元都能抑制所有其它神经元对输入模式的响应机会，从而使自己成为获胜者。经过训练所形成的网络结构，最终是由输入决定的。事实上，每个神经元的权重都和某一种输入模式越来越相似。网络的结构可以在图形上表示，神经元的相互位置形成了拓扑图形，相近的元素总是对应着相似的输入。网络可以有不同的图形结构：节点可以线性排列，以矩形或六边形或其他图形表示。对每个节点_ ，的使用一个近邻函数，划分出以j 为中心的邻域。这样的邻域包括了和节点，处于特定距离的所有节点。出于j 邻域的节点也会学习识别原始节点所识别出的输入向量。图3 4 邻域的例子。第三章几种典型聚类算法的分析图3 4 ：近邻的例子：a 半径为l 的圆形的近邻；b 半径为2 的圆形c 矩形；d 六边形。3 3 2 自组织特征映射的算法自组织特征映射算法是一种无教师示教的聚类方法，它能将任意输入模式在输出层映射成一维或二维离散图形，并保持其拓扑结构不变。也就是在无教j | i | i 卅教的情况f ，通过对输入的自组织学习，在竞争层将分类结果表示_ n 来。此外，网络通过对输入模式的反复学习，可以是连接权矢量空问分布密度与输入模式的概率分布趋于一致，即连接权矢量空间分布能反映输入模式的统计特征。对于输入模式，神经网络的不同区域具有不同的相应特征。通常只有一个神经元或局部区域的神经元对输入有积极响应。输入模式x = x l ，x 2 ，k 】7 并行连接到网络的每一个神经元，而每个神经元对应一个权向量m ，它是网络的可第三章几种典型聚类算法的分析调参数。对于输入模式x ，每个神经元的权向量都和其进行比较，距离最近的权向量会自动调节直到与输入模式x 的某一个最大主分量的方向相重合为止。自组织特征映射的算法，具体过程如下。对于输入模式x ，首先确定中心神经元帆，满足0 z 一忱忙r n i n 刮置一m 盼。然后，对以帆为中心的周围神经元的权向量按下式进行调整。 t ( 七+ 1 ) = t ( | ) + 口( 七) 【r 一 t ( 七) 】，i e ：( )其中c 表示由为中心的周围神经元组成的邻域。在学习中，札( ) 的初始可以大一些，然后逐步缩小。学习系数a ( k ) 在初始时可取接近于1 0 的常数，然后逐渐变小，例如a ( k ) 可取为o 9 ( i 1 1 0 0 0 ) 。自组织特征映射网络的学习和工作规则：1 初始化。将网络的连接权( w ) 赋予【o ，1 区间内的随机值，i = 1 ，2 ，n ；j = 1 ，2 ，m 。确定学习速率坪的初始值：确定邻域初始值；确定学习次数。2 从输入层读入向量薯= ( 五，屯，) ( 2 2 节中的a u ，向量中的每一个值都作为一个输入) ；3 计算输入x 和每个输出节点_ ，之间的距离，使用如下公式一l嘭= 置( f ) 一嘞) ) 2 ，其中 是节点i 在t 时刻的输入值，) 是在t 时忡o刻从输入节点i 到输出节点j 的权重：4 输出具有最小噍= m i n 【嘭 - - 1 ，2 ，m 的节点j ；5 更新节点，的权重和所有由邻域内节点的权重，依照如下公式：p + 1 ) = ( f ) + ，7 ( f ) ( ( f ) 一( ，) ) ，0 i n 一1 ，其中叩是学习率( 0 可( f ) - 2 1 结束。_ _ h 、i|、? ，一_一p 一一_|一i图3 5 ：通过随机输入训练的二维网络。矩形表示输入的范围，是第一个输入的权重，是每个节点第二次输入的权重。优点和不足自组织特征映射网络可以产生更为结构化的初始中心( 也就是权重矢量矩阵) ，把聚类结果在空间体现。同时可能会产生的问题和解决方案：有神经元造成了网络中的扭转。这可以通过改变训练是近邻的规模来避免。由于紧邻的规模随着学习和训练的过程在递减，图中的扭转就不太可能发生了。在训练过程中，开始学习的慢或者最后不稳定的学习状态。不稳定的学习意味着网络始终在几个状态间交替变换。这种情况可以通过降低整个学习过程中的学习速率来避免，速率开始的时候z l 处理的最后阶段“0 。这就保证了较快的初始学习速度同时具有稳定的结果。通过在两个方式运行算法可以产生同样的结果：第一种调整方式是使用大的学习速率，第二种调第三章几种典型聚类算法的分析节方式是使用较小的学习速率。另一种提高算法学习速度的方法是相对于紧邻其他的神经元给胜出的神经元更大的学习速率。为了算法能够正常工作，向量要标准化或者标明其值域。3 4 模糊c 平均值算法和其背景3 4 1 模糊平均值逻辑模糊集基础我们利用模糊数据，模糊规则和不精确的信息，正如利用统计信息一样。统计信息处理的是概率，模糊模型处理的是一种可能性，而并不是概率意义的不精确。模糊集是对普通集合( 清晰集) 的扩充。每个集合s 是由其成员函数从刻画的，定义在全域x 的所有元素，如果换成清晰集那么其函数值只能用0或1 来表示是不是属于该集合的成员。模糊集具有类型更为一般的成员函数。有必要的话，成员函数得知可以取 0 ，1 】之间的任何值。这个值称为特定元素的隶属度。比如考虑一个普通男性的身高，具有“矮小”、“中等”“高大”这些特性描述。那么其成员函数b ，辱会如图3 6 所示。017 0 m1 8 0 m1 9 0 m图3 6 ：模糊集合s ，m 和t 的成员函数使用模糊逻辑有许多优点。首先模糊逻辑考虑到数据中的噪音所以它提取的是趋势而不是精确的数值。其次模糊逻辑算法和我们平时思考和谈论问题的1 9第三章几种典型聚类算法的分析方式相似( 比如我们常用“许多”，“有时候”，“很多”等词汇) 。最后模糊逻辑所采川阳实现方法是可以有效计算的，也是可以微划分成许多模块米实现的。为了能够用模糊集执行有意义的运算，需要定义一些常用的集合操作符。对于它们中的一些，在下一个总论中有对于在同一个论域上的两个子集a 和b的一个定义：相等性：a = b 营胁( x ) = ( x ) ，y x x相容性：a c b 铮心( x ) ( x ) f i x e x互补性：爿= b 甘胁( x ) = 1 - 熊( 如v x e x交运算：a n b 曹鳓m ( x ) = m i n u a ( x ) ，玩( x ) ，坛e x并运算：a w b 营u a 。口( x ) = m a x u a ( x ) ，鳓( x ) ) ，v x x值得注意的是对于一个模糊集n 可能会出现n n o 和u n x 。这就是说模糊集和它的补集相交不必为空，并集不必是全集x 。模糊集和概率论的区别隶属度和概率之间有一些重要的概念区别。考虑元素x 在模糊集“高度”中具有隶属度为o 7 。这就是说这个元素不是特别高，但是当然也不矮，但还是够高的。相对于一个具有高度概率为o 7 的元素来说，这就意味着这个元素是高的可能性为0 7 ，但实际上该元素具有很小的概率是很矮的。另一种区别是对结果的解释：可能性表示的是一个元素的真值，无论我们获得了什么信息，这个值都保持不变，但是一个元素的概率表明，尽管事实上一个元素是或不是高的但是我们没有足够的信息去断定它到底属于哪一个。我们只有知道足够多的信息才能总结出一个元素有更多可能是属于高的但是当获得更多的信息后，比如对高度1 0 0 的测度，元素是高的概率就是1 ( 或者o ) 。使用模糊逻辑进行聚类分析一般的c 平均值算法试图最小化目标函数，就是从所有点到类中心点距离平方的和( 这是在清晰集中) 。算法受c 值选择的影响，聚类初始中心的估计，对样本次序地考虑，数据的距离测度和几何属性。大多数聚类技术假定任意元素可以只属于一个类。模糊聚类技术允许元素拥有对一组类中的任何一个的部分或分布式的成员特性。对于模糊子集的数学定义和对模糊划分的正规描述如2 0第三章几种典型聚类算法的分析f ：对于整数c ，1 c n 同时x = “，屯， ，在j 空间中n 个向量的矩阵，如果( = t , l i ( x k ) ，i 蔓k ，z ，1 i c 满足以下的两个条件：1 0 “m 1 ，v i ，| 】 ；2 ：= 1 ，v 七；那么c 模糊子集 q ：x _ o ，1 】 是一个模糊c 划分。由g * r l 维的矩阵u = 所组成的集合m 。是一个模糊c 划分集，其中满足以上条件。当u 中所有u 。只取0 或1 时，便得到了一个去掉非模糊化的普通c 划分所组成的集合 屯。对于聚类应用的两个重要问题：组间的相似度或距离；m 。中评价最优聚类的标准。需要哪一个m 。由c 值的选择来决定的。运用模糊聚类中隶属度的主要一个好处是表明要注意哪些对象，在一般的硬划分中每个对象都被分派到一个类中，而模糊聚类可以在若干个类中选择那些具有更高隶属值的对象。可以通过对第二条限制的放宽得到对模糊平均值划分的扩充，也就是每个对象所有类中隶属度之和是一个常数，可以大于1 。这样任何元素都可以得到一个比1 大的成员值( 有助于类间求和) 。可以这样做是因为我们所考虑的是隶属度而不是概率。这样做对于处理边界点和错误划分问题有较好的效果。在解决实际问题i i i ，采用模糊划分更符合所处珊限题的本质，i f i 朋原则上可以获得更好的纳采。3 4 2 模糊平均值算法模糊平均值算法的原则是基于最小化目标函数以( u ，矿) ，涉及到隶属度矩阵u ，进行模糊c 划分的数据集x ，还有v ( 临时的聚类中心) ：c( u ，矿) = ( ) 9 d 2 ( ，k ) ，csn ，j - l1 - 1其中q 是比1 大的实数，x ，是第j 个对象( 或者是2 2 节中r 句i t a 。的第i 行的向量) ，巧是类i 的中心，是在类f 中的隶属度，d 2 ( ，k ) 是求两个向2 l第三章几种典型聚类算法的分析量间的距离( 置和巧间的距离) ，n 是数据点的个数，c 是类的个数。参数q 是的指数权重，起作用是控制聚类结果的模糊度。q 值越高，那么有些元素的隶属值会越少的影响目标函数。在修改聚类中心和成员函数时隶属度小的点对修改结果影响也越小。q 值越高，则划分的模糊性则越大。当q 值为零时也就退化为通常的硬聚类，如k m e a n s 等。模糊划分的实现是通过对于对象的反复最优化实现的，遵循以下步骤：1 择中心点m ( 原型) ：2 每个对织隶j | l l ；度的计算方法而高】l 怕。2 。1 一；。o 而蒜一3 新中心点y 的方法：脊，根据c 2 ，更新从到如的隶属度：4 如果最大的 i 一如| 】 占，那么就停止，否则的话就跳转到( 3 ) ，其中占是介于0 到1 之间的终止值。计算的隶属值依赖于所采用的距离测度，d 2 ( 一， ( ) = ( 巧一k 厂么( 一) 。根据统计属性，在距离测度中矩阵a ( m m 的正定矩阵) 可以调节距离权重。如果为了a 选择了n a * m 的恒等矩阵i ，那么就使用欧拉距离和模糊c 平均值算法。对于超椭圆聚类，类中密度可变和每个类中数据点的数量各不相同的情况下，就可以由上式定义一个基于极大似然估计的指数距离测度d 2 ( 一，巧) 。第四章算法的实现4 1 算法的实现第四章算法的实现所有实验都是在m a t l a b 开发环境下完成的，m a t l a b 是美国m a t h w o r k s 公司1 9 8 4 年推向市场的国际公认最优秀的科技应用第四代程序开发软件。层次聚类的实现层次聚类的算法模块设计成函数h i e r c l u s ( m e t h o d ，d s e t ，d i m ，n o f c l u s t e r s ) ，其中参数m e t h o d 是聚类距离计算的方式，d s e t 是输入的表达数据矩阵，d i m 是标示针对基因还是针对实验进行聚类，n o f c l u s t e r s 是指定要产生的聚类个数。程序框图如下( 图4 1 1 ) ：隰4 1 1层次聚类的算法实现流程图第四章算法的实现自组织特征映射网络的算法实现网络结构：输入层：8 7 * 7 7 表达矩阵；输出层：1 + 6 神经元；学习规则：k 9 + 1 ) = o ) + 刁( f ) ( ( f ) 一( f ) ) ，t 是学习次数分别设为5 0 0 和1 0 0 0 次，学习速率初始值为0 9 ，r l ( t ) = 0 9 ( 1 一t c r ) ；权向量的初始值根据输入矢量的值域设定：图4 1 2自组织特征映射网络的结构图模糊平均值聚类的算法实现：nc目标函数：( u ，矿) = ( ) 9 d 2 ( 一，巧) ，c n ，中心点和隶属度的更新公式在3 4 2 节都有介绍图4 ，1 3 模糊平均值划分的流程图2 4第五章实验分析第五章实验分析5 1 实验目标和数据集通过对基因组在相互独立实验条件下的表达数据进行聚类分析，按照相同时间段c d n a 表达峰值模式相近或者一致的标准，将这些调控基因聚集成不同的组。组内基因的表达模式相对组间更为接近。表达模式相近的基因其发挥的调控作用一般是一致的，因此聚类技术有助于发现未知的调控基因。酵母基因组是真核生物基因组中研究得最为详尽的基因组之一。实验中所用的数据是六千多条在酵母细胞有丝分裂过程中起调控作用的基因。d n a 复制是细胞增值的一个关键事件，和细胞分裂是相互协调、相互调控的。原核细胞d n a 复制完成后就发生有丝分裂，而真核细胞中d n a 的复制只发生在细胞周期中特定时期，细胞周期合成期s 期。通常一个细胞周期内，d n a 必须也只能复制一次。细胞周期由s g 2 m 0 1 四期，各期转变均受某些基因的调节。也就是说这六千多条基因分属于细胞分裂不同阶段的功能基因。5 1 1 所使用的数据从斯坦福大学分子生物系的网站上可以免费获得6 1 6 5 条酵母基因片段( 见图5 1 ) 在三个独立试验条件( c l n ，a l p h a ，e l u t r i a t i o n ) 下的表达数据。h t t p ：h 1 7 1 6 5 7 6 4 9 c e l l c y c l e d a t a r a w d a t a 第五章实验分析图5 16 1 6 5 条酵母基因在三个独立试验下的表达数据为了比较以上三种算法的实验效果，从中选取了一个比较小的数据集作为第五章实验分析实验数据，这个数据集由8 7 条基因组成，每个基因所属调控时期是已知的。按照顺序编号可以将8 7 个基因分为六组( 图5 2 ) ：第一组：1 1 1 号：( m g 1 边界期)第二组：1 2 2 4 号；( s c b 调控的g l 后期)第三组：2 5 5 8 号；( m c b 调控的g 1 后期)第四组：5 9 6 6 号：( s 期)第五组：6 7 7 2 号；( s g 2 期)第六组；7 3 8 7 号。( g 2 m 期)由于已知这些基因分别属于那个细胞循环周期，所以可以对每个算法的处理结果进行评估。图5 2 ：8 7 条酵母基因，分属6 个细胞周期。5 2 实验结果实验采用的距离测度是欧式距离和相关系数：欧式距离主要是度量向量两两之间的空间几何距离，相关系数则是度量向量间两两之间的线性相关性。所第五章实验分析以采用不同的测度，所要衡量的对象特性是不同的。在使用欧式距离时，要产生一个l ( 8 7 ( 8 7 1 ) 2 ) 维的距离矩阵记录任意两个向量之间的距离。同样用相关系数作为测度时，也可以产生这样的一个矩阵。下图显示了它们各自的平面分布：基因两两