2022機(jī)器學(xué)習(xí)公式詳解

機(jī)器學(xué)習(xí)公式詳解

第［章緒論

2第2章霞型評(píng)估與選擇

3第3章線性模型

4第4章決策樹

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

6第6章支持向量機(jī)

7第7章貝葉斯分類器

8第8章集成學(xué)習(xí)

9第9章聚類

第10章‘降維與度量學(xué)習(xí)

0

1第II章特征選擇與稀疏學(xué)習(xí)

2第12章計(jì)算學(xué)習(xí)理論

3第13章半監(jiān)督學(xué)習(xí)

4第14章概率圖模型

5第15章規(guī)則學(xué)習(xí)

6第16章強(qiáng)化學(xué)習(xí)

第1章緒論

式(1.1)

電「ZX『㈤坳3"/㈤)PS|X￡)

AafX-X

參見式(1.2)

式(1.2)

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

/，A■3片①

-E曄)￡P(guān)(A|X￡)EI(MZ)"(N))

■di/②

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

rfXXA③

*￡P(guān)㈤￡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③：首先要知道此時(shí)我們假設(shè)J是任何能將樣本映射到｛01｝的函數(shù).存在不止一個(gè)了

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

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

人：/乂對(duì)）-o=1；

A:gJ-】JJ（如）-比

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

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

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

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

￡1（加0W加））=軻

有一半的/與它預(yù)測(cè)值相等，所以/2.

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

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

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

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

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

內(nèi)容.

第2章模型評(píng)估與選擇

式(2.20)

?m-l

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

isl

解析

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

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

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

個(gè)反例，即m+=m-=4)進(jìn)行預(yù)測(cè)，預(yù)測(cè)結(jié)果為：

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

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

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

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

例如對(duì)于反例的來說，當(dāng)前學(xué)習(xí)器/(?)預(yù)測(cè)它是正例的概率為。叔.

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

根據(jù)“西瓜書”上給出的繪制方法，首先需要對(duì)所有測(cè)試樣本按照學(xué)習(xí)器給出的預(yù)測(cè)結(jié)果進(jìn)

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

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

率也都為0,所以我們可以在坐標(biāo)Q0：處標(biāo)記一個(gè)點(diǎn).接下來需要把分類閾值從大到小依次

設(shè)為每個(gè)樣本的預(yù)測(cè)值，也就是依次設(shè)為0.77,0.62,0.58,0.47,0.33,0.23,0.15,然后分別計(jì)

算真正例率和假正例率，再在相應(yīng)的坐標(biāo)上標(biāo)記點(diǎn)，最后再將各個(gè)點(diǎn)用直線連接，即可得

到RCC曲線.需要注意的是，在統(tǒng)計(jì)預(yù)測(cè)結(jié)果時(shí)，預(yù)測(cè)值等于分類閾值的樣本也被算作預(yù)

測(cè)為正例.例如，當(dāng)分類閾值為n77時(shí)，測(cè)試樣本d減預(yù)測(cè)為正例，由于它的真實(shí)標(biāo)記也

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

11

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

t

變動(dòng)分類閾值時(shí)，若新增，個(gè)假正例，那么相應(yīng)的工軸坐標(biāo)也就增加白；若新增J個(gè)真正

1

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

圖2“所示的KOC曲線.

圖2-1ROC曲線示意

注：表示紅色線段；表示藍(lán)色線段；_____表示綠色線段

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

號(hào)代替.其中綠色線段表示在分類閾值變動(dòng)的過程中只新增了真正例，紅色線段表示只新

增了假正例，藍(lán)色線段表示既新增了真正例也新增了假正例.根據(jù)AUC值的定義可知，此

時(shí)的AUC值其實(shí)就是所有紅色線段和藍(lán)色線段與了軸圍成的面積之和.觀察圖2“可知，紅色

線段與了軸圍成的圖形恒為矩形，盛色線段與了軸圍成的圖形恒為梯形.由于梯形面積式既

能算梯形面積，也能算矩形面積，所以無論是紅色線段還是藍(lán)色線段，其與工軸圍成的面

積都能用梯形公式來計(jì)算：

5（力+1一備）?（弘+弘+1）

其中，（31-xJ為“高力明為“上底”，阱n為嚇底”.那么對(duì)所有紅色線段和藍(lán)色線段與工軸

圍成的面積進(jìn)行求和，則有

￡?。╣-加版+/+i）

tsi

此即AUC

式（2.21）

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

解析

按照我們上述對(duì)式（2.20）的解析思路，，一■可以看作是所有綠色線段和藍(lán)色線段與期軸闈成

的面積之和，但從式Q.21）中很難一眼看出其面積的具體計(jì)算方式，因此我們進(jìn)行恒等變

形如下：

J-＜/（?*））+^（/（?*）-/（?-））]

bwIMbWD*',

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

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

??UE?-vn-

E【（/—）

a~cD~?

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

