凝聚法分層聚類中有一堆方法可以用來算兩點(pair)之間的距離：歐式，歐式平方，manhattan等，還有一堆方法可以算類(cluster)與類之間的距離，什么single-linkage、complete-linkage、還有這個ward linkage。(即最短最長平均，離差平方和)

其他的好像都挺好理解，就是最后這個有點麻煩。。。

這個方法說白了叫離差平方和(這是個啥？)。是ward寫那篇文章時候舉的一個特例。這篇文章是說分層凝聚聚類方法的一個通用流程。在選擇合并類與類時基于一個object function optimise value，這個object function可以是任何反應研究目的的方程，所以許多標準的方法也被歸入了。為了闡明這個過程，ward舉了一個例子，用的object function 是error sum of squares(ESS)，這個例子就成為ward's method。

找了N多資料，終于把這個算法的過程搞清楚了。首先輸入的是一個距離矩陣，知道每兩個點之間的距離。然后初始化是每個點做為一個cluster，假設總共N組，此時每個組內的ESS都是0，ESS的公式，如下(從原稿《Hierarchical Grouping To Optimize An Objective Function》上摘的)：

我當時還有點蒙ESS是個啥？——我現在知道了，凡是蒙的都是概率沒學好(我是說我)……先從wiki上轉個公式過來：

這是方差的公式，寫的再通俗點，就是：

等號兩邊同時乘上n，好了，你應該知道ESS是啥了——ESS就是【方差×n】！so easy了～～

但是等下——這看起來是個一維的公式啊——因為你已經知道ESS是【方差×n】了，那多維的還不會算嗎？先求所有點的均值點

，然后再算所有點到這個均值點(central)的距離(距離公式你得自己定，見開頭，但是最后算出來就是一個數)，然后把所有距離平方后加起來(此時即為方差乘上n)，就得到ESS了。

說了半天光說ESS了，列位看官，人只有一張嘴，故ESS此處按下不表，接著說ward method。ward method是要求每次合并后ESS的增量最小，這怎么講呢？還是上圖吧(圖是從youtube上的一個教程里截的)：

只看最下面ward's method的兩個圖好了，先看下面的圖，合并前紅色組和黃色組分別能算各自的ESS，總的ESS是什么呢？很簡單，加起來就好了，即：

ESS(總-合并前)=ESS(紅)+ESS(黃)+ESS(其他沒畫出來的組)

如果合并這兩個組，則可以作為一個新組再算一個ESS，此時

ESS(總-合并后)=ESS(紅黃)+ESS(其他沒畫出來的組)

你注意這里還沒有真的合并，只是算了一下合并紅黃兩組的“成本”(即：ESS(總-合并后)-ESS(總-合并前)，當然這個成本肯定是增加的)，如果總共有N個組，必須把每兩個組合并的成本都算一遍，也就是算N×(N-1)/2個數出來，然后找里面合并后成本最小的兩組合并。然后再重復這個過程。

我說清楚了吧！？

嗯，至于畫的那個樹狀圖的高度，可以認為是上面說的這個“成本”。

對了，還得說一下這個公式：

啥意思呢，就是說，如果用ward's method來度量兩個cluster之間的距離，那么兩個cluster之間的距離就是把這兩個cluster合并后新cluster的ESS，其中x就表示合并前兩個cluster中所有點，而

就是合并后那個新cluster的中心點(均值點)，

就表示每個點x到中心點的距離，平方后加起來，就是ESS了。

好了，總結一下，ward's method是凝聚法分層聚類中一種度量cluster之間距離的方法。按照這個方法，任意兩個cluster之間的距離就是這兩個cluster合并后新cluster的ESS

摘要: ward linkage method是什么不介紹了，只說下怎么算，有一個快速的計算方法叫Lance-Williams Algorithm可以大大簡化ward method的計算

ward's method是分層聚類凝聚法的一種常見的度量cluster之間距離的方法，其基本過程是這樣的(參考：http://blog.sciencenet.cn/blog-2827057-921772.html?)

