（计算机应用技术专业论文）多视角判别聚类算法的研究.pdf

n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n d a s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g eo fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y r e s e a r c ho nm u l t i v i e wd i s c r i m i n a n t c l u s t e r i n ga l g o r i t h m s a t h e s i si n c o m p u t e ra p p l i c a t i o nt e c h n o l o g y b y z h u a n g c h u a n z h i a d v i s e db y z h a n gd a o q i a n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g j a n u a r y , 2 0 1 0 | | i l llli illi ll p if u 1 l i y 1 8 2 5 7 7 1 一 r 、 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：杰鲢 日 期：22 止至：! 生 ， - 摘要 多视角学习是近年来机器学习中的热点研究领域之一，广泛应用于场景分析、图像处理及 网页信息处理等多个实际应用领域。本文主要针对多视角聚类进行研究，在已有单视角判别聚 类算法的基础之上，提出了一系列多视角判别聚类算法，主要研究工作如下： ( 1 ) 通过在两个视角数据上进行交叉降维和聚类，首先提出了一种适用于两个视角数据的 多视角判别聚类算法m v d c - 2 ，然后将其扩展到一般的适用于n 个视角的多视角判别聚类算法 m v d c n 。此外，提出了一种基于m a r g i n 的多视角判别聚类算法m m d c 。实验结果验证了上 述算法的有效性。 ( 2 ) 将核方法引入多视角判别聚类，分别提出了基于核的多视角判别聚类算法k m d c 以及 核化的基于m a r g i n 的多视角判别聚类算法k m m d c ，在多特征手写体数据集、o r l 人脸数据 库和w c b k b 网页数据集上验证了所提算法的性能。 ( 3 ) 将典型相关分析( c c a ) 及其判别形式( 包括判别型典型相关分析算法d c c a 及局部判别 典型相关分析算法l d c c a ) 引入到多视角聚类的框架中，提出了多个基于典型相关分析的多视 角判别聚类算法，在实际数据集上验证了所提算法的有效性。 关键词g 聚类，多视角聚类，判别聚类，典型相关分析，核方法 多视角判别聚类算法的研究 a b s t r a c t m u t i - v i e wl e a r n i n gi st h eo n eo ft h eh o 啪t si nm a c h i n el e a r n i n g i tc a nb ew i d e l yu s e di ns c e n e a n a l y s i s ，i m a g ep r o c e s s i n g ，a n dw e bp a g ei n f o r m a t i o np r o c e s s i n ga n do t h e rr e l a t e df i e l d s b a s e do n s i n g l ev i e wd i s c r i m i n a n tc l u s t e r i n gm e t h o d s ，w ef o c u so nm u l t i v i e wc l u s t e r i n g ，a n dp r o p o s eas e r i e s o fm u l t i - v i e wc l u s t e r i n gm e t h o d si nt h i st h e s i s t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa 托l i s t e da s f o l l o w s ： ( 1 ) f i r s t l y , w ep r o p o s eam u l t i v i e wd i s c r i m i n a n tc l u s t e r i n ga l g o r i t h mc a l l e dm v d c - 2b y a p p l y i n gd i m e n s i o nr e d u n c t i o na n dc l u s t e r i n gm e t h o d si nt w ov i e wd a t a s e t ，a n dt h e nw ee x t e n di tf o r nv i e wc a s e s i na d i t i o n ，w ep r o p o s eam a r g i nb a s e dm u l t i - v i e wd i s c r i m i n a n tc l u s t e r i n ga l g o r i t h m ( m v d c - n ) t h ee x p r i m e n tr e s u l t sv a l i d a t et h ee f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m s ( 2 ) s e c o n d l y , k e r n e lm e t h o di si n t r o d u c e di n t om u l t i - v i e wd i s c r i m i n a n tc l u s t e r i n ga l g o r i t h m s a k e m e l i z e dm u l t i - v i e wd i s c r i m i n a n tc l u s t e r i n ga l g o r i t h mc a l l e dk m d ca n dak e m e l i z e dm 岫b a s e d m u l t i - v i e wd i s c r i m i n a n tc l u s t e r i n ga l g o r i t h mc a l l e dk m m d ca r ep r o p o s e ds e p a r a t e l y w ev a l i d a t e t h ee f f e c t i v e n e s so fo u ra l g o r i t h m si nh a n d w r i t i n gd a t a s e t , o r la n dw e b k bd a t a s e t ( 3 ) t h i r d l y , w ei n t r o d u c ec a n o n i c a lc o r r e l a t i o na n a l y s i s ( c c a ) a n di t s d i s c r i m i n a n tf o r m a t ( i n c l u d i n gd i s c r i m i n a n tc c aa n dl o c a ld i s c r i m i n a n tc c a ) i n t ot h ef r a m e w o r ko fm u l t i v i e w c l u s t e r i n ga l g o r i t h m s ，a n dt h r e em u l t i - v i e wd i s c r i m i n a n tc l u s t e r i n ga l g o r i t h m sa r ep r o p o s e d a n dw e v a l i d a t et h ee f f e c t i v e n e s so f t h o s ea l g o r i t h m si na c t u a ld a t a s e t s k e yw o r d s ：m u l t i - v i e wl e a r n i n g ，m u l t i - v i e wc l u s t e r i n g ，c a n o r d c a lc o r r e l a t i o na n a l y s i s ， d i s c r i m i n a n tc l u s t e r i n g ，k e r n e lm e t h o d 第一章绪论l 1 1 本课题的研究意义l 1 2 国内外研究现状2 1 3 本文的主要研究内容4 1 4 内容安排4 第二章相关背景知识。6 2 1 聚类6 2 1 1 聚类简介6 2 1 2 聚类算法介绍6 2 2 多视角学习。8 2 2 1 标准协同训练算法8 2 2 2 多视角学习的进展9 2 2 3 多视角聚类的进展l o 2 3 核方法。1 l 2 4 典型相关分析1 3 2 5 本章小结1 4 第三章多视角判别聚类算法1 5 3 1 引言1 5 3 2 单视角判别聚类算法1 5 3 2 1k 均值k m e a l l 。15 3 2 2f i s h e r 线性判别分析l d a 1 6 3 2 3 单视角判别聚类算法k m l d a 1 6 3 3 多视角判别聚类算法m v d c - 2 1 8 3 3 1 算法介绍18 3 3 2 实验结果2 0 3 3 3 实验分析2 2 3 4 多视角判别聚类算法m v d c - n 2 3 3 4 1 算法介绍2 3 3 4 2 实验结果与分析2 4 多视角判别聚类算法的研究 3 5 基于m a r g i n 的多视角判别聚类m m d c 2 5 3 5 1 算法介绍2 5 3 5 2 实验结果2 6 3 5 3 实验分析2 7 3 6 本章小结2 7 第四章核框架下的多视角判别聚类2 9 4 1 弓i 言2 9 4 2 基于核的多视角判别聚类算法2 9 4 2 1 高斯函数的性质2 9 4 2 2 核化的k i i l e a n 聚类算法k k m e a r l 3 0 4 2 3 基于核的多视角判别聚类算法k m d c 3 1 4 3 核化基于m a r g i n 的多视角判别聚类算法k m m d c 3 2 4 3 1 算法介绍3 2 4 4 实验结果与分析3 2 4 4 1 实验结果。3 2 4 4 2 实验分析。3 4 4 5 本章小结3 4 第五章基于典型相关分析的多视角判别聚类算法3 6 5 1 引言3 6 5 2 典型相关分析的刻画及求解3 7 5 2 1 典型相关分析的刻画。3 7 5 2 2 典型相关分析求解算法3 7 5 3 基于c c a 的多视角聚类算法3 8 5 3 1 算法介绍3 8 5 3 2 实验结果。3 9 5 3 3 实验分析4 l 5 4 基于d c c a 和u ) c c a 的多视角聚类算法4 2 5 4 1 基于d c c a 的多视角聚类算法。4 2 5 4 2 基于l d c c a 的多视角聚类算法4 3 5 4 3 实验结果4 5 5 4 4 实验分析4 7 5 5 本章小结一4 8 9 9 6 2 展望4 9 参考文献5 l 致谢5 6 在学期间的研究成果及发表的学术论文5 7 v 弘 多视角判别聚类算法的研究 图清单 图2 1c o v e r 模式可分性定理的一个示例1 l 图3 1 多视角判别聚类算法示意图1 9 图3 2o r l 数据集中的部分人脸图像2 0 图3 3k i i l e a n ，k m l d a ，m v d c 算法在o r l 数据集上的聚类精度对比2 0 图3 4g i i l e a l l ，k m l d a ，m v d c 算法在w e b k b 1 数据集上的聚类精度对比2 2 图3 5m v d c 算法在w e b k b 1 数据集上两个视角的聚类精度差异的变化情况2 3 。 r 图3 6 多视角判别聚类( m v d c - n ) 流程示意图。2 4 图3 7w e b k b 1 数据集上4 种聚类算法的聚类精度对比2 6 图3 8o r l 数据集上4 种聚类算法的聚类精度对比2 6 图4 1 核化基于m a r g i n 的多视角判别聚类算法示意图。3 2 图4 2o r l 和w e b k b - 2 数据集上几种算法的聚类结果的对比3 4 图5 1 c m d c ，c m v c 算法和k l l l e a r l 算法在手写体数据集上算法的平均聚类结果比较4 0 图5 2 c m d c ，c m v c 算法和k i d , e a l l 算法在手写体数据集上算法的最高聚类结果比较3 8 图5 3 手写体数据集上基于c c a 及其改进的算法最高聚类结果比较4 6 表3 1k m e a r l ，k m l d a ，m v c ，m v d c 算法在手写体数据集上的聚类精度对比( ) 。2 2 表3 2m v d c 2 ，m v c 3 ，m v d c 3 算法在手写体数据集上的聚类精度比较2 4 表3 3m v d c - 4 在手写体数据集上多视角聚类算法的聚类精度2 5 表3 4w e b k b 1 ，o r l ，m f e a t 数据集在m m d c 算法中的m a r g i n 参数设置2 6 表3 5 手写体数据集上5 种聚类算法的聚类精度对比( ) 2 7 表4 1 手写体数字数据集在k m m d c 算法中的核参数设置3 3 表4 23 种核化和非核化算法在手写体数据集上的聚类精度对比( ) 3 3 表5 1c m d c ，c m v c 算法和k m e a n 算法在y a l e 数据集上的最高聚类精度比较4 l 表5 2 基于c c a 及其改进的算法在a r 数据集上最高聚类结果比较4 7 多视角判别聚类算法的研究 注释表 x ，y 仃 艿 p c ” k m e a n l d a ( f i s h e rl i n e a rd i s c r i m i n a n ta n a l y s i s ) k m l d a ( s i n g l ev i e wd i s c r i m i n a n tc l u s t e r i n g ) m v c ( m u l t i - v i e wk m e a l lc l u s t e r i n g ) m v d c ( m d c x m u l t i - v i e w d i s c r i m i n a n tc l u s t e r i n g ) m v d c 一2 ( t w o - v i e wd i s c r i m i n a n tc l u s t e r i n g ) m v d c - n ( n - v i e w d i s c r i m i n a n tc l u s t e r i n g ) m m d c ( m a r g i nb a s e dm u l t i - v i e wd i s c r i m i n a n tc l u s t e r i n g ) c c a ( c a n o n i c a lc o r r e l a t i o na n a l y s i s ) d c c a ( d i s c r i m i n a n tc a n o n i c a lc o r r e l a t i o na n a l y s i s ) l d c c a ( l 0 c a ld i s c r i m i n a n tc a n o n i c a lc o r r e l a t i o na n a l y s i s ) c m d c ( c c ab a s e dm u l t i - v i e wd i s c r i m i n a n tc l u s t e r i n g ) d c m d c ( d c c ab a s e dm u l t i - v i e wd i s c n m i n a n tc l u s t e r i n g ) l d c m d c ( l d c c a b a s e dm u l t i - v i e wd i s c r i m i n a n t c l u s t e r i n g ) k k m e 锄( k e m e lk m e a n ) k m d c ( k e m e lb a s e dm u l t i - v i e wd i s c r i m i n a n tc l u s t e r i n g ) k m m d c ( k e m e lb a s e dm m d c ) 输入样本 唧参数 核参数 典型相关系数 类别个数 样本个数 k 均值聚类 f i s h e r 线性判别分析 单视角判别聚类算法 多视角i e a r l 聚类 多视角判别聚类 两个视角的判别聚类 多个视角的判别聚类 基于m a r g i n 的多视角判别聚类 典型相关分析 判别型典型相关分析 局部判别型典型相关分析 基于c c a 的多视角判别聚类 基于d c c a 的多视角判别聚类 基于l d c c a 的多视角判别聚类 核k 均值聚类 核多视角判别聚类 核化基于l m 咖的多视角判别聚 类 第一章绪论 1 1 本课题的研究意义 聚类学习是一种无监督的机器学习技术，在日常生活中发挥着重要的作用【1 】【2 】。随着技术 的进步，数据的收集也越来越容易，如各种类型的贸易交易数据、w e b 文档数据【3 】、图像、基 因表达数据等，对这些数据进行恰当的聚类分析，能够发现其中相似的活动和数据，对以后活 动的开展产生有益的影响。 在迅猛发展的现代科技推动下，许多样本可以被两个或多个不同的方式表利4 】【5 l 【6 】，而获取 多种不同表示的数据也变得更容易和方便。例如，每一个网页中包含许多构成文章的单词，而 每一个指向该网页的超链接也由相关的单词及字符组成，因此一个网页可由网页的内容特征来 表示也可由指向该网页的链接特征来表示；一段电影通常由视频和音频这两个独立部分组成， 人在说话的时候身体的相关部位通常也会伴有相关的动作，比如人在说“是”的时候通常会点 头，在说“再见”的时候通常会有挥手的动作，因此可以将视频中人的行为用视频特征来表示， 或者用音频特征来表示。在日常生活中，摄像头的应用也越来越广泛，不论是同一个人还是同 一个物体都可以通过多个摄像头从多个角度观察到其特征，而不同的角度得到的特征在光照、 形态等各个方面都有所区别，不仅如此，对同一个视角得到的数据通过不同的转换，也可以得 到不同的特征值。直观上说，看到的越多，对事物理解的越细致。 在实际应用中，同一个事物经常可以以多种形状或者姿态展示在人的面前。正如古诗里所 说的“横看成岭侧成峰，远近高低各不同”，同一个物体在上面，侧面，下面看的时候，其都具 有不同的形态，对于每一个角度的观测本文称为一个视角，相应的每一个视角均可以得到相应 不同视角的数据。 不同方式得到的对同一事物的描述均可以多种方式表示，即所获取的数据常常可以由多个 视角表示，于是我们称之为多视角的数据，在一些科学文献以及实际应用中也被称为多表示的、 多类型的或者是多模态的数据7 】【8 1 【9 j 。由于多视角数据获取比较方便，并且在某些非理想条件下， 单视角的机器学习的性能会出人意料地大幅下降，所以，多视角学习日益受到众多研究者的关 注。并且，随着多视角数据的增加，研究如何找出多视角数据所包含的重要信息已成为当前机 器学习领域研究的热点，研究者已经在多视角机器学习方面取得了一定的成果，并运用到实际 的应用中【4 1 【5 】【1 0 1 1 1 1 1 。 许多的研究结果表明，相比仅使用一个视角的特征或者简单把所有视角的特征作为一个视 角来处理而言，多视角学习( m u t i - v i e wl e a r n i n g ) 通过恰当的融合不同视角的特征，通常可以获 得更好的结果。恰当的整合多视角的数据，并找到适合的多视角聚类的算法，对于当前的多视 1 多视角判别聚类算法的研究 角学习的研究及应用有很高的价值。 1 2 国内外研究现状 近些年，多视角学习的研究十分活跃，许多重要的国际学术会议都出现了多视角学习的相 关文章。国内外许多研究人员和机构已经在这个领域做了相关的理论和应用研究【4 】【坨l ，使多视 角学习的理论和方法不断发展和成熟，并被用于现实生活中的各个方面，如基于音频一视频信 号的语音识别系统，基于指纹、签名、语音等生物信息特征的身份识别【”】等。 多视角学习方法在机器学习领域最早始于y a r o w s k y 使用无指导的机器学习来进行语义消 歧【l6 】。y a r o w s k y 描述了一个对于词义模糊问题的算法，在这个算法中使用两个视角的分类器， 一个是基于单词局部内容的分类器，另外一个是基于同一篇文档中单词只有一个词性的分类器， 两个分类器可以相互迭代运行，得到超过了有监督的机器学习的正确率。b l u m 和m i t c h e l l 4 l 第 一次提出了c o - t r a i n i n g 算法，也称标准协同训练算法。标准协同训练算法的思想是在两个视角 上各自训练一个分类器，然后利用所得的分类器标记另一个视角上置信度较高的无标号的样本。 在网页分类实验中，一个视角是出现在网页中的单词，另外一个视角是指向网页的超链接中出 现的单词，标准协同训练在这个实验中，取得了较低的错误率，甚至低于使用有指导的学习的 错误率。协同训练算法由于其同时利用了有标号的样本和无标号的样本，最初作为一种半监督 学习方法，但是其利用多个视角来进行学习的思想影响到机器学习的其他方面，引起了广泛的 关注和研究。 c o - t r a i n i n g 算法基于两个前提假设：第一，使用任意一个属性集均可以进行有效分类：第 二，属性集之间的联系并不密切，即在给定标记条件下，每个属性集均条件独立于另一个属性 集【4 】。然而，在实际应用中，上述两个条件并不总是满足的。为克服这一缺点，很多后续的研 究者从理论和算法上对其进行了一系列的拓展1 2 】【1 刀，从而在不具有充分冗余以及属性集特征并 不条件独立的情况下亦能有效进行多视角学习。 c o l l i n s 和s i n g e r 认为c o - t r a i n i n g 算法的约束条件过于局限，并且很难构造这样的分类器。 为此，通过优化一个度量在不同视角中规则间的一致性的目标函数，提出了改进的c o - t r a i n i n g 算法【协l 。n i g a m 和g h a n i 在不具有冗余视图的条件下对c o - t r a i n i n g 算法的性能进行了研列1 2 l ， 他们把e m 算法和协同训练算法整合在一起，通过选择条件独立的特征作为协同训练算法的属 性集合，并通过比较朴素贝叶斯模型、期望最大模型和协同训练算法在各种不同条件下测试了 特征实验的效果，并且指出即使在样本本身无法自然分成两个视角，而样本也足够的大随机 将样本属性划分为两个视角也可以达到同样的效果，c o - t r a i n i n g 的效率优于单纯的e m 算法。 m u s l e a 等人在多个视角的数据集不一致或者不是足够大的时候引入了多视角验证算法1 1 9 1 ，使用 c 4 5 算法对视角中属性集的是否可以用来多视角的学习进行选择。z h o u 和“提出了一种既不 2 南京航空航天大学硕士学位论文 要求分冗余视图、也不要求使用不同类型分类器的t r i - t r a i n i n g 算法 1 4 1 。t r i - t r a i n i n g 使用集成 学习中经常用到的投票法来将三个分类器组成一个集成来实现对未见示例的预测，而不再象以 往算法那样挑选一个分类器来使用。 d a s g u p t a 在b i u m 等人的理论研究基础上，推导出了协同训练在视图间的条件独立性假设 成立下的的泛化误差界【13 1 ，并证明了c o l l i n s 的假设是正确的；a b e n y t 2 0 1 考虑到b l u m 和d a s g u p t a 等人提出的条件独立假设不总存在，建议用更加实用的弱独立假设取代原来的条件独立假设。 b a l c a n 等人进一步的研究【1 7 1 发现，对于协同训练技术而言，如果在每个视图上都能训练一个强 学习器，只要数据分布满足比弱独立性假设弱得多的扩张性假设即可。w a n g 和z h o u 在文献 2 3 】 中证明了只要两个学习器有较大的差异，就可以通过协同训练来利用未标记示例提高学习性能。 他们又做了进一步的分析，不仅解释了为什么在两个视图的条件独立性不成立时协同训练可以 有很好的效果，还解释了那些根本不利用两个视图的算法，例如文献【1 4 】【2 1 】奏效的原因。不仅 如此，w a n g 和z h o u 2 3 】还解释了为什么在实际使用协同训练时往往出现这样的情况，即在若干 轮协同训练之后如果再进行下去，不仅不能改善学习结果，有时甚至会导致性能下降的情况， 而从以往的理论分析来看，使用协同训练总可以使得泛化能力提高，甚至可以将弱学习器提高 到任意精度。 协同训练算法是监督和无监督学习的一个折中，它在不降低性能的前提下，尽量多的使用 未带标记的数据。它从一个小规模的带标记的样本开始，同时使用大规模的未带标记的样本来 学习，是一种半监督学习的方法。然而，b l u m 和m i t c h e l l 利用数据不同视图的思想为多视角学 习这一新的研究领域奠定了基础，这也使得其影响超越了半监督学习领域，为后续的研究者提 供了新的方向。 同时协同训练的思想被引入到机器学习的其他领域。在回归领域，z h o u 和“最早使用协 同训练技术进行半监督回归【2 5 1 ，他们提出了一个选择标记置信度最高的未标记样本的准则 标记置信度最高的未标记样本是在标记后与学习器的有标记训练集最一致的样本来克服示例的 属性是连续的实数值的问题，通过使用设置同一学习器的不同参数来生成两个初始学习器。 b r e f e l d 等人提出了e o r l s r t 捌，这是一种基于协同学习框架下的半监督回归算法，他们把基于 协同训练的半监督回归思想移植到正则化框架下，通过最小化不同视图下回归模型对未标记示 例的预测差异来改善各视图的回归模型，取得了较好的效果。 在多视角聚类领域，w a n g 等提出了多视角增强聚类算法，使用数据属性集之间的相关性 来提高聚类效剁9 】；k a i l i n g 等把基于密度的可以发现任意形状聚类的d b s c a n 算法扩展到多 视角中，使用概念的联合以及局部近邻的交互处理多种表示的样本1 7 1 ：b i c k e l 和s c h e f f e r t 2 4 1 提出 了多视角k 均值聚类算法( m v c ) ，通过用一个最大系数替代类别变量以得到一个多角度的聚类 算法。在每个视角上分别做k 均值聚类，然后把每个视角上的聚类标号提供给另一个视角上的 3 多视角判别聚类算法的研究 聚类使用，并通过实验证明多角度的g m e a n s 和e m 与单角度的相比性能有了较大的提高。t o n g 和h e 等把拉普拉斯特征映射进行降维的方法引入谱聚类中，提出了基于谱聚类的多视角聚类 算法【引。 1 3 本文的主要研究内容 针对同一个事物可以有多个表示的途径这一事实，本文在讨论多视角学习的基础上，结合 判别型聚类的方法，提出了基于多视角判别聚类的方法，并将其核化；同时将典型相关分析抽 取最大相关特征的作用和多视角聚类的方法结合，提出了基于c c a 及其改进的多视角聚类算 法。本文的主要工作包括以下几个部分： ( 1 ) k l l i e a n 聚类算法是一种非常流行的聚类学习方法，线性判别分析l d a 是一种降维方法， 这种降维方法可以求得使不同类别的样本差异最大，通过分析二者的共性，在判别聚类分析方 法的基础上，提出了多视角判别聚类( m u l t i - v i e wd i s c r i m i n a n tc l u s t e r i n g ，简记为m v d c ) 算法。 多视角判别聚类算法同时使用两个视角的数据，并同时在两个视角上进行交叉降维和聚类；同 时，将两个视角的判别聚类算法扩展到多个视角的判别聚类的形式。不仅如此，在多视角判别 聚类算法中引入基于m a r g i n 的l d a ，提出基于m a r g i n 的多视角判别聚类算法( m a r g i nb a s e d m u l t i v i e wd i s c r i m i n a n tc l u s t e r i n g ，m m d c ) ，该算法明显提高了聚类性能，且要高于简单的多 视角k n l e a n 聚类算法，且得到两个视角的聚类标号之间的差异性随着迭代次数的增加而降低， 并通过实际数据集验证了其有效性。 ( 2 ) 核方法是机器学习中的一个重要概念，将核函数引入到非线性映射和非线性函数，提 高了机器学习算法的推广能力。将核方法引入到多视角判别聚类算法中，将特定的在输入空间 进行聚类中心计算的核化g r f l e a n 算法用于多视角判别聚类中，得到基于核的多视角判别聚类， 并将其引入所提出基于m 画n 的多视角判别聚类算法，得到了其核化形式的算法。 ( 3 ) 典型相关分析( c c a ) 主要讨论两组变量间的相关性问题，被有效地用来做特征抽取，用 少数的几对特征之问的相关性来反映两组变量间的相关信息，使抽取得到的特征之间的相关最 大。本文在介绍典型相关分析( c c a ) 、判别型典型相关分析( d c c a ) 和局部判别型典型相关分析 ( l d c c a ) 的基础上，将特征抽取的方法引入到多视角聚类的框架中，得到多个基于c c a 及其 改进的多视角聚类算法，提高了聚类性能，并通过手写体数字数据集和其他数据集验证了其有 效性。 1 4 内容安排 本文的内容共分五章，具体内容安排如下： 第一章阐明了本文的研究意义，介绍了聚类学习和多视角学习的研究现状，并概述本文的 主要研究工作。 4 第三章在分析单视角判别聚类算法的基础上，结合多视角学习的思想，提出两个视角的判 别型聚类算法( m v d c 2 ) 及多个视角的判别聚类算法( m v d c n ) ；同时将常用改进的判别分析降 维方法应用到多视角判别聚类算法中，提出了基于m a r g i n 的多视角判别聚类算法( m m d c ) ，并 进行了大量的实验，验证了其有效性。 第四章首先从数学的角度讨论了核函数的基本理论和性质，并将核函数方法应用到多视角 聚类算法中，将特定的核k m c a n 聚类算法引入上述多视角判别聚类算法中，得到基于核的多视 角判别聚类，并在w e b k b 、o r l 和手写体数字数据集上验证了上述两个算法的有效性，取得 了预期的效果。 第五章介绍了典型相关分析( c c a ) 以及d c c a 及l d c c a 特征选择方法，并分别将其引入 多视角聚类的框架，得到基于c c a ( c m d c ) ，d c c a ( d c m d c ) 和l d c c a ( l d c m d c ) 的多视角 聚类算法，并验证了基于c c a 特征提取的多视角聚类算法的高效性。 第六章对本文的工作进行了简要的总结，并对今后的工作进行了展望。 5 多视角判别聚类算法的研究 第二章相关背景知识 2 1 聚类 机器学习是研究怎样利用计算机来模拟或实现人类学习活动的科学。近几年来，机器学习 的研究发展迅速，已经渗透到模式识别、计算机视觉、数据挖掘以及生物信息学等多个领域。 机器学习的研究具有重要的科学意义，聚类就是一种典型的机器学习技术。 2 1 1 聚类简介 聚类学习通过对一组无标记的训练样本进行学习，以发现训练集中隐藏的结构性知识。 聚类有着十分广泛的应用，一直是模式识别、数据挖掘、图像处理等领域的研究热点之一。“物 以类聚，人以群分”，在自然界中，存在着大量的聚类问题。所谓类，就是指相似元素的集合。 聚类的过程就是将物理或抽象对象的集合分成由类似的对象组成的多个类的过程。聚类与分类 的不同在于，聚类要求划分的类未知。在传统的的分类学中，人们主要依靠经验和专业知识来 实现分类，很少利用数学工具进行定量的分类。随着人类科学技术的发展，对分类的要求越来 越高，仅凭经验和专业知识难以确切地进行分类，于是人们逐渐地把数学工具引用到了分类学 中，形成了数值分类学，之后又将多元分析的技术引入到数值分类学形成了聚类分析。 聚类分析在图像处理、信息安全、数据分析等方面都有很广泛的应用。在图像处理中，可 以通过对模板匹配的结果，精确找出物体的运动曲线：在信息安全领域，可以通过聚类技术分 析网络流量的大小及网络访问的方式、状态判断网络状态。在生物学领域，聚类能用于推导植 物和动物的分类，对基因进行分类，获得对种群中固有结构的认识；在商业中，还可以通过用 户的消费信息，来推断该类型用户的购买能力，购买习惯等来进行广泛的市场营销活动的进行。 另外，聚类技术在地球观测数据库中确定相似的地区，对汽车保险单持有者进行分组，及根据 房子的类型、价值和地理位置对一个城市中房屋的分组上也发挥着作用。聚类技术还被应用于 对w e b 上的文档进行分类，以发现有价值的信息。技术的进步使得数据收集变得越来越容易， 使数据库规模越来越大，如各种类型的贸易交易数据、w e b 文档、图像、基因数据等，数据量 也随着增多，伴随着科学技术的发展及机器学习技术的成熟，采用聚类学习的方法自动的给这 些样本标号已成为一种不可避免的趋势。 2 1 2 聚类算法介绍 常用的聚类算法主要有划分方法、层次方法、基于密度的方法、基于网格的方法和基于模 型的方法啪1 嘲。各种方法的选择主要依赖于数据的类型、类别的个数和实际应用的特点。 6 少包含一个样本，每个样本必须属于且只属于一个类。代表算法有k - m e a n s 算法、k - m e d o i d s 算法2 引、c l a r a n s 算法1 2 9 1 。 ( 2 ) 层次方法。层次的聚类方法将数据对象组成一棵分层次的树【2 引，根据层次分解是自底 向上的还是自顶向下形成的，层次聚类方法可以进一步分为凝聚的( a g g l o m e r a t i v e ) 和分裂的 ( d i v i s i v e ) 层次聚类。层次聚类方法尽管简单，而合并或分裂点选择则非常关键，因为一旦一组 对象合并或分裂完成，它就不能被撤销，下一步的处理将在新完成的类上进行。这个规定由于 不用担心组合数目的不同选择，计算代价会比较小，在现实的应用中非常有用。但由于合并或 分裂的决定需要检查和估算大量的对象或结果，这种聚类不具有很好的可伸缩性。代表算法【2 町 有：b i r c h 算法、c u r e 算法、c h a m e l e o n 算法等。 ( 3 ) 基于密度的方法。基于密度的聚类方法将每一类看作是数据空间中被低密度区域分割 开的高密度区域。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的类。 d b s c a n 3 0 】是一个有代表性的基于密度的方法，它根据一个密度阀值来控制类的增长 o p t i c s 3 1 】是另一个基于密度的方法，它为自动的和交互的聚类分析计算一个聚类顺序。 ( 4 ) 基于网格的方法。基于网格的方法把对象空间量化为有限数目的单元，形成一个网格 结构。所有的聚类操作都在这个网格结构( 即量化的空间) 上进行。基于网格的聚类方法的主要 优点是处理速度快，其处理时间独立于数据对象的数目，只与量化空间中的每一维的单元数目 有关。s t i n g 算法利用存储在网格单元中的统计信息：w a v e c l u s t e r 算法利用一种小波变换方 法来聚类对象；而c l i q u e 算法是一种在高维数据空间中基于网格和密度的聚