基于低秩约束的熵加权多视角模糊聚类算法

随着多样化信息获取技术的发展, 人们可以从不同途径或不同角度来获取对象的特征数据, 即多视角数据. 多视角数据包含了同一对象不同角度的信息. 例如: 网页数据中既包含网页内容又包含网页链接信息; 视频内容中既包含视频信息又包含音频信息; 图像数据中既涉及颜色直方图特征、纹理特征等图像特征, 又涉及描述该图像内容的文本. 多视角学习能有效地对多视角数据进行融合, 避免了单视角数据数据信息单一的问题[1-4].

多视角模糊聚类是一种有效的无监督多视角学习方法[5-7]. 它通过在多视角聚类过程中引入各样本对不同类别的模糊隶属度来描述各视角下样本属于该类别的不确定性程度. 经典的工作有: 文献[8]以经典的单视角模糊C均值(Fuzzy C-means, FCM)算法作为基础模型, 利用不同视角间的互补信息确定协同聚类的准则, 提出了Co-FC (Collaborative fuzzy clustering)算法; 文献[9]参考文献[8]的协同思想提出Co-FKM (Multiview fuzzy clustering algorithm collaborative fuzzy K-means)算法, 引入双视角隶属度惩罚项, 构造了一种新型的无监督多视角协同学习方法; 文献[10]借鉴了Co-FKM和Co-FC所使用的双视角约束思想, 通过引入视角权重, 并采用集成策略来融合多视角的模糊隶属度矩阵, 提出了WV-Co-FCM (Weighted view colla-borative fuzzy C-means) 算法; 文献[11]通过最小化双视角下样本与聚类中心的欧氏距离来减小不同视角间的差异性, 基于K-means聚类框架提出了Co-K-means (Collaborative multi-view K-means clustering)算法; 在此基础上, 文献[12]提出了基于模糊划分的TW-Co-K-means (Two-level wei-ghted collaborative K-means for multi-view clustering)算法, 对Co-K-means算法中的双视角欧氏距离加入一致性权重, 获得了比Co-K-means更好的多视角聚类结果. 以上多视角聚类方法都基于成对视角来构造不同的正则化项来挖掘视角之间的一致性和差异性信息, 缺乏对多个视角的整体考虑.

一致性和差异性是设计多视角聚类算法需要考虑的两个重要原则[10-14]. 一致性是指在多视角聚类过程中, 各视角的聚类结果应该尽可能保持一致. 在设计多视角聚类算法时, 往往通过协同、集成等手段来构建全局划分矩阵, 从而得到最终的聚类结果[14-16]. 差异性是指多视角数据中的每个视角均反映了对象在不同方面的信息, 这些信息互为补充[10], 在设计多视角聚类算法时需要对这些信息进行充分融合. 综合考虑这两方面的因素, 本文拟提出新型的低秩约束熵加权多视角模糊聚类算法(Entropy-weighting multi-view fuzzy C-means with low rank constraint, LR-MVEWFCM), 其主要创新点可以概括为以下3个方面:

1)在模糊聚类框架下提出了面向视角一致性的低秩约束准则. 已有的多视角模糊聚类算法大多基于成对视角之间的两两关系来构造正则化项, 忽视了多个视角的整体一致性信息. 本文在模糊聚类框架下从视角全局一致性出发引入低秩约束正则化项, 从而得到新型的低秩约束多视角模糊聚类算法.

2) 在模糊聚类框架下同时考虑多视角聚类的一致性和差异性, 在引入低秩约束的同时进一步使用面向视角差异性的多视角香农熵加权策略; 在迭代优化的过程中, 通过动态调节视角权重系数来突出具有更好分离性的视角的权重, 从而提高聚类性能.

3)在模糊聚类框架下首次使用交替方向乘子法(Alternating direction method of multipliers, ADMM)[15]对LR-MVEWFCM算法进行优化求解.

