Featured image of post 聚类算法
计算机

聚类算法

重点介绍高斯混合模型

2

K均值聚类（K-Means）的数学原理

K均值聚类是一种迭代优化算法，其目标是将数据分为 \( k \) 个簇，最小化簇内样本点与簇中心的平方误差和（即误差平方和，SSE）。以下是核心数学原理：

1. 目标函数

K均值算法的目标是最小化以下目标函数： $ J = \sum_{i=1}^k \sum_{x \in C_i} ||x - \mu_i||^2 $

  • \( k \)：簇的数量（预定义）。
  • \( $C_i $)：第 \( i \) 个簇。
  • \($ \mu_i $ \)：第 \( i \) 个簇的中心（质心）。
  • \( x \)：数据点。
  • \($||x - \mu_i||^2$ \)：数据点 \( x \) 与簇中心 \( \mu_i \) 的欧氏距离的平方。

2. 算法流程

K均值通过以下步骤进行迭代优化：

  1. 初始化簇中心： 随机选择 \( k \) 个数据点作为初始簇中心，或者随机初始化。

  2. 分配样本点： 对每个样本点 \( x \)，计算它到所有簇中心 \( \mu_i \) 的欧氏距离，分配到最近的簇： $ C_i = {x | ||x - \mu_i||^2 \leq ||x - \mu_j||^2, \forall j \neq i} $

  3. 更新簇中心： 对每个簇 \( C_i \)，重新计算其簇中心为簇中所有点的均值： $ \mu_i = \frac{1}{|C_i|} \sum_{x \in C_i} x $

  4. 迭代： 重复步骤 2 和 3，直到簇中心不再发生变化或达到最大迭代次数。

3. 收敛性

  • 收敛条件：目标函数 \( J \) 收敛到局部最小值。
  • 缺点：对初始值敏感，可能陷入局部最优。

伪代码

以下是 K 均值算法的伪代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

输入: 数据集 X = {x1, x2, ..., xn}，簇的数量 k，最大迭代次数 max_iters
输出: 簇分配结果 C = {C1, C2, ..., Ck} 和簇中心 μ = {μ1, μ2, ..., μk}

1. 初始化 μ = {μ1, μ2, ..., μk} （随机选择 k 个点作为初始簇中心）
2. 重复以下步骤直到收敛或达到最大迭代次数：
   2.1 分配样本到最近的簇：
       对于每个点 x ∈ X：
           计算 d(x, μi) = ||x - μi||^2，针对所有 i
           将点 x 分配到距离最近的簇 Ci
   2.2 更新簇中心：
       对于每个簇 Ci：
           μi = (1 / |Ci|) * ∑(x ∈ Ci) x
   2.3 计算目标函数 J
3. 输出簇分配结果 C 和簇中心 μ

  1. 层次聚类的数学原理

    层次聚类（Hierarchical Clustering）是一种基于层次结构的聚类方法，分为两种类型：凝聚式层次聚类（Agglomerative Hierarchical Clustering） 和 分裂式层次聚类（Divisive Hierarchical Clustering）。常用的凝聚式层次聚类从单个点开始，将其逐步合并为簇。

    1. 数学原理

    层次聚类通过定义簇之间的相似度或距离逐步构建一个层次结构（如树状结构）。核心数学原理包括以下部分：

    1.1 数据点之间的距离

    常见的距离度量方式：

    • 欧氏距离（Euclidean Distance）： $ d(x_i, x_j) = \sqrt{\sum_{k=1}^m (x_{ik} - x_{jk})^2} $
    • 曼哈顿距离（Manhattan Distance）： $ d(x_i, x_j) = \sum_{k=1}^m |x_{ik} - x_{jk}| $
    1.2 簇之间的距离

    定义两个簇 \( C_i \) 和 \( C_j \) 的距离的方法：

    • 单链接法（Single Linkage）： $ D(C_i, C_j) = \min_{x \in C_i, y \in C_j} d(x, y) $
    • 全链接法（Complete Linkage）： $ D(C_i, C_j) = \max_{x \in C_i, y \in C_j} d(x, y) $
    • 平均链接法（Average Linkage）： $ D(C_i, C_j) = \frac{1}{|C_i| |C_j|} \sum_{x \in C_i, y \in C_j} d(x, y) $
    • 质心法（Centroid Linkage）： $ D(C_i, C_j) = ||\mu_i - \mu_j||_2 $ 其中 \( $\mu_i$ \) 和 \( $\mu_j $\) 是两个簇的质心。
    1.3 层次结构
    • 在凝聚式层次聚类中，初始状态将每个点作为一个簇，逐步合并最近的簇，直到最终所有点合并为一个簇。
    • 在分裂式层次聚类中，从整体簇开始，逐步分裂为多个小簇。

    2. 算法流程（以凝聚式为例）

    1. 初始化：将每个数据点作为一个独立的簇。
    2. 计算所有簇之间的距离，找到最近的两个簇。
    3. 合并最近的两个簇。
    4. 更新距离矩阵（根据所选的距离计算方法）。
    5. 重复步骤 2 至 4，直到所有簇合并为一个簇或达到指定层次。

    伪代码

    以下是凝聚式层次聚类的伪代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

