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

??

??

??