内网网站如何建设方案,如何做阿里巴巴的网站,云南信息港,昆明 网站 制作最近在利用python跟着参考书进行机器学习相关实践#xff0c;相关案例用到了ward算法#xff0c;但是我理论部分用的是周志华老师的《西瓜书》#xff0c;书上没有写关于ward的相关介绍#xff0c;所以自己网上查了一堆资料#xff0c;都很难说清楚ward算法#xff0c;幸…最近在利用python跟着参考书进行机器学习相关实践相关案例用到了ward算法但是我理论部分用的是周志华老师的《西瓜书》书上没有写关于ward的相关介绍所以自己网上查了一堆资料都很难说清楚ward算法幸好最后在何晓群老师的《多元统计分析》这本书找到了比较清晰的说法所以总结出了一些心得在这篇文章中记录一下同时分享给广大网友大家一起探讨一下如果有误也请谅解。当然如果这篇文章还能入得了各位“看官”的法眼麻烦点赞、关注、收藏支持一下
本文主要从三个方面进行说明1、方差、离差平方和2、ward算法原理3、ward算法距离推导公式举例说明
一、方差、离差平方和
方差 离差平方和 对比方差和离差平方和公式我们可以清楚的看到离差平方和就是方差公式中的分子部分
另外我对于离差平方和有两点我要解释一下
第一点可能很多人在网上看到的离差平方和公式跟我给出的有点区别但是两者是一样的只是网上大部分是拆开并且化简过得而我这个是和起来的同样因为我ward算法看的是何晓群老师的书所以跟书上的表达方式保持一致
第二点可能很多人在网上看到的离差平方和的符号是ESS但是我这里却用SS表示这个我觉得有必要跟大家说清楚ESS表示的是回归平方和SS才是离差平方和两者是完全不同的东西对此若有质疑可以查看下面的链接链接来源于百度百科
离差平方和_百度百科 (baidu.com)回归平方和_百度百科 (baidu.com)
同时对于方差大家网上看到最多的形式应该是上述的形式但是在聚类分析中数据点常常是多维数据所以很多人可能不太清楚对于多维数据方差该如何计算下面举个二维数据的例子大家看一下。每个样本通常由两个特征例如坐标组成如(x1,x2)所以方差如下 其中表示第i个样本点的第一个特征表示样本均值点的第一个特征
从上述的公式我们也就可以知道离差平方和其实就等于每个样本点到样本均值点的距离的平方和
二、ward算法原理
ward算法认为同类样本之间的离差平方和应该尽量小不同类之间的离差平方和应该尽量大。
假设现在有n个样本我们要将他分成k类那么第t类样本的离差平和以及整个类内的离差平方和如下所示 其中 表示第t类样本的个数表示第t类样本中的第i个样本表示第t类样本的均值点
ward算法的目标就是使得聚类完成之后整个类内的离差平方和达到极小至于为什么下面解释一下
从上面的公式中我们可以看出来整个类内的离差平方和就是对各类样本的离差平方和的求和因为ward要求同类样本之间的离差平方和最小即要求最小所以整个类内的离差平方和也会达到最小
注意整个类内的离差平方和不等于不同类之间的离差平方和
引用何晓群老师《多元统计分析》一书中的原话如果直接将所有分类可能性的离差平方和算出来然后找出使l达到极小的分类那么这个计算量是巨大的对计算机要求是非常高的因此ward算法是一种寻找局部最优解的方法其思想就是先让n个样品各自成一类然后每次缩小一类每缩小一类离差平方和就要增大选择使增加最小的两类合并直到所有的样品归为一类为止
我们应该都知道层次聚类算法本质上都是通过距离来对样本进行聚类操作距离相近的簇类会被划分到同一簇中所以ward算法也为我们提供了一种簇间距的算法帮助我们直接通过对簇间距的计算来近似获得局部最优解公式如下 np表示Gp类中样本个数nk表示Gk类中的样本个数nr表示Gr类中的样本个数
可能有些小伙伴对于这个上面的距离递推公式看的很迷所以下面我会借用SciPy帮助文档例子进行举例说明
三、ward算法距离推导公式举例说明
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()
通过代码我们知道输入的是数组X输出的是链接数组Z其中X是一个8行1列的二维数组每一行数据都代表着一个位置标记同时根据网上大佬的说法Z是一个n行4列的数组前两列表示要聚类的簇的编号第三列表示两个即将聚类的簇之间的距离第四列表示聚类所得的新簇中含有的样本个数
Z的输出如下 对应于第一行数据可能有些小伙伴会觉得疑惑5、6是哪里来的因为上文中已经说过了ward算法会先n个样本各成一类所以5、6代表数组X的8个样本中编号为5和6的样本数组X的样本编号对照表如下
X28041990簇编号01234567
根据表可以知道簇编号为5、6代表的样本就是两个位置为9的样本
同时编号5、6的簇又会聚类成会编号为8的新簇同理依次递推编号2、7的样本又会聚类成会聚类成编号为9的新簇……结果如下所示
进行聚类操作的簇编号5、62、70、41、89、103、1211、13新聚类的簇编号891011121314
Z的前两列我已经通过表格说明了但是相信很多人卡就卡在不知道第三列数据是怎么求的
所以下面对Z的第三列数据进行说明
重点来了
第一行数据由第一个表可知编号为5、6的簇且都仅包含一个样本所以样本的位置就代表簇的位置因此两簇的位置都是9两簇的距离
第二行数据由第一个表可知编号为2、7的簇且都仅包含一个样本所以样本的位置就代表簇的位置因此两簇的位置都是0两簇距离
第三行数据由第一个表可知编号为0、4的簇且都仅包含一个样本所以样本的位置就代表簇的位置因此两簇的位置分别是2和1两簇的距离
第四行数据由第一个表可知编号为1簇仅有一个样本由表二可知编号为8的簇是由簇5和簇6聚类而来其中含有两个样本所以为了计算簇1和簇8之间的距离这时就需要用到上述所说到的ward算法的距离递推公式计算流程如下 注意Dw后面括号中的数字代表簇编号
第五行数据由第二个表可知编号为9的簇是由簇2和簇7聚类而来其中含有两个样本编号为10的簇是由簇0和簇4聚类而来其中含有两个样本所以为了计算簇9和簇10之间的距离这时就需要用到上述所说到的ward算法的距离递推公式计算流程如下 所以 因为比较懒所以第六行与第七行中的第三列数据我就不再详细列计算过程了大家看了第四行和第五行的计算过程应该也能明白如何使用ward的距离推导公式了
参考文章
何晓群.多元统计分析(第五版)[M].中国人民大学出版社,2019.
Python层次聚类sci.cluster.hierarchy.linkage函数详解_scipy.cluster.hierarchy-CSDN博客
