《若干聚類問題複雜性及其算法》是2013年10月電子工業出版社出版的圖書，作者是劉培強、李曙光、肖進傑。
基本介紹
- 書名：若干聚類問題複雜性及其算法
- 作者：劉培強、李曙光、肖進傑
- 出版社：電子工業出版社
- 出版時間：2013年10月
- 頁數：148 頁
- 定價：35 元
- 開本：16 開
- ISBN：9787121213793
內容簡介,圖書目錄,
內容簡介
聚類是指根據給定的多個對象及其屬性，基於相似性函式度量對象間的相似性，以尋找有意義或有用的對象分組。聚類分析方法是人們認識和理解世界的最基本方式之一，廣泛套用於計算生物學、市場分析、社交網路數據分析、電子商務數據分析等眾多領域。由於聚類分析的多樣性、重要性和廣泛性，尤其是在目前大數據時代背景下，眾多套用領域對聚類分析算法提出了新的挑戰。本書從問題的計算複雜性證明和近似算法設計的角度，對若干個聚類問題進行了討論和研究，主要研究了帶缺失值的兩元指紋向量聚類問題、兩元矩陣的k-子矩陣劃分問題、割聚類問題、設施定位問題與k-median 問題等。本書可作為從事計算複雜性理論、聚類分析研究和套用科技人員的參考書。
圖書目錄
第1章 緒論 1
1.1 聚類分析 1
1.2 雙向聚類 3
1.2.1 雙向簇的類型 4
1.2.2 雙向聚類的解格式 5
1.3 數據矩陣上的聚類問題 6
1.4 兩元矩陣聚類問題 7
1.5 割聚類 8
1.6 設施定位問題和k-median問題 9
第2章 計算複雜性理論簡介 11
2.1 算法 11
2.2 計算模型 13
2.3 複雜性類 18
2.4 NP-完全問題 20
2.5 NP-難問題 21
2.6 近似算法與啟發式算法 22
第3章 帶缺失值的基因表達譜聚類問題 29
3.1 問題的套用背景 29
3.2 問題的形式化描述 33
3.3 BCMV(2)問題的複雜性 34
3.3.1 零件圖及其性質 36
3.3.2 基於零件圖和X3C(3)實例構造圖G 37
3.3.3 由關聯圖構造BCMV(2)問題的實例 38
3.3.4 完成NP-難證明 42
3.4 求解BCMV問題的GCP算法 42
3.4.1 基於團劃分的啟發式算法 43
3.4.2 基於鍊表的GCP算法 45
3.4.3 基於鍊表的GCP算法實驗結果分析 50
3.4.4 經驗公式 54
3.5 基於線性規劃的求解算法 55
3.5.1 LAB算法 55
3.5.2 LAB算法的實驗結果及分析 59
3.6 本章小節 61
第4章 兩元矩陣的子矩陣劃分問題的複雜性及求解算法 62
4.1 引言 62
4.2 k-SPBM問題和k-PBB問題介紹 66
4.3 3-PBB問題是NP-完全的 67
4.3.1 二分圖零件Ti1, Ti2, Ti3 69
4.3.2 由二分圖零件的MO3實例構造二分圖B 74
4.3.3 完成3-PBB的NP-完全性證明 81
4.4 當k為大於3的正整數常量時，k-PBB (k>3)問題的複雜性 83
4.5 k-SPBM問題的NP-完全性證明 84
4.6 k-PBB問題求解算法 85
4.6.1 求解算法 85
4.6.2 算法分析 86
4.6.3 算法測試 87
4.7 本章小節 88
第5章 均衡負載聚類 90
5.1 問題的套用背景 90
5.2 引言 92
5.3 預備知識 93
5.4 鏈和環中的均衡負載聚類 93
5.5 樹和限制樹寬圖中的均衡負載聚類 95
5.6 本章小結 97
第6章 顏色相關最小負載聚類 98
6.1 引言 98
6.2 預備知識 99
6.3 仙人掌圖 100
6.4 參數為k的幾乎樹 103
6.5 本章小節 106
第7章 設施定位和k -median問題 107
7.1 相關概念和算法介紹 107
7.1.1 公制空間（Metric Space） 107
7.1.2 組合的生成算法 108
7.2 設施定位問題 108
7.2.1 基本概念 108
7.2.2 設施定位問題局部搜尋算法 109
7.2.3 局部搜尋算法的實現與求解實驗 115
7.2.4 局部搜尋算法的改進 121
7.3 k-median問題 122
7.3.1 基本概念 122
7.3.2 k-median貪心近似算法 123
7.3.3 貪心算法近似度分析 124
7.3.4 貪心算法實驗數據 126
7.4 本章小節 128
本書符號說明 129
參考文獻 130
