2022機器學習公式詳解

機器學習公式詳解

第［章緒論

2第2章霞型評估與選擇

3第3章線性模型

4第4章決策樹

5第5章神經(jīng)網(wǎng)絡

6第6章支持向量機

7第7章貝葉斯分類器

8第8章集成學習

9第9章聚類

第10章‘降維與度量學習

0

1第II章特征選擇與稀疏學習

2第12章計算學習理論

3第13章半監(jiān)督學習

4第14章概率圖模型

5第15章規(guī)則學習

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⑤

③■⑥顯然成立

解析

?！觫?/p>

EEE玳(“)加(川xfj

/*uex-x

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

u^X-X/A

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

MTTh1

②T③：首先要知道此時我們假設J是任何能將樣本映射到｛01｝的函數(shù).存在不止一個了

時，/服從均勻分布，即每個/出現(xiàn)的概率相等.例如樣本空間只有兩個樣本時，

*=即項｝.|川=2.那么所有可能的真實目標函數(shù)孜口下,

人：/乂對）-o=1；

A:gJ-】JJ（如）-比

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

一共2田=少=4個可能的其實目標函數(shù)，所以此時通過算法￡n學習出來的模型h（0對每個樣

本無論預測值為0還是1，都必然有一半的/與之預測值相等，例如，現(xiàn)在學出來的模型川工；

對N1的預測值為1，即“數(shù)）=】，那么有且只有人和人與科蜥預測值相等，也就是有且只

￡1（加0W加））=軻

有一半的/與它預測值相等，所以/2.

值得一提的是，在這里我們假設真實的目標函數(shù)f服從均勻分布，但是實際情形并非如

此，通常我們只認為能高度擬合已有樣本數(shù)據(jù)的函數(shù)才是真實目標函數(shù)，例如，現(xiàn)在已有

的樣本數(shù)據(jù)為｛1工?。?lt;i'）,那么此時為才是我們認為的真實目標函數(shù)，由于沒有收集到

或者壓根不存在他MM◎⑷h伍|」）,」工人機這類樣本,所以九加人都不

算是真實目標函數(shù).這也就是“西瓜書”式（1.3）下面的第3段中“騎自行車”的例子所想表達的

內(nèi)容.

第2章模型評估與選擇

式(2.20)

?m-l

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

isl

解析

在解釋AUC式之前，需要先弄清楚RCC曲線的具體繪制過程.下面我們就舉個例子，按

照“西瓜書”圖2.4下方給出的繪制方法來講解一下RCK曲線的具體繪制過程.

假設我們己經(jīng)訓練得到一個學習器〃*現(xiàn)在用該學習器來對8個洌試樣本(4個正例，4

個反例，即m+=m-=4)進行預測，預測結果為：

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

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

此處用■表示樣本，以和坐標(￡”)作出區(qū)分

其中，，和一分別表示樣本為正例和為反例，數(shù)字表示學習器/預測該樣本為正例的概率，

例如對于反例的來說，當前學習器/(?)預測它是正例的概率為。叔.

上面給出的預測結果已經(jīng)按照預測值從大到小排序

根據(jù)“西瓜書”上給出的繪制方法，首先需要對所有測試樣本按照學習器給出的預測結果進

行排序，接著將分類閾值設為一個不可能取到的最大值.顯然，此時所有樣本預測為正例

的概率都一定小于分類閾值，那么預測為正例的樣本個數(shù)為0,相應的真正例率和假正例

率也都為0,所以我們可以在坐標Q0：處標記一個點.接下來需要把分類閾值從大到小依次

設為每個樣本的預測值，也就是依次設為0.77,0.62,0.58,0.47,0.33,0.23,0.15,然后分別計

算真正例率和假正例率，再在相應的坐標上標記點，最后再將各個點用直線連接，即可得

到RCC曲線.需要注意的是，在統(tǒng)計預測結果時，預測值等于分類閾值的樣本也被算作預

測為正例.例如，當分類閾值為n77時，測試樣本d減預測為正例，由于它的真實標記也

是正例，所以此時是一個真正例.為了便于繪圖，我們將工軸(假壬例率軸)的“步長”定

11

為不,y軸(真正例率軸)的“步長”定為二三根據(jù)真正例率和假正例率的定義可知，每次

t

變動分類閾值時，若新增，個假正例，那么相應的工軸坐標也就增加白；若新增J個真正

1

例，那么相應的y軸坐標也就增加嬴.按照以上講述的繪制流程，最終我們可以繪制出如

圖2“所示的KOC曲線.

圖2-1ROC曲線示意

注：表示紅色線段；表示藍色線段；_____表示綠色線段

在這里，為了能在解析式（2.21）時復用此圖，我們沒有寫上具體的數(shù)值，轉而用其數(shù)學符

號代替.其中綠色線段表示在分類閾值變動的過程中只新增了真正例，紅色線段表示只新

增了假正例，藍色線段表示既新增了真正例也新增了假正例.根據(jù)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后面的內(nèi)容便是在求綠色線段或者藍色線段與“軸圍成的面積，即；

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

I"1-mJ/m

?~wD-u~^D~

與式（2.20）中的求解思路相同，不論是綠色線段還是藍色線段，其與y軸圍成的圖,面積都

可以用梯形公式來進行計算，所以上式表示的依舊是一個梯形的面積公式.其中薪即梯形

的“高”，中括號內(nèi)便是“上底+下底"，下面我們來分別推導一下“上底（較短的底）和“下

底”（較長的底）.

由于在繪制ROC曲線的過程中，每新增一個假正例時“坐標也就新增一個步長，所以對于

1

“上底”，也就是綠色或者藍色線段的下端點到軸的距離，長度就等于U乘以預測值大于

〃工十）的假正例的個數(shù)，即

*￡1（/（?+）＜/（?■））；

而對于“下底”，長度就等于二7乘以預測值大于等于/（的假正例的個數(shù)，即

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等價于在附注中求

-

解事件最大發(fā)生頻率/由附注可知

C=minCa.t.(：)/f

Mt7-F1'/

所以

C.C

—=mm-8.1￡就i尸

mm

Qc

將上式中的UI,四等價替換為^工內(nèi)可得

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(創(chuàng)，屬于簡單的恒等變形

同①③一樣，減一個甌加一個4屬于簡單的恒等變形

同②珊一樣，將最后一項利用期望的運算性質進行展開

解析

M)：首先將中括號內(nèi)的式子展開，有

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

然后根據(jù)期望的運算性質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和如是兩個相互獨立的隨機變量.根據(jù)期望的運算性質

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和眼為常量，根據(jù)期望的運算性質，有⑥中的第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.

附注

二項分布參數(shù)m勺檢驗[1]

設某事件發(fā)生的概率為P,以未知.做m次獨立試驗，每次觀察該事件是否發(fā)生，以*記該事

件發(fā)生的次數(shù)，則X服從二項分布現(xiàn)根據(jù)X檢驗如下假設：

%：P4國；

Hi：p>內(nèi).

由二項分布本身的特性可知；P越小，獨到較小值的概率越大,因此，對于上述假設，一

個直觀上合理的檢驗為

9:"￡C時接飄否則就拒絕仇

其中，表示事件最大發(fā)生次數(shù).此檢驗對應的功效函數(shù)為

flr（p）-P（X>C7）

-1-P（X<C）

由于“礴小，x取到較小值的概率越大”可以等價表示為：p（x&a是關于成勺減函數(shù)，所

以內(nèi)⑵=p（x>c）=I-PZW。是關于『的增函數(shù)，那么當pSR時，43）即％（P）的上

確界.乂根據(jù)參考文獻［1］中5.1.3的定義1.2可知，檢驗水平C默認取最小可能的水平，所以

在給定檢驗水平n時，可以通過如下方程解得滿足檢驗水平c的整數(shù)C：

更為嚴格的數(shù)學證明參見參考文獻［1］中第二章習題7

。=sup{a（p）}

顯然，當P《肉時有

a-=?up{flr（P））

■4佃）

對于此方程，通常不一定正好解得一個使得方程成立的整數(shù)G較常見的情況是存在這樣

一個「使得

Z（：）'（"例廣<0

|“.1'7;

￡（:）月（1-闖

此時，Q只能取6或者⑦+1.若C取值則相當于升高了檢驗水平m若。取。/】則相當于降

低了檢驗水平n.具體如何取舍需要結合實際情況，但是通常為了減小犯第一類錯誤的概

率，會傾向于令Q取0+1.

下面考慮如何求解日易證九&：是關于。的減函數(shù)，再結合上述關于「的兩個不等式易推得

C=minCB.t.￡（：）/4（"內(nèi)廣<。

iaC41'）

參考文獻

u陳希孺.概率論與數(shù)理統(tǒng)計[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=一力協(xié)-叫）-工如=§-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來實現(xiàn)上式的話，上式中的求和運算只能用循環(huán)來實現(xiàn).但是如果能將

上式向量化，也就是轉換成矩陣（即向量）運算的話，我們就可以利用諸如NumPy這種

專門加速矩陣運算的類庫來進行編寫.下面我們就嘗試將上式進行向量化.

1住J=心

將mJM代入分母可得

X航旭一工）

w=上___________

一1日

m

￡僅內(nèi)■旅￡）

￡（才-?。?/p>

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-川內(nèi)(加《)).

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

■

由于眸0或1,則

I工卜編?卜(1*/'))…?1

兩式綜合可得

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

4=1

由于此式仍為極大似然估計的似然函數(shù)，所以最大化似然函數(shù)等價于最小化似然函數(shù)的相

反數(shù)，即在似然函數(shù)前添加負號即可得式(3.27).值得一提的是，若將式(3.26)改寫為

pGgw,b)-佃他⑶聲優(yōu)偈⑶)F再代入式(3.25河得

，同=(佃(如向).佃國創(chuàng)F)

ui

m

?￡伍b(ft(據(jù)；例)+(1-喻卜(ft(A；砌)

t=t

m

=￡(M伽(pi(,；例)-1n3(卻削)十必佃(為;再)))

?=1

整m(㈱)+2⑼)

=能(產(chǎn))+、($))

?￡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),可定義拉格朗日函數(shù)為

￡(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)此時等價于如下優(yōu)化問題

但-3例丁$網(wǎng)

根據(jù)拉格朗日乘子法，可定義上述優(yōu)化問題的拉格朗日函數(shù)

"W內(nèi)=-EMSM+MEMS」W)-"

根據(jù)矩陣微分式近"(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

其中，?慳示樣本類別總數(shù)，%表示第&類樣本所占的比例，有占.若令

卜1=兒內(nèi)=%那么信息嫡Eut(D)就可以看作一個n元實值函數(shù)，即

n

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

4=1

ra

其中上.

下面考慮求該多元函數(shù)的最值.首先我們先來求最大值，如果不考慮約束0404】而僅考

n

慮g"=\則對/(〃「?,力求最大值等價于如下最小化問題；

n

minnlog2q

1=1

M

=i

k=i

顯然，在時，此問題為凸優(yōu)化問題.對于凸優(yōu)化問題來說，使其拉格朗日函數(shù)的

一階偏導數(shù)等于0的點即最優(yōu)解.根據(jù)拉格朗日乘子法可知，該優(yōu)化問題的拉格朗日函數(shù)為

以工匕…,、閭=￡工*M4+入

\k=lJ

其中，1為拉格朗日乘子.對〃內(nèi),…,RZ分別關于力,…,求一階偏導數(shù)，并令偏導數(shù)

等于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，顯然所以〃=及=…=是滿足所有

約束的坡優(yōu)解，即當］前最小化問題的最小值點，同時也是/（孫…,G:的最大值點.將

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

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

\nn/j-jnnnn

R

ow=i

所以/Gi「?在滿足約束￡時的最大值為路外.

52n=1

下面求最小值.如果不考慮約束M而僅考慮。（口（L則〃及「,?7）可以看作〃個

互不相關的一元函數(shù)的和，即

/（了2??,北）

1-1

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

/（0,???4）也就取到了最小值.所以接下來考慮分別求…，仙”各自的最小

值，由于。，的定義域和函數(shù)表達式均相同，所以只需求出d&）的最小值

也就求出了"沖），…，的最小值.下面考慮求“方）的最小值，首先對“了1次于孫求一階

和二階導數(shù)，有

Ji\d{fk<E）t____1,_1

*'=-須?冊=-g工LR

顯然，當04口41時門"）=一亞恒小于0,所以十5）是一個在其定義域范圍內(nèi)開口向

下的凹函數(shù)，那么其最小值必然在邊界取.分別取打=。和h=1,代入4方）可得

計算信息熠時約定：若*°Q，則￡嘀/=。

g（0）=—0logo0=0

y（0=-1logjl=0

所以，*1）的最小值為0,同理可得“物），…屈?。┑淖钚≈狄捕紴?,即〃九…H）的最

小值為o.但是，此時僅考慮約束0（打《］，而未考慮M.若考慮約束X,那

么〃的最小值一定大于等于0.如果令某個“二L那么強據(jù)約束X可知

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

――…網(wǎng)

■-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)

此為信息增益的定義式.在信息論中信息增益也稱為互信息（參見本章附注①），表示已

知一個隨機變量的信息后另一個隨機變量的不確定性減少的程度.所以此式可以理解為，

在已知屬性優(yōu)的取值后，樣本類別這個隨機變量的不確定性減小的程度.若根據(jù)某個屬性計

算得到的信息增益越大，則說明在知道其取值后樣本集的不確定性減小的程度越大，

即“西瓜書”上所說的“純度提升”越大.

式(4.6)

Ginijixicx(D,a)

此為數(shù)據(jù)集用屬性〃的基尼指數(shù)的定義，表示在屬性的取值已知的條件下，數(shù)據(jù)集按

照屬性「的所有可能取值劃分后的純度.不過在構造CART決策樹時并不會嚴格按照此式來

選擇最優(yōu)劃分屬性，主要是因為CART決策樹是一棵二叉樹，如果用上面的式去選出最優(yōu)

劃分屬性，無法進一步選出最優(yōu)劃分屬性的最優(yōu)劃分點.常用的CART決策樹的構造算法如

下：

（1）考慮每個屬性n的每個可能取值小將數(shù)據(jù)集。分為a=1：和。*I兩部分來計算基尼指

數(shù)，即

|D?|

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

⑵選擇基尼指數(shù)最小的屬性及其對應取值作為最優(yōu)劃分屬性和最優(yōu)劃分點;

⑶重復以上兩步，直至滿足停止條件,

下面以“西瓜書”中表4.2中西瓜數(shù)據(jù)集2.0為例來構造CART決策樹，其中第一個最優(yōu)劃分

屬性和最優(yōu)劃分點的計算過程如下；以屬性“色澤”為例，它有3個可能的取值；｛青綠｝,

｛烏黑｝，｛淺白｝,若使用該屬性的屬性值是否等于“青綠”對數(shù)據(jù)集成行劃分，則可得到

2個子集，分別記為打'（色澤二青綠）,從色澤W青綠）.子集。咆含編號UIf川，13”共6個

33

樣例，其中正例占■=￡反例占力=禮子集加包含編號（2.3,5,7,8911,12.14,15,16）共

5_6

11個樣例，其中正例占出.記，反例占內(nèi)二記，根據(jù)式（4.5）可計算出用“色澤二青綠”劃分

之后得到基尼指數(shù)為

Giniindex0色澤=青綠）

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

類似地，可以計算出不同屬性取不同值的基尼指數(shù)如下：

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.

特別地，對于屬性“觸感”，由于它的可取值個數(shù)為2,所以其實只需計算其中一個取值的

基尼指數(shù)即可.根據(jù)上面的計算結果可知，Gini_indux（〃紋理=清晰）二0.286最小，所以選

擇屬性“紋理”為最優(yōu)劃分屬性并生成根節(jié)點，接著以“紋理=清晰”為最優(yōu)劃分點生成。1紋

理:清晰）、加（紋理，清晰）兩個子節(jié)點，對兩個子節(jié)點分別重復上述步驟繼續(xù)生成下一層

子節(jié)點，直至滿足停止條件，

以上便是CART決策樹的構建過程，從構建過程可以看出，CART決策樹最終構造出來的

是一棵二叉樹CART除了決策樹能處理分類問題以外，回歸樹還可以處理回歸問題，附注

②中給出了CART回歸樹的構造算法.

式(4.7)

此式所表達的思想很簡單，就是以每兩個相鄰取值的中點作為劃分點.

下面以“西瓜書，葉表4.3中西瓜數(shù)據(jù)集3.0為例來說明此式的用法.對了“密度”這個連續(xù)屬

性，已觀測到的可能取值為｛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個值，根據(jù)式(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）用于離散化后的連續(xù)屬性的版本，其中Z由式（4.7）計算得來，入€{-,+}表示

屬性。的取值分別小于等于和大于候選劃分點?時的情形，即當入=■時有當

A三十時有歷=

附注

①互信息[1]

在解釋互信息之前，需要先解釋一下什么是條件場.條件嫡表示的是在已知一個隨機變量

的條件下，另一個隨機變量的不確定性.具體地，假設有隨機變量用口丫且它們服從以下

聯(lián)合概率分布

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）

此即互