數據挖掘原理（第3版）

麥克斯·布拉默（Max Bramer）,是英國樸次茅斯大學信息技術系榮譽教授、IFIP副主席、英國計算機學會AI專家組主席。
自從“數據挖掘”“數據庫中的知識發現”“大數據”和“預測分析”等技術興起以來，Max積極參與了多個數據挖掘項目，尤其是與數據自動分類相關的項目。
Max發表了大量技術文章，曾撰寫Research and Development in Intelligent Systems等著作。
Max具有多年的本科和研究生教學經驗。

目錄
第 1 章  數據挖掘簡介   1
1.1  數據爆炸   1
1.2  知識發現   2
1.3  數據挖掘的應用   3
1.4  標簽和無標簽數據   4
1.5  監督學習：分類   4
1.6  監督學習：數值預測   5
1.7  無監督學習：關聯規則   6
1.8  無監督學習：聚類   7

第 2 章  用於挖掘的數據   9
2.1  標準制定   9
2.2  變量的類型   10
2.3  數據準備   11
2.4  缺失值   13
2.4.1  丟棄實例   13
2.4.2  用最頻繁值/平均值替換   13
2.5  減少屬性個數   14
2.6  數據集的UCI存儲庫   15
2.7  本章小結   15
2.8  自我評估練習   15

第 3 章  分類簡介：樸素貝葉斯和最近鄰算法   17
3.1  什麽是分類   17
3.2  樸素貝葉斯分類器   18
3.3  最近鄰分類   24
3.3.1  距離測量   26
3.3.2  標準化   28
3.3.3  處理分類屬性   29
3.4  急切式和懶惰式學習   30
3.5  本章小結   30
3.6  自我評估練習   30

第 4 章  使用決策樹進行分類   31
4.1  決策規則和決策樹   31
4.1.1  決策樹：高爾夫示例   31
4.1.2  術語   33
4.1.3  degrees數據集   33
4.2  TDIDT算法   36
4.3  推理類型   38
4.4  本章小結   38
4.5  自我評估練習   39

第 5 章  決策樹歸納：使用熵進行屬性選擇   41
5.1  屬性選擇：一個實驗   41
5.2  替代決策樹   42
5.2.1  足球/無板籃球示例   42
5.2.2  匿名數據集   44
5.3  選擇要分裂的屬性：使用熵   46
5.3.1  lens24數據集   46
5.3.2  熵   47
5.3.3  使用熵進行屬性選擇   48
5.3.4  信息增益最大化   50
5.4  本章小結   51
5.5  自我評估練習   51

第 6 章  決策樹歸納：使用頻率表進行屬性選擇   53
6.1  實踐中的熵計算   53
6.1.1  等效性證明   55
6.1.2  關於零值的說明   56
6.2  其他屬性選擇標準：多樣性基尼指數   56
6.3  χ2屬性選擇準則   57
6.4  歸納偏好   60
6.5  使用增益比進行屬性選擇   61
6.5.1  分裂信息的屬性   62
6.5.2  總結   63
6.6  不同屬性選擇標準生成的規則數   63
6.7  缺失分支   64
6.8  本章小結   65
6.9  自我評估練習   65

第 7 章  估計分類器的預測精度   67
7.1  簡介   67
7.2  方法1：將數據劃分為訓練集和測試集   68
7.2.1  標準誤差   68
7.2.2  重復訓練和測試   69
7.3  方法2：k-折交叉驗證   70
7.4  方法3：N -折交叉驗證   70
7.5  實驗結果I   71
7.6  實驗結果II：包含缺失值的數據集   73
7.6.1  策略1：丟棄實例   73
7.6.2  策略2：用最頻繁值/平均值替換   74
7.6.3  類別缺失   75
7.7  混淆矩陣   75
7.8  本章小結   77
7.9  自我評估練習   77

