第3章分类问题
本章学习要点
 了解分类问题的基本概念与常用术语。
 了解并掌握基于后验概率的贝叶斯分类器设计原理与常用方法。
 了解并掌握基于特征直接建立判别函数的非贝叶斯分类器设计原理与常用方法。
 了解多分类问题，以及将其拆分成二分类问题的策略。
 了解常用的分类模型评价指标。
 了解特征降维的基本原理及常用方法。

为了认识客观世界，人们按相似程度将客观事物划分成类别(class)。从不同角度观察客观事物会得到不同的属性，这种属性被称作客观事物的特征(feature)。可以基于特征定义距离(distance)，用于度量事物间的相似程度，距离的定义可以有各种形式。同类事物之间的相似度高，相互间的特征距离就小； 反之，不同类的事物之间相似度低，特征距离就大。
给定样本特征，将其划归某个类别，这就是分类(classification)问题，或称为识别(recognition)问题。与回归分析相比，回归是一种定量分析，而分类则是一种定性分析。分类是人类最基本的智力活动之一，分类问题也因此成为机器学习中最基本、研究也最为广泛的问题之一。如何让计算机具备学习能力，解决分类问题呢？首先需要对分类问题进行抽象、建模，然后基于特征建立判别函数(discriminant function，或称决策函数)，并根据判别函数进行分类决策。机器学习将分类所用的判别函数称作分类器(classifier)。
可以借助统计学相关的理论与方法来解决分类问题。类别是一个集合概念，例如苹果、香蕉是两类水果，分别代表两类水果的集合。从概率论角度，类别是一种离散型随机变量，其值域是一个离散的类别集合，例如{苹果，香蕉}； 特征也是随机变量(离散型或连续型)，不同类别的特征服从不同的概率分布，例如苹果与香蕉的颜色就服从不同的概率分布。各
类别的特征概率分布被称为该类别的模式(pattern)，基于概率分布进行分类的问题也因此被称为模式识别(pattern recognition)问题。贝叶斯(Bayes)决策是统计决策中一种建立判别函数、解决分类问题的基本方法。
也可以借助计算机科学中的算法设计思想，直接基于特征(而不是特征的概率分布)来设计分类算法，建立判别函数，从而解决分类问题，例如k近邻方法、线性判别分析、决策树等。本章将这些分类器统称为非贝叶斯决策。

3.1贝叶斯分类器
在分类问题中，分类错误率(或正确率)是一个重要的评价标准。所谓贝叶斯分类器，就是给定特征X，然后基于条件概率P(Y=ci|X)进行决策分类，将类别Y判定为条件概率最大的ci。这种分类规则能使分类错误率最小(即正确率最大)，因此贝叶斯分类器是一种错误率最小的分类器。应用贝叶斯分类器解决分类问题，首先需通过样本训练集建立起问题的概率模型。




3.1.1贝叶斯决策
由已知条件推出未知结论，这就是逻辑推理。如果已知条件、未知结论都是随机的，需要由已知条件推出未知结论的概率，这就是概率推理。贝叶斯公式是概率论中一个基本的概率推理公式。

1. 贝叶斯公式与贝叶斯决策
贝叶斯公式设离散型随机变量Y的值域为ΩY={c1,c2,…,cn}且P(Y=ck)>0，k=1,2,…,n，则对任意的随机变量X，P(X)>0，有
P(Y=ck|X)=P(X,Y=ck)P(X)

=P(X|Y=ck)P(Y=ck)∑nk=1P(X|Y=ck)P(Y=ck)，k=1,2,…,n
(31)

或将Y=ck简写成Yk，有
P(Yk|X)=P(X,Yk)P(X)=P(X|Yk)P(Yk)∑nk=1P(X|Yk)P(Yk)，k=1,2,…,n(32)

式（31）或式（32）被称为贝叶斯公式。贝叶斯公式有什么用处呢？假设用Y表示原因，X表示结果，则式（32）可改写为
P(原因k|结果)=P(结果|原因k)P(原因k)∑nk=1P(结果|原因k)P(原因k)，k=1,2,…,n

贝叶斯公式的意义在于它建立了概率P(结果|原因)与P(原因|结果)之间的桥梁。如果已知什么原因可能导致什么结果，则通过贝叶斯公式就可以在已知结果的情况下反推其背后的原因。这一点非常有用，例如医学知识告诉我们什么疾病(病因)可能有什么症状(结果)，利用贝叶斯公式就可以反过来通过症状去诊断疾病。在分类问题中，特征是可观测的结果，类别是不可观测的原因，分类就是依据特征去推测类别。
依据随机事件的概率进行推理与决策，这就是统计决策。基于贝叶斯公式进行概率推理与决策，这就是贝叶斯决策。
贝叶斯决策设离散型随机变量Y的值域为ΩY={c1,c2,…,cn}且P(Yk)>0，k=1,2,…,n，对任意的随机变量X，P(X)>0，如果
k*= argmaxk=1,2,…,nP(Yk|X)(33)

则判定： 给定X时Y=ck*。
将贝叶斯决策规则应用于分类问题，式（33）中的随机变量Y表示类别(共n个类别)，X表示分类特征。假设已求得P(Y=ck|X)，k=1,2,…,n，则给定特征X时可基于式（33）的贝叶斯决策规则判定，特征X所描述事物的类别为ck*。这时，式（33）就是一个分类判别函数，它被称为贝叶斯分类器(Bayes classifier)。可以证明，在已知概率分布的情况下，贝叶斯分类器是错误率最小的分类器。因为式（32）中P(Yk|X)的计算公式具有共同的分母P(X)，所以式（33）等价于
k*= argmaxk=1,2,…,nP(X,Yk)= argmaxk=1,2,…,nP(X|Yk)P(Yk)(34)

设计贝叶斯分类器，最主要的工作就是通过样本数据获得(估计)分类所需的概率分布。通过样本数据能比较容易地估计出特征概率分布P(X)、类别概率分布P(Yk)，以及各类的特征条件概率P(X|Yk)。而类别条件概率P(Yk|X)则需要使用式（32）的贝叶斯公式，通过P(X)、P(Yk)和P(X|Yk)计算出来，在此基础上再使用式（33）进行分类决策。如果改用式（34）的判别函数，则不需要知道P(X)，只需要P(Yk)和P(X|Yk)就可以进行分类决策，这样可以有效简化分类决策的计算过程。
式（32）中，P(Yk|X)为类别条件概率，P(X,Yk)为联合概率分布，P(X)为特征概率分布，P(Yk)为类别概率分布，P(X|Yk)为各类的特征条件概率。其中，类别概率分布P(Yk)是给定样本特征之前的先验知识，贝叶斯决策将其称为类别分布的先验概率(prior probability)； 而类别条件概率P(Yk|X)是获得样本特征信息X之后对先验概率P(Yk)的更新，因此被称为类别分布的后验概率(posterior probability)。贝叶斯公式可以被看作一个将先验概率更新为后验概率的公式。

2. 贝叶斯分类器举例
下面就以一个苹果分类的例子，详细讲解贝叶斯决策的过程。红富士和国光是两个非常知名的苹果品种，如图31所示。


图31两个知名的苹果品种


红富士苹果(见图31（a）)为大型果，单果重180~400g； 底色淡黄或黄绿，着暗红或鲜红色霞； 外形呈扁圆或近似圆形； 口感甜脆。国光苹果(见图31（b）)为中型果，平均果重150g左右； 底色黄绿或绿色； 果实为扁圆形； 口感酸甜。假设随机采集到如表31所示的10个样本苹果，希望能基于这个样本数据集建立起苹果的品种分类模型。本例只有两个类别(红富士或国光)，机器学习将只有两个类别的分类问题称作二分类(binary classification)问题。相应地，将具有多个类别的分类问题称作多分类(multiclass classification)问题。


表31红富士和国光苹果样本(样本容量为10)




编号底色外形口感果重/g品种
1黄圆甜190红富士
2黄绿扁圆酸甜260红富士
3绿扁圆酸甜150国光
4黄绿圆甜200红富士
5绿扁圆酸甜210国光
6黄绿扁圆酸甜170国光
7黄圆酸甜200红富士
8黄绿扁圆酸甜230红富士
9绿扁圆甜180国光
10黄绿扁圆酸甜240红富士

表31是原始苹果样本数据，其中的底色、外形、口感和果重是4个可用于分类的特征数据X，品种则是分类的目标Y。建立分类模型，需要先估计概率分布P(X)、P(Y)和P(X|Y)，然后使用式（32）的贝叶斯公式计算出后验概率P(Y|X)，最后再使用式（33）的贝叶斯分类器进行分类。

1) 使用单个离散型特征的贝叶斯分类器
假设选取表31中的“口感”作为苹果品种的分类特征X，这是一个离散型随机变量，其值域为{甜，酸甜}，只有两个取值。记“甜”为x1，“酸甜”为x2，特征X的概率分布包含两项，即P(X=x1)、P(X=x2)。可以统计样本数据集“口感”一列“甜”和“酸甜”出现的次数来估计特征X的概率分布P(X)。记分类目标“品种”为Y，其值域为{红富士，国光}，记“红富士”为c1，“国光”为c2，同理可以通过样本数据集估计出类别概率分布P(Y)。估计概率分布P(X)、P(Y)的过程及结果如表32所示。


表32特征概率分布P(X)与类别概率分布P(Y)



类别
口感： X品种： Y

甜： x1酸甜： x2红富士： c1国光： c2

出现次数X=x1： 3

X=x2： 7Y=c1： 6

Y=c2： 4
概率分布P(X=x1)=3/10

P(X=x2)=7/10P(Y=c1)=6/10

P(Y=c2)=4/10

估计特征条件概率P(X|Y)时需要先给定类别Y(红富士或国光)，然后将该类别的样本数据筛选出来并生成子集。估计特征X在子集上的概率分布，其结果就是类别Y的特征条件概率P(X|Y)。表33给出了红富士、国光苹果特征条件概率P(X|Y)的估计过程及结果。


表33红富士与国光苹果的特征条件概率P(X|Y)



类别



品种Y

口感X|Y=红富士c1口感X|Y=国光c2

甜： x1酸甜： x2甜： x1酸甜： x2

出现次数X=x1： 2

X=x2： 4X=x1： 1

X=x2： 3
概率分布P(X=x1|Y=c1)=2/6

P(X=x2|Y=c1)=4/6P(X=x1|Y=c2)=1/4

P(X=x2|Y=c2)=3/4

表32、表33的P(X)、P(Y)和P(X|Y)，就构成了一个完整的苹果分类问题的概率分布模型。任意给定新样本的口感特征X，例如口感“酸甜”，可表示为(X=x2)，可以使用式（32）所示的贝叶斯公式计算出后验概率P(Y|X)，即
P(Y1|X)=P(X,Y1)P(X)=P(X=x2|Y1)P(Y1)P(X=x2)=46×610710=47

或
P(Y1|X)=P(X,Y1)P(X)=P(X=x2|Y1)P(Y1)∑2i=1P(X=x2|Yi)P(Yi)=46×61046×610+34×410=47

同理，可得
P(Y2|X)=P(X,Y2)P(X)=P(X=x2|Y2)P(Y2)P(X=x2)=34×410710=37

因为P(Y1|X)>P(Y2|X)，根据式（33）所示的贝叶斯决策，将口感酸甜的苹果判定为c1(红富士)。
如果改用式（34）所示的贝叶斯决策，则不需要知道特征概率分布P(X)，只需计算
P(X=x2|Y1)P(Y1)=46×610=410

P(X=x2|Y2)P(Y2)=34×410=310

因为P(X=x2|Y1)P(Y1)>P(X=x2|Y2)P(Y2)，所以将口感酸甜的苹果判定为c1(红富士)。这与式（33）所示的贝叶斯决策的结论相同，但计算过程简化了。

2) 使用两个离散型特征的贝叶斯分类器
假设选取表31中的“口感”和“外形”两项作为苹果品种的分类特征，这是两个离散型随机变量，可记作X=(X1,X2)，其值域是{甜，酸甜}和{圆，扁圆}的组合，即{(甜，圆)，(甜，扁圆)，(酸甜，圆)，(酸甜，扁圆)}，共有4种取值。记“甜”为x11，“酸甜”为x12； 再记“圆”为x21，“扁圆”为x22，特征X的概率分布包含4项，即P(X=(x11，x21))、P(X=(x11，x22))、P(X=(x12，x21))和P(X=(x12，x22))。
可以统计样本数据集的数据，估计出特征X的概率分布P(X1,X2)、类别概率分布P(Y)，还有特征条件概率P(X1,X2|Y)，上述估计过程及结果如表34、表35所示。


表34特征概率分布P(X1,X2)与类别概率分布P(Y)




类别


(口感，外形)： X=(X1,X2)品种： Y

甜x11，酸甜x12； 圆x21，扁圆x22红富士： c1国光： c2


出现次数X=(x11，x21)： 2

X=(x11，x22)： 1

X=(x12，x21)： 1

X=(x12，x22)： 6Y=c1： 6

Y=c2： 4
概率分布P(X=(x11，x21))=2/10

P(X=(x11，x22))=1/10

P(X=(x12，x21))=1/10

P(X=(x12，x22))=6/10P(Y=c1)=6/10

P(Y=c2)=4/10



表35红富士与国光苹果的特征条件概率P(X1,X2|Y)



类别


品种Y

(口感，外形)X|Y=红富士c1(口感，外形)X|Y=国光c2
甜x11，酸甜x12； 圆x21，扁圆x22甜x11，酸甜x12； 圆x21，扁圆x22

出现次数X=(x11，x21)： 2

X=(x11，x22)： 0

X=(x12，x21)： 1

X=(x12，x22)： 3X=(x11，x21)： 0

X=(x11，x22)： 1

X=(x12，x21)： 0

X=(x12，x22)： 3
概率分布P(X=(x11，x21)|Y=c1)=2/6

P(X=(x11，x22)|Y=c1)=0/6

P(X=(x12，x21)|Y=c1)=1/6

P(X=(x12，x22)|Y=c1)=3/6P(X=(x11，x21)|Y=c2)=0/4

P(X=(x11，x22)|Y=c2)=1/4

P(X=(x12，x21)|Y=c2)=0/4

P(X=(x12，x22)|Y=c2)=3/4

表34、表35的P(X1,X2)、P(Y)和P(X1,X2|Y)，就构成了一个完整的苹果分类问题的概率分布模型，其中使用了两个离散型分类特征，需计算它们的联合概率分布或联合条件概率分布。任意给定新样本的口感、外形特征X，例如(酸甜，扁圆)，可表示为(X=(x12，x22))。使用式（34）所示的贝叶斯决策，有
P(X=(x12，x22)|Y1)P(Y1)=36×610=310

P(X=(x12，x22)|Y2)P(Y2)=34×410=310

因为P(X=(x12，x22)|Y1)P(Y1)、P(X=(x12，x22)|Y2)P(Y2)两者相等，所以可以将具有(酸甜，扁圆)特征的苹果判定为c1(红富士)，也可以判定为c2(国光)。

3) 使用离散型、连续型混合特征的贝叶斯分类器
假设选取表31中的“口感”和“果重”两项作为苹果品种的分类特征，“口感”特征是离散型随机变量，而“果重”特征是连续型随机变量。统计样本数据集的数据，可以很容易地估计出离散型随机变量的概率分布，而估计连续型随机变量的概率分布则相对比较复杂。
估计连续型随机变量概率分布常用的方法： 先假设随机变量服从某种概率分布，例如正态分布N(μ,σ2)，然后使用极大似然估计方法估计出其中的参数μ和σ，最终求得随机变量的概率密度函数。表36、表37给出了估计离散型、连续型混合特征联合概率分布P(X1,X2)、类别概率分布P(Y)和混合特征联合条件概率分布P(X1,X2|Y)的大致过程。习惯上，大写字母P表示离散型随机变量的概率分布或连续型随机变量的分布函数，小写字母p表示连续型随机变量的概率密度函数。


表36特征概率分布P(X1,X2)与类别概率分布P(Y)



类别


(口感，果重)： X=(X1,X2)品种： Y

甜x11，酸甜x12； 果重x2∈R红富士： c1国光： c2

出现次数X=(x11，x2)： 3

