《机器学习算法原理与编程实践》

编辑推荐

　　《机器学习算法原理与编程实践》围绕神经网络、智能推理、矩阵计算三大主线，提供近25个经典的算法讲解。解剖有代表性的算法库：Scikit-Learn算法库、OpenCV机器视觉、Theano深度学习库。作为本土原创图书，《机器学习算法原理与编程实践》更符合国内人的阅读习惯，适合作为机器学习算法设计的入门读物。

内容简介

　　《机器学习算法原理与编程实践》是机器学习原理和算法编码实现的基础性读物，内容分为两大主线：单个算法的原理讲解和机器学习理论的发展变迁。算法除包含传统的分类、聚类、预测等常用算法之外，还新增了深度学习、贝叶斯网、隐马尔科夫模型等内容。对于每个算法，均包括提出问题、解决策略、数学推导、编码实现、结果评估几部分。数学推导力图做到由浅入深，深入浅出。结构上数学原理与程序代码一一对照，有助于降低学习门槛，加深公式的理解，起到推广和扩大机器学习的作用。

作者简介

　　郑捷，www.threedweb.cn网站负责人，研究方向是机器学习与自然语言处理。当前负责的核心产品是高精度自然语言认知系统的设计与研发，研发目标是高精度（识别率在85%~95%）的统一架构的NLP认知系统。

目录