第 8 章  連續屬性   79
8.1  簡介   79
8.2  局部與全局離散化   81
8.3  向TDIDT添加局部離散化   81
8.3.1  計算一組偽屬性的信息增益   82
8.3.2  計算效率   86
8.4  使用ChiMerge算法進行全局離散化   88
8.4.1  計算期望值和χ2   90
8.4.2  查找閾值   94
8.4.3  設置minIntervals和maxIntervals   95
8.4.4  ChiMerge算法：總結   96
8.4.5  對ChiMerge算法的評述   96
8.5  比較樹歸納法的全局離散化和局部離散化   97
8.6  本章小結   98
8.7  自我評估練習   98

第 9 章  避免決策樹的過度擬合   99
9.1  處理訓練集中的沖突   99
9.2  關於過度擬合數據的更多規則   103
9.3  預剪枝決策樹   104
9.4  後剪枝決策樹   106
9.5  本章小結   111
9.6  自我評估練習   111

第 10 章  關於熵的更多信息   113
10.1  簡介   113
10.2  使用位的編碼信息   116
10.3  區分值   117
10.4  對“非等可能”的值進行編碼   118
10.5  訓練集的熵   121
10.6  信息增益必須為正數或零   122
10.7  使用信息增益來簡化分類任務的特徵   123
10.7.1  示例1：genetics數據集   124
10.7.2  示例2：bcst96數據集   126
10.8  本章小結   128
10.9  自我評估練習   128

第 11 章  歸納分類的模塊化規則   129
11.1  規則後剪枝   129
11.2  沖突解決   130
11.3  決策樹的問題   133
11.4  Prism算法   135
11.4.1  基本Prism算法的變化   141
11.4.2  將Prism算法與TDIDT算法進行比較   142
11.5  本章小結   143
11.6  自我評估練習   143

第 12 章  度量分類器的性能   145
12.1  真假正例和真假負例   146
12.2  性能度量   147
12.3  真假正例率與預測精度   150
12.4  ROC圖   151
12.5  ROC曲線   153
12.6  尋找最佳分類器   153
12.7  本章小結   155
12.8  自我評估練習   155

第 13 章  處理大量數據   157
13.1  簡介   157
13.2  將數據分發到多個處理器   159
13.3  案例研究：PMCRI   161
13.4  評估分佈式系統PMCRI的有效性   163
13.5  逐步修改分類器   167
13.6  本章小結   171
13.7  自我評估練習   171

第 14 章  集成分類   173
14.1  簡介   173
14.2  估計分類器的性能   175
14.3  為每個分類器選擇不同的訓練集   176
14.4  為每個分類器選擇一組不同的屬性   177
14.5  組合分類：替代投票系統   177
14.6  並行集成分類器   180
14.7  本章小結   181
14.8  自我評估練習   181

第 15 章  比較分類器   183
15.1  簡介   183
15.2  配對t檢驗   184
15.3  為比較評估選擇數據集   189
15.4  抽樣   191
15.5  “無顯著差異”的結果有多糟糕?   193
15.6  本章小結   194
15.7  自我評估練習   194

第 16 章  關聯規則挖掘I   195
16.1  簡介   195
16.2  規則興趣度的衡量標準   196
16.2.1  Piatetsky-Shapiro標準和RI度量   198
16.2.2  規則興趣度度量應用於chess數據集   200
16.2.3  使用規則興趣度度量來解決沖突   201
16.3  關聯規則挖掘任務   202
16.4  找到最佳N條規則   202
16.4.1  J-Measure：度量規則的信息內容   203
16.4.2  搜索策略   204
16.5  本章小結   207
16.6  自我評估練習   207

第 17 章  關聯規則挖掘II   209
17.1  簡介   209
17.2  事務和項目集   209
17.3  對項目集的支持   211
17.4  關聯規則   211
17.5  生成關聯規則   213
17.6  Apriori   214
17.7  生成支持項目集：一個示例   217
17.8  為支持項目集生成規則   219
17.9  規則興趣度度量：提升度和杠桿率   220
17.10  本章小結   222
17.11  自我評估練習   222

