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

第一章机器学习的基础

“基础决定高度，而不是高度决定基础。”

机器学习脱胎于人工智能，自诞生开始，就充满了挑战，这个领域从来都吸引了全世界最顶尖的科学家，本书所讲述的正是他们多年的研究成果。对于普通读者而言，快速而全面的掌握各类算法技术并不是一件容易的事情。机器学习应用的领域方方面面：从交通运输、医疗诊断到自然语言处理等几乎各行各业都有。为了简化，多数书籍都偏重于数学理论，但即便完全形式化为数学概念，不仅不便于理解，所涉及到的知识也很庞杂。毕竟几十年来，机器学习这座大厦是靠一砖一瓦坚实的构筑起来的。

本章是全书的第一章，主要从程序编码、数据结构、数学理论、数据处理与可视化等几个方面阐述了机器学习相关的理论和技术实现。初看涉及内容比较多，为了避免混乱，我们以矩阵为中心贯穿本章各部分的知识讲解，然后扩展到概率论，数值分析，矩阵分析等知识来逐步引导读者进入机器学习的数学世界。

对大多数读者而言，理解数学原理和推导过程起初会存在一些障碍，这也是初学者们的一大壁垒，很多人虽有兴趣，但每到此处只能望而却步。因此，在数学理论方面，我们并没有罗列大量的公式和晦涩的术语，而是力求结合人们的日常生活，通过深入浅出的案例，使读者由浅入深、循序渐进地接触概念，最终真正领悟内涵。对象与维度、初识矩阵、理解随机性等章节完全不需要高等数学的基础，但是它们所阐述的方法和概念是整个机器学习大厦的基础。

而且幸运的是，由于软件编程方法的日新月异，矢量化编程方式（在第二节将详细介绍）能够将数学公式直观的转换为程序代码，这极大降低了程序设计的难度，多数公式的程序代码仅有1~2行。读者可以从Numpy矩阵运算和Linalg线性代数库两节逐步熟悉矢量化编程的风格，各类距离公式是矢量化编程的应用。除程序设计的之外，这两节也可看作是对线性代数中一些重要概念的回顾，如果读者对线性代数的概念生疏了，可以借此重温一下。总体而言，机器学习对程序设计的要求不高，除去矢量化编程，一般而言都是一些最基本的指令，只要掌握一定的编程技术和高等数学的基本概念，学好本书还是不难的。

各类距离公式、矩阵空间变换对于某些读者而言可能属于新知识。本章涉及的距离公式比较多，但总的来讲都不难，本书也都提供了程序代码。矩阵的空间变换是个重点，后续章节中多有涉及，需要读者认真领会。如果理解上有困难，具体算法上我们还会详细讲解。

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

·2·

总之，我们的目标是使程序设计变为一件轻松、快乐的事情。常言道：“千里之行，始于足下”。现在，就让我们开始激动人心的机器学习之旅吧！

1.1 编程语言与开发环境

1.1.1 搭建python开发环境

“工欲善其事，必先利其器”，还好Python语言还算锋利，一般具有程序设计基础的读者，几周就可掌握本书中所需的语言技术。因此，书中绝大多数程序代码都使用Python语言编写，原因有以下几点：

❑免费、开源：Python语言是免费开源的脚本语言。这两个词几乎成为流

行编程语言必不可少的特征

❑Python编程更简单，相比于编译语言(C,C++)而言，Python是一种跨平台

脚本语言，编写好的代码可以直接部署在各类操作系统上(例如，Linux、

Windows、MAC OS X)；

❑开发和执行效率高，其各种库大多数都是基于C语言编写的(相对于Java

而言)，并适用于32位和64位系统，性能损失小，适合大规模数据处理；

❑丰富的程序库，支持矢量编程，Python在机器学习和自然语言处理方面

提供了完备程序库，包括：机器学习、数学分析、可视化库、GPU并行库等

等；

❑Python支持网络编程，写好的代码可以直接发布到Internet上。

