第1章習(xí)題

第1題

垃圾分類：可回收物、有害垃圾、廚余垃圾和其他垃坡。

重量屬性、濕度屬性、顏色屬性、形狀屬性、名稱屬性等。

第2題

模型性能評(píng)估主要是對(duì)模型性能優(yōu)良進(jìn)行評(píng)價(jià)，測(cè)度模型是否達(dá)到任務(wù)要求，不同任

務(wù)通常設(shè)計(jì)不同評(píng)估函數(shù)；

損失函數(shù)也叫代價(jià)函數(shù)，定義為整個(gè)訓(xùn)練集上所有樣本誤差的平均：

目標(biāo)函數(shù)定義為優(yōu)化函數(shù)，等于代價(jià)函數(shù)+正則化項(xiàng)。

第3題

監(jiān)督學(xué)習(xí)，每個(gè)數(shù)據(jù)都有對(duì)應(yīng)標(biāo)簽。簡(jiǎn)單說(shuō)，通過(guò)數(shù)據(jù)+標(biāo)簽訓(xùn)練模型。

非監(jiān)督學(xué)習(xí)，數(shù)據(jù)沒(méi)有對(duì)應(yīng)標(biāo)簽。簡(jiǎn)單說(shuō)，通過(guò)數(shù)據(jù)，獲得某種潛在函數(shù)。

強(qiáng)化學(xué)習(xí)通過(guò)在智能體與環(huán)境的交互過(guò)程中智能體學(xué)習(xí)策略以達(dá)成回報(bào)最大化或?qū)?/p>

現(xiàn)特定目標(biāo)。

第4題

自適應(yīng)學(xué)習(xí)率、小批量梯度下降、動(dòng)量

第5題

奧卡姆剃刀準(zhǔn)則：如無(wú)必要，勿增實(shí)體。(Entitiesshouldnotbemultipliedunnecessarily)

羅生門現(xiàn)象(LeoBMman)：處理問(wèn)題時(shí)，往往各執(zhí)一詞，從而形成有利于自己的處理

方式。機(jī)器學(xué)習(xí)中的羅生門現(xiàn)象與嶺回歸有關(guān)，沒(méi)有唯一解.

“沒(méi)有免費(fèi)的午鈴”定理(NoFreeLunchTheorem,NFL)：在優(yōu)化算法中任何個(gè)模

型函數(shù)都不能解決所有問(wèn)題。如果在一些訓(xùn)練樣本上表現(xiàn)好，那么在另一些訓(xùn)練樣本上

表現(xiàn)不好。

第6題

0.5166.程序，略。

第1題

高斯分布對(duì)離群點(diǎn)非常敏感，擁擠現(xiàn)象影響明顯。

參考教材圖2.13,采用學(xué)生/分布計(jì)算相似度。實(shí)現(xiàn)同一簇類點(diǎn)（距離較近）聚合更緊密,

不同簇類間點(diǎn)更加疏遠(yuǎn)。

第2題

描述屬性間相關(guān)矩陣。

。。心1占)cov(xxx2)…COU(M產(chǎn)N)

cov{_x2x^cov(x2x2)…cov(x2xN)

:?

(COV{XNXx)cov(xx)???cov(xx)

N2NN

xTx描述樣本間相關(guān)矩陣。

第3題

E[(〃k--Mm)l=-3加c+*外n-區(qū)內(nèi)n-4M)]

=2EKM?-M“)]=2E(或〃。-2E(〃>m)

=2E(〃屈Q-2E(戒)E("Q=2]E(區(qū)-MoMol

E[(〃k-〃O)T(〃K-Mo)]=+gjMo-區(qū)Mo-麗k)l=E(或一尾4o

E[3k-一4n)]=2磯3-〃0)T3k-Mo)]

第4題

模仿例2.4,詳細(xì)過(guò)程略。

第1題

略。

第2題

提示：輸入圖像，計(jì)算直方圖，然后估計(jì)概率分布曲線。

第3題

稀少事件指在有限次試驗(yàn)中很少甚至不出現(xiàn)事件。以至于，稀少事件概率為零，實(shí)際上

