k-均值問(wèn)題的近似算法

定　價(jià)：￥69.00

作　者：	張冬梅、李敏、徐大川
出版社：	清華大學(xué)出版社
叢編項(xiàng)：
標(biāo)　簽：	暫缺

購(gòu)買這本書(shū)可以去

ISBN：	9787302617563	出版時(shí)間：	2022-10-01	包裝：	平裝-膠訂
開(kāi)本：	16開(kāi)	頁(yè)數(shù)：		字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

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

作者簡(jiǎn)介

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

圖書(shū)目錄

第 1 章緒論 1
1.1 k-均值問(wèn)題 1
1.2 k-均值問(wèn)題的重要變形 7
1.2.1 k-中位問(wèn)題 7
1.2.2 球面 k-均值問(wèn)題 8
1.2.3 魯棒 k-均值/中位問(wèn)題 9
1.2.4 帶約束的 k-均值問(wèn)題 11
1.2.5 隱私保護(hù) k-均值問(wèn)題 12
1.2.6 泛函 k-均值問(wèn)題 13
1.2.7 模糊 C-均值問(wèn)題 13
1.2.8 其他變形 14
第 2 章 k-均值初始化方法 15
2.1 k-均值算法 15
2.1.1 算法設(shè)計(jì) 16
2.1.2 算法分析 16
2.1.3 下界 25
2.2 k-均值 || 算法 27
2.2.1 并行算法設(shè)計(jì) 27
2.2.2 并行算法分析 28
第 3 章 Johnson-Lindenstrauss 降維引理 35
3.1 預(yù)備知識(shí) 35
3.1.1 基本概念 35
3.1.2 Brunn-Minkowski 不等式 36
3.2 高維空間及其特性 36
3.2.1 超球體的幾何特性 37
3.2.2 高維空間的概率集中性 38
3.3 隨機(jī)投影定理和 Johnson-Lindenstrauss 降維引理 40
3.3.1 隨機(jī)投影定理 40
3.3.2 Johnson-Lindenstrauss 降維引理 42
第 4 章核心集與近似質(zhì)心集 45
4.1 核心集 45
4.1.1 問(wèn)題描述 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-均值問(wèn)題 55
4.2.3 稀疏實(shí)例 57
4.2.4 一般實(shí)例 61
第 5 章 k-中位和 k-均值問(wèn)題的局部搜索算法 67
5.1 k-中位問(wèn)題的局部搜索算法 67
5.1.1 問(wèn)題描述 67
5.1.2 單交換局部搜索算法 68
5.1.3 簡(jiǎn)單情形的局部比值 68
5.1.4 一般情形的局部比值 78
5.1.5 多項(xiàng)式時(shí)間近似算法 80
5.1.6 多交換局部搜索算法 83
5.2 k-均值問(wèn)題的局部搜索算法 87
5.2.1 單交換局部搜索算法 87
5.2.2 多交換局部搜索算法 91
第 6 章 k-均值問(wèn)題的雙準(zhǔn)則近似算法 95
6.1 線性規(guī)劃舍入算法 95
6.2 局部搜索算法 106
第 7 章有序 k-中位問(wèn)題 113
7.1 問(wèn)題描述 113
7.2 近似算法 114
7.2.1 算法框架 114
7.2.2 矩形有序 k-中位問(wèn)題的近似比分析 116
7.2.3 一般有序 k-中位問(wèn)題的近似比分析 123
第 8 章球面 k-均值問(wèn)題 127
8.1 問(wèn)題描述 127
8.1.1 概述 127
8.1.2 性質(zhì) 129
8.2 球面 k-均值問(wèn)題的初始化算法 132
8.2.1 問(wèn)題描述 132
8.2.2 可分離球面 k-均值問(wèn)題的近似初始化算法 133
8.2.3 推廣的球面 k-均值問(wèn)題的近似算法 140
8.3 局部搜索算法 142
8.3.1 單交換的局部搜索算法 142
8.3.2 多交換的局部搜索算法 148
第 9 章魯棒 k-均值問(wèn)題 152
9.1 帶懲罰的 k-均值問(wèn)題 152
9.1.1 概述 152
9.1.2 單交換局部搜索算法 152
9.1.3 多交換局部搜索算法 158
9.2 帶懲罰 k-中位/均值問(wèn)題局部搜索算法 162
9.2.1 問(wèn)題描述 163
9.2.2 算法及分析 163
9.3 帶異常點(diǎn) k-中位/均值問(wèn)題局部搜索算法 171
9.3.1 問(wèn)題描述 171
9.3.2 算法描述 172
9.3.3 近似比分析 173
第 10 章帶約束 k-均值問(wèn)題 181
10.1 問(wèn)題描述 181
10.2 帶約束 k-均值問(wèn)題的剝離封閉算法 183
10.2.1 單純形引理 184
10.2.2 剝離封閉算法 188
10.2.3 剝離封閉算法分析 190
10.3 帶約束 k-均值問(wèn)題的選擇算法 197
10.3.1 下界約束 k-均值問(wèn)題的選擇算法 197
10.3.2 r -容量約束 k-均值問(wèn)題的選擇算法 198
10.3.3 色譜 k-均值問(wèn)題的選擇算法 198
第 11 章其他變形 199
11.1 隱私保護(hù) k-均值 199
11.1.1 差分隱私概念 199
11.1.2 差分隱私 k-均值問(wèn)題描述 200
11.1.3 差分隱私常用的機(jī)制 201
11.1.4 高維差分隱私 k-均值問(wèn)題 202
11.2 泛函 k-均值問(wèn)題 206
11.2.1 問(wèn)題描述 206
11.2.2 泛函 k-均值問(wèn)題的初始化算法 209
11.3 模糊 C-均值問(wèn)題 211
11.3.1 問(wèn)題描述 211
11.3.2 模糊 C-均值問(wèn)題的初始化算法. 214
11.4 平方和設(shè)施選址問(wèn)題 217
11.4.1 問(wèn)題描述 217
11.4.2 連續(xù) SOS-FLP 的局部搜索算法 221
11.4.3 離散 SOS-FLP 的局部搜索算法 231
11.5 帶懲罰 -相似 Bregman 散度 k-均值問(wèn)題 234
11.5.1 問(wèn)題描述 234
11.5.2 帶懲罰-相似 Bregman 散度 k-均值問(wèn)題的初始化算法 236
參考文獻(xiàn) 247
名詞索引 259

??
??
??