（计算机软件与理论专业论文）基因表达数据的聚类技术研究与应用.pdf

摘要 摘要 人类基因组计划的顺利完成标志着生命科学的研究进入了的后基因组时 代。科学家的研究重点转向了从大规模生物数据中发掘蕴含的结构和功能信息。 微阵列和基因芯片等技术的运用使得研究者可以同时观察成千上万条基因在某 个生命过程中的表达情况，从而将基因的活动状态比较完整地展现出来。基因 表达分析已经成为了生物信息学研究的一个重要方向。 聚类技术将数据集根据相应特征聚成不同的类，同一类中的数据比其他类 中的数据更相近。基因表达数据的聚类分析是目前生物信息学中重要的研究内 容。具有相似表达特征的基因能够被聚到一起，表示具有相近的细胞功能。与 此同时，同一类中相互表达的基因更有可能包含在同一个细胞过程中，这些基 因的表达特征的相关性预示着它们之间的互相关。 本文研究基因表达数据分析中的聚类技术，着重研究了结合基因表达数据 特征和k c a n s 聚类算法特点的改进算法，实验结果显示比传统k m e a n s 的方法 要好。本文还研究了聚类结果的验证方法a r i ，以及从基于基因的聚类结果挖掘 基因间相关性的方法。另外，本文介绍了开发的基因表达数据分析系统 g e n e m i n e r 的设计与开发。 关键字生物信息基因芯片基因表达数据聚类关联规则 a b s 廿a c t a b s t r a c t w i t ht h ea c c o m p l i s h m e n to fh u m a ng e n o m ep r o j e c t ，t h eb i o l o g i c a lr e s e a r c h c o m e st ot h en e wp o s t g e n o m ee r a s c i e n t i s t sn o wf o c u so ne x p l o r i n gg e n o m e s t r u c t u r e sa n df u n c t i o n sf r o mb i o l o g i c a ld a t a d n am i c r o a r r a yt e c h n o l o g yh a sn o w m a d ei tp o s s i b l et os i m u l t a n e o u s l ym o n i t o rt h ee x p r e s s i o nl e v e l so ft h o u s a n d so f g e n e sd u r i n gb i o l o g i c a lp r o c e s s e s t h et e c h n o l o g yb r o u g h tan e wl i g h tt ot h el i f e s c i e n c er e s e a r c ha n dg e n ee x p r e s s i o na n a l y s i sh a sb e c o m eav e r yi m p o r t a n tb r a n c ho f b i o i n f o r m a t i t sr e s e a r c h c l u s t e rt e c h n o l o g ys e e k st op a r t i t i o nag i v e nd a t as e ti n t og r o u p sb a s e do n s p e c i f i e df e a t u r e ss ot h a tt h ed a t ap o i n t si nt h es a m ec l u s t e ra r em o r es i m i l a rt oe a c h o t h e rt h a nt h ep o i n t si nd i f f e r e n tc l u s t e r s c l u s t e r i n ga n a l y s i so ng e n ee x p r e s s i o nd a t a i sak i n do fi m p o r t a n tr e s e a r c hi nb i o i n f o r m a t i c sn o w g e n e sw i t hs i m i l a re x p r e s s i o n p a t t e r n sc a nb ec l u s t e r e dt o g e t h e rw i t hs i m i l a rc e l l u l a rf u n c t i o n s c o e x p r e s s e dg e n e s i nt h es a m ec l u s t e ra r el i k e l yt ob ei n v o l v e di nt h es a m ec e l l u l a rp r o c e s s ，a n das t r o n g c o r r e l a t i o no fe x p r e s s i o np a t t e r n sb e t w e e nt h o s eg e n e si n d i c a t e sc o r e g n i a t i o n t h i st h e s i sf o c u s e so nt h er e s e a r c ho nt h ec l u s t e r i n gt e c h n o l o g y 叩p l i e di n a n a l y z i n gg e n ee x p r e s s i o nd a t a c o n v e n t i o n a lk i v i e a n sa l g o r i t h mi sa d j u s t e db y c o n s i d e f i n gt h ec h a r a c t e r so fg e n ee x p r e s s i o nd a t aa n dt h es h o r t c o m i n g so fk i v e a n s a l g o r i t h m t h ee x p e r i m e n t ss h o wt h a tt h ea d a p t e da l g o r i t h m sp e r f o r mb e t t e rt h a nt h e t r a d i t i o n a lk m e a n sm e t h o d t h ec l u s t e r i n gv a l i d a t i o nm e t h o da r ii si n v e s t i g a t e d t o r e v e a lb i o l o g i c a l l yr e l e v a n ta s s o c i a t i o n sa m o n gg e n e si nt h es a m ec l u s t e r , i ti s p r o p o s e dt o u s ea s s o c i a t i o nr u l e st om i n et h e g e n e b a s e dc l u s t e r i n gr e s u l t s i n a d d i t i o n ，t h et h e s i si n t r o d u c e st h eg e n ee x p r e s s i o nd a t aa n a l y s i ss y s t e m g e n e m i o e r k e yw o r d sb i o i n f o r m a t i c s ，g e n e c h i p s ，g e n ee x p r e s s i o nd a t a , c l u s t e r i n g ， a s s o c i a t i o nr u l e s i l 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文：学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：圣毫寿 2 一j 年f 月2 2 日 经指导教师同意，本学位论文属于保密，在2 口c 坚i 年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 聂嘉看 解密时间：2 朋歹年 石 月 7 日 各密级的最长保密年限及书写格式规定如下： 内部5 年( 最长5 年，可少于5 年) 秘密 k l o 年( 晶长1 0 年，可少于l o 年) 机密- k 2 0 年( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 毫饼 诉堂月2 - 2e t 第一章引言 1 1 生物信息学 第一章引言 随着各种模式生物的基因组全序列的公布，以及科学家获取人类自身基因 组的绝大部分序列，人类基因组的研究全面进入信息提取和数据分析的崭新阶 段。科学家的研究重点转向了结构和功能研究的后基因组时代。人类基因组测 序以及结构和功能研究的广泛开展，产生了海量的生物数据；而且由于生物体 的结构和功能以及生命活动过程本身的多样性和复杂性、生物实验方法的独特 性导致生物学数据的复杂性。面对生物学数据在量( 海量) 与质( 复杂性) 方 面所提出的严峻挑战“1 ，生物信息学( b i o i n f o r m a t i c s ) 孕育而生。生物信息学包 含生物信息的获取、处理、贮存、分发、分析和解释，综合运用数学、计算机 科学和生物学的各种工具进行研究，以了解数据中的生物学意义“1 。 生物信息学的研究目标有两个，一是作为实验手段的辅助工具，为分子生 物学家提供各种分析软件：二是作为直接的分析工具，从已有的大量数据库中 提取信息，挖掘新的生物学知识，推延新的发现。它的最终研究目标是解读生 命的遗传密码。生物信息学的研究需要一些必要的基础，一是要建立各种数据 库，使得实验获得的数据能够被更加容易的存储、提取和分析，二是基于这些 数据开发各种算法，从数据中挖掘出新的有用信息，帮助生物学家得出许多新 的生物学知识和提出有价值的生物学问题，而且有些生物学问题必须通过生物 信息学的手段来实现。 最近兴起的微阵列( m i c r o a r r a y ) 和基因芯片技术，使人们可以同时观察上 万条基因在某个生命现象中的表达情况，从而将基因的活动状态比较完整地展 现出来，使得人们能够从基因组的整体水平上把握生命的某些特征，这无疑为 科学家进行大规模功能基因组分析提供了思路“1 。通过对全基因组范围内的基因 的表达进行分析，人们可以预测未知基因的功能，发现基因之间的调控关系。 基因表达分析已经成为了生物信息学研究的一个重要方向。 第一章引言 1 2 微阵列技术及基因表达数据 基因表达数据的主要来源是微阵列( m i c r o a n - a y ) 技术的运用。传统的基因 研究方法着重于对单一基因的小规模实验和数据收集。基因表达微阵列技术使 得生物学家能够在基因组层次上研究任何种类细胞相应时间和条件下的基因表 达模式。在这类微阵列中，一个微阵列是个小的芯片，从细胞或组织中提取 r n a 并反转录成带有放射性同位素或荧光标记的c d n a 。然后，c d n a 与由基 因片断组成的、固定在玻片或膜上的称为探针的e d n a 或寡核苷酸进行杂交。 最后，采用荧光或其他成像技术测定上千个基因在各种不同实验条件下的表达。 图1 1 为e d n a 微阵列芯片实验流程【2 j 。 图1 1e d n a 微阵列芯片实验流程 把一引 第一章引言 1 ) 基因表达数据是高通量的。人类全基因组的基因有十万条左右，简 单的真核生物酵母的全基因组基因有六千多条，为了能充分合理的 发现基因表达之间的关系，一般都需要同时观察整个基因组的表达 情况，这就意味着会有高维的表达矩阵。 2 ) 基因的表达量化较为粗糙，基因表达量是通过扫描杂交实验得到的 图像，分析颜色的深浅计算而得到的，目前这种定量工作主要是采 用参考基因对比定量。 3 ) 基因表达数据存在着较多的缺失和噪声。 目前，对基因表达数据的分析主要是在三个层次上进行： 1 ) 分析单个基因的表达水平，根据在不同实验条件下，基因表达水平 的变化，来判断它的功能，例如，可以根据表达差异的显著性来确 定肿瘤分型相关的特异基因。 2 ) 考虑基因组合，将基因分组，研究基因的共同功能、相互作用以及 协同调控等。 3 ) 尝试推断潜在的基因调控网络，从机理上解释观察到的基因表达数 据。 通过对基因表达数据矩阵的分析，可以帮助生物研究者回答一些生物学问 题，例如，基因的功能是什么? 在不同条件或不同细胞类型中，哪些基因的表 达存在差异? 在特定的条件下，哪些基因的表达发生了显著改变，这些基因受 到哪些基因的调节，或者控制哪些基因的表达? 哪些基因的表达是细胞状态特 异性的，根据它们的行为可以判断细胞的状态( 生存、增殖、分化、凋亡、癌 变或应激等) 等等。 1 3 基因表达数据分析中的聚类技术 聚类是指将数据集根据相应特征聚成不同的类，同一类中的数据比其他类 中的数据更相近。聚类方法在生物信息处理中有着直接的意义。对于d n 蛋白 质序列数据，相似的序列表明序列问可能存在同源性，从进化角度看它们可能 是有同一祖先进化而来；对于大分子结构数据，相似的结构代表可能存在相似 的分子功能，这在生物材料、药物设计等方面有直接的意义：对于基因表达数 据，相似的基因或基因片断代表相似的基因表达功能，这对于基因筛选、医学 3 第一章引言 中的分析病变原理都有重要的意义。 在上述三种数据分析中，聚类方法应用最多的是基因表达数据。在基因表 达数据的分析中，基因表达数据非常庞大，但生物学里已知信息的基因相对较 少，采用分类的有监督方法不合适，聚类是一种无监督学习，不需要先验知识， 能直接把具有相似表达性质的基因聚在一起。聚类技术能够很好的用于理解基 因功能、基因规则及细胞过程。具有相似表达特征的基因( 互表达基因c o e x p r e s s d g e n e s ) 能够被聚到一起，表示具有相似的细胞功能。因为生物中很多基因的功 能是未知的，聚类方法将有助于理解这些基因的功能。而且，同一类中相互表 达的基因更有可能包含在同一个细胞过程中，这些基因的表达特征的强相关性 显示出它们之间的互相关( c o r e g u l a t i o n ) 。通过聚类基因表达数据来推断基因间 的规则能够帮助生物研究人员推断考虑转录规则网络的机制【”。 基因表达数据中常用的聚类方法有k - m e a n s 算法【1 1 l 【1 2 】【1 3 】，层次聚类 ( h i e r a r c h i c a lc l u s t e r i n g ) 1 1 4 1 1 5 】，f c m l 6 】【堋，基于密度的聚类算法( d b s c a n a l g o r i t h m ) 【9 】【1 8 1 ，g m m 聚类算法1 1 9 l 。 1 4 本文的主要研究内容 本文研究基因表达数据分析中聚类技术，着重研究结合基因表达数据特征 和k i v l e a n s 聚类算法特点的改进算法。同时本文还将研究聚类结果的验证方法 a r i 以及从基于基因的聚类结果挖掘基因间相关性的方法。 此外，本文就基因表达数据分析系统g e n e m i n e r 的设计和开发、相关特点、 模块和功能进行介绍。 本文随后将在第二章介绍针对基因表达数据中包含噪声或奇异点的特点， 改进k m e a n s 方法来分析基因表达数据。第三章将介绍已知类别的基因指导聚类 挖掘的方法。第四章讲详细介绍聚类结果的验证方法a r i 和利用关联规则从基 于基因的聚类结果挖掘基因间相关性的方法。在第五章讲介绍基因表达数据分 析系统g e n e m i n e r 的功能、设计和实现。 4 第二章k c l e a n $ 聚类增强抗噪性的改进 第二章k m e a n s 聚类增强抗嗓性的改进 基因表达数据来源于大规模的杂交试验，在实验设计、杂交实验，到最后 的图像扫描、数据采集，这一系列过程的复杂性以及基因表达本身的特性使得 实际用于分析的基因表达数据不可避免的存在噪声或孤立数据。传统的k j v e a i l s 算法当结果簇是密集的，簇与簇之间的区别明显时，具有较好的效果和较高的 效率。但当数据集中存在“噪声”和奇异点时，e a s 算法是很敏感的，少量 的“噪声”和奇异点就会对聚类的结果产生较大的影响。因此，直接用k , j v i c a i l s 算法对基因表达数据进行聚类，结果聚类结果受到影响。本章将关注k j 、_ , e a n s 算法，针对基因表达数据中可能包含噪声或奇异点的特点，采用相应的改进算 法来分析基因表达数据，希望能够提高k m e a n s 算法的聚类正确率。 2 1k m e a n s 算法介绍 k m e a s 算法是基因表达数据分析中常用的一种基于划分的聚类方法，该算 法首先由m a c q u e n 提出【“】 1 2 】【1 3 。基于划分的算法描述为：对于一个已知的d 维空间口4 ，定义一个目标函数c ，作为对聚类结果的一个量化评价，输入1 3n 中 的数据集合x 以及要生成的类的数目r ，要求输出x 的一个划分 z 。 l ，满足使 目标函数c 最小化。 k “e a l l s 算法在指定类别数r 后，对样本数据集进行聚类，聚类的结果由k 个类中心以及每条数据的类的归属来表达。k m e a n s 算法常用的目标函数c 定义 为： c - 三三d u ( 2 ；) ( 2 1 ) 其中v 。表示类石的类中心，n ，表示类咒包含的数据条数，d i ( x i 川) 是数据x i x 与 类咒的类中心h 的距离测度，常采用的距离测度为e u c l i d e a n 距离： k e a n s 算法如下 酗州嘲，瓶焉 5 ( 2 2 ) 第二章k m e n s 聚类增强抗噪性的改进 2 2k m e a n s 聚类基因表达数据中增强抗噪性的改进方法 2 2 1 基于距离限制的i c m e a n s 改进方法 噪声对k 2 d e a n s 算法的影响表现为使类中心偏离实际的位置，因此在聚类过 程中，可以预先设置一个距离阈值，如果数据点和与其距离最近的类中心之间 的距离超过这个阈值，则将该数据点排除在外，并认为该数据点是噪声点。这 样在更新类中心的过程中可以将这些点排除在外，避免类中心受到相应的影响。 算法描述如下所示： 6 第二章k m e a n s 聚类增强抗噪性的改进 实验首先采用u c i 数据集i r i s 2 0 l 来验证上述两种方法。i r i s 数据集采用花瓣 和萼片的长宽来预测i r i s 植物的三个类别，共包含1 5 0 条数据，数据维数为4 ， 分为三个类别，每一类包含5 0 条数据，数据类别分布如表2 1 所示： 表2 1i r i s 数据类别分布 n m m 二黝 鞘i 、：，一+警i + ：jn ；誊臻。幽0 附描辱m ；。1j 黼。i 嬲 第1 类1 5 0 第2 类5 l 一1 0 0 第3 类l o l 一1 5 0 在i r i s 数据集中加入随机产生的l o 条噪声数据，如表2 2 所示 表2 2 噪声数据 潦j 雾纛；凝缫簇蓊蘩霉雅j4 篡，第誊维篓i i 繁霸，维 1 5 11 6 0 9 21 4 4 5 81 5 7 7 9一1 8 9 5 4 1 5 2一1 6 0 9 2一1 8 9 5 4 - 1 6 0 9 21 8 9 5 4 1 5 39 7 6 3 61 1 1 2- 1 8 2 7 31 2 4 3 6 1 5 41 1 6 4 61 63 5 4- 2 0 5 7 5 8 1 3 4 5 1 5 51 8 1 0 21 4 3 9 71 7 3 5 72 0 3 4 4 1 5 61 4 8 5 11 4 6 91 i 3 7 5 1 3 9 8 6 1 5 7- 1 6 5 3 91 3 8 8 81 4 8 5 l一1 4 6 9 1 5 8- 1 2 8 - 1 9 6 1 7一1 0 9 4 4- 1 5 7 0 9 1 5 9i 0 9 4 41 5 7 0 91 3 4 4 1 0 1 5 6 1 6 01 4 7 0 9 1 1 6 7 51 4 8 5 91 0 5 7 7 对这1 6 0 条数据构成实验数据集用基于距离限制的改进算法进行聚类，其 中距离阈值参数设置为7 ，聚类结果别出了这1 0 个噪声，其中1 5 0 条i r i s 数据 聚类结果如表2 3 所示： 表2 3 基于距离限制改进方法聚类i r i s 数据集实验结果 i 第1 类 5 0 l 一5 0 i 第2 类5 05 l _ 6 87 0 7 2 7 4 8 38 4 1 0 01 i i 1 3 91 4 2 第3 类 5 06 97 38 4i 0 1 1 1 01 1 2 一1 3 81 4 01 4 11 4 3 - 1 5 0 用传统的k m e a n s 算法分析这1 6 0 条基因表达数据，由于k l e a n s 算法不能 识别噪声数据，因此聚类结果正确率很低，结果如表2 4 所示： 7 第二章k m e a l l $ 聚类增强抗噪性的改进 表2 4k m e a f l s 算法聚类1 5 0 条数据实验结果 、；j 数据爨蒺：i ： 戮。一z 、搿耕五审茜t 撼。符融嚣 ：；捌n 皇吲 第l 类 5 11 5 09 9 第2 类 5 1 5 3 1 5 51 5 9 1 6 0 第3 类 1 0 45 1 9 81 0 0 - 1 5 21 5 6 1 5 8 下面将改进方法对真实的基因表达数据进行聚类分析。由于分析各种聚类 算法的实际效果需要己知功能的基因表达数据，因此本章采用的数据集是酵母 的基因组( 大约6 0 0 0 条基因) 在两个细胞周期上表达水平的波动，包括1 7 个 时相点，本章使用其中的一个子集，包括3 8 4 条基因，对应细胞周期的5 个阶 段，其表达水平达到峰值。经过预处理，从这3 8 4 条基因表达数据中抽取2 4 5 条基因表达数据构成所需实验数据集。这些都为已知类别的基因，这对聚类结 果的评价有直接意义；另外酵母是人类已经全部测出基因序列的真核生物之一， 对酵母数据的分析对未来人类基因的分析有尝试性的意义。 2 4 5 条基因表达数据的类别分布和示例表如表2 5 、2 6 所示。 表2 52 4 5 条基因表达数据类别分布 j 强嚣j i 蝗军吡。蠢1 1 1 1 。瓢i j 特掘 淼 一 第1 类 l 一4 9 第2 类5 0 1 5 7 第3 类 1 5 8 - 1 9 8 第4 类1 9 9 - 2 2 0 第5 类 2 2 1 - 2 4 5 表2 62 4 5 条基因表达数据示例表 g e n e i d s a m p l e ls a m p l e 2s a m p l e 3s a m p l e 4s a m p l e l 7 1- 0 7 5 8 10 9 0 3 2 0 9 8 舛 - 0 7 3 9 9 0 7 8 8 2 20 4 8 8 4 0 7 0 8 3 - 0 4 7 6 9- 0 6 5 8 10 8 2 2 8 采用基于距离限制的改进算法对这2 4 5 条基因表达数据进行聚类，聚类结 果如表2 7 所示，错3 6 条，正确率为8 5 3 ： 表2 7 基于距离限制改进方法聚类2 4 5 条基因表达数据实验结果 第一类 5 31 4 74 91 7 7 1 8 0 1 9 72 2 12 3 0 第二类 1 0 94 8 。5 0 1 5 7 第三类 4 01 5 8 1 7 61 7 8 1 7 91 8 l 一1 9 1 1 9 5 1 9 61 9 82 0 02 0 52 1 2 2 1 4 8 第二章k m e a n $ 聚类增强抗噪性的改进 续表2 7 基于距离限制改进方法聚类2 4 5 条基因表达数据实验结果 i第四类 3 91 9 92 0 1 2 0 42 0 6 2 1 l2 1 5 - 2 2 02 2 2 2 2 92 3 1 2 3 92 4 1 2 4 5 i第五类 41 9 2 - 1 9 42 4 0 改进方法标示出的可能的数据噪声点为4 9 、1 9 2 、1 9 4 、1 9 7 、2 0 0 、2 4 0 。 用传统的k m e a n s 算法对2 4 5 条数据进行聚类，聚类结果错3 7 个，聚类结 果如表2 8 所示： 表2 82 4 5 条基因表达数据k m e a n s 方法的聚类结果 第1 类 5 3 1 4 74 91 7 7 1 8 0 1 9 72 2 12 3 0 第2 类 1 0 94 8 ，5 0 - 1 5 7 第3 类 4 i1 5 8 1 7 61 7 8 1 7 91 8 l 一1 9 11 9 5 1 9 61 9 82 0 02 0 52 1 02 1 2 2 1 4 第4 类 3 81 9 92 0 1 2 0 42 0 6 2 0 92 1 12 1 5 2 2 02 2 2 2 2 92 3 l 一2 3 92 4 1 2 4 5 第5 类 41 9 2 1 9 42 4 0 改进方法比k l e a l l s 算法稍好，改进方法标示出的数据噪声点最终还需要通 过生物实验来验证。 实验用基于距离限制改进算法分析b l o c h 从【2 1 】中随机选取的数据集【矧，共 6 4 条酵母基因的基因表达数据。表2 9 为这些基因按照功能划分的一个简表。 表2 96 4 条按功a 分类的酵母基因 甥i 日雕= ii 黉”i 强暇 誊i ；葚f 矧：嚣女蜒 c h r o m a t i ny b r 0 1 a w ，y n i 1 c ，y n l 0 3 0 w ，y b r 0 0 9 c ，y d r 2 2 4 c ， 1 8 ( 1 - 8 ) s t r u c t u r ey b 瑚3 c ，y d r 2 2 5 w ，y b l 0 0 2 w y d r 0 5 0 c ，y k l l 5 2 c ，y c r 0 1 2 w ，y g r l 9 2 c ，y j r 0 0 9 c ， y l m l 7 4 w ，l n 5 2 w ，y k i d 6 0 c ，y p r 0 7 4 c ，y l r l 3 4 w ， g l y c o l y s i s 2 1 6 ( 9 _ 2 5 ) y g r 0 8 7 c ，y l r 0 4 4 c ，y a i m 3 8 w ，y g l 2 5 3 w ，y o r 3 4 4 c ， y g r 2 4 0 c ，y i 且1 5 3 c y d i j ) 0 7 w ，y e r 0 9 4 c ，y f r 0 0 4 w ，y g r 0 4 8 w y d r 4 2 7 w ， y k l l 4 5 w ，y g l 0 4 8 c ，y f r 0 5 0 c ，y d i 伪7 c ，y o r 2 5 9 c ， p r a t e i ny p r l 0 8 w ，y e r 0 2 1 w ，y g r 2 5 3 c ，y g l 0 1 1 c ，y m r 3 1 4 w ， 3 2 9 ( 2 6 _ 一5 4 ) d e g r a d a t i o n y g r l 3 5 w ，y o r 0 1 2 w ，y p r l 0 3 w ，y j l 呻1 w ，y o r 3 6 2 c ， y o r l 5 7 c ，y o l d 3 8 w ，y b l 0 4 1 w ，y h r 2 0 0 w y d r 3 9 4 w ， y o r l l 7 w ，y f r 0 5 2 w ，y d l l 4 7 w ，y o r 2 6 1 c y l r 0 4 5 c ，y o r 0 3 3 c ，l 1 5 9 w ，y n i 上2 5 c y l r 2 1 0 w ， s p i n d l e 4l o ( 5 5 6 4 ) p o ky c r 0 0 2 c ，y g l l l 6 w ，y d l l 5 5 w ，y d r l l 8 w ，y k l 0 2 2 c 表2 1 0 和表2 1 1 分别是用k m e a n s 算法和基于距离的k m e a l l s 改进算法的 聚类结果。由表2 1 0 可知，使用k - m e a n s 算法对6 4 条数据进行聚类，第2 6 ，4 2 ， 9 第二章k m e a n $ 聚类增强抗噪性的改进 5 1 共3 条基因被错分到了其它的簇里。而在表2 1 1 中看到，使用基于距离的 k k , l e a n s 改进算法，聚类结果与传统k i v e a i $ 算法聚类结果相同，并且实验并没 有发现可能的噪声数据。 表2 1 0k - m e n s 聚类6 4 条基因表达数据实验结果 | | j ii ；甏嚣孵蠹i i 旁蒜鋈黪曩1 1 i 潮n 受 辅? 闵肆 第1 类8 条1 8 第2 类2 0 条9 _ 2 5 ，2 6 ，4 2 ，5 1 第3 类2 6 条2 7 4 1 ，4 3 5 0 ，5 2 5 4 第4 类1 0 条 5 5 _ 6 4 表2 1 1 基于距离限制的改进算法聚类6 4 条基因表达数据实验结果 li 类鞠燃i ! ；i i 羲，鼗j蠢i 飘疆皿蓐凼；：彗- - 第1 类8 条1 8 第2 类2 0 条 9 _ 一2 5 2 6 ，4 2 5 1 第3 类2 6 条2 7 _ 4 1 4 3 5 0 ，5 2 5 4 第4 类1 0 条5 5 _ 6 4 可能噪音0 条 用对距离限制的改进方法对6 4 条基因表达数据集进行聚类，聚类结果并没 有较好的改善，其原因很有可能是没有找到合适的距离阈值或者数据集各类数 据的实际分散度较大。因为上述改进算法在数据分布已知，而且各个类别所含 数据的分散度比较接近时，容易找到合适的距离阈值，并且会有比较好的结果。 如果数据分布未知，或者各个类别所含数据的分散度相差比较大时，很难确定 限制距离阈值a 的大小，因而会造成聚类结果会较差。 为此，希望事先通过一定的方法对数据集的分布有一定的了解并且自动识 别可能的噪声点。而神经网络中的s o m ( s e l fo r g a n i z i n gm a p ) 算法具有将高维 数据集映射到低维空间的特性，能够很好的表达输入数据集的空间分布；模型 本身自组织的特性使得其能够检测到噪声或者奇异点。因此，本章在下一节提 出了一种结合s o m 算法的优点对k i e a n s 算法进行改进的方法。 2 2 2 基于s o m 的k m e a n s 改进方法 s o m ( s e r f - o r g a n i z i n gm a p ) 是一种可用于聚类的神经网络模型【2 3 l 【2 4 1 瞄 h i 。 神经网络聚类主要有两种方法，分别是竞争学习( c o m p e t i t i v el e a r n i n g ) 和自组 织特征映射，这两种方法都涉及有竞争的神经单元。竞争学习采用“胜者全取” 1 0 第二章k m e a l l $ 聚类增强抗噪性的改进 的方式对系统当前的输入对象进行竞争，获胜的单元修正它与对象的连接权重， 以便未来它能够对与当前对象相似或一样的对象做出较强的反应。自组织特征 映射也是对当前的输入对象进行竞争，为了更接近输入对象，获胜的单元及其 邻近的神经单元的权向量将进行调整。s o m 正是属于自组织映射的神经网络聚 类方法。 s o m 算法的输出竞争层由m n = m 个神经单元组成，且形成一个二维平面 阵列。输入层神经元与竞争层各神经元之间实现全互连接，如下图2 1 所示： 矗 图2 1s o m 网络模型 竞争输出层每一个神经单元都有一个连接权向量m ：【，】，其中p 为网 络输入矢量的维数。 s o m 可以将任意维数的输入信息转变为二维的映射，并以拓扑有序的方式 自适应实现这个变换。这主要受大脑神经系统的生理结构的启发：人脑在许多 地方对不同的感觉输入用拓扑有序的方式映射到人脑皮层的不同区域。映射过 程分为三个子过程：竞争、合作以及模型矢量自适应调节。 竞争过程：对每个输入模式，网格中的神经元分别计算与输入模式的判别 函数值，根据判别函数值来确定获胜的神经元。这个判别函数为神经元之间的竞 争提供基础通常采用的判别函数为e u c l i d e a n 距离。 合作过程：获胜神经元的拓扑邻域决定兴奋神经元的空间位置，从而提供 相邻神经元合作的基础。其关键问题是：怎样定义一个在神经生物学上正确的 拓扑邻域。从神经生物学来说，一个激活的神经元倾向于激活它紧接的邻域内 的神经元而不是和它隔得远的神经元。具体地，设h 。：表示以获胜神经元c 为中心 第二章k v l e a l l s 聚类增强抗噪性的改进 的拓扑邻域函数，d 。表示获胜神经元c 和兴奋神经元f 之间的侧向距离，h 。必须 满足两个要求： 1 ) 拓扑邻域函数h 。在d 。一。的获胜神经元c 处达到最高值； 2 ) 拓扑邻域函数h 。的幅度值随侧向距离d 。的增加而单调递减，当d 。一m 时趋于0 ： 满足这些要求的一个h u 的典型选择为高斯函数h “。e x p ( 一j ；帮。( i ) 用于度 量兴奋神经元在学习过程中参与的程度，随迭代次数f 指数下降，以此来保证拓 扑邻域函数值随时间递减。o ( t ) 较为流行的选择是o o ) ；a d e x p ( 一与。 r l 模型矢量自适应调节过程：为了使网络成为自组织的，要求神经元权值向 量随输入向量改变。这一机制使神经元通过对它们突触权值的适当调节使获胜 神经元对以后相似输入模式的响应增强。k o h o n e n 提出下面权重修改规则【2 6 1 ： m ( f + 1 ) 一w i ( f ) + 吃。( f ) g m o ) ) ( 2 3 ) s o m 聚类算法描述如下【2 6 j ： 1 ) 初始化：设定竞争输出层的规模大小，随机初始化竞争输出层各个神经元 的权向量叶( o ) ，i l m 2 ) 发现获胜的竞争神经元：对于每一个输入矢量z ，找出相应的获胜神经元 c ，满足c - a t g r a ：i n - 肛一，i - 1 , m ，其中m 为竞争神经元个数 3 ) 调整连接权重w f ( 0 ) ，根据下式调整获胜单元c 及周围神经元的权， 岍1 ) = 瞄”淞叫1 黜 其中札( f ) 是以c 为中心的一个邻域，对于满足f o + 1 ) c t c , ( t ) ： k o ) 。唧( 一鬯嘉) ，和是神经元f 和c 在s 。m 竞争输出层中的位 置，忙一圳为它们之间的距离 4 ) 重复执行步骤2 ) 一3 ) ，直至权向量稳定为j e s o m 算法的自适应过程分为两个阶段：排序阶段和收敛阶段。 1 ) 排序阶段：在这一阶段将形成权值向量的拓扑排序，这一过程可能需 1 2 第二章k i e a n s 聚类增强抗噪性的改进 要s o m 算法迭代1 0 0 0 次或更多。 2 ) 收敛阶段：这一阶段将微调神经元模型矢量从而提供对输入空间的准 确统计性。一般来说这一过程迭代次数至少是网络中神经元数目的 5 0 0 倍。 图2 2 a ) 显示训练模型时所用数据的分布情况，满足足均匀分布。图2 2 - b ) 、 2 2 c ) 、2 2 d ) 为s o m 训练模型时各阶段模型拓扑结构的显示，其中图2 2 b ) 显示随机初始化神经元模型矢量的初始值，图2 2 一c ) 显示排序阶段完成后各模 型矢量的值，图2 2 - d ) 显示收敛阶段完成后各模型矢量的值。 由此可以看出s o m 算法具有很好的拓扑排序性质。算法通过自组织方法用 大量样本数据来调整权向量，能够在低维空问中直观的反映高维输入数据集的 分布情况，由于在调整权向量时获胜的单元及其邻近的神经单元都会被调整， 向输入对象靠近，所以相邻的神经元权向量反映相近的输入对象，网格中神经 元的空间位置对应于输入模式的特定区域或特征；而且神经元模型矢量能够近 似的表示输入空问。这一特性有助于发现“噪声”和奇异点。 2 2 - 曲 2 2 a ) 2 2 - a ) 图2 2s o m 模型训练过程各阶段显示 ， 蛳 0 第二章k m e a n s 聚类增强抗噪性的改进 因此，可以预先通过s o m 算法剔除数据集内可能存在的奇异点，从而避免 这些噪声或者奇异点在算法迭代的过程中对聚类中心的干扰，同时可以利用 s o m 的结果选取k - m e a n s 的初始聚类中心。 基于s o m 的k m e a n s 改进方法如下所剥2 8 】： 1 1 设定k - m e a n s 所要生成的簇的数目为k 、域值a 表示s o m 自组织图 的神经元认为其有效时所应该映射的样本数据的最小数目，以及s o m 网络模型结构； 2 1 用输入样本数据集训练s o m 自组织图至权向量稳定，将样本数据映射 到相应的自组织图单元中： 3 ) 计算每个神经元内映射数据的数日l ，若l 小于九，则表示相应的数 据可能为“噪声”或奇异点，该神经元被认为无效； 4 1 从有效的神经元里随机选择k 个样本数据点作为k - m e a n s 算法的初始 聚类中心； 5 1 从输入数据集中选择那些被映射到有效神经元的数据组成一个数据子 集，进行k - m e a n s 聚类； 6 1 对于被映射到无效神经元的样本数据，将其划分到与各最终k - m e a n s 聚类中心中距离测度最小的那一类中，表示可能为噪声点的数据最有 可能属于哪一类。 实验首先采用上一节所用的i r i s 数据集加上1 0 个噪声点所构成的数据集， s o m 模型选择7 * 8 ，实验识别出了上述1 0 个噪声点，1 5 0 条i r i s 数据的聚类结 果如表2 1 2 所示： 表2 1 2 基于s o m 的改进算法聚类k i s 数据实验结果 l 粪剐j 誓臣条数； 叠_ 。 对应数据撅号 1第1 类 5 01 5 0 j第2 类 5 05 l 一6 87 07 27 4 8 38 5 1 0 0l l l1 3 91 4 2 第3 类5 06 97 38 41 0 1 ll o11 21 3 81 4 0 1 4 11 4 3 1 5 0 此外，改进算法还识别4 2 、4 7 、6 6 、7 8 、8 0 、9 0 这6 条数据为噪声点，由 于改进方法在发现可能的噪声点后，并没有将其丢弃而只是在训练类中心的时 候不用，在算法的最后还是给与了类别划分。 用基于s o m 的k m e a n s 改进方法对2 1 节中所用的2 4 5 条酵母基因的基因 1 4 第二章k m c a i l s 聚类增强抗噪性的改进 表达数据进行聚类，表2 1 3 是聚类结果，聚错3 6 个，比上节中传统k m c a n s 方 法的结果要好。 表2 1 3 基于s o m 的k m e a i l s 改进方法聚类2 4 5 条基因表达数据实验结果 一类j 别 j 数据袭叛| ： = 第1 类 5 3l 一4 74 91 7 71 8 01 9 72 2 12 3 0 第2 类 1 0 94 85 0 1 5 7 第3 类 4 01 5 8 一1 7 61 7 8 - 1 7 91 8 1 1 9 11 9 5 1 9 61 9 82 0 02 0 52 1 2 2 1 4 第4 类 3 9 1 9 92 0 1 - 2 0 42 0 6 2 1 12 1 5 2 2 02 2 2 2 2 92 3 l 一2 3 92 4 1 2 4 5 第5 类 51 9 2 1 9 42 4 0 改进算法标示出的可能的噪声点为4 91 9 2 、1 9 4 、1 8 01 9 2 、1 9 7 、2 0 0 、2 0 9 2 1 0 2 1 4 、2 3 52 4 0 。 用基于s o m 的k m e a n s 改进方法对2 1 节中所用的6 4 条酵母基因的基因表 达数据进行聚类，表2 1 4 是用基于s o m 的k m e a n s 改进算法的聚类结果。 表2 1 4 基于s o m 的改进算法聚类“条基因表达数据实验结果 囊。爨强峨、i i 鬃；激i i 第1 类8 条 l 8 第2 类1 7 条9 2 5 4 2 第3 类2 9 条 2 6 _ 一4 1 ，4 3 5 4 第4 类1 0 条 5 5 _ 6 4 可能噪音2 条 2 64 2 结果比表2 1 0k - m e a n s 聚类结果和表2 1 1 基于距离限制的改进算法的