模式识别

一转眼十年又过去了，十年前在出版本书第3版时，我曾经感慨信息时代的到来，而从那以后的这十年，我们则深刻感受到了智能时代的来临。清华大学出版社的老师告诉我，《模式识别》第2版和第3版到目前已经共印刷了38次，总发行量超过10万册。在我平时的工作中，时常收到采用本教材授课的高校教师的问题和建议，也收到一些读者反馈。我要特别感谢这些老师和读者对本教材长期的支持和关爱，也很高兴看到这本教材为这个蓬勃发展的学科贡献了一份力量。
21世纪的前20年，见证了模式识别、机器学习和人工智能学科的飞速发展。这一点从本教材各个版本使用情况的演化也可见一斑。从边肇祺先生主持编写的《模式识别》第1版到边肇祺、张学工共同编写的《模式识别》第2版，当时的读者主要是直接从事本领域研究的教师、研究生和科技工作者，而《模式识别》第3版的读者已经扩展到各个专业对本领域感兴趣的教师、研究生、本科生和科技工作者。模式识别类的课程开始是少数院校在自动化系、计算机系等开设的研究生专业课，现在已经成为很多院系的研究生专业基础课，很多学校和院系开始把模式识别和机器学习类课程作为本科生专业必修课和全校性选修课。在我自己这些年的本科生课堂上，选课同学不但来自计算机、自动化、电子、软件等信息类专业，还有大量同学来自数学、物理、生物、医学以及各种工程类、机械类、管理类专业，也有同学来自建筑学院、美术学院和心理学、社会学、语言学等专业。这一方面说明了各专业同学数理基础和计算机基础的普遍提高，另一方面更从一个侧面映射出了这一学科受欢迎的程度。
从学科本身看，近十年的发展当属深度学习和机器学习与人工智能结合产生出的大量成功应用。在十年前编写第3版教材时刚刚显露头角的深度神经网络和在较小范围内研究的概率图模型等，已经成为受关注的热点。同时，大量机器学习软件平台的出现和发展，也改变了人们以往学习和利用模式识别与机器学习方法的方式。这些日新月异的发展，使我强烈感受到这本教材的内容需要很多更新和补充，但因为其他各种工作太繁忙，早就答应出版社的教材编写计划几次被拖延。2019年底，在与汪小我老师共同准备“模式识别与机器学习”课程时，我邀请汪老师与我共同进行这本书的写作。
2020年初，突如其来的新冠肺炎疫情改变了所有人的生活和工作，也促使每个人更清楚地认识自己对社会和历史的责任。于是，我和汪老师商量决定，与疫情赛跑，在春季学期的远程授课中就采用新版教材的内容，迫使自己在春季学期授课的同时完成本书新版的写作，力争在年内出版。2020年7月19日，我们完成了新版的全部写作，与第3版相比，增加了5章新内容，对原有内容也进行了必要的调整和补充。
对于业内学者来说，“模式识别”与“机器学习”是非常接近和高度相关的概念，但对于尚未学习这些内容的读者，可能会对这两个名词有不同的认识。为了更全面地反映本书的内容范围，我们增加了副标题“模式识别与机器学习”，也据此对很多内容进行了补充和调整。近年来，很多人尤其是产业界和投资界把模式识别和机器学习都放在人工智能的大框架下，因此，我们也在新版第15章专门对“模式识别”“机器学习”“人工智能”三个概念的关系、演化和背后的学术思想进行了讨论。
新版内容的编写得到了很多老师和同学的帮助，尤其是2020年春季学期清华大学自动化系本科生课程“模式识别与机器学习”的助教研究生王昊晨、颜钱明、张威、乔榕，和2019年秋季学期清华大学自动化系研究生英文课程“机器学习”的助教研究生花奎、陈斯杰、马天行、孟秋辰、李嘉骐。在新版的具体内容编写中，第4章隐马尔可夫模型和贝叶斯网络、第10章10.9节的tSNE降维可视化方法、第11章11.8节的一致聚类方法和第12章12.8.2节的实例主要由汪小我负责起草，其中颜钱明帮助计算了10.9节和11.8节的例子； 张威起草了第14章机器学习软件平台的介绍和计算机代码示例； 其他新增章节（第7章、第12章、第15章）和其他章节调整内容均由张学工负责起草，其中王昊晨帮助起草了12.7节生成模型的初稿，第7章采用了《模式识别》第2版中的部分原稿，第12章中采纳了胡越、罗东阳同学之前准备的部分素材。张学工负责了新版的统稿。第12章深度学习的前半部分草稿得到了清华大学自动化系黄高老师的很多建议和指正。马天行、李嘉骐、陈斯杰、孟秋辰、王昊晨、颜钱明、张威、乔榕、张嘉惠等同学帮助对部分书稿进行了文字和公式检查。厦门大学王颖教授对部分公式错误给出了更正。本次主要新增章节草稿在2020年春季清华大学自动化系本科生课程“模式识别与机器学习”中进行了试用。本书的编写也得到了清华大学自动化系古槿、闾海荣、江瑞等老师的帮助，并得到了福州数据技术研究院的大力帮助和支持。
本教材编写得到了清华大学历年来多个教学改革和学科建设项目的支持，教材中涉及的很多科学研究内容，得到了国家自然科学基金创新研究群体项目、杰出青年基金项目和优秀青年基金项目等的支持。

