k-均值問題的近似算法

定　價：￥69.00

作　者：	張冬梅、李敏、徐大川
出版社：	清華大學出版社
叢編項：
標　簽：	暫缺

購買這本書可以去

ISBN：	9787302617563	出版時間：	2022-10-01	包裝：	平裝-膠訂
開本：	16開	頁數(shù)：		字數(shù)：

內(nèi)容簡介

　　k-均值問題是經(jīng)典組合優(yōu)化問題，也是著名的NP-難問題之一，相應的Lloyd算法是數(shù)據(jù)挖掘的十大經(jīng)典算法之一. k-均值問題在人工智能、數(shù)據(jù)挖掘、理論計算機科學、運籌學和管理科學中有著廣泛的應用. 本書介紹k-均值問題及其變形的基于隨機抽樣、降維、核心集、近似質(zhì)心集、局部搜索、線性規(guī)劃舍入等技術(shù)的近似算法. 主要內(nèi)容包括：經(jīng)典k-均值問題的近似算法， k-中位，球面 k-均值，魯棒k-均值，帶約束的k-均值，隱私保護k-均值， k-均值的其他變形等.

作者簡介

　　張冬梅，山東建筑大學計算機學院副教授。1991年獲山東師范大學計算科學與技術(shù)專業(yè)理學學士，1999年獲山東工業(yè)大學計算機應用技術(shù)專業(yè)工學碩士，2012年獲山東大學計算機應用技術(shù)專業(yè)工學博士。2006年-2012年期間參與山東大學信息檢索實驗室研究工作，2014年8月-2015年8月在美國特拉華大學訪學一年，合作課題為醫(yī)學文本挖掘。研究方向為組合優(yōu)化、機器學習、數(shù)據(jù)挖掘、信息檢索等。主持或參加國家自然科學基金、山東省自然科學基金、山東省高?？萍加媱濏椖俊⑸綎|省信息產(chǎn)業(yè)廳、濟南市科技局等項目10余項。曾獲得山東省科學技術(shù)進步獎三等獎、山東省計算機應用優(yōu)秀成果獎二等獎、山東省軟科學優(yōu)秀成果獎三等獎。在北京航空航天大學出版社出版教材《操作系統(tǒng)》（主編），在山東大學出版社出版教材《C語言》（參編）、《計算機文化基礎(chǔ)》（參編）、《計算機引論》（參編）。擔任Asia-Pacific Journal of Operational Research客座編委。發(fā)表學術(shù)論文50余篇。

圖書目錄

第 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 章核心集與近似質(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-均值問題的雙準則近似算法 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 隱私保護 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 連續(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
參考文獻 247
名詞索引 259

??
??
??