無(wú)監(jiān)督學(xué)習(xí)和聚類(lèi)PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 無(wú)監(jiān)督學(xué)習(xí)和聚類(lèi)無(wú)監(jiān)督學(xué)習(xí)和聚類(lèi) 第1頁(yè)/共61頁(yè) 第2頁(yè)/共61頁(yè) 是通常說(shuō)的無(wú)監(jiān)督學(xué)習(xí)方法。 第3頁(yè)/共61頁(yè) 第4頁(yè)/共61頁(yè) 第5頁(yè)/共61頁(yè) 身，無(wú)標(biāo)號(hào)。如果發(fā)現(xiàn)數(shù)據(jù)集呈 現(xiàn)某種聚集性，則可按自然的聚 集性分類(lèi)，但不以與某種預(yù)先的 分類(lèi)標(biāo)號(hào)為目的。 第6頁(yè)/共61頁(yè) n 方法屬于非監(jiān)督學(xué)習(xí)方法。 第7頁(yè)/共61頁(yè) 第8頁(yè)/共61頁(yè) 第9頁(yè)/共61頁(yè) 分類(lèi)樣本就被劃分成同一類(lèi)，稱(chēng) 為單峰子類(lèi)。 第10頁(yè)/共61頁(yè) 第11頁(yè)/共61頁(yè) 第12頁(yè)/共61頁(yè) 第13頁(yè)/共61頁(yè) 第14頁(yè)/共61頁(yè) 第15頁(yè)/共61頁(yè) u對(duì)每個(gè)得到的子集(聚類(lèi))重復(fù)上 述過(guò)程，直到每個(gè)集不能再分(為

2、 單峰)為止。 第16頁(yè)/共61頁(yè) 1 argm ax() L k tJk 取主值，使 J(k)最大時(shí) 的K值 第17頁(yè)/共61頁(yè) 2 11 (|)(|)() cc ij ij JfKfKpd xxxx 1 (|)(,) i ii K fKK N x xx x 第18頁(yè)/共61頁(yè) argm ax(|), kikj i JfKKxx 第19頁(yè)/共61頁(yè) n相似性度量 n樣本樣本聚類(lèi) (,) ij Kx (,)() () T ijijij x xxxxx 第20頁(yè)/共61頁(yè) 最小誤差平方和準(zhǔn)則 1 ( y,) i c i iK J y m 第21頁(yè)/共61頁(yè) 第22頁(yè)/共61頁(yè) 第23頁(yè)/共61頁(yè)

3、 第24頁(yè)/共61頁(yè) 第25頁(yè)/共61頁(yè) 第26頁(yè)/共61頁(yè) 第27頁(yè)/共61頁(yè) 第28頁(yè)/共61頁(yè) 代表點(diǎn) 11 (,)()() ii cc T iii iKiK J xx x mxmym 第29頁(yè)/共61頁(yè) 1.初始化：選擇c個(gè)代表點(diǎn)p1, p2, ,pc 2.建立c個(gè)空聚類(lèi)列表： K1, K2, ,Kc 3.按照最小距離法則逐個(gè)對(duì)樣本x 進(jìn)行分類(lèi)： 4.計(jì)算J及用各聚類(lèi)列表計(jì)算聚類(lèi)均 值，并用來(lái)作為各聚類(lèi)新的代表 點(diǎn)（更新代表點(diǎn)） 5.若J不變或代表點(diǎn)未發(fā)生變化，則 停止。否則轉(zhuǎn)2。 arg(,), add(,)m in ij i jKx px 1 (,) i c i iK J x x

4、p 第30頁(yè)/共61頁(yè) 第31頁(yè)/共61頁(yè) 第32頁(yè)/共61頁(yè) 第33頁(yè)/共61頁(yè) 逐個(gè)樣 本修正法成批樣本修正 法 n聚類(lèi)數(shù)目的動(dòng)態(tài)決定 argm in(,), ij i jy py 第34頁(yè)/共61頁(yè) nK-算法舉例 例：已知有20個(gè)樣本，每個(gè)樣本有2個(gè)特征，數(shù)據(jù)分布如下 圖 樣本序號(hào)樣本序號(hào) x1x2x3x4x5x6x7x8x9x10 特征特征x10101212367 特征特征x20011122266 x11x12x13x14x15x16x17x18x19x20 8678978989 6777788899 第35頁(yè)/共61頁(yè) 1 5 4 3 1 2 6 6 5432 1 X 10 10

5、9 9 8 8 7 7 0 2 X 1 x 2 x 3 x 4 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 x 17 x 18 x 19 x 20 x 5 x 第36頁(yè)/共61頁(yè) 11 12 1112 11 21 00 (1)0 00 01 (1)1 00 (1)(1) (1) 10 (1)1 00 xZ xZ xZxZ xZ xZ 第二步：（ ）（ ） （ ）（ ） 因?yàn)?所以 （ ）（ ） 第一步：令K=2，選初始聚類(lèi)中心為 1122 (1)(0, 0);(1)(1, 0) TT ZxZx 第37頁(yè)/共61頁(yè) 22 2122 22

