（计算机应用技术专业论文）方向性聚类技术及其应用.pdf

摘要 摘要 聚类分析是利用数学的方法研究和处理给定对象的分类，其目的是发现隐藏分 布在数据集中的结构。近十几年来，人们获得和生产数据的能力大幅度地提高。通 过聚类分析算法人们有效的发现这些大量的隐藏数据内的数据分布模式，以及数据 属性之间存在的有价值的联系。聚类分析技术广泛应用于生物信息学，考古学，心 理学，计算机图像处理，信息检索，工程控制等诸多领域。 在实际应用中常常会碰到高维数据，如基因表达数据，文本数据，多媒体数据 等。由于这种数据存在的普遍性，使得对高维数据的聚类分析研究具有重要意义。 本文针对高维数据的方向性及其聚类分析中出现的问题进行了研究。主要包括 基因表达数据聚类分析和文本聚类分析，并提出了一些解决问题的方法，具有一定 的理论意义利现实指导意义。 本文的主要研究工作有： 1 ) 通过对高维数据方向性特点的分析，针对基因表达数据提出了一种新的相似 度度量一方向性相似度，并在此基础上构造了适合基因表达的聚类算法d s c m 。 该算法克服了其他方向性聚类算法在基因表达聚类时的初始化敏感性，在一定 程度上可以自动判断类数以及具有一定的离群点检测功能，因而具有一定的鲁棒性。 大量的仿真实验证明了该算法具有良好的性能。 2 ) 将信息论中的极大熵原理引入到经典的球面文本聚类中，构造了适合文本聚 类的极大熵目标函数和极大熵球面文本聚类算法。新的算法可以避开局部极小而得 到全局极小，初步解决了经典球面文本聚类算法对初始化敏感性的问题，且聚类性 能有所改善。 关键词：聚类分析高维数据方向性数据方向性度量基因表达数据，文 本聚类极大熵原理 a b s t m d a b s t r a c t c 1 u s t e r i n ga n a l y s i s u s e sm a t h e m a t i c sm e t h o dt o s t u d y a n dd e a lw i t ht h e c l a s s i f i c a t i o no “h ed a t a ，t h eg o a lo fw h i c hi st of i n dt h es t m c t u r eo fu n h o w nd a t a f o r r e c e n t y e a r s ，t h e a b i l i t y o f g e t t i n g a n d m a l ( i n g d a t ah a v eb e e ni n c r e a s e d s i g n i f i c a n t l y u s i n gc l u s t e r i n ga n a l y s i st e c h n o l o g y ，p e o p l ec a nd i s c o v e rt h ed i s t r i b u t i o n p a t t e m si nt h i st r e m e n d o u sd a t aa n du s e f u lr e l a t i o n sb e t w e e nt h ea t t r i b u t e so fd a t a t h i s t e c h n o l o g yh a ss u c c e s s f u l l ya p p l i e di nt h e 丘e l d ss u c ha sb i o i l l f o r m a t i c s ，a r c h a e 0 1 0 9 y ， p s y c h o l o 卧i n f 0 册a t i o nr e t r i e v a l ，d i 百t a l i m a g ep r o c e e d i n ge n 西n e e rc o n t r 0 1 l i n g t h eh i g hd i m e n s i o n a ld a t aa r e 丘e q u e n t l ym e ts u c ha sg e n ee x p r e s s i o nd a t a ，t e x t d a t a ，m u l t i m e d i ad a t a t h eu n i v e r s a l i t yo fh i 曲d i m e n s i o n a ld a t am a k e sr e s e a r c h e so n h i 曲d i m e n s i o n a lc l u s t e r i n ga n a l y s i sv e r yi m p o n a n t t h i sp a p e rf o c u s e sm a i n l yo n i n v e s t i g a t i n ga n ds t u d y i n gc l u s t e r i n ga n a l y s i s p r o b l e m so fh i g hd i r e c t i o n a ld i m e n s i o n a ld a t a ，w h i c hi n c l u d e sg e n ee x p r e s s i o nd a t a a n d t e x td a t a a n dw ep r e s e n ts o m em e t h o d st os o l v et h e s ep r o b l e m s t 1 l ew o r k si nt h i sp a p e r h a v em u c hi m p o n a n tt h e o r e t i c a la n dp m c t i c a ls i g n i f i c a n c e t 1 1 em a j o r i t yo fo u rw o r ki ss u m m a r i z e dh e r e ： 1 ) an e ws i m i l a r i t y d i r e c t i o n a ls i m i l a r i t yt om e a s u r et h ep r o x i i i l i t yo fg e n e e x p r e s s i o nd a t ai sp r e s e n t e db ya n a l y z i n gt h ec h a r a c t e r i s t i co fd i r e c t i o n a l i t yo ft h eh i 曲 d i m e n s i o n “ d a t a b yu s i n gt h i s n e ws i m i l a r i t y ，an e w c l u s t e t i n ga l g o r i t h mi s p r e s e n t e d t h ea l g o r i t h mo v e r c o m et h e i n i t i a l i z a t i o n s e n s i t i v i t yo fo t h e rd i r e c t i o n a l c l u s t e r i n ga l g o r i t h m s i ti sa l s or o b u s tt of 访do u t l i e r so fd a t a s e t a n da u t o m a t i ce s t i m a t e t h ec l a s sn u m b e ro fd a t a s e t 2 ) c o n s i d e r i n gt h es h o n c o m i n go ft h ec o n v e n t i o n a ls p h e r i c a lk m e a n sc l u s t e r i n g a l g o r i t h m s ，b a s e do nt h em a x i m u me n t r o p yo fi n f 0 珊a t i o nt h e o r y ，w ep r e s e n tan e w s p h e r i c a lk m e a n sa 1 9 0 r i t h mw i t hm a x i m u me n t r o p y ，t h en e wa l g o r i t h mc a na v o i d l o c a lm i n i m aa n dg e tg l o b a lm i n i m a ，w h i c hp a n i a l l ys o l v e ds o m eo ft h ep m b l e m s ，e g s e n s i t i v et ot h ei n i “a lc o 玎d i t i o n s k e yw b r d s ：c l u s t e r i n ga n a l y s i sh i 曲d i i i i e n s i o n a ld a t as i m i l a r i t y - b a s e dc l u s t e r i n g d i r e c t i o n a ld a t ad i r e c t i o n a l s 面i l a r i t y g e n ee x p r e s s i o n d a t a t e x t c l u s t e r i i l g m a x i m u me n t t o p yt h e 0 t y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名 日期：沁6 年，月2 日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：缸导师签名： 日期：伽6年，月z 一日 第一章绪论 第一章绪论 1 1 引言 随着社会的发展，数据量急剧膨胀，数据的时效性和复杂性远远超过了当前的 信息处理能力。信息化和全球化是二十一世纪的最大特征，在计算机信息技术的推 动下，近十几年来，人们生产和获取数据的能力大幅度地提高，数据的产生和存储 都发生了一定的变化。无论是商业企业，科研机构还是政府部门都积累了海量的数 据资料。在数据生产、传输能力远远大于数据分析能力的今天，我们是如此的渴望 知识，却被淹没在信息的海洋中。人们不再仅仅满足于简单地获得数据，而希望摆脱 繁琐的数据处理、分析，直接获得较高层次上的信，皂、一知识。聚类分析技术能够有 效的发掘数据内在的分布模式，既可以作为一种挖掘手段，也可以作为一种预处理 技术，因而一直是一个非常活跃的研究课题。 聚类分析是利用数学的方法研究利处理给定对象分类，其目的是发现隐藏分 布在未知的数据集中的结构。聚类分析算法首先规定数据对象之间相似或者不相似 的度量，并根据数据集中数据的不同特征，将其划分为不同的簇，使得属于同一簇 内的个体之间的相似度尽可能的小，而不同簇的个体间的相似度尽可能大。通过有 效的聚类分析算法人们可以发现一定的隐藏数据集中的数据分布模式，以及数据属 性之间存在的有价值的联系。聚类分析源于许多研究领域】，包括数据挖掘，统计 学，生物学，以及机器学习等。 在数据挖掘中1 3j ，大多数工作集中在设计有效、高效地对大数据库进行聚类分 析的方法上。相关的研究课题包括：聚类方法的可扩展性，复杂形状和复杂数据类 型的聚类分析及有效的高效性，高维聚类技术，以及混合数值属性与符号属性数据 库的聚类分析方法等。由于数据库中收集了大量的数据，聚类分析已经成为数据挖 掘研究领域中一个研究重点。 作为统计学的一个分支，聚类分析的研究已有多年的历史。诸多被广泛应用的 统计软件包，如：s - p l u s ，s p s s 和s a s 都包含有k 均值和k 中心等聚类分析方法。 在生物信息学领域的研究中，聚类分析一直受到广泛的重视【4 jj 。2 1 世纪的生 物技术产生了大量数据，此时光凭经验的知识难于有效地分析这些数据。聚类分析 作为种探索性的数据分析方法在基因表达数据和d n a 序列的研究中已经成为标 准的程序。 1 江南大学硕士学位论文 在机器学习领域【6 】，聚类分析属于无( 教师) 监督的学习方法。与有( 教师) 监督的 学习方法不同，无监督的学习不依赖于事先确定的数据类别以及有类标的数据学习 样本。因此无监督学习和聚类是从未标记的样本中提取有用信息的过程。 由于聚类分析技术的特点，使得其成为当前非常活跃的研究课题之一，并被广 泛应用于生物信息学，考古学，心理学，计算机图像处理，信息检索，工程控制等 诸多领域。 1 2 问题的提出 无论是在哪个领域中聚类分析的目的都是揭示样本点之间最本质的“抱团”性 质。要想定量地处理一批样本点，首先必须对这些样本点的性质进行定量的表示。 结合该领域样本的特点确定采用哪些指标特征变量来精确刻画样本的性质，以及如 何定义样本之间的相似性测度。高维数据因为在高维空间体现出很多低维数据没有 的特征，因此使得对该类数据的聚类方法具有一定的特殊性。由于高维数据出现的 广泛性，目前有大量学者在研究高维数据的聚类分析技术。本文中我们关注于高维数 据的方向性以及其在聚类分析算法的研究与应用。 1 3 国内外研究现状 方向性数据【7 】的共同基本特征是数据的度量只需要考虑数据的方向性，而数据 本身无大小之分，只有方向或相对位置不同。这类数据常出现在农业、国防、地理、 医药、生物等各个领域。由于方向性数据的重要性，国内外很早就有方向性数据的 性质和聚类分析的研究】，但这些研究主要针对于低维方向性数据。近年来研究表 明高维的基因表达数据以文本数据也具有方向数据的某些特征，因而高维数据的方 向性及其聚类分析得到国内外学者的重视，许多学者提出了针对高维情况的方向性 聚类算法。s t r e h la 等人【1 0 ，“峙旨出使用余弦夹角作为相似性度量的s p k m e a n s 算法 在文本聚类中取得的聚类效果要明显好于使用欧几里德距离作为度量的k m e a n s 算 法。d h i l l o nl - s 等人【1 3 j 使用了一种基于余弦相似度量的算法用于寻找功能相对( 方 向相反1 的基因。s i n k k o n e n 等人【1 4 】提出了基于方向性的v m f 核函数的基因表达聚类 算法来寻找功能关的基因，b a n e j e e a 等人“】提出了针对文本数据和基因表达数据 的混合v m f 密度模型聚类算法，并首次提出了某些高维数据其内在分布为v m f 方 向性分布。文献【”】根据数据的方向性特征提出了针对高维数据的平衡聚类方法。我 们同时注意到这些聚类方法在完成有效聚类的同时都缺乏一定的鲁棒性即存在对初 始化敏感，不能够自动判断类的数量，以及缺乏抗噪声和离群点检测的缺点。而鲁 第一章绪论 棒性在聚类分析中具有重要意义，因此分析与开发具有一定鲁棒性的针对方向性数 据聚类的算法具有重要的意义。 1 4 本文的工作 本文就基因表达数据，文本两个典型的高维数据的聚类问题进行了研究与探讨 工作： 在生物信息学领域，重点研究了基因表达数据的聚类分析方法。根据方向性数 据的特征，针对基因表达数据的聚类提出了方向性相似度的概念，并提出了相应的 聚类算法。该算法克服了其他方向性聚类算法在基因表达聚类时的初始化敏感性， 在一定程度上可以自动判断类的数量并具有一定的离群点检测功能。大量的实验表 明，新的算法取得了较好的聚类结果。 在信息检索领域，重点研究了文本数据的聚类分析方法。针对经典的方向性球 面文本聚类算法对初始化敏感容易陷入局部极小值的缺点，在传统的s p k m e a n s 算 法中引入了极大熵方法，推导出了基于极大熵原理的球面文本聚类算法m e s p k m 。 实验表明引入极大熵方法的球面文本聚类方法对初始化的敏感性较小，且聚类性能 有所改善。 1 5 本文的组织结构 本文在第一章介绍了所研究问题的由来，各个问题的定义、意义、研究现状和 本人所开展的工作。正文从第二章开始，介绍了常见的高维数据以及高维数据的特 点，特别是高维数据的方向性。第三章首先介绍了目前常用的基因表达聚类技术， 在方向性分布的基础上提出了方向性相似度，并根据基因表达数据的特点提出了以 方向性相似度为度量的聚类算法d s c m ，该算法解决了其他方向性聚类算法在基因 表达数据聚类时缺乏鲁棒性的问题。第三章首先介绍了文本聚类的原理及经典的文 本聚类算法，而后描述了极大熵原理。通过在经典的文本聚类算法s p k m e a n s 中引 入极大熵方法，提出了m e s p k m s 算法。新的算法进一步提升了经典的文本聚类算 法s p k m e a n s 的性能。本文的最后对研究工作进行了总结并指出了今后工作的方向。 第二章高维数据及其特钳 第二章高维数据及其特征 2 1 高维数据【3 ，1 8 】 由于数据形式和存储的多样性，聚类分析方法往往是针对不同领域的特定数据 设计的，即没有任何一种单一的聚类方法可以通用地处理任何类型的数据。在很多 应用中，我们经常会碰到一些对象，它们可能有几十，几百或者成千上万个属性。 若这些对象表示成高维属性空间中的点或者向量，那么客观世界中的对象就可以用 高维数据的集合来表示。下面是一些常见的高维数据的例子： 2 1 - 1 购物篮数据 在零售商业中，一个客户的一次购物行为可以看作一个交易。客户采购商品的 集合构成交易记录，形象地称为购物篮。人们为了维护客户事务数据，开发了大型 的购物篮数据库，数据库中记录了许多客户的交易记录。我们可以将所有商品种类 看成一个表的列，而客户的一次购物行为看成表的行。如果在该次购物中有某种商 品，就在对应的列上记录1 ，否则就记为o 。这样就可以将购物篮数据看成以商品种 类为维，以交易为记录的多维数据。因为商品的种类一般都非常多( 几千一几万种) ， 所以购物篮数据具有高维，稀疏的特征。对购物篮数据进行分析可以识别客户的购 物行为，发现客户的购买模式和趋势，使企业改进服务质量，从而取得更好的客户 保持力和满意度。 2 1 2 基因表达数据 生物芯片技术是9 0 年代中期以来影响最深远的重大科技进展之一，用基因芯片 进行的表达水平检测可自动、快速地检测出成千上万个基因的表达情况。基因表达 数据是由基因芯片实验产生的，这种数据可以表示成一个矩阵，每个行对应一个基 因，每个列表示个实验条件。每个数值表示为特定条件下的m r n a 的相对丰度。 通常实验条件从几十到几千即对应基因表达数据的维数非常高，所以基因表达数据 也是一种典型的高维数据。生物学家意在通过这种数据找到特定条件组合下表现出 的相似或者相关基因的集合，从而进一步发现基因的功能。 2 1 3 文本数据 在信息检索领域，经常会用向量模型来表示文档。在向量模型中，每个文档被 看作是在词空间中的一个向量。由于词空间是一个高维空间，因此在空间向量模型 江南大学硕士学位论文 中，文档数据是一种高维数据。文本类型数据的具体形式如：网页、摘要、e m a i l 等。人们对文本数据已经开展了大量的研究工作，如获取万维网的结构、预测网页 数量、从万维网上检索数据、从网页中抽取信息等。文本聚类方法可以有效的分析 海量数据的内在结构从而帮助人们快速的获取信息。 2 1 4 多媒体数据 多媒体数据库在许多领域，如地理学，分子生物学，c a d 中得到越来越重要的 应用。基于内容的相似性搜索是多媒体数据挖掘的一个最基本操作。解决这一问题 的一种方法是通过特征抽取将多媒体对象映射成为高维空间中的点( 特征向量) 。这 样就将多媒体对象的相似性搜索问题转化成为高维空间中的最邻近查找问题。对媒 体数据进行聚类的索引机制，可以利用它建立聚类索引表来缩小查询范围，从而有效 的提高检索效率。 2 2 高维数据的特点 2 2 1 稀疏性 假设一个d 维的数据集d 存在于一个超级立方体单元q = 【o ，1 r 中，数据在空间 均匀分布，并且每个维之间是独立的。对于一个边长为s 的超级立方体范围，一个 点在这个范围内的概率为s 。，由于5c 1 ，因此随着维数d 的增大，这个概率的值会 越来越小。也就是说即使在一个很大的范围内可能连一个点也不包括旧。因此在 高维空间中数据点是非常稀疏的。 2 2 2 维数灾难 维数灾难【1 9 ，2 0 】( t h ec u r s eo fd i m e n s i o n a l i t y ) 最初含义是不可能在一个离散的多维 网格上用蛮力搜索去优化一个有很多变量的函数。这是因为网格的数目会随着维数 呈指数集的增长。随着时间的推移，“维灾”这一术语用来泛指在数据分析中遇到的 由于维数( 属性) 过多而引起的所有问题。有于“维灾”与传统上采用l 。范数作为 距离函数相关，因此通过重新定义合适的距离函数或者相似度函数可以避开“维灾” 的问题。此外有效的选维和降维技术也是解决高维维灾问题的重要手段。 2 2 3 方向性 当统计数据只包含有方向，它们可以表示为单位球面的点，称这种数据为方向 数据( 或者球面数据) 。方向数据m l j 的共同基本特征是数据的度量只需要考虑数据的 方向性，而数据本身无大小之分，只有方向或相对位置不同。在许多情况下，人们 第二章高维数据及其特自i 。 观测到的数据只包含有方向，例如5 ，f = l ，2 ，p 为p 个不同项目中各项所占的比 p 例，一个合理的约束是罗s 。= 1 。令x 。= s ，并记x ；( x ，x ：，x ，) ，故在欧式范 贸 数下，x 为尺中的单位向量。这种比例问题在日常生活中及科学研究中是极为常 见的。在另外的一些情况下，人们观测到的数据是一个向量，无法测出 大小， 因此只知道方向。文献【7 2 1 】手日出在从地理问题直到动物的行为的广泛领域中，人们 在科研实践中经常会遇到方向数据。因而对方向数据的研究具有很重要的意义。 b a n e r j e ea ，s u v r i ts 等人的研究1 6 ，2 2 】表明某些经过归一化的高维数据不但具 有稀疏性、维灾问题，还具有方向性的特征，其数据的内在分布符合一定的方向性 分布而不是传统的高斯分布。利用高维数据的方向性可以提高高维数据聚类的准确 度。高维数据的方向性性质的研究不但在一定程度上解释了传统上采用l ，范数作为 距离函数导致算法效果差的原因，而且也为进一步利用数据的方向性，设计新的数 据聚类算法提供了理论依据。 第三章基于方向卡似性的垫吲表达数据聚类算法 第三章基于方向相似性的基因表达数据聚类算法 3 1 基因芯片与基因表达数据 基因芯片( g e n ec h i p 或d n ac h i p ) 也叫d n a 微阵列( c d n am i c r o a r r a y ) ，是包被 在固相载体上的高度d n a 的微阵列。基因芯片“1 可以对整个基因表达组范围的 基因表达进行水平分析，能够快速有效地获取大量的基因表达信息。随着基因芯片 技术的广泛使用，基因表达谱分析中起关键作用的聚类分析技术得到了重视。如何 针对各种数据集设计处理数据的算法与方法，并解释大量数据集中的信息是目前生 物信息学探索方向之一。可以说没有聚类分析技术的参与，基因芯片技术就不可能 发挥最大的作用。 借助基因芯片技术，我们可以得到“基因表达谱”矩阵，用它来描述每个基因 在基因组中的动态功能。表3 1 是一段基因表达数据的片段。其中：行代表基因， 列代表表达水平( 对应不同的实验处理或者时间周期) 。矩阵里的数字用来表 示某一特定基因在某一特定水平上的表达强度，我们称这样的数据表格为基因表达 矩阵或基因表达数据矩阵。这些数据往往包含几千个基因或者基因片断。通常的基 因表达数据是高维的，一般至少有八九维，甚至多达几百维。 表3l 基因表达数据 n a m ea i d h a0a l o h a7a i d h a l 4a l d h a2 1a i d h a2 8a i d h a3 5 y b r l 6 6 c03 3 01 700 400 700 9- 01 2 y o r 3 5 7 c一06 4 - 03 80 3 2- o 2 90 2 2- 0 0 1 y l r 2 9 2 c- 0 2 30 1 903 601 40401 6 y g l l l 2 c- 0 6 9- 08 9 07 4- 05 6- 06 401 8 y ll 1 1 8 w0 0 40 0 1一o 8 1- o304 9 y d l l 2 0 w0 1 1o 3 200 303 2o0 3- 01 2 3 2 基因表达数据聚类分析算法 通常功能相关的基因有共同的表达，因此检测具有相似表达谱的基因群是研究 基因功能的一种有效方法。聚类分析作为一种探索性的数据分析方法，可以有效的 发现隐藏在数据内部的关系，因此基因表达数据分析的一类重要方法就是聚类分析。 基因表达聚类分析的首要目标是将表达谱相似的基因归纳成类，然后聚焦于那些可 9 江南大学硕士学位论文 能参与某些生物过程的基因群，对这些类进行生物学注释，同时获得新的生物学知 识。一个理想的基因表达数据分析方法应该具有以下特征：能够简化原始数据，结 果直观，使研究者能在海量基因数据中分析出正确的基因表达谱和功能信息；分析 方法是建立在合理的算法基础之上的，应该能全面的、综合并直观地分析原始数据， 找到新的联系。目前常用的基因表达聚类算法1 4 ，5 】方法主要有以下几种：k 一均值， 自组织映射s o m ，层次聚类算法，基于模型的聚类算法。以下就常用的基因表达聚 类算法做简要说明。 3 2 1 分层聚类 分层聚类( h i e r a r c h i c a lc l u s t e r i n 曲是一种经典的聚类方法，它用二元树形状的系 统图( d e n d r o g r a m ) 来描述数据间的关系，其中的最相似的谱形成嵌套子集中的一层。 分层聚类可以分成两种，一种是聚合式( a g g l o m e r a t i v e ) 层次聚类，另外一种是分裂 式( d i v i s i v e ) 层次聚类。聚合式的层次聚类比较常用，聚类开始时将每一条表达当成 一类，反复地将最近的两类合并成一类，在一定水平上中止系统树，可以将数据分 成类。在层次聚类算法中需要计算类之间的相似度度量。计算类之间相似性可以通 过对象间相似性度量得到，根据相似性度量方式的不同，主要可以分为三种方式： 1 简单连接( s i n 四eh n k a g e ) 。最近的两个对象的距离就是两个类相似性，两个 对象分别属于两个类； 2 完全连接( c o m p l e t eh k a g e ) 。最远的两个对象的距离就是两个类的相似性， 两个对象分别属于两个类； 3 平均连接( a v e r a g el i n k a g e ) 。两个类的所以点对的距离的平均值就是两个类的 相似性，点对中两个点分别来自两个类。 分层聚类的性能随待分类基因数的平方下降，因其需要计算每一对基因表达谱 间的距离，若分析大量的基因，计算工作量将非常大。同时选择不同的类间距离定 义在一定程度上将影响类的构成并最终导致不同的聚类结果。而且分层聚类缺乏稳 健性，解也可能不是唯一的，数据的输入次序对结果也可能产生影响 3 2 2k - m e a n s 聚类 k m e a n s 聚类是种简单快速的聚类算法，且能处理大量数据，其目标是最小 化如下的误差函数： e 。著剖阳，1 | ( 3 1 ) 第三章基于方向耵| 以性的基因表达数据聚炎算法 其中，d 为类e 中的样本，“。是类c 的中心向量( 均值) ，在最小化式( 3 1 ) 的基 础上，将样本划分到k 个类。 运行算法前必须先指定类数k 和迭代次数或者收敛条件，并随机指定k 个质心。 根据一定的距离准则( 如欧式距离) ，将每一个表达谱分配到最接近或“相似”的质 心，形成类，然后以每一类的平均矢量作为这一类的质心，重新分配，反复迭代直 到算法收敛或者达到最大迭代次数。 k m e a n s 聚类算法的关键问题是如何初始化质心和如何确定合理的聚类类数。 对于基因表达数据，一般来说事先不知道确切的类数，所以往往采用选择不同的聚 类数多次运行聚类算法，并比较不同聚类数时的聚类结果。此外由于算法对初始化 的方法极为敏感，故有多种初始化方法。 3 2 3 自组织映射 自组织映射( s e l f - o r g a n i z i n g m a p s ，s o m ) 是一科- 非常简单的神经学习方法，算法的 目标是找到能描述输入数据集的原型矢量，同时将高维输入空间连续映射到低维网 格上。这个网格由一定数目的神经元组成，一般为六角型或方形排列的二维网格， 从而易于显示。即以低维目标空间的点去表示高维原始空间的点，使得这种表示尽 可能地保留原始的距离或相似性关系。s o m 学习算法的最大优点在对高维数据聚类 时比k m e a n s 更稳健，而且对噪声稳定，一般不依赖于数据的分布形状，同时能高 性能地显示大量数据。 s o m 算法的缺点是需要用户在聚类前指定聚类类数以及网络的拓扑结构，且这 种拓扑结构容易产生不均衡的分类结果。若不相关的数据太多，则在s o m 输出中 这种数据将占据大部分类，在这种情况下使得感兴趣的数据只能处于少数类中，导 致聚类的分辨率可能很低。 3 2 4 基于混合模型的聚类方法 基于混合模型的聚类算法( m o d e l b a s e dc l u s t e r i n g ) 假定聚类的个体由一种内在的 概率框架产生，服从一定的概率分布。在这一框架下聚类方法的选择和类数的确定 问题转化为模型的选择问题。假设数据x 月一来自多个分布的混合体，那么其概率 密度就可以表示为 ，( x ；日) = 工( x ；q ) f 3 2 ) 其中为密度分支的个数，0 为各混合密度分支的比例，通常未知。正( x ，q ) 第 江南大学硕士学位论文 f 个分支的密度，其中q 为相应密度分支中的参数。整个混合密度模型的参数为 日= “，q ，吼) 当有了观测数据集 x 。，艽：，吒，为辨识混合密度模型的参数 口，可以使用最大似然函数法或者e m 方法求出模型的参数。文献的最新研究指 出高维数据诸如基因表达数据和文本数据服从方向性分布，并提出了基于混合v m f 密度模型的聚类算法。该研究结果表明可以利用方向数据的性质完成对这类数据的 有效聚类。 3 3 基于方向相似性度量的基因表达数据聚类算法d s c m 3 3 1 方向性分布及方向相似度 在生物信息学领域经常使用p e a r s o n 相关系数作为相似度的度量。给出x ，y 彤 则p e a r s o n 相关系数p 为： p 0 ，y ) = 此处二2 言d ，- ，；4 言：出，若有映射z _ 舅，5 了蔚，则有 p ( 叠，) = j 7 夕。如果：= 1 ，则可以看出p e a r s o n 相关系数的本质是种使用非度 量的相似性函数s ，夕) = 王7 夕，即向量的归一化内积膏7 夕。c o s a ，夕) 余弦相似来度量 向量x 和y 之间的线性相关性。当向量i 和箩的夹角越小则相似性函数值越大，也 即向量i 和箩越相似。文献【1 0 l 指出使用p e a r s o n 相关系数聚类分析数据本质上就是 使用余弦相似来度量数据的相似性问题。 方向性数据最常见的分布是v o nm i s e s f i s h e r ( v m f ) 分布【7 】其密度函数如下： ，( 工l “，七) = c d e h 。 ( 3 3 ) 其中= 1 ，七，口( 本文中如无特殊说明i h f 均代表欧几里德范数) ，c d 是如下的 常数： 铲( 妒2 焉 ( 3 4 ) 式( 3 4 ) 中，( ) 为第一类变型b e s s e l 函数【7 】o 我们常称式( 3 3 ) 中的“r x 为向量“和向量 第三章基于方向十 似性的塾凶表达数据聚炎算法 x 的余弦相似距离。特别的对于二维情况，v m f 分布的一种特殊形式被称为v o n m i s e s 分布，其概率密度函数为： m ( 0 ；“，七) = c o e 。“o 。“，os 日s f ( 3 5 ) 其中c 。是归一化常数。 图3 1 为“= 0 ，女 0 ，o 3 ，1 ，4 ，2 0 ) 时的v o n m i s e s 分布密度。从图中可以看出v o n m i s e s 分布中心位置由参数“确定，分布集中到中心位置的邻近程度由参数确定。 因此称“为位置参数，t 为尺度参数。显然当= 0 时v o nm i s e s 分布收敛于均匀分 布，而v m f 分布收敛于s “1 球面的均匀分布，当t 一* 时v o n m i s e s 和v m f 分布都 退化为“处的单点分布。 18 k = 2 0 16 - 14 12 1 。 0 8 一k = 4 0 6 1 9 点1 4 ：蓦每专一 一r f i 芦午o r 产尹产一。 图3 1 不同k 值的对应的v o nm i s e s 分布密度图( k = o 1 ，o 3 ，1 4 ，4 ，2 0 ) 基于以上对v m f 分布性质的分析，我们定义一个新的方向相似度量函数s ( x ，“) 来度量方向数据向量x 和聚类中心向量“的相似性： s 0 ，“) = e x p ( h 7 x ) ( 3 6 ) 其中：“7 “= 1 ，( 0 ) 类似式( 1 ) 中的尺度参数。显然s ( x ，“) 值越大说明数据向量z 与中心向量“的相似度越高，刚x 属于中心向量为“的类的可能性越大。 文【1 5 】提出了针对高维方向性数据的聚类算法m o v m f ，但这种算法存在对初始 化敏感且存在不能够自动判断类的数量等缺点。为克服传统算法的缺点，基于新的 方向数据的相似性度量，我们提出了方向相似性聚类方法d s c m ，d s c m 的优势在 江南大学硕士学位论文 于通过使用方向相似性度量以及内在集成的d s c a 和a h c 两个算法使得d s c m 在 对基因表达数据的聚类时具有一定的鲁棒性。 3 3 2 基因表达数据聚类算法d s c m 考虑s ( x ，“。) 作为数据点x ，和第i 个聚类中心吩( f = 1 ，2 ，c ；，= 1 ，2 ，n ) 之间 的相似性度量，则聚类目标是使如下的目标评价函数j ， ) 最大： ， ) 一s ( z ，“i ) 一e x p 慨；“r ) ( 3 7 ) l 。j l f - lj 。j 其中“= 。，“2 ，“。) ，且有“；7 “。= 1 ，f = 1 ，2 c 。女为尺度参数，可以根据需要 取值，的值对最终聚类结果有一定的影响。则聚类思想可以理解成求解最优的聚类 中心“。，使目标评价函数，( “) 最大，也即样本间相似测度总和最大。易知目标评价 函数，以) 取最大值的必要条件为鱼型：o ，同时注意到对于方向性数据有约束条 a “ 件“。7 “。一1 ( f = 1 ，2 c ) ，为此可以利用拉格朗日乘数法把约束条件下的求解， ) 最 大的最优化问题转化成无约束的方程求解。通过引入拉格朗日乘子x ，并定义如下 的拉格朗日目标函数l ，a ) ： o ，九) = ， ) + 九妻( 7 “i 一1 ) = 妻羔e x p ( h j ) + 九妻o 。7 略一1 ) 对工( “，a ) 中的每个中心向量“j 求偏导有： 絮半：兰觑je x 胀+ 2 地； d “f两 令式( 3 9 ) 等于0 ，则有 奴；e x p ( 缸m 峨一1 r 一 一 因“：7 “。= 1 ，由( 3 1 0 ) 可以进一步推出： ( 38 ) ( 3 9 ) ( 3 1 0 ) 一一篓三! 兰王塑堕塑! ! 壁塑些塑鲞竺塑塑壅鲞簦堕 x je x p ( h 沁) 网 式( 3 1 1 ) 中代表向量的欧几里德范数。考虑到中心向量式( 3 1 1 ) 中坼无法直接求解， 但通过有限次迭代过程可得其最优解，我们可以用不动点迭代法求其摄优解。最优 交互迭代的过程可以j i | f i 述如下，令 “= m 似) ( 3 1 2 1 其中，中是特定的算法映射，“扣是初始的聚类中心。定义算法映射 中d 蚴：“。一 “。为 睁 蓍。je x ”( 舡j “- ) 鼢唧c 啪f f ( 3 ，1 3 ) 最优交互迭代过程为首先初始化“? ；在迭代过程中，先计算m ( “? ) ，然后用 中o ? ) 值更新“；”；反复这种迭代计算，当第u + 1 ) 次的迭代值与第f 次的解非常接 近，则意味着聚类中心已经达到了不动点，取第( f + 1 ) 次的迭代解“ ，为最后的解， 结束最优迭代过程，最终迭代的不动点代表j 。( “) 的峰值。为避免了算法对初始化 的敏感性， 可以选取全部的样本点怍为初始聚类中心，即 “”；以黔“：，一，“：) = 协。，工一，工。) ，经过有效次迭代过程找到所有最优聚类的不动 点。我们定义此过程为基于方向相似度的聚类算法d i r e c t i o n a ls i m i l a r i t y b a s e d c l u s t e r i n ga l g o r i t h m ( d s c a ) 。算法具体描述如下： ) 一llli二j| “ 一 “ j 一 j 舡 一 h p p x x e e 一 ， 一 ， x x 。v箭一。v智 江南大学硕士学位论文 a l g o r i t h m ：d s c a i r e c t i o n a ls i m i l a r i t y b a s e dc l u s t e n ga l g o t h m ) s t e p l ：初始化中心“o = 0 f 0 ) ，“努，“：) 。仁，x ：，h ) ，并给定一个 o ，初始 迭代计算器f = 0 。 s t e p 2 ：按照式( 4 ) 计算相似性测度向量s “1 o ，虬) 。 s t e p 3 ：按照式( 1 1 ) 计算“( “”，计数器f = f + 1 。 s t e p 4 ： 重复计算s t e p 2 ，s t e p 3 ，直到满足”“一“刈tr ，迭代结束，此时“( ) 即为最后的解。 下面给出一个简单的实例说明d s c a 算法对数据的最优交互迭代过程。图3 2 是一个按文献 1 l 】使用的复合v m f 分布的人工方向性数据生成算法产生的复合3 个 不同的v m f 分布的2 维数据集s y n t h e t i c 3 图。 图3 2s y n t h e t i c 3 数据集 对图3 2 所示的数据进行初始化，设定中心“o = 0 f 0 ) ，“：，一，“：) 一 x ，z ：，“) ，然 后应用d s c a 算法。 聚类结果如图3 3 d 所示，所有的初始值向三个点靠拢( 聚类 中心) 。在图3 3 ( a ) ，( b ) ，( c ) 中，初始聚类中心经过1 次，6 次，1 1 次迭代所对应的状 态很好的体现d s c a 算法的聚类过程。最终所有初始中心的收敛的状态反映于图3 3 ( d ) 中，对于这个数据样本集而言，最优的聚类划分数为3 。这个结果与图3 3 ( d 1 是一致的。 尹：f ；严 第三章基于方向十h 似性的基表达数据浆类算法 ( a ) 第1 次迭代后 ( b ) a f i e r 6i t e r a t j o n s f b ) 第6 次迭代后 ( c ) a f t e r1 l 畸a t i o n s( d ) c o n v e r g e n c ea f t e r5 0i t e m t i o n s ( c ) 第1 1 次迭代后( d ) 收敛状态 图33 对图2 s y n i h e t i c 3 数据集使用d s c a 算法 因为在d s c a 算法中设定“o = ( “f ，“：，“：) = 似。，z ：，_ ，所以最终n 个聚 类中心反映了样本点数据的最终状态，因而这个过程为我们提供了一个利用它们的 最终状态进行分类的方法。假设“，“。o 收敛到同一个不动点，也就是说与对 “1 ”，“。0 应的x 1 ，_ 属于同一个类。因此当“o = ：“，“! ，“? ) = 缸1 ，x 2 ，_ ) 收敛于 c + 个类中心，数据集同时也被分成对应的c + 类。，因此我们可以称这种最优交互迭 代过程为数据的自组织过程。 为了更为精确的从”个类中心确定最优的聚类数，对最后的d s c a 得到的数据 的自组织状态即分离的比较合理的不动点解“c “- ，进一步采用凝聚层次聚类算法 ( a g g l o m e r a t i v eh i e r a r c h i c a lc l u s t e r i n g ，a h c ) 分析出类中心点即不动点的层次数，并 通过层次聚类图可以进一步确定最佳聚类数以及类与类之间的关系。 对于d s c m 方法中的a h c 算法，因为数据已经通过d s c a 进行了白组织，类 1 7 江南大学硕士学位论文 之间得到了较好的分离，故在a h c 中使用欧氏距离作为不相似性度量近似等同