第 18 章  關聯規則挖掘III：頻繁模式樹   225
18.1  簡介：FP-growth   225
18.2  構造FP-tree   227
18.2.1  預處理事務數據庫   227
18.2.2  初始化   229
18.2.3  處理事務1：f, c, a, m, p   230
18.2.4  處理事務2：f, c, a, b, m   231
18.2.5  處理事務3：f, b   235
18.2.6  處理事務4：c, b, p   236
18.2.7  處理事務5：f, c, a, m, p   236
18.3  從FP-tree中查找頻繁項目集   238
18.3.1  以項目p結尾的項目集   240
18.3.2  以項目m結尾的項目集   248
18.4  本章小結   254
18.5  自我評估練習   254

第 19 章  聚類   255
19.1  簡介   255
19.2  k-means聚類   257
19.2.1  示例   258
19.2.2  找到最佳簇集   262
19.3  凝聚式層次聚類   263
19.3.1  記錄簇間距離   265
19.3.2  終止聚類過程   268
19.4  本章小結   268
19.5  自我評估練習   268

第 20 章  文本挖掘   269
20.1  多重分類   269
20.2  表示數據挖掘的文本文檔   270
20.3  停用詞和詞乾   271
20.4  使用信息增益來減少特徵   272
20.5  表示文本文檔：構建向量空間模型   272
20.6  規範權重   273
20.7  測量兩個向量之間的距離   274
20.8  度量文本分類器的性能   275
20.9  超文本分類   275
20.9.1  對網頁進行分類   276
20.9.2  超文本分類與文本分類   277
20.10  本章小結   279
20.11  自我評估練習   280

第 21 章  分類流數據   281
21.1  簡介   281
21.2  構建H-Tree：更新數組   283
21.2.1  currentAtts數組   284
21.2.2  splitAtt數組   284
21.2.3  將記錄排序到適當的葉節點   284
21.2.4  hitcount數組   285
21.2.5  classtotals數組   285
21.2.6  acvCounts陣列   285
21.2.7  branch數組   286
21.3  構建H-Tree：詳細示例   287
21.3.1  步驟1：初始化根節點0   287
21.3.2  步驟2：開始讀取記錄   287
21.3.3  步驟3：考慮在節點0處分裂   288
21.3.4  步驟4：在根節點上拆分並初始化新的葉節點   289
21.3.5  步驟5：處理下一組記錄   290
21.3.6  步驟6：考慮在節點2處分裂   292
21.3.7  步驟7：處理下一組記錄   292
21.3.8  H-Tree算法概述   293
21.4  分裂屬性：使用信息增益   295
21.5  分裂屬性：使用Hoeffding邊界   297
21.6  H-Tree算法：最終版本   300
21.7  使用不斷進化的H-Tree進行預測   302
21.8  實驗：H-Tree與TDIDT   304
21.8.1  lens24數據集   304
21.8.2  vote數據集   306
21.9  本章小結   307
21.10  自我評估練習   307

第 22 章  分類流數據II：時間相關數據   309
22.1  平穩數據與時間相關數據   309
22.2  H-Tree算法總結   311
22.2.1  currentAtts數組   312
22.2.2  splitAtt數組   312
22.2.3  hitcount數組   312
22.2.4  classtotals數組   312
22.2.5  acvCounts數組   313
22.2.6  branch數組   313
22.2.7  H-Tree算法的偽代碼   313
22.3  從H-Tree到CDH-Tree：概述   315
22.4  從H-Tree轉換到CDH-Tree：遞增計數   315
22.5  滑動窗口法   316
22.6  在節點處重新分裂   320
22.7  識別可疑節點   320
22.8  創建備用節點   322
22.9  成長/遺忘備用節點及其後代   325
22.10  用備用節點替換一個內部節點   327
22.11  實驗：跟蹤概念漂移   333
22.11.1  lens24數據：替代模式   335
22.11.2  引入概念漂移   335
22.11.3  使用交替lens24數據的實驗   336
22.11.4  關於實驗的評論   343
22.12  本章小結   343
22.13  自我評估練習   343

附錄 A  基本數學知識   345
附錄 B  數據集   357
附錄 C  更多信息來源   371
附錄 D  詞匯表和符號   373
附錄 E  自我評估練習題答案   391
參考文獻   419