该书是当前国际新兴的热门研究领域-关系数据挖掘-的首部有关关系数据聚类的奠基性专著。该书通过深入浅出的方法，系统地介绍了关系数据挖掘领域中的关系数据聚类的主要研究问题和广泛的重要应用方向。该书作者被国际学术界公认为最早从事关系数据聚类的学者之一，并一直在这一方向上发表有影响力的工作。该书凝聚了作者这些年来的最新研究成果，并以自成体系的方式由浅入深地完整地表述给读者，是当今了解关系数据聚类分析这一新兴热门课题的首选读物，具有很强的学术性。关系数据聚类是一个崭新的热门研究方向。它之所以能在短暂的时间内得到迅猛发展，就是因为它有广泛的应用前景。在如今社会的各个领域，从政府决策，到市场营销，到舆情分析，到社会关系网络分析，到生物信息学等，都其应用的广泛前景。由于该书也是广大从业人员必不可少的工具书，该书同时也有着极其广泛的市场需求前景。

第1章引言
1.1研究领域
聚类问题是数据挖掘和机器学习研究领域的基本问题。聚类分析是这样一个过程，它把数据对象集合划分成聚类，这样来自同一聚类的对象相似，来自不同聚类的对象不相似。
在文献中，很多聚类方法集中在“单一”的数据，这些数据对象用一个固定长度的属性矢量表示。然而，很多实际数据集合在结构上更加丰富，涉及多种类型对象，它们之间互相联系。例如，在一个文献库中，文献与关键词；在一个网页搜索系统中，网页、查询和网页用户；在营销体系中，商店、顾客、供应商、股东和广告媒体。我们称这些数据为关联数据，即数据对象之间互相有关联。
因为关联数据在不同重要应用中的惊人作用，关联数据得到越来越多的关注，如文本分析推荐系统、Web挖掘、网络广告、生物信息学、引用分析和流行病学。在不同的数据挖掘领域，不同的关联学习问题有不同的称呼。关联学习的一个重要任务是在关联数据中发现隐含团体（聚类），即关联数据聚类。下面是关联数据聚类的例子。
① 文本分析。从双类型关联数据，文献关键词数据中，学习文献聚类和关键词聚类。
② 推荐系统。基于用户聚类（团体）和电影聚类的电影推荐系统，从涉及用户、电影、演员的关联数据中学习。
③ 网上广告。基于关联数据库，其中广告人、投标人条件和关键字是内在互相联系的，广告聚类和投标人条件聚类可以从投标条款建议中学习。
④ 生物信息学。从基因、环境、标注的关键词的关联数据中，自动识别基因团（聚类）。
⑤ 研究团体挖掘和主题识别。从作者、论文、关键词组成的关联数据中，识别研究团体（作者聚类）和研究主题（论文聚类）。
一般而言，关联数据库包含三种类型的数据信息，即个体对象的属性、同类型对象的同质关联、不同类型对象的异质关联。例如，在一个论文和作者的科学出版物关联数据集合中，个人信息，如作者的联系方式是属性，论文间的引用关联是同质关联，论文与作者间的著作权关联是异质关联。在机器学习和统计学中，这些数据违反了经典的独立同分布假设，对传统的聚类方法提出巨大的挑战。
对关联数据聚类的挑战问题有两种结构，一种是单独聚类结构，另一种是集体聚类结构。
在单独聚类结构中，我们把关联数据转换成平面数据，然后单独聚类每个类型的对象。这个结构的一个直观方法是把所有的关联都转换成特征，然后直接应用传统聚类算法。另一方面，在集体聚类结构中，我们同时聚类不同类型的数据对象。与集体聚类结构比较，单独聚类结构有如下欠缺的地方。
首先，转换导致关联和结构信息丢失［48］。第二，在聚类关联数据时，传统聚类算法不能解决传播影响，即对象不同类型的隐含模式可能互相直接影响和间接影响（通过关联链）。第三，在一些数据挖掘应用中，用户不仅关心对象不同类型的隐含模式，而且关心涉及对象多种类型的互动模式。例如，在文献聚类中，除文献聚类和关键词聚类之外，文献聚类与关键词聚类之间的关联也是有用的信息。通过单独聚类对象的每个类型，发现这些互动模式是困难的。
另一方面，基于所有三种类型信息，学习局部和全局聚类结构。集体聚类结构有明显的好处，在集体聚类结构下，与关联数据的不同类型有不同的重点。这里有不同关联数据聚类的子领域：基于双类型异质关联数据库的集体聚类、多类型异质关联数据的异质关联数据聚类、同质关联数据的同质关联数据聚类、一般关联数据的一般关联数据聚类。
另一个有兴趣的注意点是重要聚类的数目问题，它在相关文献中有重要的意义，可以看作关联聚类的特殊情况。例如，图聚类分割可以看作单个类型关联数据库的聚类，它由同质类型关联（代表如图的亲密矩阵）的集体聚类组成。它出现在重要的应用中，如文件聚类和微阵列数据聚类。在联合聚类结构下，这可以规划为只有异质关联组成的双类型关联数据聚类。半监督聚类是一个特别的聚类类型，既使用已标记的数据，又使用未标记的数据。在11.3节中，我们将说明半监督聚类可以规划为聚类在单个类型关联数据上，数据由属性和同质类型关联组成。
虽然本书内容主要集中在集体聚类结构，但是也包括我们关于单独聚类结构的研究，特别是多视图关联数据聚类。因为在一些应用中，当在一个关联数据集中，大量的对象类型以复杂的方式互相联系时，我们希望关注数据对象的特定类型来减少模型的复杂度。
图1.1关联数据聚类不同领域之间的关联
图1.1说明了关联数据聚类不同领域之间的关联。总之，作为蓬勃发展的研究领域，关联数据聚类在广泛的应用范围兴起，在文献中也涉及一些重要的聚类问题，所以非常需要有一个关联数据聚类的实用算法推导和理论结构构建，这也是本书的主要目的。
1.2本书的内容和组织
本书的目标是为一个新的数据挖掘领域，关联数据聚类和一族不同关联聚类问题的新算法介绍一个新颖的理论结构。
本书的组织如下。全书包含引言、模型、算法和应用。引言部分定义关联数据聚类的领域并概述全书的内容；模型部分介绍不同类型关联数据聚类的模型公式；算法部分说明对应模型的不同算法；应用部分用广泛的实验结果展现模型和算法的应用。本书集中在6个关联数据聚类专题。
第一个专题是双类型异质关联数据库，即数据对象的双类型之间是异质关联。例如，一个文献集可以形式化为文献和关键词的双类型关联数据集，其中文献和关键词是异质关联。在文献中，双类型关联数据聚类也被称为集体聚类。对双类型异质关联数据，我们提出一个新的集体聚类结构，即块值分解 (block value decomposition，BVD)。对双类型关联数据，块值分解把关联数据矩阵分解为三个部分（行系数矩阵、块值矩阵、列系数矩阵）。在这个结构下，我们关注一个特殊已经非常流行的情况——非负关联数据，并提出具体新颖的集体聚类算法。算法基于更新规则，迭代计算三个分解矩阵。
第二个专题是关于双类型异质关联数据的更一般情况。多类型异质关联数据库可以形式化为不同结构的k部图。事实上，许多真实世界数据的例子涉及数据对象的多种类型，它们彼此互相联系，自然地形成数据对象异质类型的k部图。例如，分类挖掘中的文献、关键词、类别；网页搜索系统中的网页、查询要求、网页用户；科学出版档案室中的论文、关键词、作者和出版地点。我们提出一个通用模型，即网络关联摘要，从k部异质关联图发现隐含结构（局部聚类结构和全局团体结构）。模型提出非监督学习不同结构k部异质关联图的主要结构。在一个广泛失真标准下，通过构建一个网络关联摘要来近似原始的k部异质关联图，我们可以得到一个新颖的算法来确认k部异质关联图的隐含结构。
第三个专题部分是同质关联数据聚类。在异质关联数据中，我们有数据对象不同类型的异质关联。另一方面，在同质关联数据中，有单个类型数据对象之间的同质关联。同质关联数据同样在重要的应用领域兴起，如网页挖掘、社会关联分析、生物信息学、超大规模电路设计、任务调度。在文献中，图分割被看做一个同质关联数据聚类的特例。基本上图分割寻找稠密的聚类，对应内部连接非常强的子图。另一方面，同质关联数据聚类的目标更普遍，更具挑战性。它要确认稠密的聚类和稀疏的聚类。在这一章中，我们提出一个基于图近似的通用模型，从图中学习基于聚类结构的关联模式。模型推广了传统图分割方法，并适用于学习各种聚类结构。在这个模型下，我们得到一族算法，可以灵活地学习各种聚类结构，并易于吸收聚类结构较早的知识。
第四个专题是在关联数据最常见情况下的聚类，包含三种类型的信息，即个体对象的属性、同类型对象之间的同质关联、不同类型对象之间的异质关联。对聚类多类型相关的对象，如何同时利用好三种类型的信息是一个巨大的挑战，因为这三种类型信息有不同的形式和非常不同的统计特性。我们对关联聚类提出一个概率模型，也提供了一个主要结构以统一各种重要的聚类问题，包括传统以属性为基础的属性聚类、半监督聚类、集体聚类和图聚类。提出的模型旨在为数据对象的每个类型确定聚类结构和不同类型对象之间的互动模式。在这个模型下，我们提出在一个数目大的指数族分布下参数硬或软的关联聚类算法。
第五个专题是关于单独聚类结构。对于这个专题，我们对多视图非监督学习提出一个通用模型。提出的模型采用映射函数的概念，使不同模式空间的不同模式可以比较，因此最佳的模式可从多重表征的多种模式中学到。在这个模式下，我们为两种重要的情况，即非监督学习、聚类和谱降维，规划出两种具体的模型，为多视图聚类推导出一个迭代算法和一个简单算法，它能提供一个全局最优的多谱降维。随着边界信息，我们还扩展了进化聚类和非监督学习已提出的模型和算法。
第六个专题是关于我们在进化聚类方面的研究，可以把时间效应也纳入到关联聚类中。在数据挖掘领域，进化聚类是一个相对较新的研究方向。进化聚类是指场景，在场景中数据集在时间上演化；每个时间，数据集有一定数目的聚类；当数据集从一个时间演化到另一个时间，新的数据项可能加入到数据集中，数据集中存在的数据项可能消失。类似的，新的聚类可能出现，同时存在的聚类可能消失，所以数据项和聚类集合都可能随时间变化。与传统聚类算法比较，这对进化聚类算法问题提出一个巨大的挑战。在本书中，我们提出基于Dirichlet过程的进化聚类模型和算法。
1.3本书的读者
本书的预期读者包括该领域的研究人员和工程师，包括但不限于数据挖掘、机器学习、计算机视觉、多媒体数据挖掘、模式识别、统计学，也包括其他使用关联数据聚类技术的应用领域，如Web挖掘、信息检索、营销和生物信息学的人。由于本书资料的介绍是自包含的，同样可以作为对关联数据聚类这一新领域有兴趣人的理想参考书。另外，也包括任何对它有兴趣，或者工作领域需要这本参考书的人。最后，这本书还可以作为数据挖掘或机器学习课程的参考书。
1.4进一步的阅读
作为数据挖掘和机器学习领域新出现的研究热点，关联数据聚类可以说还在起步阶段。目前还没有专门的、重要的地点来出版这个领域的研究工作，所以作为本书进一步阅读的补充信息，这个领域的相关工作还可以在两个上级领域的文献中发现。
在数据挖掘领域，相关工作可能在重要的会议中发现，例如ACM关于知识发现和数据挖掘国际会议、IEEE关于数据挖掘国际会议和SIAM关于数据挖掘国际会议。特别地，相关工作可能发现在专注于关联学习领域的专题讨论会中，如统计关联学习专题讨论会。在期刊方面，数据挖掘领域的主要期刊可能包含关联数据挖掘相关工作，如IEEE关于知识和数据工程师的学报、ACM关于数据挖掘的学报。
在机器学习领域，有关工作可以在重要的会议中发现，如机器学习国际会议、神经信息处理系统、欧洲机器学习会议、欧洲在数据库中知识发现原则和实践会议、国际人工智能联合会议和学习理论会议。在期刊方面，机器学习方面的主要期刊也包含关联数据聚类的相关工作，包括机器学习研究和机器学习杂志。

