[关闭]
@hainingwyx 2017-06-07T09:28:17.000000Z 字数 1585 阅读 806

Modularity-based model selection for kernel spectral clustering

聚类


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

模型选择

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

其中是相似度矩阵,表示所有权重的和,对于非加权网络,表示图中所有的连线的数量。表示随机模型中节点连线的值。表示节点在同一个簇中,否则就是。因为标准随机图限制度序列和实际度序列相等,所以可以写成

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

其中, 是模块矩阵或者Q拉普拉斯矩阵。是每个节点的度组成的向量,是对角矩阵,表示簇节点的数量,为簇指示矩阵。

算法流程

算法流程

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

验证过程可以分为两步:

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

数据处理
加权图
加权图使用RBF核。对于BLF,如果使用亲密度矩阵,对于大尺度网络会带来非常大的计算和存储消耗。所以采用以下策略。

  1. 从大的亲密度矩阵中选择一个子矩阵,代表整个网络的子图
  2. 改变观点,将这个矩阵看做欧式空间中的训练数据矩阵
  3. 验证集是和训练集维度相同的数据矩阵

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

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

非加权图
commmunity核用于建立图相似度矩阵,不需要调整参数。定义为两个节点相同邻居的数量,其中表示节点相同邻居的集合,表示图的邻接矩阵。所以即使两个节点没有直接相连,但是它们共享很多邻居,它们的相似度也会很大。

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

仿真

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

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

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

Western USA power grid network

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

未来工作

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注