k-均值问题的近似算法

　　k-均值问题是经典组合优化问题， 也是著名的NP-难问题之一， 相应的Lloyd算法是数据挖掘的 十大经典算法之一. k-均值问题在人工智能、数据挖掘、理论计算机科学、运筹学和管理科学中有 着广泛的应用. 本书介绍k-均值问题及其变形的基于随机抽样、降维、核心集、近似质心集、局部 搜索、线性规划舍入等技术的近似算法. 主要内容包括： 经典k-均值问题的近似算法， k-中位， 球面 k-均值， 鲁棒k-均值， 带约束的k-均值， 隐私保护k-均值， k-均值的其他变形等.

　　张冬梅，山东建筑大学计算机学院副教授。1991年获山东师范大学计算科学与技术专业理学学士，1999年获山东工业大学计算机应用技术专业工学硕士，2012年获山东大学计算机应用技术专业工学博士。2006年-2012年期间参与山东大学信息检索实验室研究工作，2014年8月-2015年8月在美国特拉华大学访学一年，合作课题为医学文本挖掘。研究方向为组合优化、机器学习、数据挖掘、信息检索等。主持或参加国家自然科学基金、山东省自然科学基金、山东省高校科技计划项目、山东省信息产业厅、济南市科技局等项目10余项。曾获得山东省科学技术进步奖三等奖、山东省计算机应用优秀成果奖二等奖、山东省软科学优秀成果奖三等奖。在北京航空航天大学出版社出版教材《操作系统》（主编），在山东大学出版社出版教材《C语言》（参编）、《计算机文化基础》（参编）、《计算机引论》（参编）。担任Asia-Pacific Journal of Operational Research客座编委。发表学术论文50余篇。

第 1 章  绪论    1
1.1  k-均值问题  1
1.2  k-均值问题的重要变形    7
1.2.1  k-中位问题    7
1.2.2  球面 k-均值问题  8
1.2.3  鲁棒 k-均值/中位问题  9
1.2.4  带约束的 k-均值问题  11
1.2.5  隐私保护 k-均值问题  12
1.2.6  泛函 k-均值问题    13
1.2.7  模糊 C-均值问题  13
1.2.8  其他变形  14
第 2 章  k-均值初始化方法  15
2.1  k-均值 算法  15
2.1.1  算法设计  16
2.1.2  算法分析  16
2.1.3  下界    25
2.2  k-均值 || 算法  27
2.2.1 并行算法设计  27
2.2.2 并行算法分析  28
第 3 章  Johnson-Lindenstrauss 降维引理  35
3.1  预备知识    35
3.1.1  基本概念  35
3.1.2  Brunn-Minkowski 不等式  36
3.2  高维空间及其特性  36
3.2.1  超球体的几何特性    37
3.2.2  高维空间的概率集中性   38
3.3  随机投影定理和 Johnson-Lindenstrauss 降维引理    40
3.3.1  随机投影定理  40
3.3.2  Johnson-Lindenstrauss 降维引理    42
第 4 章  核心集与近似质心集  45
4.1  核心集   45
4.1.1  问题描述  45
4.1.2  核心集构造算法    47
4.1.3  核心集结论的证明    49
4.2  -近似质心集    53
4.2.1  -近似质心集的定义和性质. 54
4.2.2  整数格上的 k-均值问题  55
4.2.3  稀疏实例  57
4.2.4  一般实例  61
第 5 章  k-中位和 k-均值问题的局部搜索算法    67
5.1  k-中位问题的局部搜索算法    67
5.1.1  问题描述  67
5.1.2  单交换局部搜索算法    68
5.1.3  简单情形的局部比值    68
5.1.4  一般情形的局部比值    78
5.1.5  多项式时间近似算法    80
5.1.6  多交换局部搜索算法    83
5.2  k-均值问题的局部搜索算法    87
5.2.1  单交换局部搜索算法    87
5.2.2  多交换局部搜索算法    91
第 6 章  k-均值问题的双准则近似算法    95
6.1  线性规划舍入算法  95
6.2  局部搜索算法 106
第 7 章  有序 k-中位问题  113
7.1  问题描述  113
7.2  近似算法  114
7.2.1  算法框架    114
7.2.2  矩形有序 k-中位问题的近似比分析 116
7.2.3  一般有序 k-中位问题的近似比分析 123
第 8 章  球面 k-均值问题  127
8.1  问题描述  127
8.1.1  概述  127
8.1.2  性质  129
8.2  球面 k-均值问题的初始化算法    132
8.2.1  问题描述    132
8.2.2  可分离球面 k-均值问题的近似初始化算法  133
8.2.3  推广的球面 k-均值问题的近似算法 140
8.3  局部搜索算法 142
8.3.1  单交换的局部搜索算法   142
8.3.2  多交换的局部搜索算法   148
第 9 章  鲁棒 k-均值问题  152
9.1  带惩罚的 k-均值问题  152
9.1.1  概述  152
9.1.2  单交换局部搜索算法  152
9.1.3  多交换局部搜索算法  158
9.2  带惩罚 k-中位/均值问题局部搜索算法    162
9.2.1  问题描述    163
9.2.2  算法及分析    163
9.3  带异常点 k-中位/均值问题局部搜索算法  171
9.3.1  问题描述  171
9.3.2  算法描述  172
9.3.3  近似比分析    173
第 10 章  带约束 k-均值问题    181
10.1  问题描述    181
10.2  带约束 k-均值问题的剥离封闭算法   183
10.2.1  单纯形引理  184
10.2.2  剥离封闭算法  188
10.2.3  剥离封闭算法分析  190
10.3  带约束 k-均值问题的选择算法  197
10.3.1  下界约束 k-均值问题的选择算法  197
10.3.2  r -容量约束 k-均值问题的选择算法  198
10.3.3 色谱 k-均值问题的选择算法  198
第 11 章  其他变形    199
11.1  隐私保护 k-均值  199
11.1.1  差分隐私概念    199
11.1.2  差分隐私 k-均值问题描述   200
11.1.3  差分隐私常用的机制   201
11.1.4  高维差分隐私 k-均值问题   202
11.2  泛函 k-均值问题  206
11.2.1  问题描述  206
11.2.2  泛函 k-均值问题的初始化算法  209
11.3  模糊 C-均值问题  211
11.3.1  问题描述  211
11.3.2  模糊 C-均值问题的初始化算法. 214
11.4  平方和设施选址问题  217
11.4.1  问题描述  217
11.4.2  连续 SOS-FLP 的局部搜索算法   221
11.4.3  离散 SOS-FLP 的局部搜索算法   231
11.5  带惩罚 -相似 Bregman 散度 k-均值问题    234
11.5.1  问题描述  234
11.5.2  带惩罚-相似 Bregman 散度 k-均值问题的初始化算法  236
参考文献  247
名词索引  259
                       
??
??
??