層次聚類分支
1）分裂法
從上到下對(duì)大類別進(jìn)行分割
2）凝聚法
從下到上對(duì)小類別進(jìn)行聚合
層次聚類優(yōu)點(diǎn)
kmeans中需要人工確定聚類類別K基于初始化聚類中心包竹，這將會(huì)很大程度上影響聚類效果审姓。
而層次聚類避免了這一問(wèn)題赴肚。
分裂法
分裂法指的是初始時(shí)將所有的樣本歸為一個(gè)類簇，然后依據(jù)某種準(zhǔn)則進(jìn)行逐漸的分裂，直到達(dá)到某種條件或者達(dá)到設(shè)定的分類數(shù)目辰斋。用算法描述：
輸入：樣本集合D代芜，聚類數(shù)目或者某個(gè)條件（一般是樣本距離的閾值埠褪，這樣就可不設(shè)置聚類數(shù)目）
輸出：聚類結(jié)果
1.將樣本集中的所有的樣本歸為一個(gè)類簇；
repeat：
2.在同一個(gè)類簇（計(jì)為c）中計(jì)算兩兩樣本之間的距離挤庇，找出距離最遠(yuǎn)的兩個(gè)樣本a,b钞速；
3.將樣本a，b分配到不同的類簇c1和c2中嫡秕；
4.計(jì)算原類簇（c）中剩余的其他樣本點(diǎn)和a渴语，b的距離，若是dis(a)<dis(b)昆咽，則將樣本點(diǎn)歸到c1中驾凶，否則歸到c2中；
util： 達(dá)到聚類的數(shù)目或者達(dá)到設(shè)定的條件
舉例：
在平面上有6個(gè)點(diǎn)：p0(1,1), p1(1,2), p2(2,2), p3(4,4), p4(4,5), p5(5,6)潮改，我現(xiàn)在需要對(duì)這6個(gè)點(diǎn)進(jìn)行聚類狭郑，對(duì)應(yīng)著上邊的步驟我可以這樣做：
將所有的點(diǎn)歸為一個(gè)類簇c（p0,p1,p2,p3,p4,p5）
-
repeat:
1）在類簇c中計(jì)算他們的距離（簡(jiǎn)單的歐式距離）我們可以得到：
2）確定最遠(yuǎn)的兩個(gè)點(diǎn)：
首輪計(jì)算得到距離最遠(yuǎn)的兩個(gè)點(diǎn)為 p0 和 p5，
3）確定簇：
將 p0 分配到類簇 c1汇在，將 p5 分配到類簇c2翰萨；
4）為每個(gè)簇分配點(diǎn)：
查表可以看出，剩余的點(diǎn)中p1和p2與p0的距離小糕殉，所以將它們兩個(gè)歸到類簇c1中亩鬼；p3和p4與p5的距離小，所以將它們兩個(gè)歸到類簇c2中阿蝶。這樣我們得到了一次新的聚類 結(jié)果c1=（p1,p2,p3）,c2=(p3,p4,p5); Util：
若僅要求聚類為兩個(gè)類別雳锋，則聚類結(jié)束。
若要求一個(gè)簇中最大樣本間距離不超過(guò)sqrt(2)羡洁，那么需要返回repeat繼續(xù)聚類：
因?yàn)閏1中的樣本的距離都不大于sqrt（2）玷过，所以不需要再分了；而類簇c2中的dis(p3,p5)=sqrt(5)>sqrt(2),還需要繼續(xù)分筑煮，c2最后分聚類成兩個(gè)類（p3,p4）和(p5),這樣我們最終得到了三個(gè)類簇（p1,p2,p3）辛蚊、(p3,p4)和（P5）。
凝聚法
凝聚法與分裂法整好相反真仲，是先將每個(gè)樣本點(diǎn)看做一個(gè)簇袋马，然后再根據(jù)某種規(guī)則對(duì)小的類簇進(jìn)行合并，直到達(dá)到距離閾值的條件或者達(dá)到設(shè)定的分類數(shù)秸应。
算法流程如下：
輸入：樣本集合D虑凛，聚類數(shù)目或者某個(gè)條件（一般是樣本距離的閾值碑宴，這樣就可不設(shè)置聚類數(shù)目）
輸出：聚類結(jié)果
將樣本集中的所有的樣本點(diǎn)都當(dāng)做一個(gè)獨(dú)立的類簇；
repeat：
1）.計(jì)算兩兩類簇之間的距離桑谍，找到距離最小的兩個(gè)類簇c1和c2延柠；
2）.合并類簇c1和c2為一個(gè)類簇；
util： 達(dá)到聚類的數(shù)目或者達(dá)到設(shè)定的條件
上述算法流程中锣披，對(duì)于計(jì)算兩兩簇之間的距離有較多的方法：
1）取兩個(gè)簇中最近的兩個(gè)樣本點(diǎn)作為簇間距離
2）取兩個(gè)簇中最遠(yuǎn)的兩個(gè)樣本點(diǎn)作為簇間距離
3）將兩個(gè)簇中兩兩點(diǎn)間的距離均值作為簇間距離
4）將兩個(gè)簇中兩兩點(diǎn)間的距離的中位數(shù)作為簇間距離
5）將兩個(gè)簇中兩兩點(diǎn)間的距離求和除以除以兩個(gè)簇的樣本總數(shù)
轉(zhuǎn)載注明：http://www.reibang.com/p/cabab63f7a00