X=(x12，x2)： 7Y=c1： 6

Y=c2： 4
概率分布P(X1=x11)=3/10

P(X1=x12)=7/10

p1(x2|X1=x11)~N(μ1,σ21)

p2(x2|X1=x12)~N(μ2,σ22)

P(X1,X2)=P(X2|X1)P(X1)P(Y=c1)=6/10

P(Y=c2)=4/10



表37红富士与国光苹果的特征条件概率P(X1,X2|Y)



类别


品种Y

(口感，果重)X|Y=红富士c1(口感，果重)X|Y=国光c2
甜x11，酸甜x12； 果重x2∈R甜x11，酸甜x12； 果重x2∈R


出现次数X=(x11，x2)： 2

X=(x12，x2)： 4X=(x11，x2)： 1

X=(x12，x2)： 3
概率分布P(X1=x11)=2/6

P(X1=x12)=4/6

p1(x2|X1=x11)~N(μ1,σ21)

p2(x2|X1=x12)~N(μ2,σ22)

P(X1,X2|Y=c1)=P(X2|X1)P(X1)P(X1=x11)=1/4

P(X1=x12)=3/4

p3(x2|X1=x11)~N(μ3,σ23)

p4(x2|X1=x12)~N(μ4,σ24)

P(X1,X2|Y=c2)=P(X2|X1)P(X1)

估计表36的混合特征联合概率分布P(X1,X2)时，需先按离散型特征“口感”(X1，甜或酸甜)将样本数据拆分成两个子集； 然后使用极大似然估计方法估计出连续型特征“果重”X2在子集上的概率密度函数p(x2|X1)，例如服从正态分布N(μ,σ2)时需估计其参数μ和σ； 最后再计算混合特征的联合概率分布P(X1,X2)=P(X2|X1)P(X1)。对于表37的混合特征联合条件概率分布P(X1,X2|Y)，可以使用类似的方法进行估计。
表36、表37的P(X1,X2)、P(Y)和P(X1,X2|Y)，就构成了一个完整的苹果分类问题的概率分布模型，其中使用了一个离散型特征和一个连续型特征。可以看出，随着特征数的增加、离散型与连续型的混合，特征联合概率密度的估计难度不断加大。贝叶斯分类器的难点在于概率分布的估计。
在已知概率分布的情况下，贝叶斯分类器在理论上是错误率最小的分类器。但实际应用中，由于估计多个特征之间联合概率分布的难度非常大，因此贝叶斯分类器难以实施。贝叶斯分类器通常被作为研究分类器性能时的一种基准模型。

3.1.2朴素贝叶斯与参数估计
贝叶斯分类器的难点在于概率分布估计，特别是高维特征的联合概率分布，其估计难度非常大。一个d维特征的联合概率分布P(X1,X2,…,Xd)，可以使用贝叶斯公式分解成如下形式，
P(X1,X2,…,Xd)=P(X1|X2,…,Xd)P(X2,…,Xd)
=P(X1|X2,…,Xd)P(X2|X3,…,Xd)P(X3,…,Xd)
=P(X1|X2,…,Xd)P(X2|X3,…,Xd)…P(Xd-1|Xd)P(Xd)

假设所有特征之间相互独立，则联合概率分布可简化为
P(X1,X2,…,Xd)=P(X1)P(X2)…P(Xd)=∏di=1P(Xi)(35)

同理，如果假设给定类别条件下所有特征之间相互独立，则

P(X1,X2,…,Xd|Y)=P(X1|Y)P(X2|Y)…P(Xd|Y)=∏di=1P(Xi|Y)

(36)

这样，d维特征联合概率分布的估计问题就简化为d个一维特征概率分布的估计问题。这种简化具有非常大的应用价值，可以有效降低概率估计的难度。
所有特征之间相互独立，这是一个限制性很强的假设，基于这种假设所设计的贝叶斯分类器被称作朴素贝叶斯(naive Bayes)分类器。除了特征联合条件概率分布P(X1,X2,…,Xd|Y)的估计方法不同之外，朴素贝叶斯分类器与贝叶斯分类器在其他方面都是一样的。
在朴素贝叶斯分类器中，d维联合概率分布的估计问题被简化为一维特征概率分布的估计问题。下面对一维特征概率分布的估计问题做必要讲解，然后再给出一个关于乳腺癌诊断的分类器设计与编程实例。

1. 特征条件概率的估计
设计朴素贝叶斯分类器，最主要的工作就是通过样本数据获得(估计)分类所需的特征条件概率，即给定类别Y=y的条件下各项特征Xi的概率分布P(Xi|Y=y)。下面给出三种常用概率分布形式，以及它们的参数估计方法。

1) 01分布与二项分布(离散型)
给定类别Y=y，如果离散型特征X(随机变量)只有两种取值(可表示成0或1)，其概率分布为

P(X=1|Y=y)=p，P(X=0|Y=y)=1-p，0<p<1

则称随机变量X服从参数为p的01分布，又称伯努利(Bernoulli)分布。如果独立重复m次试验，每次试验均服从参数为p的01分布，用X表示m次试验中1发生的次数，则称随机变量X服从参数为(m,p)的二项(binomial)分布。
给定类别Y=y时的特征样本数据集{x1,x2,…,xm}，可以估计出参数p。数据集的样本容量为m，统计其中取值为1的样本点个数m1，则p=m1/m，即

P(X=1|Y=y)=m1m，P(X=0|Y=y)=1-m1m(37)

例31证明p=m1/m是
二项分布的极大似然估计。
证明：  给定类别
Y=y时的特征样本数据集{x1,x2,…,xm}，其中各样本点服从相同的01分布，联合概率服从二项分布。该数据集的似然函数为

L(p)=P(X=x1|Y=y)P(X=x2|Y=y)…P(X=xm|Y=y)
=∏m1i=1P(X=1|Y=y)∏m-m1i=1P(X=0|Y=y)
=pm1(1-p)m-m1

两边取对数，得对数似然函数

ln L(p)=m1ln p+(m-m1)ln(1-p)

求对数似然函数ln L(p)对参数p的导数，并令其等于零，即

ln L(p)p=m1p-m-m11-p=0

解方程得p=m1/m，这就是使似然函数最大的参数取值，即二项分布的极大似然估计。

2) 多项分布(离散型)
给定类别Y=y，如果离散型特征X(随机变量)有n种取值(可表示为1~n，n>2)，其概率分布为

P(X=i|Y=y)=pi，0<pi<1，∑ni=1pi=1

则称P(X|Y=y)服从多项(multinomial)分布。
给定类别Y=y时的特征样本数据集{x1,x2,…,xm}，可以估计出参数{p1,p2,…,pn}。数据集的样本容量为m，统计其中取值为i的样本点个数mi，则pi=mi/m，即

P(X=i|Y=y)=mim，i=1,2,…,n(38)

为防止样本欠采样造成概率pi为零的情况，通常采用拉普拉斯平滑(Laplace smoothing)技术对pi的计算公式进行修正。平滑后，pi=(mi+1)/(m+n)>0，即

P(X=i|Y=y)=mi+1m+n，i=1,2,…,n


3) 高斯分布(连续型)
给定类别Y=y，如果特征X(随机变量)取连续值，值域ΩX={x:x∈R}，且其概率密度函数为

p(x|Y=y)=12πσe-(x-μ)22σ2

则称P(X|Y=y)服从参数为(μ,σ2)的正态(normal)分布，又称高斯(Gaussian)分布。
给定类别Y=y时的特征样本数据集{x1,x2,…,xm}，可以估计出参数μ、σ2。使用极大似然估计可得

μ= x-=1m∑mi=1xi，σ2=1m∑mi=1(xi-x-)2(39)

例32证明式（39）中的μ、σ2是高斯分布的极大似然估计。
证明： 给定类别Y=y时的特征样本数据集{x1,x2,…,xm}，其似然函数为

L(μ,σ2)=p(x1|Y=y)p(x2|Y=y)…p(xm|Y=y)=∏mi=112πσe-(xi-μ)22σ2

两边取对数，得对数似然函数

ln L(μ,σ2)=-mln2π-mln σ-12σ2∑mi=1(xi-μ)2
=-mln2π-m2ln σ2-12σ2∑mi=1(xi-μ)2

求对数似然函数lnL(p)对参数μ和σ2的偏导数，并令其等于0，即

ln L(μ,σ2)μ=1σ2∑mi=1(xi-μ)=0
ln L(μ,σ2)σ2=-m2σ2+12σ4∑mi=1(xi-μ)2=0

解方程可得式（39），这就是使似然函数最大的参数取值，即高斯分布的极大似然估计。

2. 使用scikitlearn库提供的样本数据集练习编程
scikitlearn为机器学习提供了很多练习用的数据集，例如练习回归任务的boston houseprices dataset、diabetes dataset； 练习分类任务使用的iris dataset、digits dataset、breast cancer wisconsin dataset等。本章选用其中的乳腺癌数据集breast cancer wisconsin dataset来讲解朴素贝叶斯分类器的设计过程及编程实现。
breast cancer wisconsin dataset是一个乳腺癌诊断的数据集，其中包含569个病例，每个病例包含30项特征数据(均为连续型特征)和一项诊断结果(1表示恶性（malignant），0表示良性（benign）)。诊断乳腺癌就是根据各项临床特征(即检查指标)判定乳腺癌是恶性肿瘤还是良性肿瘤。这是一个分类问题，更准确地说是一个二分类问题。
图32给出了一个下载乳腺癌诊断数据集的示例代码，它将数据集及其说明文档分别保存到data目录下的breast_cancer.csv文件和breast_cancer.txt中。



图32下载乳腺癌诊断数据集的示例代码



3. 使用scikitlearn库中的朴素贝叶斯模型
scikitlearn库根据分类特征的概率分布形式，将朴素贝叶斯分类器模型封装成不同的类，常用的有三个： GaussianNB(高斯分布特征)、MultinomialNB(多项分布特征)、BernoulliNB(伯努利分布特征，即二项分布)，并将它们存放在sklearn.naive_bayes模块中。这些朴素贝叶斯类都实现了学习算法fit()、预测算法predict()和评价算法score()。下面通过乳腺癌诊断数据集来具体讲解朴素贝叶斯类的使用方法。为了进行本章的分类器编程实战，这里新建一个Jupyter记事本文件，后面将在该文件中正式编写程序代码。
乳腺癌诊断数据集的各项临床检查指标都是连续型特征，因此需要选用高斯分布的朴素贝叶斯类GaussianNB。使用GaussianNB类建立乳腺癌诊断模型(即分类模型)主要分为3步。
1) 加载数据集
从下载到本地data目录下的breast_cancer.csv文件中加载乳腺癌诊断数据集，得到一个DataFrame类的二维表格cancer，显示其形状(shape，即表格的行数和列数)。取出数据集中的特征(0~29列)，生成特征集X； 再取出诊断结果(第30列，列名为malignant)，生成目标集Y。图33给出了示例代码。



图33加载数据集的示例代码



2) 拆分训练集和测试集
使用sklearn.model_selection模块中的函数train_test_split()，将特征集、目标集再分别拆分成训练集和测试集，得到训练集的特征集X_train和目标集Y_train、测试集的特征集X_test和目标集Y_test，共4个子集。图34给出了示例代码。



图34拆分训练集和测试集的示例代码



3) 训练并测试模型
图35给出了使用GaussianNB类建立并训练乳腺癌诊断模型的示例代码。其中，诊断模型(即分类模型)是基于高斯分布的朴素贝叶斯分类器，训练模型使用的是训练集(X_train、Y_train)； 然后用训练好的模型对测试集X_test前两个病例样本进行分类预测，将预测结果predict与Y_test中的真实诊断结果malignant进行比对，1表示恶性，0表示良性； 最后使用函数score()计算模型在训练集(X_train、Y_train)和测试集(X_test、Y_test)上的平均正确率(mean accuracy)。



图35使用GaussianNB类建立并训练乳腺癌诊断模型的示例代码


从图35可以看出，使用GaussianNB类建立并训练乳腺癌诊断模型，其在训练集、测试上的诊断正确率分别为94%和97%左右。
3.1.3逻辑斯谛回归与牛顿法
贝叶斯分类器需要先估计特征概率分布P(X)、类别概率分布P(Yi)，以及各类的特征条件概率P(X|Yi)，然后使用贝叶斯公式计算出后验概率P(Yi|X)，最后再进行分类决策。能不能通过特征X直接估计出后验概率P(Yi|X)呢？对于二分类问题来说，答案是肯定的。给定样本数据集，可以使用逻辑斯谛回归方法直接估计后验概率P(Y1|X)、P(Y0|X)。注： P(Y1|X)、P(Y0|X)分别是P(Y=1|X)和P(Y=0|X)的简写。
在二分类问题中，类别Y的取值只有两个，ΩY={1,0}，其后验概率P(Y|X)服从01分布，即

P(Y1|X)=p，P(Y0|X)=1-p，0<p<1

P(Y1|X)+P(Y0|X)=1

将P(Y1|X)与P(Y0|X)之比称作01分布的几率(odds)，将几率的自然对数称作对数几率(logit，记作z)，其数学形式可表示为

几率=P(Y1|X)P(Y0|X)=p1-p(310)

对数几率z=lnP(Y1|X)P(Y0|X)=lnp1-p(311)

整理式（311）可得

p=ez1+ez=11+e-z(312)

式（312）的函数形式被称为逻辑斯谛函数，它是一种sigmoid函数(即S形函数)。式（311）、式（312）描述了01分布中对数几率z与概率p之间的函数关系。
针对二分类问题，给定样本特征X=x，可以使用逻辑斯谛回归方法预测后验概率分布P(Y|
X=x)的对数几率z，然后使用式（312）计算出概率p。逻辑斯谛回归有一个重要假设： 01分布的对数几率z与特征x之间存在线性关系，即

z=ωTx(313)

其中，ω是未知参数。这个假设来源于自然界的生物增长模型，具有一定的合理性(参见
2.5.2节)。将式（313）代入式（312），得

p=ez1+ez=eωTx1+eωTx(314)

由此可得后验概率P(Y1|X=x)、P(Y0|X=x)的回归模型，即

P(Y1|X=x)=p=eωTx1+eωTx，P(Y0|X=x)=1-p=11+eωTx(315)

有了式（315）的后验概率回归模型，再结合式（33）的贝叶斯决策，这样所设计出的分类器被称为逻辑斯谛回归(logistic regression)分类器，或对数几率回归(logit regression)分类器。式（315）的回归模型中，ω是未知参数，需通过样本训练集并使用极大似然估计进行训练，确定出最优参数ω*。

1. 构造似然函数
给定二分类的样本数据训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi是样本特征，yi是其对应的真实类别(0或1)，可以构造式（315）所示回归模型的似然函数，将使似然函数最大的参数取值ω*作为最优参数。
式（315）所示回归模型的似然函数可以定义为

L(ω)=∏mi=1P(Y=yi|xi； ω)

两边取自然对数，得到对数似然函数

ln L(ω)=ln∏mi=1P(Y=yi|xi； ω)=∑mi=1ln P(Y=yi|xi； ω)(316)

其中，后验概率P(Y=yi|xi； ω)按yi的取值可分为如下两种情况。
（1) 如果yi=1，则

P(Y=yi|xi； ω)=P(Y=1|xi； ω)=eωTxi1+eωTxi

lnP(Y=1|xi； ω)=lneωTxi1+eωTxi=ωTxi-ln(1+eωTxi)(317)

（2) 如果yi=0，则

P(Y=yi|xi； ω)=P(Y=0|xi； ω)=11+eωTxi

ln P(Y=0|xi； ω)=ln11+eωTxi=-ln(1+eωTxi)(318)

可以构造一个新函数，将式（317）、式（318）的两个对数概率函数合并成一个，即

ln P(Y=yi|xi； ω)=yiln P(Y=1|xi； ω)

+(1-yi)lnP(Y=0|xi； ω)(319)

其中，yi、1-yi必然一个是0，另一个是1，这相当于对等号右边两个对数概率项进行开关选择。
式（319）是第i个样本点的对数似然函数，其负数形式

-lnP(Y=yi|xi； ω)=-［yilnP(Y=1|xi； ω)+(1-yi)lnP(Y=0|xi； ω)］

