Modularity-based model selection for kernel spectral clustering

聚类

---

这是基于KSC框架的，用于选择调节参数的算法。之前的BLF仅在簇可分性好的时候得到最优的结果。而实际的簇往往是存在尺寸不同或者存在重叠。比较好的划分，其Modurity模块性会比较高。所以模块性可以用于聚类有效性的评价。

模型选择

首先通过选择不同的参数进行训练，通过比较验证集的模块性，选择最优参数。模块性在2006年的“Modularity and community structure in networks”中首次提出。这是基于随机图不可能有聚类结构，通过比较随机的图和真实的图的连线可以得到可能的簇。模块性可正可负，正且较大时，意味着有很强的结构。

$$Q={1 \over 2m}\sum_{ij}(S_{ij}-F_{ij})\delta_{ij}$$

其中$i, j \in A_p, p= 1,...k,S$是相似度矩阵,$m$表示所有权重的和，对于非加权网络，$m$表示图中所有的连线的数量。$F_{ij}$表示随机模型中节点$i$和$j$连线的值。$\delta _{ij}=1$表示节点$i$和$j$在同一个簇中，否则就是$0$。因为标准随机图限制度序列和实际度序列相等，所以可以写成

$$Q={1 \over 2m}{\sum}_{ij}(S_{ij}-{d_{i}d_{j} \over 2m})\delta_{ij}$$

通过线性代数计算，最大化Q可转换成

$$\max_{X}[{\rm tr}(X^{T}MX)]\ {\rm such\ that}\ X^{T}X=D^{M}$$

其中， $M=S-{1 \over 2m}dd^{T}$是模块矩阵或者Q拉普拉斯矩阵。$d=[d_{1}, \ldots, d_{N}]$是每个节点的度组成的向量，$D^{M}\in {\bf R}^{k\times k}$是对角矩阵，$D_{ii}^{M}=\vert C_{i}\vert$，$\vert C_{i}\vert$表示簇$C_i$节点的数量，$X$为簇指示矩阵。

算法流程

X的计算比较简单，有不止一个X满足要求。

验证过程可以分为两步：

1. 预测验证集
2. 评估验证集

数据处理
加权图
加权图使用RBF核。对于BLF，如果使用亲密度矩阵$S\in {R}^{N\times N}$，对于大尺度网络会带来非常大的计算和存储消耗。所以采用以下策略。

1. 从大的亲密度矩阵中选择一个子矩阵$S\in {R}^{C\times C},C < N$，代表整个网络的子图
2. 改变观点，将这个矩阵看做欧式空间中的训练数据矩阵
3. 验证集是和训练集维度相同的数据矩阵

对于模块性算法，前面步骤相同，后面第二步验证过程还是回到欧式空间表示图。训练集是亲密度子图矩阵，验证集是剩下的子图矩阵。因为模块性矩阵B在定义中包含了亲密度矩阵，所以只能求验证集的亲密度矩阵了。

前25%作为训练集，后75%作为验证集。第一列表示验证过程的第一步，预测所属。第二列是第二步，验证的阶段。对于模块性算法，免不了求亲密度矩阵的步骤。

非加权图
commmunity核用于建立图相似度矩阵，不需要调整参数。$K_{ij}$定义为两个节点$i$和$j$相同邻居的数量$K_{ij}=\sum_{k,l\in {\cal N}_{ij}}A_{kl}$，其中${\cal N}_{ij}$表示节点$i$和$j$相同邻居的集合，$A$表示图的邻接矩阵。所以即使两个节点没有直接相连，但是它们共享很多邻居，它们的相似度$k_{ij}$也会很大。

BLF，学习训练过程，将图看成邻接列表，每一行看做源节点。模块性，第一步不是用的方形邻接矩阵。

仿真

关联列表：邻接列表的变种，允许用二外的连接描述连接

邻接矩阵：二维布尔矩阵，行和列表示二位源点和目标点，

关联矩阵：二维布尔矩阵，行代表定点，列代表边。

Louvain方法的结果是41类。BLF没有检测到网络的结构，因为其BLF值非常小。

未来工作

运用主动采样技术，如Renyi熵标准，以获得更好的训练集。