当前位置: 首页 > article >正文

机器学习 [白板推导](N)[谱聚类、前馈神经网络]

21. 谱聚类(Spectral Clustering)

21.1. 背景

​  在高斯混合模型中,假设样本有多个类别,每个类内数据遵从不同的高斯分布。但在某些数据中(如下图),其并不具有类似高斯分布的特性,则GMM或其他基于空间距离的聚类方法(例如k-means)易于失效。
在这里插入图片描述
​  为了应对上述问题,一种方法是使用合适的kernel函数,将难以处理的分布转换成高斯分布(或其他空间上易于分离的分布)。但实际应用中这样的kernel函数搜索困难。因此需要另一种基于连通性(Connectivity)的方法,从图的角度理解数据分布,即为谱聚类方法(对应的GMM、K-means一类方法为基于Compactness的方法)。

21.2. 模型介绍

21.2.1. 数学建模

  将数据集 D a t a : X N × p = ( x ⃗ 1 , ⋯   , x ⃗ N ) T Data: X_{N\times p}=(\vec{x}_1, \cdots, \vec{x}_N)^T Data:XN×p=(x 1,,x N)T 视作一个图:
G = { V , E } , V = { v ⃗ i } , 其中 v ⃗ i ↔ x ⃗ i , E : W = { w i j } , 1 ⩽ i , j ⩽ N , (21.1) \begin{aligned}G&=\{V, E\}, &\\ V&=\{\vec{v}_i\}, &其中 \vec{v}_i\leftrightarrow \vec{x}_i, \\ E&: W=\{w_{ij}\}, &1\leqslant i, j \leqslant N,\end{aligned}\tag{21.1} GVE={V,E},={v i},:W={wij},其中v ix i,1i,jN,(21.1)