被称为第i个样本点的交叉熵(cross entropy)。整个训练集Dtrain上的交叉熵为各样本点交叉熵之和，即

-∑mi=1lnP(Y=yi|xi； ω)

最大化似然函数
等价于最小化交叉熵。交叉熵的作用相当于
训练逻辑斯谛回归模型时的
损失函数。
将式（317）、式（318）代入式（319），则

lnP(Y=yi|xi； ω)=yi［ωTxi-ln(1+eωTxi)］+(1-yi)［-ln(1+eωTxi)］

整理可得

ln P(Y=yi|xi； ω)=yiωTxi-ln(1+eωTxi)(320)

将式（320）代入式（316）的对数似然函数，则

ln L(ω)=∑mi=1［yiωTxi-ln(1+eωTxi)］(321)

最大化对数似然函数lnL(ω)，等价于最小化其负值(即交叉熵)，记作L1(ω)，即


L1(ω)=-ln L(ω)=∑mi=1［-yiωTxi+ln(1+eωTxi)］(322)

式（322）是关于ω的连续且高阶可导凸函数，可以使用梯度下降法、牛顿法等迭代算法求解出最优参数ω*，即

ω*= argminω L1(ω)(323)

如果使用梯度下降法，其参数迭代公式为

ωk=ωk-1-a·L1(ωk-1)

如果使用牛顿法，则参数迭代公式为


ωk=ωk-1-H-1(ωk-1)×L1(ωk-1)(324)


其中，

L1(ω)=L1ω1
L1ω2
︙
L1ωd，H(ω)=2L1ω1ω12L1ω1ω2…2L1ω1ωd
2L1ω2ω12L1ω2ω2…2L1ω2ωd
︙︙︙
2L1ωdω12L1ωdω2…2L1ωdωd


2. 牛顿法
梯度下降法、牛顿法都属于数值迭代算法。梯度下降法利用一阶导数(或一阶偏导数)确定下一个迭代点的搜索方向，牛顿法在此基础上进一步利用二阶导数(或二阶偏导数)确定出下一个迭代点的大致位置，因此牛顿法能够提高迭代算法的收敛速度。
先讨论一元函数的无约束最小化问题： x*=minx∈Rf(x)。假设从xk-1处出发，该如何搜索下一个迭代点xk，使得f(xk)≤f(xk-1)呢？一元函数f(x)在xk-1处的二阶泰勒展开式为

f(x)=f(xk-1)+f′(xk-1)(x-xk-1)+12f″(xk-1)(x-xk-1)2

+o((x-xk-1)2)

令

φ(x)=f(xk-1)+f′(xk-1)(x-xk-1)
+12f″(xk-1)(x-xk-1)2


≈f(x)

则函数φ(x)是f(x)的近似函数，且在xk-1处的一阶导数、二阶导数与f(x)相同，可以将φ(x)的极值点作为最小化f(x)的下一个迭代点。求φ(x)的一阶导数，并令其等于0，即

φ′(x)=f′(xk-1)+f″(xk-1)(x-xk-1)=0

解得

x=xk-1-f′(xk-1)f″(xk-1)

将φ(x)的极值点x作为下一个迭代点xk，即

xk=xk-1-f′(xk-1)f″(xk-1)(325)

式（325）就是牛顿法的迭代公式。
使用牛顿法求解一元函数f(x)无约束最小化问题的算法过程如下： 首先任意选取一个参数初值x0，然后按照式（325）的迭代公式，不断更新迭代，得到新的参数x1,x2,…,xk,…，使f(x)的函数值逐步下降，即f(xk)≤f(xk-1)； 重复迭代过程，直到相邻两次迭代计算出的函数值基本没有变化，则f(x)收敛至最小值，迭代结束，将当前参数xk作为最优参数x*。
将一元函数的无约束最小化问题推广到多元函数，例如d元函数，即

x*= minx∈Rdf(x)

其中，x=(x1,x2,…,xd)T是一个d维向量。从一元函数推广到d元函数，需将一阶、二阶导数分别替换成梯度向量(一阶偏导向量)f(x)和黑塞矩阵(二阶偏导矩阵)H(x)。对于d元函数，牛顿法迭代公式的推导过程如下。

f(x)=f(xk-1)+f(xk-1)(x-xk-1)+12(x-xk-1)TH(xk-1)(x-xk-1)+

o((x-xk-1)T
（x-xk-1）)

其中，

f(x)=fx1
fx2
︙
fxd，H(x)=2fx1x12fx1x2…2fx1xd
2fx2x12fx2x2…2fx2xd
︙︙︙
2fxdx12fxdx2…2fxdxd

令

φ(x)=f(xk-1)+f(xk-1)(x-xk-1)+12(x-xk-1)TH(xk-1)(x-xk-1)

≈f(x)

则函数φ(x)是f(x)的近似函数，可以将φ(x)的极值点作为最小化f(x)的下一个迭代点。求φ(x)的一阶偏导数，并令其等于零，即

φ(x)=f(xk-1)+H(xk-1)(x-xk-1)=0

如果H(x)可逆，解方程得

x=xk-1-H-1(xk-1)f(xk-1)

将φ(x)的极值点x作为下一个迭代点xk，即

xk=xk-1-H-1(xk-1)f(xk-1)(326)

式（326）就是多元函数时的牛顿法迭代公式。

3. 使用scikitlearn库中的逻辑斯谛回归分类器模型
scikitlearn库将逻辑斯谛回归分类器模型封装成一个类(类名为LogisticRegression)，并将其存放在sklearn.linear_model模块中。LogisticRegression类实现了逻辑斯谛回归分类器模型的学习算法fit()、预测算法predict()和评价算法score()。
应用逻辑斯谛回归分类器，需要对样本的特征数据进行标准化(zscore或MinMax)，然后再将特征集、目标集进一步拆分成训练集和测试集。对乳腺癌诊断问题，图36给出了特征标准化和数据集拆分的示例代码。示例代码先对3.1.2节得到的特征集X进行标准化，得到新的特征集X1，然后将X1和目标集Y按照8:2的比例拆分成训练集和测试集。拆分得到训练集的特征集X1_train和目标集Y_train、测试集的特征集X1_test和目标集Y_test，共4个子集。



图36特征标准化和数据集拆分的示例代码



图37给出了使用LogisticRegression类建立并训练乳腺癌诊断模型的示例代码。其中，诊断模型(即分类模型)采用的是逻辑斯谛回归分类器，训练模型使用的是训练集(X1_train、Y_train)； 然后用训练好的模型对测试集X1_test前两个病例样本进行分类预测，将预测结果predict与Y_test中的真实诊断结果malignant进行比对，1表示恶性，0表示良性； 最后使用函数score()计算模型在训练集(X1_train、Y_train)和测试集(X1_test、Y_test)上的平均正确率。



图37使用LogisticRegression类建立并训练乳腺癌诊断模型的示例代码


4. 将逻辑斯谛回归推广至多分类
可以将逻辑斯蒂回归由二分类推广至多分类(假设为N分类)，这时类别后验概率由二分类的01分布推广至多项分布。相应地，后验概率的函数形式也由逻辑斯谛函数推广至归一化指数函数(或称作softmax函数)，其数学形式为

zk=ωTkx，k=1,2,…,N

ztotal=∑Nk=1ezk=∑Nk=1eωTkx

P(Yk|x)=softmax(zk)=ezkztotal，k=1,2,…,N

其中，x为样本特征，ωk为第k类的回归系数； P(Yk|x)为第k类的后验概率，0<P(Yk|x)<1，且∑Nk=1P(Yk|x)=1。
给定一个多分类的样本特征x，使用逻辑斯谛回归方法分别估计出各类的后验概率
P(Yk|x)，k=1,2,…,N，然后将使P(Yk|x)最大的Yk作为分类结果。
二分类时，第i个样本点的交叉熵(记作H)为

H=-lnP(Y=yi|xi； ω)
=-［yilnP(Y=1|xi； ω)+(1-yi)lnP(Y=0|xi； ω)］

而多分类时，通常会对样本类别进行N位onehot编码，例如类别1的onehot编码为10…0，类别2的onehot编码为01…0，…，类别N的onehot编码为00…1。这时第i个样本点类别yi的onehot编码可记为y1iy2i…yNi，其交叉熵可写成

H=-lnP(Y=yi|xi； ω)=-∑Nk=1ykilnP(yi=k|xi； ω)，yki∈{0,1}

基于逻辑斯谛回归进行分类决策时，交叉熵的作用相当于
训练模型时的
损失函数。

5. 进一步理解交叉熵
设p(y)、q(y)是随机变量Y上的两个概率分布，则q(y)相对于p(y)的交叉熵被定义为



H(q,p)=-∑y∈ΩYq(y)lnp(y)，离散型
H(q,p)=-∫ΩYq(y)lnp(y)dy，连续型

其中，ΩY为随机变量Y的值域。交叉熵描述了两种不同概率分布之间的差异程度，因此常被分类模型用作度量真实概率分布与预测概率分布之间误差的损失函数。注： 交叉熵不是对称的，即H(q,p)≠H(p,q)。
例如，使用逻辑斯谛回归方法进行二分类时，给定样本xi，可以估计出类别y∈{0,1}的预测概率分布p(y)，可记作p1、p0。另外，可以将样本xi的真实类别yi也表示成概率分布的形式并记作q1、q0。例如，yi=1时的概率分布q(y)为： q1=1，q0=0； yi=0时的概率分布q(y)则为： q1=0，q0=1。这时度量
预测概率分布p(y)与真实概率分布q(y)的差异，可以使用交叉熵的形式，即

H(q,p)=-∑y∈{0,1}q(y)lnp(y)=-(q1lnp1+q0lnp0)

对比式（319）可以看出，交叉熵与对数似然函数互为相反数。使用逻辑斯谛回归方法进行分类时，最大化对数似然函数就等价于最小化交叉熵损失函数。

3.2非贝叶斯分类器
计算机科学是一门新兴学科，它善于从其他学科汲取营养，善于运用算法来解决问题。针对分类问题，本节介绍三种借助算法思想所设计的非贝叶斯分类器模型，它们分别是k近邻方法、线性判别分析和决策树。这三种方法都是直接基于特征(而不是特征的概率分布)来设计分类算法，建立判别函数，从而解决分类问题。

3.2.1k近邻分类器与距离度量
k近邻(kNearest Neighbor，KNN)分类器是一种基于实例(instancebased)的分类器。这种分类器不建立任何模型，只是将训练集作为样本实例保存起来。假设给定训练集

Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}

其中,xi是样本特征，yi∈{c1,c2,…,cn}是其对应的实际类别，直接将训练集Dtrain以某种数据结构(data structure)保存起来。
给定新样本x，按照某种距离度量(distance metric)查找训练集中k个(例如1个、3个或5个等)距离最近(称作最近邻，nearest neighbor)的样本实例，然后统计这k个样本实例的类别； 最后的分类决策规则是，将出现次数最多的类别判定为新样本x的类别，这种分类决策规则被称为简单多数表决(simple majority vote)规则。k近邻分类器直接基于训练集实例进行分类，没有显式的学习过程，也不需要学习算法。

1. 距离度量
如何对样本点特征之间的相似度(距离)进行度量，这是k近邻分类器最核心的内容。度量两个d维特征xi={xi1,xi2,…,xid}和xj={xj1,xj2,…,xjd}之间的相似度，通常使用欧氏(Euclidean)距离或曼哈顿(Manhattan)距离。闵可夫斯基(Minkowski)距离则给出了更一般形式的定义。将闵可夫斯基距离记作Lp，其定义形式为

Lp(xi,xj)=∑dl=1|xil-xjl|p1p，p≥1(327)

如果p=1，则闵可夫斯基距离就是曼哈顿距离，记作L1(xi,xj)或‖xi-xj‖1。

L1(xi,xj)=∑dl=1|xil-xjl|

如果p=2，则闵可夫斯基距离就是欧氏距离，记作L2(xi,xj)或‖xi-xj‖2。

L2(xi,xj)=
∑dl=1
|xil-xjl|2=∑dl=1(xil-xjl)2

如果p=+∞，则闵可夫斯基距离就是切比雪夫(Chebyshev)距离，记作L∞。

L∞(xi,xj)= maxl=1,2,…,d|xil-xjl|


2. 数据结构与查找算法
给定新样本x，k近邻分类器需要逐个计算与训练集里各实例xi的距离。如果使用顺序表(例如数组或链表)存储训练集Dtrain，则查找算法的平均复杂度为O(N)。
可以改用kd树(kdimensional tree)来存储训练集Dtrain，这样能将查找x最近邻算法的平均复杂度降到O(logN)，有效提高算法的查找速度。kd树由“数据结构”中的二叉搜索树(Binary Search Tree，BST)演变而来，常用于高维数据的存储与查找。如果想详细了解kd树及其查找算法，读者可进一步查阅相关资料。

3. 简单多数表决规则
给定新样本x，使用查找算法查找出训练集Dtrain中与x距离最近的k个实例。假设这k个实例为(x1,y1)，(x2,y2)，…，(xk,yk)，其中实例类别yi∈{c1,c2,…,cn}。统计n个类别在k个实例中出现的次数，将出现次数最多的类别判定为新样本x的类别。

4. 使用scikitlearn库中的k近邻分类器模型
scikitlearn库将k近邻分类器模型封装成一个类(类名为KNeighborsClassifier)，并将其存放在sklearn.neighbors模块中。KNeighborsClassifier类实现了k近邻分类器模型的学习算法
fit()、预测算法predict()和评价算法score()。
图38给出了使用KNeighborsClassifier类建立并训练乳腺癌诊断模型的示例代码。其中，诊断模型(即分类模型)采用的是k近邻分类器； 数据集使用的是3.1.3节标准化后的乳腺癌诊断数据集，其中的训练集(X1_train、Y_train)被用
作样本实例； 然后用训练好的模型对测试集X1_test前两个病例样本进行分类预测，将预测结果predict与Y_test中的真实诊断结果malignant进行比对，1表示恶性，0表示良性； 最后使用函数score()计算模型在训练集(X1_train、Y_train)和测试集(X1_test、Y_test)上的平均正确率。





图38使用KNeighborsClassifier类建立并训练乳腺癌诊断模型的示例代码



5. 超参数k的选择
k近邻分类器模型中的k是一个超参数，其取值对分类结果有很大影响。图39给出一个例子，对于新样本x，不同k值会得到不同的分类结果。当k=1时，k近邻分类器也被称作最近邻分类器。


图39不同k值会得到不同的分类结果




对于乳腺癌诊断模型所采用的k近邻分类器，图310、图311分别给出对比不同k值(1~9)时模型分类性能(其中采用了5折交叉验证，即cv=5)的示例代码和折线图。图311的折线图可以为超参数k值的选择提供参考。


图310对比不同k值(1~9)时模型分类性能的示例代码




图311对比不同k值(1~9)时模型分类性能的折线图



3.2.2线性判别分析与特征空间
贝叶斯分类器需要先估计特征概率分布P(X)、类别概率分布P(Yk)，以及各类的特征条件概率P(X|Yk)，然后使用贝叶斯公式计算出后验概率P(Yk|X)，最后再进行分类决策。估计概率分布需要有足够多的样本数据。如果特征X包含的属性个数很多，即高维特征，则估计特征概率分布P(X)、各类特征条件概率P(X|Yk)所需样本集的容量要求很大，否则就会因样本稀疏造成概率估计的偏差。
对于二分类问题，线性判别分析(Linear Discriminant Analysis，LDA)方法的思路是： 给定训练集，设法将其中的高维特征压缩到一维，然后基于一维特征来设计分类器，这样就能降低对样本集容量的要求。

1. 特征空间与向量投影
给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi是样本特征，yi∈{c1,c2,…,cn}是其对应的实际类别，i=1,2,…,m。可以将每个样本点的特征看作向量空间里的一个向量，这种向量空间被称为特征空间(feature space)，其中的向量被称为特征向量(feature vector，这个特征向量与矩阵的特征向量不是一回事)。图312给出一个二维特征空间的示意图。


图312将每个样本点的特征看作
特征空间中的一个向量


