层次聚类

• 层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构，
• 数据集的划分可采用“自底向上（合并）”的聚合策略，也可采用“自顶向下（拆分）”的分析策略。依据采用的策略可以将层次聚类方法分为：
  • 聚合式聚类（agglomerative clustering）
  • 分拆式聚类（divisive clustering）
• 两种方法均是启发式的策略，没有去优化一个明确的目标函数来实现聚类，很难严格评价聚类的效果。
• 层次聚类得到的结果是 "树状图"

根据不同虚线的位置，可以得到不同数量的聚类

聚合式聚类

• 在开始时把每个样本都每个样本都当成一簇，然后在每一次迭代中将最相似的（距离最近）的两个簇合并，直到把所有簇合并为包含所有样本的一簇

流程：

1. 将每个样本看做一个簇: C i ← { i } , i = 1 , 2 , . . . , n C_i \leftarrow \{i\}, i = 1,2,...,n Ci​←{i},i=1,2,...,n
2. 初始化可供合并的簇集： S ← { 1 , 2 , . . . , n } S \leftarrow \{1,2,...,n\} S←{1,2,...,n}
3. 计算出簇间距离矩阵
4. 重复迭代如下步骤直至没有可供合并的簇：
   1. 选择两个最相似的簇进行合并：$(j,k)\leftarrow arg{\min }_{j,k\in S}{d}_{j,k}$
   2. 创建新簇 $C_l\leftarrow C_j\cup C_k$
   3. 从 $S$ 中取出已合并的$j$和$k$： S ← S ∖ { j , k } S \leftarrow S\setminus\{ j,k\} S←S∖{j,k}
   4. 如果 C l ≠ { 1 , 2 , . . . , n } C_l \neq \{ 1,2,...,n\} Cl​​={1,2,...,n}，那么增加一个可合并集 S ← S ∪ { l } S \leftarrow S \cup \{l\} S←S∪{l}
   5. 对于每个$i\in S$ ，更新簇间距离矩阵$d(i,l)$

簇间距离的计算

单链接(single-linkage)

​ 也称为最近邻距离，即簇$G$ 和簇$H$之间的距离定义为两簇之间最近的成员之间的距离：
$$d_{sl}(G,h)=\underset{i\in G,i^{{}^{\prime }}\in H}{\min }{d}_{i,i^{{}^{\prime }}}$$

全链接(complete-linkage)

​ 也称为最远邻距离，即簇G和簇H之间的距离定义为两簇之间最远的成员之间的距离。
$$d_{cl}(G,H)=\underset{i\in G,i^{{}^{\prime }}\in H}{\max }{d}_{i,i^{{}^{\prime }}}$$

平均链接(average-linkage)

• 表示两簇之间所有成员对的平均距离

$$d_{avg}(G,H)=\frac{1}{n_G{n}_H}\sum _{i\in G}\sum _{i^{{}^{\prime }}\in H}{d}_{i,i^{{}^{\prime }}}$$

• $n_G$ 和$n_H$ 是簇G和簇H的样本个数。

三种距离方式的比较

• 单链接(single-linkage)
  • 只需要考虑两簇之间有成员对距离足够近就将两簇合并，而并没有考虑其他簇内其他成员的距离。因此单连接法形成的簇很有可能违背紧致性特征，即簇内成员应该尽可能相似
• 全连接法（complete-linkage）：
  • 只有两簇的联合的成员间的距离相对较小时，才将两簇合并，因此完整连接法倾向于生成紧致簇
• 均连接法（average-linkage）
  • 介于单连接和全连接之间的方法
  • 易于生成相对紧致的簇同时簇间距离较远。

分拆式聚类

​ 分拆聚类将所有样本集合看作一簇，以自上而下的方式，递归地将现有的簇分拆为两个子簇。

​ 利用不同的启发式方法进行分拆方式的选择：

• 二分K-means聚类

  • 选择半径最大的簇，对该簇进行K（2）-means聚类分为两个子簇
  • 重复此过程直到到达想要的簇个数

• 最小生成树法

  • 将每个样本看作一个图节点，将样本间距离看作节点边的权重，根据此图建立最小生成树。
  • 从权重最大处将该簇分拆为两簇，然后重复此过程直到达到想要的簇个数。实际上，该方法得到的聚类结果和单连接的聚合聚类得到的结果一致。

层次聚类算法总结

• 层次聚类一次性地得到了整个聚类的过程，想要分多少个簇都可以直接根据“树状图”来得到结果，改变簇的数目不再需要再次计算数据点的归属类别；
• 单连接和全连接代表了簇间距离度量的两个极端，它们对离群点或噪声数据过分敏感
• 平均连接时一种计算量大，而且错分在层次聚类中时不可修正的，一旦某个样本被分到某个聚类中，则该样本永远停留在该聚类中。
• 层次聚类的缺点是：
  • 计算量大
  • 而且错分在聚合式聚类中是不可修正的，一旦某个样本被分到某个聚类中，则该样本永远停留在该聚类中。

起步

层次聚类（hierarchical clustering）是聚类算法中的一种，通过计算不同类别的相似度组成新的类创建一个层次的嵌套的树。

基本结构如图所示：

层次聚类算法介绍

假设有n个待聚类的样本，对于层次聚类算法，它的步骤是：

