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

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

一、方差、離差平方和

方差：

離差平方和：

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

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

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

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

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

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

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

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

二、ward算法原理

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

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

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

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

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

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

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

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

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

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

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

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()

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

Z的輸出如下：

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

X	2	8	0	4	1	9	9	0
簇編號	0	1	2	3	4	5	6	7

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

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

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

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

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

重點(diǎn)來了！！！！

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

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

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

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

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

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

?所以：

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

參考文章：

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

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