在图312所示的特征空间中，每一项特征属性都是一个维度(dimension)，d项特征属性就构成一个d维空间。样本点x在特征空间中的坐标(x1,x2,…,xd)就是各属性的取值。例如，假设特征1表示苹果的“口感”，特征2表示“果重”，苹果样本x的坐标(甜，190)就表示x的口感是“甜”，果重为190g。
样本点x的坐标实际上是向量x在各基向量(坐标轴)上的投影。例如图312中，样本点x的坐标(x1,x2)就是其在基向量e1、e2上的投影x1、x2。可以将样本点x投影到其他向量(例如ω)上。假设向量ω的坐标是(ω1,ω2,…,ωd)，向量x在ω上的投影可分为标量投影(scalar projection，记作z)与向量投影(vector projection，记作p)两种形式(参见图312)，其计算公式分别为

z=ωTx‖ω‖(328)

p=zω‖ω‖(329)

其中，向量x=(x1,x2,…,xd)T，ω=(ω1,ω2,…,ωd)T； z是标量，为x在ω上的标量投影； p是向量，为x在ω上的向量投影； ωTx是向量ω与向量x的内积(或称点积)，ωTx=ω1x1+ω2x2+…+ωdxd； ‖ω‖是向量ω的模(即长度)，‖ω‖=ω21+ω22+…+ω2d=ωTω。
可以证明，ωTx=‖ω‖‖x‖cosθ(θ为ω与x之间的夹角)，由此可推导出式(328)。如果ω为单位向量，即‖ω‖=1，则式(328)可简化为

z=ωTx=ω1x1+ω2x2+…+ωdxd(330)

式(328)、式(330)的标量投影，实际上是通过线性组合方法将d维向量x=(x1,x2,…,xd)T压缩成ω方向上的一维标量z，线性组合中的各项系数分别对应向量ω的各个分量。

2. 选择投影方向


图313二维特征空间的投影示意图

对于二分类问题，线性判别分析方法希望在选择投影方向ω时，能够让样本特征投影点“类内方差最小，类间方差最大”。换句话说，投影后同类样本点越聚集越好，不同类的样本点越远离越好。图313给出一个二维特征空间的投影示意图，其中的●、▲分别表示类0和类1的样本点，�瘙
經、ω分别表示两个不同的投影方向，μ0、μ1分别表示投影后类0和类1样本投影点的均值。可以看出，ω方向的投影效果比�瘙
經方向要好，因为类0和类1在�瘙
經方向上的投影点混杂在一起，很难分类。通过投影对原始特征进行变换，这是线性判别分析方法最核心的内容。

下面用数学语言来描述选择最优投影方向ω的过程，整个过程分4步完成。给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi=(xi1,xi2,…,xid)T是d维样本特征，yi∈{0,1}是其对应的实际类别。假设训练集Dtrain中0类样本有m0个，1类样本有m1个，将数据集按类别拆分成子集Dk={(x1,k),(x2,k),…,(xmk,k)}，k=0,1。

1) 定义投影前d维特征空间的统计量
分别定义各类特征的均值μk和离散度(类似于协方差)矩阵Sk，k=0,1，

μk=1mk∑mki=1xi(331)

Sk=∑mki=1(xi-μk)(xi-μk)T(332)

其中，xi∈Dk。式(331)、式(332)的展开式为

μk=μk1
μk2
︙
μkd，μkl=1mk∑mki=1xil，l=1,2,…,d

Sk=σ11σ12…σ1d
σ21σ22…σ2d
︙︙︙
σd1σd2…σdd，σjl=∑mki=1(xij-μkj)(xil-μkl)，j,l=1,2,…,d

再定义d维特征空间的类内离散度矩阵(withinclass scatter matrix)Sw和d维特征空间的类间离散度矩阵(betweenclass scatter matrix)Sb为

Sw=P(Y=0)S0+P(Y=1)S1=m0mS0+m1mS1(333)


Sb=(μ0-μ1)(μ0-μ1)T(334)

式(334)的展开式为

(μ0-μ1)=μ01-μ11
μ02-μ12
︙
μ0d-μ1d

Sb=b11b12…b1d
b21b22…b2d
︙︙︙
bd1bd2…bdd，bjl=(μ0j-μ1j)(μ0l-μ1l)，j,l=1,2,…,d


式(333)中的Sw、式(334)中的Sb都是对称半正定矩阵，且Sw在m>d时一般是可逆的。

2) 定义投影后一维投影空间的统计量
在特征向量x=(x1,x2,…,xd)T向ω=(ω1,ω2,…,ωd)T投影后的一维空间，定义各类特征投影点z的均值μ~k和离散度(类似于方差)S～k，k=0,1，

μ~k=1mk∑mki=1zi=1mk∑mki=1ωTxi=ωTμk(335)

S～k=∑mki=1(zi-μ~k)2=∑mki=1(ωTxi-ωTμk)(ωTxi-ωTμk)T=ωTSkω(336)

式(335)、式(336)的展开式为

μ~k=ωTμk=(ω1,ω2,…,ωd)μk1
μk2
︙
μkd

S～k=ωTSkω=(ω1,ω2,…,ωd)σ11σ12…σ1d
σ21σ22…σ2d
︙︙︙
σd1σd2…σddω1
ω2
︙
ωd

再定义一维投影空间的类内方差(withinclass variance)S～w和一维投影空间的类间方差(betweenclass variance)S～b为


S～w=P(Y=0)S～0+P(Y=1)S～1=m0mS～0+m1mS～1

=m0mωTS0ω+m1mωTS1ω=ωTSwω(337)



S～b=(μ~0-μ~1)2=(ωTμ0-ωTμ1)2=(ωTμ0-ωTμ1)(ωTμ0-ωTμ1)T

=ωT(μ0-μ1)(μ0-μ1)Tω=ωTSbω(338)

式(337)中的S～w、式(338)中的S～b都是二次型的形式，且S～w≥0，S～b≥0。

3) 构造准则函数
对于二分类问题，线性判别分析方法希望在选择投影方向ω时，能够让样本特征投影点“类内方差最小，类间方差最大”。这句话的含义就是希望让一维投影空间的类内方差S～w最小，类间方差S～b最大。可以构造如下准则函数J(ω)：

J(ω)=S～bS～w=ωTSbωωTSwω(339)


然后选择使准则函数J(ω)最大的ω作为最优投影方向。这样，选择最优投影方向问题被转换为最大化准则函数J(ω)的问题。注： 式（339）的准则函数是1936年由R.A. Fisher提出的，因此被称作Fisher准则函数。

4) 最大化准则函数
式（339）是ω的两个二次型之比，因此对任意常数c，J(cω)=J(ω)，即准则函数J(ω)的最优参数ω不唯一。不失一般性，可以令分母ωTSwω=1，以此作为对ω的约束条件，然后最大化分子ωTSbω。这样式（339）的优化问题等价于

maxωωTSbω(340)

s.t. ωTSwω=1

使用拉格朗日乘子法，定义拉格朗日函数为

L(ω,λ)=ωTSbω-λ(ωTSwω-1)

其中，λ为拉格朗日乘子。对ω求偏导数，并令其等于零，即

L(ω,λ)ω=2Sbω-2λSwω=0

其中，xTAxx=2Ax，解得

S-1wSbω=λω(341)

将式（334）的Sb代入Sbω，则

Sbω=(μ0-μ1)(μ0-μ1)Tω

式中的(μ0-μ1)Tω是两个向量的点积，其结果为标量(记作R)，这说明Sbω是(μ0-μ1)方向上的一个向量。由式（341）可得

λω=S-1w(Sbω)=S-1w(μ0-μ1)((μ0-μ1)Tω)=S-1w(μ0-μ1)R

整理可得

ω=RλS-1w(μ0-μ1)

因为线性判别分析方法只希望找出最优的投影方向，即找出投影方向上的任意一个向量ω均可，所以可以忽略比例因子Rλ，最终求得最优投影向量ω*为

ω*=S-1w(μ0-μ1)(342)

式（342）中的Sw、μ0、μ1是已知的，可通过训练集样本数据直接计算出来。在求矩阵Sw的逆矩阵时，可以使用奇异值分解方法
来简化求解
，即先对Sw做奇异值分解，则

Sw=UΣVT

其中U、V是正交矩阵(即U-1=UT，V-1=VT)，Σ是对角阵(其对角元素是Sw的奇异值)； 然后求出Sw的逆矩阵，则

S-1w=VΣ-1UT


3. 线性判别分析分类器
对于二分类问题，给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi=(xi1,xi2,…,xid)是d维样本特征，yi∈{0,1}是其对应的实际类别。线性判别分析方法使用式（331）~式（333）分别计算出Sw、μ0和μ1，再用式（342）即可求出最优投影向量ω*。
在确定了最优投影向量ω*之后，使用式（328）的标量投影将训练集Dtrain的d维特征向量xi转换为一维特征标量zi，即

zi=(ω*)Txi‖ω*‖，i=1,2,…,m

这样就能得到一维特征的训练集D′train={(z1,y1),(z2,y2),…,(zm,ym)}。
对于二分类问题，可以基于一维特征训练集D′train直接设定阈值T，例如T=12(μ~0+μ~1)，然后将分类决策规则定为： 给定新样本x，如果

z=(ω*)Tx‖ω*‖T

则将新样本x的类别判定为0或1，这就是一个最简单的线性判别分析分类器。也可以基于一维特征训练集D′train设计其他形式的分类器，例如贝叶斯分类器或k近邻分类器。设计分类器，是由于一维特征模型比高维特征模型要简单得多。
目前，解决分类问题已经很少使用线性判别分析方法了，线性判别分析被更多地用于特征降维(详见3.4.3节)。

4. 使用scikitlearn库中的线性判别分析模型
scikitlearn库将线性判别分析模型封装成一个类(类名为LinearDiscriminantAnalysis)，并将其存放在sklearn.discriminant_analysis模块中。LinearDiscriminantAnalysis类实现了线性判别分析分类器模型的学习算法fit()、预测算法predict()和评价算法score()。LinearDiscriminantAnalysis类既可以用于分类，也可以用于特征降维。
图314给出了使用LinearDiscriminantAnalysis类建立并训练乳腺癌诊断模型的示例代码。其中，诊断模型(即分类模型)采用的是线性判别分析分类器； 数据集使用的是3.1.3节标准化后的乳腺癌诊断数据集，其中的训练集(X1_train、Y_train)被用于训练模型； 然后
用训练好的模型对测试集X1_test前两个病例样本进行分类预测，将预测结果predict与Y_test里的真实诊断结果malignant进行

图314使用LinearDiscriminantAnalysis类建立并训练乳腺癌诊断模型的示例代码
比对，1表示恶性，0表示良性； 最后使用函数score计算模型在训练集(X1_train、Y_train)和测试集(X1_test、Y_test)上的平均正确率。


3.2.3决策树
如何区分流感与普通感冒？一般来说，普通感冒的症状较轻，多数患者仅出现咳嗽、喉咙痛、流鼻涕等上呼吸道症状，但发高烧的人却不多； 而流感除上呼吸道症状以外，同时还会伴随高烧、头痛、明显肌肉酸痛等全身症状。
区分流感与普通感冒可以使用不同的特征项，其中的某些特征项对于区分流感与普通感冒比较有效(例如是否高烧或全身酸痛等)，某些特征项的区分效果不明显(例如咳嗽、流鼻涕等)。

1. 决策树分类模型
决策树(decision tree)分类模型是一种按照特征有效性，先主要特征，后次要特征，逐步递进，最终完成分类决策的模型。决策树模型的分类决策过程分多步完成，每步选用一个特征项，生成若干个分支，将其绘制成图形非常像一棵倒立的树，故被称作“决策树”。图315给出一个对苹果进行分类的决策树示意图，它根据口感、外形和底色三个特征项来区分苹果是红富士还是国光。



图315一个苹果分类的决策树示意图


一棵决策树包含一个根结点、若干内部结点和若干叶子结点。根结点和每个内部结点都分别代表一步决策(例如图315中的方形结点1~5)，决策内容是根据某项特征生成若干分支，其中根结点(图315中的方形结点1)是决策的起点； 每个叶子结点代表决策的一个结论，即分类结果(例如图315中的椭圆形结点①~⑧)。
给定一个样本苹果，假设其特征为(酸甜，圆，黄绿)，根据图315的决策树分类模型，分类决策过程从根结点1开始，根据“口感=酸甜”这项特征做出第一步决策，进入内部结点3； 再根据“外形=圆”这项特征做出第二步决策，进入叶子结点⑤； 进入叶子结点表示决策已得出结论，叶子结点⑤的结论是： 样本苹果的品种为“红富士”。从根结点到叶子结点的路径对应决策过程的步骤序列，步骤的每一步可被描述成一个ifthen规则，例如： 

if (口感 = 酸甜)..................... 第一步

then

if (外形 = 圆).................. 第二步

then

品种 = 红富士 ............ 结论

if (外形 = 扁圆)

then

...

if (口感 = 甜)........................ 第一步

then

...

整个决策树就是一个ifthen规则集合，所描述的是根据历史观测提炼出来的某种一般性知识。基于ifthen规则进行分类决策，非常类似于人们基于知识的演绎推理(deductive reasoning)，即从一般性知识推及某个特定的个体(从一般推及个别)。但这些ifthen规则是怎么来的呢？它们是通过对样本数据进行归纳推理(inductive reasoning，从个别推及一般)得来的。决策树的归纳推理过程就是基于训练集和学习算法来习得知识、建立决策树模型的过程。

2. 决策树学习算法
给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi=(xi1,xi2,…,xid)是d维样本特征，yi∈{c1,c2,…,cn}是其对应的类别，i=1,2,…,m。决策树学习算法就是要通过训练集来建立一个决策树分类模型。
决策树的学习过程从建立根结点开始，选择某项特征并根据其取值将训练集划分成不同子集，每个取值生成一个子集，然后为每个子集生成一个内部结点； 剔除已使用过的特征项，再对所有子集重复“选择特征划分子集”的过程，直到不可划分为止； 将不可划分子集的结点设为叶子结点，并将其标记为某个类别。可以看出，决策树的学习过程是一个递归过程。
下面就以3.1.1节表31的10个苹果样本数据为训练集，具体讲解决策树的学习过程。苹果样本数据有4项特征，X=(底色，外形，口感，果重)； 类别有两个，即红富士和国光，它属于二分类问题。
首先建立根结点(记作1号结点)，其对应的初始训练集包含10个样本数据(记作D1)，对样本数据按顺序进行编号，D1={1,2,…,10}。对1号结点进行“选择特征划分子集”过程。假设选用特征“底色”来划分子集(参见表38)，该项特征有3个不同取值，分别为黄、黄绿和绿。


表38红富士和国光苹果样本(10个)




编号底色外形口感果重/g品种
1黄圆甜190红富士
2黄绿扁圆酸甜260红富士
3绿扁圆酸甜150国光
4黄绿圆甜200红富士
5绿扁圆酸甜210国光
6黄绿扁圆酸甜170国光
7黄圆酸甜200红富士
8黄绿扁圆酸甜230红富士
9绿扁圆甜180国光
10黄绿扁圆酸甜240红富士


按特征“底色”的取值，对1号结点数据集D1进行划分，可划分出3个子集： 

“底色=黄”的子集D2={1,7}； 
“底色=黄绿”的子集D3={2,4,6,8,10}； 
“底色=绿”的子集D4={3,5,9}。
为每个子集建立一个内部结点，分别记作2号结点、3号结点、4号结点，此时所建立的决策树形状如图316（a）所示。




图316选择特征与划分子集的过程


如果改用特征“口感”来划分子集，该项特征有两个不同取值(甜、酸甜)，按“口感”的取值对1号结点数据集D1进行划分，可划分出2个子集： 
“口感=甜”的子集D2={1,4,9}； 
“口感=酸甜”的子集D3={2,3,5，6，7，8,10}。
为每个子集建立一个内部结点，分别记作2号结点、3号结点，此时所建立的决策树形状如图316（b）所示。
可以看出，选用不同特征项会生成不同的决策树。决策树模型是按特征有效性(先主后次)分步建立决策树的。特征有效性指的是特征对分类是否有效。该如何度量特征有效性呢？
表38包含10个苹果样本数据，它是训练决策树模型的初始集合D1，其中既包含红富士苹果，也包含国光苹果。决策树模型依据某项特征将D1划分成子集，希望每个子集尽可能属于同一类别，也就是将D1划分成纯度(purity)较高的子集。机器学习借用信息论中的信息熵或统计学中的基尼指数来度量数据集的纯度，然后根据所划分子集的纯度来选择特征项。所划分子集的纯度越高，则特征项越有效。如何选择特征项、如何度量数据集的纯度，这是决策树分类模型最核心的内容。

