Spectral clustering via ensemble deep autoencoder learning (SC-EDAE)
时间：2023-08-29 17:07:01
论文：2020 Pattern Recognition
网络结构
给定数据矩阵 X ∈ R n × d X \in R^{n×d} X∈Rn×d，首先使用 m m m不同的超参数AutoEncoder（由PCA建筑)训练，中间层表示 { Y l } l ∈ [ 1 , m ] \{Y_l \}_{l \in [1, m]} {
Yl}l∈[1,m]。然后通过每一个 Y l Y_l Yl构建图相似度矩阵 S l S_l Sl并将其融合成一个集成的图相似矩阵 S ˉ \bar S Sˉ。最后，在 S ˉ \bar S Sˉ上应用谱聚类方法。
接下来我们从谱聚类切入，详细介绍相似矩阵的构建过程。
谱聚类
这里使用的是对称拉普拉斯矩阵。
L s y m = D − 1 / 2 L D − 1 / 2 = I − D − 1 / 2 W D − 1 / 2 L_{sym} =D^{−1/2}LD^{−1/2} = I - D^{−1/2}WD^{−1/2} Lsym=D−1/2LD−1/2=I−D−1/2WD−1/2
对于无向图 G G G的切图，我们的目标是将图 G ( V , E ) G(V,E) G(V,E)切成相互没有连接的k个子图，每个子图点的集合为： A 1 , A 2 , . . . , A k A_1,A_2,...,A_k A1,A2,...,Ak，它们满足 A i ∩ A j = ∅ A_i∩A_j=∅ Ai∩Aj=∅,且 A 1 ∪ A 2 ∪ . . . ∪ A k = V A_1∪A_2∪...∪A_k=V A1∪A2∪...∪Ak=V.
对于任意两个子图点的集合 A , B ⊂ V , A ∩ B = ∅ A,B⊂V, A∩B=∅ A,B⊂V,A∩B=∅, 我们定义 A A A和 B B B之间的切图权重为：
W ( A , B ) = ∑ i ∈ A , j ∈ B w i j W(A, B) = \sum\limits_{i \in A, j \in B}w_{ij} W(A,B)=i∈A,j∈B∑wij
那么对于我们 k k k个子图点的集合： A 1 , A 2 , . . . , A k A_1,A_2,...,A_k A1,A2,...,Ak，我们定义切图cut为：
c u t ( A 1 , A 2 , . . . A k ) = 1 2 ∑ i = 1 k W ( A i , A ‾ i ) cut(A_1,A_2,...A_k) = \frac{1}{2}\sum\limits_{i=1}^{k}W(A_i, \overline{A}_i ) cut(A1,A2,...Ak)=21i=1∑kW(Ai,Ai)
其中 A ˉ i \bar A_i Aˉi为 A i A_i Ai的补集，意为除 A i A_i Ai子集外其他 V V V的子集的并集。
那么如何切图可以让子图内的点权重和高，子图间的点权重和低呢？一个自然的想法就是最小化 c u t ( A 1 , A 2 , . . . , A k ) cut(A_1,A_2,...,A_k) cut(A1,A2,...,Ak), 但是可以发现，这种极小化的切图存在问题，如下图
我们选择一个权重最小的边缘的点，比如C和H之间进行cut，这样可以最小化 c u t ( A 1 , A 2 , . . . , A k ) cut(A_1,A_2,...,A_k) cut(A1,A2,...,Ak), 但是却不是最优的切图，如何避免这种切图，并且找到类似图中"Best Cut"这样的最优切图呢，可以用下面的Ncut的切图方法。
Ncut切图
对每个切图，不光考虑最小化cut(A1,A2,…Ak)，它还同时考虑最大化每个子图点的权重
N C u t ( A 1 , A 2 , . . . A k ) = 1 2 ∑ i = 1 k W ( A i , A ‾ i ) v o l ( A i ) NCut(A_1,A_2,...A_k) = \frac{1}{2}\sum\limits_{i=1}^{k}\frac{W(A_i, \overline{A}_i )}{vol(A_i)} NCut(A1,A2,...Ak)=21i=1∑kvol(Ai)W(Ai,Ai)
那么怎么最小化这个Ncut函数呢？牛人们发现，Ncut函数可以通过如下方式表示。
我们引入指示向量 h j ∈ { h 1 , h 2 , . . . , h k } h_j∈\{h_1,h_2,...,h_k\} hj∈{
h1,h2,...,hk}, j = 1 , 2 , . . . k , j=1,2,...k, j=1,2,...k,对于任意一个向量 h j h_j hj, 它是一个n维向量（n为样本数），我们定义 h i j h_{ij} hij为：
h i j = { 0 v i ∉ A j 1 v o l ( A j ) v i ∈ A j h_{ij}= \begin{cases} 0& { v_i \notin A_j}\\ \frac{1}{\sqrt{vol(A_j)}}& { v_i \in A_j} \end{cases} hij={
0vol(Aj)1vi∈元器件数据手册、IC替代型号，打造电子元器件IC百科大全！
