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

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

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

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

第1章 机器学习的基础
1.1 编程语言与开发环境
1.1.1 搭建Python开发环境
1.1.2 安装Python算法库
1.1.3 IDE配置及其安装测试
1.2 对象、矩阵与矢量化编程
1.2.1 对象与维度
1.2.2 初识矩阵
1.2.3 矢量化编程与GPU运算
1.2.4 理解数学公式与NumPy矩阵运算
1.2.5 Linalg线性代数库
1.3 机器学习的数学基础
1.3.1 相似性的度量
1.3.2 各类距离的意义与Python实现
1.3.3 理解随机性
1.3.4 回顾概率论
1.3.5 多元统计基础
1.3.6 特征间的相关性
1.3.7 再谈矩阵–空间的变换
1.3.8 数据归一化
1.4 数据处理与可视化
1.4.1 数据的导入和内存管理
1.4.2 表与线性结构的可视化
1.4.3 树与分类结构的可视化
1.4.4 图与网络结构的可视化
1.5 Linux操作系统下部署Python机器学习开发环境
1.5.1 Linux发行版的选择
1.5.2 CentOS部署多版本Python实例
1.5.3 安装NumPy、SciPy、Matplotlib开发包
1.5.4 安装Scikit-Learn开发包
1.6 结语
第2章 中文文本分类
2.1 文本挖掘与文本分类的概念
2.2 文本分类项目
2.2.1 文本预处理
2.2.2 中文分词介绍
2.2.3 Scikit-Learn库简介
2.2.4 向量空间模型
2.2.5 权重策略：TF-IDF方法
2.2.6 使用朴素贝叶斯分类模块
2.2.7 分类结果评估
2.3 分类算法：朴素贝叶斯
2.3.1 贝叶斯公式推导
2.3.2 朴素贝叶斯算法实现
2.3.3 算法的改进
2.3.4 评估分类结果
2.4 分类算法：kNN
2.4.1 kNN算法原理
2.4.2 kNN算法的Python实现
2.4.3 评估分类结果
2.5 结语
第3章 决策树的发展
3.1 决策树的基本思想
3.1.1 从一个实例开始
3.1.2 决策树的算法框架
3.1.3 信息熵测度
3.2 ID3决策树
3.2.1 ID3算法
3.2.2 ID3的实现
3.2.3 决策树主方法
3.2.4 训练决策树
3.2.5 持久化决策树
3.2.6 决策树分类
3.2.7 算法评估
3.3 C4.5算法
3.3.1 信息增益率
3.3.2 C4.5的实现
3.3.3 训练决策树
3.3.4 分类数据
3.4 Scikit-Learn与回归树
3.4.1 回归算法原理
3.4.2 *小剩余方差法
3.4.3 模型树
3.4.4 剪枝策略
3.4.5 Scikit-Learn实现
3.5 结语
第4章 推荐系统原理
4.1 推荐系统概述
4.1.1 从亚马逊网站认识推荐系统
4.1.2 推荐系统的架构
4.1.3 开源推荐系统
4.2 协同过滤及其算法
4.2.1 协同过滤
4.2.2 数据预处理
4.2.3 使用Scikit-Learn的KMeans聚类
4.2.4 User CF原理
4.2.5 Item CF原理
4.2.6 SVD原理与计算
4.3 KMeans算法详解
4.3.1 KMeans算法流程
4.3.2 辅助函数
4.3.3 聚类主函数
4.3.4 评估分类结果
4.4 聚类的改进：二分KMeans算法
4.4.1 二分聚类主函数
4.4.2 评估分类结果
4.5 SVD算法详解
4.5.1 SVD算法回顾
4.5.2 常用距离函数
4.5.3 SVD数据集
4.5.4 SVD算法主函数
4.5.5 评估结果
4.6 结语
第5章 梯度寻优
5.1 **化与计算复杂性
5.1.1 **化理论
5.1.2 **化的数学描述
5.1.3 凸集与分离定理
5.1.4 凸函数及其性质
5.1.5 局部**与全局**
5.1.6 计算复杂性与NP问题
5.1.7 逐次逼近法
5.2 Logistic梯度下降法
5.2.1 梯度下降法
5.2.2 线性分类器
5.2.3 Logistic函数–世界不是非黑即白
5.2.4 算法流程
5.2.5 对测试集进行分类
5.3 算法分析
5.3.1 超平面的变化趋势
5.3.2 超平面的收敛评估
5.3.3 权重向量的收敛评估
5.3.4 算法总体评价
5.4 随机梯度下降法：算法改进与评估
5.4.1 主函数
5.4.2 程序输出
5.4.3 步长变化率
5.4.4 权重收敛评估
5.4.5 权重分量的变化趋势
5.4.6 算法总体评价
5.5 结语
第6章 神经网络初步
6.1 神经网络简史
6.1.1 起源与早期发展
6.1.2 中期发展
6.1.3 当前的发展与反思
6.2 BP神经网络理论
6.2.1 线性不可分问题
6.2.2 BP网络构成
6.2.3 BP网络的训练过程
6.3 BP网络的实现和评估
6.3.1 BP网络类与主要方法
6.3.2 设计BP网络
6.3.3 辅助函数
6.3.4 主函数
6.3.5 分类器
6.3.6 执行分类并输出结果
6.3.7 BP网络评估
6.4 自组织特征映射神经网络
6.4.1 SOM网络框架
6.4.2 SOM类
6.4.3 功能函数
6.4.4 SOM网络的实现
6.4.5 聚类结果
6.5 Boltzmann机算法
6.5.1 问题的提出
6.5.2 模拟退火原理
6.5.3 Boltzmann分布与退火过程
6.5.4 Boltzmann机类与功能函数
6.5.5 *短路径的实现
6.5.6 执行算法
6.5.7 评估结果
6.6 结语
第7章 预测的技术与哲学
7.1 线性系统的预测
7.1.1 回归与现代预测学
7.1.2 *小二乘法
7.1.3 代码实现
7.1.4 正规方程组法
7.1.5 正规方程组的代码实现
7.1.6 算法评估
7.2 径向基网络
7.2.1 RBF网络
7.2.2 辅助函数
7.2.3 使用RBF预测
7.2.4 评估预测结果
7.3 岭回归
7.3.1 验证多重共线性
7.3.2 岭回归理论
7.3.3 岭际分析
7.3.4 k值的判定
7.3.5 辅助函数
7.3.6 岭回归的实现与k值计算
7.3.7 算法评估
7.4 预测的哲学
7.4.1 从《周易》谈起
7.4.2 两仪生四象
7.4.3 周期三与混沌
7.4.4 Logistic中的吸引子
7.4.5 三生万物
7.4.6 八卦图及其推演
7.5 结语
第8章 **分类器–支持向量机
8.1 支持向量机的理论基础
8.1.1 经验风险**
8.1.2 关键定理与VC维
8.1.3 结构风险**
8.2 SVM的数学推导
8.2.1 **间隔超平面
8.2.2 拉格朗日乘子法
8.2.3 KKT条件与对偶变换
8.2.4 分类器函数
8.2.5 映射到高维空间
8.2.6 核函数法
8.2.7 离群点的松弛变量
8.3 SMO算法
8.3.1 SMO求解SVM
8.3.2 构造SMO类
8.3.3 主函数
8.3.4 训练数据
8.3.5 分类并评估算法
8.4 SVM中文文本分类
8.4.1 回顾中文文本分类
8.4.2 Scikit-Learn SVM分类
8.4.3 评估结果
8.5 结语
第9章 人脸识别中的机器学习
9.1 模式识别概述
9.1.1 认知与模式

 