并不等于零。為避免這種不準(zhǔn)確的概率計(jì)算出現(xiàn)，可以采用“m-估計(jì)法”。

例如0/事件概率計(jì)算

No+mn0Ni+mnx

Po=N+m；P1=/V+zn

No+M=N

沏和心為專家直覺(jué)概率，即憑先驗(yàn)知識(shí)，出現(xiàn)。和1的概率應(yīng)該為質(zhì)和叼。

第1題

模仿例題4』，詳細(xì)過(guò)程略。

第2題

設(shè)包含N個(gè)樣本的樣本集0=｛（九力）,（無(wú)272），…,（布,%）｝共有C個(gè)類別和樣本%”的k近

鄰樣本集為｛%1，不，…,4｝，采用k近鄰分類的平均錯(cuò)誤率為PkNN（e），

Nrk

PkNN?=WWP（4（元n&））尸（心兄）PM

n=lL?n=l

C

P（e|（%m，&））=1-WP（c|"m）P（c'）

C=1

PkNN=J$PkNN（e）

第3題

1.ball-tree是對(duì)kd-tree的改進(jìn)，在數(shù)據(jù)維度較大時(shí)，kd-tree性能急劇下降，而

ball-tree在高維數(shù)據(jù)情況卜.具有更好的性能。

2.kd-tree采用二叉樹(shù)思想，最近鄰使用歐式距離（超球體），分割子空間為超方體。

顯然，分割的超方體與搜索的超球體相交可能性大，而相交空間需要檢查；

3.ball-tree,采用兩邊之和與第三邊大小進(jìn)行判斷，分割子空間也是超球體，所以分

割區(qū)與搜索區(qū)相交部分減少。

第1題

略。

第2題

1.優(yōu)化問(wèn)題存在約束條件，

min/(X),s.t.hk(x)=0,k=1,2,...

拉格朗日函數(shù)定義為，

FSB。=/(%)+W6kM(%)

2.優(yōu)化問(wèn)題存在不等式約束條件，

min/(x),s.t.h,k(x)=0,k=1,2,...,m=1,2,...

如果滿足KKT條件：

(])a.(x，6k，'m)|_Q.

dxlx=x"

(2)6k*o；

(3)>0;

(4)Amgm(x^=0,互補(bǔ)松弛條件，

其拉格朗日函數(shù)定義為，

F(x,/?fc,Am)=/(x)+，Bkhk(x)+AmgmM

km

第3題

%_______（i-yn）"（5；w）

中=-法/On；w）1-f（xn；w）]dw

n=L

___yn_______（l-yn）"（%；W）dz

f（x;W）1-f（x;w）]dz

42nndw

=4S[7(^)-1，君R/&；?)(//6；卬))器

n=l

]N

=一百W帆@-f（&；卬））一（1一W）]%n

n=l

]']N

=一斤W[為一f（%n；W）拉n=]Zh一%n

II—111-1

第4題

刃(W,b)1Y,TfA、]

-^T=NL[x^WXn+b~Zn)]

n=l

N

=N(wx”

百Q(mào)n-b))]

n=l

1NN

=瓦2必與)2-：＞(4—)媒=0

/VZ-1

n=ln=l

N]N

aj(w,b)_1「2仍一(z〃一w?]=b--^(z-w喘)=0

db一NZ1(Kb句)]-八n

n=ln=ln=l

第5題

wx

8/(w)_1dj(w)[yVcfgcn

f

n=c]logcwx

dwc~Ndwc|ZJX；n=ieW"n

1刃(w)卜yy況%=c)(wcxn-logy

Ndwc|z

=用￡碼_」yx^ew^\\

n~c}vn與篙…J

N219{yn=c}ewf|

=4Z-(

n=l

「用r春N”(fwx?\1

，…Fc-r)|

ln=l

4[f(p(yn

=c\f(xn;w)}-6(yn=c})xn

第1題

設(shè)X的特征向量和特征值分別是&和九即=

N

(W0(%)(0區(qū)))7二加(1)

n=l

NN

"=)W((08))‘)6(孫)=W,斯=,((?6))%)⑵

71=171=1

TT

(。區(qū)))山=入(。⑶))V(3)

將(2)代入(3)得，

NN