3. 随机变量的信息熵与基尼指数
将数据集D中样本的类别Y看作一个离散型随机变量，其值域Ω={c1,c2,…,cn}，共n个类别； 再假设D中样本类别的概率分布为P(Y=ck)=pk，∑nk=1pk=1，则
（1） 数据集D的信息熵(information entropy)被定义为

H(D)=-∑nk=1pklbpk(343)

其中，0≤H(D)≤lbn。注： 计算信息熵时若pk=0，则约定0×lb0=0。
(2) 数据集D的基尼指数(Gini index)被定义为

Gini(D)=∑nk=1∑j≠kpkpj=∑nk=1pk(1-pk)=1-∑nk=1p2k(344)

其中，0≤Gini(D)≤n-1n。注： 基尼指数可理解为从数据集D中随机抽取两个样本点，其类别不一致的概率(它反映了数据集的混乱程度)，或数据集D中样本点被错分
概率的数学期望。
例如表38所示的初始数据集D1，其中有两个苹果类别{红富士，国光}，属于01分布。由样本数据可以估计出苹果类别Y1的概率分布为

P(Y1=红富士)=610=0.6，P(Y1=国光)=410=0.4

分别计算D1的信息熵和基尼指数，有

H(D1)=-(0.6×lb0.6+0.4×lb0.4)=0.97095
Gini(D1)=1-(0.62+0.42)=0.48

假设将数据集D1划分成子集D2、D3，D2只包含红富士苹果，D3只包含国光苹果，即

P(Y2=红富士)=1，P(Y2=国光)=0

P(Y3=红富士)=0，P(Y3=国光)=1

则D2、D3都属于纯度最高的数据集，分别计算它们的信息熵和基尼指数，计算结果都将为零。

H(D2)=-(1×lb1+0×lb0)=0，Gini(D2)=1-(12+02)=0

H(D3)=-(0×lb0+1×lb1)=0，Gini(D3)=1-(02+12)=0

可以看出，数据集的纯度越高，则信息熵和基尼指数越小； 纯度越低，则信息熵和基尼指数越大。如果数据集只包含一个类别，则纯度最高，其信息熵和基尼指数最小(都为0)； 如果数据集包含全部类别(假设为n)且服从均匀分布，则纯度最低，其信息熵和基尼指数最大，信息熵最大值为lbn，基尼指数最大值为n-1n。借用信息熵或基尼指数，可以度量数据集的纯度。

4. 特征选择准则
给定数据集D={(x1,y1),(x2,y2),…,(xm,ym)}，其中包含m个样本数据。假设
 数据集D的样本特征为d维，记作X={X1,X2,…,Xd}，其中Xi表示第i项特征； 
 所有特征项都是离散型的，第i项特征Xi有Vi个可能的取值。

则按第i项特征Xi的取值，可以将数据集D划分成Vi个子集{D1,D2,…,DVi}。将每个子集包含的样本数据个数记作m1,m2,…,mVi，m1+m2+…+mVi=m。将数据集D及其子集{D1,D2,…,DVi}中样本的类别看作离散型随机变量，它们具有共有的值域Ω={c1,c2,…,cn}，共n个类别。特征选择就是根据所划分子集的纯度来选择特征项，子集纯度越高，则该项特征越有效。
决策树学习算法的关键是如何定义纯度的度量形式，即特征选择准则。目前，常用的决策树学习算法有ID3、C4.5和CART，它们分别提出了三种不同形式的特征选择准则。

1) ID3(信息增益)
假设按第i项特征Xi将数据集D划分成Vi个子集{D1,D2,…,DVi}，ID3算法首先按式(343)计算数据集D及其各子集D1,D2,…,DVi的信息熵，然后定义特征Xi对数据集D进行划分所获得的信息增益(information gain)为

Gain(D,Xi)=H(D)-∑Vik=1mkmH(Dk)，i=1,2,…,d(345)

其中，等式右边的第二项可看作子集{D1,D2,…,DVi}的平均信息熵。最终，将信息增益最大(即对纯度提升最大)的特征项选作对数据集D进行划分的最优特征，即

Xoptimal= argmaxi=1,2,…,dGain(D,Xi)(346)

信息增益最大，这意味着子集的平均信息熵最小，也就是子集的平均纯度最大。基于信息增益选择特征，往往会偏向选择取值较多(即子集较多)的特征。为消除这种偏向，决策树学习算法引入了信息增益率的概念，基于信息增益率选择特征会更加客观。

2) C4.5(信息增益率)
假设按第i项特征Xi将数据集D划分成Vi个子集{D1,D2,…,DVi}，C4.5算法在式(345)信息增益的基础上，再定义特征Xi对数据集D进行划分所获得的信息增益率(information gain ratio)为

Gain_ratio(D,Xi)=Gain(D,Xi)HXi(D)，i=1,2,…,d(347)

其中，HXi(D)表示数据集D中特征Xi的信息熵(将特征Xi看作随机变量)，其计算公式为

HXi(D)=-∑Vik=1mkmlbmkm，i=1,2,…,d(348)

最终，将信息增益率最大的特征项选作对数据集D进行划分的最优特征，即

Xoptimal= argmaxi=1,2,…,dGain_ratio(D,Xi)(349)


3) CART(基尼指数)
假设按第i项特征Xi将数据集D划分成Vi个子集{D1,D2,…,DVi}，CART算法按式(344)计算各子集D1,D2,…,DVi的基尼指数，然后定义特征Xi对数据集D进行划分所得子集的平均基尼指数(average Gini index)为

Gini_average(D,Xi)=∑Vik=1mkmGini(Dk)，i=1,2,…d(350)

最终，将平均基尼指数最小(即子集平均纯度最大)的特征项选作对数据集D进行划分的最优特征，即

Xoptimal= argmini=1,2,…,dGini_average(D,Xi)(351)


5. 将不可划分子集设为叶子结点
决策树学习算法从建立根结点开始，依据某种准则(ID3、C4.5或CART)选择最优特征项，并按该特征项的取值将初始训练集划分成若干子集，为每个子集生成一个内部结点； 剔除已使用过的特征项，再对所有子集重复“选择特征划分子集”的过程，直到不可划分为止； 将不可划分子集的结点设为叶子结点，并将其标记为某个类别。决策树学习算法是一个递归算法，停止递归的条件是子集不可划分。
什么样的子集是不可划分子集呢？不可划分子集有4种情况。
(1) 当前子集的样本属于同一类别(假设为ck)，无须划分。将当前子集的结点设为叶子结点，并将其类别标记为ck。
（2) 当前子集为空集，无法划分。将当前子集的结点设为叶子结点，并将该结点的类别标记为其父结点数据集中所含样本最多的类别。注： 按照某个特征项的取值划分数据集，如果数据集没有覆盖该特征项的全部取值，则未被覆盖取值所划分出的子集为空集。
（3) 选择特征项划分当前子集，如果所有特征项都已使用过，没有任何新特征项可供选择，则无法继续划分。将当前子集的结点设为叶子结点，并将该结点的类别标记为当前子集所含样本最多的类别。注： 对子集重复“选择特征划分子集”的过程时，需要剔除之前已经使用过的特征项，只在剩下的新特征项中选择。
（4) 选择某个特征项划分当前子集，如果当前子集包含的所有样本点在该特征项下的取值都相同，则无法继续划分。将当前子集的结点设为叶子结点，并将该结点的类别标记为当前子集所含样本最多的类别。
总结一下，决策树模型就是将初始训练集逐步划分为纯度更高的子集，并在此过程中学习到分类规则，即决策树。今后，可以使用决策树对任意新样本进行分类。这里进一步对分类器模型做一下总结。给定特征X，建立分类器模型有两种不同的思路：一是贝叶斯分类器，即基于概率模型并依最大后验概率P（Y|X）来判定类别Y，例如朴素贝叶斯分类器、逻辑斯蒂回归等，其中最值得借鉴的是如何基于严谨的概率模型与概率推理来求解问题；二是非贝叶斯分类器，即直接基于特征X来建立类别Y的判别函数，例如k近邻分类器、线性判别分析、决策树等，其中最值得借鉴的是如何提出创新思想并将其形式化为可被计算机执行的算法，也即将只可“意会”的思想转变为可以“言传”的算法。
6. 使用scikitlearn库中的决策树分类器模型
scikitlearn库将决策树分类器模型封装成一个类(类名为DecisionTreeClassifier)，并将其存放在sklearn.tree模块中。DecisionTreeClassifier类实现了决策树分类器模型的学习算法fit()、预测算法predict()和评价算法score()。
图317给出了使用DecisionTreeClassifier类建立并训练乳腺癌诊断模型的示例代码。



图317使用DecisionTreeClassifier类建立并训练乳腺癌诊断模型的示例代码


其中诊断模型(即分类模型)采用的是决策树分类器； 数据集使用的是3.1.3节标准化后的乳腺癌诊断数据集，其中的训练集(X1_train、Y_train)被用于训练模型； 然后用训练好的模型对测试集X1_test前2个病例样本进行分类预测，将预测结果predict与Y_test中的真实诊断结果malignant进行比对，1表示恶性，0表示良性； 最后使用函数score()计算模型在训练集(X1_train、Y_train)和测试集(X1_test、Y_test)上的平均正确率。


3.3多分类问题与分类模型评价
某些分类器既可以处理二分类，也可以处理多分类； 而某些分类器只能处理二分类。本节首先讲解如何将多分类问题转换为二分类问题，然后使用二分类的方法来处理多分类。
机器学习在训练好模型之后，更关注模型对新样本的预测能力，即泛化能力。模型的泛化能力强，这才是机器学习意义上的好模型。为此，机器学习在训练好模型之后还需要再用测试集进行测试，评价模型的泛化性能。评价回归模型泛化能力的主要指标有均方误差MSE和决定系数R方（参见2.3.3节)，而评价分类模型泛化能力则会使用完全不同的指标。本节将介绍评价分类模型泛化能力的主要指标。

3.3.1二分类与多分类
对“是/否”“真/假”“好/坏”等问题进行分类属于二分类问题。例如，根据临床特征判定乳腺癌是否恶性肿瘤就是一个二分类问题。在二分类问题中，类别的取值只有两个。通常将感兴趣的类别记作1，并将其称作正类(positive class)； 另外那个类别记作0或-1，并将其称作反类(negative class)。例如乳腺癌诊断问题所关注的是恶性肿瘤，可以将恶性肿瘤看作正类，良性肿瘤看作反类。对于数据集中的样本数据，正类的样本数据被称作正例(positive example)，反类的样本数据被称作反例(negative example)。
实际应用中还有一些多分类问题，例如判断苹果品种是红富士、国光或黄元帅(三分类)，人脸识别和语音识别(N分类)等。某些分类器既可以处理二分类，也可以处理多分类，例如朴素贝叶斯、k近邻、决策树等。某些分类器本来只能处理二分类，但略加修改即可推广至多分类，例如逻辑斯谛回归、线性判别分析等。
处理多分类问题的另一种思路是将其转换为二分类问题。可以将多分类问题拆分为若干个二分类问题，为每个二分类问题设计一个分类器，然后汇总它们的二分类结果，最终得出多分类的结果。
假设给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi是样本特征，yi∈{c1,c2,…,cN}是其对应的实际类别，共N个类别。将这样的N分类问题拆分为二分类问题，常用的拆分策略有一对一(One vs 
One，OvO)或一对其余(One vs  Rest，OvR)。

1. 一对一
按照一对一拆分策略，将N个类别两两组合，总共拆分出N(N-1)/2个二分类问题。每个类别ck与另外N-1个类别按一对一方式，分别设计N-1个分类器。给定新的样本特征，每个分类器会得到一个是或不是ck的二分类结果； 统计是ck的结果个数(记作nk)，然后将nk最大的类别作为多分类结果。

2. 一对其余
按照一对其余拆分策略，每次将N个类别中的一个作为正类，其余N-1个合起来作为反类，总共拆分出N个二分类问题。设计N个分类器，每个类别ck对应一个以ck为正类的分类器。给定新的样本特征，每个分类器会得到一个是否正类的二分类结果； 如果只有一个分类器判定样本为正类，则将该分类器对应的正类ck作为多分类结果； 如果有多个分类器判定样本为正类，则将正类概率(或称score)最大的那个ck作为多分类结果。

3.3.2分类模型的评价指标
分类模型在训练好之后还需要再用测试集进行测试，评价其泛化能力。注意，训练模型时会使用损失函数或准则函数来评价模型在训练集上的性能，并以此作为选择最优参数的标准。不同模型在训练时会使用不同的损失函数或准则函数，但评价泛化能力时则应使用统一的评价指标，这样才有可比性。

1. 二分类模型的评价指标
给定某个样例(x,y)，将分类器模型f的分类结果记作f(x)。如果样例(x,y)的分类结果f(x)与真实类别y一致，即f(x)=y，则称样例(x,y)分类正确，否则就是分类错误。
式（352）定义了一个机器学习中常用的函数I(A)，其中A表示一个事件。该函数被称作事件A的指示函数(indicator function)，或事件A的指示随机变量(服从01分布)。

I(A)=1，如果事件A发生了

0，如果事件A未发生(352)

例如，

I(f(x)=y)=1，如果f(x)=y

0，如果f(x)≠y

针对二分类问题，假设给定测试集Dtest={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi是样本特征，yi∈{0,1}是其对应的真实类别。测试集Dtest共有m个测试样例，假设其中正例有m+个，反例有m-个，m++m-=m。下面给出评价二分类模型泛化能力的主要指标。

1) 正确率
正确率(accuracy)就是分类器模型f对测试集Dtest分类正确的样例数占总样例数的比例，即

accuracy=∑mi=1I(f(xi)=yi)m(353)

在正类、反类分布不平衡的情况下，正确率并不能客观反映分类器模型的性能。例如，乳腺癌分类器模型可以将恶性肿瘤看作正类，良性肿瘤看作反类。假设良性肿瘤占全部肿瘤的99%，恶性肿瘤只占1%。设计一个最简单的分类器，给定任意肿瘤样本，将分类结果都固定判定为良性肿瘤，则其分类正确率可高达99%。这显然是不合理的，或者说不符合人们对分类器模型的评价需求。

2) 混淆矩阵
在二分类问题中，被分类器判定为正类的样例，如果其真实类别确实是正类，则称为真正例(True Positive，TP)； 如果其真实类别是反类，则称为假正例(False Positive，FP)。同理，被分类器判定为反类的样例，如果其真实类别确实是反类，则称为真反例(True Negative，TN)； 如果其真实类别是正类，则称为假反例(False Negative，FN)。
使用测试集对分类器模型进行测试，二分类结果可以表示成混淆矩阵(confusion matrix)的形式，其中包括TP、FP、TN、FN这4种情形的样例数（参见表39）。


表39二分类结果的混淆矩阵




真实类别
分类结果
正例反例
正例TP(真正例)FN(假反例)
反例FP(假正例)TN(真反例)

假设测试集有m个测试样例，其中正例有m+个，反例有m-个，则

TP+FN=m+； TN+FP=m-； TP+FN+TN+FP=m


3) 精确率与召回率
在乳腺癌分类器模型中，人们可能会更关注恶性肿瘤(正类)的分类性能，这时可以使用正类的精确率或召回率来评价分类模型。
精确率(precision，记作P)就是在被分类器判定为正类的样例(TP+FP)中，有多大比例属于真正例(TP)； 召回率(recall，记作R)就是在数据集的全部正例(TP+FN)中，有多大比例能被分类器判定为正例(即真正例TP)。基于混淆矩阵可以计算出精确率P和召回率R。

P=TPTP+FP(354)

R=TPTP+FN(355)

