k-均值问题的近似算法

k-均值是重要的聚类方法,本书系统介绍经典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.1k-均值问题1
1.2k-均值问题的重要变形7
1.2.1k-中位问题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.1k-均值++算法15
2.1.1算法设计16
2.1.2算法分析16
2.1.3下界25
2.2k-均值||算法27
2.2.1并行算法设计27
2.2.2并行算法分析28
第3章Johnson-Lindenstrauss降维引理35
3.1预备知识35
3.1.1基本概念35
3.1.2Brunn-Minkowski不等式36
3.2高维空间及其特性36
3.2.1超球体的几何特性37
3.2.2高维空间的概率集中性38
3.3随机投影定理和Johnson-Lindenstrauss降维引理40
3.3.1随机投影定理40
3.3.2Johnson-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.1k-中位问题的局部搜索算法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.2k-均值问题的局部搜索算法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.2r-容量约束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