Mog))%=MO?))'W即081)=4W即(0&))‘奴無(wú)”)

n=ln=l

=4((0(4))70(%1)(0g)y0(%2)…(0(xfc))T0(xiv))(7)

=AXcr

NN

（0（^/c））TZv=（。（4））號(hào)2。（項(xiàng)）（0（范））〉即。區(qū)）

i=ln=l

N/N\

=，W即(0(())[We?)(。?))[

n=l\i=l)

0(xj(0?)))0(%i)…(0(九))[108)(08)))OQN：)(?)

=2

所以有，ANJCa=K2aXNa=OCa

第2題

設(shè)/W”XN,]q=iij=1,2,…，N

/N\//N

T

無(wú)(項(xiàng)巧)=(0(xf))0(xy)=(奴陽(yáng))-'W*(3))(3(勺)一'W奴4)

NN

女（4勺）=（奴/））”（勺）一，一"2（火距））“（丸）

n=lk=l

N

+禧W（*g））%g）

fc,n=l

NNN

女（片，巧）="（勺,巧）一，2/i,nK（%n，U）一（WK（巧±Wk,n^（xn,Xk）IkJ

n=lk=lntk=l

=K（x”巧）一卜雙陽(yáng)⑹-%（xl-,x;）//v+lNJC（＜xi,Xj'）IN

第3題

%（xf,x;）=（</>（Xi）f（/）（Xj））=￡（焉/養(yǎng)xj）（焉e一券芍n）

71=0

I區(qū)一”12

exp

2a2

n=0

第4題

K（M，巧）=（1+x]xj）2=（1+WXk』Xk,j）

\k=l）

dd〃一1d

=1+W（伍h）（伍kj）+WW（缶k/m」）（低k,/mj）+W歡咨3

k=lk=2m=lk=l

=<0（Xi）,0（X;））

第5題

1

核函數(shù)均為正定函數(shù)：VneN,a={alta2...,an]ER,

nnnnnn

2w《a必（量巧）=w2<“°8）嗎。（巧》亢=〈2%0（'）2為@（芍”亢

i=ij=li=lj=li=lj=l

