学习日记_20241115_聚类方法（层次聚类）

前言

提醒：
文章内容为方便作者自己后日复习与查阅而进行的书写与发布，其中引用内容都会使用链接表明出处（如有侵权问题，请及时联系）。
其中内容多为一次书写，缺少检查与订正，如有问题或其他拓展及意见建议，欢迎评论区讨论交流。

聚类算法

聚类算法在各种领域中有广泛的应用，主要用于发现数据中的自然分组和模式。以下是一些常见的应用场景以及每种算法的优缺点：

经典应用场景

1. 市场细分：根据消费者的行为和特征，将他们分成不同的群体，以便进行有针对性的营销。

2. 图像分割： 将图像划分为多个区域或对象，以便进行进一步的分析或处理。

3. 社交网络分析：识别社交网络中的社区结构。

4. 文档分类：自动将文档分组到不同的主题或类别中。

5. 异常检测识别数据中的异常点或异常行为。

6. 基因表达分析：在生物信息学中，根据基因表达模式对基因进行聚类。

层次聚类

层次聚类
层次聚类（Hierarchical
Clustering）是一种聚类分析方法，通过构建一个树状结构（或树形图），将数据集中的样本分组。层次聚类有两种主要类型：凝聚型（自下而上）和分裂型（自上而下）。以下是层次聚类的优缺点：

优点

直观易理解：层次聚类通过树形图（Dendrogram）展示聚类结构，使得结果更直观易懂，方便分析数据之间的关系。
无需预先指定聚类数：与K-Means等方法不同，层次聚类不需要用户提前指定聚类的数量。用户可以根据树形图的结构选择适合的聚类数。
适用于各种类型的数据：可以处理任意类型的距离度量（如欧几里得距离、曼哈顿距离等），也可以应用于不规则形状的聚类。
适合小规模数据集：在小规模数据集上表现良好，可以提供更细致的聚类结果。
可嵌套的聚类结果：层次聚类可以生成不同层次的聚类，用户可以根据不同的需求选择不同的聚类层次。

缺点

计算复杂度高：层次聚类的时间复杂度通常为 $O(n^3)$ 或 $O(n^2\log n)$，因此在大规模数据集上可能会表现得非常缓慢。
对噪声和离群点敏感：层次聚类对数据中的噪声和离群点非常敏感，这可能会影响最终的聚类结果。
难以处理非球形簇：尽管层次聚类可以处理不同形状的聚类，但在实际应用中，很多实现仍然假设簇是球形的，因此对某些复杂形状的簇处理不佳。
合并或分裂的不可逆性：在凝聚型层次聚类中，一旦两个簇被合并，就无法再分开。这可能导致最终聚类结果不够灵活和准确。
选择距离度量和合并准则的挑战：层次聚类的结果对所选择的距离度量和合并准则（如单连接、全连接、平均连接等）非常敏感，不同的选择可能导致完全不同的聚类结果。

总结

层次聚类是一种强大且直观的聚类方法，适合小规模数据集和探索性数据分析。然而，由于其计算复杂度高、对噪声敏感以及合并不可逆性等缺点，在处理大规模数据集或需要高效实时处理的场景中可能不够理想。在选择层次聚类时，用户应考虑数据的规模、特性以及所需的聚类精度。

简单实例（函数库实现）

import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage
# 生成随机数据
np.random.seed(42)
data = np.random.rand(10, 2)  # 生成10个二维随机点
# 打印生成的数据点
print("Generated Data Points:")
print(data)
# 进行层次聚类
linked = linkage(data, method='ward')  # 使用Ward方法进行聚类
# 绘制树形图
plt.figure(figsize=(10, 5))
plt.subplot(1, 2, 1)
plt.scatter(data[:, 0], data[:, 1], c='black')
# 在每个点旁边添加编号
for i, (x, y) in enumerate(zip(data[:, 0], data[:, 1])):
    plt.text(x, y, str(i), fontsize=15, ha='right')
plt.title('First Scatter Plot')
plt.xlabel('X Axis')
plt.ylabel('Y Axis')
plt.subplot(1, 2, 2)
dendrogram(linked, 
           orientation='top', 
           distance_sort='descending', 
           show_leaf_counts=True)
plt.title("Hierarchical Clustering Dendrogram")
plt.xlabel("Sample index")
plt.ylabel("Distance")
plt.show()

