基于近邻思想和同步模型的聚类算法

目录
第1章 聚类算法与空间索引结构基础 1
1.1　背景与意义 1
1.2　聚类算法简介 2
1.2.1 基于划分的聚类算法 2
1.2.2 层次聚类算法 3
1.2.3 密度聚类算法 4
1.2.4 网格聚类算法 4
1.2.5 模型聚类算法 5
1.2.6 图聚类算法 5
1.2.7 其他聚类算法 5
1.3　聚类算法的研究现状及发展趋势 5
1.4　同步聚类 7
1.4.1 同步的起源与发展 7
1.4.2 同步聚类的起源与发展 7
1.5　近邻思想及同步模型在聚类分析中的应用 11
1.6　空间索引结构基础 12
1.7　本书的主要内容 13
第2章 基于近邻图与单元网格图的聚类算法 14
2.1　基本概念及性质 15
2.2　基于近邻图的聚类算法 20
2.2.1 CNNG算法示例 20
2.2.2 CNNG算法描述 22
2.2.3 CNNG算法的复杂度分析 22
2.2.4 CNNG算法的改进 23
2.3　基于单元网格图的聚类算法 23
2.3.1 CGCG算法的预处理 24
2.3.2 CGCG算法预处理步骤的复杂度分析 24
2.3.3 CGCG算法描述 25
2.3.4 CGCG算法的复杂度分析 25
2.4　算法实现与改进的若干方法及细节 25
2.4.1 多维网格划分法 25
2.4.2 多维索引树结构 26
2.4.3 近邻点集的构造 27
2.4.4 ? 近邻单元网格集的构造 28
2.4.5 区域是否存在交集的判定 31
2.5　本章小结 32
第3章 基于近邻势与单元网格近邻势的聚类算法 33
3.1　基本概念 33
3.2　基于近邻势的聚类算法 35
3.2.1 CNNI算法描述 35
3.2.2 CNNI算法的说明 36
3.2.3 参数? 的设置 37
3.2.4 CNNI算法的改进版本 37
3.2.5 CNNI算法的变种版本 38
3.3　基于单元网格近邻势的聚类算法 40
3.3.1 CIGC算法描述 40
3.3.2 CIGC算法的复杂度分析 43
3.3.3 CIGC算法的参数设置 43
3.4　本章小结 44
第4章 快速同步聚类算法 46
4.1　基本概念 47
4.2　快速同步聚类算法的三种具体版本 48
4.2.1 SynC算法描述 48
4.2.2 基于R树的快速同步聚类算法 49
4.2.3 基于多维网格和红黑树的快速同步聚类算法 50
4.2.4 FSynC算法的一些知识 53
4.2.5 FSynC算法的复杂度分析 54
4.2.6 FSynC算法的参数设置 57
4.3　本章小结 57
第5章 基于Vicsek模型线性版本的同步聚类算法 58
5.1　基本概念及性质 58
5.2　有效的ESynC算法 62
5.2.1 有效的ESynC算法描述 62
5.2.2 比较Kuramoto扩展模型、Vicsek模型的线性版本
及Vicsek模型的原始版本 63
5.2.3 ESynC算法的复杂度分析 68
5.2.4 ESynC算法的参数设置 68
5.2.5 ESynC算法的收敛性 68
5.2.6 ESynC算法的改进 69
5.3　本章小结 69
第6章 基于线性加权Vicsek模型的收缩同步聚类算法 71
6.1　基本概念 71
6.2　SSynC算法的对比与分析 73
6.2.1 SSynC算法描述 73
6.2.2 比较SynC算法、ESynC算法和SSynC算法的动态
同步聚类过程 75
6.2.3 SSynC算法的复杂度分析 83
6.2.4 SSynC算法的参数设置 83
6.2.5 SSynC算法的收敛性 86
6.2.6 SSynC算法的改进 86
6.3　本章小结 87
第7章 基于分而治之框架与收缩同步聚类算法的多层同步聚类方法 88
7.1　MLSynC 88
7.1.1 使用MLSynC的条件 88
7.1.2 MLSynC的两层框架算法描述 90
7.1.3 MLSynC的递归算法描述 91
7.2 MLSynC的分析 92
7.2.1 比较SynC算法、ESynC算法、SSynC算法和
MLSynC的同步聚类过程 92
7.2.2 MLSynC的复杂度分析 98
7.2.3 MLSynC的参数设置 99
7.2.4 MLSynC的收敛性 100
7.2.5 MLSynC的改进 100
7.3　本章小结 100
第8章 基于ESynC算法与微聚类合并判断过程的组合聚类算法 101
8.1　基本概念及性质 102
8.2　组合ESynC算法与微聚类合并判断过程的聚类方法 103
8.2.1 CESynC算法描述 103
8.2.2 CESynC算法中微聚类的合并策略 104
8.2.3 CESynC算法中微聚类的合并判断方法 106
8.2.4 CESynC算法的复杂度分析 107
8.2.5 CESynC算法的参数设置 108
8.3　本章小结 108
第9章 近邻同步聚类模型与指数衰减加权同步聚类模型的
比较与分析 110
9.1　基本概念 110
9.2　基于同步模型的聚类算法框架 112
9.2.1 CNNS 112
9.2.2 CEDS 113
9.3　复杂度分析 114
9.3.1 算法9-1的复杂度分析 114
9.3.2 算法9-2的复杂度分析 115
9.4　参数的优化确定 116
9.5　本章小结 116
第10章 总结与展望 117
10.1　总结 117
10.2　展望 117
参考文献 119
附录A 128
致谢 134