• 步骤一：（初始化）将每个样本都视为一个聚类；
• 步骤二：计算各个聚类之间的相似度；
• 步骤三：寻找最近的两个聚类，将他们归为一类；
• 步骤四：重复步骤二，步骤三；直到所有样本归为一类

整个过程就是建立一棵树，在建立的过程中，可以在步骤四设置所需分类的类别个数，作为迭代的终止条件，毕竟都归为一类并不实际。

聚类之间的相似度

聚类和聚类之间的相识度有什么来衡量呢？既然是空间中的点，可以采用距离的方式来衡量，一般有如下三种方式：

Single Linkage

又叫做 nearest-neighbor ，就是取两个类中距离最近的两个样本的距离作为这两个集合的距离。这种计算方式容易造成一种叫做 Chaining 的效果，两个 cluster 明明从“大局”上离得比较远，但是由于其中个别的点距离比较近就被合并了，并且这样合并之后 Chaining 效应会进一步扩大，最后会得到比较松散的 cluster 。

Complete Linkage

这个则完全是 Single Linkage 的反面极端，取两个集合中距离最远的两个点的距离作为两个集合的距离。其效果也是刚好相反的，限制非常大。这两种相似度的定义方法的共同问题就是指考虑了某个有特点的数据，而没有考虑类内数据的整体特点。

Average Linkage 这种方法就是把两个集合中的点两两的距离全部放在一起求均值，相对也能得到合适一点的结果。有时异常点的存在会影响均值，平常人和富豪平均一下收入会被拉高是吧，因此这种计算方法的一个变种就是取两两距离的中位数。

Python的代码实现：

空间中点的距离使用欧拉公式：

import math
import numpy as np
from sklearn import datasets,cluster

def euler_distance(point1: np.ndarray, point2: list) -> float:
    """
    计算两点之间的欧拉距离，支持多维
    """
    distance = 0.0
    for a, b in zip(point1, point2):
        distance += math.pow(a - b, 2)
    return math.sqrt(distance)

定义聚类点的节点：

class ClusterNode(object):
    def __init__(self, vec, left=None, right=None, distance=-1, id=None, count=1):
        """
        :param vec: 保存两个数据聚类后形成新的中心
        :param left: 左节点
        :param right:  右节点
        :param distance: 两个节点的距离
        :param id: 用来标记哪些节点是计算过的
        :param count: 这个节点的叶子节点个数
        """
        self.vec = vec
        self.left = left
        self.right = right
        self.distance = distance
        self.id = id
        self.count = count

vec 表示合并后的聚类中心，是一个点，代表整个聚类的位置；distance 表示左节点和右节点的距离。

计算层次聚类算法的类：

class Hierarchical(object):
    def __init__(self, k = 1):
        assert k > 0
        self.k = k
        self.labels = None
    def fit(self, x):
        nodes = [ClusterNode(vec=v, id=i) for i,v in enumerate(x)]
        distances = {}
        point_num, future_num = np.shape(x)  # 特征的维度
        self.labels = [ -1 ] * point_num
        currentclustid = -1
        while len(nodes) > self.k:
            min_dist = math.inf
            nodes_len = len(nodes)
            closest_part = None  # 表示最相似的两个聚类
            for i in range(nodes_len - 1):
                for j in range(i + 1, nodes_len):
                    # 为了不重复计算距离，保存在字典内
                    d_key = (nodes[i].id, nodes[j].id)
                    if d_key not in distances:
                        distances[d_key] = euler_distance(nodes[i].vec, nodes[j].vec)
                    d = distances[d_key]
                    if d < min_dist:
                        min_dist = d
                        closest_part = (i, j)
            # 合并两个聚类
            part1, part2 = closest_part
            node1, node2 = nodes[part1], nodes[part2]
            new_vec = [ (node1.vec[i] * node1.count + node2.vec[i] * node2.count ) / (node1.count + node2.count)
                        for i in range(future_num)]
            new_node = ClusterNode(vec=new_vec,
                                   left=node1,
                                   right=node2,
                                   distance=min_dist,
                                   id=currentclustid,
                                   count=node1.count + node2.count)
            currentclustid -= 1
            del nodes[part2], nodes[part1]   # 一定要先del索引较大的
            nodes.append(new_node)
        self.nodes = nodes
        self.calc_label()

    def calc_label(self):
        """
        调取聚类的结果
        """
        for i, node in enumerate(self.nodes):
            # 将节点的所有叶子节点都分类
            self.leaf_traversal(node, i)

    def leaf_traversal(self, node: ClusterNode, label):
        """
        递归遍历叶子节点
        """
        if node.left == None and node.right == None:
            self.labels[node.id] = label
        if node.left:
            self.leaf_traversal(node.left, label)
        if node.right:
            self.leaf_traversal(node.right, label)

最后将聚类的列表标记保存于 labels 中。

测试：

与 sklearn 进行对比：

iris = datasets.load_iris()

my = Hierarchical(4)
my.fit(iris.data)
print(np.array(my.labels))

sk = cluster.AgglomerativeClustering(4)
sk.fit(iris.data)
print(sk.labels_)

得到输出：

层次聚类的优缺点：

优点：

• 一次性得到聚类树，后期再分类无需重新计算；
• 相似度规则容易定义；
• 可以发现类别的层次关系。

缺点：

• 计算复杂度高，不适合数据量大的；
• 算法很可能形成链状。