摘要: 分享对论文的理解, 原文见 Xi Peng, Yunfan Li, Ivor W. Tsang, Hongyuan Zhu, Jiancheng Lv, Joey Tianyi Zhou,
XAI Beyond Classification: Interpretable Neural Clustering, Journal of Machine Learning Research 22 (2021) 1–27.
源码地址: www.pengxi.me.
1. 符号系统
符号风格按照本贴作者的习惯有所修改.
| 符号 | 涵义 | 备注 |
|---|---|---|
| X = { x 1 , … , x n } \mathbf{X} = \{\mathbf{x}_1, \dots, \mathbf{x}_n\} X={x1,…,xn} | 数据集 | n n n 为实例个数 |
| x i = ( x i 1 , … , x i m ) \mathbf{x}_i = (x_{i1}, \dots, x_{im}) xi=(xi1,…,xim) | 对象/实例 | m m m 为特征个数/数据维度 |
| S = { S 1 , … , S k } \mathcal{S} = \{\mathbf{S}_1, \dots, \mathbf{S}_k\} S={S1,…,Sk} | 聚类结果/数据集划分 | k k k 为簇数 |
| S i = { s i 1 , … , s i n i } ⊂ X \mathbf{S}_i = \{\mathbf{s}_{i1}, \dots, \mathbf{s}_{i n_i}\} \subset \mathbf{X} Si={si1,…,sini}⊂X | 第 i i i 簇 | ∑ i = 1 k n i = n \sum_{i = 1}^k n_i = n ∑i=1kni=n |
| Ω = ( ω 1 , … , ω k ) \mathbf{\Omega} = (\mathbf{\omega}_1, \dots, \mathbf{\omega}_k) Ω=(ω1,…,ωk) | 聚类中心点 | |
| ω i = ( ω i 1 , … , ω i m ) \mathbf{\omega}_i = (\omega_{i1}, \dots, \omega_{im}) ωi=(ωi1,…,ωim) | ω i = 1 n i ∑ j = 1 n i s i j \mathbf{\omega}_i = \frac{1}{n_i}\sum_{j=1}^{n_i} \mathbf{s}_{ij} ωi=ni1∑j=1nisij | S i \mathbf{S}_i Si 的均值 |
| W = ( w i j ) k × m \mathbf{W} = (w_{ij})_{k \times m} W=(wij)k×m | 2 2 2 倍 Ω \mathbf{\Omega} Ω | 主要是改个形式方便神经网络 |
下面给出一个数据集:
0.2, 0.3
0.1, 0.4
0.5, 0.6
0.6, 0.8
0.7, 0.2
0.9, 0.3
其中, n = 6 n = 6 n=6, m = 2 m = 2 m=2. (鹏鹏作业: 做一个 n = 20 n = 20 n=20 的人造数据集.)
2. k k kMeans 算法
k
k
kMeans 的目标是求一个最优聚类方案 (划分)
S
∗
=
arg min
S
∑
j
=
1
k
∑
x
i
∈
S
j
∥
x
i
−
ω
j
∥
2
2
.
(1)
\mathcal{S}^* = \argmin_{\mathcal{S}} \sum_{j = 1}^k \sum_{\mathbf{x}_i \in \mathbf{S}_j} \|\mathbf{x}_i - \mathbf{\omega}_j\|_2^2. \tag{1}
S∗=Sargminj=1∑kxi∈Sj∑∥xi−ωj∥22.(1)
换言之, 就是最大化各簇的"内聚性"之和.
为尽可能降低理解难度, 解释如下:
∥
x
i
−
ω
j
∥
2
2
=
∑
l
=
1
m
(
x
i
l
−
ω
j
l
)
2
=
(
x
i
1
−
ω
j
1
)
2
+
⋯
+
(
x
i
m
−
ω
j
m
)
2
,
(2)
\|\mathbf{x}_i - \mathbf{\omega}_j\|_2^2 = \sum_{l = 1}^m (x_{il} - \omega_{jl})^2 = (x_{i1} - \omega_{j1})^2 + \dots + (x_{im} - \omega_{jm})^2, \tag{2}
∥xi−ωj∥22=l=1∑m(xil−ωjl)2=(xi1−ωj1)2+⋯+(xim−ωjm)2,(2)
即为两个
m
m
m 维数据点的欧氏距离平方.
k k kMeans 算法描述如下:
- Step 1. 随机选择 k k k 个数据点, 获得 Ω \mathbf{\Omega} Ω;
- Step 2. 对于任意
x
i
∈
X
\mathbf{x}_i \in \mathbf{X}
xi∈X, 计算它到
Ω
\mathbf{\Omega}
Ω 中各点的距离, 并确定其簇编号为
c ( x i ) = arg min j ∥ x i − ω j ∥ 2 2 , (3) c(\mathbf{x}_i) = \argmin_j \|\mathbf{x}_i - \mathbf{\omega}_j\|_2^2, \tag{3} c(xi)=jargmin∥xi−ωj∥22,(3)
由此构建 S j = { x i ∣ c ( x i ) = j } \mathbf{S}_j = \{\mathbf{x}_i \vert c(\mathbf{x}_i) = j\} Sj={xi∣c(xi)=j}. - Step 3. 计算各簇的新中心集合
Ω
′
=
(
ω
1
′
,
…
,
ω
k
′
)
\mathbf{\Omega}' = (\mathbf{\omega}_1', \dots, \mathbf{\omega}_k')
Ω′=(ω1′,…,ωk′), 其中
ω i ′ = 1 n i ∑ j = 1 n i s i j ; (4) \mathbf{\omega}_i' = \frac{1}{n_i}\sum_{j=1}^{n_i} \mathbf{s}_{ij}; \tag{4} ωi′=ni1j=1∑nisij;(4) - Step 4. 如果 Ω ′ = Ω \mathbf{\Omega}' = \mathbf{\Omega} Ω′=Ω, 则表示收敛, 算法结束; 否则转到 Step 2.
该算法的 Java 代码见 第 56 天: kMeans 聚类.
- 问题1:
k
k
kMeans 能保证收敛到全局最优解吗?
回答: 不能. 不同的初始聚类中心选择, 可能导致不同的聚类结果.
(鹏鹏作业: 根据所构造例子, 用 k k kMeans 获得两种聚类结果, 并展示其过程.) - 问题2: 优化问题 (1) 式是一个困难问题吗?
回答: 它是一个 NP 完全问题.
(鹏鹏作业: 找到相应的证明, 可以不去手动证明, 贴图即可.) - 问题 3: 簇确定后, 为什么聚类中心点的计算为 (3) 式, 用其它的点会不会导致 (1) 式更小?
(鹏鹏作业: 自己去证明.)
3. 用神经网络来实现
将 (1) 式改写为:
min
∑
i
=
1
n
∑
j
=
1
k
I
j
(
x
i
)
∥
x
i
−
ω
j
∥
2
2
,
(5)
\min \sum_{i = 1}^n \sum_{j = 1}^k \mathcal{I}_j(\mathbf{x}_i) \|\mathbf{x}_i - \mathbf{\omega}_j\|_2^2, \tag{5}
mini=1∑nj=1∑kIj(xi)∥xi−ωj∥22,(5)
其中
I
j
(
x
i
)
\mathcal{I}_j(\mathbf{x}_i)
Ij(xi) 对于任意一个
i
i
i 而言, 仅有一个
j
j
j 所对应的值为
1
1
1, 其余
j
j
j 对应的值为
0
0
0. 可以把它写成一个
n
×
k
n \times k
n×k 矩阵, 如:
I
=
(
1
0
0
0
1
0
1
0
0
0
0
1
0
0
1
0
1
0
)
,
\mathcal{I} = \left( \begin{array}{llll} 1 & 0 & 0\\ 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 0 & 1\\ 0 & 1 & 0\\ \end{array} \right),
I=
101000010001000110
,
它表示对象被划分为
S
=
{
{
x
1
,
x
3
}
,
{
x
2
,
x
6
}
,
{
x
4
,
x
5
}
}
\mathcal{S} = \{\{\mathbf{x}_1, \mathbf{x}_3\}, \{\mathbf{x}_2, \mathbf{x}_6\}, \{\mathbf{x}_4, \mathbf{x}_5\}\}
S={{x1,x3},{x2,x6},{x4,x5}}. 我认为使用
I
i
j
\mathcal{I}_{ij}
Iij 可能比
I
j
(
x
i
)
\mathcal{I}_j(\mathbf{x}_i)
Ij(xi) 这种函数形式更好看一点.
(鹏鹏作业: 根据程序运行结果, 把自己数据对应的布尔矩阵写出来.)
注意 (5) 式与 (1) 式等价. 为了便于优化, 将该布尔矩阵换成一个小数矩阵, 其中原来为 0 0 0 的值不变, 1 1 1 则成为一个 ( 0 , 1 ] (0, 1] (0,1] 区间的小数. 先把它理解为一个隶属度 (cluster membership) 吧, 越接近聚类中心的点, 该值越接近 1 1 1.
将 (2) 式改写为
∥
x
i
−
ω
j
∥
2
2
=
∑
l
=
1
m
(
x
i
l
−
ω
j
l
)
2
=
∑
l
=
1
m
x
i
l
2
−
2
x
i
l
ω
j
l
+
ω
j
l
2
=
∥
x
i
∥
2
2
−
2
ω
j
T
x
i
+
∥
ω
j
∥
2
2
,
(6)
\begin{array}{ll}\|\mathbf{x}_i - \mathbf{\omega}_j\|_2^2 & = \sum_{l = 1}^m (x_{il} - \omega_{jl})^2\\ & = \sum_{l = 1}^m x_{il}^2 - 2 x_{il}\omega_{jl} + \omega_{jl}^2 \\ & = \|\mathbf{x}_i\|_2^2 - 2\mathbf{\omega}_j^{\mathsf{T}}\mathbf{x}_i + \|\mathbf{\omega}_j\|_2^2, \end{array}\tag{6}
∥xi−ωj∥22=∑l=1m(xil−ωjl)2=∑l=1mxil2−2xilωjl+ωjl2=∥xi∥22−2ωjTxi+∥ωj∥22,(6)
这里使用转置符号
T
\mathsf{T}
T 是为了支撑内积的计算.
令
β
i
=
∥
x
i
∥
2
2
,
(7)
\beta_i = \|\mathbf{x}_i\|_2^2, \tag{7}
βi=∥xi∥22,(7)
它是
x
i
\mathbf{x}_i
xi 与坐标原点距离的平方, 在聚类算法执行过程中不变, 因此可以看作是一个常数.
b
j
=
∥
ω
j
∥
2
2
,
(8)
b_j = \|\mathbf{\omega}_j\|_2^2, \tag{8}
bj=∥ωj∥22,(8)
是
ω
i
\mathbf{\omega}_i
ωi 与坐标原点距离的平方, 在聚类算法执行过程改变.
w
j
=
2
ω
j
.
(9)
\mathbf{w}_j = 2\mathbf{\omega}_j. \tag{9}
wj=2ωj.(9)
因此 (6) 式进一步被改造成
∥
x
i
−
ω
j
∥
2
2
=
β
i
−
w
j
T
x
i
−
b
j
.
(10)
\|\mathbf{x}_i - \mathbf{\omega}_j\|_2^2 = \beta_i - \mathbf{w}_j^{\mathsf{T}}\mathbf{x}_i - b_j. \tag{10}
∥xi−ωj∥22=βi−wjTxi−bj.(10)
令
I
i
j
=
exp
(
−
∥
x
i
−
ω
j
∥
2
2
/
τ
)
∑
j
=
1
k
exp
(
−
∥
x
i
−
ω
j
∥
2
2
/
τ
)
,
(11)
\mathcal{I}_{ij} = \frac{\exp\left(- \|\mathbf{x}_i\ - \mathbf{\omega}_j \|_2^2 / \tau \right)}{\sum_{j=1}^k \exp\left(- \|\mathbf{x}_i\ - \mathbf{\omega}_j \|_2^2 \right / \tau)}, \tag{11}
Iij=∑j=1kexp(−∥xi −ωj∥22/τ)exp(−∥xi −ωj∥22/τ),(11)
如果某一数据点与自己的簇中心越近, 则分子越大; 离别人的簇中心越远, 则分子越小. 且该数据取值区间为
(
0
,
1
)
(0, 1)
(0,1). 其中
τ
\tau
τ 为温度因子 (可能与模拟退火法相关).
(鹏鹏作业: 根据 (11) 式及自己的例子计算
I
\mathcal{I}
I 矩阵, 分别设置
τ
=
0.1
,
0.5
,
0.9
\tau = 0.1, 0.5, 0.9
τ=0.1,0.5,0.9 各计算一次.)
实际上, (11) 式为 softmax 函数的一种扩展, 它在神经网络中很常用.
简单起见, 仅考虑单个样本
x
i
\mathbf{x}_i
xi 的损失.
L
i
=
∑
j
L
i
j
=
∑
j
I
i
j
(
β
i
−
w
j
T
x
i
−
b
j
)
(12)
\mathcal{L}_i = \sum_j \mathcal{L}_{ij} = \sum_j \mathcal{I}_{ij} \left(\beta_i - \mathbf{w}_j^{\mathsf{T}}\mathbf{x}_i - b_j\right)\tag{12}
Li=j∑Lij=j∑Iij(βi−wjTxi−bj)(12)
图 1 展示了对应于 (12) 式的损失函数计算实现方式.
令
z
i
j
=
−
β
i
+
w
j
T
x
i
+
b
j
z_{ij} = - \beta_i + \mathbf{w}_j^{\mathsf{T}}\mathbf{x}_i + b_j
zij=−βi+wjTxi+bj
L
i
=
−
∑
j
exp
(
z
i
j
/
τ
)
∑
j
=
1
k
exp
(
z
i
j
/
τ
)
z
i
j
=
−
∑
j
f
(
z
i
j
)
(12)
\begin{array}{ll}\mathcal{L}_i & = - \sum_j \frac{\exp(z_{ij} / \tau)}{\sum_{j=1}^k \exp(z_{ij} / \tau)} z_{ij}\\ & = - \sum_j f(z_{ij}) \end{array} \tag{12}
Li=−∑j∑j=1kexp(zij/τ)exp(zij/τ)zij=−∑jf(zij)(12)
因此, 优化目标可以写为
max
∑
j
f
(
z
i
j
)
,
where
z
i
j
=
−
β
i
+
w
j
T
x
i
+
b
j
.
(13)
\begin{array}{l} \max \sum_{j} f(z_{ij}),\\ \textrm{where } z_{ij} = - \beta_i + \mathbf{w}_j^{\mathsf{T}}\mathbf{x}_i + b_j. \end{array} \tag{13}
max∑jf(zij),where zij=−βi+wjTxi+bj.(13)
然而, 这里的
z
i
j
z_{ij}
zij 中,
w
j
\mathbf{w}_j
wj 和
b
j
b_j
bj 相互依赖 (耦合), 无法进行有效的优化. 为此, 必须在训练阶段将拆开.
使用支持向量机类似的方案, 将这里的常数和
b
j
b_j
bj 归一化, 同时
ω
j
=
ω
j
/
∥
ω
j
∥
\mathbf{\omega}_j = \mathbf{\omega}_j / \|\mathbf{\omega}_j\|
ωj=ωj/∥ωj∥, 可以获得
L
i
=
∑
j
I
i
j
(
2
−
w
j
T
x
i
)
(14)
\mathcal{L}_i = \sum_j \mathcal{I}_{ij} \left(2 - \mathbf{w}_j^{\mathsf{T}}\mathbf{x}_i\right) \tag{14}
Li=j∑Iij(2−wjTxi)(14)
如图 2 所示, 进行式 (14) 的权重归一化之后, 向量的模被控制在单位长度, 以免趋近于无穷; 梯度归一化之后, 变化量被控制在一定范围, 类似于梯度下降时使用的步长, 以避免抖动并保证收敛.
现在将聚类嵌入到一个编码-解码器结构中, 令文章来源：https://www.toymoban.com/news/detail-490180.html
L
=
L
r
e
c
+
L
c
l
u
=
∑
i
∥
x
i
−
g
(
h
(
x
i
)
)
∥
2
2
+
λ
∑
i
,
j
I
i
j
(
2
−
w
j
T
h
(
x
i
)
.
)
\mathcal{L} = \mathcal{L}_\mathrm{rec} + \mathcal{L}_\mathrm{clu} = \sum_{i} \|\mathbf{x}_i - g(h(\mathbf{x}_i))\|_2^2 + \lambda \sum_{i, j} \mathcal{I}_{ij} \left(2 - \mathbf{w}_j^{\mathsf{T}}h(\mathbf{x}_i). \right)
L=Lrec+Lclu=i∑∥xi−g(h(xi))∥22+λi,j∑Iij(2−wjTh(xi).)
其中
h
(
⋅
)
h(\cdot)
h(⋅) 和
g
(
⋅
)
g(\cdot)
g(⋅) 分别为编码、解码函数.文章来源地址https://www.toymoban.com/news/detail-490180.html
- rec 表示 reconstruction, clu 表示 clustering, 也就是说, 同时考虑数据重建与聚类的损失.
- 使用编码 (本质是特征提取) 后的特征进行聚类, 有可能是将原始空间中非球形的簇变换到接近球形;
- 这里使用 h h h 代替原文的 f f f 是为了避免与 (13) 式的 f f f 冲突.
- 论文里面设置 λ = 0.01 \lambda = 0.01 λ=0.01, 不知道为什么如此小, 聚类效果如此不重要吗? (鹏鹏作业: 在实际数据上运行, 看两个损失的比例.)
4. Model Explainability vs. Interpretable Model
- 前者是模型可解释性, 即获得的中间结果, 最终结果是否可以被强行解释.
- 后者是可解释模型, 即模型本身的机制是否可解释的.
到了这里，关于论文笔记: 可解释神经聚类 (鹏鹏专用)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
