|
|
|
k-均值問題是經典組合優化問題，也是的NP-難問題之一，相應的Lloyd演算法是資料採擷的十大經典演算法之一、k-均值問題在人工智慧、資料採擷、理論電腦科學、運籌學和管理科學中有著廣泛的應用。本書介紹k-均值問題及其變形的基於隨機抽樣、降維、核心集、近似質心集、局部搜索、線性規劃舍入等技術的近似演算法，主要內容包括：經典k-均值問題的近似演算法，k-中位元，球面k-均值，魯棒k-均值，帶約束的k-均值，隱私保護k-均值，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 多交換局部搜索演算法
