Hierarchical Agglomerative Clustering（层次凝聚聚类），是聚类分析中的一种重要方法。
- 基本原理
- 它是一种自底向上的聚类方法。开始时，每个数据点都被视为一个单独的聚类。然后，在每一步中，算法会根据某种相似度（或距离）度量标准，寻找最相似（距离最近）的两个聚类，并将它们合并为一个新的聚类。这个过程不断重复，直到满足某个停止条件，比如达到预定的聚类数量或者所有数据点都合并到一个聚类中。
- 例如，假设有5个数据点A、B、C、D、E。最初，聚类为{A}、{B}、{C}、{D}、{E}。如果根据距离度量发现A和B是最相似的，那么就将它们合并为一个新的聚类{AB}，此时聚类情况变为{AB}、{C}、{D}、{E}。然后继续寻找最相似的聚类进行合并，直到满足停止条件。
- 相似度（距离）度量标准
- 欧几里得距离：这是最常用的距离度量方法之一。对于两个数据点(X=(x_1,x_2,\cdots,x_n))和(Y=(y_1,y_2,\cdots,y_n))，它们之间的欧几里得距离(d(X,Y)=\sqrt{\sum_{i = 1}^{n}(x_i - y_i)^2})。例如，在二维空间中有两个点((1,2))和((4,6))，它们之间的欧几里得距离为(\sqrt{(4 - 1)^2+(6 - 2)^2}=\sqrt{9 + 16}=\sqrt{25} = 5)。
- 曼哈顿距离：也叫城市街区距离。对于上述的两个数据点(X)和(Y)，曼哈顿距离(d(X,Y)=\sum_{i = 1}^{n}\vert x_i - y_i\vert)。在二维空间中，点((1,2))和((4,6))的曼哈顿距离为(\vert4 - 1\vert+\vert6 - 2\vert = 3+4 = 7)。
- 余弦相似度：主要用于衡量两个向量方向的一致性。对于两个非零向量(X)和(Y)，余弦相似度(\cos\theta=\frac{X\cdot Y}{\vert X\vert\times\vert Y\vert})，其中(X\cdot Y=\sum_{i = 1}^{n}x_i\times y_i)，(\vert X\vert=\sqrt{\sum_{i = 1}^{n}x_i^2})，(\vert Y\vert=\sqrt{\sum_{i = 1}^{n}y_i^2})。余弦相似度的值在([-1,1])之间，值越接近1表示两个向量越相似。
- 合并策略（Linkage Criteria）
- 单链接（Single - Linkage）：也称为最近邻链接。当合并两个聚类时，它是基于两个聚类中最近的数据点之间的距离来判断的。例如，有聚类(C1)和(C2)，单链接方法会找到(C1)中的一个点(x)和(C2)中的一个点(y)，使得(d(x,y))是所有(C1)和(C2)中点对距离中的最小值，然后根据这个最小值来决定是否合并(C1)和(C2)。这种方法容易受到噪声和离群点的影响，可能导致链状结构的聚类。
- 全链接（Complete - Linkage）：也称为最远邻链接。它是基于两个聚类中最远的数据点之间的距离来判断的。对于聚类(C1)和(C2)，全链接方法会找到(C1)中的一个点(x)和(C2)中的一个点(y)，使得(d(x,y))是所有(C1)和(C2)中点对距离中的最大值，然后根据这个最大值来决定是否合并(C1)和(C2)。这种方法倾向于产生紧凑的聚类。
- 平均链接（Average - Linkage）：它是基于两个聚类中所有数据点对之间距离的平均值来判断的。对于聚类(C1)和(C2)，计算(C1)和(C2)中所有点对之间的距离，然后求平均值，根据这个平均值来决定是否合并(C1)和(C2)。这种方法在单链接和全链接之间取得了平衡。
- 应用场景
- 生物学领域：在生物分类学中，用于对生物物种进行分类。例如，根据生物的基因序列或者形态特征等数据，通过层次凝聚聚类方法，可以将相似的物种聚类在一起，帮助生物学家更好地理解生物之间的亲缘关系和进化关系。
- 市场细分：在市场营销中，对消费者进行细分。通过收集消费者的购买行为、偏好、人口统计学等数据，利用层次凝聚聚类可以将消费者分成不同的群体，企业可以针对不同的消费群体制定更精准的营销策略。例如，将消费者分为价格敏感型、品牌忠诚型、时尚追求型等不同的聚类，然后根据各个聚类的特点推出相应的产品和促销活动。
- 图像识别：在图像数据处理中，对图像进行分类或分割。例如，根据图像的颜色、纹理、形状等特征，将相似的图像聚类在一起，或者将图像中的不同物体通过聚类进行分割。在医学图像分析中，也可以利用这种方法对细胞图像或者组织图像进行分类，辅助医生进行诊断。