例如乳腺癌分类器模型将恶性肿瘤看作正类，良性肿瘤看作反类，则精确率P表示被分类器判定为恶性肿瘤的样例中，有多大比例属于真的恶性肿瘤； 召回率R表示数据集的全部恶性肿瘤样例中，有多大比例能被分类器找出来(即确实被判定为恶性肿瘤)。
设计分类器时，精确率和召回率通常很难同时兼顾到。精确率高时，召回率往往偏低； 召回率高时，精确率就会偏低。例如，设计乳腺癌分类器模型时，严格恶性肿瘤的诊断标准可以提高精确性，但会造成某些恶性肿瘤的漏诊(召回率降低)； 放松诊断标准虽能提高召回率，但会将某些良性肿瘤误诊为恶性肿瘤(精确率降低)。不同分类问题对精确率、召回率的关注程度不同，某些问题关注精确率，另外一些问题可能更关注召回率。
可以将精确率和召回率结合起来，构造一个综合性评价指标。F1值就是这样一种比较常用的综合性指标，其定义形式为

1F1=12·1P+1R

整理可得，

F1=2×P×RP+R(356)


2. 使用scikitlearn库中的度量函数
scikitlearn库为分类模型评价指标提供了相应的计算函数，它们被统一存放在sklearn.metrics模块中。
accuracy_score()： 正确率计算函数； 
precision_score()： 精确率计算函数； 
recall_score()： 召回率计算函数； 
f1_score()： F1值计算函数。
图318给出了计算乳腺癌诊断模型评价指标的示例代码。其中图318（a）使用的诊断模型是决策树分类器，图318（b）使用的则是逻辑斯谛回归分类器； 数据集使用的都是3.1.3节标准化后的乳腺癌诊断数据集，训练集(X1_train、Y_train)被用于训练模型； 然后用测试集(X1_test、Y_test)对模型进行测试，分别计算并显示模型在测试集上的正确率、精确率、召回率和F1值。




图318计算乳腺癌诊断模型评价指标的示例代码



3. 多分类模型的评价指标
多分类问题可以看作由多个二分类问题组成，测试结果可以表示成多个二分类混淆矩阵。对这些二分类混淆矩阵求平均，将所得到的平均指标作为多分类模型的评价指标。
第一种求平均的方法： 先计算各混淆矩阵的精确率、召回率和F1值，然后
对计算结果分别
求平均，所得到的平均值被称为宏精确率(macroP)、宏召回率(macroR)和宏F1值(macroF1)。
第二种求平均的方法： 先对混淆矩阵的TP、FP、TN、FN样例数求平均，得到一个平均混淆矩阵，基于这个平均混淆矩阵所求出的精确率、召回率和F1值被称为
微精确率(microP)、微召回率(microR)和微F1值(microF1)。

3.3.3PR曲线与ROC曲线
本节再介绍两种评价分类模型的可视化曲线，即PR曲线与ROC曲线。针对二分类问题，一个理想分类器应当将正例样本判定为正类，将反例样本判定给反例。给定样本特征，分类器会生成一个属于正类(或反类)的后验概率，或一个模拟的后验概率值。使用测试集对分类器模型进行测试，按后验概率(或模拟后验概率)对测试样本进行降序排序，如图319所示。



图319按后验概率(或模拟后验概率)排序后的测试样本


如果是理想分类器，则所有正例样本属于正类的后验概率都应该比反例样本高，会排在反例样本的前面(见图319（a）)。但实际的分类器很难做到这一点，某些反例样本属于正类的后验概率比正例样本高，反而排在正例样本的前面(见图319（b）)。正例样本和反例样本的排列次序能在更深层次上反映分类器性能的优劣。
1. PR曲线
为后验概率(或模拟后验概率)设定一个阈值(threshold)T，将高于或等于阈值的样本判为正类，低于阈值的判为反类，这样可以模拟一次分类决策。按从高到低的
顺序逐次降低阈值Ti，模拟出一组分类决策，分别计算每次分类结果的精确率和召回率，得到一组(Pi,Ri)数据。将这组(Pi,Ri)数据绘制成图形，以精确率P为纵轴，召回率R为横轴，就得到一条“精确率召回率”曲线，它被称作PR曲线(PR curve)。
scikitlearn库为计算PR曲线提供了一个函数precision_recall_curve()，它可以自动设置阈值，并计算出一组(Pi,Ri)数据，该函数被存放在sklearn.metrics模块中。
图320给出了计算并绘制乳腺癌诊断模型PR曲线的示例代码(见图320（a）)及其运行结果(见图320（b）)。其中的诊断模型是逻辑斯谛回归分类器，可以调用其predict_proba()函数获取测试样本的后验概率； 数据集使用的是3.1.3节标准化后的乳腺癌诊断数据集，训练集(X1_train、Y_train)被用于训练模型； 然后用测试集(X1_test、Y_test)对模型进行测试，计算并显示测试结果的PR曲线。




图320计算并绘制乳腺癌诊断模型PR曲线的示例代码和运行结果


因为乳腺癌数据集比较小，正例
（恶性）样本更少，因此图320（b）所绘制的PR曲线(实线部分)很不平滑。在样本数据足够多的情况下，PR曲线应该像图320（b）中虚线部分那样比较平滑。从PR曲线可以更直观地看到，精确率高时，召回率往往偏低； 召回率高时，精确率就会偏低。PR曲线越偏向右上角，说明分类器的性能越好。

2. ROC曲线
将PR曲线的纵轴由精确率P改为真正例率(True Positive Rate，TPR)，横轴由召回率R改为假正例率(False Positive Rate，FPR)，这样所得到的曲线被称为ROC(Receiver Operating Characteristic)曲线。真正例率TPR、假正例率FPR的定义分别为

TPR=TPTP+FN(357)

FPR=FPTN+FP(358)

ROC曲线的计算与绘制过程与PR曲线类似。使用测试集对分类器模型进行测试，按从高到低的次序为测试样本后验概率设定一组阈值Ti，模拟出一组分类决策，分别计算每次分类结果的真正例率和假正例率，得到一组(TPRi,FPRi)数据。将这组(TPRi,FPRi)数据绘制成图形，以真正例率TPR为纵轴，假正例率FPR为横轴，就得到一条ROC曲线。
scikitlearn库为ROC曲线提供了一个函数roc_curve()，它可以自动设置阈值，并计算出一组(TPRi,FPRi)数据，该函数被存放在sklearn.metrics模块中。图321给出了计算并绘制乳腺癌诊断模型ROC曲线的示例代码(见图321（a）)及其运行结果(见图321（b）)。


图321计算并绘制乳腺癌诊断模型ROC曲线的示例代码和运行结果


同样，因为乳腺癌数据集比较小，所以图321（b）所绘制的ROC曲线(实线部分)不太平滑。在样本数据足够多的情况下，ROC曲线应该像图321（b）中虚线部分那样，比较平滑。ROC曲线越偏向左上角，说明分类器的性能越好。

3.4特征降维
给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi是d维样本特征，yi∈{c1,c2,…,cn}是其对应的实际类别，i=1,2,…,m。可以将样本特征xi看作特征空间里的向量。在特征空间中，每个特征项是一个维度并对应一个标准基向量，d个特征项就构成一个d维特征空间，其标准基向量可记作{e1,e2,…,ed}。每个样本数据xi对应特征空间里的一个点，其坐标{xi1,xi2,…,xid}就是样本在各特征项上的取值。
例如表31的苹果样本数据，其样本特征包含底色、外形、口感和果重4个特征项，以这4个特征项为坐标轴就构成一个四维特征空间。表31的苹果样本特征是经过人的加工整理，然后提炼出来的，这个加工、提炼过程被称为特征提取(feature extraction)。
经过特征提取的数据比较精炼、规范，这样的数据被称为结构化(structured)数据。实际应用中还有大量非结构化(unstructured)数据，例如文本数据、音频数据、图像数据、视频数据等。提取非结构化数据的特征需专门领域的知识，例如自然语言处理、语音信号处理、数字图像处理等。
可以先对非结构化的原始数据进行特征提取，然后基于所提取的特征数据进行机器学习。也可以直接以非结构化原始数据为特征进行机器学习，其优点是不会因特征提取而丢失任何信息，缺点是维数太多。维数很多的数据被称为高维(highdimension)数据。例如，在22kHz采样率情况下，一段10ms语音采样数据(见图322（a）)大约有22×10=220(个)，其维数是220维； 一幅64×64=4096(像素)灰度图像(见图322（b）)的维数是4096维，而彩色图像的维数则是4096×3=12288维。



图322高维数据示例


在机器学习中，特征维数过高很容易导致距离计算困难、对样本需求量迅速加大(否则难以体现联合概率分布)等问题，这种现象被称为维数灾难(curse of dimensionality)。降维(dimension reduction)是缓解维数灾难的重要途径，其中会用到线性代数相关的知识，例如坐标变换及其矩阵表示、矩阵的特征值分解与奇异值分解等。

3.4.1线性代数基础
1. 坐标变换及其矩阵表示

一个二维特征空间(见图323)，其两个标准基{e1,e2}分别对应样本特征的两个特征项。可以将样本特征数据x看作特征空间中的一个点，其坐标(x1,x2)为样本在特征项1、特征项2上的取值； x也被称作特征空间中的一个特征向量，记作x=(x1,x2)T。



图323二维特征空间的坐标变换


假设将特征向量x在e1、e2方向上的坐标分别拉伸λ1、λ2倍(见图323（a）)，则拉伸(或称缩放)变换后新向量z的坐标为

z=z1
z2=λ1x1
λ2x2=λ10
0λ2x1
x2=λ10
0λ2x

记D=λ10
0λ2，则z=Dx。一般地，d维特征空间的拉伸变换可以用一个d×d对角矩阵D表示，其对角元素就是在各坐标轴方向的拉伸倍数。换句话说，对角矩阵对应的坐标变换为拉伸变换。
假设将两个标准基{e1,e2}旋转某个角度θ(见图323（b）)，得到一组新的基{u1,u2}： 


u1=u11
u12，u2=u21
u22，或写成u1=u11e1+u12e2，u2=u21e1+u22e2。
旋转变换后，向量x=(x1,x2)T在基{u1,u2}下的坐标z为

z=z1
z2=u11u12
u21u22x1
x2=uT1
uT2x(359)

记U=uT1
uT2，则z=Ux。坐标z实际上就是向量x在新基向量{u1,u2}上的标量投影(被称作
投影变换)，旋转变换就是一种投影变换。一般地，d维特征空间从一组基，例如标准基{e1,e2,…,ed}，到另一组基{u1,u2,…,ud}的投影变换可以用一个d×d矩阵U表示，其行向量分别对应新的基向量。将向量x=(x1,x2,…,xd)T在基{u1,u2,…,ud}下的坐标记作z=(z1,z2,…,zd)T，则

z=Ux，其中Ud×d=uT1
uT2
︙
uTd(360)

矩阵U称作从基{e1,e2,…,ed}到基{u1,u2,…,ud}的转移矩阵(transition matrix)。如果新的基向量{u1,u2,…,ud}是规范正交基(由相互正交单位向量构成的基)，即

uTiuj=1，i=j

0，i≠j，i,j=1,2,…,d

则转移矩阵Ud×d为正交矩阵(orthogonal matrix)，即U-1=UT，或UTU=I。任意一组基(可能不正交或不规范)到规范正交基的投影变换，其转移矩阵均为正交矩阵。
对样本数据进行坐标变换，实际上是对样本做特征变换。变换前，坐标x=(x1,x2,…,xd)T是样本在原特征项上的取值； 变换后，坐标z=(z1,z2,…,zd)T是样本在新特征项上的取值，因此坐标变换就是将原特征x变换成新特征z。
式（359）、式（360）坐标变换所得到的新特征z是原特征x的线性组合，即线性变换。
线性变换可表示成矩阵形式，
拉伸变换和投影变换都属于线性变换。线性变换可以利用线性代数相关的理论、方法进行处理。实际应用中还会存在非线性的情况，某些非线性变换可以通过核函数(kernel function)转化为线性变换。

2. 特征值、特征向量与特征值分解
定义31一个n×n矩阵A，如果存在一个非零向量x使得Ax=λx，则称标量λ为矩阵A的特征值(eigenvalue)，向量x为矩阵A的属于特征值λ的特征向量(eigenvector)。

定理31一个n×n矩阵A是可对角化的，当且仅当A有n个线性无关的特征向量。
证明： 若A有n个线性无关特征向量x1,x2,…,xn，其对应的特征值分别为λ1,λ2,…,λn，则以这n个特征向量为列向量的矩阵X=(x1,x2,…,xn)可逆并能将A对角化，即

AX=A(x1,x2,…,xn)=(Ax1,Ax2,…,Axn)=(λ1x1,λ2x2,…,λnxn)，

AX=(x1,x2,…,xn)λ1
λ2

λn=XD
(361)

因为x1,x2,…,xn线性无关，所以X可逆，因而

X-1AX=D，或A=XDX-1(362)

其中的X、D不唯一，因为将各列重排或乘以一个非零系数，新的X及其对应的D仍能将A对角化。矩阵A可对角化也可以说成是矩阵A可按特征值分解为XDX-1。

定理32(谱定理)若A是n×n实对称矩阵，则存在一个正交矩阵U可以对角化A，即UTAU=D，其中U的列向量是A的n个线性无关特征向量(单位向量)，D是对角矩阵(对角元素是特征向量对应的特征值)。或者说，实对称矩阵A可分解为一个正交矩阵U和一个对角矩阵D，即

A=UDUT=(u1,u2,…,un)λ1
λ2

λnuT1
uT2
︙
uTn

=λ1u1uT1+λ2u2uT2+…+λnunuTn

定理32的意义在于，如果将n×n实对称矩阵A看作一个坐标变换，则该变换可分解成两次到规范正交基的投影变换和一次拉伸变换，其中投影变换的基对应矩阵A的各特征向量，拉伸变换的倍数对应矩阵A的各特征值。或者说，实对称矩阵A可分解成一组分量(即u1uT1、u2uT2、…、unuTn)的线性组合，各分量的系数(或称作“谱”)就是矩阵A的特征值。

定义32一个n×n实对称矩阵A，若对任意非零向量x∈Rn，有xTAx≥0，则称A为半正定的(positive semidefinite)。

定理33半正定矩阵的所有特征值都为非负实数。
证明： 对于n×n半正定矩阵A，若λ是A的特征值，x是属于λ的特征向量，则对任意非零向量x∈Rn，有 xTAx=λxTx=λ‖x‖2。
因为xTAx≥0，所以

λ=xTAx‖x‖2≥0


定理34若A为一m×n实矩阵，则ATA为n×n实对称半正定矩阵，AAT为m×m实对称半正定矩阵，且ATA、AAT的所有特征值均为非负实数。
证明： 若A为一m×n实矩阵，则ATA为n×n实对称矩阵。对任意非零向量x∈Rn，有xTATAx=(Ax)T(Ax)=‖Ax‖2≥0，所以ATA为n×n半正定矩阵，其所有特征值均为非负实数。
同理可证，AAT为m×m实对称半正定矩阵，其所有特征值也都为非负实数。

定理34的几何意义在于，如果将n×n实对称矩阵ATA看作一个坐标变换，则该变换可分解成两次到规范正交基的投影变换和一次拉伸变换（谱定理），其中投影变换的基对应矩阵ATA的各特征向量，拉伸变换的倍数对应矩阵ATA的各特征值，它们均为非负实数。同理，AAT与此类似。

3. 矩阵的奇异值分解
定理35(SVD定理)若A为一m×n实矩阵(假设m>n)，则A有一个奇异值分解，即A=UΣVT，其中U是一m×m正交矩阵，V是一n×n正交矩阵，Σ是一m×n矩阵。Σ的矩阵形式为

Σ=Σ1
0，其中Σ1=σ1
σ2

σn(363)

其对角线元素满足

σ1≥σ2≥…≥σn≥0且σ21,σ22,…,σ2n为ATA的特征值

证明： 略(分别用ATA的特征向量构造V，用AAT的特征向量构造U)。

定理36A为一m×n实矩阵，若A的奇异值分解为A=UΣVT，则
（1) U=(u1,u2,…,um)的列向量为AAT的特征向量，且U可对角化AAT，即

UTAATU=ΣΣT

（2) V=(�瘙
經1,�瘙
經2,…,�瘙
經n)的列向量为ATA的特征向量，且V可对角化ATA，即

VTATAV=ΣTΣ