张学工

2020年7月20日

前言

前言

第3版前言

从本书第2版出版到现在已经又是十年了。在这十年里，我们真切地感受到了信息时代的到来。对信息的处理和分析，已经不仅仅是信息科学家所关心的问题，也不仅仅是信息技术产业所关心的问题，而是为很多学科和很多领域共同关心的问题。作为信息处理与分析的重要方面，模式识别也开始从一个少数人关心的专业，变成一个在工程、经济、金融、医学、生物学、社会学等各个领域都受到关注的学科。
模式识别学科的发展，可以从笔者所在的清华大学自动化系在模式识别专业教学和教材上的沿革窥见一斑。早在1978年，在已故中科院学部委员常迵教授的领导下，自动化系成立了信号处理与模式识别教研组，后更名为信息处理研究所，1981年获准成立“模式识别与智能系统”学科（当时称“模式识别与智能控制”）的个硕士点、博士点。从那时起，边肇祺等教授就开始为研究生开设模式识别课程，后逐渐包括进少部分五年级本科生（当时清华大学本科学制为五年）。20世纪80年代中期，边肇祺、阎平凡、杨存荣、高林、刘松盛和汤之永等老师组成了教材编写小组，开始编写模式识别教材，这就是1988年出版的《模式识别》。该教材的出版，为我国模式识别学科的发展做出了历史性的贡献，被很多高校和科研院所作为教材或参考书。十年以后，模式识别学科的内容有了很多更新和发展，我们成立了由边肇祺、阎平凡、赵南元、张学工和张长水组成的改写小组，由笔者与边肇祺老师共同组织编写了本书的第2版，2000年正式出版。此时的模式识别课程，已经由初只有十几位研究生参加的小课，发展为由上百名研究生和高年级本科生参加的大课。第2版教材也得到了国内同行的欢迎，9年内已经重印15次。
随着模式识别学科的日益发展，我们很快认识到，对模式识别课程的需求已经超出了本专业研究生的范围。于是我们将模式识别课程分为两门： 面向研究生的“模式识别”和面向本科生的“模式识别基础”。到今天，本科生“模式识别基础”每年的选课人数也已达到100~150人，除了来自本系的学生，每年还有多位来自其他院系的学生选课。2007年，该课程荣幸地被评为国家精品课程。
在近几年的教学实践中，我们体会到，原来的教材有些地方不太适应大范围教学的需要，而且近十年来模式识别自身以及它在很多领域中的应用又有了很多新发展。因此，笔者从两年前开始着手编写新版教材。新版教材的出发点是： 一方面，结合当前的发展，精炼传统内容，充实新内容，进一步增强实用性，接触学科前沿； 另一方面，在教材的深度和广度上兼顾广大本科生学习的特点和本专业研究生的需求，力求达到使非本专业学生通过本教材能学到足够系统的基本知识，而本专业学生又能以本教材作为其专业研究的重要起点。
编写新版教材所需要的时间超出了我的预想，很高兴她今天终于能和读者见面了。在此要感谢在本书编写过程中给了我很多帮助的同事和同学们，尤其是： 美国南加州大学的Jasmine X. Zhou教授在2007年给我提供了短期访问机会，使我能够有一段相对完整的时间集中开始本书的写作； 蒋博同学通读了本书三分之二的初稿并做了多处补充； 现在已经分别是电子科技大学和北京大学教师的凡时财、李婷婷同学帮助准备了本书部分素材。我还要感谢清华大学出版社王一玲编辑在本书编写过程中的一贯支持。当然，重要的，我要感谢参加本书第1版和第2版编写的所有老师，这不但是因为在这一版中仍使用了前两版的一些内容，更是因为，是这些老师们把我带进了模式识别的大门，使我受益至今。
由于时间仓促和个人水平所限，教材中难免有错误或不足之处，敬请广大同行和读者批评指正，以便在再版时补充和修改。
在本书终完稿的时候，我十岁的女儿以极大的兴致看完了我讲“模式识别基础”课的录像，并说将来长大了要听我讲课。谨以此书献给我的妻子和女儿。

