k-均值問題的近似算法

第1章 緒論
1.1 k-均值問題
1.2 k-均值問題的重要變形
1.2.1 k-中位問題
1.2.2 球面k-均值問題
1.2.3 魯棒k-均值/中位問題
1.2.4 帶約束的k-均值問題
1.2.5 隱私保護k-均值問題
1.2.6 泛函k-均值問題
1.2.7 模糊C-均值問題
1.2.8 其他變形

第2章 k-均值初始化方法
2.1 k-均值++演算法
2.1.1 演算法設計
2.1.2 演算法分析
2.1.3 下界
2.2 k-均值｜｜演算法
2.2.1 平行算法設計
2.2.2 平行算法分析

第3章 Johnson-Lindenstrauss降維引理
3.1 預備知識
3.1.1 基本概念
3.1.2 Brunn-Minkowski不等式
3.2 高維空間及其特性
3.2.1 超球體的幾何特性
3.2.2 高維空間的概率集中性
3.3 隨機投影定理和Johnson-Lindenstrauss降維引理
3.3.1 隨機投影定理
3.3.2 Johnson-Lindenstrauss降維引理

第4章 核心集與近似質心集
4.1 核心集
4.1.1 問題描述
4.1.2 核心集構造演算法
4.1.3 核心集結論的證明
4.2 ε-近似質心集
4.2.1 ε-近似質心集的定義和性質
4.2.2 整數格上的k-均值問題
4.2.3 稀疏實例
4.2.4 一般實例

第5章 k-中位和k-均值問題的局部搜索演算法
5.1 k-中位元問題的局部搜索演算法
5.1.1 問題描述
5.1.2 單交換局部搜索演算法
5.1.3 簡單情形的局部比值
5.1.4 一般情形的局部比值
5.1.5 多項式時間近似演算法
5.1.6 多交換局部搜索演算法
5.2 k-均值問題的局部搜索演算法
5.2.1 單交換局部搜索演算法
5.2.2 多交換局部搜索演算法