其中Σ如式（363）所示，ΣΣT(或ΣTΣ)为对角矩阵，其对角元素为AAT(或ATA)的特征值。
证明： 略(将A=UΣVT代入UTAATU、VTATAV即可)。

4. 样本特征的协方差矩阵
给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi是d维样本特征，则定义训练集特征矩阵X为

Xd×m=(x1,x2,…,xm)=x11x21…xm1
x12x22…xm2
︙︙︙
x1dx2d…xmd(364)

其中的每一列对应一个样本数据xi，i=1,2,…,m。
换个角度，可以将d维样本特征的每个特征项看作一个随机变量Xk，k=1,2,…,d，则特征矩阵X的第k行就是随机变量Xk的样本数据。每个特征随机变量Xk有m个样本数据，计算其均值，

μ=μ1
μ2
︙
μd，μk=1m∑mi=1xik，k=1,2,…,d

再将特征随机变量的协方差矩阵(或称特征内积矩阵)记作Σ(与式（363）中的Σ没有关系，仅仅是用了相同的记号)，其计算公式为

Σd×d=1m-1(x1-μ,x2-μ,…,xm-μ)(x1-μ,x2-μ,…,xm-μ)T

=1m-1x11-μ1x21-μ1…xm1-μ1
x12-μ2x22-μ2…xm2-μ2
︙︙︙
x1d-μdx2d-μd…xmd-μdx11-μ1x21-μ1…xm1-μ1
x12-μ2x22-μ2…xm2-μ2
︙︙︙
x1d-μdx2d-μd…xmd-μdT

由定理34可知，协方差矩阵Σ是一个d×d实对称半正定矩阵。记

Σd×d=σ211σ212…σ21d
σ221σ222…σ22d
︙︙︙
σ2d1σ2d2…σ2dd

其中，σ2kl=1m-1∑mi=1(xki-μk)(xli-μl)，k,l=1,2,…,d，并且Σ中的对角元素为各特征项的方差，非对角元素为不同特征项之间的协方差。
如果先对样本特征做去中心化(zerocentered，或称零均值化)处理，即将各特征项样本数据分别减去其均值，这样可以简化协方差矩阵的计算。去中心化后每个特征随机变量Xk的均值μk=0，特征的协方差矩阵Σ因此可简化为

Σd×d=1m-1x11x21…xm1
x12x22…xm2
︙︙︙
x1dx2d…xmdx11x21…xm1
x12x22…xm2
︙︙︙
x1dx2d…xmdT=1m-1XXT(365)

记

Σd×d=σ211σ212…σ21d
σ221σ222…σ22d
︙︙︙
σ2d1σ2d2…σ2dd

其中，σ2kl=1m-1∑mi=1xkixli，k,l=1,2,…,d。

3.4.2主成分分析
样本特征由多个特征项组成，可以将每个特征项看作样本特征的一个成分(component，或称分量)，每个成分(即每个特征项)都是一个随机变量。主成分分析(Principal Component Analysis，PCA)是一种常用的特征降维方法，其核心思想是： 
 两个特征项之间的协方差反映它们的相关性。协方差越大，则特征项之间的相关性就越大，数据冗余也越大。机器学习应尽可能消除数据冗余，也即降低特征项之间的相关性，让它们的协方差越接近于零越好。
 特征项的方差反映所携带的信息量。方差越大，则特征项所携带的信息量就越大。方差大的特征项属于样本特征的主要成分，方差小的则属于次要成分。特征降维时应保留样本特征的主要成分，丢弃次要成分。
 通过对样本特征进行投影变换，尽可能降低不同特征项之间的相关性，然后仅保留样本特征的主要成分即可实现降维。PCA降维的关键是选择投影方向，找出最优的投影基向量。

1. 标准化样本特征
给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，或Dtrain={x1,x2,…,xm}，其中xi是d维样本特征。PCA降维要求先对原始样本特征做去中心化和归一化处理(例如zscore标准化)，去中心化是为了简化协方差矩阵的计算，归一化是为了让不同特征之间的方差可比较； 然后构造样本的特征矩阵Xd×m(见式（364）)，并计算其协方差矩阵Σd×d(见式（365）)。为便于后续讲解，这里将特征矩阵Xd×m的协方差矩阵Σd×d改记为ΣXd×d。

2. 选择最优特征变换方向
给定d维样本特征数据x或样本特征矩阵Xd×m=(x1,x2,…,xm)，从原始基向量，例如标准基{e1,e2,…,ed}，到另一组规范正交基{w1,w2,…,wd}对样本特征做投影变换，变换后的坐标可表示为如下矩阵形式： 

z=Wx=wT1
wT2
︙
wTdx(366a)

或

Zd×m=WXd×m=wT1
wT2
︙
wTd(x1,x2,…,xm)(366b)

其中，W为d×d转移矩阵，z为单个样本特征x投影变换后的新特征向量； Zd×m为样本特征矩阵Xd×m投影变换后的新特征矩阵，其展开式为

Zd×m=(z1,z2,…,zm)=z11z21…zm1
z12z22…zm2
︙︙︙
z1dz2d…zmd

因为样本特征矩阵Xd×m经过去中心化处理，所以每一行的均值或累加和都为0。投影变换所得到新的样本特征矩阵Zd×m，其每一行的均值与累加和也保持为零。
如果将新样本特征的每个特征项(Zd×m中的每一行)看作一个随机变量Zk，k=1,2,…,d，则新特征随机变量的协方差矩阵为

ΣZd×d=1m-1z11z21…zm1
z12z22…zm2
︙︙︙
z1dz2d…zmdz11z21…zm1
z12z22…zm2
︙︙︙
z1dz2d…zmdT=1m-1ZZT

PCA希望新的特征随机变量Zk之间相关性越小越好，这样可以消除数据冗余。理想情况下，协方差矩阵ΣZd×d应为对角阵，即各特征项之间的协方差都为0： 

ΣZd×d=σ211
σ222

σ2dd

因为

ΣZd×d=1m-1ZZT=1m-1(WX)(WX)T=W1m-1XXTWT(367)

将式（365）代入式（367）得

ΣZd×d=W1m-1XXTWT=W(ΣXd×d)WT(368)

可以看出，如果W(ΣXd×d)WT是对角阵，则ΣZd×d就是对角阵。那么该如何选择转移矩阵W，使得W(ΣXd×d)WT为对角阵呢？
ΣXd×d是实对称半正定矩阵，因此存在一个正交矩阵U可对角化ΣXd×d
（谱定理），即

UT(ΣXd×d)U=uT1
uT2
︙
uTd(ΣXd×d)(u1,u2,…,ud)=λ1
λ2

λd(369)


其中，U为d×d正交矩阵，u1,u2,…,ud为矩阵ΣXd×d的d个线性无关特征向量(单位向量)； x=diag(λ1,λ2,…,λd)为对角矩阵，对角元素分别为特征向量u1,u2,…,ud对应的特征值λ1,λ2,…,λd。如果以{u1,u2,…,ud}作为投影变换的基向量{w1,w2,…,wd}，则转移矩阵Wd×d=UTd×d，即

Wd×d=UTd×d=uT1
uT2
︙
uTd(370)

将式（370）、式（369）代入式（368）得

ΣZd×d=W(ΣXd×d)WT=UT(ΣXd×d)U=λ1
λ2

λd(371)

从式（371）可以看出，选择协方差矩阵ΣXd×d的单位特征向量构造一组规范正交基{u1,u2,…,ud}，则

对样本特征从原始基向量到新基向量{u1,u2,…,ud}
做投影变换，变换得到的新样本特征具有如下特性。

（1) 各特征项之间相互独立，协方差为零。结论1： 
由协方差矩阵ΣXd×d各单位特征向量所构造的规范正交基{u1,u2,…,ud}，就是PCA所要选择的最优投影基向量，也即最优的变换方向。
（2) 第k个特征项Zk的方差为对应基向量uk的特征值λk。结论2： 对各特征值排序，λ1≥λ2≥…≥λd≥0，则特征值大的基向量代表样本特征的主要成分，其所对应的特征项应当保留； 特征值小的基向量代表样本特征的次要成分，其所对应的特征项可以丢弃。

3. PCA算法步骤
给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，或Dtrain={x1,x2,…,xm}，其中xi是d维样本特征。
1) 样本特征标准化
构造训练集特征矩阵Xo，计算各特征项均值μk、标准差σk，对Xo进行zscore标准化，得到标准化特征矩阵X。

Xod×m=(x1,x2,…,xm)=x11x21…xm1
x12x22…xm2
︙︙︙
x1dx2d…xmd

μk=1m∑mi=1xik，σk=
1m-1∑mi=1
(xik-μk)2，k=1,2,…,d

Xd×m=(x11-μ1)/σ1(x21-μ1)/σ1…(xm1-μ1)/σ1
(x12-μ2)/σ2(x22-μ2)/σ2…(xm2-μ2)/σ2
︙︙︙
(x1d-μd)/σd(x2d-μd)/σd…(xmd-μd)/σd(372)


2) 对协方差矩阵ΣXd×d做特征值分解
按照式（365）计算协方差矩阵ΣXd×d，然后进行特征值分解，求得特征值λ1,λ2,…,λd及其对应的特征向量u1,u2,…,ud。
3) 构造转移矩阵W
假设将d维样本特征降到d′维，则先对特征值排序，按从大到小的顺序选取前d′个特征值所对应的特征向量u1,u2,…,ud′，以它们为行向量构造出投影变换的转移矩阵Wd′×d。
4) 特征降维
给定d维样本特征x，按照计算公式z=Wd′×dx，求得降维后的d′维样本特征z。
注： 算法第2步可以将特征值分解改为奇异值分解。这时可以不计算协方差矩阵ΣXd×d，而是直接对训练集特征矩阵X做奇异值分解，即X=UΣVT，求得奇异值σ1,σ2,…,σd。奇异值σi与协方差矩阵ΣXd×d特征值λi之间的关系是： σ2i=λi，奇异值σi在U中的左奇异向量(列向量)也恰好对应着协方差矩阵ΣXd×d的特征向量ui。按训练集特征矩阵X奇异值大小，选择d′个单位左奇异向量为行向量构造出投影变换的转移矩阵Wd′×d，它与按协方差矩阵ΣXd×d特征值分解求得的转移矩阵完全一致。

4. 核主成分分析
样本特征是被观测到的数据，它反映了事物的某种内在规律。这种内在规律可能是在低维空间上展开，却在高维空间被观测到并记录成高维空间的特征。例如，单摆上的小球在一维曲线上做往复摆动(见图324)，但观测记录的特征却是二维
(甚至是三维)位置坐标。这种情况被描述为，具有低维结构的特征被嵌入(embedding)高维空间中，简称“低维嵌入”。



图324单摆小球在一维曲线上做往复摆动


协方差矩阵是很多机器学习算法的基础，它反映了特征(即随机变量)之间的相关性或特征之间的某种结构。PCA降维就是在构造标准化特征矩阵X之后，先按式（365）计算其协方差矩阵ΣXd×d，然后再基于协方差矩阵进行降维。
核主成分分析(Kernel PCA，KPCA)的核心思想： 在低维嵌入的情况下，应当基于低维特征协方差而不是高维特征协方差来进行降维，否则会丢失特征的低维结构。
如果知道低维特征是如何嵌入到高维空间中去的，例如已知嵌入函数： 低维特征→高维特征(或-1： 高维特征→低维特征)，则可以根据嵌入函数找出计算低维特征协方差的办法。但多数情况下，嵌入函数是未知的。
在嵌入函数未知的情况下，如何根据观测到的高维特征去计算低维特征的协方差呢？协方差计算是基于向量内积的。可以基于高维特征定义一个函数来模拟低维特征的内积，这样的函数被称作核函数(kernel function)，通常记作K(xi,xj)。其中xi,xj是两个高维特征向量，而函数值则是它们在低维空间对应特征向量的内积(即-1(xi)·-1(xj))。
至于如何定义或选择核函数K(xi,xj)，目前还没有统一的方法。常用的核函数有径向基函数(Radial Basis Function，RBF)核、sigmoid核(sigmoid kernel)、多项式核(polynomial kernel)等。径向基函数核(也称RBF核、高斯核)是一种常用的核函数，其函数形式为

K(xi,xj)=e-γ‖xi-xj‖2

定义核函数之后，就可以按照核函数计算低维特征的协方差矩阵，记作ΣXKPCA。给定训练集样本特征矩阵

Xd×m=(x1,x2,…,xm)=x11x21…xm1
x12x22…xm2
︙︙︙
x1dx2d…xmd

将样本特征的每个特征项(Xd×m的每一行)看作一个随机变量Xk，k=1,2,…,d，特征随机变量的低维协方差矩阵ΣXKPCA为

ΣXKPCA=K(X1,X1)K(X1,X2)…K(X1,Xd)
K(X2,X1)K(X2,X2)…K(X2,Xd)
︙︙︙
K(Xd,X1)K(Xd,X2)…K(Xd,Xd)(373)

其中，K(Xk,Xl)=-1(Xk)·-1(Xl)，k,l=1,2,…,d。
KPCA将基于这个低维特征协方差矩阵ΣXKPCA进行降维，其后续算法步骤与PCA完全一样： 即先对ΣXKPCA做特征值分解，求出最优的特征投影方向，然后构造投影变换的转移矩阵W。需要注意的是，核函数K(xi,xj)应具有对称性，并使所构造的协方差矩阵ΣXKPCA为半正定，这样后续的特征值分解等算法步骤才能成立。

5. 使用scikitlearn库中的PCA降维模型
scikitlearn库将PCA、KPCA降维模型封装成类(类名分别为PCA和KernelPCA)，并将其存放在sklearn.decomposition模块中。PCA和KernelPCA类实现了降维模型的学习算法
fit()和降维转换算法transform()。
图325给出了使用PCA类进行特征降维，然后再使用逻辑斯谛回归分类器LogisticRegression建立并训练乳腺癌诊断模型的示例代码。其中数据集使用的是3.1.3节zscore标准化后的乳腺癌诊断数据集，先将数据集(X1_train、X1_test)从30维降到5维，查看这5个新特征的方差贡献率； 再使用降维后的5个特征训练模型，并对测试集X1_test前2个病例样本进行分类预测，将预测结果predict与Y_test中的真实诊断结果malignant进行比对，1表示恶性，0表示良性； 最后使用函数score()计算模型在训练集(X1_train、Y_train)和测试集(X1_test、Y_test)上的平均正确率。


图325使用PCA类进行特征降维，然后再使用逻辑斯谛回归分类器LogisticRegression

并建立乳腺癌诊断模型的示例代码



3.4.3线性判别分析
3.2.2节曾介绍过使用线性判别分析(LDA)解决二分类问题，其思路是先将高维特征投影到一维，然后基于一维特征来设计分类器。对于多分类问题，可以对高维特征做若干次投影，得到一组新特征，然后再设计分类器。LDA多次投影的过程实际上就是消除特征冗余，选择主要成分的降维过程，这与PCA非常类似。LDA既可作为分类器模型，也可作为降维模型。
PCA不考虑类别标注，其投影原则是将高维特征投影到协方差最小的方向。而LDA使用带类别标注的训练集，其投影原则是将高维特征投影到“类内方差最小，类间方差最大”的方向。PCA不考虑类别标注，属于无监督降维； 而LDA考虑类别标注，属于有监督降维。这是两者的根本区别，它们后续的投影原则及学习算法也因此有很大不同。

1. LDA降维算法
下面用数学方法来描述LDA选择最优投影方向ω的过程，整个过程分4步完成。给定训练集
Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi=(xi1,xi2,…,xid)是d维样本特征，yi∈{c1,c2,…,cN}是其对应的实际类别，共N个类别。假设训练集Dtrain中第k类样本有mk个，将其从数据集中拆分出来形成子集Dk，即

Dk={(x1,ck),(x2,ck),…,(xmk,ck)}，k=1,2,…,N

分别定义各类特征的均值μk和离散度(类似于协方差)矩阵Sk，

μk=1mk∑mki=1xi，Sk=∑mki=1(xi-μk)(xi-μk)T，k=1,2,…,N

再定义d维特征空间的类内离散度矩阵(withinclass scatter matrix)Sw，

Sw=∑Nk=1P(Y=ck)Sk=∑Nk=1mkmSk