其中 V V V 为节点集合,其中每个节点 v ⃗ i \vec{v}_i v i 表示对应样本 x ⃗ i \vec{x}_i x i 的特征表示; E E E 为边集合,可以用权重矩阵(邻接矩阵,affinity matrix) W W W 表示,其中每个元素 w i j w_{ij} wij 表示节点 v ⃗ i \vec{v}_i v i v ⃗ j \vec{v}_j v j 的相似度。相似度可以使用多种方法计算,以高斯核函数为例:
w i j = { K ( v ⃗ i , v ⃗ j ) = exp ⁡ { − ∥ v ⃗ i − v ⃗ j ∥ 2 σ 2 } , ( i , j ) ∈ E 0 , ( i , j ) ∉ E (21.2) w_{ij}=\left\{\begin{matrix}\mathcal{K}(\vec{v}_i, \vec{v}_j)=\exp\{-\frac{\|\vec{v}_i-\vec{v}_j\|}{2\sigma^2}\},&(i, j)\in E\\0,&(i, j)\notin E\end{matrix}\right.\tag{21.2} wij={K(v i,v j)=exp{2σ2v iv j},0,(i,j)E(i,j)/E(21.2)

  定义相似度损失:存在节点集合 A ⊆ V A\subseteq V AV B ⊆ V B\subseteq V BV,则二者的相似度损失为:
W ( A , B ) = ∑ v ⃗ i ∈ A ∑ v ⃗ j ∈ B w i j , (21.3) \mathcal{W}(A, B)=\sum_{\vec{v}_i \in A}\sum_{\vec{v}_j \in B}w_{ij},\tag{21.3} W(A,B)=v iAv jBwij,(21.3)

则可以计算总聚类损失:假设一共聚为 K K K 个类别: { A 1 , ⋯   , A K } \{A_1,\cdots,A_K\} {A1,,AK},定义 A ˉ i = { A j } i ≠ j , 1 ⩽ j ⩽ K \bar{A}_i=\{A_j\}_{i\neq j,1\leqslant j\leqslant K} Aˉi={Aj}i=j,1jK,则总聚类损失计算为:
L ( A 1 , ⋯   , A K ) = Cut ( A 1 , ⋯   , A K ) = ∑ k = 1 K W ( A k , A ˉ k ) = ∑ k = 1 K ∑ v ⃗ i ∈ A k ∑ v ⃗ j ∉ A k w i j , (21.4) \begin{aligned}\mathcal{L}(A_1,\cdots,A_K)&=\text{Cut}(A_1,\cdots,A_K)\\ &=\sum_{k=1}^K \mathcal{W}(A_k, \bar{A}_k)\\ &=\sum_{k=1}^K\sum_{\vec{v}_i \in A_k}\sum_{\vec{v}_j \notin A_k}w_{ij},\end{aligned}\tag{21.4} L(A1,,AK)=Cut(A1,,AK)=k=1KW(Ak,Aˉk)=k=1Kv iAkv j/Akwij,(21.4)

则整个聚类问题可以建模为最小化总聚类损失的优化问题 min ⁡ { A k } k = 1 K L \underset{\{A_k\}_{k=1}^K}{\min}\mathcal{L} {Ak}k=1KminL,但这个优化目标可能因为数据分布不均衡而导致优化过程产生偏差,因此需要对目标函数进行归一化以排除偏差:
L N ( A 1 , ⋯   , A K ) = ∑ k = 1 K W ( A k , A ˉ k ) Δ k , (21.5) \mathcal{L}_{\text{N}}(A_1,\cdots,A_K)=\sum_{k=1}^K \frac{\mathcal{W}(A_k, \bar{A}_k)}{\Delta_k}, \tag{21.5} LN(A1,,AK)=k=1KΔkW(Ak,Aˉk),(21.5)

其中一种计算归一化因子 Δ k \Delta_k Δk 的方法是使用样本数,即 Δ k = ∣ A k ∣ \Delta_k=|A_k| Δk=Ak,但仅仅考虑样本数不足以消除偏差,因为各个节点在图中的关联度差异很大,因此可以使用基于类内总关联度的归一化因子,计算如下:
Δ k = degree ( A k ) = ∑ v ⃗ i ∈ A k degree ( v ⃗ i ) = ∑ v ⃗ i ∈ A k ∑ j = 1 N w i j . (21.6) \begin{aligned}\Delta_k&=\text{degree}(A_k)\\ &=\sum_{\vec{v}_i\in A_k}\text{degree}(\vec{v}_i)\\ &=\sum_{\vec{v}_i\in A_k}\sum_{j=1}^Nw_{ij}.\end{aligned}\tag{21.6} Δk=degree(Ak)=v iAkdegree(v i)=v iAkj=1Nwij.(21.6)

21.2.2. 模型求解

  指示向量(Indicator Vector):为了更优雅地表示优化变量,可以采用指示向量 y ⃗ i = [ y i 1 , ⋯   , y i K ] \vec{y}_i=[y_{i1}, \cdots, y_{iK}] y i=[yi1,,yiK] 表示每个节点 v ⃗ i \vec{v}_i v i (或样本 x ⃗ i \vec{x}_i x i)的类别,即 y i k = 1 y_{ik}=1 yik=1 表示该节点属于类别 A k A_k Ak,同时 ∑ k = 1 K y i k = 1 , ∀ i \sum_{k=1}^Ky_{ik}=1, \forall i k=1Kyik=1,i. 因此总体优化问题可以定义为:
Objective : min ⁡ Y = [ y ⃗ 1 , ⋯   , y ⃗ N ] T L N ( Y ) s.t. ∑ k = 1 K y i k = 1 , ∀ i (21.7) \begin{aligned}\text{Objective}:&\min_{Y=\left[\vec{y}_1, \cdots, \vec{y}_N\right]^T}\mathcal{L}_{\text{N}}(Y)\\ \text{s.t.}&\sum_{k=1}^Ky_{ik}=1, \forall i\end{aligned}\tag{21.7} Objective:s.t.Y=[y 1,,y N]TminLN(Y)k=1Kyik=1,i(21.7)

则该问题求解可以表示为: Y ^ = arg min ⁡ Y L N ( Y ) \hat{Y}=\underset{Y}{\argmin}\mathcal{L}_{\text{N}}(Y) Y^=YargminLN(Y).

  要求解模型,需要将其表示为矩阵形式,首先拆解聚类损失函数:
L N ( Y ) = ∑ k = 1 K W ( A k , A ˉ k ) ∑ v ⃗ i ∈ A k d i = tr [ ( W ( A 1 , A ˉ 1 ) ∑ v ⃗ i ∈ A 1 d i W ( A 2 , A ˉ 2 ) ∑ v ⃗ i ∈ A 2 d i ⋱ W ( A K , A ˉ K ) ∑ v ⃗ i ∈ A K d i ) ] = tr [ ( W ( A 1 , A ˉ 1 ) W ( A 2 , A ˉ 2 ) ⋱ W ( A K , A ˉ K ) ) ⋅ ( ∑ v ⃗ i ∈ A 1 d i ∑ v ⃗ i ∈ A 2 d i ⋱ ∑ v ⃗ i ∈ A K d i ) − 1 ] , (21.8) \begin{aligned} \mathcal{L}_{\text{N}}(Y)&=\sum_{k=1}^K\frac{\mathcal{W}(A_k,\bar{A}_k)}{\sum_{\vec{v}_i\in A_k}d_i}\\ &=\text{tr}\left[\left(\begin{matrix} \frac{\mathcal{W}(A_1,\bar{A}_1)}{\sum_{\vec{v}_i\in A_1}d_i} & & & \\ & \frac{\mathcal{W}(A_2,\bar{A}_2)}{\sum_{\vec{v}_i\in A_2}d_i} & & \\ & & \ddots & \\ & & & \frac{\mathcal{W}(A_K,\bar{A}_K)}{\sum_{\vec{v}_i\in A_K}d_i} \end{matrix}\right)\right]\\ &=\text{tr}\left[\left(\begin{matrix} \mathcal{W}(A_1,\bar{A}_1) & & & \\ & \mathcal{W}(A_2,\bar{A}_2) & & \\ & & \ddots & \\ & & & \mathcal{W}(A_K,\bar{A}_K) \end{matrix}\right)\cdot\right.\\ &\left. \left(\begin{matrix} {\sum_{\vec{v}_i\in A_1}d_i} & & & \\ & {\sum_{\vec{v}_i\in A_2}d_i} & & \\ & & \ddots & \\ & & & {\sum_{\vec{v}_i\in A_K}d_i} \end{matrix}\right)^{-1}\right], \end{aligned}\tag{21.8} LN(Y)=k=1Kv iAkdiW(Ak,Aˉk)=tr v iA1diW(A1,Aˉ1)v iA2diW(A2,Aˉ2)v iAKdiW(AK,AˉK) =tr W(A1,Aˉ1)W(A2,Aˉ2)W(AK,AˉK) v iA1div iA2div iAKdi 1 ,(21.8)

其中 d i = degree ( v ⃗ i ) = ∑ j = 1 N w i j d_i=\text{degree}(\vec{v}_i)=\sum_{j=1}^Nw_{ij} di=degree(v i)=j=1Nwij,令式(21.8)左右两个矩阵分别为 P P P Q − 1 Q^{-1} Q1,则 L N = tr ( P ⋅ Q − 1 ) \mathcal{L}_{\text{N}}=\text{tr}(P\cdot Q^{-1}) LN=tr(PQ1). 此时需要使用 W W W Y Y Y 表示 P P P Q Q Q 即可推导出模型的矩阵表示。

  根据指示矩阵 Y Y Y 进行推导:
Y T Y = [ y ⃗ 1 , ⋯   , y ⃗ N ] ⋅ [ y ⃗ 1 ⋮ y ⃗ N ] = ∑ i = 1 N y ⃗ i y ⃗ i T , (21.9) \begin{aligned} Y^TY&=\left[\vec{y}_1, \cdots, \vec{y}_N\right]\cdot\left[\begin{matrix}\vec{y}_1\\\vdots\\\vec{y}_N\end{matrix}\right]=\sum_{i=1}^N\vec{y}_i\vec{y}_i^T, \end{aligned}\tag{21.9} YTY=[y 1,,y N] y 1y N =i=1Ny iy iT,(21.9)

其中指示向量具有一个特性:当 v ⃗ i ∈ A k \vec{v}_i\in A_k v iAk 时,
y ⃗ i y ⃗ i T = { a p q } K × K , a p q = { 1 , p = q = k 0 , otherwise , (21.10) \vec{y}_i\vec{y}_i^T=\{a_{pq}\}_{K\times K}, a_{pq}=\left\{\begin{matrix}1, p=q=k\\0, \text{otherwise}\end{matrix}\right.,\tag{21.10} y iy iT={apq}K×K,apq={1,p=q=k0,otherwise,(21.10)

因此联立式(21.9)和式(21.10)可得:
Y T Y = ∑ i = 1 N y ⃗ i y ⃗ i T = ( ∑ v ⃗ i ∈ A 1 1 ∑ v ⃗ i ∈ A 2 1 ⋱ ∑ v ⃗ i ∈ A K 1 ) , (21.11) \begin{aligned} Y^TY&=\sum_{i=1}^N\vec{y}_i\vec{y}_i^T=\left(\begin{matrix} \sum_{\vec{v}_i\in A_1}1 &&&\\ &\sum_{\vec{v}_i\in A_2}1&&\\ &&\ddots&\\ &&&\sum_{\vec{v}_i\in A_K}1 \end{matrix}\right), \end{aligned}\tag{21.11} YTY=i=1Ny iy iT= v iA11v iA21v iAK1 ,(21.11)

因此设关联度对角矩阵 D = ( d 1 ⋱ d N ) = diag ( W ⋅ 1 ⃗ N ) D=\left(\begin{matrix}d_1&&\\&\ddots&\\&&d_N\end{matrix}\right)=\text{diag}(W\cdot \vec{1}_N) D= d1dN =diag(W1 N),则有:
Y T D Y = ∑ i = 1 N d i ⋅ y ⃗ i y ⃗ i T = ( ∑ v ⃗ i ∈ A 1 d 1 ∑ v ⃗ i ∈ A 2 d 2 ⋱ ∑ v ⃗ i ∈ A K d K ) = Q . (21.12) \begin{aligned} Y^TDY&=\sum_{i=1}^Nd_i\cdot\vec{y}_i\vec{y}_i^T\\&=\left(\begin{matrix} \sum_{\vec{v}_i\in A_1}d_1 &&&\\ &\sum_{\vec{v}_i\in A_2}d_2&&\\ &&\ddots&\\ &&&\sum_{\vec{v}_i\in A_K}d_K \end{matrix}\right)\\&=Q. \end{aligned}\tag{21.12} YTDY=i=1Ndiy iy iT= v iA1d1v iA2d2v iAKdK =Q.(21.12)

  另外,相似度损失可以有如下关系:
W ( A k , A ˉ k ) = ∑ v ⃗ i ∈ A k ∑ v ⃗ j ∉ A k w i j = ∑ v ⃗ i ∈ A k ( ∑ v ⃗ j ∈ V w i j − ∑ v ⃗ j ∈ A k w i j ) = ∑ v ⃗ i ∈ A k d i − W ( A k , A k ) , (21.13) \begin{aligned}\mathcal{W}(A_k, \bar{A}_k)&=\sum_{\vec{v}_i \in A_k}\sum_{\vec{v}_j \notin A_k}w_{ij}\\ &=\sum_{\vec{v}_i \in A_k}\left(\sum_{\vec{v}_j \in V}w_{ij}-\sum_{\vec{v}_j \in A_k}w_{ij}\right)\\ &=\sum_{\vec{v}_i \in A_k}d_i-\mathcal{W}(A_k, A_k),\end{aligned}\tag{21.13} W(Ak,Aˉk)=v iAkv j/Akwij=v iAk v jVwijv jAkwij =v iAkdiW(Ak,Ak),(21.13)

因此将式(21.13)带入矩阵 P P P 可得:
P = ( W ( A 1 , A ˉ 1 ) W ( A 2 , A ˉ 2 ) ⋱ W ( A K , A ˉ K ) ) = Q − ( W ( A 1 , A 1 ) W ( A 2 , A 2 ) ⋱ W ( A K , A K ) ) , (21.14) \begin{aligned} P&=\left(\begin{matrix} \mathcal{W}(A_1,\bar{A}_1) & & & \\ & \mathcal{W}(A_2,\bar{A}_2) & & \\ & & \ddots & \\ & & & \mathcal{W}(A_K,\bar{A}_K) \end{matrix}\right)\\ &=Q-\left(\begin{matrix} \mathcal{W}(A_1,A_1) & & & \\ & \mathcal{W}(A_2,A_2) & & \\ & & \ddots & \\ & & & \mathcal{W}(A_K,A_K) \end{matrix}\right) ,\end{aligned}\tag{21.14} P= W(A1,Aˉ1)W(A2,Aˉ2)W(AK,AˉK) =Q W(A1,A1)W(A2,A2)W(AK,AK) ,(21.14)

  为进一步推导,先计算
Y T W Y = ( y ⃗ 1 ⋯ y ⃗ N ) ⋅ ( w 11 ⋯ w 1 N ⋮ ⋱ ⋮ w N 1 ⋯ w N N ) ⋅ ( y ⃗ 1 T ⋮ y ⃗ N T ) = ∑ i = 1 N ∑ j = 1 N w i j ⋅ y ⃗ i y ⃗ j T = ( ∑ v ⃗ i ∈ A 1 ∑ v ⃗ j ∈ A 1 w i j ⋯ ∑ v ⃗ i ∈ A 1 ∑ v ⃗ j ∈ A K w i j ⋮ ⋱ ⋮ ∑ v ⃗ i ∈ A K ∑ v ⃗ j ∈ A 1 w i j ⋯ ∑ v ⃗ i ∈ A K ∑ v ⃗ j ∈ A K w i j ) , (21.15) \begin{aligned} Y^TWY&=\left(\begin{matrix}\vec{y}_1&\cdots&\vec{y}_N\end{matrix}\right)\cdot \left(\begin{matrix}w_{11}&\cdots&w_{1N}\\\vdots&\ddots&\vdots\\w_{N1}&\cdots&w_{NN}\end{matrix}\right)\cdot \left(\begin{matrix}\vec{y}_1^T\\\vdots\\\vec{y}_N^T\end{matrix}\right)\\ &=\sum_{i=1}^N\sum_{j=1}^N w_{ij}\cdot \vec{y}_i\vec{y}_j^T\\ &=\left(\begin{matrix}\sum_{\vec{v}_i\in A_1}\sum_{\vec{v}_j\in A_1}w_{ij}&\cdots&\sum_{\vec{v}_i\in A_1}\sum_{\vec{v}_j\in A_K}w_{ij}\\\vdots&\ddots&\vdots\\\sum_{\vec{v}_i\in A_K}\sum_{\vec{v}_j\in A_1}w_{ij}&\cdots&\sum_{\vec{v}_i\in A_K}\sum_{\vec{v}_j\in A_K}w_{ij}\end{matrix}\right), \end{aligned}\tag{21.15} YTWY=(y 1y N) w11wN1w1NwNN y 1Ty NT =i=1Nj=1Nwijy iy jT= v iA1v jA1wijv iAKv jA1wijv iA1v jAKwijv iAKv jAKwij ,(21.15)
尽管该矩阵与式(21.14)中减号后的矩阵不同,但因为最终的损失函数计算要取 tr ( ⋅ ) \text{tr}(\cdot) tr(),所以非对角线元素不影响计算结果,因此可以将损失函数表示为:
L N ( Y ) = tr ( P ⋅ Q − 1 ) = tr [ ( Y T D Y − Y T W Y ) ⋅ ( Y T D Y ) − 1 ] = tr [ Y T ( D − W ) Y ⋅ ( Y T D Y ) − 1 ] , (21.16) \begin{aligned} \mathcal{L}_{\text{N}}(Y)&=\text{tr}(P\cdot Q^{-1})\\ &=\text{tr}\left[(Y^TDY-Y^TWY)\cdot(Y^TDY)^{-1}\right]\\ &=\text{tr}\left[Y^T(D-W)Y\cdot(Y^TDY)^{-1}\right], \end{aligned}\tag{21.16} LN(Y)=tr(PQ1)=tr[(YTDYYTWY)(YTDY)1]=tr[YT(DW)Y(YTDY)1],(21.16)

其中 D − W D-W DW拉普拉斯矩阵。至此便完成了矩阵表示,可以对其求导得到解析解或梯度下降逼近解,过程略。

22. 前馈神经网络

22.1. 从机器学习到深度学习

  机器学习分为频率派和贝叶斯派,分别从不同的角度深入研究得到了不同的模型,也以不同的范式进入了深度学习时代。具体来说:

  • 频率派 → 统计学习
    • 正则化
    • 核化(Kernel SVM)
    • 集成化(Adaboost,Random Forest)
    • 层次化(Neural Network —— 狭义的深度学习)
      • MLP
      • AutoEncoder
      • CNN
      • RNN
  • 贝叶斯派 → 概率图模型
    • 有向图:Bayesian Network → Deep Directed Network
      • Sigmoid Belief Network
      • VAE
      • GAN
    • 无向图:Markov Network → Deep Bottzmam Machine
    • 有向+无向:Mixed Network → Deep Belief Network

   贝叶斯派的深度学习范式被称为 Deep Generative Model,也属于现代深度学习的分支,但因为概率图模型本身在增加深度后学习和推理难度显著增加,因此深度学习很多时候在狭义上指 Deep Neural Network 为基础的频率派深度学习方法。


http://www.kler.cn/a/588405.html

相关文章:

  • mysql学习-删除数据(drop、truncate、delete)
  • 【FMC214】基于VITA57.1标准的4路12G SDI视频传输FMC子卡模块
  • 2025年03月16日Github流行趋势
  • [JAVASE] Collection集合的遍历
  • PTA7-13 统计工龄
  • 【算法】动态规划
  • 3个 Vue nextTick 原理的关键点
  • (七)Spring Boot学习——Redis使用
  • Windows 注册表、定时任务与开机自启
  • 基于有限状态机的数字电路设计:Verilog 实践与探索
  • 柯南ED35 Hello Mr. My Yesterday日文歌词附假名注音,祭奠逝去的青春
  • 如何向 Linux 中加入一个 IO 扩展芯片
  • 4060ti-16G显卡部署deepseek-32B(支持联网搜索)
  • Android Room 框架表现层源码深度剖析(三)
  • Spring MVC 核心组件详解
  • Go语言进化之旅:从1.18到1.24的语法变革
  • 【SpringMVC】常用注解:@MatrixVariable
  • Spark sql 中row的用法
  • 深度学习 Deep Learning 第3章 概率论与信息论
  • 【C++初阶】模板初阶