數據挖掘與分析 : 概念與算法 (Data Mining and Analysis: Fundamental Concepts and Algorithms)

Mohammed J. Zaki 
倫斯勒理工學院計算機科學系教授，ACM傑出科學家，IEEE會士，目前致力於研究新數據挖掘技術。曾獲得谷歌教職研究獎等諸多獎項。

Wagner Meira Jr. 
巴西米納斯聯邦大學計算機科學系教授，數據庫專家。
 

第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