Python 开发环境可以搭建在Linux下，也可以搭建在Windows下，可以是32位的，也可以是64位的。这为开发者提供了很大的灵活性。为了便于初学者学习，本书在Windows7下部署64位的Python开发环境，同时在附录中也提供Linux下的部署方式。

Python可在官方网站直接下载，网址：https://http:///downloads/source/。本书使用的是 2.7-64位版本,下载地址:https://http:///downloads/release/python-279/，所装的库和代码也是以2.7版本为基础的，如果读者使用其他版本，需要做相应的修改。

下面给出在Windows 下简要的安装步骤:

1．双击下载的安装程序：python-2.7.9.amd64.msi，执行安装（如图1.1），如果其他用户不需要python的话，可以使用第二个，不过我们一般都是单用户，所以没差别。

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

·3·

图1.1 python安装步骤1

2．选择安装路径，可按默认路径安装，也可自己新建路径，新建路径一般用英文名比较好，方便命令行访问，本书使用的是C:\python64点击Next（如图1.2）。

图1.2 python安装步骤2

3．其他界面都一路Next，程序开始复制安装文件，复制完文件后点击finish，完成安装（如图1.3）。

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

·4·

图1.3 python安装步骤3

该界面出现，指示安装完成。

1.1.2 安装python算法库