第1章机器学习的基础1
1．1编程语言与开发环境2
1．1．1搭建Python开发环境2
1．1．2安装Python算法库4
1．1．3IDE配置及其安装测试5
1．2对象、矩阵与矢量化编程8
1．2．1对象与维度8
1．2．2初识矩阵10
1．2．3矢量化编程与GPU运算13
1．2．4理解数学公式与NumPy矩阵运算14
1．2．5Linalg线性代数库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．5Linux操作系统下部署Python机器学习开发环境48
1．5．1Linux发行版的选择48
1．5．2CentOS部署多版本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．3Scikit-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分类算法：kNN83
2．4．1kNN算法原理83
2．4．2kNN算法的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．2ID3决策树98
3．2．1ID3算法98
3．2．2ID3的实现101
3．2．3决策树主方法101
3．2．4训练决策树103
3．2．5持久化决策树104
3．2．6决策树分类105
3．2．7算法评估106
3．3C4．5算法106
3．3．1信息增益率106
3．3．2C4．5的实现108
3．3．3训练决策树108
3．3．4分类数据109
3．4Scikit-Learn与回归树110
3．4．1回归算法原理110
3．4．2最小剩余方差法111
3．4．3模型树113
3．4．4剪枝策略113
3．4．5Scikit-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．4UserCF原理129
4．2．5ItemCF原理131
4．2．6SVD原理与计算132
4．3KMeans算法详解135
4．3．1KMeans算法流程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．5SVD算法详解143
4．5．1SVD算法回顾143
4．5．2常用距离函数146
4．5．3SVD数据集146
4．5．4SVD算法主函数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．2Logistic梯度下降法163
5．2．1梯度下降法164
5．2．2线性分类器166
5．2．3Logistic函数――世界不是非黑即白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．2BP神经网络理论192
6．2．1线性不可分问题192
6．2．2BP网络构成193
6．2．3BP网络的训练过程196
6．3BP网络的实现和评估199
6．3．1BP网络类与主要方法199
6．3．2设计BP网络199
6．3．3辅助函数202
6．3．4主函数203
6．3．5分类器204
6．3．6执行分类并输出结果205
6．3．7BP网络评估207
6．4自组织特征映射神经网络208
6．4．1SOM网络框架208
6．4．2SOM类211
6．4．3功能函数212
6．4．4SOM网络的实现212
6．4．5聚类结果213
6．5Boltzmann机算法215
6．5．1问题的提出215
6．5．2模拟退火原理216
6．5．3Boltzmann分布与退火过程217
6．5．4Boltzmann机类与功能函数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．1RBF网络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．4k值的判定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．4Logistic中的吸引子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．2SVM的数学推导272
8．2．1最大间隔超平面272
8．2．2拉格朗日乘子法275
8．2．3KKT条件与对偶变换276
8．2．4分类器函数277
8．2．5映射到高维空间278
8．2．6核函数法280
8．2．7离群点的松弛变量281
8．3SMO算法284
8．3．1SMO求解SVM284
8．3．2构造SMO类288
8．3．3主函数290
8．3．4训练数据291
8．3．5分类并评估算法293
8．4SVM中文文本分类293
8．4．1回顾中文文本分类294
8．4．2Scikit-LearnSVM分类294
8．4．3评估结果295
8．5结语296
第9章人脸识别中的机器学习297
9．1模式识别概述297
9．1．1认知与模式297
9．1．2机器视觉与OpenCV300
9．1．3OpenCV的文件与基本操作301
9．2人脸检测305
9．2．1人脸识别的历史与架构305
9．2．2人脸识别系统307
9．2．3人脸检测原理与Haar级联检测308
9．2．4人脸检测特征文件311
9．2．5Haarcascade的实现314
9．2．6LBPcascade的实现315
9．3AdaBoost算法概述316
9．3．1算法原理与步骤316
9．3．2辅助函数317
9．3．3AdaBoost分类器318
9．3．4单层决策树分类子算法319
9．3．5训练数据集321
9．3．6执行分类322
9．4人脸识别323
9．4．1人脸数据库324
9．4．2PCA原理325
9．4．3特征脸识别类327
9．4．4生成特征脸328
9．4．5执行人脸识别330
9．5结语330
第10章认知计算与深度学习332
10．1认知计算332
10．1．1认知层次论333
10．1．2从具体到抽象336
10．1．3Theano库与基本操作338
10．2多层感知器343
10．2．1MNIST数据集343
10．2．2Softmax回归类345
10．2．3正则化方法347
10．2．4执行SoftMax学习350
10．2．5多层感知器353
10．2．6多层感知器的实现355
10．2．7MLP的训练过程358
10．3卷积神经网络358
10．3．1理论基础358
10．3．2卷积类363
10．3．3LeNet5函数364
10．3．4CNN的训练过程369
10．4Theano安装与GPU运算370
10．4．1Anaconda安装370
10．4．2实现CPU运算372
10．4．3安装VS2013374
10．4．4安装CUDA375
10．4．5实现支持GPU运算378
10．5结语378
第11章概率图模型与词性标注380
11．1马尔科夫过程381
11．1．1随机过程与状态图381
11．1．2马尔科夫链及其概念382
11．1．3马尔科夫链的实现384
11．2概率图模型和贝叶斯网385
11．2．1概述385
11．2．2条件独立性386
11．2．3贝叶斯网简介390
11．2．4贝叶斯网的构造392
11．2．5贝叶斯网的推理简介394
11．3隐马尔科夫模型396
11．3．1概述396
11．3．2HMM推理与前向算法399
11．3．3Vertibi算法原理403
11．3．4Vertibi算法实现405
11．3．5执行并输出结果406
11．4词性标注系统406
11．4．1语料库与词性资源407
11．4．2手工计算409
11．4．3结果验证413
11．5结语414

前言/序言

　　动机

　　2011年1月14日，史上最强的人机对抗在美国纽约约克镇高地拉开序幕。Jeopardy!是美国具有25年历史的众所皆知的电视问答节目秀。每次三名参赛者相互角逐，在竞赛中需要迅速理解屏幕上提出的各类智力问题，并作出回答。问题涉及的领域十分广泛，就像一套世界知识的百科《机器学习算法原理与编程实践》，超过个人所能掌握的知识容量的极限。而这次，一名特殊的参赛者名列其中，它就是IBM公司的计算机参赛者Watson，挑战两位人类选手Ken和Brad。经过激烈的角逐，Watson同时击败了两位人类选手，赢得100万美元奖金而一举成名。这一具有历史意义的比赛被Jeopardy!的哥伦比亚广播公司连续在2011年2月14～16日三天晚上进行了重播，也成为计算机发展史上一个重要的时刻。IBM评论为：

　　“在Jeopardy!比赛中，计算机打败人类选手是开放领域问答系统的一个里程碑！”