=卜[%0區(qū)）之。

第1題

略。

第2題

略。

第3題

定理：Hoeffding不等式

設(shè)Z1，Z2，…,2?為獨(dú)立有界隨機(jī)變量，且-8<aWbV8,那么，

P(5(ZLE㈤)Nt)vexp(一丹)

PG￡(ZLE閡"-t)<exp(-^7)

第4題

Booting是實(shí)現(xiàn)集成學(xué)習(xí)的?種機(jī)制；而AdaBoost(AdaptiveBoosting)是實(shí)現(xiàn)Boosting

機(jī)制的一種方式。

第5題

CART與ID3和C4.5相同點(diǎn)：特征選擇、樹(shù)的生成和剪枝三個(gè)不揍。

ID3和C4.5用于分類，CART既可用于分類，也可以實(shí)現(xiàn)回歸。

第8章聚類..........................................................................II

一一聚類基本理論...............................................................11

8.1.1聚類的唾...................................................................11

8.1.2相似性測(cè)度...................................................................12

8.1.3類簇中心.....................................................................13

8.1.4聚類算法評(píng)價(jià)書(shū)梟示.............................................................15

一_K均值聚類..................................................................20

―一層次聚類....................................................................21

83.1凝聚糠.....................................................................22

8.3.2平衡雌削減層次聚類........................................................23

__密度聚類....................................................................26

8.4.1DDSCAN..........................................................................................................................................26

8.4.2高斯混合聚類.................................................................28

—_小結(jié)與拓展..................................................................29

實(shí)驗(yàn)八聚類實(shí)驗(yàn)....................................................................29

習(xí)題...............................................................................31

第8章聚類

聚類是無(wú)監(jiān)督學(xué)習(xí)算法，其目的是把相似樣本歸為一類，不相似樣本歸為另一類。例如

將動(dòng)物聚類，可以根據(jù)“腿屬性”聚類成無(wú)足動(dòng)物、兩腿動(dòng)物和四腿動(dòng)物。聚類算法大體可

分為均值區(qū)域劃分聚類、層次聚類、密度聚類和譜聚類算法。層次聚類算法可追溯到1963

年，最著名的k均值聚類算法則于1967年被提出，1995年提出的MeanShift算法于1995

年用于聚類，譜聚類算法誕生于2000年左右。

相似度測(cè)度：歐式距離，殳哈頓距礴，閔可夫斯基距離，值差異

類簇中心：K均值中心、基于密度的中

評(píng)價(jià)指標(biāo)：純度，聚類烯，同質(zhì)性，蘭德指數(shù)，輪廓系

K均值聚類：k-mean,k-mean++

層次聚類：凝聚筑巢，平衡迭代削

鷲度聚類:DBSCAN,高斯混合聚

俗話說(shuō)：物以類聚，人以群分。樹(shù)立正確的人生觀、價(jià)值觀和世界觀。

聚類基本理論

8.1.1聚類的性質(zhì)

對(duì)樣本數(shù)據(jù)集X=口1/2,…，無(wú)N｝聚類成K個(gè)樣本簇：｛的,32,…，網(wǎng)卜滿足二個(gè)住質(zhì):

?非空性：符00,k=1,2,...,K

?不相交：XkCyXi=0,k,l=k*I

?全覆蓋：U￡=i%=%。

聚類簇須中樣本在某個(gè)屬性或某些屬性指導(dǎo)下

彼此“相似”而物以類聚，異簇之間樣本“不相似”

而敬而遠(yuǎn)之。實(shí)際上，聚類結(jié)果未必全滿足上述三個(gè)

條件。如圖8.1所示，如果把圖中黑色點(diǎn)當(dāng)作噪聲樣

本，顯然上述三個(gè)條件全滿足。如果不是噪聲點(diǎn)，1號(hào)

圖8.1聚類示意

黑色樣本點(diǎn)可能同時(shí)被劃歸為無(wú)2和工3,2號(hào)黑色樣本

點(diǎn)不被任何簇吸收。

8.1.2相似性測(cè)度

一相似度測(cè)度的性質(zhì)

在聚類算法，樣本間相似度通常需要采用兩個(gè)樣本之間的“距離測(cè)度(DistanceMetric,

T

DM)”進(jìn)行衡量。設(shè)兩個(gè)向量％=(與,％2，…,xd),y=(yny2，…,％)丁，則它們之間距離用

表示。距離測(cè)度應(yīng)該具有如下性質(zhì)：

?非負(fù)性，距離不能是負(fù)數(shù)：OM(%,y)NO；

?同一性，具有相同屬性向量的兩個(gè)樣本的距離等于零：OM(%,%)=0；

?無(wú)向性或?qū)ΨQ性，4到y(tǒng)與y到％的距離相等：DM(x,y)=DM(y,x)；

T

?直遞性，三角不等式:DM(x,y)<DM(x,z)+d(z,y),z-(zltz2,...,zd)o

?常見(jiàn)距離測(cè)度

1)歐氏距離(Euclidean)

0M(4,y)=￡?=信…)(81)

2)曼哈頓距離(Manhattan)

d

=\氏一

DM(x,y)=^1(8.2)

t=i

3)閔可夫斯基距離(Minkowski)

1

DM(x,y)=(8.3)

式中，p=l時(shí)，閔氏距離即為曼哈頓距離；

當(dāng)p=2時(shí),閔氏距離則為歐氏距離。

圖8.2顯示了二維空間中樣本點(diǎn)(k1，.2)取不同值

時(shí)，與原點(diǎn)(0,0)的距離為1((=1)的點(diǎn)的圖形。

一不同量綱間距離測(cè)度

計(jì)算上述距離時(shí)，隱含一個(gè)假設(shè)：各屬性分量的量

綱(單位)相同。然而如果屬性分量的單位不相同，則各

分量的分布(期望，方差等特性)可能不同。舉個(gè)例子：

二維樣本(身高，體重)，其中身高范圍是150?190屈米,

體重范圍是50?60公斤?，F(xiàn)有三個(gè)樣本：張三(180,50),李四(190,50),王五(180,60)。那么

張三與李四之間的閔氏距離等于張三與王五之間的閔氏距離，但是身高的10厘米并不一定

等價(jià)于體重的10公斤。

針對(duì)量綱不同的屬性，通常采用兩種方式進(jìn)行標(biāo)準(zhǔn)化:

1)采用每個(gè)屬性值的標(biāo)準(zhǔn)差進(jìn)行歸一