《信息科学技术学术著作丛书》序
作者中文版序
前言
第一部分引言
第1章引言3
1.1研究领域3
1.2本书的内容和组织5
1.3本书的读者7
1.4进一步的阅读7
第二部分模型
第2章集体聚类11
2.1引言11
2.2相关工作12
2.3模型建立和分析13
2.3.1块值分解13
2.3.2NBVD方法15
第3章异质关联数据聚类18
3.1引言18
3.2相关工作19
3.3关联摘要网络模型20
第4章同质关联数据聚类24
4.1引言24
4.2相关工作26
4.3图逼近的社区学习27
第5章一般关联数据聚类32
5.1引言32
5.2相关工作33
5.3混合成员关联聚类34
5.4谱关联聚类36
第6章多视图关联数据聚类38
6.1引言38
6.2相关工作40
6.3背景和模型公式40
6.3.1多视图非监督学习的一般模型41
6.3.2多视图聚类和多视图谱嵌入43
第7章演化数据聚类45
7.1引言45
7.2相关工作46
7.3狄利克雷过程混合链48
7.4HDP演化聚类模型50
7.4.1HDP-EVO表示50
7.4.2对HDP-EVO的双等级CRP51
7.5无限层次隐马尔可夫状态模型52
7.5.1iH2MS的描述52
7.5.2iH2MS的扩展54
7.5.3HTM的最大似然估计54
7.6包含有HTM的HDP(HDP-HTM)55
第三部分算法
第8章集体聚类61
8.1非负块值分解算法61
8.2证明NBVD算法的正确性63
第9章异质关联数据聚类66
9.1关联摘要网络算法66
9.2聚类方法的统一71
9.2.12部谱图分割71
9.2.2有特征减少的二进制数据聚类72
9.2.3信息理论的集体聚类72
9.2.4K均值聚类73
第10章同质关联数据聚类74
10.1硬CLGA算法74
10.2软CLGA算法75
10.3平衡CLGA算法79
第11章一般关联数据聚类81
11.1混合成员关联聚类算法81
11.1.1有指数族的MMRC81
11.1.2蒙特卡洛E步83
11.1.3M步83
11.1.4硬MMRC算法86
11.2谱关联聚类算法88
11.3对聚类的一个统一观点91
11.3.1半监督聚类91
11.3.2集体聚类92
11.3.3图聚类93
第12章多视图关联数据聚类95
12.1算法推导95
12.1.1多视图聚类算法95
12.1.2多视图谱嵌入算法97
12.2扩展和讨论99
12.2.1演化聚类99
12.2.2有补充信息的非监督学习100
第13章演化数据聚类101
13.1DPChain推理101
13.2HDP-EVO推理102
13.3HDP-HTM推理104
第四部分应用
第14章集体聚类109
14.1数据集和实现细节109
14.2评价指标110
14.3结果和讨论110
第15章异质关联数据聚类114
15.1数据集和参数设置114
15.2结果和讨论117
第16章同质关联数据聚类119
16.1数据集和参数设置119
16.2结果和讨论120
第17章一般关联数据聚类123
17.1图聚类123
17.2双聚类和三聚类124
17.3关于演员-电影数据的案例研究126
17.4谱关联聚类应用127
17.4.1在双类型的关联数据上聚类127
17.4.2在三种类型关联数据上聚类129
第18章多视图和演化数据聚类132
18.1多视图聚类132
18.1.1合成数据132
18.1.2真实的数据134
18.2多视图谱嵌入135
18.3半监督聚类137
18.4演化聚类138第五部分总结
第19章总结143
参考文献146