　　事实上，这次比赛有力地证明了，在广泛的知识和智能领域，机器有能力全面超越人类。开放领域问答软件的一个重要核心就是机器学习。从很多方面来看，这才仅仅是一个开始。近年来，计算机行业取得的最重要成就或多或少地都与机器学习领域的技术突破密切相关。2010年前后，多伦多大学的GeoffreyHinton提出的深度学习（DeepLearning）算法，突破了产生抽象概念的技术瓶颈，被评价为：

　　“借助于DeepLearning算法，人类终于找到了如何处理‘抽象概念’这个亘古难题的方法。”

　　该算法与衍生的卷积神经网络（CNN——有监督）和深度置信网络（DNN——无监督）在计算机视觉、语音识别和部分自然语言处理领域获得巨大的成功，其与另一个并行处理架构MapReduce并称“大数据”技术的基石。

　　2012年11月，微软在天津的一次活动上公开演示了一个全自动的同声传译系统，讲演者用英文演讲，后台的计算机一气呵成自动完成语音识别、英中机器翻译和中文语音合成，效果非常流畅。据报道，后面支撑的关键技术就是DNN，或者深度学习（DeepLearning，DL）。

　　人与动物最本质的区别之一就是人类具有高度发达的智能。千百年来，人类从未停止过对智慧本身的研究与探索。20世纪50年代，图灵就在论文《机器能思考吗》中提出了一个著名测试，后世称为图灵测试：

　　“假如一台机器通过特殊的方式与人沟通，若有一定比例的人（超过30%）无法在特定时间内（5分钟）分辨出与自己交谈的是人还是机器，则可认为该机器具有‘思考’的能力。”

　　这里的思考能力就是指智能。而对于计算机领域而言，它是一个多么奢侈而艰难的字眼。以IBMWatson为例，它由90台IBM服务器、360个计算机芯片驱动组成，是一个有着10台冰箱那么大的计算机系统。它拥有15TB内存，2880台处理器，每秒可进行80万亿次运算。系统配置的处理器是Power7系列处理器，这是当前RISC（精简指令集计算机）架构中最强的处理器。它采用45nm工艺打造，拥有8个核心、32个线程，主频最高可达4.1GHz，仅其二级缓存就达到32MB。

　　在大数据领域，据Google称，其知识图谱的信息有许多来源，包括CIA的世界概况、Freebase和维基百科，其功能与Ask.com和WolframAlpha等问题问答系统相似。截至2012年，其语义网络包含超过570亿个对象，超过18亿个介绍，用来理解搜索关键词含义的、不同对象之间的链接关系更是不可计数。2012年11月4日，知识图谱新增了7种语言：西班牙语、法语、德语、葡萄牙语、日语、俄罗斯语及意大利语。

　　历经半个多世纪，在各个领域的商业机构和科研机构的共同努力下，几经沉浮，人们逐渐意识到，高度并行的计算（硬件）能力和大规模数据的学习（算法）能力是“思考”的基础。距离让机器像人类一样思考的目标已经不远了！

　　《机器学习算法原理与编程实践》特色

　　《机器学习算法原理与编程实践》的最大特色就是理论讲解深入浅出、通俗易懂，入门门槛不高，理论与实践并重。降低学习门槛是我们主要的努力方向。对于中国读者，特别是广大的工程技术人员，无论是在职还是学生，进入机器学习领域不外乎两条路。

　　第一条路是从开源代码学习，辅助一些书籍资料。大多数软件设计人员都做过几年源码解析工作，源码解析这条路是比较辛苦的，但一旦掌握，就会形成一种条件反射。程序员宁可读源码也不愿意读数学公式，这是普遍现象。笔者认为，随着机器学习一步步走向工程实践，这部分人在读者群中应占绝大部分。

　　为了最大限度地降低学习的难度，首先，在内容上，我们以大量的文字描述来说明重要的定理和公式，尽可能在数学推导过程中增加充分的文字解释，消除初学者的理解障碍。其次，我们将源码、公式和文字解释对照起来，使初学者在阅读源码和文字解释的同时，也能够轻松理解算法的数学原理，使他们认识到数学分析并不遥远，理解起来并不困难。最后，我们使用矢量编程的设计方式，这种方式的优势是可以部分将数学公式直接映射到代码上，代码简介，思路清晰，学习效率很高。三管齐下，使初学者能多角度加深算法概念的理解，在实践应用中做到举一反三。