計算每個cluster的ESS

計算總的ESS

枚舉所有二項cluster【N個cluster是N*(N-1)/2個二項集】，計算合并這兩個cluster后的總ESS值

選擇總ESS值增長最小的那兩個cluster合并

重復以上過程直到N減少到1

這個方法其實效率比較低，特別是算cluster的ESS值還要先求均值點，然后算距離的平方再求和，不過有一個快速的計算方法叫Lance-Williams Algorithm可以大大簡化ward method的計算。先來一個圖(來源：https://www.youtube.com/watch?v=aXsaFNVzzfI

然后你其實可以發現，這個算法簡化的是合并后更新ESS的那部分過程，比如有ABCDE五個cluster，合并了AB，那么后面要更新CDE到這個AB的距離，怎么算？ESS唄——平方和——好復雜！

那用這個新算法怎么算？答，新算法可以不用ESS的公式計算ESS，直接套用上面那個公式(注意最后絕對值里面應該一個i一個j，他寫錯了)。初始的ESS由兩點之間的距離決定——所以就是說完全不需要算ESS了！

好了，試著寫一下算法：輸入是一個距離矩陣，輸出是一個合并序列[(cluster1id, cluster2id, distance), ...]

clusterDistance=dict() #存放cluster之間的距離，形如'1-2':3表示cluster1與cluster2之間的距離為3

clusterMap=dict() #存放cluster的情況，形如'1':4表示cluster1里面有4個元素(樣本)

clusterCount=0 #每合并一次生成新的序號來命名cluster

defward_linkage_method(distance_matrix):

N=len(distance_matrix)

clusterCount=N-1

for i in range(0,N-1):

for j in range(i,N):

name=getName(i,j)

clusterDistance[name]=distance_matrix[i][j]

for k in range(0,N):

clusterMap[k]=1

while True:

# 查找距離最短的兩個cluster

# clusterDistance里面有冗余(即合并后之前的距離仍在，

# 所以循環以clusterMap為準，這個里面沒有冗余。

tmp=max(clusterDistance.values())

clusterList = clusterMap.keys()

clusterListLength=len(clusterList)

for iii in range(0, clusterListLength-1):

for jjj in range(iii+1, clusterListLength):

name=getName(clusterList[iii], clusterList[jjj])

if tmp > clusterDistance[name]:

i=iii

j=jjj

tmp=clusterDistance[name]

ni=clusterMap[i] # 第i個cluster內的元素數

nj=clusterMap[j]

del clusterMap[i] # 刪掉原來的cluster

del clusterMap[j]

clusterCount+=1 # 新增新的cluster

clusterMap[clusterCount]=ni+nj #新cluster的元素數是之前的總和

print i,j,'->',clusterCount,tmp # 輸出合并信息:i,j合并為clusterCount，合并高度(距離)為tmp

if len(clusterMap)==1:break # 合并到只剩一個集合為止，然后退出

# 更新沒合并的cluster到新合并后的cluster的距離

for k in clusterMap.keys():

if k==clusterCount:continue

else: # 計算新的距離

nk=clusterMap[k]

alpha_i=(ni+nk)/(ni+nj+nk)

alpha_j=(nj+nk)/(ni+nj+nk)

beta= -nk/(ni+nj+nk)

newDistance = alpha_i * clusterDistance[getName(i,k)]

newDistance += alpha_j * clusterDistance[getName(j,k)]

newDistance += beta * clusterDistance[getName(i,j)]

# 把新的距離加入距離集合

clusterDistance[getName(clusterCount,k,'.')]=newDistance

defgetName(i,j):

t=[i,j]

t.sort()

return t[0]+'-'+t[1]

當然了，這段代碼只是一個示意，可以改進的地方還很多。

轉載本文請聯系原作者獲取授權，同時請注明本文來自宋景和科學網博客。

鏈接地址：http://blog.sciencenet.cn/blog-2827057-921772.html

總結

以上是生活随笔為你收集整理的凝聚式层次聚类 java_凝聚法层次聚类之ward linkage method的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。