6、313231 414242 5620 56202 113 1 11 (1)( )( )0 00 (1)(1) , (1) (1)1(1)2,(1) (1)2(1 (1)(,), (1) )1,(1) . .(1) xZ xZxZ xZ xZxZxZ xZxZxZ xxx xxxZ Gxx G 因?yàn)?所以 同理 同樣把所有、與第二個(gè)聚類(lèi)中心的距 離計(jì)算出來(lái)，判斷 一、 二、 、都屬于 因此分為兩類(lèi)： 24520 12 (,.) 2,18 xxxx NN 第38頁(yè)/共61頁(yè) n第三步：根據(jù)新分成的兩類(lèi)建立新的聚類(lèi)中心 1(1) 113 1 00 111 (2)()( )( ) 0122 0 1 (

7、 )(0,0.5) 12 x T G ZXxx N 2 22452 ( 0 2 1) 11 (2)(.) 18 (5.67,5.33) xG T ZXxxxx N 第四步： 轉(zhuǎn)第二步。 第二步：重新計(jì)算 到z1(2) , z2(2) 的距離，把它們歸為最近聚類(lèi)中心，重新分為兩 類(lèi)， (2)(1),1,2() JJ ZZJ新舊聚類(lèi)中心不等 1220 ,.,x xx 第39頁(yè)/共61頁(yè) n第三步，更新聚類(lèi)中心 1 11238 (2) 1 11 (3)(.) 8 (1.25,1.13) x G T ZXxxxx N 2 291020 (2) 2 11 (3)(.) 12 (7.67,7.33) x

8、G T ZXxxx N 11281 (2)(,.,),8GxxxN 2910202 (2)(,.,),12Gx xxN 第40頁(yè)/共61頁(yè) n第四步， n第二步， n第三步，更新聚類(lèi)中心 (3)(2),1,2, jj ZZj因轉(zhuǎn)第二步 122012 1220 1128 29102012 ,.,(3),(3) ,., (4)(,.,) (4)(,.,),8,12 x xxZZ x xx Gx xx GxxxNN 重新計(jì)算到的距離， 分別把歸于最近的那個(gè)聚類(lèi)中心， 重新分為二類(lèi) 11 22 (4)(3)(1.25,1.13) (4)(3)(7.67,7.33) T T ZZ ZZ 計(jì)算結(jié)束。 第4

9、1頁(yè)/共61頁(yè) 上機(jī)作業(yè)上機(jī)作業(yè) n已知十個(gè)樣本，每個(gè)樣本2個(gè)特 征，數(shù)據(jù)如下： n用K-均值算法分成3類(lèi)，編程上 機(jī)，并畫(huà)出分類(lèi)圖。 樣本序號(hào)樣本序號(hào)1 2 3 4 5 6 7 8 9 10 x10 1 2 4 5 5 6 1 1 1 x20 1 1 3 3 4 5 4 5 6 第42頁(yè)/共61頁(yè) 第43頁(yè)/共61頁(yè) 第44頁(yè)/共61頁(yè) (,) i Kx 第45頁(yè)/共61頁(yè) argm in(,), add(,) ij i jKLxx 1 (,) i c i iK JK y x 第46頁(yè)/共61頁(yè) 1 1 / 2 / 2 11 ()exp()() 2 (2) T iiii d j K xxmx

10、m 1 11 (,)()()log 22 T iiiij K xxmxm 第47頁(yè)/共61頁(yè) n近鄰函數(shù) 11 NN wij ij La 第48頁(yè)/共61頁(yè) , m in() kilj ijkl KK a yy m axm axm axm ax m axm axm ax m axm axm ax m axm axm axm ax ()(), , , , ijiijjijiijj ijiijiijj ij ijjijiijj ijijijiijj aaifaa aifaa b aifaa aaifaa 第49頁(yè)/共61頁(yè) bij ij Lb 1.計(jì)算距離矩陣 2.用距離矩陣計(jì)算近鄰矩陣M 3.計(jì)

11、算近鄰函數(shù)矩陣L 4.在L 中，每個(gè)點(diǎn)與其最近鄰連接，形成初始的劃分 5.對(duì)每?jī)蓚€(gè)類(lèi)計(jì)算rij 和aimax，ajmax ，只要rij 小于 aimax、ajmax中的任何一個(gè)，就合并兩類(lèi)（建立連 接）。重復(fù)至沒(méi)有新的連接發(fā)生為止 wb JLL 第50頁(yè)/共61頁(yè) 第51頁(yè)/共61頁(yè) y1y2y3y4 y5 y6 100 90 80 70 60 50 40 1-水平 - 2-水平 - 3-水平 - 4-水平 - 5-水平 - 6-水平 - 第52頁(yè)/共61頁(yè) (,)m in(,) i j ij K K KK x y x y (,)m ax(,) i j ij K K KK x y x y (,)(,) ijij KKmm 第53頁(yè)/共61頁(yè) 舉例：如下圖所示 1.按距離定義層次聚類(lèi) 2. 作距離矩陣D(0) 3 G 1 G 2 G 5 G 4 G 6 G x 第54頁(yè)/共61頁(yè) G1G2G3G4G5 G29 G3116 G4491664 G5254364 G664258119 第55頁(yè)/共61頁(yè) n3.求最小元素： n4.把G1,G3合并G7=(1,3) G4,G6合并G8=(4,6) n5.作距離矩陣D(1) 1 6431 dd G7G2G8 G29 G84916 G5254