张冬梅，山东建筑大学计算机学院副教授。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

??

??

??