在本文中, 令N$N$为样本总量, D$D$为样本维度, K$K$为视角数目, C$C$为聚类数目, m$m$为模糊指数. 设xj,k${\mathit{x}}_{j,k}$表示多视角场景中第j$j$个样本第k$k$个视角的特征向量, j=1,⋯,N$j=1,\cdots ,N$, k=1,⋯,K$k=1,\cdots ,K$; vi,k${\mathit{v}}_{i,k}$表示第k$k$个视角下, 第i$i$个聚类中心, i=1,⋯,C$i=1,\cdots ,C$; Uk=[μij,k]$U_k=\left[{\mu }_{ij,k}\right]$表示第k$k$个视角下的模糊隶属度矩阵, 其中μij,k${\mu }_{ij,k}$是第k$k$个视角下第j$j$个样本属于第i$i$个聚类中心的模糊隶属度, i=1,⋯,C$i=1,\cdots ,C$, j=1,⋯,N.$j=1,\cdots ,N.$

本文第1节在相关工作中回顾已有的经典模糊C均值聚类算法FCM模型[17]和多视角模糊聚类Co-FKM模型[9]; 第2节将低秩理论与多视角香农熵理论相结合, 提出本文的新方法; 第3节基于模拟数据集和UCI (University of California Irvine)数据集验证本文算法的有效性, 并给出实验分析; 第4节给出实验结论.

1.   相关工作

1.1   模糊C均值聚类算法FCM

设单视角环境下样本x1,⋯,xN∈RD${\mathit{x}}_1,\cdots ,{\mathit{x}}_N\in {\mathbf{R}}^D$, U=[μi,j]$U=[{\mu }_{i,j}]$是模糊划分矩阵, V=[v1,v2,⋯,vC]$V=[{\mathit{v}}_1,{\mathit{v}}_2,\cdots ,{\mathit{v}}_C]$是样本的聚类中心. FCM算法的目标函数可表示为

可得到JFCM$J_{\mathrm{F}\mathrm{C}\mathrm{M}}$取得局部极小值的必要条件为

根据式(2)和式(3)进行迭代优化, 使目标函数收敛于局部极小点, 从而得到样本属于各聚类中心的模糊划分矩阵U$U$.

1.2   多视角模糊聚类Co-FKM模型

在经典FCM算法的基础上, 文献[9]通过引入视角协同约束正则项, 对视角间的一致性信息加以约束, 提出了多视角模糊聚类Co-FKM模型.

多视角模糊聚类Co-FKM模型需要满足如下条件:

多视角模糊聚类Co-FKM模型的目标函数JCo-FKM$J_{\mathrm{C}\mathrm{o}\text{-}\mathrm{F}\mathrm{K}\mathrm{M}}$定义为

式(5)中, η$\eta$表示协同划分参数; Δ$\mathrm{\Delta }$表示视角一致项, 由式(6)可知, 当各视角趋于一致时, Δ$\mathrm{\Delta }$将趋于0.

迭代得到各视角的模糊隶属度μij,k${\mu }_{ij,k}$后, 为了最终得到一个具有全局性的模糊隶属度划分矩阵, Co-FKM算法对各视角下的模糊隶属度采用几何平均的方法, 得到数据集的整体划分, 具体形式为

其中, μ^ij${\hat{\mu }}_{ij}$为全局模糊划分结果.

2.   基于低秩约束的熵加权多视角模糊聚类算法

针对当前多视角模糊聚类算法研究中存在的不足, 本文提出一种基于低秩约束的熵加权多视角模糊聚类新方法LR-MVEWFCM. 一方面通过向多视角模糊聚类算法的目标学习准则中引入低秩约束项, 在整体上控制聚类过程中各视角的一致性; 另一方面基于香农熵理论, 通过熵加权机制来控制各视角之间的差异性. 同时使用交替方向乘子法对模型进行优化求解.

设多视角隶属度U1,⋯,UK$U_1,\cdots ,U_K$融合为一个整体的隶属度矩阵U$U$, 将矩阵U$U$的秩函数凸松弛为核范数, 通过对矩阵U$U$进行低秩约束, 可以将多视角数据之间的一致性问题转化为核范数最小化问题进行求解, 具体定义为

其中, U=[U1⋯UK]T$U=[U_1\cdots U_K{]}^{\mathrm{T}}$表示全局划分矩阵, ∥⋅∥∗${\Vert \cdot \Vert }_{\ast }$表示核范数. 式(8)的优化过程保证了全局划分矩阵的低秩约束. 低秩约束的引入, 可以弥补当前大多数多视角聚类算法仅能基于成对视角构建约束的缺陷, 从而更好地挖掘多视角数据中包含的全局一致性信息.