#我们使用numpy生成10个二维的随机点，进行聚类分析。使用scipy.cluster.hierarchy.linkage函数
#进行层次聚类。在这个例子中，使用ward了方法，该方法最小化聚类间的方差。

data数据分布与代码运行结果：

数学表达

层次聚类（Hierarchical Clustering）是一种将数据点逐步合并成类的聚类方法，形成一个树状结构（树形图，dendrogram）。它可以分为两种主要类型：凝聚型（Agglomerative）和分裂型（Divisive）。下面将结合数学表达式对其进行详细讲解。

凝聚型层次聚类（Agglomerative Hierarchical Clustering）

以下是凝聚型层次聚类的数学描述：

1. 初始化

假设有 $n$ 个数据点 X = { x 1 , x 2 , … , x n } X = \{x_1, x_2, \ldots, x_n\} X={x1​,x2​,…,xn​}，初始时每个数据点作为一个独立的簇。记每个数据点对应的簇为 C i = { x i } C_i = \{x_i\} Ci​={xi​}。

2. 距离度量 为了判断簇之间的相似度，首先需要定义簇之间的距离。对于任意两个簇 $C_i$ 和 $C_j$，选择一种距离度量方法，常见的有：

• 单链接（Single Linkage）： $$d(C_i,C_j)=\underset{x\in C_i,y\in C_j}{\min }d(x,y)$$
• 全链接（Complete Linkage）： $$d(C_i,C_j)=\underset{x\in C_i,y\in C_j}{\max }d(x,y)$$
• 平均链接（Average Linkage）： $$d(C_i,C_j)=\frac{1}{|C_i|\cdot |C_j|}\sum _{x\in C_i}\sum _{y\in C_j}d(x,y)$$
• Ward方法： $$d(C_i,C_j)=\sqrt{\frac{|C_i|\cdot |C_j|}{|C_i|+|C_j|}\cdot \Vert {\mu }_i-{\mu }_j{\Vert }^2}$$ 其中，${\mu }_i$ 和${\mu }_j$ 分别是簇 $C_i$ 和 $C_j$ 的质心（均值）。在聚类分析中，$|C_k|$ 表示簇 $C_k$中的数据点的数量，即簇 $C_k$的大小。

3. 合并过程

在每一步中，找到距离最小的两个簇 $C_a$ 和 $C_b$，然后合并它们： $$C_{new}=C_a\cup C_b$$

更新簇的数量： $$k=k-1$$

4. 更新距离矩阵 合并后，需要更新距离矩阵。对于新产生的簇 $C_{new}$ 和其他簇 $C_k$ 的距离可以根据选择的距离度量方式进行计算。例如：

• 对于单链接： $$d(C_{new},C_k)=\min (d(C_a,C_k),d(C_b,C_k))$$
• 对于全链接： $$d(C_{new},C_k)=\max (d(C_a,C_k),d(C_b,C_k))$$
• 对于平均链接： $$d(C_{new},C_k)=\frac{|C_a|\cdot d(C_a,C_k)+|C_b|\cdot d(C_b,C_k)}{|C_a|+|C_b|}$$
• 对于Ward方法： $$d(C_{new},C_k)=\sqrt{\frac{|C_{new}|\cdot |C_k|}{|C_{new}|+|C_k|}\cdot \Vert {\mu }_{new}-{\mu }_k{\Vert }^2}$$
  其中，${\mu }_{new}$ 是合并后新簇的质心。

5. 终止条件

重复步骤3和步骤4，直到所有数据点合并为一个簇，或者达到预定的簇数量 $k$。

6. 结果表示

最终结果可以用树形图（dendrogram）表示，展示了所有簇的合并过程及其对应的距离。

通过以上的数学表达和步骤，可以较为清晰地理解凝聚型层次聚类的过程及其特征。

分裂型层次聚类（Divisive Hierarchical Clustering）

分裂型层次聚类（Divisive Hierarchical Clustering）是与凝聚型层次聚类相反的方法，它从一个整体簇开始，然后逐步将其分裂成更小的簇。以下是分裂型层次聚类的数学表达和过程描述：

1. 初始化

