最近在利用python跟著參考書(shū)進(jìn)行機(jī)器學(xué)習(xí)相關(guān)實(shí)踐，相關(guān)案例用到了ward算法，但是我理論部分用的是周志華老師的《西瓜書(shū)》，書(shū)上沒(méi)有寫(xiě)關(guān)于ward的相關(guān)介紹，所以自己網(wǎng)上查了一堆資料，都很難說(shuō)清楚ward算法，幸好最后在何曉群老師的《多元統(tǒng)計(jì)分析》這本書(shū)找到了比較清晰的說(shuō)法，所以總結(jié)出了一些心得，在這篇文章中記錄一下，同時(shí)，分享給廣大網(wǎng)友，大家一起探討一下，如果有誤，也請(qǐng)諒解。當(dāng)然，如果這篇文章還能入得了各位“看官”的法眼，麻煩點(diǎn)贊、關(guān)注、收藏，支持一下！

本文主要從三個(gè)方面進(jìn)行說(shuō)明：1、方差、離差平方和；2、ward算法原理；3、ward算法距離推導(dǎo)公式舉例說(shuō)明

一、方差、離差平方和

方差：

離差平方和：

對(duì)比方差和離差平方和公式，我們可以清楚的看到，離差平方和就是方差公式中的分子部分

另外，我對(duì)于離差平方和有兩點(diǎn)我要解釋一下：

第一點(diǎn)：可能很多人在網(wǎng)上看到的離差平方和公式跟我給出的有點(diǎn)區(qū)別，但是兩者是一樣的，只是網(wǎng)上大部分是拆開(kāi)并且化簡(jiǎn)過(guò)得，而我這個(gè)是和起來(lái)的，同樣因?yàn)槲襴ard算法看的是何曉群老師的書(shū)，所以跟書(shū)上的表達(dá)方式保持一致

第二點(diǎn)：可能很多人在網(wǎng)上看到的離差平方和的符號(hào)是ESS，但是我這里卻用SS表示，這個(gè)我覺(jué)得有必要跟大家說(shuō)清楚，ESS表示的是回歸平方和，SS才是離差平方和，兩者是完全不同的東西，對(duì)此若有質(zhì)疑，可以查看下面的鏈接，鏈接來(lái)源于百度百科：

離差平方和_百度百科 (baidu.com)；回歸平方和_百度百科 (baidu.com)

同時(shí)，對(duì)于方差，大家網(wǎng)上看到最多的形式應(yīng)該是上述的形式，但是在聚類(lèi)分析中，數(shù)據(jù)點(diǎn)常常是多維數(shù)據(jù)，所以很多人可能不太清楚對(duì)于多維數(shù)據(jù)方差該如何計(jì)算，下面舉個(gè)二維數(shù)據(jù)的例子，大家看一下。每個(gè)樣本通常由兩個(gè)特征（例如坐標(biāo)）組成，如(x1,x2)，所以方差如下：

其中表示第i個(gè)樣本點(diǎn)的第一個(gè)特征，表示樣本均值點(diǎn)的第一個(gè)特征? ?

從上述的公式，我們也就可以知道，離差平方和其實(shí)就等于每個(gè)樣本點(diǎn)到樣本均值點(diǎn)的距離的平方和

二、ward算法原理

ward算法認(rèn)為同類(lèi)樣本之間的離差平方和應(yīng)該盡量小，不同類(lèi)之間的離差平方和應(yīng)該盡量大。

假設(shè)，現(xiàn)在有n個(gè)樣本，我們要將他分成k類(lèi)，那么第t類(lèi)樣本的離差平和以及整個(gè)類(lèi)內(nèi)的離差平方和如下所示：

其中，?表示第t類(lèi)樣本的個(gè)數(shù)，表示第t類(lèi)樣本中的第i個(gè)樣本，表示第t類(lèi)樣本的均值點(diǎn)

ward算法的目標(biāo)就是使得聚類(lèi)完成之后整個(gè)類(lèi)內(nèi)的離差平方和達(dá)到極小，至于為什么，下面解釋一下：

從上面的公式中，我們可以看出來(lái)，整個(gè)類(lèi)內(nèi)的離差平方和就是對(duì)各類(lèi)樣本的離差平方和的求和，因?yàn)閣ard要求同類(lèi)樣本之間的離差平方和最小，即要求最小，所以整個(gè)類(lèi)內(nèi)的離差平方和也會(huì)達(dá)到最小

注意：整個(gè)類(lèi)內(nèi)的離差平方和不等于不同類(lèi)之間的離差平方和

引用何曉群老師《多元統(tǒng)計(jì)分析》一書(shū)中的原話(huà)：如果直接將所有分類(lèi)可能性的離差平方和算出來(lái)，然后找出使l達(dá)到極小的分類(lèi)，那么這個(gè)計(jì)算量是巨大的，對(duì)計(jì)算機(jī)要求是非常高的，因此，ward算法是一種尋找局部最優(yōu)解的方法，其思想就是先讓n個(gè)樣品各自成一類(lèi)，然后每次縮小一類(lèi)，每縮小一類(lèi)，離差平方和就要增大，選擇使增加最小的兩類(lèi)合并，直到所有的樣品歸為一類(lèi)為止

我們應(yīng)該都知道層次聚類(lèi)算法，本質(zhì)上都是通過(guò)距離來(lái)對(duì)樣本進(jìn)行聚類(lèi)操作，距離相近的簇（類(lèi)）會(huì)被劃分到同一簇中，所以，ward算法也為我們提供了一種簇間距的算法，幫助我們直接通過(guò)對(duì)簇間距的計(jì)算來(lái)近似獲得局部最優(yōu)解，公式如下：

