機器學習算法原理與編程實踐

第1章 機器學習的基礎 1
1.1 編程語言與開發環境 2
1.1.1 搭建Python開發環境 2
1.1.2 安裝Python算法庫 4
1.1.3 IDE配置及其安裝測試 5
1.2 對象、矩陣與矢量化編程 8
1.2.1 對象與維度 8
1.2.2 初識矩陣 10
1.2.3 矢量化編程與GPU運算 13
1.2.4 理解數學公式與NumPy矩陣運算 14
1.2.5 Linalg線性代數庫 18
1.3 機器學習的數學基礎 20
1.3.1 相似性的度量 21
1.3.2 各類距離的意義與Python實現 22
1.3.3 理解隨機性 29
1.3.4 回顧概率論 30
1.3.5 多元統計基礎 32
1.3.6 特征間的相關性 33
1.3.7 再談矩陣——空間的變換 35
1.3.8 數據歸一化 40
1.4 數據處理與可視化 42
1.4.1 數據的導入和內存管理 42
1.4.2 表與線性結構的可視化 45
1.4.3 樹與分類結構的可視化 46
1.4.4 圖與網絡結構的可視化 47
1.5 Linux操作系統下部署Python機器學習開發環境 48
1.5.1 Linux發行版的選擇 48
1.5.2 CentOS部署多版本Python實例 49
1.5.3 安裝NumPy、SciPy、Matplotlib開發包 52
1.5.4 安裝Scikit-Learn開發包 54
1.6 結語 55

第2章 中文文本分類 56
2.1 文本挖掘與文本分類的概念 56
2.2 文本分類項目 58
2.2.1 文本預處理 58
2.2.2 中文分詞介紹 61
2.2.3 Scikit-Learn庫簡介 66
2.2.4 向量空間模型 70
2.2.5 權重策略：TF-IDF方法 71
2.2.6 使用朴素貝葉斯分類模塊 74
2.2.7 分類結果評估 76
2.3 分類算法：朴素貝葉斯 78
2.3.1 貝葉斯公式推導 78
2.3.2 朴素貝葉斯算法實現 79
2.3.3 算法的改進 82
2.3.4 評估分類結果 82
2.4 分類算法：kNN 83
2.4.1 kNN算法原理 83
2.4.2 kNN算法的Python實現 86
2.4.3 評估分類結果 88
2.5 結語 88

第3章 決策樹的發展 89
3.1 決策樹的基本思想 89
3.1.1 從一個實例開始 90
3.1.2 決策樹的算法框架 95
3.1.3 信息熵測度 96
3.2 ID3決策樹 98
3.2.1 ID3算法 98
3.2.2 ID3的實現 101
3.2.3 決策樹主方法 101
3.2.4 訓練決策樹 103
3.2.5 持久化決策樹 104
3.2.6 決策樹分類 105
3.2.7 算法評估 106
3.3 C4.5算法 106
3.3.1 信息增益率 106
3.3.2 C4.5的實現 108
3.3.3 訓練決策樹 108
3.3.4 分類數據 109
3.4 Scikit-Learn與回歸樹 110
3.4.1 回歸算法原理 110
3.4.2 最小剩余方差法 111
3.4.3 模型樹 113
3.4.4 剪枝策略 113
3.4.5 Scikit-Learn實現 115
3.5 結語 117

第4章 推薦系統原理 118
4.1 推薦系統概述 119
4.1.1 從亞馬遜網站認識推薦系統 119
4.1.2 推薦系統的架構 122
4.1.3 開源推薦系統 125
4.2 協同過濾及其算法 126
4.2.1 協同過濾 126
4.2.2 數據預處理 127
4.2.3 使用Scikit-Learn的KMeans聚類 127
4.2.4 User CF原理 129
4.2.5 Item CF原理 131
4.2.6 SVD原理與計算 132
4.3 KMeans算法詳解 135
4.3.1 KMeans算法流程 135
4.3.2 輔助函數 136
4.3.3 聚類主函數 137
4.3.4 評估分類結果 139
4.4 聚類的改進：二分KMeans算法 141
4.4.1 二分聚類主函數 141
4.4.2 評估分類結果 142
4.5 SVD算法詳解 143
4.5.1 SVD算法回顧 143
4.5.2 常用距離函數 146
4.5.3 SVD數據集 146
4.5.4 SVD算法主函數 147
4.5.5 評估結果 147
4.6 結語 148

第5章 梯度尋優 149
5.1 最優化與計算復雜性 149
5.1.1 最優化理論 149
5.1.2 最優化的數學描述 150
5.1.3 凸集與分離定理 151
5.1.4 凸函數及其性質 153
5.1.5 局部最優與全局最優 155
5.1.6 計算復雜性與NP問題 156
5.1.7 逐次逼近法 159
5.2 Logistic梯度下降法 163
5.2.1 梯度下降法 164
5.2.2 線性分類器 166
5.2.3 Logistic函數——世界不是非黑即白 169
5.2.4 算法流程 171
5.2.5 對測試集進行分類 175
5.3 算法分析 175
5.3.1 超平面的變化趨勢 176
5.3.2 超平面的收斂評估 177
5.3.3 權重向量的收斂評估 179
5.3.4 算法總體評價 180
5.4 隨機梯度下降法：算法改進與評估 180
5.4.1 主函數 181
5.4.2 程序輸出 182
5.4.3 步長變化率 183
5.4.4 權重收斂評估 184
5.4.5 權重分量的變化趨勢 185
5.4.6 算法總體評價 187
5.5 結語 187