目前已有的多视角的聚类算法在处理多视角数据时, 通常默认每个视角平等共享聚类结果[11], 但实际上某些视角的数据往往因空间分布重叠而导致可分性较差. 为避免此类视角的数据过多影响聚类效果, 本文拟对各视角进行加权处理, 并构建香农熵正则项从而在聚类过程中有效地调节各视角之间的权重, 使得具有较好可分离性的视角的权重系数尽可能大, 以达到更好的聚类效果.

令视角权重系数∑Kk=1wk=1$\sum _{k=1}^K{w}_k=1$且wk≥0$w_k\ge 0$, 则香农熵正则项表示为

综上所述, 本文作如下改进: 首先, 用本文提出的低秩约束全局模糊隶属度矩阵U$U$; 其次, 计算损失函数时考虑视角权重wk$w_k$, 并加入视角权重系数的香农熵正则项. 设U=[U1⋯UK]T$U=[U_1\cdots U_K{]}^{\mathrm{T}}$; ww=[w1,⋯,wk,⋯,wK]$ww=[w_1,\cdots ,w_k,\cdots ,w_K]$表示K$K$个视角下的视角权重. 本文所构建LR-MVEWFCM的目标函数为

其中, 约束条件为

本文取模糊指数m=2$m=2$.

2.1   基于ADMM的求解算法

在本节中, 我们将使用ADMM方法, 通过交替方向迭代的策略来实现目标函数(11)$\left(11\right)$的最小化.

最小化式(10)$\left(10\right)$可改写为如下约束优化问题:

其求解过程可分解为如下几个子问题:

1) V$V$-子问题. 固定w$\mathit{w}$和U$U$, 更新V$V$为

通过最小化式(15)$\left(15\right)$, 可得到v(t+1)i,k${\mathit{v}}_{i,k}^{\left(t+1\right)}$的闭合解为

2) U$U$-子问题. 固定w$\mathit{w}$, Q$Q$和Z$Z$, 更新U$U$为

通过最小化式(17)$\left(17\right)$, 可得到U(t+1)$U^{\left(t+1\right)}$的封闭解为

3) w$w$-子问题. 固定V$V$和U$U$, 更新w$\mathit{w}$为

4) Z$Z$-子问题. 固定Q$Q$和U$U$, 更新Z$Z$为

通过引入软阈值算子, 可得式(20)$\left(20\right)$的解为

其中, U(t+1)+Q(t)=AΣBT$U^{\left(t+1\right)}+Q^{\left(t\right)}=A{\mathrm{\Sigma }B}^{\mathrm{T}}$为矩阵U(t+1)+Q(t)$U^{(t+1)}+Q^{(t)}$的奇异值分解, 核范数的近邻算子可由软阈值算子Sθ/ρ(Σ)=diag({max(0,σi−θ/ρ)})(i=1,2,⋯,N)$S_{\theta /\rho }(\mathrm{\Sigma })=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(\{max(0,{\sigma }_i-\theta /\rho )\})(i=1,2,\cdots ,N)$给出.

5) Q$Q$-子问题. 固定Z$Z$和U$U$, 更新Q$Q$为

经过上述迭代过程, 目标函数收敛于局部极值, 同时得到不同视角下的模糊隶属度矩阵. 本文借鉴文献[10]的集成策略, 使用视角权重系数 w=$\mathit{w}=$[w1,⋯,wk,⋯,wK]$[w_1,\cdots ,w_k,\cdots ,w_K]$和模糊隶属度矩阵U$U$来构建具有全局特性的模糊空间划分矩阵U~$\tilde{U}$:

其中, wk$w_k$, Uk$U_k$分别表示第k$k$个视角的视角权重系数和相应的模糊隶属度矩阵.

LR-MVEWFCM算法描述如下:

输入. 包含K (1≤k≤K)$K\left(1\le k\le K\right)$个视角的多视角样本集, 其中任意一个视角对应样本集Xk={x1,k,⋯,xN,k}$X_k=\{{\mathit{x}}_{1,k},\cdots ,{\mathit{x}}_{N,k}\}$, 聚类中心C$C$, 迭代阈值ϵ$ϵ$, 最大迭代次数T$T$;