（计算机应用技术专业论文）科技项目管理中专家与申请书分组匹配算法的研究.pdf

摘要 在模式识别领域中，聚类是一种非常重要的技术而联合聚类是将两种异质 对象同时进行聚类分析在科技项目管理中，需要组织专家对申请项目的申请书 进行评审，评审时需要将参与评审的专家分成若干组，每个组专家的人数基本相 同，申请项目的申请书分成若干组，每个组的申请书数目基本相同，使一个专家 组评审一个申请书组，专家组中的专家对申请书组中的申请书都比较熟悉我们 可以借鉴联合聚类的思想，对专家和申请书进行分组和匹配目前常见的联合聚 类算法主要有两种，基于二部图谱划分的联合聚类方法和基于信息论的联合聚类 方法 本文介绍了联合聚类的概念以及发展情况叙述了目前常见的联合聚类算法， 包括基于二部图的谱聚类算法、等周二部图划分方法、基于信息论的联合聚类算 法和其他一些聚类算法，重点介绍了基于二部图的谱聚类算法和基于信息论的联 合聚类算法的理论基础与关键步骤 本文提出了科技项目管理中对专家和申请书分组匹配模型，模型控制了每个 专家组和申请书组成员的个数，使得专家和申请书均匀分布到各个组中，并使一 个专家组评审一个申请书组，提出了专家与申请书关联强度的计算公式，提出并 实现了基于二部图谱划分的专家与申请书分组匹配算法和基于信息论的专家与申 请书分组匹配算法，证明了这两个算法的正确性 实验表明了基于二部图谱划分的专家与申请书分组匹配算法和基于信息论的 专家与申请书分组匹配算法在实际应用中都可以正确的对专家和申请书分组和匹 配，都有很好的表现，但基于信息论的方法更简单易懂并有很大的扩展性 关键词：科技项目管理；联合聚类：二部图谱划分；信息论 类号：t p 3 9 1 3 i nt h ed o m a i no fp a t t e r nr e c o g n i t i o n ，o n eo fv e r yi m p o r t a n tt e c h n o l o g i e s i s c l u s t e r i n g t h et e c h n o l o g yo fc o c l u s t e r i n gi s t oc l u s t e rt w ok i n d so fh e t e r o g e n e o u s o b j e c t ss i m u l t a n e u s l y i nt h ep r o c e s so ft e c h n o l o g yp r o j e c tm a n a g e m e n t ，w en e e dt o o r g a n i z ee x p e r t st oe v a l u a t et h ea p p l i c a t i o n so f t h ep r o j e c t a l le x p e r t sa r ed i v i d e di n t o s e v e r a lg r o u p s ，a l lg r o u p sh a v et h es a m en u m b e ro fe x p e r t s t h ea p p l i c a t i o n sa r e i nt h e s a m es i t u a t i o n a l le x p e r t sa r ef a m i l i a rw i t ht h ea p p l i c a t i o n st h e yn e e dt oe v a l u a t e w e c a i lu s em ei d e ao fc o c l u s t e r i n gt od i s t r i b u t ea n dm a t c h t h ee x p e r t sa n da p p l i c a t i o n sa n d l e tag r o u po fe x p e r t st oe v a l u a t eag r o u po fa p p l i c a t i o n s a tp r e s e n t t h e r ea r e 锕ok i n d s o fc o m m o nc o c l u s t e r i n ga l g o r i t h m s ，w h i c ha r ec 0 c l u s t e r i n gu s i n gb i p a r t i t es p e c t r a l g r a p hp a r t i t i o n i n ga n d i n f o r m a t i o nt h e o r e t i cc 0 。c l u s t e r i n g t h i sp a p e ri n t r o d u c e st h ec o n c e p ta n dd e v e l o p m e n to fc o c l u s t e r i n g ，f o c u s e so n t h e b a s i ct h e o r c r i e sa n dk e ys t e p so fc o c u l s t e r i n gu s i n gb i p a r t i t es p e c t r a lp a r t i t i o n i n ga n d i n f o m l a t i o nt h e o r e t i cc o c l u s t e r i n g , d e s c r i b e so t h e rc o m m o na l g o r i t h m so fc o c l u s t e r i n g , w h i c ha r ec o c l u s t e r i n gu s i n gb i p a r t i t ei s o p e r i m e t r i cg r a p hp a r t i t i o n i n ga n do t h e r c o - c l u s t e r i n ga l g o r i t h m s t h i sp a p e rp u t sf o r w a r dam o d e lo fd i s t r i b u t i n ga n dm a t c h i n ge x p e r t sa n d a p p l i c a t i o n si nt e c h n o l o g yp r o j e c tm a n a g e m e n t ，w h i c hc o n t r o l st h en u m b e ro fe x p e r t s a n da p p l i c a t i o n si ne a c hg r o u pa n dl e tag r o u po fe x p e r t st o e v a l u a t eag r o u po f a p p l i c a t i o n s t h i sp a p e r a l s op u t sf o r w a r daf o r m u l at oc o m p u t et h ea s s o c i a t i o ns t r e n g t h b e t w e e ne x p e r t sa n da p p l i c a t i o n st h e np r o p o s e sa n di m p l e m e n t st h ed i s t r i b u t i n ga n d m 删i 玛a l g o r i t h m o fe x p e r t sa n da p p l i c a t i o n su s i n gb i p a r t i t es p e c t r a lp a r t i t i o n i n ga n d t h ed i s t r i b u t i n ga n dm a t c h i n ga l g o r i t h m o fe x p e r t sa n da p p l i c a t i o n sb a s e do n i n f o r m a t i o nt h e o r e t i ca n dp r o v e dt h ev a l i d i t yo f b o t ha l g o r i t h m s t h ee x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mu s i n gb i p a r t i t es p e c t r a lp a r t i t i o n i n ga n d t h ea l g o r i t h mb a s e do ni n f o r m a t i o nt h e o r e t i cc a nd i s t r i b u t ea n dm a c t he x p e r t sa n d a p p l i c a t i o n sc o r r e c t l yi np r a c t i c a la p p l i c a t i o na n dt h ea l g o r i t h mb a s e do ni n f o r m a t i o n t h e o r e t i ci sm o r ee a s y - t o u n d e r s t a n da n d h a v eg r e a te x p a n s i b i l i t y k e y w o r d s ：t e c h n o l o g yp r o j e c tm a n a g e m e n t ；c o - c l u s t e r i n g ；b i p a r t i t es p e c t r a lg r a p h p a r t i t i o n i n g ；i n f o r m a t i o n t h e o r e t i c s c l a s s n o ：t p 31 9 3 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国 家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：惨县嘻 签字日期：钞噌年月厂日 导师签名： 签字日期：如扩年月d - 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名：确醢签字日期：v g 年6 月f 日 致谢 本论文的工作是在我尊敬的导师瞿有利副教授的悉心指导下完成的，从论文 的选题，论文的撰写，一直到论文的最终定稿，瞿老师一直给予我细心的指导和 无尽的关怀瞿有利副教授严谨的治学态度和科学的工作方法给了我极大的帮助 和影响在此衷心感谢两年来瞿有利老师对我的关心和指导 衷心感谢黄厚宽教授和田盛丰教授，两位教授宽广豁达的长者风范、以及严 谨的治学态度始终让我深深地敬仰他们在此期间对我的关心和鼓励让我深受感 动 王志海老师悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向王志海老师表示衷心的谢意 于剑老师对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心 的感谢 在实验室工作及撰写论文期间，张俊三、吴学良、蒋敏梅等同学对我论文研 究工作给予了热情帮助，在此向他们表达我的感激之情 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业 最后，衷心地感谢在百忙之中审阅论文的各位老师和专家，恳请各位老师多 多批评指j 下，并提出宝贵的意见 1 1课题背景 1 引言 近几十年来，科技的进步，特别是信息产业的发展，把人类带入了一个崭新 的信息时代从二十世纪8 0 年代开始，随着计算机应用的普及和互联网技术的不 断发展，许多工作可以通过计算机，通过互联网来完成，人们开始寻求用计算机 和网络技术方便快捷的完成以前需要很大的人工成本和时间成本才能完成的工 作以前的科技项目管理系统，都是通过上级单位人工书写项目书，邮寄给想要 申请完成该项目的下级单位，下级单位书写项目申请书，邮寄给上级单位，上级 单位组织专家评审申请书，给通过审核的单位邮寄审核结果通知书，下级单位才 可以实施项目，期间提交各种验收报告，上级单位再审核等等繁琐复杂的工作特 别是组织专家评审申请书的工作，必须通过人工考虑各种情况，选择合适的专家 为申请书评审打分在目前基于w e b 的科技项目管理系统中，可以通过w e b 完成 提交申请及各种报告的提交与审核工作，但是对于组织专家评审申请书的工作还 是采用人工分配的方式，对专家和项目申请书进行分组和匹配因此，需要有一 种自动算法可以自动对专家和项目申请书进行分组和匹配，从而节约人工成本， 使项目管理过程更方便快捷 因为需要对专家和项目申请书这两种有关联的对象同时进行分组和匹配，我 们可以联想到使用联合聚类的方法所谓联合聚类，就是把多种属性不同但相互 关联的数据同时进行聚类比如在对文本集合的分析和挖掘中，常常需要对文本 和从文本中抽取的特征词进行联合聚类，也就是说，在把文本聚集成若干类别( 如 科技类文章、文化类文章、评论类文章等) 的同时，把特征词也聚集成一些相应 的类别( 如科技类词汇、文化类词汇、评论类词汇等) ，以便进一步分析各文本类 别和各特征词类别之间的相互关系在对专家和项目申请书的分组匹配过程中， 我们也可以使用联合聚类的方法，在把专家聚集成若干分组( 按研究方向、教育 背景、科研能力等几种因素综合考虑) 的同时，把参评的申请书也聚集成若干分 组( 按研究方向、论文单位、申请主要负责人等因素考虑) ，最后选择一个专家组 对一个申请书组的申请书进行评定 1 2本文所完成的工作 在科技项目管理中，为了将参与评审的专家和申请书分组匹配，我们利用了 联合聚类的思想，目前对联合聚类的研究已经有了很大的进展联合聚类方法主 要分两大类，一类是基于二部图划分的联合聚类方法：它将数据对象用二部图的 形式表示，对数据对象的聚类可以被看作是二部图的划分问题，使用最广泛的图 划分算法是基于谱聚类的思想构建的，近年来还出现了其它的图划分方法另一 类是基于信息论的联合聚类方法：通过最小化互信息损失选择最优的聚类方法此 外，还出现了一些其它的联合聚类方法但是，这些联合聚类方法都不能直接用 于对评审专家和申请书的自动分组和匹配，需要对这些联合聚类方法进行扩充和 改进以适应科技项目管理中的特殊需求 在上述背景之下，本文完成的工作是： 首先，介绍联合聚类的概念及基本理论 其次，介绍典型的联合聚类算法及其变形，包括基于二部图的联合聚类方 法，基于信息论的联合聚类方法，和其它一些联合聚类方法 第三，分析了在科技项目管理系统中对专家与申请书分组匹配的特殊要 求，提出了对专家和申请书分组匹配的建模方法，并提出了基于二部图谱 划分的专家与申请书分组匹配算法和基于信息论的专家与申请书分组匹 配算法两种算法 第四，使用模拟数据对两种算法进行测试，测试算法是否符合科技项目管 理系统对于专家和申请书的自动分组和匹配 最后，得出结论，上述两种算法都可以达到对专家和申请书自动分组和匹 配的效果，但是基于信息论的专家与申请书分组匹配算法更有效并适用于 大规模数据，该算法还可以应用于其它领域 1 3论文的组织安排 本文的主要框架和结构如下： 第1 章给出了课题的出发点以及研究的问题及范围，叙述了在科技项目管理 系统中需要应用联合聚类思想对专家和申请书进行分组和匹配的需求，叙述了联 合聚类的相关概念，介绍了本文所完成的工作 第2 章是全文的理论基础，介绍了对于联合聚类研究的历史和联合聚类的基 本概念和理论，以及几种典型的联合聚类方法 第3 章分别介绍了基于二部图划分方法的联合聚类，基于信息论方法的联合 聚类，和其它一些联合聚类方法在基于二部图的划分方法中，介绍了二部图模 型的概念和谱图划分及等周二部图划分两种基于二部图的划分的联合聚类方法 2 第4 章是本文的重点部分，首先分析了在科技项目管理中对专家和申请书进 行分组匹配的特殊需求，提出了两种异质对象集分组匹配解决模型，并给出了在 科技项目管理中对专家和申请书分组匹配模型和专家对于申请书熟悉程度的计算 公式 第5 章是本章的核心部分，提出了在科技项目管理中的专家与申请书分组匹 配算法，分别是基于二部图谱划分的专家与申请书分组匹配算法和基于信息论的 专家与申请书分组匹配算法，并给出了算法正确性的证明 第6 章给出了本文的算法实验过程和结果，提出了两个模拟数据集，演示了 算法在两个数据集下的运算主要过程，并表明了算法最后的结果与实际需求相符 第7 章总结全文，对本课题研究做了分析和总结，分析了基于信息论的专家 与申请书分组匹配算法的适用于大规模数据并有很大扩展性的优点，并给出了本 课题将来的研究内容和方向 3 2 联合聚类理论概述 所谓聚类，就是将一个对象的集合分割成几个类，每个类内的对象之间是相 似的，但与其它类的对象是不相似的例如对文本的聚类，根据文本的特征( 比 如关键词) ，可以把它们分成科技类文本，文化类文本，娱乐类文本等从聚类对 象的属性来分，聚类可以分为同质对象的聚类分析和异质对象的联合聚类分析在 同质对象的聚类分析中，对象集是由若干同种类型的样本组成的，例如在图像聚 类中，对象集由一些图像对象组成，而在文本聚类中，对象集由若干文本样本组 成近几十年来，同质对象的聚类分析已经在模式识别领域中被深入和广泛的研 究，并被广泛的应用到机器学习和数据挖掘领域罩解决这种问题的常见算法有k 均值聚类算法 1 、最大似然估计算法 1 、无监督贝叶斯学习算法 1 以及谱聚类 算法 2 等 近年来，在越来越多的应用中人们需要对多种相互关联的异质对象进行联合 聚类所谓联合聚类，是指把多种属性不同但相互关联的对象同时进行聚类例 如在文本聚类中，常常需要把文本和文本的关键词同时聚类在聚类文本的时候 不只考虑特征词的信息，还需要考虑词所构成的词簇的信息，同时，也根据文档 簇对特征词进行聚类，最终将文档按照具有的特征词的相似性聚成簇，将特征词 按照所在文档的相似性聚成簇联合聚类的优势主要有两点：一是利用词簇信息 聚类文档聚类文档，大规模的降低了聚类维数，并且对文档间距离的度量更加恰 当；二是可以挖掘出更多有用的信息，得到文档簇与词簇的对应信息，这一对应 信息可以用于文档类别和词类别的相互描述，同时词聚类的结果本身也可以用于 文本挖掘、信息检索中 与文档和特征词类似，还有许多其它需要联合聚类分析的例子，例如市场分 析系统中的顾客、商品和供货商，研究支持系统中的论文、作者和会议等，它们 属于异质对象，对于这些相互关联的异质对象的联合聚类分析也简称为异质聚类 联合聚类的思想最早可以追述到1 9 7 2 年j a h a r t i g a n 的文章 3 ，在 3 中， 作者通过局部贪婪分裂过程层次聚类矩阵中的行和列，这是最早出现的联合聚类 算法，但这一思想很多年都没有被推广直到2 0 0 0 年，y c h e n g 和g m c h u r c h 提 出了基于方差的联合聚类算法并应用于生物基因数据中 4 ，这篇论文至今仍是生 物基因表达联合聚类中最重要的文献i s d h i l l o n 分别在2 0 0 1 年和2 0 0 3 年提出 了两类算法，前者基于二部图划分思想 5 ，后者基于信息论的思想 6 ，近几年 提出的联合聚类方法，大多是基于这两种思想的改进 两种异质对象的联合聚类，主要是依据这两种对象间的关系，而不考虑这两 种对象各自内部的关系，这完全符合二部图的特性，因此可以将两种对象及它们 4 的相互关系用二部图表示那么对这两种对象的联合聚类问题，很自然的转换为 了二部图的划分问题但是找到图的最小割的顶点划分是一个n p 完全问题，根据 谱图理论，可以通过对矩阵的奇异值分解得到图划分的最优解，因此i s d h i l l o n 利用谱图理论的谱聚类算法对二部图进行划分m r e g e 等基于经典等周问题设计 了等周二部图划分算法 7 ，划分图的依据是寻找具有最小周长与体积比的顶点集 合，得到的划分就是最优解 两个对象的互信息是指在一个对象给定的情况下另一个对象的不确定性的减 少程度，或者说一个对象含有另一个对象的信息的多少将聚类前两种异质对象 的第一种表示成x ，第二种表示成y ，将聚类后含有簇信息的第一种对象表示成j ， 含有簇信息的第二类对象表示成p 如果在聚类后含有簇信息的两类对象的互信息 ，( j ，穸) 与聚类前的互信息i ( x ，y ) 非常接近，则说明这样的聚类过程对于两种对象 的关联信息损失不大，那么可以认为这样的算法得到的聚类效果比较好，因此可 以用聚类前后互信息的损失作为衡量聚类算法的优劣基于互信息的联合聚类算 法就是利用这一思想，将互信息的损失作为目标函数，在给定聚类数的条件下， 尽量降低聚类前后互信息的损失在 6 中，i s d h i l l o n 将聚类前后互信息的损 失等价于概率分布p 和9 的k u l i b a c k - l e i b l e r ( k l ) 距离，其中p 表示聚类前两种 对象的分布，口表示聚类后两种对象的分布k l 距离用来衡量两个随机分布的差 距，当两个随机分布相同时k l 距离为0 ，当两个随机分别差距增加时，k l 距离也 随之增加因此i s d h i l l o n 将算法的目标函数转化为求p 和g 的k l 距离最小 此外，也出现了一些其它种类的联合聚类方法，诸如基于矩阵分解的算法和 相互加强聚类 在本文中，我将重点介绍几种典型的联合聚类算法及其变形，并对基于二部 图的谱图划分方法和基于信息论的联合聚类方法进行改进 3 1概述 3 典型联合聚类算法及其变形 目前出现的联合聚类方法主要可以分为两大类，一类是基于二部图划分的联 合聚类方法：它将数据对象用二部图的形式表示，对数据对象的聚类可以被看作 是二部图的划分问题，使用最广泛的图划分算法是基于谱聚类的思想构建的，近 年来还出现了其它的图划分方法另一类是基于信息论的联合聚类方法：通过最 小化互信息损失选择最优的聚类方法此外，还出现了一些其它的联合聚类方法 3 2基于二部图划分方法的联合聚类 基于二部图划分的方法广泛应用于异质对象的聚类 5 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 】主要 思想是将异质对象聚类中数据及其关系建模成二部图，寻找二部图的最优切割， 通过对二部图的划分将原始数据进行聚类不同的二部图划分方法产生不同的联 合聚类算法，本节首先介绍二部图模型，然后介绍这类方法中几种有代表行的联 合聚类算法 3 2 1二部图模型 在图论中，图g = ( y ，e ) 包括顶点集y = l ，2 ，l v i ) 和带有权值铂的边 i j ) 的集合，图的邻接矩阵m 定义为： m = 协0 嚣有边也办 b ， i ，其它 、7 所谓二部图，是指图中的顶点可以被分成两个不相交的子集，每个子集内部 的任两个点之间都没有边相连，而所有的边都只是连接来自不同子集的顶点 6 图3 1 二部图模型 f i g u r e3 1t h eb i p a r t i t eg r a p hm o d e l 在图3 1 中，长方形和椭圆表示两种异质对象，分别对应于对象集括缸，, x 2 ， ) 和降 y t , y 2 ， y n ) ，我们可以看到，图中的所有边都是连接异质的两个对象 的这样，一个二部图图可以由一个三元组g = x e ) 来表示，其中x 和】，是顶点 集矿的两个异质子集，满足x n y ：- 口，x u y = v , e 是连接两个异质对象的边的集合， 即庐心少i e x , 如果我们用彳来表示集合彳和j ，的关系矩阵，其中爿u 锄 那么图3 1 所示的二部图邻接矩阵可以写为如下形式，其中前i n 个顶点表示来自j 的对象，后1 1 个顶点表示j ，中的对象 m = 僻吾) 2 ， 肚【彳t oj ( 3 2 ) 于是，我们可以通过对二部图邻接矩阵的划分，完成对两个异质对象的联合 聚类 3 2 2二部图谱聚类算法 近几十年来，谱聚类【2 ，1 4 1 得n t 广泛的关注与研究，它是一种基于谱图分解 【1 5 】的算法，是图论和矩阵的谱分解理论在聚类方面的结合应用 在谱聚类中，人们用图来对集合中的对象以及它们之间的关系进行建模：用 图中的顶点来代表集合中的对象，用图中的边来表示对象之间的关系，而关系的 强弱则用边的权重来表示众所周知，聚类是将一个对象的集合分割成几类，每 个类内的对象之间是相似的，但与其他类的对象是不相似的那么在上述谱聚类 的图模型中，我们就要把原图切分成几个子图，使得每个子图的内部边的权重相 对来说比较大，而连接各个子图的边的权重比较小，也就是使得切分子图是需要 切掉的边的权重之和最小这样，聚类问题就可以转化为图的切分问题假设在 7 二类聚类问题中，顶点集矿被切分为两个子集所和圪，那么它们之间的割( c u t ) 损 失定义为： c u t ( k ，匕) = m 驴 ( 3 3 ) 拒巧，吃 割的定义很容易的扩展到k 个顶点子集，即： c u t ( k ，圪) = c u t ( k ，巧) ( 3 4 ) i 是j 的女个簇，仅，轧，或) 是y 的，个簇c 。和c y 是两个映射： q ：“，而，) 专 l ，芟2 ，夏) ( 3 1 0 ) q ：饥，y ：，y 。 专积，致，剪) ( 3 1 1 ) 简写为j = c x ( x ) ，矿= c y ( 】，) ，文和分别是石和】，的确定性函数的随机变 量 给定聚类的类别数后，聚类质量用互信息 1 6 】损失来衡量，i ( x ，y ) - i ( 爻，p ) ( 在 行簇数和列簇数给出的约束下) ，目的是最小化这个损失，也就是最大化，( j ，矿) 互 信息可以用以下公式来计算： 删 y ) 2 ；莓p k j ，) 1 0 颤器) ( 3 1 2 ) 联合聚类互信息的损失可以通过计算一个k u l l b a c k l e i b e r 散度 1 6 】而得到这 样， z ( x ，y ) 一i ( 爻，t ) = d ( p ( x ，y ) iq ( x ，y ) )( 3 1 3 ) 这里d ( | j - ) 表示k u l l b a c k l e i b l e r 散度( 交叉熵) ，q ( x ，y ) 的形式为： q ( x ，y ) = p ( 囊，多) p ( xj 受) p ( yj 争) ，x 曼，y 夕 ( 3 1 4 ) 由此可以推出： i ( x ，y ) - i ( 文，p ) - d ( p ( x ，y ) llq ( x ，y ) ) 2 莓军萎萎p ( x ，y ) l o g 景等( 3 1 5 ) 为了方便的描述有关联合聚类( c r ，c r ) 的算法和证明，我们可以考虑以只 j ，p 的联合概率分布，即假定x 和y 的联合概率分布矩阵为p 似e 冀，矿) ， 我们有： (x，ypy ，曼，多) = pl x ，夕) pl 7 x ，y i “x ，多) ( 3 1 6 )l x ，x ，y ，=，y ，y ，k j l b ， q7 x ，y ，9 ) = ，9 ) ( x jj ) 79 )(317)lxyxp l xppl y 1 q，y ，2，y ，l x ， y jl j 由此我们可以通过下式来表示联合聚类互信息的损失： i ( x ，y ) 一i ( 文，p ) = d ( p ( x ，y ) iq ( x ，y ) ) = d ( p ( x ，y ，殳，它) lq ( x ，y ，文，叠) ) ( 3 1 8 ) 通过推导可以得出： d ( p ( x ，y ，文，圣) l q ( x ，y ，殳，鼋) ) = p ( x ) d ( p ( y lx ) i iq ( yi ：未) )( 3 1 9 ) i x ：c x ( j ) 巧 d ( p ( x ，y ，文，它) i q ( x ，y ，文，量) ) = p ( y ) d ( p ( x y ) i iq ( xi ) ) ) ( 3 2 0 ) ，y ：c , t ( y ) = 夕 其中q ( yj ) = q ( yi 夕) g ( 夕ij ) ，q ( x i 多) = g ( 工l 童) 口( 引夕) ，证明过程这里不赘述 这样，我们就可以通过交互的计算行聚类和列聚类来极小化互信息的损失， 并在最优的情况下得到联合聚类的结果i s d h i l l o n 证明了这种交互式计算可以 迭代进行，并且迭代过程是收敛的于是可以得出以下联合聚类算法： 1 2 表3 3 基于信息论的联合聚类算法 一 一一! i ! 1 2 ：j1 2 1 o 磐垒! i 2 21 垒2 堡：i 22 2 ：三! ：! 璺呈量一一 一一 算法基于信息论的联合聚类算法 输入：集合x 和y 的联合概率分布矩阵p 矽，x 的分类个数k ，y 的分类个数， 输出：集合x 和y 的联合聚类结果映射函数c x 和c y 1 初始化：设t = 0 ，初始化最初的映射函数c 和c ，计算分布g ( ( j ，矿) ， g o ( x i j ) ，g o ( 】，l p ) 和g ( 】，l 劝，1 叠k 2 重新对行进行聚类：对每一行x ，使用下面的公式计算它所属新的簇 c ! 引( 工) = a r g m i n ；d ( p ( ylx ) i lg “( yl 舅) ) 并使母“ = 畔 3 计算分布g ( 川( 膏，矿) ，g 【川( x l 譬) ，g ( 川( 】，i 矿) 和g ( 川( x i 夕) ，l 夕， 4 重新对列进行聚类；对每一列y ，使用下面的公式计算它所属新的簇 母+ 2 ( 石) = a r g m i n ；d ( p ( xly ) l iq ( t + d ( xi 夕) ) 并使础+ 2 = c 5 计算分布g ( m ( j ，矿) ，g ( m ( xi 膏) ，g ( m ( 】，l 矿) 和g ( m ( 】，l 量) ，1 曼七 6 如果d ( p ( x ，y ) l lg ( x ，l ，) ) 一d ( p ( x ，y ) 8g 件2 ( x ，y ) ) 的值足够小( 比如说1 0 3 ) ， 则停止计算并输出q = 畔+ 2 ，g = 母+ 2 否则使t = t + 2 ，回到第二步继续计 算 在应用中，算法表现出了缓解稀疏高维问题的能力对于词文档使用联合聚 类的结果优于没有任何词聚类的文档聚类这是因为联合聚类的每一次迭代中都 进行了一次适当的维约简，并且比标准一维聚类方法需要估计更少的参数这种 算法比二部图谱分解算法的效率要高，而且可以处理大规模的数据集 3 4其它的联合聚类方法 b l o n g 等提出了一种新的联合聚类框架，称作块值分解( b l o c kv a l u e d e c o m p o s i t i o n , b v d ) 【1 7 】它将联合聚类建模成三矩阵因数分解的优化问题，主 要思想是：一个二维并矢数据矩阵( d y a d i cd a t am a t r i x ) 能够被分解成三部分：行 系数矩阵r 、块值矩阵b 和列系数矩阵g 系数表示行和列的度，这个度与行列的 簇关联通过最小化目标函数：f ( r ，b ，c ) 刮iz r b c1 1 2 对数据矩阵r l * m 矩阵z 进 行块值分解，同时满足约束v 移：r 。0 且c ，0 ，其中i 是f r o b e n i u s 矩阵范式， r ，b 和c 分别是刀k ，k x ，和，m 矩阵，k ，l 并且z m 块值矩阵是数据矩阵 中隐藏块结构的清楚简洁的表现在这个框架下，开发了一种非负并矢数据的联 1 3 合聚类算法，称作非负块值分解( n b v d ) ，n b v d 在b v d 的基础上增加了噩，0 的 约束，n b v d 算法基于乘法更新规则迭代地计算三个分解矩阵，即： 局卜篆 ( 3 2 1 ) 岛卜岛器 ( 3 2 2 ) g 卜q 善兰堕 ( 3 2 3 ) 【b r 1 r b c ) v 通过每次迭代将行和列的聚类完成维约简，使得算法较好的适用于数据挖掘 应用中的高维稀疏数据 b ol o n g 等在 1 3 中提出了一种利用谱聚类的方法聚类多种类型相关数据的方 法该算法具有谱聚类方法的简单性，适用于具有多样结构的关系数据，并且具 有充分的理论支持它的贡献有三点：首先，提出了一个通用模型，相关矩阵的 集合因数分解，从而基于特征信息和关系信息发现多类型对象的隐藏结构通过 多类型对象的同时聚类，这个模型对每种类型的数据进行维约简通过共享因子 的相关因数分解，不同类型对象的隐藏结构可以在模型下相互影响除了每种类 型数据的簇结构，这个模型也提供了在不同类型对象簇之间的关系第二，在这 个模型下，产生了一个新颖的算法谱关系聚类，可以同时聚类多种类型且相 互关联的数据对象通过迭代的将每种类型的数据对象嵌入低维空间，算法受益 于不同类型数据对象的隐藏结构之间的相互影响算法具有谱聚类方法的简单性， 同时也适用于具有多样结构的关系数据理论分析和实验结果说明了算法的有效 性第三，现有的谱聚类算法可以被看作提出的模型和算法的具体情况，这为理 解算法间的联系提供了统一的见解 具体地说，给出m 个的数据对象集合，它们具有不同的类型且彼此相关， x 。= 而，x 。) ，l = x m ，x r a n 。) ，我们希望同时把五聚成毛个簇，把 以聚成吒个簇一方面，将多类型相关数据( m u l t i t y p er e l a t i o n a ld a t a ，m t r d ) 看作一个关系矩阵的集合，在这个集合中的每一个矩阵尺( ，r 几巩是表示对象集 五与x j 的关系矩阵，矩阵元素r 用( o 表示和之间的关系；另一方面，对象集 合五有自己的特征，用特征矩阵，u r “，元素碟表示对象的第g 个特征 值，f 是置的特征数 两个有关联的对象集合置和x ，的聚类结构可以反映成关系矩阵的三因数分 解r 寥c ( o a ( o ( c 1 r 1 2 ，其中c o ，1 妓l 是五的簇指示矩阵，c 2 = 1 表示五 中的第p 个对象与第g 个簇相关，兰l 罐= 1 ；类似的c n o ，l ；a 扩r ”- 1 4 是簇关联矩阵，表示置中的第p 个簇和x j 中的第g 个簇之间的关联如果鼍 有特征矩阵，( r 哳，它的簇结构反映为，( ) 的因数分解f 7 ) c 曰( n ，其中 c ( 0 3 k l 是簇指示矩阵，曰el r k , 。, 是特征基础矩阵，包括特征空间中的岛个 基本( 聚类中心) 向量 基于上面的讨论，我们可以把多类型相关数据的联合聚类描述为如下的最优 化问题：给定m 个正数玩) 倚s 。和多类型相关数据，瓦) ，关系矩阵集合 r 僭r ) l 型s 翩，特征矩阵集合 f u r 嘶哳) l g 如，权值蟛，1 彬( b i r ，多类型相 关数据的联合聚类任务是最小化： 三= 蟛i | r 抑一c o 彳驴( c ) ri | 2 + 姑| lf n c b o0 2 ( 3 2 4 ) i | | i 裳求矩阵的f r o b e n i u s 范数这j 模型被称作相关矩阵的联合因数分 解( c o l l e c t i v ef a c t o r i z a t i o no nr e l a t e dm a t r i c e s ，c f r m ) 不失一般性，我们重新定义簇指示矩阵c ( ) ： r 1 嘤： 赤栅掣 ( 3 2 5 ) 1 0 ，其它 其中l 群l 表示五的第g 个簇的对象数目，这里( c “) r c u = 厶，厶，是毛毛的 单位矩阵因此，我们的任务是最小化： m i nl ( 3 2 6 ) ( d ) 7 c ( o = k 幽 ( g e 盈j l “ - ， e r 哳 镕 根据定理：“如果矩阵c ，a 和b 是这个目标等式的最优解，那么有 a ( u 1 = ( c ( j ) 7 r 扩7 和b = ( c ( 。) r f 成立 ，我们可以将目标函数简化为只是 c ( ，的函数，从而推出如下理论：“l 的最小化问题等价于最大化问题： ( 渺m a 引x 蝴。( 一彬护( ( r 咒聃r c ) + l 搿纠细彬t r ( ( c 勺7 r 州c1 c 7 ) r ( ) r c ) ) ( 3 2 7 ) 使用迭代算法确定等式的上述最大化问题的最优解，即，在迭代的每一步只 与一个矩阵c ，有关，同时固定其它的矩阵c d ，p ，l p ，j m ，经过推导， 每一步的迭代任务等价于最大化问题： ( c 黔； ，护( ( c ( ，) 7 m 朋c ( ，) ( 3 2 8 ) 其中 m p = 谚( ，p ( f p ) r ) + 彬( 尺c 气c 一7 ( 尺西) r ) p j m + yw 乡( ( 尺( 彦) ，c ( ，( c u ) r 尺( 彦) ( 3 2 9 ) j _ 。 l s j p 是一个对称矩阵我们放松c ( 力为一个标准正交矩阵，根据k y f a n 理论：“如 果m 是一个有特征值五五以和相应的特征向量u = ，】，那么 ：。丑= m a x r x 吐t r ( x r m x ) ，此外，最优的彳由 。，】q 给出，q 是一个任意 的直交矩阵因此，我们可以用膨( p 的前k 。个特征向量更新c ( p ) ，迭代步骤结 束后，用k 均值将c 转换为簇指示矩阵 b m a n d h a n i 等提出了一种两步划分凝聚算法，层次地联合聚类文档一词划 分步骤用于识别子矩阵，这些子矩阵形成凝聚步骤中的叶子结点 1 8 互相加强聚类是一种聚类多种类型相关对象的方法，基本思想是：以数据的 初始聚类结构作为起始；对于每种类型的对象，根据相关对象的簇信息，产生新 的约简特征；基于新的特征，用传统的聚类方法聚类每种类型的对象；回到第二 步直到算法稳定基于这个思想，z e n g 等在 1 9 2 0 通过迭代加强聚类过程改进 对相互关联的数据对象的聚类质量，但是在这个方法中，没有健壮的目标函数， 也没有有效性和正确性( 收敛性) 的理论证明 1 9 通过一个迭代加强聚类过程，用数据对象问的关系改进聚类质量，同时， 相关数据对象关系产生的链结构用来区别对象的重要性，这个重要性也用于进一 步改进聚类结果实验结果显示，本方法不仅有效地克服高维关系空间引起的数 据稀疏问题，也极大的改进聚类的准确性 该方法的产生出于如下三点考虑：首先，相互影响的数据对象之间的关系往 往是稀疏的，聚类算法不得不处理高维特征向量；第二，对于确定的应用，相同 类型的数据对象可能在聚类过程中起着不同的作用，例如，正如大家所熟知的， 一些w e b 页面是比其它的页面更具有权威性，明显的，在聚类的时候统一对待所有 的w e b 页面是不合适的；最后，数据对象间的一些关系可能仅仅在聚类过程中被发 现，不能在指派给数据对象的特征中反应出来因此， 1 9 提出了一种聚类多类 型相关数据对象的框架r e c o m ，这个框架充分发掘了这些对象之间的关系在这个 框架下：首先指出数据对象在类型内和类型间的关系，并且将这些关系表示成数 据对象的特征因此对象间的相似性不仅包括它们自己的属性的相似性，也包括 它们的关系的相似性第二，类型间的关系用来加强相关对象的聚类过程即， 一种类型对象的聚类结果形成一个新的特征空间，被投影和传播到其它类型的对 象，然后，用这个更新的特征空间对其它相关类型的对象聚类这样的迭代加强 过程在每一个对象类型上执行，直到所有类型的数据聚类达到稳定第三，根据 类型间和类型内的关系产生的链结构，给数据对象指派不同的权重通过在聚类 中使用对象的加权和，一个改进的直接k 均值聚类算法被用于确定簇中心 1 6 3 5联合聚类算法总结 联合聚类的很多算法是基于谱图划分理论的基于图划分理论的谱聚类方法 聚焦于根据优化预定义的标准函数找到图的最好分割标准函数的优化通常导致 图相似矩阵中奇异向量或特征向量的计算谱聚类算法将数据矩阵形式化为二部 图并求图的最优标准分割，由于二部图的特性，这些算法要求不同类型的对象一 定具有一对一的关系目前谱聚类算法的研究中仍存在一些问题，如切割点的选 择，簇的数量的确定，因为谱方法没有全局目标函数所以难以