2022机器学习公式详解

机器学习公式详解

第［章绪论

2第2章霞型评估与选择

3第3章线性模型

4第4章决策树

5第5章神经网络

6第6章支持向量机

7第7章贝叶斯分类器

8第8章集成学习

9第9章聚类

第10章‘降维与度量学习

0

1第II章特征选择与稀疏学习

2第12章计算学习理论

3第13章半监督学习

4第14章概率图模型

5第15章规则学习

6第16章强化学习

第1章绪论

式(1.1)

电「ZX『㈤坳3"/㈤)PS|X£)

AafX-X

参见式(1.2)

式(1.2)

E"⑸叫工)“㈤)P(A|X£)

/，A■3片①

-E晔)£P(A|X£)EI(MZ)"(N))

■di/②

=XP㈤，P(?||X£)；/三

rfXXA③

*£P㈤£W£)

"Y-fh④

■/・】TP㈤.i

4V⑤

③■⑥显然成立

解析

。■②

EEE玳(“)加(川xfj

/*uex-x

-Ep㈤xz>g)"g))pwx£)

u^X-X/A

=£p㈤£p(川XCJEKMMW/H)

MTTh1

②T③：首先要知道此时我们假设J是任何能将样本映射到｛01｝的函数.存在不止一个了

时，/服从均匀分布，即每个/出现的概率相等.例如样本空间只有两个样本时，

*=即项｝.|川=2.那么所有可能的真实目标函数孜口下,

人：/乂对）-o=1；

A:gJ-】JJ（如）-比

/<-A（Hl）-1J，*2）n1.

一共2田=少=4个可能的其实目标函数，所以此时通过算法£n学习出来的模型h（0对每个样

本无论预测值为0还是1，都必然有一半的/与之预测值相等，例如，现在学出来的模型川工；

对N1的预测值为1，即“数）=】，那么有且只有人和人与科蜥预测值相等，也就是有且只

£1（加0W加））=轲

有一半的/与它预测值相等，所以/2.

值得一提的是，在这里我们假设真实的目标函数f服从均匀分布，但是实际情形并非如

此，通常我们只认为能高度拟合已有样本数据的函数才是真实目标函数，例如，现在已有

的样本数据为｛1工小）<i'）,那么此时为才是我们认为的真实目标函数，由于没有收集到

或者压根不存在他MM◎⑷h伍|」）,」工人机这类样本,所以九加人都不

算是真实目标函数.这也就是“西瓜书”式（1.3）下面的第3段中“骑自行车”的例子所想表达的

内容.

第2章模型评估与选择

式(2.20)

।m-l

AUC■--1|),(防+沥+1)

isl

解析

在解释AUC式之前，需要先弄清楚RCC曲线的具体绘制过程.下面我们就举个例子，按

照“西瓜书”图2.4下方给出的绘制方法来讲解一下RCK曲线的具体绘制过程.

假设我们己经训练得到一个学习器〃*现在用该学习器来对8个洌试样本(4个正例，4

个反例，即m+=m-=4)进行预测，预测结果为：

(fl,0.77,+),(«2,0.62,-),(«3,0.58,+),(«,0.47,f)

(q047.-).(即,0.33,-)Jr,0.23,+)

此处用■表示样本，以和坐标(£”)作出区分

其中，，和一分别表示样本为正例和为反例，数字表示学习器/预测该样本为正例的概率，

例如对于反例的来说，当前学习器/(•)预测它是正例的概率为。叔.

上面给出的预测结果已经按照预测值从大到小排序

根据“西瓜书”上给出的绘制方法，首先需要对所有测试样本按照学习器给出的预测结果进

行排序，接着将分类阈值设为一个不可能取到的最大值.显然，此时所有样本预测为正例

的概率都一定小于分类阈值，那么预测为正例的样本个数为0,相应的真正例率和假正例

率也都为0,所以我们可以在坐标Q0：处标记一个点.接下来需要把分类阈值从大到小依次

设为每个样本的预测值，也就是依次设为0.77,0.62,0.58,0.47,0.33,0.23,0.15,然后分别计

算真正例率和假正例率，再在相应的坐标上标记点，最后再将各个点用直线连接，即可得

到RCC曲线.需要注意的是，在统计预测结果时，预测值等于分类阈值的样本也被算作预

测为正例.例如，当分类阈值为n77时，测试样本d减预测为正例，由于它的真实标记也

是正例，所以此时是一个真正例.为了便于绘图，我们将工轴(假壬例率轴)的“步长”定

11

为不,y轴(真正例率轴)的“步长”定为二三根据真正例率和假正例率的定义可知，每次

t

变动分类阈值时，若新增，个假正例，那么相应的工轴坐标也就增加白；若新增J个真正

1

例，那么相应的y轴坐标也就增加嬴.按照以上讲述的绘制流程，最终我们可以绘制出如

图2“所示的KOC曲线.

图2-1ROC曲线示意

注：表示红色线段；表示蓝色线段；_____表示绿色线段

在这里，为了能在解析式（2.21）时复用此图，我们没有写上具体的数值，转而用其数学符

号代替.其中绿色线段表示在分类阈值变动的过程中只新增了真正例，红色线段表示只新

增了假正例，蓝色线段表示既新增了真正例也新增了假正例.根据AUC值的定义可知，此

时的AUC值其实就是所有红色线段和蓝色线段与了轴围成的面积之和.观察图2“可知，红色

线段与了轴围成的图形恒为矩形，盛色线段与了轴围成的图形恒为梯形.由于梯形面积式既

能算梯形面积，也能算矩形面积，所以无论是红色线段还是蓝色线段，其与工轴围成的面

积都能用梯形公式来计算：

5（力+1一备）•（弘+弘+1）

其中，（31-xJ为“高力明为“上底”，阱n为吓底”.那么对所有红色线段和蓝色线段与工轴

围成的面积进行求和，则有

£丁（g-加版+/+i）

tsi

此即AUC

式（2.21）

J=<EX（WQ）<，所））+；W（6"（O）

解析

按照我们上述对式（2.20）的解析思路，，一■可以看作是所有绿色线段和蓝色线段与期轴闱成

的面积之和，但从式Q.21）中很难一眼看出其面积的具体计算方式，因此我们进行恒等变

形如下：

J-＜/（«*））+^（/（»*）-/（»-））]

bwIMbWD*',

£[Ei（/①）＜/（=-））+：,£W（N+）=/（N-））

=E!!Ews*）＜/（工，））+

•♦UE•-vn-

E【（/—）

a~cD~・

=E5*L【（"）＜”­））+

＞-«o-

w

2Ei（"）■/"））

・一£11-

在变动分类阈值的过程当中，如果有新增真正例，那么图2-1就会相应地增加一条绿色线

E

段或蓝色线段，所以上式中的面看可以看作是在累加所有绿色和蓝色线段，相应地，

・21后面的内容便是在求绿色线段或者蓝色线段与“轴围成的面积，即；

EW（力＜/所））十5E“/（”♦）-））.

I"1-mJ/m

•~wD-u~^D~

与式（2.20）中的求解思路相同，不论是绿色线段还是蓝色线段，其与y轴围成的图,面积都

可以用梯形公式来进行计算，所以上式表示的依旧是一个梯形的面积公式.其中薪即梯形

的“高”，中括号内便是“上底+下底"，下面我们来分别推导一下“上底（较短的底）和“下

底”（较长的底）.

由于在绘制ROC曲线的过程中，每新增一个假正例时“坐标也就新增一个步长，所以对于

1

“上底”，也就是绿色或者蓝色线段的下端点到轴的距离，长度就等于U乘以预测值大于

〃工十）的假正例的个数，即

*£1（/（«+）＜/（«■））；

而对于“下底”，长度就等于二7乘以预测值大于等于/（的假正例的个数，即

5(E</(«-))+£i(/(^)=/(z-))Y

\r^D~.FD*/

式(2.27)

€=max€s.t.Z(mj?(l-€)**■*<a

iatnxm-1*!'/

解析

截至2018年12月“西瓜书”第1版第30次印刷，式(2.27)应当勘误为

e=mine&.t.£—CQ)"*-*<a

jm‘l'''

具体推导过程如下：由“西瓜书”中的上下文可知，对,<a进行假设检验，等价于本章附

注中所述的对D4为进行假设检验，所以在“西瓜书”中求解最大错误率7等价于在附注中求

-

解事件最大发生频率/由附注可知

C=minCa.t.(：)/f

Mt7-F1'/

所以

C.C

—=mm-8.1£就i尸

mm

Qc

将上式中的UI,四等价替换为^工内可得

e=mineM.g。)点1■4尸,(。

式⑵41)

川:=E[(/(x：r

D)nD)-yr))①

=ED[(/(?：〃)-f(x)+/(z)-yp)2②

2

=E0[(/(Z;D)-/(X))]+ED[(加)-㈤’卜

ED[2(/(X:D)-/(»))(/(x)-yD)③

=M[(/(z;D)一/㈤丹+Ep[(/(a)-如)’④

"ED"3；D)-施)丹+即[(『㈤-y+y-㈤’⑤

=%[(/(瓯D)-/(*)丹+%[(/(«)-^+坳仙-加丹+

2即[l/(x|-j/ily-yi)\⑥

-%f(/(x；。)-加冈+(/(z)r户+E。Ryp-y)r⑦

g②：减一个fW再加一个f(创，属于简单的恒等变形

同①③一样，减一个瓯加一个4属于简单的恒等变形

同②珊一样，将最后一项利用期望的运算性质进行展开

解析

M)：首先将中括号内的式子展开，有

%[(/(»；。)一祠)，(/M-to)1+2(a；D)一施))(祠一⑹],

然后根据期望的运算性质EA-ME[A1+E]可将上式化为

4[(/(»;D)-词)]+%[(祠-即)1+

E,[2(〃室0-/(力)(/㈤一⑹].

③草：再次利用期望的运算性质将第3步得到的式子的最后一项展开，有

%[2(f(x;D)-/(»))(/(»)-FD)1

■ED【2(〃室D)-/(«))-/(z)]一ED|2(/(Z;D)-/(«))yn]

首先计算展开后得到的第1项，有

%[2{/(z;D)-/{z))./(«)]-ED固□0・加)・2津)・/(«)].

由于f(z)是常量，所以由期望的运算性质：用.4工+8]匚.4£：川+3(其中43均为常量)

可得

ED[2(/(Z;D)-/(Z))-/(1)]=2/(X)-ED(/(«；0)-2/(力/(«).

由式(2.37)可知E/>MHD)]/㈤,所以

Ep[2(/t：〃)-fix)).〃■)]=2/(z)-八0一2/(z)•f(s)=0

接着计算展开后得到的第二项

%[2(/(*;。)-/(«))•yo\=2Ep[/(mD)-yp]-2f(x)-即加],

由于噪声和/无关，所以/”；0和如是两个相互独立的随机变量.根据期望的运算性质

EA*]E[F|(其中m口讷相互独立的随机变量)可得

/[2(/(*；。)■加))，㈤■塞D[/,；0,沏]-2/(1).%\gD

■2Epf/(«:0)1•ED加-2/(工)•ED\UD

■2/(®)-EDfirol-2f(x)・EDM

=0

所以

ED[2(/(z;D)-/(z)){/(z}.yD)]

=ED[2(/(Z;O)-*))・-ED[2(/(幽D)-f(x))•耐

■O+Q

K0

⑥T⑦：因为44和眼为常量，根据期望的运算性质，有⑥中的第2项

En[(/(«)-y)2]=(/(工)y)J

同理有⑥中的最后一项

2ED[(f(x)-1/)(y->D)]=2(，㈤一y)%(y-㈤,

由于此时假定噪声的期望为零，即3)以-*)]・Q所以

2E0[(/(x)-y)(y-VD)]-2(/(x)-y)-0=0.

附注

二项分布参数m勺检验[1]

设某事件发生的概率为P,以未知.做m次独立试验，每次观察该事件是否发生，以*记该事

件发生的次数，则X服从二项分布现根据X检验如下假设：

%：P4国；

Hi：p>内.

由二项分布本身的特性可知；P越小，独到较小值的概率越大,因此，对于上述假设，一

个直观上合理的检验为

9:"£C时接飘否则就拒绝仇

其中，表示事件最大发生次数.此检验对应的功效函数为

flr（p）-P（X>C7）

-1-P（X<C）

由于“礴小，x取到较小值的概率越大”可以等价表示为：p（x&a是关于成勺减函数，所

以内⑵=p（x>c）=I-PZW。是关于『的增函数，那么当pSR时，43）即％（P）的上

确界.乂根据参考文献［1］中5.1.3的定义1.2可知，检验水平C默认取最小可能的水平，所以

在给定检验水平n时，可以通过如下方程解得满足检验水平c的整数C：

更为严格的数学证明参见参考文献［1］中第二章习题7

。=sup{a（p）}

显然，当P《肉时有

a-=»up{flr（P））

■4佃）

对于此方程，通常不一定正好解得一个使得方程成立的整数G较常见的情况是存在这样

一个「使得

Z（：）'（"例广<0

|“.1'7;

£（:）月（1-闯

此时，Q只能取6或者⑦+1.若C取值则相当于升高了检验水平m若。取。/】则相当于降

低了检验水平n.具体如何取舍需要结合实际情况，但是通常为了减小犯第一类错误的概

率，会倾向于令Q取0+1.

下面考虑如何求解日易证九&：是关于。的减函数，再结合上述关于「的两个不等式易推得

C=minCB.t.£（：）/4（"内广<。

iaC41'）

参考文献

u陈希孺.概率论与数理统计[M].合肥：中国科学技术大学出版社,2009.

第3章线性模型

式(3.5)

=2卜~£包-%

解析

HI

&“剧=5^E-wbY

己知£,所以

=2《瓜・叫・/

1x1

m

=£【2・3,一Mi,—6)・(一引

-I

m

■£R・(iwf-y,Ti+bii)

isl

=2,+bgj

\JiI»1J

=2-EM-卜)片)

VUI/

式(3.6)

凄^=2卜_£(*-叼“

解析

m

&“)=V(/一鼠小一W

已知X,所以

叫“）d/

-^一二丽［之（/_蚂_8）

—柄

isl

m

=£口（如一11%—6）・（一1）］

£1

m

-|2•（6-%

t=i

IRmm\

2»-£防+22叫）

（JIi-lI/

=2（"力-4（阶・Wi））

式（3.7）

E以勺-£)

解析

令式（3.5）等于Q有

wim

0=-b）Ti,

xi1

Ii=i

］*ImIni

b=一力协-叫）-工如=§-52A=j

由于令式（3.6）等于0可得‘"X,又因为r"X且用X,则

b=i-wir代入上式可得

mm■

如£4=Eg-E®-喙）孙

f=li=lt=l

wSi?=Ev*ii-*Ex<+,DiSxi'

T山£1日

i-l/i-1

将咚E”急唔m"・空65?—1/（5?）代入上式,即可

得式（3.7）：

£班（美-了）

":*!尉

如果要想用Python来实现上式的话，上式中的求和运算只能用循环来实现.但是如果能将

上式向量化，也就是转换成矩阵（即向量）运算的话，我们就可以利用诸如NumPy这种

专门加速矩阵运算的类库来进行编写.下面我们就尝试将上式进行向量化.

1住J=心

将mJM代入分母可得

X航旭一工）

w=上___________

一1日

m

£仅内■旅£）

£（才-取）

mmmmm

又因为占M占M£r且

HlHl.*FT1

£［（明’二钏土一石』十邛）

三.田-甲一琼十日

比1（孙一万（物一。

・仁«一尸

若令…工,|=(八一『」2一元…"m-TP为去均值后的.；

1/三旧卜他,…』n)L山■(班一仄假一仄…必一VF为去均值后的“，代入上式可得

“、R0加为彳而列的列向量

"一乖d

式(3.10)

—-2X1(Xw-v)

ikw

解析

将/*51V-XwlT(yX5展开可得

心=vrv-KTXW-wTXTy+wTXTXw

对溢导可得

gd守vdy^xwdwTxTva»Txrxw

------+

iiw[hisdwdw-------------dw

=0-XTV-Xvy.(XTX+XTX)让

=2XT(XW-V)

TTT

daxdxadxAr..mT.

矩阵微分式F1=H=aF-=(4+A注

式(327)

m

，(向-E(-y0Z♦In(l+」"))

解析

将式(3.26)代入式(3.25)可得

m

。伯)=£In(y(Pi(加汗)+(1-川内(加《)).

其中川•,冽=闯卬加百，代入上式可得

■

由于眸0或1,则

I工卜编・卜(1*/'))…・1

两式综合可得

«同=玄(心-、("")》

4=1

由于此式仍为极大似然估计的似然函数，所以最大化似然函数等价于最小化似然函数的相

反数，即在似然函数前添加负号即可得式(3.27).值得一提的是，若将式(3.26)改写为

pGgw,b)-佃他⑶声优偈⑶)F再代入式(3.25河得

，同=(佃(如向).佃国创F)

ui

m

・£伍b(ft(据；例)+(1-喻卜(ft(A；砌)

t=t

m

=£(M伽(pi(,；例)-1n3(却削)十必佃(为;再)))

«=1

整m(㈱)+2⑼)

=能(产)+、($))

・£G0T,Tn(1+4*))

tsi

显然，此种方式更易推导出式(3.27).

式(3.30)

叩t=l

解析

此式可以进行向量化.令九一阴(以3),代入上式得

鬻=一£着3一鲍

=-加

t=l

=XT(ir-v)

XT(PI(X;3)-V)

式(3.32)

J=973-(冏--J"

gT(Eo+Ei)w

解析

IM%—-洲

WT(ED+Ei)v

卜打一办尸[；

WT(£O+£I)W

WT(EO+EI)W

W]W

wT(lb^EI)W

=—31火｝31一11)/卬

wr(Sn+Si)w

式(3.37)

ShW=ASWU!

解析

由式(3.36),可定义拉格朗日函数为

£(w.A)=-wTSiw+A(WTSU.W-1)

对靠求偏导可得

8L(wN_d(wlS^w)d(wlS^w-l)

dwDw+加

■■(S'+S；)w+A(Sr+s1)u.

=2ShW♦24Su3.

这是由于S»・S]、§・■s]

令上式等于。即可得

—2S^w+2XSvw=0

Skw=ASwt£

由于我们想要求解的只有tn而拉格朗日乘子退体取值多少都无叶谓，因此可以任意设

定】来配合我们求解WI注意到

s6s=(外一加乂/一"尸吗

如果我们令人=(出一出)T叫那么上式即可改写为

S加=*四|一

将其代入与"，=AS"即可解得

式(3.38)

S6w=At/io-pJ

参见式(3.37)

式(339)

小=$丁(视一⑸

参见式(3.37)

式(3.43)

Sb=St—sw

N

■£mi3-㈤飙一〃尸

i=i

解析

由式(3.40)、式(3.41)、式(3.42)可得：

Sh=S.■S.

■N

■£（%—〃）（s—一££g—闻（方一间'

tai・£晨

=£@3(g-w-NT-g■闻g-W))

£(!>-")①-冏—-川，田)]

♦IJx,/

-E(E(«T_-M«T+M+*+Ml/—/MG

=£(Z(T“T一心T+"+*P?+3,-件后))

•->1IwX,/

=£(-gw，-EH+E3+

*wk/

N

-£-四川十朝〃，丁+仙"/丁+四i：-mgg

t=l

!9

-£(-mg"，-+2/1，fm/流

i=l

=£m,(-四〃T-M+M+

t=!

N

式(3.44)

tr(lVTS3V)

炉HWEW)

解析

此式是式（3.35）的推广形式，证明如下.

设卬・1吗叫…工，,.….心「）—'"-1）,其中犯€片对为d行1列的列向量，则

/»-i

T

tr(lVS^)=£w7Skvb

NT

U(WTS9W)=EW[SM，

所以式(3.44)可变形为

IN-\

E⑼

a4=1

------

£B「S■皿

t=i

对比式(3.35)易知，上式即式(3.35)的推广形式.

式(3.45)

SkW=AS.H

解析

同式(3.35),此处也固定式(3.44)的分母为1,那么式(3.44)此时等价于如下优化问题

但-3例丁$网

根据拉格朗日乘子法，可定义上述优化问题的拉格朗日函数

"W内=-EMSM+MEMS」W)-"

根据矩阵微分式近"(XTBX)■(,+小)*对上式关于哪偏导可得

dUW,A)a(tr(WT®w))“tr(WT&W)-1)

aw-=aiv1-w

=-⑸+怨)IV+入⑸,+S：)W

=-2SM，2XSwW.

这是由丁S>・S；且s.・s!

令上式等于0即可得

-2SbW+2XSwW-0

SKW=ASgW

第4章决策树

式(4.1)

必

Em(D)-㈱如2PA

&=i

解析

下面证明DgEnt(D)＜：log.\y.

已知集合成信息嫡的定义为

Eht(D)--汇以丘2跺

n

oc^ci.yP*=I

其中，»悭示样本类别总数，%表示第&类样本所占的比例，有占.若令

卜1=儿内=%那么信息嫡Eut(D)就可以看作一个n元实值函数，即

n

Ent(。)=/(町,…：4)=■£n1。&5

4=1

ra

其中上.

下面考虑求该多元函数的最值.首先我们先来求最大值，如果不考虑约束0404】而仅考

n

虑g"=\则对/(〃「・,力求最大值等价于如下最小化问题；

n

minnlog2q

1=1

M

=i

k=i

显然，在时，此问题为凸优化问题.对于凸优化问题来说，使其拉格朗日函数的

一阶偏导数等于0的点即最优解.根据拉格朗日乘子法可知，该优化问题的拉格朗日函数为

以工匕…,、闾=£工*M4+入

\k=lJ

其中，1为拉格朗日乘子.对〃内,…,RZ分别关于力,…,求一阶偏导数，并令偏导数

等于o可得

^^耀—八信旬卜

=啕孙+町-+A=0

flInJ

=1°副《H+—+A=C

2In2

/F唱后…一(ET卜。

孙%£工』*+延时1)]=。

、11

a(m=。

n2"=1.

整理一下可得

A»-logjJi-白』一坳益・白=…=-106axm-占,

以一

(I

由以上两个方程可以解得

1

M1T~・・=3一

又因为△还需满足约束1，显然所以〃=及=…=是满足所有

约束的坡优解，即当］前最小化问题的最小值点，同时也是/（孙…,G:的最大值点.将

"=灯=…=J='代入〃工）中可得

/=■尸［厄的』=-n'-iog2-=1。的“

\nn/j-jnnnn

R

ow=i

所以/Gi「・在满足约束£时的最大值为路外.

52n=1

下面求最小值.如果不考虑约束M而仅考虑。（口（L则〃及「,•7）可以看作〃个

互不相关的一元函数的和，即

/（了2・・,北）

1-1

其中，g（川―一川。5〃,08nSL那么当加川屈丁。….巾；）分别取到其最小值时，

/（0,・・・4）也就取到了最小值.所以接下来考虑分别求…，仙”各自的最小

值，由于。，的定义域和函数表达式均相同，所以只需求出d&）的最小值

也就求出了"冲），…，的最小值.下面考虑求“方）的最小值，首先对“了1次于孙求一阶

和二阶导数，有

Ji\d{fk<E）t____1,_1

*'=-须・册=-g工LR

显然，当04口41时门"）=一亚恒小于0,所以十5）是一个在其定义域范围内开口向

下的凹函数，那么其最小值必然在边界取.分别取打=。和h=1,代入4方）可得

计算信息熠时约定：若*°Q，则£嘀/=。

g（0）=—0logo0=0

y（0=-1logjl=0

所以，*1）的最小值为0,同理可得“物），…屈小）的最小值也都为0,即〃九…H）的最

小值为o.但是，此时仅考虑约束0（打《］，而未考虑M.若考虑约束X,那

么〃的最小值一定大于等于0.如果令某个“二L那么强据约束X可知

f|s1*］S***sJT*_］=1*141=….1.M0，将其代入・.zj可得

――…网

■-OlogaO-Okc^O——OlotgO-lk)fhl-Olot^O—••,-Ok«iO■Q

所以〃=I,xi=切工…工1rl=4.1=…-0—定是〃了h…在满足约束

f>=l

M和0《n4】的条件下的最小值点，此时/取到最小值0.

综上可知，当〃方「・，口）取到最大值时：》.©・...・/・；；,此时样本集合纯度最

低；当〃方,….J）取到最小值时:〃=卜了1=12='''=几-1="3=’・'=了n=U,此时

样本集合纯度最高.

式(42)

GMQa)=Ent⑼En«h)

