1 概述 1
1.1 问题描述 1
1.2 方法进展 2
1.2.1 经典算法 3
1.2.2 高级算法 4
1.2.3 多源数据算法 5
1.3 半监督聚类 6
1.4 数据类型 7
1.4.1 属性数据 7
1.4.2 离散序列数据 10
1.4.3 时间序列数据 11
1.4.4 文本数据 12
1.4.5 多媒体数据 14
1.4.6 流数据 15
1.4.7 各类数据聚类技术汇总 16
1.5 衍生问题 17
1.5.1 特征选择 17
1.5.2 测度学习 18
1.5.3 聚类集成 18
1.5.4 软聚类 18
1.5.5 多解聚类 18
1.5.6 聚类验证 18
1.5.7 可视化与交互聚类 19
1.6 新的挑战 19
1.6.1 大数据聚类 19
1.6.2 多模数据聚类 19
1.6.3 深度聚类 19
1.7 结论 19
参考文献 20
2 基于模型的聚类 24
2.1 混合模型 24
2.1.1 混合模型简介 24
2.1.2 高斯混合模型 26
2.1.3 伯努利混合模型 27
2.1.4 混合模型选择 28
2.2 期望最大化算法 29
2.2.1 詹森不等式 29
2.2.2 期望最大化算法分析 30
2.2.3 期望最大化算法框架 32
2.2.4 期望最大化扩展算法 32
2.3 求解高斯混合模型 33
2.4 求解伯努利混合模型 34
参考文献 35
3 基于划分的聚类算法 37
3.1 划分方法概述 37
3.2 k-均值算法 38
3.2.1 目标函数 38
3.2.2 算法流程 40
3.2.3 性能分析 42
3.2.4 k的选择 42
3.2.5 初始中心点选择 44
3.3 类k-均值算法 46
3.3.1 k-中心点算法 46
3.3.2 k-中值算法 49
3.3.3 k-modes算法 50
3.3.4 模糊k-均值算法 51
3.3.5 核k-均值算法 52
3.3.6 二分k-均值算法 53
3.4 改进的k-均值算法 54
3.4.1 改进的k-均值算法概述 54
3.4.2 基于边界值的k-均值算法 54
3.4.3 阴阳k-均值算法 58
3.4.4 基于块向量的加速k-均值算法 62
参考文献 66
4 基于密度的聚类算法 68
4.1 密度算法概述 68
4.2 DBSCAN算法 69
4.2.1 基本定义及算法流程 69
4.2.2 算法分析 71
4.3 OPTICS算法 73
4.3.1 基本定义及算法流程 73
4.3.2 算法分析 77
4.4 DENCLUE算法 77
4.4.1 基本定义及算法流程 77
4.4.2 算法分析 79
4.5 DBSCAN、OPTICS、DENCLUE算法对比 81
4.6 其他算法 81
4.6.1 基于网格的聚类算法 81
4.6.2 基于共享最近邻的聚类算法 83
4.6.3 基于密度的不确定数据聚类算法 84
4.6.4 基于密度峰值的聚类算法 84
4.7 总结 86
参考文献 86
5 基于网格的聚类算法 88
5.1 网格算法概述 88
5.2 传统算法 90
5.2.1 GRIDCLUS算法 90
5.2.2 BANG算法 92
5.2.3 STING算法 93
5.3 自适应算法 95
5.4 轴平移算法 96
5.4.1 NSGC算法 97
5.4.2 ASGC算法 98
5.4.3 GDILC算法 99
参考文献 99
6 层次聚类算法 101
6.1 层次算法概述 101
6.2 聚合方法 102
6.2.1 Single-link方法 104
6.2.2 Complete link方法 106
6.2.3 簇均值方法 107
6.2.4 带权重的簇均值方法 108
6.2.5 质心方法 109
6.2.6 中间值方法 112
6.2.7 Ward方法 113
6.3 分裂方法 117
6.4 几种经典层次聚类算法 117
6.4.1 SLINK算法 117
6.4.2 CLINK算法 119
6.4.3 CURE算法 121
6.4.4 ROCK算法 122
6.4.5 BIRCH算法 124
6.4.6 Chameleon算法 125
6.4.7 DIANA算法 127
6.4.8 DISMEA算法 128
6.5 最新算法 129
6.5.1 贝叶斯层次聚类 129
6.5.2 互信息聚类 131
6.5.3 快速聚合层次聚类 132
参考文献 134
7 半监督聚类 136
7.1 约束信息 136
7.1.1 标签约束 137
7.1.2 成对约束 137
7.2 约束满足最大化 138
7.2.1 基于标签约束的算法 138
7.2.2 基于成对约束的算法 140
7.2.3 基于复杂约束的算法 141
7.3 半监督测度学习 142
7.4 混合方法 145
7.5 约束传播 146
7.5.1 标签约束传播 147
7.5.2 成对约束传播 149
7.6 主动学习 153
7.6.1 基于最远优先遍历策略的算法 153
7.6.2 改进的最远优先遍历策略算法 154
7.6.3 边界判定法 155
参考文献 155
8 谱聚类 157
8.1 谱聚类概述 157
8.2 谱聚类算法 158
8.2.1 非正则化的拉普拉斯矩阵 158
8.2.2 正则化的拉普拉斯矩阵 159
8.2.3 经典的谱聚类算法 160
8.2.4 谱聚类与图划分 162
8.2.5 谱聚类与随机游走 165
8.2.6 谱聚类相关问题 168
8.3 谱聚类图构造 170
8.3.1 ε-邻居法 170
8.3.2 k-最近邻法 170
8.3.3 完全连通法 171
8.4 大规模谱聚类 175
8.4.1 Nystr？m扩展 175
8.4.2 Nystr？m扩展与谱聚类 176
8.4.3 一次性抽样 177
8.4.4 增量抽样 178
8.5 半监督谱聚类 181
8.5.1 修改目标函数 182
8.5.2 约束信息的传播 184
8.5.3 核学习 184
参考文献 187
9 基于非负矩阵分解的聚类 190
9.1 非负矩阵分解 190
9.1.1 非负矩阵分解简介 190
9.1.2 基本非负矩阵分解方法 191
9.1.3 非负矩阵分解优化方法 191
9.1.4 非负矩阵分解扩展方法 193
9.1.5 非负矩阵分解方法的优势 196
9.1.6 非负矩阵分解方法的挑战 196
9.1.7 非负矩阵分解方法的应用 197
9.2 非负矩阵分解和k-均值算法 198
9.2.1 非负矩阵分解与k-均值算法的关系 198
9.2.2 正交非负矩阵分解和k-均值算法的等价性证明 198
9.2.3 正交非负矩阵分解聚类 199
9.2.4 正交非负矩阵三分解方法 200
9.3 对称非负矩阵分解和谱聚类 201
9.3.1 对称非负矩阵分解概述 201
9.3.2 正交对称非负矩阵分解和谱聚类的等价性证明 202
9.3.3 正交对称非负矩阵分解聚类 202
9.4 联合聚类 204
9.4.1 基于二分图的联合聚类 204
9.4.2 基于信息论的联合聚类 204
9.4.3 基于非负矩阵三分解的联合聚类 205
9.5 半监督非负矩阵分解 206
9.5.1 半监督非负矩阵分解框架 206
9.5.2 基本非负矩阵分解的半监督方法 206
9.5.3 对称非负矩阵分解的半监督方法 211
参考文献 213
10 高维数据聚类 216
10.1 高维数据的挑战 216
10.1.1 维度灾难 216
10.1.2 高维数据分析方法 219
10.2 无监督降维方法 219
10.2.1 特征选择 221
10.2.2 线性特征提取 222
10.2.3 非线性特征提取 228
10.3 子空间聚类 233
10.4 轴平行子空间聚类 235
10.4.1 子空间搜索策略 235
10.4.2 投影子空间聚类 236
10.4.3 软投影子空间聚类 238
10.4.4 子空间枚举聚类 241
10.4.5 混合方法 243
10.4.6 半监督子空间聚类算法 243
10.5 基于模式的子空间聚类 249
10.5.1 联合聚类概念 250
10.5.2 簇搜索策略 251
10.6 任意方向子空间聚类算法 254
10.6.1 基本原理 254
10.6.2 关联聚类算法 256
参考文献 257
11 图聚类 261
11.1 图聚类总论 261
11.2 图聚类基本理论 263
11.3 簇的识别方法 265
11.3.1 基于顶点相似度 265
11.3.2 基于局部关系 266
11.4 图划分算法 268
11.4.1 局部划分 268
11.4.2 全局划分 270
11.5 分裂方法 271
11.5.1 GN算法 271
11.5.2 模拟电路 273
11.5.3 基于信息中心度的算法 274
11.5.4 基于聚集系数的算法 274
11.6 基于模块的方法 275
11.6.1 基于模块的方法概述 275
11.6.2 模块度最优化 275
11.6.3 模块度的局限性 278
参考文献 280
12 不确定数据聚类 282
12.1 不确定数据聚类概述 282
12.2 基于密度的不确定数据聚类 284
12.2.1 FDBSCAN算法 284
12.2.2 FOPTICS算法 287
12.2.3 PDBSCAN算法和PDBSCANi算法 290
12.2.4 总结 296
12.3 基于划分的不确定数据聚类 296
12.3.1 UK-means算法 296
12.3.2 UK-means改进算法 297
12.3.3 CK-means算法 299
12.3.4 UK-medoids算法 300
12.3.5 MMVar算法 301
12.3.6 UCPC算法 303
12.3.7 总结 306
12.4 基于层次的不确定数据聚类 306
12.5 基于可能世界模型的不确定数据聚类 309
12.6 表征不确定数据聚类算法 310
12.6.1 不确定数据、不确定数据库、聚类算法的泛化定义 310
12.6.2 聚类可能世界 311
12.6.3 表征聚类 311
12.6.4 表征聚类的步骤 313
12.6.5 表征不确定数据聚类与基于可能世界模型的不确定数据聚类 314
12.7 基于概率分布相似度的不确定数据聚类 314
12.8 其他算法 317
12.8.1 不确定数据子空间聚类算法 317
12.8.2 不确定数据流聚类算法 319
12.8.3 不确定图聚类算法 321
12.9 总结 321
参考文献 322
13 多源相关数据聚类 324
13.1 多视角聚类 324
13.1.1 多视角聚类概述 324
13.1.2 基于期望最大化的多视角聚类 325
13.1.3 基于谱聚类的多视角聚类 326
13.1.4 基于非负矩阵分解的多视角聚类 331
13.1.5 数据部分对应和数据不对应的多视角聚类 338
13.1.6 其他算法 344
13.2 多任务聚类 344
13.2.1 基于共享空间学习的多任务聚类 345
13.2.2 多任务布莱格曼散度聚类 349
13.2.3 基于非负矩阵分解的多任务联合聚类 356
13.2.4 基于压缩差异性度量的多任务聚类 359
13.2.5 基于约束对称非负矩阵分解的多任务聚类 361
13.2.6 凸判别多任务聚类 364
13.2.7 自适应多任务聚类 368
13.3 多任务多视角聚类 371
13.3.1 多任务多视角聚类框架 371
13.3.2 多任务多视角聚类算法 372
13.4 迁移聚类 375
13.4.1 自学习聚类 375
13.4.2 迁移谱聚类 377
13.5 多模聚类 379
13.5.1 一致等周高阶多模聚类 379
13.5.2 约束驱动多模聚类 381
参考文献 385
后记 389