输入: 数据集 X = {x1, x2, ..., xn}，距离度量方式 dist_method
输出: 层次树状结构 Dendrogram

1. 初始化：将每个点 xi 视为一个簇 Ci
2. 计算初始距离矩阵 D，其中 D(i, j) = dist_method(Ci, Cj)
3. 重复以下步骤直到所有簇合并为一个：
   3.1 找到距离矩阵 D 中最小的非对角元素，对应的两个簇 Ci 和 Cj
   3.2 合并簇 Ci 和 Cj 为新簇 Cnew
   3.3 更新距离矩阵 D：
       对于每个簇 Ck ≠ Cnew，计算 D(Cnew, Ck)
   3.4 删除簇 Ci 和 Cj，添加簇 Cnew
4. 输出层次树状结构 Dendrogram

高斯混合模型 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

import numpy as np
import matplotlib.pyplot as plt
from scipy.stats import multivariate_normal

red_mean=2
red_std=3
red=np.random.normal(red_mean,red_std,1000)

blue_mean=7
blue_std=1
blue=np.random.normal(blue_mean,blue_std,1000)

both_color=np.sort(np.concatenate((red,blue)))
#print(both_color)
plt.rcParams["figure.figsize"] = (15,2)
# 绘制红色和蓝色点
plt.scatter(red,np.zeros_like(red),color="red",s=10)
plt.scatter(blue,np.zeros_like(blue),color="blue",s=10)
plt.title(r'Distribution of red and blue points (known colours)', fontsize=17)
#隐藏y坐标
plt.yticks([])
plt.show()
x_train=both_color.reshape(-1,1)

class Gaussian:
    def __init__(self,x_train,num=2,eps=0.1):
        if len(x_train.shape)==1:
            self.x_train=x_train.reshape(-1,1)
        else:
            self.x_train=x_train
        self.m=self.x_train.shape[0]
        self.n=self.x_train.shape[1]
        self.num=num
        self.sigma=np.ones((self.num,self.n))
        self.mean=np.zeros((self.num,self.n))
        self.eps=eps
        self.resp_val=np.zeros((self.m,self.num))
        self.pi=np.ones(self.num)/self.num

    def train(self):
        sigma_new = np.inf * np.ones((self.num, self.n))
        mean_new = np.inf * np.ones((self.num, self.n))
        pi_new = np.inf * np.ones(self.num)
        m1 = np.column_stack((sigma_new, mean_new, pi_new))
        m2 = np.column_stack((self.sigma, self.mean, self.pi))
        while np.max(np.abs(m1 - m2)) > self.eps:
            self.resp_val = self.calc_resp_val()
            val_sum = np.sum(self.resp_val, axis=0)
            mean_new = np.dot(self.resp_val.T, self.x_train) / val_sum[:, None]
            sigma_new = np.zeros((self.num, self.n))
            for k in range(self.num):
                diff = self.x_train - mean_new[k, :]
                sigma_new[k, :] = np.sum(self.resp_val[:, k,None] * (diff ** 2), axis=0) / val_sum[k]
            pi_new = val_sum / self.m
            m1 = np.column_stack((sigma_new, mean_new, pi_new))
            m2 = np.column_stack((self.sigma, self.mean, self.pi))
            self.mean = mean_new
            self.sigma = sigma_new
            self.pi = pi_new
        print("mu为:")
        print(self.mean)
        print("sigma:")
        print(self.sigma)
        print("pi:")
        print(self.pi)

    def calc_resp_val(self):
        """
        param: resp_val[j,k]为gamma_j_k
        """
        resp_val=np.zeros((self.m,self.num))
        for i in range(self.m):
            x=self.x_train[i,:]
            t=np.array([self.gauss(x,k) for k in range(self.num)])
            t=self.pi*t
            t=t/np.sum(t)
            resp_val[i,:]=t
        return resp_val

    def gauss(self,x,k):
        cov=np.diag(self.sigma[k,:])
        mean=self.mean[k,:]
        multi_gaussian=multivariate_normal(mean,cov)
        return multi_gaussian.pdf(x)