张学工

2009年11月29日

系统介绍模式识别的基本概念、理论体系、典型方法以及实际应用实例，强调基础性和实用性，同时兼顾学科发展的**动向，包括了各种典型方法在R和Matlab环境下的现有程序和应用方法，并包括了对针对大数据应用的模式识别方法的讨论。

张学工，1989年毕业于清华大学，1994年获得博士学位，现为清华大学自动化系教授，清华信息科学与技术国家实验室（筹）生物信息学研究部主任，主要研究方向是模式识别与机器学习、生物信息学与计算生物学。已经在国内外重要期刊发表论文200多篇，出版教材2部、译著2部，曾获国家科技进步二等奖，2006年获得国家杰出青年基金，2009年获教学成果一等奖，所开设的《模式识别基础》课程2007年被评为精品课。

第1章概论

1.1模式与模式识别

1.2模式识别的主要方法

1.3监督模式识别与非监督模式识别

1.4模式识别系统举例

1.5模式识别系统的典型构成

1.6本书的主要内容

第2章统计决策方法

2.1引言： 一个简单的例子

2.2小错误率贝叶斯决策

2.3小风险贝叶斯决策

2.4两类错误率、NeymanPearson决策与ROC曲线

2.5正态分布时的统计决策

2.5.1正态分布及其性质回顾

2.5.2正态分布概率模型下的小错误率贝叶斯决策

2.6错误率的计算

2.6.1正态分布且各类协方差矩阵相等情况下错误率的计算

2.6.2高维独立随机变量时错误率的估计

2.7离散时间序列样本的统计决策

2.7.1基因组序列的例子

2.7.2马尔可夫模型及在马尔可夫模型下的贝叶斯决策

2.7.3隐马尔可夫模型简介

2.8小结与讨论

第3章概率密度函数的估计

3.1引言

3.2似然估计

3.2.1似然估计的基本原理

3.2.2似然估计的求解

3.2.3正态分布下的似然估计

3.3贝叶斯估计与贝叶斯学习

3.3.1贝叶斯估计

3.3.2贝叶斯学习

3.3.3正态分布时的贝叶斯估计

3.3.4其他分布的情况

3.4概率密度估计的非参数方法

3.4.1非参数估计的基本原理与直方图方法

3.4.2kN近邻估计方法

3.4.3Parzen窗法

第4章隐马尔可夫模型与贝叶斯网络

4.1引言

4.2贝叶斯网络的基本概念

4.3隐马尔可夫模型（HMM）

4.3.1HMM评估问题

4.3.2HMM隐状态推断问题（解码问题）

4.3.3HMM学习问题

4.4朴素贝叶斯分类器（Nave Bayes）

4.5在贝叶斯网络上的条件独立性

4.6贝叶斯网络模型的学习

4.6.1贝叶斯网络的参数学习

4.6.2贝叶斯网络的结构学习

4.7讨论

第5章线性学习机器与线性分类器

5.1引言

5．2线性回归

5．3线性判别函数的基本概念

5．4Fisher线性判别分析

5．5感知器

5．6小平方误差判别

5．7罗杰斯特回归

5．8分类超平面与线性支持向量机

5．8．1分类超平面

5．8．2大间隔与推广能力

5．8．3线性不可分情况

5．9多类线性分类器

5．9．1多个两类分类器的组合

5．9．2多类线性判别函数

5．9．3多类罗杰斯特回归与软

5．10讨论

第6章典型的非线性分类器

6．1引言

6．2分段线性判别函数

6．2．1分段线性距离分类器

6．2．2一般的分段线性判别函数

6．3二次判别函数

6．4多层感知器神经网络

6．4．1神经元与感知器

6．4．2用多个感知器实现非线性分类

6．4．3反向传播算法

6．4．4多层感知器网络用于模式识别

6．4．5神经网络结构的选择

6．4．6前馈神经网络与传统模式识别方法的关系

6．4．7人工神经网络的一般知识

6．5支持向量机

6．5．1广义线性判别函数

6．5．2核函数变换与支持向量机

6．5．3支持向量机早期应用举例

6．5．4支持向量机的实现算法

6．5．5多类支持向量机

6．5．6用于函数拟合的支持向量机——支持向量回归

6．6核函数机器