第6章 神經網絡初步 189
6.1 神經網絡簡史 189
6.1.1 起源與早期發展 189
6.1.2 中期發展 190
6.1.3 當前的發展與反思 192
6.2 BP神經網絡理論 192
6.2.1 線性不可分問題 192
6.2.2 BP網絡構成 193
6.2.3 BP網絡的訓練過程 196
6.3 BP網絡的實現和評估 199
6.3.1 BP網絡類與主要方法 199
6.3.2 設計BP網絡 199
6.3.3 輔助函數 202
6.3.4 主函數 203
6.3.5 分類器 204
6.3.6 執行分類並輸出結果 205
6.3.7 BP網絡評估 207
6.4 自組織特征映射神經網絡 208
6.4.1 SOM網絡框架 208
6.4.2 SOM類 211
6.4.3 功能函數 212
6.4.4 SOM網絡的實現 212
6.4.5 聚類結果 213
6.5 Boltzmann機算法 215
6.5.1 問題的提出 215
6.5.2 模擬退火原理 216
6.5.3 Boltzmann分布與退火過程 217
6.5.4 Boltzmann機類與功能函數 219
6.5.5 最短路徑的實現 222
6.5.6 執行算法 223
6.5.7 評估結果 224
6.6 結語 225

第7章 預測的技術與哲學 226
7.1 線性系統的預測 226
7.1.1 回歸與現代預測學 226
7.1.2 最小二乘法 227
7.1.3 代碼實現 229
7.1.4 正規方程組法 231
7.1.5 正規方程組的代碼實現 232
7.1.6 算法評估 232
7.2 徑向基網絡 233
7.2.1 RBF網絡 233
7.2.2 輔助函數 236
7.2.3 使用RBF預測 236
7.2.4 評估預測結果 238
7.3 嶺回歸 238
7.3.1 驗證多重共線性 239
7.3.2 嶺回歸理論 240
7.3.3 嶺際分析 240
7.3.4 k值的判定 242
7.3.5 輔助函數 243
7.3.6 嶺回歸的實現與k值計算 243
7.3.7 算法評估 244
7.4 預測的哲學 245
7.4.1 從《周易》談起 246
7.4.2 兩儀生四象 249
7.4.3 周期三與混沌 251
7.4.4 Logistic中的吸引子 254
7.4.5 三生萬物 258
7.4.6 八卦圖及其推演 261
7.5 結語 263

第8章 萬能分類器——支持向量機 265
8.1 支持向量機的理論基礎 266
8.1.1 經驗風險最優 266
8.1.2 關鍵定理與VC維 267
8.1.3 結構風險最優 270
8.2 SVM的數學推導 272
8.2.1 最大間隔超平面 272
8.2.2 拉格朗日乘子法 275
8.2.3 KKT條件與對偶變換 276
8.2.4 分類器函數 277
8.2.5 映射到高維空間 278
8.2.6 核函數法 280
8.2.7 離群點的松弛變量 281
8.3 SMO算法 284
8.3.1 SMO求解SVM 284
8.3.2 構造SMO類 288
8.3.3 主函數 290
8.3.4 訓練數據 291
8.3.5 分類並評估算法 293
8.4 SVM中文文本分類 293
8.4.1 回顧中文文本分類 294
8.4.2 Scikit-Learn SVM分類 294
8.4.3 評估結果 295
8.5 結語 296

第9章 人臉識別中的機器學習 297
9.1 模式識別概述 297
9.1.1 認知與模式 29

前 言

動機

2011年1月14日，史上最強的人機對抗在美國紐約約克鎮高地拉開序幕。Jeopardy!是美國具有25年歷史的眾所皆知的電視問答節目秀。每次三名參賽者相互角逐，在競賽中需要迅速理解屏幕上提出的各類智力問題，並作出回答。問題涉及的領域十分廣泛，就像一套世界知識的百科全書，超過個人所能掌握的知識容量的極限。而這次，一名特殊的參賽者名列其中，它就是IBM公司的計算機參賽者Watson，挑戰兩位人類選手Ken和Brad。經過激烈的角逐，Watson同時擊敗了兩位人類選手，贏得100萬美元獎金而一舉成名。這一具有歷史意義的比賽被Jeopardy!的哥倫比亞廣播公司連續在2011年2月14～16日三天晚上進行了重播，也成為計算機發展史上一個重要的時刻。IBM評論為：

「在Jeopardy!比賽中，計算機打敗人類選手是開放領域問答系統的一個里程碑！」

事實上，這次比賽有力地證明了，在廣泛的知識和智能領域，機器有能力全面超越人類。開放領域問答軟件的一個重要核心就是機器學習。從很多方面來看，這才僅僅是一個開始。近年來，計算機行業取得的最重要成就或多或少地都與機器學習領域的技術突破密切相關。2010年前后，多倫多大學的Geoffrey Hinton提出的深度學習（Deep Learning）算法，突破了產生抽象概念的技術瓶頸，被評價為：

「借助於DeepLearning算法，人類終於找到了如何處理『抽象概念』這個亘古難題的方法。」

該算法與衍生的卷積神經網絡（CNN——有監督）和深度置信網絡（DNN——無監督）在計算機視覺、語音識別和部分自然語言處理領域獲得巨大的成功，其與另一個並行處理架構Map Reduce並稱「大數據」技術的基石。