2024年5月1日发(作者：格力空调的价格大概多少钱)
1. 层次聚类
层次聚类算法与之前所讲的顺序聚类有很大不同，它不再产生单一聚类，而是产生一
个聚类层次。说白了就是一棵层次树。介绍层次聚类之前，要先介绍一个概念——嵌套聚
类。讲的简单点，聚类的嵌套与程序的嵌套一样，一个聚类中R1包含了另一个R2，那这
就是R2嵌套在R1中，或者说是R1嵌套了R2。具体说怎么算嵌套呢？聚类
R1={{x1,x2},{x3},{x4,x5}嵌套在聚类R2={{x1,x2,x3},{x4,x5}}中，但并不嵌套在聚类
R3={{x1,x4},{x3},{x2,x5}}中。
层次聚类算法产生一个嵌套聚类的层次，算法最多包含N步，在第t步，执行的操作
就是在前t-1步的聚类基础上生成新聚类。主要有合并和分裂两种实现。我这里只讲合并，
因为前一阶段正好课题用到，另外就是合并更容易理解和实现。当然分裂其实就是合并的
相反过程。
令g(Ci,Cj)为所有可能的X聚类对的函数，此函数用于测量两个聚类之间的近邻性，
用t表示当前聚类的层次级别。通用合并算法的伪码描述如下：
1. 初始化：
a) 选择Â0={{x1},…,{xN}}
b) 令t=0
2. 重复执行以下步骤：
a) t=t+1
b) 在Ât-1中选择一组(Ci,Cj)，满足
c) 定义Cq=CiÈCj，并且产生新聚类Ât=(Ât-1-{Ci,Cj})È{Cq}
直到所有向量全被加入到单一聚类中。
这一方法在t层时将两个向量合并，那么这两个向量在以后的聚类过程中的后继聚类
都是相同的，也就是说一旦它们走到一起，那么以后就不会再分离……（很专一哦）。这也
就引出了这个算法的缺点，当在算法开始阶段，若出现聚类错误，那么这种错误将一直会
被延续，无法修改。在层次t上，有N-t个聚类，为了确定t+1层上要合并的聚类对，必
须考虑(N-t)(N-t-1)/2个聚类对。这样，聚类过程总共要考虑的聚类对数量就是
(N-1)N(N+1)/6，也就是说整个算法的时间复杂度是O(N3)。
举例来说，如果令X={x1, x2, x3, x4, x5}，其中x1=[1, 1]T, x2=[2, 1]T, x3=[5, 4]T,
x4=[6, 5]T, x5=[6.5, 6]T。那么合并算法执行的过程可以用下面的图来表示。
P(X)是不相似矩阵
该算法从核心过程上来讲，就是先计算出数据集中向量之间的距离，记为距离矩阵（也
叫不相似矩阵）。接着通过不断的对矩阵更新，完成聚类。矩阵更新算法的伪码描述如下：
1. 初始化：
a) Â0={{x1},…,{xN}}
b) P0=P(X) (距离矩阵)
发布者：admin，转转请注明出处：http://www.yc00.com/num/1714556033a2469226.html
评论列表（0条）