DM{x,y)=(8.4)

式中，s”表示第九維的標(biāo)準(zhǔn)差。

2)標(biāo)準(zhǔn)化屬性尺度是把所有屬性取值縮放到相同區(qū)間[0,1]

x—min(x)

(8.5)

max(x)-min(x)

值差異度量.△T￡_。衿a。.。，。。6一寸△入二

無(wú)序?qū)傩圆捎弥挡町惗攘?VDM)。

在K個(gè)類簇中，設(shè)m。/是屬性a上取值為％的樣本數(shù)，撈**表示在第攵類樣本簇中屬性。

上取值為無(wú)的樣本數(shù)，則屬性a上取值為和外的VDM定義為，

皿%―=￡|暗-等『(“)

設(shè)樣本的d屬性向量中有4個(gè)有序?qū)傩?，d-a個(gè)無(wú)序?qū)傩?，則樣本yy的閔可夫斯基距

離(Minkowski)定義為

DM(x,y)=2(%一方"+WV°Mp(孫力)(8.7)

i=li=dc+lj

當(dāng)不同屬性重要性不同時(shí)，可乘權(quán)重系數(shù)WiNO,Xf=lWt=lo

8.1.3類簇中心

類簇中心，又稱為簇質(zhì)心，定義為簇內(nèi)樣本分布中心，如圖8.1中每簇的中心點(diǎn)。然而，

不同聚類算法定義各有差別，簡(jiǎn)單分為兩種：

…均值聚類簇中心

設(shè)聚類結(jié)果為｛匕,4，…,&｝，第/類的樣本數(shù)量為以，則元=｛4,^，…，如)，K均值

聚類算法將類簇中心定義為各簇中樣本點(diǎn)的平均值，即

=〃(招)=(8.7)

通過(guò)式(8.7)計(jì)算類簇中心符合最優(yōu)理論。

基于密度的類簇中心

AlexRodriguez和AlessandroLaio在Science期刊文章中提出：類簇中心周圍都是密度

比其低的點(diǎn)，同時(shí)這些點(diǎn)歪離該簇中心的距離相比于其他聚類中心最近。

設(shè)樣本集％={/，刈，…，修/中樣本間距離為0時(shí)?！?;^)，樣本索引集〃={1,2，…,N}。

對(duì)于樣本首先計(jì)算其局部密度和距離〃n：

(1)樣本事的局部密度Pn

局部密度定義為以事為中心、￡為半徑的鄰域Ne(Xn)內(nèi)樣本點(diǎn)的數(shù)量(不包括f本身)。

根據(jù)鄰域內(nèi)外分界方式，可分為硬截?cái)?Cut-of「kernel)和高斯平滑截?cái)?GaussianKernel)兩種

模式。

1)硬截?cái)?/p>

Pn=W"DM(%n，/n)-￡)(8.8)

m€/d\{n}

式中，

把鄰域半徑￡稱為截?cái)嗑嚯x。

2)高斯平滑截?cái)?/p>

2

V/DM(xn.xm)\l

Pn=exp-----E----)(89)

nt€/d\{n}')

計(jì)算局部密度的目的為了依據(jù)密度大小尋找類簇中心，為此希望樣本點(diǎn)的局部密度盡可

能不相等。顯然，高斯平滑截?cái)嗑哂袃蓚€(gè)優(yōu)點(diǎn)：(1)具有相同局部密度的概率?。?2)鄰域MQ”)

內(nèi)樣本點(diǎn)數(shù)越多，局部密度越大。

(2)距離〃n

