數據挖掘與分析：概念與算法

第1章數據挖掘與分析1
1.1數據矩陣1
1.2屬性2
1.3數據的幾何和代數描述3
1.3.1距離和角度5
1.3.2均值與總方差8
1.3.3正交投影9
1.3.4線性無關與維數10
1.4數據：概率觀點12
1.4.1二元隨機變量17
1.4.2多元隨機變量20
1.4.3隨機抽樣和統計量21
1.5數據挖掘22
1.5.1探索性數據分析23
1.5.2頻繁模式挖掘24
1.5.3聚類24
1.5.4分類25
1.6補充閱讀26
1.7習題26
第一部分數據分析基礎
第2章數值屬性28
2.1一元變量分析28
2.1.1數據居中度度量29
2.1.2數據離散度度量32
2.2二元變量分析35
2.2.1位置和離散度的度量36
2.2.2相關性度量37
2.3多元變量分析40
2.4數據規范化44
2.5正態分布46
2.5.1一元正態分布46
2.5.2多元正態分布47
2.6補充閱讀50
2.7習題51
第3章類別型屬性53
3.1一元分析53
3.1.1伯努利變量（Bernoulli variable）53
3.1.2多元伯努利變量55
3.2二元分析61
3.3多元分析69
3.4距離和角度74
3.5離散化75
3.6補充閱讀77
3.7習題78
第4章圖數據79
4.1圖的概念79
4.2拓撲屬性83
4.3中心度分析86
4.3.1基本中心度86
4.3.2Web中心度88
4.4圖的模型96
4.4.1Erds—Rényi隨機圖模型98
4.4.2Watts—Strogatz小世界圖模型101
4.4.3Barabási—Albert無標度模型104
4.5補充閱讀111
4.6習題112
第5章核方法114
5.1核矩陣117
5.1.1再生核映射118
5.1.2Mercer核映射120
5.2向量核122
5.3特征空間中的基本核操作126
5.4復雜對象的核132
5.4.1字符串的譜核132
5.4.2圖節點的擴散核133
5.5補充閱讀137
5.6習題137
第6章高維數據139
6.1高維對象139
6.2高維體積141
6.3超立方體的內接超球面143
6.4薄超球面殼的體積144
6.5超空間的對角線145
6.6多元正態的密度146
6.7附錄：球面體積的推導149
6.8補充閱讀153
6.9習題153
第7章降維156
7.1背景知識156
7.2主成分分析160
7.2.1最優線近似160
7.2.2最優二維近似163
7.2.3最優r維近似167
7.2.4主成分分析的幾何意義170
7.3核主成分分析172
7.4奇異值分解178
7.4.1奇異值分解的幾何意義179
7.4.2奇異值分解和主成分分析之間的聯系180
7.5補充閱讀182
7.6習題182
第二部分頻繁模式挖掘
第8章項集挖掘186
8.1頻繁項集和關聯規則186
8.2頻繁項集挖掘算法189
8.2.1逐層的方法：Apriori算法191
8.2.2事務標識符集的交集方法：Eclat算法193
8.2.3頻繁模式樹方法：FPGrowth算法197
8.3生成關聯規則201
8.4補充閱讀203
8.5習題203
第9章項集概述208
9.1最大頻繁項集和閉頻繁項集208
9.2挖掘最大頻繁項集：GenMax算法211
9.3挖掘閉頻繁項集：Charm算法213
9.4非可導項集215
9.5補充閱讀220
9.6習題221
第10章序列挖掘223
10.1頻繁序列223
10.2挖掘頻繁序列224
10.2.1逐層挖掘：GSP225
10.2.2垂直序列挖掘：Spade226
10.2.3基於投影的序列挖掘：PrefixSpan228
10.3基於后綴樹的子串挖掘230
10.3.1后綴樹230
10.3.2Ukkonen線性時間算法233
10.4補充閱讀238
10.5習題239
第11章圖模式挖掘242
11.1同形和支撐242
11.2候選生成245
11.3gSpan算法249
11.3.1擴展和支撐計算250
11.3.2權威性測試255
11.4補充閱讀256
11.5習題257
第12章模式與規則評估260
12.1規則和模式評估的度量260
12.1.1規則評估度量260
12.1.2模式評估度量268
12.1.3比較多條規則和模式270
12.2顯着性檢驗和置信區間273
12.2.1產生式規則的費希爾精確檢驗273
12.2.2顯着性的置換檢驗277
12.2.3置信區間內的自助抽樣282
12.3補充閱讀284
12.4習題285
第三部分聚類
第13章基於代表的聚類288
13.1K—means算法288
13.2核K—means292
13.3期望最大聚類295
13.3.1一維中的EM297
13.3.2d維中的EM300
13.3.3極大似然估計305
13.3.4EM方法309
13.4補充閱讀311
13.5習題312
第14章層次式聚類315
14.1預備知識315
14.2聚合型層次式聚類317
14.2.1簇間距離317
14.2.2更新距離矩陣321
14.2.3計算復雜度322
14.3補充閱讀322
14.4習題323
第15章基於密度的聚類325
15.1DBSCAN算法325
15.2核密度估計328
15.2.1一元密度估計328
15.2.2多元密度估計331
15.2.3最近鄰密度估計333
15.3基於密度的聚類：DENCLUE333
15.4補充閱讀338
15.5習題339
第16章譜聚類和圖聚類341
16.1圖和矩陣341
16.2基於圖的割的聚類347
16.2.1聚類目標函數：比例割與歸—割349
16.2.2譜聚類算法351
16.2.3最大化目標：平均割與模塊度354
16.3馬爾可夫聚類360
16.4補充閱讀366
16.5習題367
第17章聚類的驗證368
17.1外部驗證度量368
17.1.1基於匹配的度量369
17.1.2基於熵的度量372
17.1.3成對度量375
17.1.4關聯度量378
17.2內部度量381
17.3相對度量388
17.3.1分簇穩定性394
17.3.2聚類趨向性396
17.4補充閱讀400
17.5習題401
第四部分分類
第18章基於概率的分類404
18.1貝葉斯分類器404
18.1.1估計先驗概率404
18.1.2估計似然405
18.2朴素貝葉斯分類器409
18.3K最近鄰分類器412
18.4補充閱讀414
18.5習題415
第19章決策樹分類器416
19.1決策樹417
19.2決策樹算法419
19.2.1分割點評估度量420
19.2.2評估分割點422
19.3補充閱讀429
19.4習題429
第20章線性判別分析431
20.1最優線性判別431
20.2核判別分析437
20.3補充閱讀443
20.4習題443
第21章支持向量機445
21.1支持向量和間隔445
21.2SVM：線性可分的情況450
21.3軟間隔SVM：線性不可分的情況454
21.3.1鉸鏈誤損455
21.3.2二次誤損458
21.4核SVM：非線性情況459
21.5SVM訓練算法462
21.5.1對偶解法：隨機梯度上升463
21.5.2原始問題解：牛頓優化467
21.6補充閱讀473
21.7習題473
第22章分類的評估475
22.1分類性能度量475
22.1.1基於列聯表的度量476
22.1.2二值分類：正類和負類479
22.1.3ROC分析482
22.2分類器評估487
22.2.1K折交叉驗證487
22.2.2自助抽樣488
22.2.3置信區間489
22.2.4分類器比較：配對t檢驗493
22.3偏置—方差分解495
22.4補充閱讀503
22.5習題504