np表示Gp類(lèi)中樣本個(gè)數(shù)，nk表示Gk類(lèi)中的樣本個(gè)數(shù)，nr表示Gr類(lèi)中的樣本個(gè)數(shù)

可能有些小伙伴對(duì)于這個(gè)上面的距離遞推公式看的很迷，所以下面我會(huì)借用SciPy幫助文檔例子進(jìn)行舉例說(shuō)明

三、ward算法距離推導(dǎo)公式舉例說(shuō)明

SciPy幫助文檔例子的代碼如下：

from scipy.cluster.hierarchy import dendrogram, linkage
from matplotlib import pyplot as plt
X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]
Z = linkage(X, 'ward')
fig = plt.figure(figsize=(25, 10))
dn = dendrogram(Z)
print(Z)
plt.show()

通過(guò)代碼我們知道輸入的是數(shù)組X，輸出的是鏈接數(shù)組Z，其中X是一個(gè)8行1列的二維數(shù)組，每一行數(shù)據(jù)都代表著一個(gè)位置標(biāo)記，同時(shí)，根據(jù)網(wǎng)上大佬的說(shuō)法Z是一個(gè)n行4列的數(shù)組，前兩列表示要聚類(lèi)的簇的編號(hào)，第三列表示兩個(gè)即將聚類(lèi)的簇之間的距離，第四列表示聚類(lèi)所得的新簇中含有的樣本個(gè)數(shù)

Z的輸出如下：

對(duì)應(yīng)于第一行數(shù)據(jù)可能有些小伙伴會(huì)覺(jué)得疑惑，5、6是哪里來(lái)的？因?yàn)樯衔闹幸呀?jīng)說(shuō)過(guò)了ward算法會(huì)先n個(gè)樣本各成一類(lèi)，所以5、6代表數(shù)組X的8個(gè)樣本中編號(hào)為5和6的樣本，數(shù)組X的樣本編號(hào)對(duì)照表如下：

X	2	8	0	4	1	9	9	0
簇編號(hào)	0	1	2	3	4	5	6	7

根據(jù)表可以知道，簇編號(hào)為5、6代表的樣本就是兩個(gè)位置為9的樣本

同時(shí)，編號(hào)5、6的簇又會(huì)聚類(lèi)成會(huì)編號(hào)為8的新簇，同理，依次遞推，編號(hào)2、7的樣本又會(huì)聚類(lèi)成會(huì)聚類(lèi)成編號(hào)為9的新簇……結(jié)果如下所示：

進(jìn)行聚類(lèi)操作的簇編號(hào)	5、6	2、7	0、4	1、8	9、10	3、12	11、13
新聚類(lèi)的簇編號(hào)	8	9	10	11	12	13	14

Z的前兩列我已經(jīng)通過(guò)表格說(shuō)明了，但是相信很多人卡就卡在不知道第三列數(shù)據(jù)是怎么求的，

所以下面對(duì)Z的第三列數(shù)據(jù)進(jìn)行說(shuō)明：

重點(diǎn)來(lái)了！！！！

第一行數(shù)據(jù)：由第一個(gè)表可知編號(hào)為5、6的簇，且都僅包含一個(gè)樣本，所以樣本的位置就代表簇的位置，因此兩簇的位置都是9，兩簇的距離

第二行數(shù)據(jù)：由第一個(gè)表可知編號(hào)為2、7的簇，且都僅包含一個(gè)樣本，所以樣本的位置就代表簇的位置，因此兩簇的位置都是0，兩簇距離

第三行數(shù)據(jù)：由第一個(gè)表可知編號(hào)為0、4的簇，且都僅包含一個(gè)樣本，所以樣本的位置就代表簇的位置，因此兩簇的位置分別是2和1，兩簇的距離

第四行數(shù)據(jù)：由第一個(gè)表可知編號(hào)為1簇僅有一個(gè)樣本，由表二可知編號(hào)為8的簇是由簇5和簇6聚類(lèi)而來(lái)，其中含有兩個(gè)樣本，所以，為了計(jì)算簇1和簇8之間的距離，這時(shí)就需要用到上述所說(shuō)到的ward算法的距離遞推公式，計(jì)算流程如下：

?注意：Dw后面括號(hào)中的數(shù)字代表簇編號(hào)

第五行數(shù)據(jù)：由第二個(gè)表可知編號(hào)為9的簇是由簇2和簇7聚類(lèi)而來(lái)，其中含有兩個(gè)樣本，編號(hào)為10的簇是由簇0和簇4聚類(lèi)而來(lái)，其中含有兩個(gè)樣本，所以，為了計(jì)算簇9和簇10之間的距離，這時(shí)就需要用到上述所說(shuō)到的ward算法的距離遞推公式，計(jì)算流程如下：

?所以：

?因?yàn)楸容^懶，所以第六行與第七行中的第三列數(shù)據(jù)我就不再詳細(xì)列計(jì)算過(guò)程了，大家看了第四行和第五行的計(jì)算過(guò)程應(yīng)該也能明白如何使用ward的距離推導(dǎo)公式了

參考文章：

何曉群.多元統(tǒng)計(jì)分析(第五版)[M].中國(guó)人民大學(xué)出版社,2019.

Python層次聚類(lèi)sci.cluster.hierarchy.linkage函數(shù)詳解_scipy.cluster.hierarchy-CSDN博客