當(dāng)獲得X={f猾=1的密度集{Pn猾=1后，則f的距離g定義為無(wú)n與密度大于P”的樣本

了集中樣本;1詁的最小距離，

%=min{DM(x,x))J/Id}1*0(8.10)

mG/dJn,n

式中，Id*={rn\pm>pj表示樣本集無(wú)中密度大于Xn的密度pn的樣本％m的索引集。

然而，當(dāng)Pn=max{p?}?=i，則/d9=0,此時(shí)％”的距離心定義為，

m€/dx

d=max[DM(_x,x)},if/吸=0(8.11)

nm€/dxnin

式中，ldx={1,2,…,N}為樣本集匯={右}匕i中每個(gè)樣本的索引集。

圖8.3展示了一個(gè)決策類簇中心的例子，圖中樣本點(diǎn)為二維屬性向量。圖8.3(a)為28個(gè)

樣本點(diǎn)分布。直觀上，容易發(fā)現(xiàn)點(diǎn)1和點(diǎn)10可作為類簇中心。

圖8.3(a)：維樣本空間分布和(b)決策圖(Pn，〃n)

圖8.3(b)是由(局部密度，距離)，即(p,d),構(gòu)建的類^中心決策圖。從圖中，不難發(fā)現(xiàn)，

點(diǎn)1和點(diǎn)10在決策圖中分布在右上角，即不僅局部密度較大，而且距離也較大。

盡管P9和P10相差不大，但是49和。10卻有很大差別：點(diǎn)9屬于點(diǎn)1的類簇(把點(diǎn)1作為

大腿抱著)，在其附近還有幾個(gè)更高的局部密度的點(diǎn)，因此心較小；在點(diǎn)10附近不存在有更

高密度的點(diǎn)，比點(diǎn)10密度更高點(diǎn)卻處于其它類簇。所以，點(diǎn)10是類簇中心而點(diǎn)9不是。

此外，點(diǎn)26、27和2B是孤立的，盡管有相對(duì)較高的距離值，但是它們的局部密度值很

低。這些點(diǎn)稱為異常點(diǎn)，可當(dāng)作噪聲點(diǎn)，也可作為單個(gè)點(diǎn)構(gòu)成的簇。

綜上所述，只有同時(shí)具有較高局部密度和距離的點(diǎn)才是非孤立點(diǎn)的類簇中心。

8.1.4聚類算法評(píng)價(jià)指標(biāo)

如圖8.4所示，假設(shè)兩種聚類算法41和A2,對(duì)％={%1，不，…，必1}聚類結(jié)果分別為，

C={G，C2,C3,CJ

為了表述方便，假設(shè)算法41的聚類結(jié)果是期望結(jié)果，稱每個(gè)聚類為一個(gè)類；聚類算法42

的結(jié)果則需要進(jìn)行評(píng)價(jià)，稱每個(gè)聚類為一個(gè)簇。

聚類算法41

聚類算法A2

圖8.4聚類算法評(píng)價(jià)指標(biāo)

實(shí)際應(yīng)用中存在許多聚類算法的評(píng)價(jià)指標(biāo)，這里主要介紹以下幾種:

純度』一。_-

將每個(gè)簇內(nèi)頻數(shù)最高的樣本類別作為正確的類簇，則每簇純度定義為,

該簇正確樣本數(shù)

Purity(K)=(8.12)

k該族樣本總數(shù)

參考算法力1的聚類結(jié)果，圖8.4聚類算法42每個(gè)簇的純度分別為:

54231

PurityW^=-,Purity(X)=Purity=-.Purity^)=PurityW)=-

62□Z□53

整個(gè)聚類的純度定義為，

頻數(shù)最高類別的樣本數(shù)之和

Purity(K)=(8.13)

樣本總數(shù)

算法42聚類后整體純度為,

5+4+2+3+115

Purity(K)=

2121

▽聚類崎

針對(duì)每一個(gè)聚類簇心，其端定義為,

Entropy^k)=~^Pks，°。3心)=一￡log葭:(8.14)

S=1S=1\/

式中，S表示聚類算法41的類別數(shù)，p人是簇招中樣本屬于類Q的概率。當(dāng)先來(lái)自同一

個(gè)Cs時(shí)，其燧等于0,這只是最理想的聚類。

圖8.4聚類算法42聚類結(jié)果每個(gè)簇的嫡為，

=一前9弓）一%四?,

EntropyEntropy^)

