hierarchical clustering

[CaesarZZP]

今天去面试，没想到面试之后来了个笔试 hierarchical clustering 核心操作： 不停地合并两个最近的cluster(如果是一开始，则合并两个最近的点，变成一个新的cluster representation)

欧式距离

• 那么怎么代表一个群体：聚类中心（centroid）=最近的两个clusters的点的平均值

eg: [此时有五个cluster]

• 然后下一个继续找最近的两个cluster 右下角的dendrogram就是我们聚类的过程，比如蓝色是我们第一次聚类，绿色是第二次，以此类推

• 第三步，红色圈（注意此时的最新聚类红圈中心是(1,2) (2,1),(0,0) 的平均，而不是x(1.5,1.5) ）

• 最后

非欧几里得case（此时要用clustroid）

centroid和clustroid的区别

停止条件

方法1：提前设置好k，但有k个聚类时，就停止训练（但这种是只适合我们知道数据有多少类的时候） 方法2：当两个聚类合并成一个新的聚类效果很差时，停止；那么什么是差的聚类呢，用的是cohesion(内聚力)

1. diameter（直径）of the merged cluster=cluster中最大的两点点距离
2. radius = 距离centroid或者clustroid最远的距离（大于某个d或r阈值时停止）
3. 基于密度的方法：number of pointes per unit volume；eg numbers of points in cluster 除以d或者r

即使用了优先队列，复杂度也要N^2*logN，所以hierarchical clustering不适合大数据集

如果忘记了，看不懂，可以看这里

[CaesarZZP]

判断两两相似度的方法有三种

• singleLinkage
• completeLinkage
• averageLinkage

1. singleLinkage：两个类中最近的两个样本之间的距离作为两个集合的距离，即：最近的两个样本之间的距离越小。此距离越小，认为相似度越大 ---问题在与：如果两个大聚类距离远，但是两个大聚类中分别有一个点，这两个点很近，那么问题就出现了

2. completeLinkage：取两个集合距离最远的两个点的距离作为两个集合的距离，其效果也刚好相反，限制非常大。

3. averageLinkage：把两个集合中的点两两距离全部放在一起求平均值，相应的能得到一点合适的结果。Average Linkage的一个变种就是取两两距离的中值，与取平均值相比更加能够解除个别偏离样本对结果的干扰。（偏离样本对均值的影响大）