　　第二条路是从数学入手，一般针对研究所或科研院校的研究人员。他们喜欢那种有一定的理论高度，看明白了拿来就可以讲课或写论文用的书籍。这部分读者的特点是比较重理论，缺点是实践能力不强。《机器学习算法原理与编程实践》可以通过丰富的算法代码弥补他们在此方面的不足。

　　最后，《机器学习算法原理与编程实践》由本土作者编写。笔者翻译过几本国外的专业论文和书籍，也看过不少的本土经典。如果内容差异不大，从效率和接受程度上，看本土书籍要快很多，时间成本对任何一个人都是重要的；本土书籍的另一个优势是作者与大多数的读者都有相似的背景知识结构，因而没有文化差异性，思路上很好理解，容易被读者接受。《机器学习算法原理与编程实践》内容多取材于实践，目标明确，针对性强，对读者而言学习效率高。

　　《机器学习算法原理与编程实践》内容及体系结构

　　《机器学习算法原理与编程实践》的特点之一是从结构上阐明了研究机器学习理论和算法的方法。最重要的不是数学，也不是这些算法本身，而是思想的发展过程，这与之前所有的书籍有所不同。《机器学习算法原理与编程实践》分为三条主线。

　　第一条主线是从第一代神经网络（线性分类器）、第二代神经网络（非线性）及其在预测领域的应用，到支持向量机，最后是深度学习。

　　从第5章开始我们深入讲解了感知器网络及Logisitic网络的算法及相关的理论基础。第6章，我们详细介绍了三种典型的神经网络：BP网络、SOM网络、玻尔兹曼机网络。这两章的内容主要集中在第二代神经网络的模型上。

　　第8章我们从统计学习理论开始，深入探讨了支持向量机的模型，并给出了文本分类的实例。支持向量机的出现结束了浅层机器学习算法的大多数问题，使人工智能走向了一个新阶段。

　　第9章和第10章我们详细介绍了认知分层理论，并探讨了人类神经系统的两大重要机制：迭代和分层。由此引入了深度神经网络框架（深度学习），并以Theano框架为中心介绍了GPU运算的模型。深度学习框架中的算法很多，我们介绍了多层感知器和卷积神经网络两个算法，作为读者入门的基础。

　　第二条主线是贝叶斯理论，从朴素贝叶斯算法到贝叶斯网，最后是隐马尔科夫模型，这部分属于智能推理的范畴。

　　第2章我们详细介绍了朴素贝叶斯算法在文本分类中的应用。由于文本处理的大多数算法都是以贝叶斯网为基础的，而朴素贝叶斯是其中最简单的算法，所以以此开篇。

　　第11章，我们从随机过程开始，层层深入，相继介绍了马尔可夫链、贝叶斯网络、隐马尔科夫模型。最后，我们给出了隐马尔科夫模型的重要应用——自然语言处理的词性标注模块，并给出详细的代码讲解和结巴分词及词性标注应用。

　　最后一条主线是矩阵降维、奇异值分解（svd）和PCA算法，因为算法简单，《机器学习算法原理与编程实践》都使用真实案例进行讲解。

　　第4章，我们通过一个实例介绍了推荐系统的内容，并分析介绍了协同过滤理论中的两个重要算法：KMeans和SVD隐语义分析。我们不仅讲解了SVD的数学推导，而且给出了手工计算的代码。

　　第9章，我们讲解了主成分分析（PCA）的基本原理和算法，并通过实例讲解，列出了PCA的算法实现和监测评估。

　　第3章和第9章，我们介绍了决策时算法的发展历史，以及各个历史时期的代表算法——ID3、C4.5、CART、AdaBoost，并给出基本原理和代码实现。

　　目前机器学习主要由这三条主线贯穿始终，《机器学习算法原理与编程实践》着力于讲解这三条主线的理论发展、思想变迁、数学原理，而具体算法就是其上的一颗颗明珠。希望读者在学习完《机器学习算法原理与编程实践》之后，能够将机器学习的各种理论融会贯通。