最初，Python社区仿照Matlab开发了类似的数学分析库，主要包括NumPy和SciPy 来处理数据，Matplotlib实现数据可视化。大多数Python数学和算法领域的应用都广泛地将其作为基本的程序库。很快，为了适应处理大规模数据的需求，Python在此基础上开发了Scikit-Learn机器学习算法库(网址: http:///stable/)；同时，还提供了深度学习算法库Theano(网址: http:///software/theano/)，并支持GPU运算。迄今为止，Python已经可以完整地提供基于C/C++的全部机器学习开发包，而且都是开源版的，有兴趣的朋友还可以下载源码包学习。后面的章节将详细讲解这些库的使用，这里就不再赘述了。

除此之外，Python也提供了大量的常用程序库，例如数据库API(MysqlDB)、GUI 图形界面库(WxPython)、高并发协程库(gevent)、中文分词库(jieba)等外部库。所有这些库可以从下面两个网址查询到：

❑官方下载地址：https://http:///pypi

❑非官方下载地址：http://www.lfd.uci.edu/~gohlke/pythonlibs/

最值得称道的是，这些算法库不仅安装非常简便，而且均提供32位和64位两个版本，并分别支持2.6，2.7，3.3，3.4不同版本的Python应用。

安装顺序与步骤：

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

·5·

❑ Python 算法库的安装非常简单:

执行C:\Python64\Scripts\pip install 库名(小写字母不加后缀)

❑ Python 算法库的安装顺序:

1. Numpy

2. Scipy

3. Matplotlib

4. Scikit-Learn

上述每个库安装完成后，都会提示如下信息： Successfully installed xxx(库名)

Cleaning up.. 表示此库安装成功。

1.1.3 IDE 配置及其安装测试

Python 的各类算法库安装完成之后，一般需要选个开发平台(IDE)编写代码。本书的核心内容偏重算法设计，对IDE 要求不高，推荐使用Ultraedit 高级文本编辑器。主要考虑资源占用较小，功能较强，支持多种文件编码转换，并有支持远程开发等优势（本地可同步远程Linux 上的源代码，本地编写，远程上运行）。网上可以下载安装绿色版的软件。下载完成之后，需要进行如下配置：

1. 在点击“高级”选项卡，点开“工具栏配置”（如图1.4）：

图1.4 配置Ultraedit 步骤1

2.

按下图界面输入,并“应用”（如图1.5）：

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

·6·

图1.5 配置Ultraedit 步骤2

3. 按下图界面输入，并点击“确定”（如图1.6）：

图1.6 配置Ultraedit 步骤3

这样Ultraedit

就算配置完成了。下面我们开始编写一些测试代码。因为安装的模

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

·7·

块比较多，简单的Hello World测试不能说明问题, 过于复杂的程序又容易使人费解。为此，我们简单编写一个应用程序用于测试，运行下面的测试代码，可以检验安装的效果。

代码文件mytest1.py：

# -*- coding: utf-8 -*-

# Filename : mytest1.py

import numpy as np # 导入numpy库

from numpy import * # 导入numpy库

import matplotlib.pyplot as plt # 导入matplotlib库

# 测试数据集-二维list

dataSet = [[-0.017612,14.053064],[-1.395634 ,4.662541],[-0.752157

,6.538620],[-1.322371 ,7.152853],[0.423363 ,11.054677],[0.406704

,7.067335],[0.667394 ,12.741452], [-2.460150 ,6.866805],[0.569411

,9.548755],[-0.026632 ,10.427743],[0.850433 ,6.920334],[1.347183

,13.175500],[1.176813 ,3.167020],[-1.781871 ,9.097953]]

dataMat = mat(dataSet).T # 将数据集转换为numpy矩阵，并转置

plt.scatter(dataMat[0],dataMat[1],c='red',marker='o') # 绘制数据集散点图

# 绘制直线图形

X = np.linspace(-2,2,100) # 产生直线数据集

# 建立线性方程

Y = 2.8*X+9

plt.plot(X,Y) # 绘制直线图

plt.show() # 显示绘制后的结果

输出结果（如图1.7）：

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

·8·

图1.7 显示执行结果

说明主要模块安装成功。

1.2 对象、矩阵与矢量化编程

有了工具，很多事情就变得方便了。现在，我们正式进入机器学习的基础知识。简单回忆一下绪论部分所提出的三种对象类型：文本、表格、图。乍一看，有点眼花缭乱，仔细分析下来，三种结构虽各有千秋，却存在着共性。

1.2.1 对象与维度

对于大多数程序员而言，对象应该不是个陌生的概念。在面向对象的程序设计思想中，对象就是一个类的实例。机器学习中的对象与之很相似，在机器学习中，对象是指含有一组特征的行向量。而行向量的集合最容易构造的结构就是表。下面我们来观察一张表（如表1.1），此表来源于现实中真实的统计数据：

表1.1 大型动物与水果

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

·9·

表中第一行黑体字：种属、重量(平均)、颜色(主)、生命周期/保质期表示为特征名称。所有特征组合在一起构成一组行向量，也称为特征向量，我们为了区别线性代数中的特征值和特征向量引入对象这个名称。以非洲象、大白鲨等开头的数据行就是一组行向量，也是一个对象。对象的维度就是行向量的列数，上述数据集的维度为5。

在实际计算中，除非特殊情况，特征名称不需列明；含有字符串的对象名称因无法直接参与运算，一般情况下可以编码为数字，我们将种属特征转换为是否动物（用布尔值0,1替代），颜色特征转换为十六进制。各列的特征值为了计算方便，应统一单位，区间值可以选择中间值。为了方便量化，表1.1删除第一列，大型动物与水果表就转换为（如表1.2）：

表1.2 大型动物与水果表

此时，该表被转换为4行、4列的数据表，维度为4。有过一些线性代数知识的朋友可以很简单的将此表转换为下面的矩阵（如表1.3）：

表1.3 大型动物与水果矩阵

1 5000 #DCDCDC 70*365

1 3200 #9D9D9D 70*365

0 0.25 #FF0000 10

0 0.3 #FFFF00 7

一般而言一个对象应被视作完整的个体，代表现实中有意义的事物，不能轻易拆分。它的表现形式可能多种多样，例如在图像识别中它可能是一张图片（如图1.8）：

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

·10·

图1.8 手写体识别中的“0”

上图是向量化的手写体图片。注意，上图的维度，即行向量的个数是32*32个，整张图被当作一行或者一个对象。因为，整张图仅代表一个完整的事物，表达了一个完整的意义。一般来说，图片数据集的维度都比较高。

文本类数据集有点特殊，需要首先生成词袋列表，再根据每个词出现的词频数值化，不过仔细想想也万变不离其宗。例如，如下文本数据集:

文本1：My dog ate my homework。

文本2：My cat ate the sandwich。

文本3：A dolphin ate the homework。

根据上述三段短文本中出现的词汇，生成词袋列表，该列表记录了上述文本中出现的每个不重复的词：

[a, ate, cat, dolphin, dog, homework, my, sandwich, the]

各段文本根据生成的词袋列表转换为对象，其维度就是词袋列表的长度，计算结果是32维。向量化后的文本称为词向量。

各段文本向量化后的词向量，其中0表示词袋中对应的词未出现在文本中，1表示该词出现在文本中1次，如果多次出现，则累加（如表1.4）：

表1.4 词向量空间

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

·11·

1.2.2 初识矩阵

在线性代数中我们学过，矩阵是由m×n个数组成的一个m行n列的矩形表格，或者更深一点的定义，表示由方程组的系数及常数所构成的二维数据表。从机器学习的角度来看，这两个定义都合适，又都不合适。

现在，我们重新考察一下矩阵。上一节，我们有了表和对象的概念。对象是被特征化的客观事物，而表是容纳这些对象的容器。换句话说，对象是表中的元素，表是对象的集合。但这个集合有点特殊，即表中的每个对象都有相同的特征和维度，对象对于每个特征都有一定的取值。这里矩阵可以理解为，具有相同特征和维度的对象集合。

总结一下：

❑矩阵是具有相同特征和维度的对象集合，表现为一张二维数据表；

❑一个对象表示为矩阵中的一行，一个特征表示为矩阵中的一列，每个特

征都有数值型的取值；

❑特征相同、取值相异的对象集合所构成的矩阵，使对象之间既相互独立，

又相互联系；

❑由特征列的取值范围所有构成的矩阵空间，应具有完整性，即能够反映

出事物的空间形式或变化。（再谈矩阵一节中详细说明）

关于第三点，我们再观察表1.4：动物种属和植物种属是两个风马牛不相及的概念，但如果放到一张表中，我们必须使用一组特征向量来衡量它们，比如：种属、重量、颜色、生命周期(年龄有点牵强)等等。但不能用味道这个特征来衡量，因为大象和鲨鱼很难讲是酸是甜。这就是各类对象之间的联系。

如果不看实例名称，我们从是否动物、重量、颜色、生命周期几个特征也能很容易的分辨出两类对象的差异性。例如，大象重量和苹果重量的悬殊差异，或生命周期/保质期的悬殊差异。这反映了对象间的相互独立。

我们再扩展一下这个例子（如表1.5）：

表1.5 扩展表1.2

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

·12·

除差异性之外，表1.5中还有一类情况，苹果和梨、大象和鲨鱼。在是否动物、重量和生命周期三个特征中，苹果和梨具有相似性，大象和鲨鱼具有相似性。很明显，大象与鲨鱼的重量较之苹果(或梨)的重量更相似；或者大象与鲨鱼的寿命较之苹果(或梨)的保质期更相似；由于这种相似性，我们很自然地可以将苹果和梨分为一类：水果（区别于植物）；大象和鲨鱼分为一类：大型动物（区别于动物）。

由此可见，分类或聚类可以看作是根据对象特征的相似性与差异性，对矩阵空间的一种划分。

下面，我们再看另一个例子(如表1.6)：

表1.6 2-18岁正常男生体重身高对照表

这个表列举了2~18岁男生的正常体重、身高的变化。数值上呈现一种递增的趋势，每个对象都与上一行或下一行的对象在时间上相关，并且时间间隔相等，都为1年。这种时间上的相关性使矩阵反映出某一事物在时间上连续变化的过程。

由此可见，预测或回归可以看作根据对象在某种序列(时间)上的相关性，表现为特征取值变化的一种趋势。

分类、聚类和回归是机器学习最基本的主题。通过矩阵，可以构建客观事物的多维度数学模型，并通过条件概率分布、梯度、神经网络、协方差等等运算方式，多角度认识和分析事物。

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

·13·

具体来讲，矩阵有三个重要用途，第一是解线性方程组，比如二维矩阵可以理解为一个平面直角坐标系内的点集，通过计算点与点之间的距离，完成聚类、分类或预测，类似的运算完全可以扩展到多维的情况。第二个用途是方程降次，也就是利用矩阵的二次型，通过升维将线性不可分的数据集映射到高维中，转换为线性可分的情形，这是支持向量机的基本原理之一。第三个用途是变换，矩阵可以通过特征值和特征向量，完成维度约简，简化类似图片这种高维数据集的运算，主成分分析使用的就是这个原理。

在程序设计中，我们可以从形式上把矩阵理解为一个二维数组。以Python语言为例，矩阵就是嵌套着若干个list的一个大list。内部的每个list都是等长的，其中每个元素都是整型或浮点型的数值。内部的list就是行向量，即一个对象。

Numpy数据包提供了专门的矩阵数据结构和线性代数库。从下一节开始，我们将详细介绍Numpy的矩阵运算。

1.2.3 矢量化编程与GPU运算

传统的计算机设计语言，例如C语言，是针对标量的，虽然也提供诸如数组、二维数组的数据结构，但这些结构的赋值、加法、数乘、转置、矩阵相乘还是要通过循环语句完成，十分麻烦，导致程序设计的复杂度也比较高。

mylist = [1,2,3,4,5]

length = len(mylist)

a = 10

for indx in xrange(length):

mylist[indx] = a*mylist[indx]

print mylist

输出结果：

[10, 20, 30, 40, 50]

而基于矩阵的算法都是针对向量的，这里也称为矢量。为了简化程序的逻辑，就需要一种新的编程方法，处理基于矩阵的基本运算，这就是所谓的矢量化编程。

随着程序设计的发展，使用计算机实现矩阵运算越来越方便。最早实现矢量化编程的语言是Matlab的脚本语言，它极大的降低了数学领域程序设计的复杂度。因此大量的人工智能算法最早都是用Matlab语言写的。

Python自带的List结构，提供切片的功能可以部分实现矢量化编程。其扩展包Numpy提供了专门的矩阵数据结构和线性代数库，完全实现了矢量化编程。

import numpy as np

mylist = [1,2,3,4,5]

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

·14·

a = 10

mymatrix = np.mat(mylist)

print a*mymatrix

输出结果：

[[10 20 30 40 50]]

矢量化编程的一个重要特点就是可以直接将数学公式转换为相应的程序代码，极大方便了程序的阅读和调试，使复杂数学公式的实现变得简单和方便，本节和下一节所用的矢量化程序的代码一般只有一两行，即可完成复杂的数学运算。

无论是Matlab还是Python的矢量化编程都可以无缝的调用底层的C函数，还可以提高算法速度。为了提升特定数值运算操作，例如矩阵相乘、矩阵相加、矩阵-向量乘法、浮点运算的速度，数值计算和并行计算的研究人员已经努力了几十年。这个领域最出色的技术就是使用图形处理器的GPU运算。

英伟达（nVidia）公司在1999年发布GeForce256图形处理芯片时首先提出了GPU 运算的概念。十几年的发展使单个GPU芯片在浮点运算、大规模并行计算方面，可以提供数十倍乃至上百倍于CPU的性能。GPU的流处理器也由几十个增加到最新的三千多个，浮点运算TFlops值也达到5以上。本书的第十章的深度学习部分专门讲解了GPU运算的Python框架Theano。

对GPU运算比较熟悉的读者也可以将本书中较大规模的矩阵运算交由GPU完成。

1.2.4 理解数学公式与Numpy矩阵运算

为了便于理解后续章节算法部分的讲解，本节将常用的矩阵数学公式和程序代码对应出来，读者可根据自己需求有选择的学习。因使用矢量编程的方法，矩阵的基本运算得到了较大的简化。

1.矩阵的初始化：

import numpy as np # 导入numpy包

1.1创建一个3*5的全零矩阵和全1矩阵

myZero = np.zeros([3,5]) # 3*5的全零矩阵

print myZero

myOnes = np.ones([3,5]) # 3*5的全1矩阵

print myOnes

输出结果：

[[ 0. 0. 0. 0. 0.]

[ 0. 0. 0. 0. 0.]

[ 0. 0. 0. 0. 0.]]

[[ 1. 1. 1. 1. 1.]

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

·15·

[ 1. 1. 1. 1. 1.]

[ 1. 1. 1. 1. 1.]]

1.2生成随机矩阵：

myRand = np.random.rand(3,4) # 3行4列的0~1之间的随机数矩阵

print myRand

输出结果：

[[ 0.79473503 0.4682515 0.53933591 0.94568244]

[ 0.52199975 0.81190881 0.41920671 0.16756969]

[ 0.57211218 0.53727222 0.83488426 0.30227915]]

1.3单位阵：

myEye = np.eye(3) # 3*3的单位阵

print myEye

输出结果：

[[ 1. 0. 0.]

[ 0. 1. 0.]

[ 0. 0. 1.]]

2.矩阵的元素运算：是指矩阵在元素级别的加、减、乘、除运算

from numpy import * #导入numpy包

2.1元素相加和相减：条件，矩阵的行数和列数必须相同

数学公式：(A ± B)i,j A i,j ± B i,j，

myOnes = ones([3,3]) # 3*3的全1矩阵

myEye = eye(3) # 3*3的单位阵

print myOnes+myEye # 矩阵相加

print myOnes-myEye # 矩阵相减

输出结果：

[[ 2. 1. 1.]

[ 1. 2. 1.]

[ 1. 1. 2.]]

[[ 0. 1. 1.]

[ 1. 0. 1.]

[ 1. 1. 0.]]

2.2矩阵数乘：一个数乘以一个矩阵

数学公式：(c A)i,j = c ·A i,j.

mymatrix = mat( [[1,2,3],[4,5,6],[7,8,9]])

a = 10

print a*mymatrix

输出结果：

[[10 20 30]

[40 50 60]

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

·16·

[70 80 90]]

2.3矩阵所有元素求和：

数学公式：i,j 11sum(A) 1<i<m,1<j<n m n i j A

===∑∑其中

mymatrix = mat([[1,2,3],[4,5,6],[7,8,9]] )

print sum(mymatrix)

输出结果： 45

2.4矩阵各元素的积：矩阵的点乘同维对应元素的相乘。当矩阵的维度不相同时，会根据一定的广播规则将维数扩充到一致的形式，

数学公式：(A.*B)ij = A ij * B ij

mymatrix = mat( [[1,2,3],[4,5,6],[7,8,9]])

mymatrix2 = 1.5*ones([3,3])

print multiply(mymatrix,mymatrix2)

输出结果： [[ 1.5 3. 4.5]

[ 6. 7.5 9. ]

[ 10.5 12. 13.5]]

2.5 矩阵各元素的n 次幂：n=2

数学公式：A ij 2 = A ij * A ij

mylist = mat( [[1,2,3],[4,5,6],[7,8,9]])

print power(mymatrix,2)

输出结果：

[[ 1 4 9]

[16 25 36]

[49 64 81]]

4. 矩阵的乘法：矩阵乘矩阵

数学公式：i,j i,11,j i,22,j i,n n,j i,r r,j 1[A,B]=B +B ...B B n r A A A A =++=

∑

from numpy import *

mymatrix = mat([[1,2,3],[4,5,6],[7,8,9]])

mymatrix2 = mat([[1],[2],[3]])

print mymatrix*mymatrix2 输出结果：

[[14]

[32]

[50]]