此为信息增益的定义式.在信息论中信息增益也称为互信息（参见本章附注①），表示已

知一个随机变量的信息后另一个随机变量的不确定性减少的程度.所以此式可以理解为，

在已知属性优的取值后，样本类别这个随机变量的不确定性减小的程度.若根据某个属性计

算得到的信息增益越大，则说明在知道其取值后样本集的不确定性减小的程度越大，

即“西瓜书”上所说的“纯度提升”越大.

式(4.6)

Ginijixicx(D,a)

此为数据集用属性〃的基尼指数的定义，表示在属性的取值已知的条件下，数据集按

照属性「的所有可能取值划分后的纯度.不过在构造CART决策树时并不会严格按照此式来

选择最优划分属性，主要是因为CART决策树是一棵二叉树，如果用上面的式去选出最优

划分属性，无法进一步选出最优划分属性的最优划分点.常用的CART决策树的构造算法如

下：

（1）考虑每个属性n的每个可能取值小将数据集。分为a=1：和。*I两部分来计算基尼指

数，即

|D«|

Gmiji>dex(D,a)■GH(D+

⑵选择基尼指数最小的属性及其对应取值作为最优划分属性和最优划分点;

⑶重复以上两步，直至满足停止条件,

下面以“西瓜书”中表4.2中西瓜数据集2.0为例来构造CART决策树，其中第一个最优划分

属性和最优划分点的计算过程如下；以属性“色泽”为例，它有3个可能的取值；｛青绿｝,

｛乌黑｝，｛浅白｝,若使用该属性的属性值是否等于“青绿”对数据集成行划分，则可得到

2个子集，分别记为打'（色泽二青绿）,从色泽W青绿）.子集。咆含编号UIf川，13”共6个

33

样例，其中正例占■=£反例占力=礼子集加包含编号（2.3,5,7,8911,12.14,15,16）共

5_6

11个样例，其中正例占出.记，反例占内二记，根据式（4.5）可计算出用“色泽二青绿”划分

之后得到基尼指数为

Giniindex0色泽=青绿）

=nx（1-G）-（D*）+x0-（H）■（H）*）=0497

类似地，可以计算出不同属性取不同值的基尼指数如下：

Gini_index（〃色泽=乌黑）=0.456

Gini_indcx（〃色泽二浅白）=0.426

Gini_index（〃根蒂=蜷缩）=0456

Gini_index（〃根蒂=稍蜷）=0.496

Gini_index（〃根蒂二硬挺）=0.439

Ginijndexm敲声=浊响）=0450

Gini_index（E（敲声=沉闷）=0.494

Gini_index（A敲声二清脆）二0.439

Gini_index（〃纹理=清晰）=0.286

Gini_index（〃纹理二稍稀）=0.437

Gini_index（一纹理=模糊）=0.403

Gini_index（“脐部=凹陷）=0.415

Gini_index（〃脐部=稍凹）=0.497

GinLindex（一脐部=平坦）=0.362

Gini_index（〃触感二硬挺）=0.494

Gini_index（4触感=软粘）=0494.

特别地，对于属性“触感”，由于它的可取值个数为2,所以其实只需计算其中一个取值的

基尼指数即可.根据上面的计算结果可知，Gini_indux（〃纹理=清晰）二0.286最小，所以选

择属性“纹理”为最优划分属性并生成根节点，接着以“纹理=清晰”为最优划分点生成。1纹

理:清晰）、加（纹理，清晰）两个子节点，对两个子节点分别重复上述步骤继续生成下一层

子节点，直至满足停止条件，

以上便是CART决策树的构建过程，从构建过程可以看出，CART决策树最终构造出来的

是一棵二叉树CART除了决策树能处理分类问题以外，回归树还可以处理回归问题，附注

②中给出了CART回归树的构造算法.

式(4.7)

此式所表达的思想很简单，就是以每两个相邻取值的中点作为划分点.

下面以“西瓜书，叶表4.3中西瓜数据集3.0为例来说明此式的用法.对了“密度”这个连续属

性，已观测到的可能取值为｛0,243,0.245,0.343,0.360,0.403,0.437,

0.481,0.556,0.593,0.608,0.634,0.639,0,657,0.666,0.697,0.719,0.774｝共17个值，根据式(4.7)可

知，此时,依次取1到16,那么“密度”这个属性的候选划分点集合为

一，0.243+0.2450.245+0.3430.343+0.洸0

。盛。二。.小蒜仁小2

0.48110.5560.556+0.5930.5品0.608

2，2，2~

0.608+0.6340.634+0.6390.639+0.657

2'2'?

0.657+0.6660.666+0.6970.697+0.7190.719+0.774

)

215'5'2

式(4.8)

Gnin(D,a)=maxGain(D«a,()

IFZ.

-maxEiM(D)-£罂昉

解析

此式是式（42）用于离散化后的连续属性的版本，其中Z由式（4.7）计算得来，入€{-,+}表示

属性。的取值分别小于等于和大于候选划分点•时的情形，即当入=■时有当

A三十时有历=

附注

①互信息[1]

在解释互信息之前，需要先解释一下什么是条件场.条件嫡表示的是在已知一个随机变量

的条件下，另一个随机变量的不确定性.具体地，假设有随机变量用口丫且它们服从以下

联合概率分布

P（X=Xj,V=yj）=i=1,2,,n,j=,m.

那么在已知如勺条件下，随机变量啪条件场为

Ent（r|X）■Z/Ent（y|X-r,）,

tsi

其中，上=n'=1/=12,・・，%互信息定义为信息嫡和条件嫡的差，它表示的是己知一

个随机变量的信息后使得另一个随机变量的不确定性减少的程度.具体地，假设有随机变

量脚Y那么在已知的信息后，的不确定性减少的程度为

I（y：X）=Ent（r）-Ent（y|X）

此即互