＞-?o-

w

2Ei（"）■/"））

?一￡11-

在變動(dòng)分類閾值的過程當(dāng)中，如果有新增真正例，那么圖2-1就會(huì)相應(yīng)地增加一條綠色線

E

段或藍(lán)色線段，所以上式中的面看可以看作是在累加所有綠色和藍(lán)色線段，相應(yīng)地，

?21后面的內(nèi)容便是在求綠色線段或者藍(lán)色線段與“軸圍成的面積，即；

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

I"1-mJ/m

?~wD-u~^D~

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

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

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

底”（較長的底）.

由于在繪制ROC曲線的過程中，每新增一個(gè)假正例時(shí)“坐標(biāo)也就新增一個(gè)步長，所以對(duì)于

1

“上底”，也就是綠色或者藍(lán)色線段的下端點(diǎn)到軸的距離，長度就等于U乘以預(yù)測(cè)值大于

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

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

而對(duì)于“下底”，長度就等于二7乘以預(yù)測(cè)值大于等于/（的假正例的個(gè)數(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)應(yīng)當(dāng)勘誤為

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

jm‘l'''

具體推導(dǎo)過程如下：由“西瓜書”中的上下文可知，對(duì),<a進(jìn)行假設(shè)檢驗(yàn)，等價(jià)于本章附

注中所述的對(duì)D4為進(jìn)行假設(shè)檢驗(yàn)，所以在“西瓜書”中求解最大錯(cuò)誤率7等價(jià)于在附注中求

-

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

C=minCa.t.(：)/f

Mt7-F1'/

所以

C.C

—=mm-8.1￡就i尸

mm

Qc

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

e=mineM.g。)點(diǎn)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②：減一個(gè)fW再加一個(gè)f(創(chuàng)，屬于簡單的恒等變形

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

同②珊一樣，將最后一項(xiàng)利用期望的運(yùn)算性質(zhì)進(jìn)行展開

解析

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

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

然后根據(jù)期望的運(yùn)算性質(zhì)EA-ME[A1+E]可將上式化為

4[(/(?;D)-詞)]+%[(祠-即)1+

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

③草：再次利用期望的運(yùn)算性質(zhì)將第3步得到的式子的最后一項(xiàng)展開，有

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

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

首先計(jì)算展開后得到的第1項(xiàng)，有

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

由于f(z)是常量，所以由期望的運(yùn)算性質(zhì)：用.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

接著計(jì)算展開后得到的第二項(xiàng)

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

由于噪聲和/無關(guān)，所以/”；0和如是兩個(gè)相互獨(dú)立的隨機(jī)變量.根據(jù)期望的運(yùn)算性質(zhì)

EA*]E[F|(其中m口訥相互獨(dú)立的隨機(jī)變量)可得

/[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⑦：因?yàn)?4和眼為常量，根據(jù)期望的運(yùn)算性質(zhì)，有⑥中的第2項(xiàng)

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

同理有⑥中的最后一項(xiàng)

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

由于此時(shí)假定噪聲的期望為零，即3)以-*)]?Q所以

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

附注

二項(xiàng)分布參數(shù)m勺檢驗(yàn)[1]

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

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

%：P4國；

Hi：p>內(nèi).

由二項(xiàng)分布本身的特性可知；P越小，獨(dú)到較小值的概率越大,因此，對(duì)于上述假設(shè)，一

個(gè)直觀上合理的檢驗(yàn)為

9:"￡C時(shí)接飄否則就拒絕仇

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

flr（p）-P（X>C7）

-1-P（X<C）

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

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

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

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

更為嚴(yán)格的數(shù)學(xué)證明參見參考文獻(xiàn)［1］中第二章習(xí)題7

。=sup{a（p）}

顯然，當(dāng)P《肉時(shí)有

a-=?up{flr（P））

■4佃）

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

一個(gè)「使得

Z（：）'（"例廣<0

|“.1'7;

￡（:）月（1-闖

此時(shí)，Q只能取6或者⑦+1.若C取值則相當(dāng)于升高了檢驗(yàn)水平m若。取。/】則相當(dāng)于降

低了檢驗(yàn)水平n.具體如何取舍需要結(jié)合實(shí)際情況，但是通常為了減小犯第一類錯(cuò)誤的概

率，會(huì)傾向于令Q取0+1.

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

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

iaC41'）

參考文獻(xiàn)

u陳希孺.概率論與數(shù)理統(tǒng)計(jì)[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社,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,又因?yàn)閞"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來實(shí)現(xiàn)上式的話，上式中的求和運(yùn)算只能用循環(huán)來實(shí)現(xiàn).但是如果能將

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

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

1住J=心

將mJM代入分母可得

X航旭一工）

w=上___________

一1日

m

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

￡（才-?。?/p>

mmmmm

又因?yàn)檎糓占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

對(duì)溢導(dǎo)可得

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

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

反數(shù)，即在似然函數(shù)前添加負(fù)號(hào)即可得式(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

顯然，此種方式更易推導(dǎo)出式(3.27).

式(3.30)

叩t=l

解析

此式可以進(jìn)行向量化.令九一陰(以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)

對(duì)靠求偏導(dǎo)可得

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而拉格朗日乘子退體取值多少都無葉謂，因此可以任意設(shè)

定】來配合我們求解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）的推廣形式，證明如下.

設(shè)卬?1嗎叫…工，,.….心「）—'"-1）,其中犯€片對(duì)為d行1列的列向量，則

/?-i

T

tr(lVS^)=￡w7Skvb

NT

U(WTS9W)=EW[SM，

所以式(3.44)可變形為

IN-\

E⑼

a4=1

------

￡B「S■皿

t=i

對(duì)比式(3.35)易知，上式即式(3.35)的推廣形式.

式(3.45)

SkW=AS.H

解析

同式(3.35),此處也固定式(3.44)的分母為1,那么式(3.44)此時(shí)等價(jià)于如下優(yōu)化問題

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

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

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

根據(jù)矩陣微分式近"(XTBX)■(,+小)*對(duì)上式關(guān)于哪偏導(dǎo)可得

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)就可以看作一個(gè)n元實(shí)值函數(shù)，即

n

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

4=1

ra

其中上.

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

n

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

n

minnlog2q

1=1

M

=i

k=i

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

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

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

\k=lJ

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

等于o可得

^^耀—八信旬卜

=啕孫+町-+A=0

flInJ

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

2In2

/F唱后…一(ET卜。

孫%￡工』*+延時(shí)1)]=。

、11

a(m=。

n2"=1.

整理一下可得

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

以一

(I

由以上兩個(gè)方程可以解得

1

M1T~??=3一

又因?yàn)椤鬟€需滿足約束1，顯然所以〃=及=…=是滿足所有

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

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

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

\nn/j-jnnnn

R

ow=i

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

52n=1

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

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

/（了2??,北）

1-1

其中，g（川―一川。5〃,08nSL那么當(dāng)加川屈丁?！?巾；）分別取到其最小值時(shí)，

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

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

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

和二階導(dǎo)數(shù)，有

Ji\d{fk<E）t____1,_1

*'=-須?冊(cè)=-g工LR

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

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

計(jì)算信息熠時(shí)約定：若*°Q，則￡嘀/=。

g（0）=—0logo0=0

y（0=-1logjl=0

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

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

么〃的最小值一定大于等于0.如果令某個(gè)“二L那么強(qiáng)據(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】的條件下的最小值點(diǎn)，此時(shí)/取到最小值0.

綜上可知，當(dāng)〃方「?，口）取到最大值時(shí)：》.??...?/?；；,此時(shí)樣本集合純度最

低；當(dāng)〃方,….J）取到最小值時(shí):〃=卜了1=12='''=幾-1="3=’?'=了n=U,此時(shí)

