（计算机应用技术专业论文）基于高维数据的双聚类算法研究与应用.pdf

硕士论文 基于高维数据的双聚类算法研究与应用 摘要 近年来，随着生物信息学、电子商务等行业的迅速发展，在这些领域积累了大量高 维数据，利用数据挖掘技术能够在这些数据中找到许多对科学研究和市场营销起到重要 作用的有价值的信息。在聚类分析技术方面，传统聚类方法只能在数据矩阵的行或者列 某一方向上进行，因此只能找到全局信息，而高维数据的特点就是含有大量的局部信息， 这是传统聚类方法所无法找到的。为了更好地聚类高维数据，尤其是在高维数据空间中聚 类局部信息，双聚类这种新的聚类方法得到了越来越广泛的应用。双聚类算法之所以更 加适应高维数据，是因为双聚类算法是在数据矩阵的行和列两个方向上同时聚类，这就使 得双聚类算法能够更加有效地发现高维数据中的局部信息。 双聚类算法的出现，很好地解决了传统聚类在聚类高维数据时遇到的瓶颈，但是由 于国内外对双聚类算法研究还处于起步阶段，近年所提出的各种双聚类算法都还存在着 各种不足之处，因此对双聚类算法的研究与改进尤为必要。本文的主要工作是首先对双 聚类的定义、类型、结构作详细阐述，然后对近年来应用较多的双聚类算法的数学模型， 聚类策略等方面进行研究分析，总结分析了这些双聚类算法的优缺点。在研究分析多种 双聚类算法的基础上，提出了一种适合高维数据的基于惩罚策略的双聚类算法( p e n a l t y s t r a t e g yb a s e do v e r l a p p i n gb i c l u s t e r i n ga l g o r i t h m ，简称p o b a ) 。重点针对c h e n ga n d c h u r c h 算法中在每次迭代过程中，须引入随机数取代聚类结果中元素的替代过程进行了 改进，利用惩罚策略改善双聚类算法的迭代过程，该策略能够使数据矩阵顺利完成双聚 类，同时避免了贪心搜索策略中随机数干扰问题，并通过设置p o b a 算法中引入的控制 惩罚力度的参数秒，达到控制双聚类结果重叠率的效果，这使得算法能够灵活的满足不 同聚类应用的需求。论文最后设计实现了p o b a 算法并将其应用在公共的高维数据集的 双聚类实验中，通过对实验结果分析，验证了算法的有效性，同时针对实验数据的分析 结果，确定了算法中参数设置的原则。 关键词：聚类分析，双聚类，高维数据，惩罚策略，双聚类算法 a b s t r a c t硕士论文 a b s t r a c t i nr e c e n ty e a r s ，晰t l lt h ed e v e l o p m e n ti nt h eb i o i n f o r m a t i c sa n de - c o m m e r c e ，m o r ea n d m o r eh i g l l - d i m e n s i o n a ld a t an e e dt ob ea n a l y z e d ，d a t am i n i n gt e c h n o l o g yc a l lf i n dv a l u a b l e i n f o r m a t i o ni nt h e s ed a t af o rs c i e n t i f i cr e s e a r c ha n dm a r k e t i n g i nt h ec l u s t e r i n gt e c h n o l o g y , t r a d i t i o n a lc l u s t e r i n gm e t h o d sc l u s t e re i t h e rr o w so rc o l u m n sb u tn o ts i m u l t a n e o u s l y , s ot h e r e s u l ti sa l m o s ta b o u tt h eo v e r a l li n f o r m a t i o n ，b u tt h eh i g hd i m e n s i o n a ld a t aa l w a y sc o n t a i n sa 1 0 to fl o c a li n f o r m a t i o n ，w h i c ht h et r a d i t i o n a lc l u s t e r i n gm e t h o dc a nn o tf i n d b i c l u s t e r i n g a l g o r i t h mc l u s t e r st h ed a t am a t r i xi nb o t ho fr o w sa n dc o l u m n sa tt h es a m et i m e ，s ot h e yc a n f i n dt h el o c a li n f o r m a t i o ni nt h ed a t am a t r i x ，t h i sn e wm e t h o di sa p p l i e dt oi m p r o v et h ee f f e c t o fc l u s t e r i n gf o rt h eh i g hd i m e n s i o n a ld a t a , e s p e c i a l l yi nc l u s t e r i n gp a r t i a lc o r r e l a t i o no f h i g h d i m e n s i o n a ld a t as p a c e b i c l u s t e r i n ga l g o r i t h mi m p r o v e st h ee f f e c to fc l u s t e r i n gf o rt h eh i 。g hd i m e n s i o n a ld a t a , b u tt h er e s e a r c ho nb i c l u s t e r i n ga l g o r i t h mi ss t i l li ni t si n i t i a ls t a g e ，t h ev a r i o u sb i c l u s t e r i n g a l g o r i t h m s s t i l lh a v ei t so w ns h o r t c o m i n g s ，a n dt h e r e f o r et h er e s e a r c ho fb i c l u s t e r i n g a l g o r i t h m si sp a r t i c u l a r l yn e c e s s a r y t h em a i nw o r ko ft h i sp a p e ri st h a t ：f i r s t l y , i ti n t r o d u c e s t h ed e f i n i t i o no ft h eb i c l u s t e r , t y p e ，a n ds t r u c t u r e ，a n dt h e na n a l y z e st h em a t h e m a t i c a lm o d e l a n dr e s e a r c hs t r a t e g yo fs e v e r a li m p o r t a n tb i c l u s t e r i n ga l g o r i t h m s ，c o n c l u d e st h e i ra d v a n t a g e s a n dd i s a d v a n t a g e s b a s e do nt h er e s e a r c ha n da n a l y s i so fb i c l u s t e r i n ga l g o r i t h m s ，i nt h i sp a p e r ， ap e n a l t ys t r a t e g yb a s e do v e r l a p p i n gb i c l u s t e r i n ga l g o r i t h m ( p o b a ) i sp r o p o s e d t h e a l g o r i t h mf o c u s e so ni m p r o v i n gt h ei t e r a t i o ni nt h ep r o c e s so fc h e n ga n dc h u r c ha l g o r i t h m ， w h i c hh a st ou s et h er a n d o mn u m b e rt or e p l a c et h eb i c l u s t e r i n gr e s u l t s ，t h ep e n a l t ys t r a t e g y c a nh e l pt h ea l g o r i t h mc o m p l e t et h eb i c l u s t e r i n g ，w h i l ea v o i d i n gt h ei n t e r f e r e n c ew i t ht h e r a n d o mn u m b e ri nt h eg r e e d ys e a r c hs t r a t e g y a n dp o b aa l g o r i t h mu s e sap a r a m e t e rt o c o n t r o lt h ep e n a l t ya n dt h eo v e r l a p p i n gr a t eo fb i c l u s t e rr e s u l t s ，i tm a k e su pf o rt h ec h e n ga n d c h u r c ha l g o r i t h ms e t b a c k s ，a n dh e l pt h ea l g o r i t h ms a t i s f yt h ed i f f e r e n tb i c l u s t e r i n gd e m a n d s f i n a l ) , , t h ep a p e ri m p l e m e n t st h ea l g o r i t h m ，u s e si tt ob i c l u s t e rt h ep u b l i ch i g h - d i m e n s i o n a l d a t as e t s t h r o u g ha n a l y z i n gt h ee x p e r i m e n t a lr e s u l t s ，t h ep a p e rp r o v e st h ee f f e c t i v e n e s so f t h ea l g o r i t h m ，a n dg i v e ss o m ea d v i c ea b o u ts e r i n gt h ep a r a m e t e r so ft h ea l g o r i t h m k e y w o r d s ：c l u s t e r i n ga n a l y s i s ，b i c l u s t e r , h i g h - d i m e n s i o n a ld a t a ，p e n a l t ys t r a t e g y , b i c l u s t e r i n ga l g o r i t h m 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学 位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或公布 过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的 材料。与我一同工作的同事对本学位论文做出的贡献均已在论文中作了明 确的说明。 研究生签名： 护7 年加乡日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或上 网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并授权 其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密论文， 按保密的有关规定和程序处理。 研究生签名： 硕士论文基于高维数据的双聚类算法研究与应用 1 绪论 1 1 课题的意义和目的 数据挖掘是一门多科学交叉学科，是数据库技术和人工智能领域的研究热点之一。 应用数据挖掘技术，可以从海量数据中发现有价值的信息。其中频繁模式、聚类、分类 是在数据挖掘中最广泛使用的模型，可以用来表示、分析和汇总大型数据集中潜在的模 式【l j 。目前已提出了大量频繁模式挖掘算法、聚类算法和分类算法，这些算法在分析维 数不高的数据集时效率高、效果不错【2 】。通过这些数据挖掘技术能够从海量数据中发现 有价值的信息，来指导科学研究与市场营销。 随着2 1 世纪的生物信息学和电子商务应用的迅速发展，在这些领域积累了大量高 维数据，对高维数据的挖掘变得越来越重要。一般的数据挖掘方法在处理高维数据时会 遇到“维灾 的问题，许多挖掘算法的计算复杂度将随着维数的增加呈指数增长p j 。一 般的数据挖掘方法在遇到高维数据时，由于高维数据与普通维数较低的数据之间存在明 显的差异，使得一些公式和数学模型失去了意义，无法利用它们来发现高维数据中的有 价值的信息。无论效率上还是信息的价值上，普通的数据挖掘算法都不能很好地适应高 维数据，因此对于高维数据挖掘方法的探索研究显得尤为迫切。 在聚类分析方面，随着维数增加，数据越来越稀疏，传统聚类算法中所依靠的相似 性度量在高维空间中变得没有意义，这使得基于相似度量的传统聚类算法无法在高维空 间中发现有价值的信息；传统聚类方法仅在数据矩阵的一个方向( 行或列) 上聚类，即在 全局模式下聚类，因此只能找到整个数据集的全局信息，而大量局部信息被丢弃掉了【4 j 。 高维数据的特点之一就是存在大量局部信息，而全局信息却不是很明显。因此传统聚类 方法很难有效地发现存在于高维数据中的有效信息。 为了更好地对高维数据进行聚类，产生了以平均平方残基为聚类标准进行聚类的双 聚类( b i c l u s t e r ) 模型【5 1 。双聚类不同于传统聚类方法，它是在数据矩阵的行和列两个方 向上同时聚类，除了能够有效发现全局信息外，也可以更加准确地在高维数据中发现局 部信息。通过双聚类对传统聚类方法的改进，在对生物信息学和电子商务上的高维数据 的挖掘时，能够发现更多有价值的信息，对生物信息的科研工作，电子商务企业的市场 决策都能起到很有意义的指导作用。 双聚类属于新兴的聚类分析方法，国内在这方面的研究还并不深入，但由于国内生 物信息技术、电子商务的迅猛发展，对双聚类算法的研究分析与实现具有重要的理论与 现实意义。 l 绪论硕士论文 课题研究现状 双聚类的思想首次由h a r t i g a n 6 j 于1 9 7 2 年提出，当时主要是用来描述同时对数据矩 阵的行和列进行聚类的思想。而双聚类( b i c l u s t e r i n g ) 这个概念的正式确立，则是由c h e n g 和c h u r c h l 5 j 两位科学家在2 0 0 0 年时提出的。从此以后，越来越多优秀的双聚类算法涌 现出来。 y a n g 7 】【8 】等改进了c h e n ga n dc h u r c h 所提出的双聚类算法，提出了一种新的双聚类 算法f l o c ，该算法能够同时发现一组符合条件的重叠的双聚类。g e t z l 9 】等提出了一种 耦合双向迭代的双聚类算法( c o u p l e dt w o w a yi t e r a t i v ec l u s t e r i n g ) 来识别双聚类。t a n g 1 0 】 等提出了另外一种关联双向聚类算法，该算法将在行和列上的聚类结果合并起来，从而 产生所需要的双聚类。l a z z e r o n i 和o w e n 提出了一种格子模型【l ，这种模型将整个数据 集建模为基于全局背景值的簇的叠加。t a n a y 1 2 】等将图论与概率论结合起来，设计了一 种s a m b a 双聚类算法，该算法将数据矩阵建模成一个二分图，将寻找双聚类的问题转 化为寻找二分图中找稠密子图的问题。k l u g e r 【1 3 j 等提出了一种双聚类算法在数据矩阵中 通过特征向量来识别独特的棋盘结构双聚类。c a n o 1 4 i 等提出了一种基于模糊理论的双聚 类算法，该算法能够发现潜在的重叠双聚类。 由于寻找双聚类的问题已经被证明为是n p 问题，因此所以大多数双聚类算法采用 启发式的搜索策略来寻找双聚类，模拟退火算法【1 5 】，蚁群算法【1 6 1 ，遗传算法【1 7 1 ，都是 最近应用较多的启发式搜索策略，许多双聚类算法通过利用这些策略，设计出了更加有 效的双聚类算法。a n u p a m 1 8 】和j a y a l a k s h m i 1 9 】将模拟退火算法应用于双聚类算法中，使 得算法较之传统的基于贪心搜索算法的双聚类算法更加高效。c h a k r a b o r t y1 2 0 等将遗传 算法应用在解决双聚类问题中，提出了一种基于迭代遗传算法的双聚类算法，算法在效 率和准确性上都有所提高。 双聚类问题的研究是一个较新且应用前景广泛的领域，人们对它的研究还处于起步 阶段，处理手段及技术还不完善，随着研究理论及手段的深入提高，针对双聚类的应用 将会越来越多，对双聚类算法的研究也将更为有效及深入。 1 3 本文的主要工作 本文所做的主要工作如下： 1 对双聚类的定义、类型、结构等概念进行了详细地分析阐述。对近年来提出的应 用较多的双聚类算法的数学模型，聚类策略等方面进行研究分析，并针对性地阐述总结 了这些双聚类算法的特点。 2 在算法的研究过程中，针对以运用贪心搜索策略进行聚类的双聚类算法中存在的 随机数对聚类结果的干扰问题，具体分析了相关算法的算法模型及步骤，确定了相应的 2 硕士论文基于高维数据的双聚类算法研究与应用 算法改进策略。 3 提出了一种适合高维数据的基于惩罚策略的双聚类算法( p e n a l t ys t r a t e g yb a s e d o v e r l a p p i n gb i c l u s t e r i n ga l g o r i t h m ，简称p o b a ) 。重点针对c h e n ga n dc h u r c h 算法中在 每次迭代过程中，须引入随机数取代聚类结果中元素的替代过程进行了改进，利用惩罚 策略改善双聚类算法的迭代过程，避免贪心搜索策略中随机数干扰问题，并通过在 p o b a 算法中引入控制双聚类结果重叠率的参数秒，使得算法能够灵活的满足不同聚类 应用的需求。 4 编程实现了改进后的p o b a 算法，并应用在公共的高维数据集的聚类实验中，验 证了p o b a 算法的有效性。通过对算法测试结果的分析，对算法中的参数设置标准进行 了研究，给出了相应参数设置的原则。 1 4 本文的组织结构 本文分为六章，各章内容如下： 第1 章：绪论。介绍课题意义，本文的主要工作以及组织结构。 第2 章：双聚类研究。主要详细阐述双聚类算法的产生背景、定义、类型、结构， 与传统聚类算法的区别等相关概念。然后针主要对近年来提出的一些应用较多的双聚类 算法的数学模型、聚类策略等方面进行研究分析。 第3 章：p o b a 双聚类算法。详细分析了基于贪心搜索策略进行聚类的双聚类算法 的特点及步骤，针对c h e n ga n dc h u r c h 算法进行相应的改进，利用惩罚策略改善双聚类 算法的迭代过程，避免了贪心搜索策略中随机数的干扰问题，实现了p o b a 双聚类算法， 同时在算法中引入双聚类结果重叠率控制参数9 ，使得算法满足不同的应用需求。 第4 章：基于高维数据的双聚类算法应用。利用p o b a 双聚类算法对公共高维数据 集进行聚类实验，并对实验结果进行分析研究，验证了算法改进的有效性，并对算法中 的参数设置做详细研究。 第5 章：总结与展望。对论文进行总结，对研究的将来发展做一些展望。 2 双聚类研究硕士论文 2 双聚类研究 2 1 双聚类算法产生背景 聚类分析作为一种数据分析方法，能够利用科学的数学方法对需要聚类数据的属性 数值特征进行归类。近年来聚类分析研究发展迅速，从数学、统计学、信息学、人工智 能等角度不断有新的方法被提出、改进，并在经济、地质、气象、生物等领域得到成功 的应用。在目前生物信息学领域，电子商务领域的研究中，聚类分析受到广泛重视。在 基因表达、d n a 序列的研究中，聚类分析已经成为标准的程序【2 1 1 。根据聚类分析的结 果，能够更好进行科学研究与市场营销。 在数据挖掘技术的应用过程中，所处理的数据通常非常复杂，所涉及的属性可能达 到成百上千个。特别是生物科学，电子商务领域，普遍存在着维数较高的高维数据。高 维数据由于维数较高，使得数据间相关性较难发现，数据中蕴藏的信息不容易被挖掘。 当面对高维数据时，以前的一些数据挖掘技术并不能够很好的适应。聚类分析技术在数 据挖掘技术中占据着重要的地位，同样，它在面对高维数据时有许多问题亟待解决。 传统聚类方法在高维数据集中进行聚类时，主要遇到几个问题【2 】： 1 高维数据集中存在大量无关的属性，使得在所有维上寻找聚类的可能性很小。 2 高维空间中数据分布较为稀疏，通过传统聚类方法中的距离公式计算出来的距 离几乎相等。 3 高维数据集中存在着大量的局部信息。 传统聚类方法都是基于距离或密度来计算数据间的相似度，如欧氏距离、余弦相似 度、p e a r s o n 相关系数 2 2 1 等常见相似度计算方法。如k 均值算法1 2 3 1 ，层次聚类【2 4 1 等一些 传统的聚类算法都是采用基于距离或密度的方法来进行聚类，在聚类普通维数较低的数 据时，效果较好，能够聚类出数据间的全局信息。但是在聚类高维数据时，由于高维数 据的数据特点，这些传统聚类算法在聚类效果上很难达到要求。 分析研究众多传统聚类算法发现，传统聚类方法都是在行或列上进行聚类，聚类结 果都是包含所有行或列的，聚类到的信息属于全局信息，高维数据中的局部信息将很难 被发现。 为了解决高维数据聚类的问题，y i z o n gc h e n g 和g e o r g em c h u r c h t 5 l 这两个人于 2 0 0 0 年首次提出了双聚类模型及算法。双聚类算法是在数据矩阵的行和列两个方向上同 时聚类，不仅能够有效地聚类出全局信息，而且能够高效地在高维数据中发现局部信息。 4 硕士论文 基于高维数据的双聚类算法研究与应用 2 2 双聚类概念 2 2 1 双聚类的定义 假设数据矩阵a 包含n 行和m 列，分别用x = “，x ：，x 。) 和y = y l ，y ：，y 肿 表示 矩阵a 的行和列的集合，则a 可以表示为，q ，表示矩阵中第i 行第j 列的数据值， 如果icx 和j c y 分别表示行和列的子集，则如= ( ，) 表示矩阵a 的子矩阵，其中 它包含了i 中所有的行和j 中所有列。 一个双聚类( b i c l u s t e r ) 就是一个矩阵的子矩阵a u = ( ，) ，其中i c x 和j c y ， 在这个子矩阵中，每一行或列都表现出一定的相似性【5 j 。 如图2 2 1 1 所示，左图为一个数据矩阵，右图为这个数据矩阵中的一个双聚类，可 以看出该双聚类是原数据矩阵中的一个子矩阵，同时这个子矩阵在相应的行列上，数据 具有一定的相似性。 1 2345123 45 4 3 9 22 8 44 1 0 8 2 2 8 4 0 12 8 l1 2 02 7 52 9 8 3 1 82 8 0 3 72 7 72 1 5 4 0 12 9 21 0 95 8 02 3 8 2 8 5 72 8 5 2 7 12 2 6 2 2 82 9 04 82 8 52 2 4 5 3 82 7 22 6 62 7 7 2 3 6 3 3 2 8 82 3 l2 7 82 1 9 3 1 22 8 84 l2 7 82 1 9 3 1 2 4 02 7 32 3 2 3 2 92 9 63 32 7 42 2 8 4 0 l1 2 02 9 8 3 1 83 72 1 5 3 1 24 l2 1 9 图2 2 1 1 示例数据矩阵与其中的双聚类 下面将对传统聚类方法与双聚类方法在高维数据上的聚类形态进行比较。 传统聚类中，对于行的进行聚类时必须包含所有列的数据，同样的，对于列的聚类 处理必须包含所有行的信息，而双聚类则可以是行和列的任意子集。双聚类的组织没有 预先的约束，行或列的信息既可以属于多个聚类，也可以不在任何簇中，因此双聚类这 种不受限制的结构使得双聚类的产生拥有了更大的自由度，从而可以使得隐藏在数据矩 阵中的不同局部聚类信息得以充分发现。双聚类与传统聚类在高维数据处理过程的区别 如图2 2 1 2 所示： 1 2 3 4 5 6 7 8 9 o 1 2 双聚类研究 硕士论文 行聚类列聚类双聚类 图2 2 1 2 传统聚类方法与双聚类方法处理高维数据的比较 上图中前两幅图是对一个数据矩阵进行传统聚类的效果，第三幅图为对一个数据矩 阵进行双聚类。通过传统聚类与双聚类两者聚类结果之间的对比，可以看出在进行传统 聚类时只在行或列进行单维的处理， 从而完成聚类，而且聚类结果通常只对应列或行的全局信息；而双聚类则同时对数 据矩阵在行和列进行聚类，因此双聚类结果对应的是由局部行和列信息组成的任意区 域，体现的是高维数据中蕴涵的有价值的局部特征信息。 下面通过另外一个例子来进一步阐述双聚类与传统聚类在聚类形态上的差别。图 2 2 1 3 所示的为一个矩阵a 中4 行在其中7 列下的数据所对应形成的点线图。 6 4 0 3 0 1 0 o l 23 4 56 图2 2 1 3 示例点线图 硕士论文基于高维数据的双聚类算法研究与应用 通过观察可以发现三个局部信息，图中r o w l ，r o w 2 ，r o w 3 在列0 ，l ，2 ，3 下曲 线的趋势一致，可以构成一个聚类；而在列l ，2 ，3 ，4 下数据矩阵的这4 行趋势都相 似，可以形成第二个聚类；在列1 到列6 下，r o w 2 ，r o w 3 ，r o w 4 相似，构成第三个 聚类。如果采用传统的聚类算法进行聚类那么需在全部七个条件下对全局信息进行聚 类，那么很显然将很难发现上述提到的三个局部聚类，而双聚类算法就是重点去发现这 些在局部模式下形成的聚类，本论文将重点针对双聚类进行讨论研究。 2 2 2 双聚类的类型 不同的双聚类算法所能够最终完成的双聚类类型是有所不同的，目前应用较广的主 要有以下四种双聚类类型【2 5 】【2 6 】： 类型1 双聚类的结果对应的数值都相等。图2 2 2 1 所示即为类型1 。 1 01 01 o1 0 1 01 01 01 o 1 01 o1 01 o 1 o1 o1 o1 0 图2 2 2 1 所包含的数值都相等的双聚类 类型2 行或列上的数值相等的双聚类。图2 2 2 2 和图2 2 2 3 所示即为类型2 。 1 o1 。01 ol 0 2 02 02 02 0 3 o 3 03 0 3 0 4 04 04 04 0 1 02 03 o4 0 1 02 o3 o4 0 1 02 03 04 0 1 02 03 04 0 图2 2 2 2 同行包含数值相等图2 2 2 3 同列包含数值相等 类型3 行或列上数值变化趋势相同的双聚类。图2 2 2 4 和图2 2 2 5 所示为类型3 。 1 02 o5 00 0 2 03 o6 01 o 4 05 08 o3 o 5 o5 09 04 0 1 02 oo 51 5 2 o4 01 o3 0 4 o8 o2 o6 o 3 o6 01 54 5 图2 2 2 4 加法模型 图2 2 2 5 乘法模型 类型4 行或列上的信息演变趋势一致的双聚类，图2 2 2 6 所示，为类型4 的实例。 7 2 双聚类研究 颂十论立 s is 2s 3s 4 s ls 3s 4 s is 2s 4 s 1s 3s 4 图2 22 6 演变趋势一致的叔聚类 由于类型l 中所包含的数据元素都相等，因此识别出该类型的双聚类算法相对来说 比较容易实现。类型1 其实是类型2 的特例。对于类型3 中的元素，因为它们的每一行 和列都能通过加上一个特定值，或者乘以特定值得到，所以一般需要更加复杂些的双聚 类算法来寻找出这种类型的双聚类。而类型4 中行或列上的元素的演变趋势大致一致， 搜索这种类型的算法存在着一定的模糊性，因此较为复杂，需在双聚类算法中将数据矩 阵元素符号化，试图通过连贯的而不是通过具体矩阵中的数值将矩阵划分为行和列的子 集。目前双聚类算法的研究较多地针对的是类型3 和类型4 。 2 2 3 双聚类的结构 双聚类的结构8 7 】口”的定义是双聚类算法所搜索到的双聚类子矩阵在原数据矩阵中 相互问的位置关系。有的双聚类算法只在数据矩阵中搜索一个它认为最好的双聚类，则 结构最简单，将如图2231 所示。中自j 阴影部分为双聚类矩阵。 圈 图2 23 1 单独烈聚粪结构 大部分双聚类聚类算法能够搜索出用户需要的k 个双聚类，这k 个双聚类在原数 据矩阵中所能够出现的排列结构，是随着算法的不同而有所区别的。总的来说，当有k 个双聚类出现时，会出现以下几种主要结构，它们分别是： 1 独有行列的双聚类，如图2 23 2 所示： 图2 232 独有行列的烈聚类 2 格子结构的，相互之f i j 不重叠的双聚类，如图2 2 33 所示 写 碰l 幕f ，维数据的日聚尝算滤究2 ，用 _ 口土 f f 臼 幽2 233 格子结构 3 独有行或独有列的双聚类，如图2234 ，图2 235 所示 瓦瓦 图2 234 独有行的取聚类图2 , 235 独有别的职聚类 4 树型的没有重叠的双聚类，如图2 236 所不； 5 没有独占，没有重 6 层次结构的重叠的 图2 238 层次结构的重叠的般聚类 韬一j 一哿 图的 圈聚 2 双聚类研究 硕士论文 从双聚类结构的角度来说，对于越复杂双聚类结构，其对应的双聚类算法也将较为 复杂。 2 3 双聚类算法研究 2 3 1 双聚类算法的搜索策略 文献【5 】中指出双聚类问题等效于图论中平衡二分图搜索问题，其实质上是一个n p 问题，因此在双聚类算法中选用的具体搜索策略至关重要，将直接影响到双聚类算法的 效率与效果。可以将双聚类算法中使用的搜索策略分为如下五类【2 9 】【3 0 】： 1 迭代合并行和列的聚类； 2 分割和攻破策略； 3 贪心迭代搜索； 4 双聚类穷举法； 5 分布参数识别法。 迭代合并行和列的聚类策略是寻找双聚类最直接的方法，它分别将传统聚类方法运 用在行和列上，然后通过某种迭代过程来合并在行和列上获得的聚类。c t w c 9 1 算法、 i t w c 1 0 博法、d c c 3 1 1 都运用了该策略，以此获得理想的双聚类。 分割与攻破策略的思想是：先将问题分成若干与原问题相似，但规模更小的子问题， 然后递归的解决这些子问题，再将这些子问题的结果合并，来能够解决原问题。这类算 法的优点就是执行速度较快，但是缺点同样显著，就是算法可能错过一些好的双聚类， 因为在发现它们之前，这些双聚类可能已经被分割。b l o c kc l u s t e r i n g l 6 j 算法第一次利用 这种方法来寻找双聚类，之后d u f f y 3 2 1 ，t i b s l l r a i l i 【3 3 】提出了几种改进方法。 有很大一部分双聚类算法，用到的是贪心迭代搜索策略。它们的每一步总是做出它 们认为的局部最优选择，并希望这些选择能够最后产生一个全局最优解。这类算法是主 要通过添加和删除行列的方法来构造双聚类，同时利用某一标准最大化得到的双聚类。 这类算法可能会做出一些错误的决定，并丢失一些好的双聚类，但是他们的执行速度都 较快。c h e n ga n dc h u r c h 首次将该策略用于搜索数据矩阵中的双聚类，f l o c t 引，o p s m l 3 4 】 等算法都是在贪心搜索策略的基础上搜索双聚类。 还有一些算法运用的是双聚类穷举法。由于双聚类问题是n p 问题，因此双聚类算 法要想找到最优的双聚类，只能通过穷举所有可能存在于原数据矩阵中的双聚类的方 法。这些算法当然可以准确找出最优的双聚类，但是有一个非常严重的缺陷，就是时间 复杂度过高，因此它们在执行时，必须要限制所搜索的双聚类的矩阵大小，同时利用利 用算法技巧优化穷举过程，才能保证算法执行的效率。s a m b a 1 2 】算法是利用穷举策略 完成双聚类的典型算法。 l o 硕士论文基于高维数据的双聚类算法研究与应用 最后一种策略叫分布参数识别。这种方法利用一个特定的统计模型来产生双聚类， 并试着找出合适的分布参数。统计模型是这类算法的关键，模型的合理性将直接影响双 聚类结果的质量。格子模型【l i j ，g i b b s 模型【3 5 1 都是基于分布参数识别策略。 2 3 2c h c n ga n dc h u r c h 算法 c h e n ga n dc h u r c h 算法【5 】是最早提出的一种双聚类算法，该算法主要基于迭代贪心 搜索策略，根据数据矩阵a 和平均平方残基最大阈值万，找出满足平均平方残基不大于 万条件的子矩阵并使其容量最大化，从而确定双聚类。为了达到这一目的，c h e n ga n d c h u r c h 在算法中提出了利用迭代贪心删除添加矩阵行列的方法，找到满足应用条件的双 聚类。 算法运行时，采用删除行列降低数据矩阵a 整体的平均平方残基，再利用相应添 加行列算法来使所得到的聚类结果尽可能的最大化，每次迭代以数据矩阵a 为起点，通 过算法迭代后可发现一个双聚类，在迭代过程中c h e n ga n dc h u r c h 算法找出一个双聚类 后利用随机数来屏蔽聚类结果，从而使得下一次迭代能够发现不同双聚类。 c h e n ga n dc h u r c h 算法能够在短时间内发现指定数量的双聚类，但是缺点也很明显，” 由于在算法执行过程中依赖随机数来屏蔽聚类结果，从而导致聚类结果被随机数干扰， 另外，算法缺乏发现具有重叠结构双聚类的能力，无法有效地发现相应的双聚类。 2 3 3s a m b a 算法 s a m b a 算法1 9 是最近提出的较重要的一个算法，利用它能够在高维数据集中有效 地找出质量较高的双聚类。为了达到找出相应双聚类的目的，该算法综合运用了图论与 统计学的理论。算法首先将输入的数据矩阵建模成一个完全的平衡二分图。在这种情况 下，寻找双聚类的问题就相当于是在二分图中找稠密子图的问题。 s a m b a 算法由于采用了穷举法策略，能够保证找出数据矩阵中较优的双聚类，但 是算法的时间复杂度较高，必须要限制所搜索的双聚类的矩阵大小，同时利用算法技巧 优化穷举过程，才能保证算法执行的效率。 2 3 4 迭代签名算法 迭代签名算法【3 6 】主要应用于基因数据。它是把基于基因数据矩阵的一个双聚类定义 为一个转录模型，选一个已知的基因集合或随机产生一个基因集合做种子。 通过不断迭代计算，优化种子，可以将集合归并到一个近似的完美簇，从而产生一 个双聚类，不断重复该过程，直到寻找到指定数目的双聚类。 迭代签名算法执行效率较高，将基因数据看成一个转录模型使得数据规格化问题得 到合理地解决。但是算法中阈值的设定较为困难，设置不当很容易造成所得到的双聚类 结果不可靠。根据不同的数据矩阵需要找到适合该数据的种子，因此生成合适种子的方 2 双聚类研究 硕士论文 法确定起来比较困难，如果方法不当，很容易造成算法结果的不准确。 2 3 5 耦合双向聚类算法 耦合双向聚类( c o u p l e dt w o - w a yc l u s t e r i n g ，c t w c ) 采用迭代合并行和列的聚类的方 法来找到所需的双聚类。该算法开始时，创建两个集合，其中一个只包含所有的行，另 一个包含所有的列。将分层聚类算法运用在每个集合上，以产生稳定的行和列的聚类。 c t w c 通过迭代上述聚类过程来寻找符合条件的稳定的子集，在这一过程中，算法利用 一种启发式的搜索方法来避免聚类产生所有可能的合并，算法规定只有那些在上一次迭 代中被认定为是稳定聚类的行和列的集合才能够参与下一次的迭代，这种方法提高了算 法的效率，同时也避免了算法产生许多没有意义的聚类。算法反复迭代，将所有稳定聚 类汇集到一起，直到不再有符合条件的新的稳定聚类出现则终止。 该算法的优点是，通过合并传统聚类算法所得到的聚类来进行双聚类，实现上较为 容易，可以根据不同的需求选择不同的已知的传统聚类算法，算法更加灵活。但是算法 在合并过程中，所产生的稳定类的数目较大，使得说得到的双聚类的意义不够直观可靠。 2 3 6 双聚类算法总结 除了上述几种双聚类算法外，还有许多应用较广的双聚类，如格子模型算法，s p e c t r a l 算法，f l o c 算法，o p c l u s t e r s 3 7 】等。综合分析研究多种双聚类算法，根据各种双聚类 算法所能聚类到的双聚类类型，双聚类结构，以及算法中采用的搜索策略，列出如表2 1 所示的总结归纳，其中双聚类类型、结构一栏中的类型标号依据的是节2 2 2 和2 2 3 中 提到的排序。 1 2 表2 1 双聚类算法的综合比较 算法 双聚类类型双聚类结构 搜索策略 c h e n g & c h u r c h 类型3类型5贪心搜索策略 万b i c l u s t e r s类型3类型6贪心搜索策略 d c c类型l类型l 类型2迭代合并行列聚类 s a m b a类型4类型6穷举法 b l o c k类型1类型4分割与攻克 c t w c类型2类型6迭代合并行列聚类 g i b b s类型2类型3分布参数识别法 o p c l u s t e m类型4类型6穷举法 f l o c类型3类型6贪心搜索策略 硕士论文基于高维数据的双聚类算法研究与应用 2 4 本章小结 本章介绍了双聚类算法的产生背景、双聚类的定义、类型、结构以及双聚类算法中 的搜索策略。通过对双聚类的分析研究，说明了双聚类算法在处理高维数据时有效地解 决了传统聚类方法无法聚类局部信息的缺陷。分别介绍几个应用较多的双聚类算法，并 有针对性地阐述了算法的特点，最后从双聚类类型、结构、搜索策略的角度总结比较了 一些近年来应用较多的算法。 3p o b a 双聚类算法硕士论文 3p o b a 双聚类算法 本章将在第二章的分析基础上，重点针对c h e n ga n dc h u r c h 双聚类算法( 简称为 c c 双聚类算法) 做详细的研究，并基于其框架下提出p o b a 双聚类算法。 3 1c c 双聚类算法 c c 双聚类算法数学模型的关键是平均平方残基，该算法主要通过使用贪心搜索策 略，逐个搜索平均平方残基值符合参数设定阈值的子矩阵，并以此作为双聚类结果。 在c c 算法的每次迭代搜索过程中，其主要两个关键步骤： 第一步，是删除数据矩阵a 行或列的过程。这一过程的本质是通过将部分平均平方 残基值较大的行和列预先删除，从而降低整个数据矩阵a 的平均平方残基值。 第二步，再通过扩展第一步中得到的子矩阵，使双聚类结果的容量最大化。 3 1 1 平均平方残基 在c h e n ga n dc h u r c h 算法中将双聚类定义为数据矩阵中具有较高相似度得分 ( s i m i l a r i t ys c o r e ) l 拘子矩阵。其中相似度得分h ( i ，j ) 就是平均平方残基( m e a ns q u a r e d r e s i d u e ，简称m s r ) 。 设待处理的数据矩阵a 其中x 和y 分别表示数据矩阵a 的行和列的集合，则a 可 以表示为a = ( x ，y ) ，表示矩阵中第i 行第j 列的数据值。用，cx 和，cy 表示行和列 的子集，则得到的双聚类结果可表示为a u ，平均平方残基h ( i ，j ) 的计算公式如下： 即2 南，蜀一一+ 2 丽1 ，。善声 o _ 式中l ，l 表示子矩阵行数，p l 表示子矩阵列数， 口；，：? 了- 口；， ( 3 2 ) 口u2 t 万2 一口f ， l j ， 5 聒1 ( f ， 3 3 旷南，密2 南2 南争， 4 ， 1 4 r s f = a 一a t ，一a 口+ 口上， ( 3 5 ) r s 口称为残基，计算的是行平均值，列平均值，子矩阵平均值。 硕士论文基于高维数据的双聚类算法研究与应用 当需要计算数据矩阵a 中单行或单列的平均平方残基时，式3 1 将分别转化为式3 6 与式3 7 ： d ( f ) 2 南。磊一一嘞+ ) 2 刚，2 击，磊矿- a o + a t a ，2 ( 3 6 ) ( 3 7 ) 通过计算矩阵的平均平方残基h ( i ，j ) ，能够很好地揭示整个矩阵的相似性程度，即 双聚类的质量。平均平方残基h ( i ，j ) 值越小，表明该矩阵中元素的相似性更强，得到的 双聚类质量将更好，平均平方残基h ( i ，j ) 值越大，则表明双聚类中的元素相似性较低， 所得到的双聚类的质量较差。 例如，如图所示3 1 1 1 数据矩阵a 。 图3 1 1 1 不例矩阵a 观察示例矩阵发现，矩阵中每行上的元素递增1 ，而每列上的元素递增3 ，数据变 化趋势一