　　前 言
　　动机
　　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并称“大数据”技术的基石。
　　2012年11月，微软在天津的一次活动上公开演示了一个全自动的同声传译系统，讲演者用英文演讲，后台的计算机一气呵成自动完成语音识别、英中机器翻译和中文语音合成，效果非常流畅。据报道，后面支撑的关键技术就是DNN，或者深度学习（DeepLearning，DL）。
　　人与动物*本质的区别之一就是人类具有高度发达的智能。千百年来，人类从未停止过对智慧本身的研究与探索。20世纪50年代，图灵就在论文《机器能思考吗》中提出了一个著名测试，后世称为图灵测试：
　　“假如一台机器通过特殊的方式与人沟通，若有一定比例的人（超过30%）无法在特定时间内（5分钟）分辨出与自己交谈的是人还是机器，则可认为该机器具有‘思考’的能力。”
　　这里的思考能力就是指智能。而对于计算机领域而言，它是一个多么奢侈而艰难的字眼。以IBM Watson为例，它由90台IBM服务器、360个计算机芯片驱动组成，是一个有着10台冰箱那么大的计算机系统。它拥有15TB内存，2880台处理器，每秒可进行80万亿次运算。系统配置的处理器是Power 7系列处理器，这是当前RISC（精简指令集计算机）架构中*强的处理器。它采用45nm工艺打造，拥有8个核心、32个线程，主频**可达4.1GHz，仅其二级缓存就达到32MB。
　　在大数据领域，据Google称，其知识图谱的信息有许多来源，包括CIA的世界概况、Freebase和维基百科，其功能与Ask.com和Wolfram Alpha等问题问答系统相似。截至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，并给出基本原理和代码实现。
　　目前机器学习主要由这三条主线贯穿始终，本书着力于讲解这三条主线的理论发展、思想变迁、数学原理，而具体算法就是其上的一颗颗明珠。希望读者在学习完本书之后，能够将机器学习的各种理论融会贯通。