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  隱私保護(hù) 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  算法設(shè)計  16
2.1.2  算法分析  16
2.1.3  下界    25
2.2  k-均值 || 算法  27
2.2.1 并行算法設(shè)計  27
2.2.2 并行算法分析  28
第 3 章  Johnson-Lindenstrauss 降維引理  35
3.1  預(yù)備知識    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 章  核心集與近似質(zhì)心集  45
4.1  核心集   45
4.1.1  問題描述  45
4.1.2  核心集構(gòu)造算法    47
4.1.3  核心集結(jié)論的證明    49
4.2  -近似質(zhì)心集    53
4.2.1  -近似質(zhì)心集的定義和性質(zhì). 54
4.2.2  整數(shù)格上的 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-均值問題的雙準(zhǔn)則近似算法    95
6.1  線性規(guī)劃舍入算法  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  性質(zhì)  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  隱私保護(hù) 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  平方和設(shè)施選址問題  217
11.4.1  問題描述  217
11.4.2  連續(xù) SOS-FLP 的局部搜索算法   221
11.4.3  離散 SOS-FLP 的局部搜索算法   231
11.5  帶懲罰 -相似 Bregman 散度 k-均值問題    234
11.5.1  問題描述  234
11.5.2  帶懲罰-相似 Bregman 散度 k-均值問題的初始化算法  236
參考文獻(xiàn)  247
名詞索引  259
                       
??
??
??