Entropy(^3')EntropyC^^)

Entropy(/)=~\lo9(1)(鄉(xiāng)~\1°9(1)

同質(zhì)性「阡。?。?。%.

同質(zhì)性也叫均一性，一個(gè)類簇中僅有一個(gè)類別的樣本，均一性最高。

相當(dāng)于精確率，即被聚類的類簇中正確分類的樣本數(shù)占該類簇中的樣本數(shù)的比例,

1v正確聚類為第k簇的樣本數(shù)量

Accuracy=—>--------------------------------------(8.15)

KKJ—1聚類為第k族的樣本總數(shù)

假設(shè)火5為噪聲簇，圖84聚類算法力2結(jié)果的均一性為,

-1-P5+一4+一2+一3+一11

51652531

有時(shí)，同質(zhì)性度量還用條件炳定義為力值,

W(%|C)

h=(8.16)

”(C)

式中，”（無(wú)|C）在給定類別條件下聚類簇的條件牖,

“（好）=-￡￡?duì)帯?（箸）

s=lk=l

“?=-￡?duì)?。喏?/p>

S=1

式中，K表示聚類算法42的簇?cái)?shù)。71總是實(shí)例數(shù)，％和以分別表示類G和簇心的實(shí)例

數(shù)，n邛是類Cs中樣本劃分給簇收的實(shí)例數(shù)。

77664444

"（C）=-57/。。（外）一77'°9（外）一7T‘°g（?T）-77，°。（?7）

乙,乙JL乙乙JL4人乙工乙JL4人

5,og

H(X|C)=--log一》?-^

乙X(I)-77logQ)og

Aio8G)-H,og?-Hiog0-H,og@-4,ogG)

osg0一舁。gG)-梟。g(I)-梟。g(I)-舁。gG)

21

00;3

lug-108,o8