if __name__=="__main__":
    Gaussian=Gaussian(x_train=both_color,num=2,eps=0.1)
    Gaussian.train()

代码说明

这段代码实现了一个简单的高斯混合模型（Gaussian Mixture Model, GMM）的训练过程，以下是其功能说明：

代码功能

  1. 生成数据：
    • 两组高斯分布数据 red 和 blue 分别从 $N(2,32)\mathcal{N}(2, 3^2)N(2,32)$ 和$ N(7,12)\mathcal{N}(7, 1^2)N(7,12)$ 生成，每组 1000 个样本。
    • 合并两组数据形成一个数据集 both_color，用于 GMM 模型的训练。
  2. 数据可视化：
    • 使用散点图展示红色和蓝色数据点，红色点和蓝色点分布在两个高斯分布的中心附近，用来直观表示两组数据的分布。
  3. 实现高斯混合模型：
    • 实现了一个 Gaussian 类，用于对输入数据训练高斯混合模型（GMM），并估计数据点的混合成分（责任度）。
  4. 高斯混合模型训练逻辑：
    • 使用 EM（Expectation-Maximization）算法，包含以下步骤：
      • E 步（Expectation Step）：计算每个数据点属于每个高斯分量的责任度 $\gamma_{jk}$。
      • M 步（Maximization Step）：根据计算出的责任度更新均值 $\mu_k$、协方差 $\sigma_k^2$ 和混合系数 $\pi_k$。
    • 模型通过循环迭代，直到参数收敛为止（满足 $\epsilon$ 条件）。
  5. 输出结果：
    • 打印最终训练得到的参数：
      • $\mu$（每个分量的均值向量）
      • $\sigma$（每个分量的协方差矩阵）
      • $\pi$（每个分量的混合系数）

类和方法功能

  1. Gaussian 类：
    • 用于实现高斯混合模型的训练。
    • 接收输入数据、分量数（num）和收敛阈值（eps）。
    • 存储模型的参数（均值、协方差、混合系数）及中间计算结果（责任度）。
  2. train 方法：
    • 执行 EM 算法，包括：
      • 计算数据点的责任度。
      • 更新高斯分布的参数：均值 $\mu_k$、协方差 $\sigma_k^2$、混合系数 $\pi_k$。
    • 打印训练后的参数。
  3. calc_resp_val 方法：
    • 计算每个数据点属于每个高斯分量的责任度 $\gamma_{jk}$。
  4. gauss 方法：
    • 计算多元正态分布的概率密度值，用于责任度的计算。

执行逻辑

  1. 生成两组高斯分布数据，合并并转换为训练数据 x_train。
  2. 初始化 Gaussian 对象，设置分量数（num=2）和收敛阈值（eps=0.1）。
  3. 调用 train 方法，训练高斯混合模型。
  4. 打印模型参数（均值、协方差、混合系数）。
comments powered by Disqus
© 2020 - 2025 懒得起名字惹
使用 Hugo 构建
主题 Stack 由 Jimmy 设计