假设有 $n$ 个数据点 X = { x 1 , x 2 , … , x n } X = \{x_1, x_2, \ldots, x_n\} X={x1​,x2​,…,xn​}，初始时所有数据点都被视为一个单一的簇：
C = { X } C = \{X\} C={X}

2. 选择分裂簇

在每一步，选择一个簇 $C_k$ 进行分裂。通常选择具有最大内部离散度的簇，以确保分裂后的簇之间的差异最大。>##### 3. 距离度量
定义簇的离散度（内部距离），可以使用某种度量，例如簇的总方差：
$$D(C_k)=\sum _{x\in C_k}d(x,{\mu }_k{)}^2$$
其中 ${\mu }_k$ 是簇 $C_k$ 的质心，$d(x,{\mu }_k)$ 是数据点 $x$ 到簇质心的距离。

4. 分裂方法

选择一个适当的分裂方法（例如 K-means）。假设我们将簇 $C_k$ 分裂为两个子簇 $C_{k1}$ 和 $C_{k2}$：
$$C_k\to C_{k1},C_{k2}$$

5. 更新簇的数量

增加新的簇数量：
$$m=m+1$$

6. 迭代过程

重复步骤 2 到 5，直到达到预定的簇数量 $k$ 或者所有簇都无法再分裂为止。

7. 结果表示

最终结果可以用树形图（dendrogram）表示，展示了所有簇的分裂过程及其对应的离散度。

备注

在分裂型层次聚类中，选择分裂的方式和度量内部离散度的标准会显著影响聚类的结果。常用的分裂方法包括 K-means 算法、PCA 等。

手动实现

import numpy as np

# 计算两个样本之间的欧氏距离
def euclidean_distance(a, b):
    return np.sqrt(np.sum((a - b) ** 2))

# 计算簇之间的距离，这里使用最小距离法
def calculate_cluster_distance(cluster1, cluster2):
    min_distance = float('inf')
    for point1 in cluster1:
        for point2 in cluster2:
            distance = euclidean_distance(point1, point2)
            if distance < min_distance:
                min_distance = distance
    return min_distance

# 初始化簇，每个样本作为一个簇
def initialize_clusters(points):
    return [[point] for point in points]

# 找到距离最近的两个簇
def find_closest_clusters(clusters):
    min_distance = float('inf')
    pair = (None, None)
    for i in range(len(clusters)):
        for j in range(i + 1, len(clusters)):
            distance = calculate_cluster_distance(clusters[i], clusters[j])
            if distance < min_distance:
                min_distance = distance
                pair = (i, j)
    return pair

# 合并两个簇
def merge_clusters(clusters, pair):
    i, j = pair
    merged_cluster = clusters[i] + clusters[j]
    clusters.pop(j)
    clusters.pop(i)
    clusters.append(merged_cluster)
    return clusters

# 凝聚型层次聚类
def agglomerative_clustering(points, distance_threshold):
    clusters = initialize_clusters(points)
    while len(clusters) > 1:
        closest_pair = find_closest_clusters(clusters)
        if calculate_cluster_distance(clusters[closest_pair[0]], clusters[closest_pair[1]]) > distance_threshold:
            break
        clusters = merge_clusters(clusters, closest_pair)
    return clusters

# 示例数据
points = np.array([[1, 2], [2, 2], [5, 8], [1, 3], [8, 8], [9, 10]])

# 调用凝聚型层次聚类算法
clusters = agglomerative_clustering(points, distance_threshold=5)

# 打印结果
for i, cluster in enumerate(clusters):
    print(f"Cluster {i+1}: {cluster}")

结果为：

代码分析

distance = euclidean_distance(point1, point2)

对于points列表中的每一个元素point，将其放入一个新列表中，然后将这些新列表组成一个新的列表。

agglomerative_clustering(points, distance_threshold=5)中distance_threshold

distance_threshold（距离阈值）：在聚类分析中，这是用来决定两个簇是否应该被视为“接近”或“相似”的临界值。如果两个簇之间的距离小于或等于这个阈值，则通常认为这两个簇足够接近，可以考虑将它们合并；如果距离大于这个阈值，则认为它们是独立的，不应该合并。
代码为，如果计算得出的两个最近簇（clusters[closest_pair[0]] 和 clusters[closest_pair[1]]）之间的距离大于给定的距离阈值（distance_threshold），那么执行if语句块中的代码：运行结束。