五I組6?@H五叫(l)-A(S

完整性一U阡Y￡O_OEC>.

同類別的樣本被歸類到同一聚類簇中，則滿足完整性。相當(dāng)于召回率，即每個(gè)聚類中正

確分類的樣本數(shù)占該類別樣本的數(shù)量，

“17正確聚類為第S簇的樣本數(shù)量

n(8.17)

SJ第s簇的樣木總數(shù)

0-1

假設(shè)&5為噪聲簇，圖8.4聚類算法42結(jié)果前4簇的完整性為,

1[5423-

了41三7+:6+二4+:4.

有時(shí)，完整性度量也用條件端定義為九值，

H(C|K)

6=1—(8.18)

H(K)

同質(zhì)性和完整性都是基于兩類別劃分間的條件牖：已知某一類別劃分后，計(jì)算另一類別

劃分的不確定性程度，不確定性越小，兩個(gè)類別劃分越接近，力值或c值就越大。

V-Measure,是同質(zhì)性和完整性的調(diào)和平均值（harmcnicmean）,定義為

(1+夕)x九xc

v=(8.19)

Pxh+c

_蘭德指數(shù)和調(diào)整蘭德指數(shù)

考慮％=中任意兩個(gè)互異樣本%n和%m，按照它們?cè)诰垲愃惴?1和力2的聚類結(jié)

果中是否屬于同一個(gè)類簇，存在以下四種關(guān)系：

?SS：f和外在41和42都屬于同類簇，“同類同簇”

SS={(久八，%m)1(*71，%7n6G)A(Xn,XmG長(zhǎng)火)}.

?SD:j和在41屬于同類，但在力2屬于不同簇，“同類但不同簇”

SD={(%,Xm)l("n，WQ)A(%n€,XmEkH/)1?

?DS:曰和在41屬于不同類簇，但在42屬于同類簇，“不同類但同簇”

DS={(xn,xm)|(xnCCi，xmGCj,iH/)n(xn,xmG%Q}.

?DD:f和在Al和A2均屬于不同類簇，“不同類不同簇”

DD={(xn,xm)|(xnwG，feCj,i右力n(xne/,丁wg,k手/)}.

用a、b、c和d分別表示上述四種關(guān)系的數(shù)量。

接下來(lái)，結(jié)合圖8.4給出計(jì)算過(guò)程：

a=琦+C?+C/+廢+C：=21

其中，廉+戲來(lái)自于3。

b、c和d無(wú)法單獨(dú)計(jì)算，需要采用組合方式，

SS+DS：同一簇中任取兩個(gè)樣本點(diǎn)來(lái)自同類和非同類，

a+c=仁+球+弓+球+以=39

SS+SD,任意兩個(gè)同類樣木點(diǎn)被聚類到同簇和非同簇.

Q+b=0+Cf+§+6=48

a+b+c+d=C尹=210

可得a=21,b=27,c=18,d=144。

進(jìn)一步制定混淆矩陣［PairConfusionMatHx),

同簇非同簇同簇非同簇

同類a=\SS\b=\SD\a+b同類212748

非同類c=\DS\d=\DD\c+d非同類18144162

Q+Cb+d39171

基于a、b、c和d,定義如下四種指數(shù):

(I)蘭德指數(shù)(RandIndex,RZ)

a+da+da+d

DI=____________=_________=_____(8.20)

a+b+c+d~以

2

(2)JaccardCoefficient

JC=——?—(8.21)

a+b+c

(3)FewIkesandMallowsindex

(8.22)

上述三個(gè)系數(shù)的范圍是[0,1],值越大，劃分越好。

然而，即便隨機(jī)劃分，RI值也未必接近于0o于是1985年Hubert和Arabie提出調(diào)整

蘭德指數(shù)：假設(shè)聚類算法.41和42為隨機(jī)劃分，各類別和各簇的樣本數(shù)是固定的。

(4)調(diào)整蘭德指數(shù)(AdjustedRandIndex,ARI)

RI-E[R1]

ADI—_________L」(8.23)

max(R/)—E[Ri]

采用調(diào)整蘭德指數(shù)是為了消除隨機(jī)標(biāo)簽對(duì)于蘭德指數(shù)評(píng)估結(jié)果的影響。

計(jì)算4R/的另一種方法是根據(jù)列聯(lián)表(contingencylable),

Am=—產(chǎn)-以差明/布

(8.24)

|m+工明-9或“工明/④

調(diào)整蘭德指數(shù)范圍是負(fù)數(shù)代表聚類結(jié)果不好，越接近于I越好。

對(duì)任意數(shù)量的聚類中心和樣本數(shù)，隨機(jī)聚類的力R/都非常接近于0。

圖8.4示列的4R/的計(jì)算過(guò)程如下：

Q=WW或人=第+C?+廢+廢+廢=21

ks

Q+C=2球"=仁+球+C2+C2+廢=39

k

a+b=W吟=以+仁+廢+以=48

S

AR]_21-(39x48)/210

i[39+48]-(39x48)/210

上述四個(gè)指數(shù)越大表明：41和42聚類結(jié)果吻合程度越高，聚類效果越好。

L輪廓系數(shù)《砒。

的SC定義為，

1-/1,Q(Xn)<b(%n)

b(x)—0.(x)1"九1

SC(%n)=m算/7={Sa(xn)=b(xn)(8.25)

max{b(xn),a(xn)})

-775-I，?U?)>b(x)

Ia("ri)n

式中，

a(f)：為樣本辦到同一簇內(nèi)其它樣本的平均距離，體現(xiàn)了樣本f的簇內(nèi)不相似度,Q(x")

越小，表示％幾越應(yīng)該聚類到該族；

樣本/到簇Kk內(nèi)樣本的平均距離，反映樣本事與此的不相似度，b/Qn)越

大，表示xn越不應(yīng)該聚類到該簇Kk；

匕(今)=血加｛法1(%)，匕%(&)…，岳*(5)｝越大表示越不應(yīng)該屬于其它簇。

SC(馬)接近1,則說(shuō)明樣本f聚類合理；SC?！?接近-1,則說(shuō)明樣本Xn更應(yīng)該分類到其

它簇；若SC(f)近似為0,則說(shuō)明樣本功在兩個(gè)簇的邊界上。

所有樣本的SC的均值稱為聚類結(jié)果的輪廓系數(shù)。

一十K均值聚類

K均值聚類算法(K-maans)的基本思路：依據(jù)距慮相似度將樣本集聚類成K個(gè)簇，致使簇

內(nèi)樣本距離盡可能小，簇間距離盡可能大。

-…