《k-均值問題的近似算法》是清華大學出版社於2022年出版的圖書，作者是張冬梅、李敏、徐大川
基本介紹
- 書名：k-均值問題的近似算法
- 作者：張冬梅、李敏、徐大川
- 出版社：清華大學出版社
- 出版時間：2022年10月1日
- 頁數：276 頁
- 定價：69 元
- 開本：16 開
- 裝幀：平裝
- ISBN：9787302617563
內容簡介,圖書目錄,
內容簡介
k-均值問題是經典組合最佳化問題, 也是著名的NP-難問題之一, 相應的Lloyd算法是數據挖掘的 十大經典算法之一. k-均值問題在人工智慧、數據挖掘、理論計算機科學、運籌學和管理科學中有 著廣泛的套用. 本書介紹k-均值問題及其變形的基於隨機抽樣、降維、核心集、近似質心集、局部 搜尋、線性規劃捨入等技術的近似算法. 主要內容包括: 經典k-均值問題的近似算法, k-中位, 球面 k-均值, 魯棒k-均值, 帶約束的k-均值, 隱私保護k-均值, k-均值的其他變形等.
圖書目錄
第 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