和d维特征空间的类间离散度矩阵(betweenclass scatter matrix)Sb为

μ=1m∑mi=1xi，Sb=∑Nk=1mkm(μk-μ)(μk-μ)T

LDA最多可以做N-1次投影，并希望各投影方向ω都尽量让样本特征投影点“类内方差最小，类间方差最大”，因此构造如下优化目标:

maxW
WTSbWWTSwW，其中Wd×(N-1)=(ω1,ω2,…,ωN-1)

求解得SbW=λSwW。这是一个广义特征值问题(generalized eigenvalue problem)。
如果需要将d维样本特征降到d′维，则取S-1wSb的d′个最大广义特征值所对应的特征向量，将其作为行向量构造出投影变换的转移矩阵W。需要注意的是，假设有N个类别，原始样本特征为d维，则d′应满足： d′≤min(N-1,d)。

2. 使用scikitlearn库中的LDA降维模型
scikitlearn库将LDA的降维模型与分类模型合在一起，封装成同一个类(类名为LinearDiscriminantAnalysis)，并将其存放在sklearn.discriminant_analysis模块中。LinearDiscriminantAnalysis类实现了降维/分类器模型的学习算法fit()、降维转换算法transform()和预测算法predict()。
图326（a）给出了使用LinearDiscriminantAnalysis类对乳腺癌诊断数据集进行特征降维的示例代码。其中数据集使用的是3.1.3节标准化后的乳腺癌诊断数据集，将数据集(X1_train、X1_test)从30维降到1维(二分类问题只能被降到一维)； 然后使用散点图对其进行可视化(见图326（b）)。




图326使用LinearDiscriminantAnalysis类对乳腺癌诊断数据集进行特征降维



3.4.4非线性降维

PCA和LDA降维使用线性变换，将低维特征表示成高维特征的线性组合，这属于线性降维。线性降维的核心思想是降维时尽可能保持高维特征的方差或类间方差，以便下一步进行回归或分类。而某些降维问题则希望降维时能尽量保持样本在高维空间的
某种低维
分布结构，以便下一步进行可视化与数据分析。通常，高维数据必须降到二维或三维才便于可视化。
给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，或Dtrain={x1,x2,…,xm}，其中xi是d维样本特征，构造训练集特征矩阵X为

Xd×m=(x1,x2,…,xm)=x11x21…xm1
x12x22…xm2
︙︙︙
x1dx2d…xmd

其中的每一列对应一个样本数据xi，i=1,2,…,m。


图327样本在高维空间的

分布结构

现在希望将d维样本特征xi(高维特征)降到d′维样本特征zi(低维特征，d′≤d)，降维时能保持样本在高维空间的
某种低维
分布结构(参见图327中沿S形结构分布的4个样本点)。所保持的分布结构可以是样本间的距离(例如图327中x1与其他样本点之间的直线距离或曲线距离)，或样本间的局部线性关系(例如图327中x1与x2、x3在局部近似具有线性关系)，或样本的局部概率分布等。
降维后让低维特征继续保持样本的分布结构，这就需要使用非线性降维方法，而且保持不同分布结构需要不同的降维模型与算法。

1. MDS——保持样本间欧氏距离
多维缩放(Multiple Dimensional Scaling，MDS)降维，就是降维后低维空间中样本点之间的欧氏距离(Euclidean distance)与高维空间保持一致。
首先根据训练集特征矩阵X，计算高维空间的距离矩阵D，

Dm×m=dist11dist12…dist1m
dist21dist22…dist2m
︙︙︙
distm1distm2…distmm(374)

其中，distij为样本点xi与xj之间的欧氏距离： distij=‖xi-xj‖2，i,j=1,2,…,m。
假设MDS降维后，高维空间样本点xi被转换为低维(d′维)空间的zi，则低维特征矩阵Z为

Zd′×m=(z1,z2,…,zm)=z11z21…zm1
z12z22…zm2
︙︙︙
z1d′z2d′…zmd′
(375)


其中的每一列对应一个低维样本数据zi，i=1,2,…,m。再构造低维特征矩阵Z的样本内积矩阵，

Bm×m=(Zd′×m)TZd′×m=zT1
zT2
︙
zTm(z1,z2,…,zm)=zT1z1zT1z2…zT1zm
zT2z1zT2z2…zT2zm
︙︙︙
zTmz1zTmz2…zTmzm(376)

依据定理34，样本内积矩阵B是m×m实对称半正定矩阵。这里注意样本内积矩阵与协方差矩阵(特征的内积矩阵)的区别。
因为MDS降维后，低维空间中样本点zi与zj之间的欧氏距离‖zi-zj‖2与其在高维空间中的欧氏距离distij一致，所以

‖zi-zj‖22=zTizi+zTjzj-2zTizj=dist2ij(377)

不失一般性，令降维后各低维特征项均被去中心化，即低维特征矩阵Z每行元素的均值为0，则其累加和也为0，∑mi=1zik=0，k=1,2,…,d′，由式（376）、式（377）可推导出

zTizj=-12dist2ij-1m∑mk=1dist2ik-1m∑mk=1dist2kj+1m2∑mk=1∑ml=1dist2kl(378)

式（378）表明， MDS通过降维前后距离矩阵D保持不变即可求得低维特征的样本内积矩阵B。下面再通过矩阵B求解低维特征矩阵Z。
样本内积矩阵B是m×m实对称半正定矩阵，因此对B进行特征值分解可得

B=UDUT(379)

其中，D=diag(λ1,λ2,…,λm)为特征值构造的对角矩阵，且λ1≥λ2≥…≥λm≥0，U=(u1,u2,…,um)是由特征值对应的单位特征向量所构成的正交矩阵。式（379）可展开为

Bm×m=(u1,u2,…,um)λ1
λ2

λmuT1
uT2
︙
uTm
=λ1u1uT1+λ2u2uT2+…+λmumuTm

可以看出，特征值为零的项可直接丢弃，特征值小的项对样本内积矩阵Bm×m的影响也比较小。如需降到d′维，则保留前d′个最大特征值及其对应的特征向量： 

B′m×m=(u1,u2,…,ud′)λ1
λ2

λd′uT1
uT2
︙
uTd′≈Bm×m

令 U′m×d′=(u1,u2,…,ud′)，D′d′×d′=diag(λ1,λ2,…,λd′)，则

B′m×m=U′m×d′(D′d′×d′D′d′×d′)(U′m×d′)T=(U′m×d′D′d′×d′)(U′m×d′D′d′×d′)T

又

B′m×m≈Bm×m=(Z
d′×m)TZd′×m

则降到d′维后的低维特征矩阵近似为

Zd′×m=(U′m×d′D′d′×d′)T=D′d′×d′(U′m×d′)T(380)

矩阵Zd′×m的列向量zi就是
高维特征xi经
MDS降维后的低维特征，i=1,2,…,m。

2. 流形降维方法
如果高维空间的样本特征具有某种分布结构，例如特征分布在某个低维曲线或曲面上，这时度量样本点距离就不能用欧氏距离(即直线距离，参见图327)，而应改用非欧形式的距离，例如曲线距离或曲面上的测地距离(geodesic distance)。如何计算高维特征空间中的非欧距离呢？
机器学习借鉴了数学和物理学中流形(manifold)的概念，认为高维特征空间虽然整体上与欧氏空间不同，但局部仍具有欧氏空间的性质。流形就是局部具有欧氏空间性质的空间，术语称这样的空间在局部与欧氏空间“同胚”。可以借助流形的思想，在降维时尽量保持样本在高维空间的局部结构，使得降维后对低维数据进行可视化时能观察到这些结构。
1) Isomap
给定训练集Dtrain={(x1,y1),(x2,y2),…,(xm,ym)}，或Dtrain={x1,x2,…,xm}，其中xi是d维样本特征。借助流形的思想，可以在每个样本点xi的邻域内利用欧氏距离找出其k个近邻样本，为样本集建立起一个邻接图(或邻接矩阵)。邻接图上的每个顶点对应一个样本点，边表示两个顶点间存在邻接关系，其权重则表示这两个邻接点之间的欧氏距离。将图上顶点之间的最短路径作为样本点间的
非欧
距离，这样就把非欧距离的计算问题转换为一个求最短路径问题，可以使用图论算法(例如Dijkstra算法)进行求解。
利用上述方法，最终可求得高维特征空间的距离矩阵D。有了距离矩阵D，下一步就可以使用MDS降维方法将d维样本特征降到d′维，d′≤d。这种借助流形求解距离矩阵，然后进行降维的方法被称为等度量映射(Isometric Mapping，Isomap)。

2) LLE和SNE
高维空间的样本特征具有某种分布结构，可以将这种分布结构看作被嵌入高维空间的低维结构，降维时应当予以保持。“分布结构”可以用样本点之间的“距离”来描述，例如MDS、Isomap认为降维时应当保持“距离”，也可以使用其他概念来描述这种分布结构。
如果使用样本点之间的“线性关系”来描述分布结构，则降维时应尽量保持这种线性关系，由此就产生了局部线性嵌入(Locally Linear Embedding，LLE)降维方法。假设原始d维样本点xi可以表示成其k个近邻点的线性组合(参见图327)，

xi=ωi1x1+ωi2x2+…+ωikxk

LLE将d维样本特征降到d′维(d′≤d)后，希望所对应的低维特征点zi能尽量保持这种线性关系，即

zi=ωi1z1+ωi2z2+…+ωikzk

采用LLE降维，低维特征zi能尽量保持其高维特征xi存在的线性关系(即分布结构)。可视化低维特征zi(通常取二维或三维)，就能看到其高维特征xi的分布结构，这非常有利于数据的分析。
也可以使用样本点之间的“条件概率”来描述分布结构，降维时尽量保持这种概率分布，由此就产生了随机近邻嵌入(Stochastic Neighbor Embedding，SNE)降维方法。假设将样本点看作随机变量，原始d维样本点xi邻域内近邻点xk出现的条件概率p(xk|xi)服从高斯分布。SNE将d维样本特征降到d′(d′≤d)维后，希望所对应的低维特征点zi能尽量保持这种概率分布，即

p(zk|zi)=p(xk|xi)

如果将低维空间概率分布p(zk|zi)由高斯分布改为t分布，则这样的SNE就被称为tSNE。

3. 使用scikitlearn库中的非线性降维模型
scikitlearn库将常用的非线性降维模型封装成类，并将它们集中存放在sklearn.manifold模块中，其中包括MDS、Isomap、LocallyLinearEmbedding和TSNE，共4个类。这些类都实现了降维模型的学习算法
fit()和降维转换算法transform()。
图328（a）给出了使用MDS类对乳腺癌诊断数据集进行特征降维的示例代码。其中，数据集使用的是3.1.2节加载的原始乳腺癌诊断数据集，将其从30维降到2维； 然后使用散点图进行可视化(见图328（b）)，其中benign表示良性，malignant表示恶性。


图328使用MDS类对乳腺癌诊断数据集进行特征降维


3.5本章习题
一、 单选题
1. 下列关于分类问题的描述中，错误的是()。

A.  给定样本特征，将其划归某一类别，这就是分类问题，或称为识别问题
B. 分类问题必须基于特征的概率分布建立判别函数
C.  机器学习将分类所用的判别函数称作分类器
D.  贝叶斯决策是统计决策中解决分类问题的基本方法
2. 在已知概率分布的情况下，分类错误率最小的分类器是()。
A.  贝叶斯  B. 朴素贝叶斯  
C. k近邻  D. 决策树
3. 给定特征X，贝叶斯决策是基于下列概率中的()最大来判定类别Y的。
A.  P(X)  B. P(Y)  
C. P(X|Y)  D. P(Y|X)
4. 下列关于朴素贝叶斯的描述中，错误的是()。
A.  朴素贝叶斯是针对高维特征联合概率分布难以估计问题而提出的
B. 朴素贝叶斯假设各特征项之间相互独立
C.  朴素贝叶斯假设各特征项与类别之间相互独立
D.  设计朴素贝叶斯分类器需估计给定类别条件下各特征项的概率分布
5. 给定类别Y，如果特征X有3个不同选项，则P(X|Y)服从下列概率分布中的()。
A.  01分布  B. 伯努利分布
C. 多项分布  D. 高斯分布
6. 下列关于牛顿法的描述中，错误的是()。
A.  牛顿法是一种数值迭代算法
B. 应用牛顿法的一个前提条件是目标函数二阶可导
C.  牛顿法利用二阶导数确定下一迭代点的搜索方向
D.  牛顿法的收敛速度比梯度下降法快
7. 将逻辑斯蒂回归应用于多分类，其后验概率的函数形式为()。
A.  logistic函数  B. softmax函数
C. sigmoid函数  D. Gaussian函数
8. 下列关于k近邻分类器的描述中，错误的是()。
A.  k近邻分类器直接基于训练集实例进行分类，没有显式的学习过程
B. 给定新样本x，k近邻分类器会查找训练集中的k个最近邻并统计它们的类别
C. k近邻分类器采用简单多数表决规则判定新样本的类别
D.  k近邻分类器必须使用欧氏距离来度量样本点间的相似度
9. 下列关于线性判别分析的描述中，错误的是()。
A.  对于二分类问题，线性判别分析的核心思想是设法将高维特征压缩至一维
B. 线性判别分析选择投影方向的标准是“类内方差最大，类间方差最小”
C. 线性判别分析在将高维特征压缩到一维之后再基于一维特征设计分类器
D.  线性判别分析更多地用于特征降维
10. 下列关于决策树分类器的描述中，错误的是()。

A.  决策树分类器按照特征有效性，先使用主要特征，后使用次要特征
B. 决策树的分类决策过程分多步完成，每步选用一个特征项
C. 决策树选择特征项的标准是“所划分子集纯度越高，则特征项越有效”
D.  使用训练集建立决策树的过程是一个演绎推理的过程
11. 决策树模型的3种特征选择准则中不包括()。
A.  ID3  B. C4.5  
C. CARTD. MSE
12. 二分类模型的评价指标中不包括()。
A.  正确率  B. 精确率  
C. 召回率D. R方
13. 设Ud×d为正交矩阵，则下列等式不成立的是()。
A.  U=UT  B. U-1=UT  
C. UTU=ID. UUT=I
14. 下列方法中属于线性特征降维方法的是()。
A.  主成分分析B. 等度量映射
C. 局部线性嵌入D. 多维缩放
15. 下列降维方法中能够保证降维后样本点之间的欧氏距离不变的是()。
A.  主成分分析B. 等度量映射
C. 局部线性嵌入D. 多维缩放

二、 讨论题

1. 假设，记表31中的分类特征“底色”为X，分类目标“品种”为Y，根据表31的样本数据分别计算特征概率分布P(X)、类别概率分布P(Y)、特征条件概率P(X|Y)，然后使用贝叶斯公式计算出类别条件概率P(Y|X)。
2. 假设表31中的分类特征“底色”“口感”相互独立且分别记为X1和X2，再记分类目标“品种”为Y，根据表31的样本数据计算特征条件概率P(X1,X2|Y)。
3. 假设随机变量X服从正态分布，给定样本数据集{x1,x2,…,xn}，使用极大似然估计求解其均值μ和方差σ2。
4. 如果一元函数f(x)二阶可导，则可使用牛顿法求解其极值点，试推导其第k次迭代时xk-1到xk的迭代公式。
5. 给定样本数据集D={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi是d维样本特征，试写出样本特征的协方差矩阵。
6. 什么是矩阵的特征值、奇异值，并简述它们的应用。

三、 编程实践题
使用scikitlearn库提供的鸢尾花数据集(iris plants dataset)设计一个逻辑斯蒂回归分类器。具体的实验步骤如下。
(1) 使用函数sklearn.datasets.load_iris()加载鸢尾花数据集； 
(2) 查看数据集说明(https://scikitlearn.org/stable/datasets/toy_dataset.html#irisdataset)，并对数据集进行必要的预处理； 
(3) 使用函数sklearn.model_selection.train_test_split()将数据集按8:2的比例拆分成训练集和测试集； 
(4) 使用sklearn.linear_mode.LogisticRegression类建立逻辑斯蒂回归模型，并使用训练集进行训练； 
(5) 分别计算模型在训练集和测试集上的平均正确率。