樣本集合純度最高.

式(42)

GMQa)=Ent⑼En?h)

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

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

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

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

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

式(4.6)

Ginijixicx(D,a)

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

照屬性「的所有可能取值劃分后的純度.不過在構(gòu)造CART決策樹時(shí)并不會(huì)嚴(yán)格按照此式來

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

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

下：

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

數(shù)，即

|D?|

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

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

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

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

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

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

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

33

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

5_6

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

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

Giniindex0色澤=青綠）

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

類似地，可以計(jì)算出不同屬性取不同值的基尼指數(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.

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

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

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

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

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

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

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

②中給出了CART回歸樹的構(gòu)造算法.

式(4.7)

此式所表達(dá)的思想很簡單，就是以每兩個(gè)相鄰取值的中點(diǎn)作為劃分點(diǎn).

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

性，已觀測(cè)到的可能取值為｛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個(gè)值，根據(jù)式(4.7)可

知，此時(shí),依次取1到16,那么“密度”這個(gè)屬性的候選劃分點(diǎn)集合為

一，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）計(jì)算得來，入€{-,+}表示

屬性。的取值分別小于等于和大于候選劃分點(diǎn)?時(shí)的情形，即當(dāng)入=■時(shí)有當(dāng)

A三十時(shí)有歷=

附注

①互信息[1]

在解釋互信息之前，需要先解釋一下什么是條件場(chǎng).條件嫡表示的是在已知一個(gè)隨機(jī)變量

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

聯(lián)合概率分布

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

那么在已知如勺條件下，隨機(jī)變量啪條件場(chǎng)為

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

tsi

其中，上=n'=1/=12,??，%互信息定義為信息嫡和條件嫡的差，它表示的是己知一

個(gè)隨機(jī)變量的信息后使得另一個(gè)隨機(jī)變量的不確定性減少的程度.具體地，假設(shè)有隨機(jī)變

量腳Y那么在已知的信息后，的不確定性減少的程度為

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

此即互