6．6．1大间隔机器与核函数机器

6．6．2核Fisher判别

6．6．3中心支持向量机

6．7讨论

第7章统计学习理论概要

7．1引言

7．2机器学习问题的提法

7．2．1机器学习问题的函数估计表示

7．2．2经验风险小化原则及其存在的问题

7．3学习过程的一致性

7．4函数集的容量与VC维

7．5推广能力的界与结构风险小化原则

7．6支持向量机的理论分析

7．7不适定问题和正则化方法简介

7．7．1不适定问题

7．7．2正则化方法

7．7．3常见的正则化方法

7．8讨论

第8章非参数学习机器与集成学习

8.1引言

8．2近邻法

8．2．1近邻法

8．2．2k近邻法

8．2．3近邻法的快速算法

8．2．4剪辑近邻法

8．2．5压缩近邻法

8．3决策树与随机森林

8．3．1非数值特征的量化

8．3．2决策树

8．3．3过学习与决策树的剪枝

8．3．4随机森林

8．4Boosting集成学习

8．5讨论

第9章特征选择

9．1引言

9．2用于分类的特征评价准则

9．2．1基于类内类间距离的可分性判据

9．2．2基于概率分布的可分性判据

9．2．3基于熵的可分性判据

9．2．4利用统计检验作为可分性判据

9．3特征选择的算法

9．4特征选择的次优算法

9．5遗传算法

9．6包裹法： 以分类性能为准则的特征选择方法

9．7讨论

第10章特征提取与降维表示

10．1引言

10．2基于类别可分性判据的特征提取

10．3主成分分析

10．4KarhunenLoève变换

10．4．1KL变换

10．4．2用于监督模式识别的KL变换

10．5用“本征脸”作为人脸识别的特征

10．6高维数据的低维可视化

10．7多维尺度(MDS)法

10．7．1MDS的基本概念

10．7．2古典尺度法

10．7．3度量型MDS

10．7．4非度量型MDS

10．7．5MDS在模式识别中的应用举例

10．8非线性特征变换方法简介

10．8．1核主成分分析(KPCA)

10．8．2IsoMap方法和LLE方法

10．9tSNE降维可视化方法

10．10讨论

第11章非监督学习与聚类

11．1引言

11．2基于模型的聚类方法

11．3混合模型的估计

11.3.1混合密度的似然估计

11．3．2混合正态分布的参数估计

11．4动态聚类算法

11．4．1C均值算法(K均值算法)

11．4．2ISODATA方法

11．4．3基于核的动态聚类算法

11．5模糊聚类方法

11．5．1模糊集的基本知识

11．5．2模糊C均值算法

11．5．3改进的模糊C均值算法

11．6分级聚类方法

11．7自组织映射(SOM)神经网络

11．7．1SOM网络结构

11．7．2SOM学习算法和自组织特性

11．7．3SOM网络用于模式识别

11．8一致聚类方法

11．9讨论

第12章深度学习

12．1引言

12．2人工神经网络回顾

12．3卷积神经网络(CNN)

12．3．1卷积层

12．3．2汇集(池化)

12．3．3深层卷积神经网络

12．3．4卷积神经网络的演化和几个代表性模型

12．3．5卷积神经网络在非图像数据上的应用举例

12．4循环神经网络(RNN)

12．4．1Hopfield神经网络

12．4．2循环神经网络

12．5长短时记忆模型(LSTM)

12．6自编码器、限制性玻尔兹曼机与深度信念网络

12．6．1自编码器

12．6．2用多层自编码器构造深度神经网络

12．6．3限制性玻尔兹曼机(RBM)

12．6．4深度自编码器与深度信念网络(DBN)

12．7生成模型

12．7．1变分自编码器(VAE)

12．7．2生成对抗网络(GAN)

12．8综合应用举例

12．8．1中文病历文本生成

12．8．2人工基因调控元件的生成

12．9深度学习算法中的部分常用技巧

12．10讨论

第13章模式识别系统的评价

13．1引言

13．2监督模式识别的错误率估计

13．2．1训练错误率

13．2．2测试错误率

13．2．3交叉验证

13．2．4自举法与0．632估计

13．3有限样本下错误率的区间估计

13．3．1问题的提出

13．3．2用扰动重采样估计SVM错误率的置信区间

13．4特征提取与选择对分类器性能估计的影响

13．5用分类性能进行关系推断

13．6非监督模式识别系统性能的评价

13．6．1聚类质量的评价

13．6．2聚类结果的比较

13．7讨论

第14章常用模式识别与机器学习软件平台

1