-
摘要:
现有多视角聚类算法存在:1)在学习低维表征的过程中无法准确捕获或忽略嵌入在多视角数据中的高阶信息和互补信息;2)未能准确捕获数据局部信息;3)信息捕获方法缺少对噪声点鲁棒性等问题. 为解决上述问题,提出一种自适应张量奇异值收缩的多视角聚类(multi-view clustering based on adaptive tensor singular value shrinkage,ATSVS)算法. ATSVS首先提出一种符合秩特性的张量对数行列式函数对表示张量施加低秩约束,在张量奇异值分解(tensor singular value decomposition, t-SVD)过程中能够根据奇异值自身大小进行自适应收缩,更加准确地进行张量秩估计,进而从全局角度精准捕获多视角数据的高阶信息和互补信息. 然后采用一种结合稀疏表示和流形正则技术优势的l1,2范数捕获数据的局部信息,并结合l2,1范数对噪声施加稀疏约束,提升算法对噪声点的鲁棒性. 与11个对比算法在9个数据集上的实验结果显示,ATSVS的聚类性能均优于其他对比算法. 因此,ATSVS是一个能够有效处理多视角数据聚类任务的优秀算法.
Abstract:The existing multi-view clustering algorithms exhibit limitations in accurately capturing the high-order information and complementary information embedded in multi-view data during the low-dimensional representations learning process. Meanwhile, these algorithms fail to capture the local information of data, and their information extraction methods lack robustness to noise and outliers. To address these challenges, an adaptive tensor singular value shrinkage multi-view clustering algorithm named ATSVS is proposed. ATSVS proposes a novel tensor log-determinant function to enforce the low-rank constraint on the representation tensor, which can adaptively enable adaptive shrinkage of singular values based on their magnitude. Consequently, ATSVS effectively captures high-order information and complementary information within multi-view data from the global perspective. Then, ATSVS captures the local information of the data by using the l1,2 norm that combines the advantages of sparse representation and manifold regularization technology, while improving the robustness of the algorithm to noisy points by combining with l2,1 norms to impose sparse constraints on the noise. The experimental results with eleven comparison algorithms on nine different types of datasets show that our proposed algorithm ATSVS has the superior clustering performance, outperforming state-of-the-art baselines significantly. Consequently, ATSVS is an excellent algorithm that can effectively handle the task of clustering multi-view data.
-
聚类作为一种典型的无监督机器学习方法,能够在没有任何先验信息的情况下发现数据内部潜在的分区结构[1]. 目前,聚类已经在隐私保护[2]、机械故障诊断[3]、图像分割[4]和大气污染防治[5]等领域发挥着重要作用. 随着数据获取技术的发展,在现实世界中对某一对象的描述呈现出多视角的特点,各个视角的描述数据组合在一起被统称为多视角数据. 由于传统的单视角聚类算法缺少视角关系发现机制,无法处理面向多视角数据的聚类任务,因此多视角聚类算法受到众多研究人员的关注[6].
在多视角数据中,不同视角的数据包含了对象的类别一致性信息和互补信息. 近年来,研究人员通过融合各视角的类别一致性信息提出了很多优秀的多视角聚类算法[7-11]. Gao等人[8]提出一种多视角子空间聚类方法,该方法对每个视角数据的自表示矩阵分别进行谱聚类,学习到由所有视角共享的一致性低维表征. Zhang等人[9]通过挖掘多视角数据的潜在表示信息进行数据重构,得到更加准确全面的潜在子空间表示信息,提高了聚类的准确性和稳定性. Zhou等人[10]提出一种多级一致性协作策略,利用语义空间的一致性信息作为自监督信号与特征空间中的簇分配进行协作,使得不同层次的空间在实现各自的一致性目标的同时相互协作,充分挖掘不同视图的一致信息. Nie等人[11]提出一种快速多视角双边k-Means聚类方法,通过引入自适应重加权策略,有效地控制每个视角的权重,更合理地利用不同视角信息进行聚类. 一致性信息作为多视角数据中的重要鉴别性信息,对聚类效果具有较大的影响. 上述算法通过捕获一致性信息能够取得较好的聚类结果,但仍然存在相应的缺点,它们忽视了视角间存在的高阶信息和互补信息,而这些信息对于聚类效果同样具有较大的影响.
为了充分挖掘数据蕴含的丰富信息进行聚类,研究人员提出将数据空间从2维扩展到3维,采用三阶张量结构探索嵌入在视角间的高阶相关性,捕获数据间的高阶信息和互补信息. Zhang等人[12]将低秩张量约束引入到子空间聚类中,利用各视角的自表示矩阵构建三阶张量,通过最小化张量核范数捕获多视角数据间的高阶信息. 然而,该方法采用Tucker秩松散近似张量核范数的值,导致最终的模型不存在全局最优解. 为解决此问题,Xie等人[13]提出一种基于张量奇异值分解(tensor singular value decomposition,t-SVD)的多视角子空间聚类算法,采用基于t-SVD的张量核范数对三阶张量进行低秩约束,同时该方法引入了张量旋转操作,使得视角内和视角间都满足低秩性,降低了计算复杂度. 然而,基于t-SVD的张量核范数在计算过程中将所有的奇异值简单相加作为函数结果值,而矩阵的秩等于矩阵非零奇异值的个数,因此这种张量低秩约束方法会导致函数值被较大奇异值所主导,最终偏离了秩的真实值. 为解决此问题,文献[14-15]提出奇异值人工加权策略协调每个非零奇异值对秩函数的贡献比重,使得最终每个奇异值尽可能具有相同的贡献值. 这种策略有效平衡了所有非零奇异值对函数值的贡献比重,能有效提升算法的聚类性能. 但在实际应用中,由于数据分布的复杂性和未知性,很难为每个数据集通过人工选择合适的加权向量.
低秩表示方法通过求取所有数据的表示系数,能够有效捕获数据的全局信息,但它忽略了数据的局部距离关系,未能捕获数据的局部信息. 稀疏约束和流形正则技术作为2种常用的捕获数据局部信息的方法,在捕获数据局部信息方面具有一定的效果,目前已经被研究人员广泛应用到多视角聚类领域中[16-18]. 然而,这2种技术也存在一定缺陷,使得捕获的局部信息不足以准确反映数据内部的真实结构. 稀疏约束在稀疏不同簇数据之间联系的同时也稀疏了部分同一簇内数据点间的紧密性,而流形正则技术简单通过数据点间的距离信息捕获局部信息,缺少了对噪声点的鲁棒性.
为解决上述多视角聚类算法所存在的问题,本文提出一种自适应张量奇异值收缩的多视角聚类(multi-view clustering based on adaptive tensor singular value shrinkage,ATSVS)算法. ATSVS能充分利用多视角数据所包含的信息进行聚类,算法总体框架如图1所示. 为捕获各个视角间的互补信息和高阶信息,ATSVS将所有视角的表示矩阵拼接成一个三阶表示张量,然后将2维空间中的一种更符合矩阵秩特性的对数行列式数函数扩展到3维空间,构造张量对数行列式函数对表示张量施加低秩约束. 其次,为捕获各个视角内部的局部信息,ATSVS对各个视角的表示矩阵施加l1, 2范数约束,将稀疏技术和流形正则技术相结合,揭示各视角数据的特异性分布. 接着,为抑制噪声数据带来的不利影响,ATSVS利用l1, 2范数引入稀疏误差项,限制噪声点的表示过程. 最后,提出一种基于ADMM的优化方法对模型求解,通过一定次数的迭代更新学习到一个包含大量鉴别性信息的亲和矩阵,在此亲和矩阵上执行谱聚类算法得到最终的聚类结果.
本文主要有4个方面的贡献:
1)采用张量对数行列式函数进行低秩约束,能够在t-SVD的过程中根据张量奇异值自身的大小自适应地收缩,使得所有奇异值对秩估计尽可能地具有相同的贡献,从而准确捕获嵌入在多视角数据中的高阶信息和互补信息.
2)采用一种结合稀疏表示和流形正则技术优势的l1,2范数对各视角表示矩阵进行约束,先利用数据稀疏化降低噪声的影响,然后再根据稀疏后的数据之间的距离捕获数据中隐藏的局部信息.
3)对噪声采用l2,1稀疏约束,结合l1,2范数进一步抑制噪声在数据表示过程中带来的不利影响,增强算法对噪声点的鲁棒性.
4)在9个数据集上的丰富实验证明,ATSVS相较于其他单视角和多视角聚类算法,具有更加优秀的聚类性能.
1. 相关理论
为了更方便地介绍后面的内容,本文在表1中对文中的符号进行了说明.
表 1 符号与含义Table 1. Notations and Meaning符号 含义 符号 含义 {\boldsymbol{x}},{\text{ }}{\boldsymbol{X}},{\text{ }} {\overset{\frown}{{\boldsymbol{X}}}} 向量,矩阵,张量 {\overset{\frown}{{\boldsymbol{Z}}}}(i,:,:) {\overset{\frown}{{\boldsymbol{Z}}}}的第i个水平切面 {\boldsymbol{I}} 单位矩阵 {\overset{\frown}{{\boldsymbol{Z}}}}(:,j,:) {\overset{\frown}{{\boldsymbol{Z}}}}的第j个侧切面 n 数据个数 {\overset{\frown}{{\boldsymbol{Z}}}}(:,:,k);{{\overset{\frown}{{\boldsymbol{Z}}}}^{(k)}} {\overset{\frown}{{\boldsymbol{Z}}}}的第k个正切面 v 第v个视角 {\left\| {\boldsymbol{Z}} \right\|_*} 矩阵{\boldsymbol{Z}}的核范数 V 视角个数 {\left\| {\boldsymbol{Z}} \right\|_{\text{F}}} 矩阵{\boldsymbol{Z}}的Frobenius
范数{d_v} 第v个视角的特征维度 {\left\| {\boldsymbol{Z}} \right\|_\infty } 矩阵{\boldsymbol{Z}}的无穷范数 {{\boldsymbol{X}}^{(v)}} \in {\mathbb{R}^{d \times N}} 第v个视角的特征矩阵 {\left\| {\boldsymbol{Z}} \right\|_{2,1}} 矩阵{\boldsymbol{Z}}的{l_{2,1}}范数 {\overset{\frown}{{\boldsymbol{Z}}}} \in {\mathbb{R}^{n \times V \times n}} 表示张量 {\left\| {\boldsymbol{Z}} \right\|_{1,2}} 矩阵{\boldsymbol{Z}}的{l_{1,2}}范数 {\mathop {\boldsymbol Z} \limits^ \smile}\in {\mathbb{R}^{n \times n \times V}} 表示张量旋转体 {\left\| {{\overset{\frown}{{\boldsymbol{Z}}}}} \right\|_ \circledast } 张量核范数 {\boldsymbol{A}} \in {\mathbb{R}^{n \times n}} 亲和矩阵 {{\overline{\boldsymbol{X}}}} = fft( {\overset{\frown}{\boldsymbol{X}}} ,[],3) {\overset{\frown}{\boldsymbol{X}}} 沿第3维度的
傅里叶变换{{\boldsymbol{E}}^{(v)}} \in {\mathbb{R}^{n \times n}} 噪声矩阵 {\overset{\frown}{{\boldsymbol{X}}}} = ifft({{\overline {\boldsymbol{X}}}},[],3) {{\overline {\boldsymbol{X}}}}沿第3维度的
傅里叶逆变换1.1 张量相关理论
由于本文提出的算法是基于张量表示的多视角聚类算法,为方便公式推导,本节对张量相关理论进行简要介绍[19-20].
定义1. 对于三阶张量{\overset{\frown}{{\boldsymbol{X}}}} \in {\mathbb{R}^{{n_1} \times {n_2} \times {n_3}}},其展开操作{upfold}({\overset{\frown}{{\boldsymbol{X}}}}{\text{)}}和折叠操作{fold}({\overset{\frown}{{\boldsymbol{X}}}} {\text{)}}被定义为
{upfold}{\text{(}} {\overset{\frown}{{\boldsymbol{X}}}} {\text{) = }}\left( {\begin{array}{*{20}{c}} {{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{(1)}}} \\ {{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{(2)}}} \\ \vdots \\ {{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{({{n}_{\text{3}}})}}} \end{array}} \right), (1) fold({upfold}( {\overset{\frown}{{\boldsymbol{X}}}} )) = {\overset{\frown}{{\boldsymbol{X}}}} . (2) 定义2. 对于三阶张量 {\overset{\frown}{{\boldsymbol{X}}}}\in {\mathbb{R}^{{n_1} \times {n_2} \times {n_3}}},其块向量化{bvec}{\text{(}} {\overset{\frown}{{\boldsymbol{X}}}} {\text{)}}被定义为
{bvec}{\text{(}} {\overset{\frown}{{\boldsymbol{X}}}} ) = ({ {\overset{\frown}{{\boldsymbol{X}}}} ^{(1)}}{\text{; }}{ {\overset{\frown}{{\boldsymbol{X}}}} ^{(2)}}{\text{; }} … {\text{; }}{ {\overset{\frown}{{\boldsymbol{X}}}} ^{({{n}_3})}})^{\text{T}}. (3) 定义3. 对于三阶张量{\overset{\frown}{{\boldsymbol{X}}}}\in {\mathbb{R}^{{n_1} \times {n_2} \times {n_3}}} ,其块循环矩阵{bcirc}{\text{(}} {\overset{\frown}{{\boldsymbol{X}}}} {\text{)}}被定义为
{bcirc}{\text{(}} {\overset{\frown}{{\boldsymbol{X}}}} ) = \left( {\begin{array}{*{20}{c}} {{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{(1)}}}&{{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{({{n}_3})}}}& … &{{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{(2)}}} \\ {{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{(2)}}}&{{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{(1)}}}& … &{{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{(3)}}} \\ \vdots & \vdots &{}& \vdots \\ {{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{({{n}_3})}}}&{{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{({{n}_3} - 1)}}}& … &{{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{(1)}}} \end{array}} \right). (4) 定义4. 对于三阶张量 {\overset{\frown}{{\boldsymbol{X}}}} \in {\mathbb{R}^{{n_1} \times {n_2} \times {n_3}}},其块对角矩阵{{bdiag(}} {\overset{\frown}{{\boldsymbol{X}}}} {\text{)}}被定义为
{{bdiag(}} {\overset{\frown}{{\boldsymbol{X}}}} {\text{) = }}\left( {\begin{array}{*{20}{c}} {{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{(1)}}}&{}&{}&{} \\ {}&{{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{(2)}}}&{}&{} \\ {}&{}& \ddots &{} \\ {}&{}&{}&{{{ {\overset{\frown}{{\boldsymbol{X}}}} }^{({{n}_3})}}} \end{array}} \right). (5) 定义5. 对于2个三阶张量 {\overset{\frown}{{\boldsymbol{X}}}} \in {\mathbb{R}^{{n_1} \times {n_2} \times {n_3}}}和 {\overset{\frown}{{\boldsymbol{Y}}}}\in {\mathbb{R}^{{n_2} \times {n_4} \times {n_3}}} ,若* 表示t-product运算,则 {\overset{\frown}{{\boldsymbol{X}}}}* {\overset{\frown}{{\boldsymbol{Y}}}}定义为
{\overset{\frown}{{\boldsymbol{M}}}}= {\overset{\frown}{{\boldsymbol{X}}}}* {\overset{\frown}{{\boldsymbol{Y}}}}=fold\{bcirc({ {\overset{\frown}{{\boldsymbol{X}}}}})bvec({ {\overset{\frown}{{\boldsymbol{Y}}}}})\}, (6) 其中 {\overset{\frown}{{\boldsymbol{M}}}} 是维度为{n_1} \times {n_4} \times {n_3}的三阶张量.
定义6. 对于三阶张量 {\overset{\frown}{{\boldsymbol{X}}}} \in {\mathbb{R}^{{n_1} \times {n_2} \times {n_3}}},其对应的t-SVD分解为 {\overset{\frown}{{\boldsymbol{X}}}} {\text{ = }} {\overset{\frown}{{\boldsymbol{U}}}}* {\overset{\frown}{{\boldsymbol{S}}}}*{ {\overset{\frown}{{\boldsymbol{V}}}}^{\text{T}}},其中 {\overset{\frown}{{\boldsymbol{U}}}} \in {\mathbb{R}^{{n_1} \times {n_1} \times {n_3}}}和 {\overset{\frown}{{\boldsymbol{V}}}} \in {\mathbb{R}^{{n_2} \times {n_2} \times {n_3}}}为正交张量, {\overset{\frown}{{\boldsymbol{S}}}} \in {\mathbb{R}^{{n_1} \times {n_2} \times {n_3}}} 是f-对角张量.
定义7. 对于三阶张量 {\overset{\frown}{{\boldsymbol{X}}}} \in {\mathbb{R}^{{n_1} \times {n_2} \times {n_3}}},其基于张量奇异值分解的张量核范数(t-SVD-TNN)定义为
{\left\| { {\overset{\frown}{{\boldsymbol{X}}}} } \right\|_ \circledast }{\text{ = }}\sum\limits_{j = 1}^{{n_3}} {{{\left\| {{{\overline{\boldsymbol{ X}}}}\left( {:,{\text{ :, }}j} \right)} \right\|}_*}} {\text{ = }}\sum\limits_{i = 1}^{\min ({{n}_1},{{n}_2})} {\sum\limits_{j = 1}^{{n_3}} {\left| {{{\overline{\boldsymbol{ S}}}}\left( {i,i,j} \right)} \right|} } , (7) 其中 {{\overline{\boldsymbol{ X}}}} 为 {\overset{\frown}{{\boldsymbol{X}}}} 沿第3维度的傅里叶变换,{{\overline{\boldsymbol{ S}}}}为{{\overline{\boldsymbol{ X}}}}的所有正切片进行奇异值分解得到,即{{\overline{\boldsymbol{ X}}}}{\text{ = }}{{\overline{\boldsymbol{ U}}}}*{{\overline{\boldsymbol{ S}}}}*{{{\overline{\boldsymbol{ V}}}}^{\text{T}}}.
1.2 基于t-SVD的多视角聚类
t-SVD作为一种紧凑的张量分解方法,在多视角聚类领域中被广泛用于挖掘视角间的高阶相关性和互补性信息. 研究人员提出一种基于t-SVD的张量核范数,并使用其对表示张量施加低秩约束,充分挖掘数据信息进行聚类,其模型为:
\begin{array}{l} \mathop{\min\limits_{{\mathop {\boldsymbol Z} \limits^ \smile}, {\boldsymbol{E}}}}\left\|{\mathop {\boldsymbol Z} \limits^ \smile}\right\|_{ \circledast}+\lambda\left\|\boldsymbol{E}\right\|_{2,1},\quad\quad\quad\quad\quad\quad\quad\quad \end{array} (8) \begin{split} &\text{s}\text{.t}\text{. }{{\boldsymbol{X}}}^{({v})} ={{\boldsymbol{X}}}^{({v})}{{\boldsymbol{Z}}}^{({v})}+{{\boldsymbol{E}}}^{({v})},v=1,\text{ }2,\text{ }…\text{, }V,\\ &\quad\;\;{\overset{\frown}{\boldsymbol{Z}}} = {\varPhi}{(}{{\boldsymbol{Z}}}^{(1)},\text{ }{{\boldsymbol{Z}}}^{(2)},\text{ }…\text{, }{{\boldsymbol{Z}}}^{(V)}{),}\\ &\quad\;\;{\boldsymbol{E}}{= (}{{\boldsymbol{E}}}^{(1)}\text{; }{{\boldsymbol{E}}}^{(2)}\text{; }…;\text{ }{{\boldsymbol{E}}}^{(V)}). \end{split} 其中{\varPhi }( \cdot )表示将所有视角的表示矩阵拼接成三阶张量 {\overset{\frown}{{\boldsymbol{Z}}}} \in {\mathbb{R}^{n \times n \times V}} ,经旋转后得到{\mathop {\boldsymbol Z} \limits^ \smile}\in {\mathbb{R}^{n \times V \times n}} . 由于不同视角的数据特征维度可能不一致,所以将每个视角的误差矩阵垂直连接以构造总的误差矩阵{\boldsymbol{E}}. 通过对张量{\mathop {\boldsymbol Z} \limits^ \smile}进行t-SVD,并将得到的f-对角张量 {\mathop {\boldsymbol S} \limits^ \smile} \in {\mathbb{R}^{n \times n \times V}} 进行收缩,最后进行t-SVD逆操作重构表示张量,进而捕获隐藏在多个视角间的高阶信息. 由于收缩f-对角张量的过程完全依赖张量奇异值的大小,而张量的秩等于非零奇异值的个数,因此式(8)未能对表示张量进行准确秩估计,从而不能准确捕获视角间的高阶信息.
奇异值加权策略在收缩f-对角张量的过程中能够有效平衡所有非零奇异值对秩估计的贡献,提升张量秩估计的准确性. 对于三阶张量 {\overset{\frown}{{\boldsymbol{X}}}} \in {\mathbb{R}^{{n_1} \times {n_2} \times {n_3}}} ,其加权张量核范数定义为
{\left\| { {\overset{\frown}{{\boldsymbol{X}}}} } \right\|_{\omega , \circledast }}{\text{ = }}\sum\limits_{i = 1}^{{n_3}} {\sum\limits_{j = 1}^{\min ({{n}_1},{{n}_2})} {{\omega _j}{{\overline{\boldsymbol{ S}}}}\left( {j,{\text{ }}j,{\text{ }}i} \right)} } , (9) 其中{\omega _j}表示张量{{\overline{\boldsymbol{ S}}}}的第i个正切片的第j个奇异值对应的权重. 研究人员通过加权张量核范数进一步提出了基于加权张量t-SVD的多视角子空间聚类算法,其模型为:
\begin{array}{l}\mathop{\min\limits_{{\mathop {\boldsymbol Z} \limits^ \smile}, {\boldsymbol{E}}}}\left\|{\mathop {\boldsymbol Z} \limits^ \smile}\right\|_{\omega, \circledast}+\lambda\left\|\boldsymbol{E}\right\|_{2,1},\quad\quad\quad\quad\quad\quad \end{array} (10) \begin{split} &\text{s}\text{.t}\text{. }{{\boldsymbol{X}}}^{({v})}\text{ = }{{\boldsymbol{X}}}^{({v})}{{\boldsymbol{Z}}}^{({v})}+{{\boldsymbol{E}}}^{({v})},v=1,\text{ }2,\text{ }…\text{, }V,\\ &\quad\;\;{\overset{\frown}{\boldsymbol{Z}}}\text{ = }{\varPhi}\text{(}{{\boldsymbol{Z}}}^{(1)},\text{ }{{\boldsymbol{Z}}}^{(2)},\text{ }…\text{, }{{\boldsymbol{Z}}}^{(V)}\text{),}\\ &\quad\;\;{\boldsymbol{E}}= ({{\boldsymbol{E}}}^{(1)}\text{; }{{\boldsymbol{E}}}^{(2)}\text{; }…;\text{ }{{\boldsymbol{E}}}^{(V)}). \end{split} 这种为奇异值加权的方法可以使得所有的非零奇异值在加权后能够对秩估计具有相同的贡献,能够更加准确地对张量进行秩估计,但在实际应用过程中,由于不同视角数据之间可能存在较大差异,很难为奇异值选择合适的权重.
1.3 局部信息捕获
局部信息对反映数据内部真实分布特征具有重要作用,准确捕获数据局部信息对取得较好的聚类效果至关重要. 常见的捕获数据局部信息的方法为稀疏约束和流形正则约束,目前已被广泛应用到多视角聚类算法中. Brbić等人[16]将稀疏和低秩融合到一个多视角聚类模型中,通过低秩约束捕获数据的全局信息,利用{l_1}范数对表示矩阵施加稀疏约束捕获数据的局部信息. 其模型为:
\begin{split} &{\mathop {\min }\limits_{{{\boldsymbol{C}}^{(v)}}} {\beta _1}{{\left\| {{{\boldsymbol{C}}^{({v})}}} \right\|}_*} + {\beta _2}{{\left\| {{{\boldsymbol{C}}^{({v})}}} \right\|}_1} + {\lambda ^{({v})}}\sum\limits_{1 \leqslant w \leqslant {n_v},v \ne w} {\left\| {{{\boldsymbol{C}}^{({v})}} - {{\boldsymbol{C}}^{({w})}}} \right\|_{\text{F}}^2} }, \\ &\qquad {{\text{s}}{\text{.t}}{\text{. }}{{\boldsymbol{X}}^{({v})}}{\mathbf{ = }}{{\boldsymbol{X}}^{(v)}}{{\boldsymbol{C}}^{{{(v)}}}},{\text{ diag(}}{{\boldsymbol{C}}^{({v})}}) = 0}, \\[-1pt] \end{split} (11) 其中{{\boldsymbol{C}}^{{\text{(}}{v}{\text{)}}}}为该算法中第v个视角数据对应的表示矩阵. 该模型方法基于数据的线性表示理论,利用矩阵{l_1}范数最小化所带来的数据稀疏性对表示矩阵施加稀疏约束,使得每个数据由其近邻数据所表示,从而捕获数据的局部信息.
Fu等人[17]提出一种低秩张量近似的局部结构多视角内在子空间聚类方法,通过引入流形正则项捕获每个视角数据的局部结构. 其完整模型为:
\begin{split} &\mathop {\min }\limits_{{\boldsymbol{A}},{{\boldsymbol{Z}}^{(v)}},{\boldsymbol{E}},{\boldsymbol{F}}} {\left\| {{\mathop {\boldsymbol A} \limits^ \smile}} \right\|_*} + \lambda {\left\| {\boldsymbol{E}} \right\|_{2,1}} + \beta \sum\limits_{v = 1}^m {{\text{tr}}({{\boldsymbol{S}}^{(v)}}{{\boldsymbol{L}}^{(v)}}{{\boldsymbol{S}}^{(v)}}^{\text{T}})} + \\ & \alpha \sum\limits_{v = 1}^m {{\text{tr}}({{\boldsymbol{F}}^{\text{T}}}{\boldsymbol{L}}_{{{\boldsymbol{S}}^{(v)}}}^{(v)}{\boldsymbol{F}})} , \end{split} (12) \begin{split} &{\text{ s}}{\text{.t}}{\text{. }}{{\boldsymbol{X}}^{(v)}} = {{\boldsymbol{X}}^{(v)}}{{\boldsymbol{Z}}^{(v)}} + {{\boldsymbol{E}}^{(v)}},{\text{ }}{{\boldsymbol{Z}}^{(v)}} = {{\boldsymbol{P}}^{(v)}}{{\boldsymbol{S}}^{(v)}},\quad\quad\quad\quad \\ &{{\boldsymbol{P}}^{(v)}}^{\text{T}}{{\boldsymbol{P}}^{(v)}} = {\boldsymbol{I}},{{\boldsymbol{F}}^{\text{T}}}{\boldsymbol{F}} = {\boldsymbol{I}}, \\ & {\overset{\frown}{{\boldsymbol{A}}}} = {\varPhi }({{\boldsymbol{S}}^{(1)}},{{\boldsymbol{S}}^{(2)}}, … ,{{\boldsymbol{S}}^{(m)}}), \\ &{\boldsymbol{E}} = ({{\boldsymbol{E}}^{(1)}},{{\boldsymbol{E}}^{(2)}}, … ,{{\boldsymbol{E}}^{(m)}}), \end{split} 其中 \displaystyle\sum\limits_{v = 1}^m {{\text{tr}}({{\boldsymbol{S}}^{(v)}}{{\boldsymbol{L}}^{(v)}}{{\boldsymbol{S}}^{(v)}}^{\text{T}})} 为该模型的流形正则项,使数据点能够映射到各个视角内部的子空间中,从而捕获数据的局部信息.
Zhao等人[18]探索了适用于多视角图聚类的隐含自适应流形,将多个自适应图无缝集成到一个共识图中,最后通过共识图直接获得聚类结果. 其模型如式(13)所示:
\begin{split} &\mathop {\min }\limits_{{{\boldsymbol{Z}}^{(v)}},{\boldsymbol{S}},{\boldsymbol{F}}} \sum\limits_{v = 1}^m {\sum\limits_{i,j = 1}^n {\left( {\left\| {{\boldsymbol{x}}_i^{(v)} - {\boldsymbol{x}}_j^{(v)}} \right\|_2^2{\textit{z}}_{ij}^{(v)} + \alpha {{\left( {{\textit{z}}_{ij}^{(v)}} \right)}^2}} \right)} }+ \\ & \frac{1}{2}\sum\limits_{v = 1}^m {{\mu ^{(v)}}\sum\limits_{i,j,k = 1}^n {{\textit{z}}_{ij}^{(v)}{{\left( {\frac{{{s_{ki}}}}{{\sqrt {d_{ii}^{(v)}} }} - \frac{{{s_{kj}}}}{{\sqrt {d_{jj}^{(v)}} }}} \right)}^2}} } + \\ &\beta \left\| {{\boldsymbol{S}} - {\boldsymbol{I}}} \right\|_{\text{F}}^2 + 2\gamma {\text{tr}}({{\boldsymbol{F}}^{\text{T}}}{{\boldsymbol{L}}_{\boldsymbol{S}}}{\boldsymbol{F}}) , \end{split} (13) \begin{split} & {\text{ s}}{\text{.t}}{\text{. }}{\left( {{\boldsymbol{z}}_i^{(v)}} \right)^{\text{T}}}{\mathbf{1}} = 1,{\textit{z}}_{ij}^{(v)} \geqslant 0,{\boldsymbol{S}}_i^{\text{T}}{\mathbf{1}} = 1,\quad\quad\quad\quad\quad\quad \\ &{s_{ij}} \geqslant 0,{\boldsymbol{F}} \in {\mathbb{R}^{n \times c}},{{\boldsymbol{F}}^{\text{T}}}{\boldsymbol{F}} = {\boldsymbol{I}}. \end{split} 其中 \left\| {{\boldsymbol{x}}_i^{(v)} - {\boldsymbol{x}}_j^{(v)}} \right\|_2^2{\textit{z}}_{ij}^{(v)} 为模型中的流形正则项,通过数据点 {\boldsymbol{x}}_i^{(v)} 和数据点 {\boldsymbol{x}}_j^{(v)} 之间的欧氏距离,动态调整2个数据点间的表示系数,距离越小,表示系数越大且距离越大,表示系数越小,使得该模型能够根据数据点间的距离关系捕获数据点间的局部信息.
1.4 2维空间中的平滑低秩表示
对数行列式函数作为一种相较于核范数更符合矩阵秩特性的秩估计方法,能够获得比核范数更加准确的秩估计[21-22]. 对数行列式函数能够根据所有非零奇异值自身的大小进行自适应收缩,减小奇异值之间的大小差距,使得最终所有奇异值对秩估计尽可能具有相同的贡献. 其中,对数行列式的定义为
LogDet\left( {{\boldsymbol{I}} + {{\boldsymbol{Z}}^{\text{T}}}{\boldsymbol{Z}}} \right){\text{ = }}\sum\limits_{i = 1}^n {{{\mathrm{\rm lb}}} \left( {1 + \sigma _i^2\left( {\boldsymbol{Z}} \right)} \right)} , (14) 其中LogDet\left( \cdot \right)为对数行列式函数,{{\mathrm{\rm lb}}} ( \cdot )表示底数为2的对数函数,{\sigma _i}({\boldsymbol{Z}})表示矩阵Z的第i个奇异值.
定理1[21]. 对一任意矩阵{\boldsymbol{X}} \in {\mathbb{R}^{d \times c}},若其奇异值分解(singular value decomposition,SVD)为 {\boldsymbol{X}} = {\boldsymbol{P\varSigma }}{{\boldsymbol{Q}}^{\text{T}}} ,其中 {\boldsymbol{\varSigma }} = {\text{diag}}\left( {{\sigma _{1,{\boldsymbol{X}}}},{\sigma _{2,{\boldsymbol{X}}}}, … ,{\sigma _{r,{\boldsymbol{X}}}}} \right) ,r = \min (d,n),n为数据个数,则 \mathop {\min }\limits_{\boldsymbol{Y}} \dfrac{1}{\lambda }LogDet\left( {{\boldsymbol{I}} + {{\boldsymbol{Y}}^{\text{T}}}{\boldsymbol{Y}}} \right) + \dfrac{1}{2}\left\| {{\boldsymbol{Y}} - {\boldsymbol{X}}} \right\|_{\text{F}}^2 的解为 {\boldsymbol{Y}} = {\boldsymbol{P\varLambda }}{{\boldsymbol{Q}}^{\text{T}}} ,其中{\boldsymbol{\varLambda }} = {\text{diag}}(\sigma _1^*,\sigma _2^*, … ,\sigma _r^*),\sigma _i^*由式(15)求得:
\begin{split} &\frac{{2\sigma _i^*}}{{1 + \sigma {{_i^*}^{^2}}}} + \lambda (\sigma _i^* - {\sigma _{i,{\boldsymbol{X}}}}) = 0,\\ &{\text{ s}}{\text{.t}}. {\text{ }}\sigma _i^* \geqslant 0,{\text{ }}i = 1,2, … ,n.\end{split} (15) 证明. 设 F({\boldsymbol{Y}}) = LogDet({\boldsymbol{I}} + {{\boldsymbol{Y}}^{\text{T}}}{\boldsymbol{Y}}) ,{\boldsymbol{X}}的SVD为{\boldsymbol{X}} = {\boldsymbol{P}}{{\boldsymbol{\varSigma }}_{\boldsymbol{X}}}{{\boldsymbol{Q}}^{\text{T}}},则{{\boldsymbol{\varSigma }}_{\boldsymbol{X}}} = {{\boldsymbol{P}}^{\text{T}}}{\boldsymbol{XQ}};设{\boldsymbol{A}} = {{\boldsymbol{P}}^{\text{T}}}{\boldsymbol{YQ}},即{\boldsymbol{A}}和{\boldsymbol{Y}}具有相同的奇异值,则{{\boldsymbol{\varSigma }}_{\boldsymbol{A}}} = {{\boldsymbol{\varSigma }}_{\boldsymbol{Y}}}. 据此可以得到:
F({\boldsymbol{Y}}) + \frac{\lambda }{2}\left\| {{\boldsymbol{Y}} - {\boldsymbol{X}}} \right\|_{\text{F}}^2. (16) 由于Frobenius范数和F({\boldsymbol{Y}})为酉不变量,因此式(16)可以变为
F({{\boldsymbol{\varSigma }}_{\boldsymbol{A}}}) + \frac{\beta }{2}\left\| {{\boldsymbol{A}} - {{\boldsymbol{\varSigma }}_{\boldsymbol{X}}}} \right\|_{\text{F}}^2. (17) 根据冯·诺依曼不等式可对式(14)做如下变换:
F({{\boldsymbol{\varSigma }}_{\boldsymbol{A}}}) + \frac{\beta }{2}\left( {\left\| {\boldsymbol{A}} \right\|_{\text{F}}^2 + \left\| {{{\boldsymbol{\varSigma }}_{\boldsymbol{X}}}} \right\|_{\text{F}}^2 - 2\left\langle {{\boldsymbol{A}},{{\boldsymbol{\varSigma }}_{\boldsymbol{X}}}} \right\rangle } \right). (18) 式(18)通过Hoffman-Wielandt不等式可得:
\begin{split} &F({{\boldsymbol{\varSigma }}_{\boldsymbol{A}}}) + \frac{\beta }{2}\left( {\left\| {\boldsymbol{A}} \right\|_{\text{F}}^2 + \left\| {{{\boldsymbol{\varSigma }}_{\boldsymbol{X}}}} \right\|_{\text{F}}^{\text{2}} - 2\left\langle {{\boldsymbol{A}},{{\boldsymbol{\varSigma }}_{\boldsymbol{X}}}} \right\rangle } \right)\geqslant \\ & F({{\boldsymbol{\varSigma }}_{\boldsymbol{A}}}) + \frac{\beta }{2}\left( {\left\| {\boldsymbol{A}} \right\|_{\text{F}}^{\text{2}} + \left\| {{{\boldsymbol{\varSigma }}_{\boldsymbol{X}}}} \right\|_{\text{F}}^{\text{2}} - 2\left\langle {{{\boldsymbol{\varSigma }}_{\boldsymbol{A}}},{{\boldsymbol{\varSigma }}_{\boldsymbol{X}}}} \right\rangle } \right)= \\ & F({{\boldsymbol{\varSigma }}_{\boldsymbol{A}}}) + \frac{\beta }{2}\left\| {{{\boldsymbol{\varSigma }}_{\boldsymbol{A}}} - {{\boldsymbol{\varSigma }}_{\boldsymbol{X}}}} \right\|_{\text{F}}^{\text{2}}. \end{split} (19) 根据 {{\boldsymbol{\varSigma }}_{\boldsymbol{A}}} = {{\boldsymbol{\varSigma }}_{\boldsymbol{Y}}} ,式(19)可变为
\begin{split} & {\text{ }}F({{\boldsymbol{\varSigma }}_{\boldsymbol{Y}}}) + \frac{\beta }{2}\left\| {{{\boldsymbol{\varSigma }}_{\boldsymbol{Y}}} - {{\boldsymbol{\varSigma }}_{\boldsymbol{X}}}} \right\|_{\text{F}}^{\text{2}}= \\ & \sum\limits_{i=1}^n{\left[ {f({\sigma _i}) + \frac{\beta }{2}{{\left( {{\sigma _i} - {\sigma _{i,{\boldsymbol{X}}}}} \right)}^2}} \right]}\geqslant \\ & \sum\limits_{i=1}^n {\left[ {f(\sigma _i^*) + \frac{\beta }{2}{{\left( {\sigma _i^* - {\sigma _{i,{\boldsymbol{X}}}}} \right)}^2}} \right]} . \end{split} (20) 因此,式(20)为式(16)的下界,其中{{\boldsymbol{\varSigma }}_{\boldsymbol{Y}}}可通过最小化式(17)得到. 根据 {{\boldsymbol{\varSigma }}_{\boldsymbol{Y}}} = {{\boldsymbol{\varSigma }}_{\boldsymbol{A}}} = {\boldsymbol{A}} = {{\boldsymbol{P}}^{\text{T}}}{\boldsymbol{YQ}} ,可得{\boldsymbol{Y}} = {\boldsymbol{P}}{{\boldsymbol{\varSigma }}_{\boldsymbol{Y}}}{{\boldsymbol{Q}}^{\text{T}}},即得到 \mathop {\min }\limits_{\boldsymbol{Y}} \dfrac{1}{\lambda }LogDet\left( {{\boldsymbol{I}} + {{\boldsymbol{Y}}^{\text{T}}}{\boldsymbol{Y}}} \right) + \dfrac{1}{2}\left\| {{\boldsymbol{Y}} - {\boldsymbol{X}}} \right\|_{\text{F}}^{\text{2}} 的最优解. 证毕.
2. 张量平滑低秩表示和{l_{1,2}}范数正则的多视角聚类
2.1 张量平滑低秩
根据2维空间对数行列式的定义可知,对数行列式能够根据奇异值的大小进行自适应收缩. 当{\sigma _i} > 0时,存在不等关系{\rm lb} \left( {1 + \sigma _i^2\left( {\boldsymbol{Z}} \right)} \right) \leqslant {\sigma _i},将其推广至整个矩阵可得 LogDet\left( {{\boldsymbol{I}} + {{\boldsymbol{Z}}^{\text{T}}}{\boldsymbol{Z}}} \right){\text{ }} \leqslant {\left\| {\boldsymbol{Z}} \right\|_*} ,即对于同一矩阵{\boldsymbol{Z}},采用对数行列式函数对奇异值进行自适应收缩可取得比核范数更小的秩估计,更符合低秩约束目的. 对于一些较大的奇异值,存在不等式关系{\rm lb} \left( {1 + \sigma _i^2\left( {\boldsymbol{Z}} \right)} \right) << {\sigma _i},说明使用对数行列式函数可有效改善核范数的值被较大奇异值所主导的情况. 当奇异值大小相差过大时,经过对数行列式收缩后能缩小它们之间的差距,即缩小不同大小奇异值在秩估计时的贡献差距,进一步解决秩估计函数值被较大奇异值所主导的情况. 对数行列式函数使得所有奇异值对秩估计尽可能地具有相同的贡献,因此相较于核范数,对数行列式是一种更符合矩阵秩特性的平滑秩估计方法. 受此启发,本文将2维空间的对数行列式函数扩展到3维空间,构造张量对数行列式函数,对于三阶张量 {\overset{\frown}{{\boldsymbol{X}}}} \in {\mathbb{R}^{{n_1} \times {n_2} \times {n_3}}},其张量对数行列式函数的定义为:
\begin{split} &{\varPsi }\left( { {\overset{\frown}{{\boldsymbol{X}}}} } \right){\text{ = }}\frac{1}{{{n_3}}}\sum\limits_{j=1}^{{n_3}} {LogDet\left( {{\boldsymbol{I}} + {{\overline{\boldsymbol{ S}}}}{{\left( {:,{\text{ :}},{\text{ }}j} \right)}^{\text{T}}}{{\overline{\boldsymbol{ S}}}}\left( {:,{\text{ :}},{\text{ }}j} \right)} \right)} =\\ &\sum\limits_{j = 1}^{{n_3}} {\sum\limits_{i = 1}^{\min ({n_1},{n_2})} {\frac{1}{{{n_3}}}} {\rm lb} (1 + {{\overline{\boldsymbol{ S}}}}{{\left( {i,{\text{ }}i,{\text{ }}j} \right)}^2})}, \end{split} (21) 其中 {{\overline{\boldsymbol{ S}}}}\left( {:,{\text{ }}:,{\text{ }}j} \right) 表示张量 {\overset{\frown}{{\boldsymbol{X}}}} 沿第3维度的傅里叶变换再经张量奇异值分解后得到f-对角张量的第 j 个切片, {{\overline{\boldsymbol{ S}}}}\left( {i,{\text{ }}i,{\text{ }}j} \right) 表示第 j 个切片的第 i 个奇异值.
张量对数行列式函数依次计算每个切片 {{\overline{\boldsymbol{ S}}}}\left( {:,{\text{ }}:,{\text{ }}j} \right) 对应的对数行列式函数值,在每个切片上按照2维空间中的计算方式对奇异值进行自适应收缩,保留了对数行列式在2维空间进行秩估计的优势,当所有切片计算结束即可得到张量奇异值的收缩结果. 通过使用张量对数行列式函数进行低秩约束可缩小张量奇异值之间的大小差距,改善了张量核范数的大小被较大奇异值所主导的情况,不需要数据集的任何先验信息,使所有奇异值对张量秩估计尽可能具有相同的贡献,能够更加平滑地进行秩估计,增强了算法的灵活性.
2.2 算法模型框架
一个优秀的多视角聚类算法应充分利用数据所包含的信息进行聚类,包括各视角的全局信息和局部信息以及视角间的互补信息和高阶信息等. 本文将各视角数据的自表示矩阵构建成三阶张量,旋转之后采用张量对数行列式函数对其施加低秩约束,以此精准捕获嵌入在各视角间的高阶信息和互补信息. 但由于低秩约束方法是同时求取所有数据的表示系数,仅对表示张量旋转体施加低秩约束会忽略数据的局部信息.
{l_{1,2}}范数作为一种特征选择的常用方法[23-25],在刻画数据分布及捕获数据局部信息方面也有显著的作用. 本文为捕各视角数据的局部信息,对构建的表示张量 {\overset{\frown}{{\boldsymbol{Z}}}} \in {\mathbb{R}^{n \times n \times V}} 采用{l_{1,2}}范数进行正则化. 对于张量 {\overset{\frown}{{\boldsymbol{Z}}}} \in {\mathbb{R}^{n \times n \times V}} ,其{l_{1,2}}范数等价于在其所有正切片上分别施加{l_{1,2}}范数[26],即 \left\| {{\overset{\frown}{{\boldsymbol{Z}}}}} \right\|_{1,2}^2 = \displaystyle\sum\limits_{v = 1}^V {\left\| {{{\boldsymbol{Z}}^{(v)}}} \right\|_{_{1,2}}^2} = {\displaystyle\sum\limits_{i = 1}^n {\left( {\displaystyle\sum\limits_{j = 1}^n {(\left| {{{\textit{z}}_{ij}}} \right|)} } \right)} ^2} . 根据矩阵{l_{1,2}}范数的计算方式可知,{l_{1,2}}范数可视为稀疏技术和流形正则技术的结合体,其先对矩阵施加稀疏约束,然后对稀疏约束后的矩阵进行流形正则化得到最终结果. 对表示矩阵施加稀疏约束可以减少不同簇数据点之间的联系,然后采用基于距离信息的流形正则技术增强簇内数据间的紧密性. 通过{l_{1,2}}范数正则化可以很好地描述簇结构分布,增加簇间差异性和簇内紧密性.
在实际应用过程中,各个视角的数据通常会混入噪声数据,这将影响到数据自表示的准确性,最终影响算法的聚类性能. 为抑制噪声数据所产生的不利影响并提升算法的鲁棒性,本文对各视角的噪声数据利用{l_{2,1}}范数进行稀疏约束. 综上所述,可得本文提出的最终模型为
\begin{split} &\mathop {\min }\limits_{{{\boldsymbol{Z}}^{(v)}}} {\text{ }}{\psi }\left( {{\mathop {\boldsymbol Z} \limits^ \smile}} \right) + \lambda {\left\| {\boldsymbol{E}} \right\|_{2,1}} + \beta {\left\| {{\overset{\frown}{{\boldsymbol{Z}}}}} \right\|_{1,2}},\quad\quad\quad\quad \end{split} (22) \begin{split} &{\text{s}}{\text{.t}}{\text{. }}{{\boldsymbol{X}}^{(v)}} = {{\boldsymbol{X}}^{(v)}}{{\boldsymbol{Z}}^{(v)}} + {{\boldsymbol{E}}^{(v)}}{\text{ , }}v = 1,{\text{ }}2,{\text{ }} … ,{\text{ }}V, \\ &{\overset{\frown}{{\boldsymbol{Z}}}} = \phi \left( {{{\boldsymbol{Z}}^{(1)}},{\text{ }}{{\boldsymbol{Z}}^{(2)}},{\text{ }} … {\text{, }}{{\boldsymbol{Z}}^{(V)}}} \right), \\ &{\boldsymbol{E}} = \left( {{{\boldsymbol{E}}^{(1)}}{\text{; }}{{\boldsymbol{E}}^{(2)}}{\text{; }} … ;{\text{ }}{{\boldsymbol{E}}^{(V)}}} \right). \end{split} 如式(22)所示,本文通过张量对数行列式捕获各视角数据的全局表示信息以及隐藏在视角间的高阶信息,通过{l_{1,2}}范数正则化并捕获各视角数据的局部信息,最后对噪声进行稀疏化以增强模型对噪声的鲁棒性. 需要注意的是,在通常情况下各视角数据的维度可能不一致,但数据总数是相等的,因此本文在约束噪声时将各个视角的噪声矩阵串接起来,再对串接起来的总噪声矩阵{\boldsymbol{E}}施加稀疏约束. 从式(22)可以看出,本文综合考虑了各视角数据的全局信息和局部信息,以及隐藏在数据之间的高阶信息和互补信息,通过模型优化求解最终能学习到一个包含数据大量鉴别性信息的亲和矩阵,最后在亲和矩阵上执行谱聚类得到聚类结果.
2.3 模型优化
为获得式(22)的最优解,本文采用交替方向乘子法(alternating direction method of multipliers,ADMM)进行模型变量优化. 为方便求解,本文在式(22)的基础上引入辅助变量{\mathop {\boldsymbol J} \limits^ \smile}和{\overset{\frown}{{\boldsymbol{F}}}} ,最终模型变为
\begin{array}{l}\underset{{\boldsymbol Z}^{(v)}}{\mathrm{min}}\text{ }\psi \left({\mathop {\boldsymbol J} \limits^ \smile}\right)+\lambda {\Vert {\boldsymbol{E}}\Vert }_{2,1}+\beta {\Vert {\overset{\frown}{\boldsymbol{F}}}\Vert }_{1,2},\\ \text{s}\text{.t}\text{. }{\boldsymbol X}^{(v)}={\boldsymbol X}^{(v)}{\boldsymbol Z}^{(v)}+{\boldsymbol E}^{(v)}\text{, }v=1,\text{ 2,}… ,\text{ }V,\\ {\mathop {\boldsymbol Z} \limits^ \smile}={\mathop {\boldsymbol J} \limits^ \smile},{\overset{\frown}{\boldsymbol{\boldsymbol Z}}}={\overset{\frown}{\boldsymbol{F}}}\text{,}\\ {\overset{\frown}{\boldsymbol{\boldsymbol Z}}}=\varPhi \left({\boldsymbol Z}^{(1)},\text{ }{\boldsymbol Z}^{(2)},\text{ }… \text{, }{\boldsymbol Z}^{(V)}\right),\\ {\boldsymbol{E}}=\left({\boldsymbol E}^{(1)}\text{; }{\boldsymbol E}^{(2)}\text{; }… ;\text{ }{\boldsymbol E}^{(V)}\right). \end{array} (23) 式(23)可通过增广拉格朗日函数转变为无约束优化问题,分离各个变量并依次求解,其对应的增广拉格朗日函数为
\begin{split} &\mathcal{L}\left( {{{\boldsymbol{Z}}^{\left( {1, … ,V} \right)}},{\text{ }}{\boldsymbol{E}},{\text{ }}{\mathop {\boldsymbol J} \limits^ \smile},{\text{ }}{\overset{\frown}{{\boldsymbol{F}}}} ,{\text{ }}{{\boldsymbol{Y}}^{\left( {1, … ,V} \right)}},{\text{ }} {\overset{\frown}{{\boldsymbol{Q}}}}{\text{, }}{\mathop {\boldsymbol W} \limits^ \smile}} \right) = \\ & \psi \left( {{\mathop {\boldsymbol J} \limits^ \smile}} \right) + \lambda {\left\| {\boldsymbol{E}} \right\|_{2,1}} + \beta {\left\| {{\overset{\frown}{{\boldsymbol{F}}}} } \right\|_{1,2}} {\text{ + }}\left\langle { {\overset{\frown}{{\boldsymbol{Q}}}},{\text{ }}{\overset{\frown}{{\boldsymbol{Z}}}} - {\overset{\frown}{{\boldsymbol{F}}}} } \right\rangle + \\ &\frac{\alpha }{2}\left\| {{\overset{\frown}{{\boldsymbol{Z}}}} - {\overset{\frown}{{\boldsymbol{F}}}} } \right\|_{\text{F}}^{\text{2}} + \left\langle {{\mathop {\boldsymbol W} \limits^ \smile},{\mathop {\boldsymbol Z} \limits^ \smile} - {\mathop {\boldsymbol J} \limits^ \smile}} \right\rangle + \frac{\rho }{2}\left\| {{\mathop {\boldsymbol Z} \limits^ \smile} - {\mathop {\boldsymbol J} \limits^ \smile}} \right\|_{\text{F}}^{\text{2}} +\\ & \sum\limits_{v = 1}^V \left( \left\langle {{{\boldsymbol{Y}}^{\left( v \right)}},{{\boldsymbol{X}}^{(v)}} - {{\boldsymbol{X}}^{(v)}}{{\boldsymbol{Z}}^{(v)}} + {{\boldsymbol{E}}^{(v)}}} \right\rangle +\right. \\ & \left.\frac{\mu }{2}\left\| {{{\boldsymbol{X}}^{(v)}} - {{\boldsymbol{X}}^{(v)}}{{\boldsymbol{Z}}^{(v)}} + {{\boldsymbol{E}}^{(v)}}} \right\|_{\text{F}}^{\text{2}} \right), \end{split} (24) 其中{\overset{\frown}{\boldsymbol{Q}}}\text{, }{\mathop {\boldsymbol W} \limits^ \smile}\text{, }{{\boldsymbol{Y}}}^{\left(1,… ,V\right)} 为拉格朗日乘子,\mu ,{\text{ }}\rho ,{\text{ }}\alpha 为大于0的惩罚项参数. 通过固定相关变量,再对剩余变量逐个求解优化得到式(23)的最优解,以下将详细介绍所有变量的更新过程.
第1步. 更新变量{{\boldsymbol{Z}}^{\left( v \right)}}. 固定其他变量后,对变量{{\boldsymbol{Z}}^{\left( v \right)}}的求解可简化为:
\begin{gathered} \mathcal{L}\left( {{{\boldsymbol{Z}}^{\left( v \right)}}} \right) = \sum\limits_{v = 1}^V {\left( \begin{gathered} \frac{\mu }{2}\left\| {{{\boldsymbol{X}}^{(v)}} - {{\boldsymbol{X}}^{(v)}}{{\boldsymbol{Z}}^{(v)}} + {{\boldsymbol{E}}^{(v)}} + \frac{{{{\boldsymbol{Y}}^{\left( v \right)}}}}{\mu }} \right\|_{\text{F}}^{\text{2}}+ \\ \frac{\rho }{2}\left\| {{{\boldsymbol{Z}}^{(v)}} - {{\boldsymbol{J}}^{\left( v \right)}} + \frac{{{{\boldsymbol{W}}^{\left( v \right)}}}}{\rho }} \right\|_{\text{F}}^{\text{2}} + \\ \frac{\alpha }{2}\left\| {{{\boldsymbol{Z}}^{(v)}} - {{\boldsymbol{F}}^{\left( v \right)}} + \frac{{{{\boldsymbol{Q}}^{\left( v \right)}}}}{\alpha }} \right\|_{\text{F}}^{\text{2}} \\ \end{gathered} \right)} . \end{gathered} (25) 对式(25)求偏导,并将导数置为0可得{{\boldsymbol{Z}}^{\left( v \right)}}的求解方法为
{{\boldsymbol{Z}}^{(v)}} = {\left( {\left( {\rho + \alpha } \right){\boldsymbol{I}} + \mu {{\boldsymbol{X}}^{\left( v \right)}}^{^{\text{T}}}{{\boldsymbol{X}}^{\left( v \right)}}} \right)^{ - 1}}\left( {\mu {{\boldsymbol{X}}^{\left( v \right)}}^{^{\text{T}}}{{\boldsymbol{M}}^{\left( v \right)}} + \rho {{\boldsymbol{N}}^{\left( v \right)}} + \alpha {{\boldsymbol{C}}^{\left( v \right)}}} \right), (26) 其中{{\boldsymbol{M}}^{\left( v \right)}} = {{\boldsymbol{X}}^{\left( v \right)}} - {{\boldsymbol{E}}^{\left( v \right)}} + \dfrac{{{{\boldsymbol{Y}}^{\left( v \right)}}}}{\mu },{{\boldsymbol{N}}^{\left( v \right)}} = {{\boldsymbol{J}}^{\left( v \right)}} - \dfrac{{{{\boldsymbol{W}}^{\left( v \right)}}}}{\rho },{{\boldsymbol{C}}^{\left( v \right)}} = {{\boldsymbol{F}}^{\left( v \right)}} - \dfrac{{{{\boldsymbol{Q}}^{\left( v \right)}}}}{\alpha }.
第2步. 更新变量{\boldsymbol{E}}. 固定其他变量后,对变量{\boldsymbol{E}}的求解将变为如下优化问题:
\begin{split} {\boldsymbol{E}} = &\mathop {\arg \min }\limits_{\boldsymbol{E}} \lambda {\left\| {\boldsymbol{E}} \right\|_{2,1}} + \sum\limits_{v = 1}^V {\frac{\mu }{2}\left\| {{{\boldsymbol{X}}^{\left( v \right)}} - {{\boldsymbol{X}}^{\left( v \right)}}{{\boldsymbol{Z}}^{\left( v \right)}} - {{\boldsymbol{E}}^{\left( v \right)}} + \frac{{{{\boldsymbol{Y}}^{\left( v \right)}}}}{2}} \right\|_{\text{F}}^{\text{2}}}= \\ &\mathop {\arg \min }\limits_{\boldsymbol{E}} \frac{\lambda }{2}{\left\| {\boldsymbol{E}} \right\|_{2,1}} + \sum\limits_{v = 1}^V {\frac{1}{2}\left\| {{\boldsymbol{E}} - {\boldsymbol{D}}} \right\|_{\text{F}}^{\text{2}}, } \\[-1pt] \end{split} (27) 其中 {{\boldsymbol{X}}^{\left( v \right)}} - {{\boldsymbol{X}}^{\left( v \right)}}{{\boldsymbol{Z}}^{\left( v \right)}} + \dfrac{{{{\boldsymbol{Y}}^{\left( v \right)}}}}{\mu }={{\boldsymbol{D}}^{\left( v \right)}},{\boldsymbol{D}} = \left( {{{\boldsymbol{D}}^{\left( 1 \right)}};\;{{\boldsymbol{D}}^{\left( 2 \right)}};\; … ;\;{{\boldsymbol{D}}^{\left( V \right)}}} \right).
由于矩阵{\boldsymbol{E}}的各个列元素之间不相关,因此可将变量{\boldsymbol{E}}分解为n个子问题进行求解. 最终得到变量{\boldsymbol{E}}的求解方式为
{{\boldsymbol{E}}_{:,i}} = \left\{ {\begin{array}{*{20}{l}} {\dfrac{{{{\left\| {{{\boldsymbol{D}}_{:,i}}} \right\|}_2} - \dfrac{\lambda }{\mu }}}{{{{\left\| {{{\boldsymbol{D}}_{:,i}}} \right\|}_2}}}{{\boldsymbol{D}}_{:,i}}{\text{ }},}&{{{\left\| {{{\boldsymbol{D}}_{:,i}}} \right\|}_2} > \dfrac{\lambda }{\mu }, } \\ {0{\text{ ,}}}&{其他} . \end{array}} \right. (28) 第3步. 更新变量 {\overset{\frown}{{\boldsymbol{F}}}} . 固定其他无关变量后,变量 {\overset{\frown}{{\boldsymbol{F}}}} 的求解变为如下模型:
{\overset{\frown}{{\boldsymbol{F}}}} = {\mathop {\arg \min }\limits_{\hat {\mathcal{F}}}} \;\beta \left\| { {\overset{\frown}{{\boldsymbol{F}}}}} \right\|_{1,2}^2 + \frac{\alpha }{2}\left\| { {\overset{\frown}{{\boldsymbol{Z}}}} - {\overset{\frown}{{\boldsymbol{F}}}} + \frac{{ {\overset{\frown}{{\boldsymbol{Q}}}}}}{\alpha }} \right\|_{\text{F}}^{\text{2}}. (29) 为简化求解过程,可将张量 {\overset{\frown}{{\boldsymbol{Z}}}} 和 {\overset{\frown}{{\boldsymbol{F}}}} 分别分解为V个不相关的子问题,因此式(29)模型可简化为
{{\boldsymbol{F}}^{\left( v \right)}} = \mathop {\arg \min }\limits_{{{\boldsymbol{F}}^{\left( v \right)}}} {\text{ }}\frac{{{\text{2}}\beta }}{\alpha }\left\| {{{\boldsymbol{F}}^{\left( v \right)}}} \right\|_{1,2}^2 + \left\| {{{\boldsymbol{F}}^{\left( v \right)}} - \left( {{{\boldsymbol{Z}}^{\left( v \right)}} + \frac{{{{\boldsymbol{Q}}^{\left( v \right)}}}}{\alpha }} \right)} \right\|_{\text{F}}^{\text{2}}. (30) 对于矩阵 {{\boldsymbol{F}}^{\left( v \right)}} ,将其分解为n个子问题:
{\boldsymbol{F}}_{i,:}^{\left( v \right)} = {\text{sgn(}}{\boldsymbol{H}}_{i,:}^{\left( v \right)}{\text{)}} \circ {\left[ {\left| {{\boldsymbol{H}}_{i,:}^{\left( v \right)}} \right| - \frac{{2\beta t}}{{\alpha + 2\beta t}}{m_t}} \right]_ + }, (31) 其中 {{\boldsymbol{H}}^{\left( v \right)}} = {{\boldsymbol{Z}}^{\left( v \right)}} + \dfrac{{{{\boldsymbol{Q}}^{\left( v \right)}}}}{\alpha } , {\text{sgn}}\left( \cdot \right) 为符号函数, \circ 为Hadamard积,{\left[ {{\text{ }} \cdot {\text{ }}} \right]_ + } = \max \{ {\text{ }} \cdot {\text{ }},0\} ,{m_t} = \dfrac{1}{t}\displaystyle\sum\limits_{j = 1}^t {\left| {{\boldsymbol{H}}_{i,{d_j}}^{\left( v \right)}} \right|} ,{d_j}为{\boldsymbol{F}}_{i,:}^{\left( v \right)}元素按降序排列后对应的索引值,t为满足不等式\left| {{\boldsymbol{H}}_{i,:}^{\left( v \right)}} \right| - \dfrac{{2\beta t}}{{\alpha + 2\beta t}}{m_t}{\text{ > 0}}成立的最大整数.
第4步. 更新变量 {\mathop {\boldsymbol J} \limits^ \smile} . 固定其他无关变量后,对变量 {\mathop {\boldsymbol J} \limits^ \smile} 的求解变为如下优化问题:
{\mathop {\boldsymbol J} \limits^ \smile} = \mathop {\arg \min }\limits_{{\mathop {\boldsymbol J} \limits^ \smile}} {\text{ }}{\varPsi }\left( {{\mathop {\boldsymbol J} \limits^ \smile}} \right) + \frac{\rho }{2}\left\| {{\mathop {\boldsymbol Z} \limits^ \smile} - {\mathop {\boldsymbol J} \limits^ \smile} + \frac{{{\mathop {\boldsymbol W} \limits^ \smile}}}{\rho }} \right\|_{\text{F}}^{\text{2}}. (32) 令{\mathop {\boldsymbol G} \limits^ \smile} ={\mathop {\boldsymbol Z} \limits^ \smile}+ \dfrac{{{\mathop {\boldsymbol G} \limits^ \smile}}}{\rho } ,再将张量{\mathop {\boldsymbol G} \limits^ \smile} 和 {\mathop {\boldsymbol J} \limits^ \smile} 沿各自的第3维度进行傅里叶变换得到 {\overline{ \boldsymbol{G}}} 和 {\overline{ \boldsymbol{J}}} ,即 {\overline{ \boldsymbol{G}}} = fft\left( {{\mathop {\boldsymbol G} \limits^ \smile},{\text{ }}[],{\text{ }}3} \right), {\overline{ \boldsymbol{J}}} = fft\left( {{\mathop {\boldsymbol J} \limits^ \smile},{\text{ }}[],{\text{ }}3} \right) ,设它们对应的t-SVD分别为 {\overline{ \boldsymbol{G}}} = {{\overline{\boldsymbol{ U}}}}* {\overline{\boldsymbol \varSigma }}*{{{\overline{\boldsymbol{ V}}}}^{\text{T}}} 和 {\overline{ \boldsymbol{J}}} = {{\overline{\boldsymbol{ U}}}}*{{\overline{\boldsymbol{ S}}}}*{{{\overline{\boldsymbol{ V}}}}^{\text{T}}} ,则 {\overline{ \boldsymbol{ \varSigma}}} 和 {{\overline{\boldsymbol{ S}}}} 的第k个正切片 {{\overline {\boldsymbol \varSigma }}^{\left( k \right)}} 和 {{{\overline{\boldsymbol{ S}}}}^{\left( k \right)}} 的构成方式分别为 {{\overline {\boldsymbol \varSigma }}^{\left( k \right)}} = {\text{diag}}\left( {{\sigma _1}\left( {{{{\overline{\boldsymbol G}}}^{\left( k \right)}}} \right),} \right. \left. {{\sigma _2}\left( {{{{\overline{\boldsymbol G}}}^{\left( k \right)}}} \right), … ,{\sigma _V}\left( {{{{\overline{\boldsymbol G}}}^{\left( k \right)}}} \right)} \right) , {{{\overline{\boldsymbol{ S}}}}^{\left( k \right)}} = {\text{diag}}\left( {\sigma {{_1^{\left( k \right)}}^{^*}},\sigma {{_2^{\left( k \right)}}^{^*}}, … ,\sigma {{_V^{\left( k \right)}}^{^*}}} \right) ,由定理1可知 {{{\overline{\boldsymbol{ S}}}}^{\left( k \right)}} 的元素值\sigma_i^ {{\left( k \right)}^{^*}}可通过求解式(33)得到.
\begin{split}\frac{2\sigma_i^{(k)^*}}{1+\sigma_i^{(k)^*2}}+\frac1\rho\Big(\sigma_i^{(k)^*}-\sigma_i\Big(\overline{\boldsymbol{G}}^{(k)}\Big)\Big)=0 , \end{split} (33) \begin{split}\mathrm{s.t.}\ \sigma_i^{(k)^*}\ge0,i=1,2,\dots,V.\end{split} 然后将更新后得到的 {{\overline{\boldsymbol{ S}}}} 联合 {{\overline{\boldsymbol{ U}}}} 和 {{\overline{\boldsymbol{ V}}}} 通过t-product得到张量{\overline{\boldsymbol J}},即 {{\overline{\boldsymbol{ U}}}}*{{\overline{\boldsymbol{ S}}}}*{{{\overline{\boldsymbol{ V}}}}^{\text{T}}} = {\overline {\boldsymbol{J}} },最后将{\overline{\boldsymbol J}}进行反快速傅里叶变换得到张量{\mathop {\boldsymbol J} \limits^ \smile}. 算法1对张量{\mathop {\boldsymbol J} \limits^ \smile}的更新进行了总结.
第5步. 更新拉格朗日乘子 {{\boldsymbol{Y}}}^{\left(1,2,… ,V\right)},\text{ }{\overset{\frown}{\boldsymbol Q}}\text{, }{\mathop {\boldsymbol W} \limits^ \smile}和惩罚项参数\mu ,{\text{ }}\alpha ,{\text{ }}\rho . 相关变量的更新方式为:
{{\boldsymbol{Y}}^{\left( v \right)}} = {{\boldsymbol{Y}}^{\left( v \right)}} + \mu \left( {{{\boldsymbol{X}}^{\left( v \right)}} - {{\boldsymbol{X}}^{\left( v \right)}}{{\boldsymbol{Z}}^{\left( v \right)}} - {{\boldsymbol{E}}^{\left( v \right)}}} \right), (34) {\overset{\frown}{{\boldsymbol{Q}}}} = {\overset{\frown}{{\boldsymbol{Q}}}} + \alpha \left( {{\overset{\frown}{{\boldsymbol{Z}}}} - {\overset{\frown}{{\boldsymbol{F}}}} } \right), (35) {\mathop {\boldsymbol W} \limits^ \smile} = {\mathop {\boldsymbol W} \limits^ \smile} + \rho \left( {{\mathop {\boldsymbol Z} \limits^ \smile} - {\mathop {\boldsymbol J} \limits^ \smile}} \right), (36) \zeta = \min \left\{ {\zeta \eta ,{\kappa _{\max }}} \right\},{\text{ }}\zeta \in \left\{ {\alpha ,\rho ,\mu } \right\}, (37) 其中\eta 和{\kappa _{\max }}是常数.
以上即为式(22)的详细优化过程,算法2对整个算法的执行进行了总结.
算法1. 更新张量{\mathop {\boldsymbol J} \limits^ \smile}.
输入:{\mathop {\boldsymbol G} \limits^ \smile} ={\mathop {\boldsymbol Z} \limits^ \smile}+ \dfrac{{{\mathop {\boldsymbol G} \limits^ \smile}}}{\rho } ;
输出:{\mathop {\boldsymbol J} \limits^ \smile}.
① {\overline{ \boldsymbol{G}}} = fft\left( {{\mathop {\boldsymbol G} \limits^ \smile},{\text{ }}[],{\text{ }}3} \right) ;
② {{\overline{\boldsymbol{ U}}}}*{\overline{\boldsymbol \varSigma }}*{{{\overline{\boldsymbol{ V}}}}^{\text{T}}}\xleftarrow{{{\text{t-SVD}}}}{{\overline {\boldsymbol{G}}}} ;
③ for k = 1:n do
④ {{\overline {\boldsymbol \varSigma }}^{\left( k \right)}} = {\text{diag}}\left( {{\sigma _1}\left( {{{{\overline{\boldsymbol G}}}^{\left( k \right)}}} \right),{\sigma _2}\left( {{{{\overline{\boldsymbol G}}}^{\left( k \right)}}} \right), … ,{\sigma _V}\left( {{{{\overline{\boldsymbol G}}}^{\left( k \right)}}} \right)} \right) ;
⑤ {{{\overline{\boldsymbol{ S}}}}^{\left( k \right)}} = {\text{diag}}\left( {\sigma {{_1^{\left( k \right)}}^{^*}},\sigma {{_2^{\left( k \right)}}^{^*}}, … ,\sigma {{_V^{\left( k \right)}}^{^*}}} \right) ;
⑥ 根据式(33)得到\sigma _i^{{\left( k \right)}^{*}};
⑦ end for
⑧ {\overline{\boldsymbol J}}\xleftarrow{{}}{{\overline{\boldsymbol{ U}}}}*{{\overline{\boldsymbol{ S}}}}*{{{\overline{\boldsymbol{ V}}}}^{\text{T}}} ;
⑨ {\mathop {\boldsymbol J} \limits^ \smile} = ifft\left( {{\overline{\boldsymbol J}},{\text{ }}[],{\text{ }}3} \right) .
算法2. ATSVS执行过程.
输入:多视角数据{{\boldsymbol{X}}^{\left( v \right)}},参数\lambda 和\beta ,簇个数c;
输出:聚类结果Clu.
① 初始化:{{\boldsymbol{Z}}^{\left( v \right)}} = {\mathbf{0}},{{\boldsymbol{E}}^{\left( v \right)}} = {\mathbf{0}},{{\boldsymbol{Y}}^{\left( v \right)}} = {\mathbf{0}},v = 1, 2, … , V, \eta = 2, {\kappa _{\max }} = {10^{10}}, {\overset{\frown}{{\boldsymbol{Q}}}} = {\overset{\frown}{{\boldsymbol{F}}}} = {\mathbf{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{0} }} , {\mathop {\boldsymbol J} \limits^ \smile} = {\mathop {\boldsymbol W} \limits^ \smile} = {\mathop {\boldsymbol 0} \limits^ \smile}, \mu = \alpha = \rho = {10^{ - 5}};
② while not converge do
③ for v = 1,2, … ,V do
④ 使用式(26)更新{{\boldsymbol{Z}}^{\left( v \right)}};
⑤ end for
⑥ 使用式(27)更新{\boldsymbol{E}};
⑦ 使用式(30)更新 {\overset{\frown}{{\boldsymbol{F}}}} ;
⑧ 通过算法1更新{\mathop {\boldsymbol J} \limits^ \smile};
⑨ for v = 1,{\text{ }}2, … ,V do
⑩ 使用式(33)更新{{\boldsymbol{Y}}^{\left( v \right)}};
⑪ end for
⑫ 分别使用式(35)和式(36)更新 {\overset{\frown}{{\boldsymbol{Q}}}} 和{\mathop {\boldsymbol W} \limits^ \smile};
⑬ 使用式(37)更新\mu ,{\text{ }}\alpha ,{\text{ }}\rho ;
⑭ end while
⑮ 通过 {\boldsymbol{A}} = \dfrac{1}{V} {{\left( {\displaystyle\sum\limits_{v = 1}^V {\left| {{{\boldsymbol{Z}}^{\left( v \right)}}} \right| + \left| {{{\boldsymbol{Z}}^{\left( v \right)}}^{\text{T}}} \right|} } \right)}}得到亲和矩阵 {\boldsymbol{A}};
⑯ 将谱聚类应用到矩阵{\boldsymbol{A}}得到聚类结果Clu.
2.4 时间复杂度分析
本节将对算法的整体时间复杂度进行分析. 需要特别说明的是,本文在计算时间复杂度时忽略矩阵简单运算,如矩阵的加、减、点乘和点除等运算所需要的时间. 在更新{{\boldsymbol{Z}}^{\left( v \right)}}的过程中,消耗时间最多的操作是对 \left( {\left( {\rho + \alpha } \right){\boldsymbol{I}} + \mu {{\boldsymbol{X}}^{\left( v \right)}}^{\text{T}}{{\boldsymbol{X}}^{\left( v \right)}}} \right) 的求逆运算,对应的时间复杂度为O\left( {{n^3}} \right);在更新{\boldsymbol{E}} \in {\mathbb{R}^{d \times n}}的过程中,主要涉及对{\left\| {\boldsymbol{E}} \right\|_{2,1}}的求解,该过程消耗的时间为O\left( {d \times n} \right),其中d = \displaystyle\sum\limits_{i = 1}^V {{d_i}} ;在对变量 {\overset{\frown}{{\boldsymbol{F}}}} \in {\mathbb{R}^{n \times n \times V}} 的更新过程中,消耗时间最多的是{l_{1,2}}范数的求解过程,该过程的时间复杂度为O\left( {V \times {n^2}} \right);在更新张量 {\mathop {\boldsymbol J} \limits^ \smile} 的过程中,对张量{\mathop {\boldsymbol G} \limits^ \smile} \in {\mathbb{R}^{n \times V \times n}} 沿第3维度的傅里叶变换及逆变换的时间消耗为O\left( {{n^2} \times V \times \log n} \right),其次,在傅里叶域内对n个正切片进行SVD分解消耗的时间为O\left( {{n^2} \times {V^2}} \right);由于更新拉格朗日乘子和惩罚项参数仅涉及矩阵的简单运算,因此本文忽略该部分的时间消耗. 综上,假设迭代次数为t,则整个算法的时间复杂度为O\left( {t \times \left( {{n^3} + d \times n + V \times {n^2} + {n^2} \times V \times \log n + {n^2} \times {V^2}} \right)} \right),由于v << n,因此可化简得到O\left( {t \times {n^3}} \right).
3. 实验分析
为评价本文所提算法的综合性能,本节将ATSVS应用到相关数据集上进行实验,包括算法的聚类结果对比实验、噪声鲁棒性实验、聚类性能可视化实验、参数分析实验和算法模型收敛性实验.
3.1 实验设置
3.1.1 实验环境
本文实验使用MATLAB 2019a编程环境,操作系统为Windows11,内存为16 GB,处理器为AMD Ryzen 5 5600H with Radeon Graphics 3.30 GHz.
3.1.2 实验数据集
为验证本文所提算法的性能,本文选取了9个数据集进行了实验. 表2对数据集相关信息做了简要描述.
表 2 数据集描述Table 2. Description of the Datasets数据集 类别数 数据量 视角数 Yale 15 165 3 Extended Yale B 10 650 3 WebKB_2views 2 1 051 2 ORL 40 400 4 HW 10 2 000 6 BBC 5 685 4 BBCSport 5 544 2 MSRC_V1 7 210 5 Scene-15 15 4 485 3 在表2中,Yale
1 ,Extended Yale B2 ,ORL3 是人脸图像数据集. Yale数据集包含了15个人的165张不同的灰度图像,每个人有11张不同面部表情的照片. Extended Yale B数据集由38个人2 414张正面人脸图像组成,每个人在不同光照条件下拍摄约64张人脸图像,本文使用该数据集前10个对象组成的650张人脸图像进行实验. ORL数据集包括了40个人在不同光照、时间和面部装饰环境下采集的400张灰度图像. HW4 是选自UCI机器学习知识库的0~9数字的手写数字数据集,其中每个数字均有200张图像. WebKB_2views5 是由世界知识库项目收集的网页数据集,共有1 051页. BBC6 和BBCSport7 是2个多段落文本数据集,其中BBC是从BBC新闻网站收集的包含体育、政治、商业和娱乐等主题的共685条新闻报道;BBCSport是从BBCSport网站收集的包括田径、板球、足球、橄榄球和网球5个类别的共544条数据.MSRC_V1是一个场景识别数据集,包含了来自树、汽车、脸、牛、自行车、建筑物和飞机这7类对象的共210张图像. Scene-15数据集包含了卧室、厨房、客厅、工厂等15类室内和室外场景的图像,每个场景包含210~410张图像.3.1.3 对比算法说明
为评估本文所提算法的聚类性能,将本文所提算法和11种对比算法在3.1.2节所介绍数据集上进行测试,本节将对选取的对比算法作简要介绍.
1)谱聚类算法(spectral clustering,SC)[27]. 为了验证本文所提算法能够捕获各个视角数据间的互补信息和高阶信息,本文选取了经典的SC算法作为单视角对比算法,对每个视角数据都执行标准的谱聚类,记录在单个视角上取得的最好结果作为该算法在相应数据集上的最终聚类结果.
2)基于自适应加权的多视角聚类(multiview clustering via adaptively weighted procrustes,AWP)[28]. AWP考虑了不同视角的重要性差异,提出一种视角加权策略进行聚类. 该算法模型不含有惩罚项参数,在实验过程中对变量的初始化采用作者原始设置值.
3)协同正则的多视角谱聚类(co-regularized multi-view spectral clustering,CoregSC)算法[29]. CoregSC提出一种协同正则策略,捕获各视角数据间的互补信息. 对CoregSC算法中含有的正则化参数\lambda ,本文选取原文中推荐的参数选区范围[0.01,0.05]进行实验.
4)多视角一致性图聚类(multiview consensus graph clustering,MCGC)[30]. MCGC通过同时优化不同视角和公共空间的信息,学习一个一致性图,图中的连通分量个数与簇个数相同,最后利用一致性图直接获得聚类结果. 对于MCGC算法中包含的参数\beta ,本文采取原文使用的\;\beta = 0.6在所有数据集上进行实验.
5)基于图学习的多视角聚类(graph learning for multiview clustering,MVGL)[31]. MVGL是一种基于图学习的方法,首先根据不同视角数据学习一个初始图,然后通过为拉普拉斯施加秩约束进一步优化初始图,最后将各视角的图集成到全局图中,并通过全局图直接获得聚类结果. 对于MVGL算法中包含的参数\;\beta 和\gamma ,本文采用原文使用的参数初始化方法,即\beta = \gamma = 1,算法在迭代过程中会自行调整参数值.
6)加权多视角谱聚类算法(weighted multi-view spectral clustering based on spectral perturbation,WMSC)[32]. WMSC在遵循2个基本原则的条件下利用谱扰动理论对各视角进行加权建模,这2个原则是:①每个视角上的聚类结果应接近于一致聚类结果;②对聚类结果相似的视角赋予相似的权重. 对于WMSC算法中包含的参数\tilde \beta 和\tilde \eta ,本文按照原文中给定的参数选取范围进行网格寻优,即\tilde \beta \in [0.08,{\text{ 0}}{\text{.14]}}和\tilde \eta \in [0.08, 0.18],在范围内每隔0.02为一个步长进行寻优选取最优结果作为算法的最终结果.
7)基于图的多视角聚类框架GBS(a study of graph-based system for multi-view clustering)[33]. GBS利用各视角特征数据构造所有视角的图矩阵,然后再将所有视角的图矩阵加权融合成一个统一的图矩阵,最终利用图矩阵直接获得聚类结果. 对于GBS算法包含的参数k和\lambda ,本文采取原文设置的参数值进行实验,即k = 15和\lambda = 1,其中\lambda 的值会随着算法的迭代自动更新.
8)基于t-SVD的多视角子空间聚类(t-SVD based multi-view subspace clustering,t-SVD-MSC)[13]. t-SVD-MSC通过叠加不同视角的子空间自表示矩阵构建张量,然后旋转张量并施加低秩张量约束以此捕获低秩张量子空间结构,最后将优化得到的张量还原成多个自表示矩阵,并将各视角自表示矩阵简单相加后放入谱聚类模型得到最终聚类结果. 对于t-SVD-MSC算法中包含的参数\lambda ,本文按照原文所给参数范围\lambda \in [0.1,{\text{ 2}}]随机选取参数值进行实验,本次实验所选参数为\lambda = 0.5.
9)基于加权张量核范数最小化(weighted tensor-nuclear norm minimization,WTNNM)的多视角聚类[14].WTNNM考虑了在t-SVD过程中各个奇异值的贡献差异性,提出了一种加权张量核范数对自表示张量进行低秩张量约束,进一步利用嵌入在不同视角间的高阶关联进行聚类. 对于WTNNM所包含的参数\lambda 和每个数据集各个视角的权重,本文对参数\lambda 根据原文中给定的参数寻优范围进行寻优,即 \lambda \in \{ 0.000{\text{ }}1, {\text{ }}0.000{\text{ }}5,{\text{ }}0.001,{\text{ }}0.005,{\text{ }}0.01,{\text{ }}0.05,{\text{ }}0.1,{\text{ }}0.5,{\text{ }}1,5,{\text{ }} 10,{\text{ }}100\} ,权重参数如果与原文所用数据集相同则按照原文所给权重进行实验,否则将各视角权重置为1进行实验.
10)联合流形学习和张量核范数的多视角聚类算法LSLMC(latent similarity learning for multi-view clustering)[34]. LSLMC将流形学习和张量奇异值分解集成到一个统一的框架,通过局部流形学习和谱聚类相结合的方法,利用每个视角中计算出的相似度矩阵来恢复潜在的表示矩阵,此外,LSLMC还通过误差矩阵构建误差张量并使用低秩张量约束来挖掘视角特定信息和噪声. 对于LSLMC算法包含的参数\alpha 和\lambda ,本文根据原文所给参数范围进行寻优,即\alpha \in \{ 0.001,{\text{ }}0.01,{\text{ }}0.1,{\text{ }}1,{\text{ }}10,{\text{ }}50\} 和 \lambda \in \{ 0.005,{\text{ }}0.01,{\text{ }}0.1, {\text{ }}1, {\text{ }}10, {\text{ }}50,{\text{ }}100\} ,寻优后将最优结果作为算法最终结果.
11)基于低秩对称亲和图(low-rank symmetric affinity graph, LSGMC)[35]的多视角子空间聚类. LSGMC将系数矩阵分成3部分来追求视角间的一致性低秩结构,并利用对称约束来保证每对数据样本的权重一致性,利用融合机制捕获数据的固有结构,最后采用自适应信息缩减策略来生成用于谱聚类的高质量相似度矩阵. 对于LSGMC算法包含的参数\lambda 和p,本文按照原文所给参数寻优范围进行寻优,即p \in \{ 0.01, 0.1,{\text{ }}0.2,{\text{ }} … , {\text{ }}0.9\} 和\lambda \in \{ {10^{ - 5}},{\text{ }}{10^{ - 4}},{\text{ }} … ,{\text{ }}{10^2}\} ,寻优后将最优结果作为算法最终结果.
为验证{l_{1,2}}捕获数据局部信息的有效性,本文将ATSVS去除{l_{1,2}}范数正则项后所得的模型(记作ATSVS-noL12)与其他算法在相同数据集上进行实验,并记录实验结果进行对比.
对比算法代码中,SC算法代码来自MATLAB中的“spectralcluster”库函数,其余算法代码均由作者提供.
3.2 聚类结果分析
本文共选取9个真实数据集来验证ATSVS的聚类性能,聚类结果采用准确率(Accuracy)、标准化互信息(normalized mutual information,NMI)、纯度(Purity)、F分数(F-score)、召回率(Recall)、调整兰德系数(adjusted rand index,ARI)这6个指标进行量化评价,它们的值越高表示聚类效果越好. 本文为避免实验结果出现偶然性,在每个数据集上先通过网格寻优的方式找到最优结果对应的参数,然后利用该参数重复进行20次实验,记录20次实验对应的量化指标平均值作为ATSVS算法在该数据集上的最终聚类结果. 表3~11分别列出了本文所提算法和11个对比算法在各个数据集上的聚类指标结果. 很明显,本文所提算法在所有数据集上均得到了最优的指标综合数据. 下面进行具体分析.
表 3 在Yale数据集上的聚类结果(平均值)Table 3. Clustering Results (Mean) on Yale Dataset算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.657 0 0.676 9 0.657 0 0.508 5 0.527 5 0.475 4 AWP 0.587 9 0.647 6 0.587 9 0.491 3 0.529 7 0.455 7 CoregSC 0.618 2 0.657 6 0.618 2 0.489 2 0.509 1 0.454 7 MCGC 0.557 6 0.590 0 0.557 6 0.388 8 0.495 8 0.339 8 MVGL 0.624 2 0.671 2 0.630 3 0.497 8 0.545 5 0.462 1 WMSC 0.630 3 0.672 3 0.630 3 0.512 3 0.528 5 0.479 6 GBS 0.654 5 0.673 6 0.660 6 0.480 1 0.562 4 0.441 0 t-SVD-MSC 0.920 6 0.927 4 0.921 2 0.872 6 0.891 3 0.864 1 WTNNM 0.941 2 0.953 9 0.943 0 0.920 1 0.933 0 0.914 8 LSLMC 0.706 7 0.730 2 0.706 7 0.570 2 0.598 5 0.540 9 LSGMC 0.460 6 0.502 5 0.497 0 0.288 5 0.277 4 0.240 4 ATSVS-noL12
(本文)0.971 5 0.980 6 0.973 3 0.961 5 0.975 0 0.958 9 ATSVS(本文) 0.997 0 0.996 1 0.997 0 0.993 6 0.993 9 0.993 2 注:黑体数值表示最优结果. 表 4 在Extended Yale B数据集上的聚类结果(平均值)Table 4. Clustering Results (Mean) on Extended Yale B Dataset算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.631 1 0.664 8 0.632 6 0.498 6 0.628 3 0.430 9 AWP 0.307 7 0.329 3 0.320 0 0.255 5 0.303 1 0.159 6 CoregSC 0.398 6 0.387 4 0.410 8 0.270 4 0.314 9 0.177 9 MCGC 0.295 4 0.287 0 0.298 5 0.218 0 0.336 0 0.097 8 MVGL 0.347 7 0.320 1 0.350 8 0.212 8 0.327 9 0.091 9 WMSC 0.381 7 0.375 1 0.395 5 0.261 7 0.304 2 0.168 3 GBS 0.433 8 0.416 3 0.436 9 0.265 1 0.378 2 0.157 2 t-SVD-MSC 0.547 1 0.566 4 0.549 7 0.444 7 0.470 1 0.380 4 WTNNM 0.585 4 0.596 1 0.587 5 0.468 0 0.498 0 0.405 9 LSLMC 0.440 0 0.431 6 0.441 5 0.304 3 0.380 0 0.211 0 LSGMC 0.966 2 0.930 3 0.966 2 0.931 0 0.928 3 0.923 5 ATSVS-noL12
(本文)0.961 1 0.939 3 0.961 1 0.925 5 0.927 6 0.917 3 ATSVS(本文) 0.976 6 0.962 4 0.976 6 0.954 6 0.956 4 0.949 6 注:黑体数值表示最优结果. 表 5 在WebKB_2views数据集上的聚类结果(平均值)Table 5. Clustering Results (Mean) on WebKB_2views Dataset算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.833 5 0.161 7 0.833 5 0.821 7 0.973 5 0.256 2 AWP 0.815 4 0.089 8 0.815 4 0.806 5 0.954 3 0.194 5 CoregSC 0.819 2 0.100 6 0.819 2 0.808 3 0.950 3 0.214 2 MCGC 0.814 5 0.087 1 0.814 5 0.805 9 0.954 7 0.190 2 MVGL 0.820 2 0.118 4 0.820 2 0.813 4 0.978 6 0.193 1 WMSC 0.891 5 0.352 6 0.891 5 0.859 8 0.902 8 0.549 3 GBS 0.776 4 0.001 0 0.781 2 0.786 7 0.974 6 0.010 2 t-SVD-MSC 0.782 1 0.002 8 0.782 1 0.794 0 0.999 4 0.004 9 WTNNM 0.782 1 0.002 8 0.782 1 0.794 0 0.999 4 0.004 9 LSLMC 0.829 7 0.131 4 0.829 7 0.813 7 0.939 3 0.267 4 LSGMC 0.780 2 0.000 4 0.999 0 0.792 0 0.657 5 -0.001 4 ATSVS-noL12
(本文)0.949 6 0.679 1 0.949 6 0.924 2 0.887 9 0.794 5 ATSVS(本文) 0.980 0 0.830 9 0.980 0 0.969 7 0.953 7 0.914 2 注:黑体数值表示最优结果. 表 6 在ORL数据集上的聚类结果(平均值)Table 6. Clustering Results (Mean) on ORL Dataset算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.819 3 0.902 3 0.839 3 0.751 9 0.776 3 0.746 0 AWP 0.755 0 0.872 8 0.777 5 0.696 1 0.770 0 0.688 4 CoregSC 0.813 8 0.899 4 0.836 0 0.747 3 0.784 8 0.741 1 MCGC 0.590 0 0.727 5 0.660 0 0.245 5 0.762 8 0.215 8 MVGL 0.707 5 0.833 7 0.772 5 0.414 8 0.817 8 0.394 4 WMSC 0.823 5 0.902 5 0.847 0 0.758 7 0.791 7 0.752 9 GBS 0.632 5 0.803 5 0.715 0 0.359 9 0.801 1 0.336 7 t-SVD-MSC 0.966 0 0.989 9 0.975 0 0.965 6 0.984 8 0.964 8 WTNNM 0.979 3 0.994 4 0.985 0 0.980 0 0.992 5 0.979 5 LSLMC 0.820 5 0.910 6 0.849 5 0.760 9 0.804 8 0.755 1 LSGMC 0.782 5 0.880 9 0.807 5 0.694 2 0.656 0 0.686 7 ATSVS-noL12
(本文)0.966 0 0.990 6 0.975 0 0.967 3 0.988 4 0.966 5 ATSVS(本文) 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 注:黑体数值表示最优结果. 表 7 在HW数据集上的聚类结果(平均值)Table 7. Clustering Results (Mean) on HW Dataset算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.968 5 0.927 5 0.968 5 0.938 2 0.938 4 0.931 3 AWP 0.879 5 0.890 8 0.880 0 0.869 8 0.954 1 0.854 0 CoregSC 0.924 4 0.890 1 0.924 4 0.870 7 0.872 3 0.856 4 MCGC 0.591 5 0.701 3 0.593 0 0.642 9 0.968 4 0.588 1 MVGL 0.853 0 0.889 9 0.880 5 0.849 3 0.916 5 0.831 3 WMSC 0.841 4 0.859 5 0.866 9 0.829 3 0.887 7 0.809 1 GBS 0.881 0 0.892 3 0.881 0 0.865 4 0.900 8 0.849 9 t-SVD-MSC 0.997 5 0.993 5 0.997 5 0.995 0 0.995 0 0.994 5 WTNNM 0.995 0 0.987 2 0.995 0 0.990 0 0.990 1 0.988 9 LSLMC 0.968 5 0.931 1 0.968 5 0.938 2 0.938 6 0.931 4 LSGMC 0.977 5 0.947 4 0.977 5 0.955 6 0.955 4 0.950 7 ATSVS-noL12
(本文)0.999 5 0.998 6 0.999 5 0.999 0 0.999 0 0.998 9 ATSVS(本文) 0.999 5 0.998 6 0.999 5 0.999 0 0.999 0 0.998 9 注:黑体数值表示最优结果. 表 8 在BBC数据集上的聚类结果(平均值)Table 8. Clustering Results (Mean) on BBC Dataset算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.439 7 0.230 2 0.496 4 0.354 8 0.494 4 0.103 9 AWP 0.389 8 0.199 3 0.458 4 0.344 5 0.551 8 0.032 3 CoregSC 0.407 7 0.234 1 0.492 4 0.341 0 0.468 4 0.060 8 MCGC 0.327 0 0.005 2 0.331 4 0.378 4 0.986 3 −0.001 3 MVGL 0.346 0 0.039 2 0.365 0 0.374 5 0.915 4 0.002 2 WMSC 0.423 5 0.238 3 0.504 4 0.355 8 0.493 5 0.080 3 GBS 0.693 4 0.485 2 0.693 4 0.633 3 0.860 0 0.478 9 t-SVD-MSC 0.937 2 0.861 6 0.937 2 0.893 6 0.863 6 0.862 4 WTNNM 0.902 9 0.813 7 0.902 9 0.833 2 0.782 7 0.786 3 LSLMC 0.849 6 0.680 7 0.849 6 0.783 1 0.778 7 0.717 2 LSGMC 0.890 5 0.754 3 0.890 5 0.833 2 0.851 7 0.783 5 ATSVS-noL12
(本文)0.992 7 0.974 9 0.992 7 0.986 7 0.980 7 0.982 6 ATSVS(本文) 0.994 2 0.980 7 0.986 2 0.989 4 0.994 2 0.984 7 注:黑体数值表示最优结果. 表 9 在BBCSport数据集上的聚类结果(平均值)Table 9. Clustering Results (Mean) on BBCSport Dataset算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.560 7 0.427 1 0.652 6 0.463 6 0.508 1 0.275 6 AWP 0.634 2 0.442 6 0.704 0 0.563 6 0.743 5 0.379 9 CoregSC 0.632 4 0.464 5 0.742 6 0.534 0 0.507 5 0.397 8 MCGC 0.404 4 0.109 0 0.433 8 0.391 4 0.871 5 0.034 1 MVGL 0.409 9 0.097 8 0.432 0 0.399 2 0.913 5 0.042 1 WMSC 0.610 3 0.471 0 0.680 5 0.519 0 0.528 1 0.364 9 GBS 0.807 0 0.722 6 0.843 8 0.794 3 0.875 3 0.721 8 t-SVD-MSC 0.965 1 0.896 7 0.965 1 0.933 0 0.915 2 0.912 5 WTNNM 0.973 5 0.916 8 0.973 5 0.948 8 0.934 4 0.933 1 LSLMC 0.944 9 0.854 4 0.944 9 0.886 3 0.878 7 0.851 1 LSGMC 0.935 7 0.849 1 0.935 7 0.862 1 0.870 3 0.819 4 ATSVS-noL12
(本文)0.970 6 0.915 4 0.970 6 0.939 8 0.925 5 0.921 3 ATSVS(本文) 0.985 3 0.955 1 0.985 3 0.976 6 0.970 6 0.969 4 注:黑体数值表示最优结果. 表 10 在MSRC_V1数据集上的聚类结果(平均值)Table 10. Clustering Results (Mean) on MSRC_V1 Dataset算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.761 9 0.642 5 0.761 9 0.609 8 0.634 5 0.544 1 AWP 0.742 9 0.671 2 0.747 6 0.676 3 0.783 3 0.615 7 CoregSC 0.804 8 0.719 5 0.804 8 0.694 7 0.704 8 0.644 7 MCGC 0.742 9 0.632 5 0.747 6 0.619 1 0.715 9 0.547 8 MVGL 0.747 6 0.721 4 0.776 2 0.673 6 0.792 1 0.611 7 WMSC 0.761 9 0.712 4 0.800 0 0.686 7 0.709 0 0.634 4 GBS 0.895 2 0.816 4 0.895 2 0.799 7 0.814 4 0.766 8 t-SVD-MSC 0.919 0 0.870 0 0.919 0 0.856 0 0.861 1 0.832 7 WTNNM 0.990 5 0.978 3 0.990 5 0.980 5 0.981 0 0.977 3 LSLMC 0.795 2 0.695 0 0.795 2 0.664 9 0.674 9 0.610 0 LSGMC 0.833 3 0.728 5 0.833 3 0.709 3 0.700 9 0.661 8 ATSVS-noL12
(本文)0.995 2 0.989 2 0.995 2 0.990 3 0.990 5 0.988 8 ATSVS(本文) 0.995 2 0.989 2 0.995 2 0.990 3 0.990 5 0.988 8 注:黑体数值表示最优结果. 表 11 在Scene-15数据集上的聚类结果(平均值)Table 11. Clustering Results (Mean) on Scene-15 Dataset算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.361 9 0.389 5 0.414 0 0.268 4 0.276 1 0.212 5 AWP 0.366 3 0.356 4 0.402 0 0.249 6 0.273 5 0.188 6 CoregSC 0.410 9 0.395 0 0.457 7 0.289 3 0.293 2 0.235 8 MCGC 0.156 3 0.103 1 0.158 8 0.154 2 0.853 6 0.032 6 MVGL 0.196 2 0.181 0 0.210 9 0.188 3 0.693 9 0.078 1 WMSC 0.432 6 0.434 0 0.466 9 0.314 4 0.323 3 0.261 9 GBS 0.218 5 0.151 2 0.836 6 0.147 0 0.077 8 0.018 0 t-SVD-MSC 0.763 8 0.766 6 0.815 2 0.707 3 0.716 7 0.685 3 WTNNM 0.680 0 0.456 2 0.534 2 0.374 5 0.372 4 0.328 7 LSLMC 0.533 6 0.575 0 0.602 0 0.457 5 0.472 2 0.430 5 LSGMC 0.473 6 0.480 9 0.534 2 0.370 3 0.354 0 0.321 2 ATSVS-noL12(本文) 0.861 1 0.853 2 0.890 5 0.825 4 0.829 9 0.812 3 ATSVS(本文) 0.929 8 0.887 8 0.871 7 0.880 6 0.882 4 0.878 8 注:黑体数值表示最优结果. 1)为验证ATSVS对数据集的适用性,本文采用来自6种不同类型的共10个数据集对比算法的聚类性能. 根据表3~10可知ATSVS在所有数据集上均取得了最优的聚类效果. 因此可得,ATSVS能够适用于多种类型的数据集,即ATSVS对数据集的类型具有鲁棒性.
2)从表3~10可以看出,ATSVS的聚类性能普遍优于单视角聚类算法SC,说明ATSVS能够有效捕获各视角间的互补信息,进而提升聚类效果.
3)ATSVS的聚类性能远优于AWP,WMSC,GBS,WTNNM这4种采用不同策略对各视角数据进行加权的聚类算法. AWP,WMSC,GBS在处理数据时未能将各视角数据放在同一空间进行,所以在加权过程中可能会由于各视角差异过大而无法采用统一的重要性度量方法进行准确加权. WTNNM则直接通过对数据集的先验信息进行手动加权,导致算法缺少灵活性. 因此可以得出结论:ATSVS所采用的将数据放到张量空间并根据数据自身特点进行视角重要性判别的方法有利于获得更优的聚类结果.
4)ATSVS在大部分数据集上均取得了比t-SVD-MSC和WTNNM更好的聚类结果. ATSVS在ORL数据集上获得了与t-SVD-MSC相同的聚类结果,在其他数据集上均取得了比t-SVD-MSC更优秀的聚类结果. 这是因为这3个算法在张量低秩约束过程中采用的方法不同,t-SVD-MSC采用的是基于t-SVD的张量核范数,通过将奇异值简单相加对张量进行秩估计,WTNNM则采用加权张量核范数通过对奇异值加权的方式平衡各奇异值的贡献程度,而ATSVS采用的是更符合秩特性的张量对数行列式函数,能够在秩估计过程中获得更加准确的秩估计值. 因此可以得出结论:张量对数行列式函数在低秩约束方面具有比基于t-SVD的张量核范数和加权张量核范数更好的效果,能够更有效捕获各视角的全局信息和嵌入在各视角数据间的高阶信息.
5)通过对比ATSVS和ATSVS-noL12的聚类结果可知,ATSVS的聚类结果普遍优于ATSVS-noL12.这是因为ATSVS在ATSVS-noL12的基础上对表示张量增加了基于{l_{1,2}}范数正则项,通过将稀疏技术和流形正则技术结合的方式捕获了各视角数据的局部信息. 因此可以得出结论,捕获数据的局部信息对提升算法的聚类性能具有较好的帮助,且{l_{1,2}}范数在捕获数据局部信息方面具有较好的效果.
6)通过对比LSLMC和ATSVS的聚类结果可知,ATSVS的聚类结果普遍优于LSLMC. 这是因为LSLMC通过流形正则项捕获数据的局部信息,而ATSVS则使用{l_{1,2}}范数作为正则项,在一定程度上克服了流形正则技术对噪声敏感的缺点. 因此可以得出结论:{l_{1,2}}范数在捕获数据局部信息方面具有比流形正则化更好的效果.
7)通过对比所有数据集上的实验结果可知,使用了张量的方法t-SVD-MSC,WTNNM,LSLMC以及本文所提算法ATSVS的聚类结果均优于其他未使用张量的算法. 这是因为单个视角的数据除了其本身所包含的鉴别性信息,还包含了对其他视角的互补信息,引入张量表示方法可以捕获各视角数据之间的互补信息,更好地刻画数据分布特征. 因此,在多视角聚类领域引入张量表示技术能够有效捕获各视角数据之间的高阶信息和互补信息,提升算法的聚类效果.
3.3 聚类性能可视化
为进一步说明ATSVS在聚类性能上的优势,本节将从t分布随机邻居嵌入(t-SNE)[36]和混淆矩阵2个角度对算法性能进行可视化分析.
本文在BBCSport和HW数据集上对每个视角的原始数据和最终学习到的亲和矩阵通过t-SNE进行可视化展示,最终呈现结果如图2和图3所示. 需要说明的是,本文在可视化过程中采用不同颜色和形状区分不同的簇,同一颜色形状的点越聚集、不同颜色形状的点越分散说明簇的可分离性越好. 根据图2(a)(b)和图3(a)~(f)可以看出,在BBCSport和HW数据集的各个视角中各个簇的数据点互相混合在一起,很难直接通过各个视角的数据进行簇划分. 图2(c)和图3(g)展示了ATSVS学习到的亲和矩阵t-SNE可视化结果,可以明显看出ATSVS能够把每个簇的大部分数据集中到一起,并使得簇与簇之间具有明显的划分. 据此可以得出结论:ATSVS能够充分利用各个视角数据上的全局和局部信息以及视角间的高阶信息来学习一个具有高鉴别性的亲和矩阵进行聚类.
为对比不同算法的类标划分情况,本文通过混淆矩阵展示了所有对比算法和ATSVS在BBC数据集上的类标划分,划分结果如图4所示. 混淆矩阵的行和列分别代表真实标签和预测标签,{\text{C}}i表示第i个簇,矩阵中第i行的数字加起来等于第i个簇包含的数据点总数,第i列表示相应算法划分到第i个簇中的数据所对应的真实簇分布. 在混淆矩阵中,越好的簇划分对应的矩阵对角块上颜色应该越深,每一行除对角块上的数字,其他位置的数字应该越小,很明显,本文所提算法ATSVS相比其他算法所对应的混淆矩阵更明显具有此特征. 从图4(i)可以看出,ATSVS得到的混淆矩阵第1,2,4行除对角块有颜色及数字,其他位置均无颜色及数字均为0,说明ATSVS对于这3个簇得到了完全正确的划分,在第3行和第5行也分别仅有3个和1个数据点未被划分正确,其余数据点均得到了正确的簇划分,说明ATSVS相较于对比算法具有极高的簇划分正确率,即ATSVS相较对比算法具有更好的聚类性能.
3.4 噪声鲁棒性实验
为验证ATSVS对噪声的鲁棒性,本文将ATSVS算法与对比算法在BBCSport数据集上进行实验对比. 本文在BBCSport数据集的每个视图中添加了服从均值为0、方差为0.1的正态分布的高斯噪声数据点. 在BBCSport数据集的噪声比为0.1,0.2,0.3,0.4,0.5的情况下,将聚类结果的准确率作为算法性能的评价指标. 最终,得到了ATSVS和对比算法在加入不同噪声比的BBCSport数据集上的聚类准确率对比,并通过图5由折线图展示.
如图5所示,在未加入噪声时,ATSVS具有最高的聚类准确率,随着加入噪声比例的增大,ATSVS的聚类准确率有略微下降,而其他算法的准确率则出现大幅下降或高低起伏的现象,但无论在哪个噪声比例下其聚类准确率均低于ATSVS,说明ATSVS相较于其他算法对噪声的鲁棒性更好,能够有效降低噪声信息所带来的负面影响.
3.5 参数分析
本文所提算法模型共有2个参数\lambda 和\;\beta ,分别调节误差项和{l_{1,2}}范数正则项在模型中的贡献程度. 本节为分析2个参数变化对算法性能的影响程度,在Yale和ORL数据集上通过网格调参法得到2个参数与聚类准确率的变化关系,其中参数的寻优值域为 \left\{ {{{10}^1},{{10}^0},{{10}^{ - 1}},{5^{ - 1}},{{10}^{ - 2}},{5^{ - 2}},{{10}^{ - 3}},{5^{ - 3}},{{10}^{ - 4}},{5^{ - 4}},{{10}^{ - 5}},{5^{ - 5}}} \right\} ,最终得到参数变化与聚类准确率的关系通过图6用3维柱状图的形式进行展示.
通过图6可以看出,不管是在Yale还是ORL数据集上,参数\lambda 的变化对聚类准确率都有一定的影响,而参数\;\beta 的变化对聚类准确率的影响都不是很大,说明算法模型对参数\lambda 敏感、对参数\;\beta 不敏感. 这是因为参数\lambda 调节的是噪声约束项在模型中的贡献程度,当数据集未被大量噪声污染时,较小的惩罚参数值会导致模型具有较大的重构误差,不利于模型取得较好的聚类结果. 如图6所示,ATSVS在Yale数据集上当\lambda \in \left\{ {{{10}^0},{5^{ - 1}}} \right\}和\beta \in \left\{ {{{10}^{ - 2}},{{10}^{ - 5}},{5^{ - 5}}} \right\}时具有最高的聚类准确率,在ORL数据集上当\lambda \in \left\{ {{{10}^{ - 1}},{5^{ - 1}},{{10}^{ - 2}}} \right\}和\beta \in \left\{ {{5^{ - 3}},{{10}^{ - 5}},{5^{ - 5}}} \right\}时具有较好的聚类准确率,因此本文建议的参数选择为\lambda = {5^{ - 1}}和\beta \in \left\{ {{{10}^{ - 5}},{5^{ - 5}}} \right\}.
3.6 收敛性分析
为证明本文所提算法模型的收敛性,本节在MSRC_V1和WebKB_2views数据集上分析相应的目标函数值和迭代次数的关系. 本文将目标函数值定义为
\text{ }目标函数值=\left(\begin{array}{c}{\Vert {\boldsymbol X}^{\left(v\right)}-{\boldsymbol X}^{\left(v\right)}{\boldsymbol Z}_{k+1}^{\left(v\right)}-{{\boldsymbol{E}}}_{k+1}^{\left(v\right)}\Vert }_{\infty }+\\ {\Vert {\boldsymbol Z}_{k+1}^{\left(v\right)}-{{\boldsymbol{J}}}_{k+1}^{\left(v\right)}\Vert }_{\infty }+\\ {\Vert {\boldsymbol Z}_{k+1}^{\left(v\right)}-{\boldsymbol F}_{k+1}^{\left(v\right)}\Vert }_{\infty }\end{array}\right). (38) 图7(a)(b)分别展示了在MSRC_V1和WebKB_2views数据集上随着迭代次数增加目标函数值的变化情况. 从图7可以看出,目标函数值随迭代次数增加都呈现先下降后稳定的趋势,并且最终趋于0.因此可以得出:ATSVS具有良好的收敛性,在经过一定的迭代次数后可以得到模型的局部最优解.
4. 总 结
本文提出了一种基于{l_{1,2}}范数正则的张量平滑低秩多视角聚类算法ATSVS. ATSVS通过将张量对数行列式函数、{l_{1,2}}范数正则项和{l_{2,1}}范数误差约束项集成到一个模型框架中,通过对模型进行优化更新能学习到一个包含各个视角全局和局部信息以及视角间高阶信息的亲和矩阵,最终通过亲和矩阵获得较好的聚类结果. 此外,本文给出了ATSVS模型迭代优化的公式推导过程,并对模型进行了参数分析和收敛性分析. 为验证算法聚类性能,本文选取了来自单视角和多视角聚类领域的11个对比算法在不同类型的共9个数据集进行实验. 实验结果表明,ATSVS相较于对比算法具有最好的聚类性能,并且能够有效处理来自多个领域的多视角数据的聚类任务,具有广泛的应用范围.
作者贡献声明:钱罗雄设计并实现所提算法,完成实验并撰写论文;陈梅提出研究方向,把握论文创新性;马学艳负责对比实验的执行与参数的调试;张弛指导实验方案的完善及结果分析;张锦宏整理实验图表、修改论文.
http://cvc.cs.yale.edu/cvc/projects/yalefaces/yalefaces.html.http://cvc.cs.yale.edu/cvc/projects/yalefacesB/yalefacesB.html.https://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html.http://archive.ics.uci.edu/ml/datasets/Multiple+Features.https://linqs.soe.ucsc.edu/data.http://mlg.ucd.ie/datasets/bbc.html.http://mlg.ucd.ie/datasets/segment.html. -
表 1 符号与含义
Table 1 Notations and Meaning
符号 含义 符号 含义 {\boldsymbol{x}},{\text{ }}{\boldsymbol{X}},{\text{ }} {\overset{\frown}{{\boldsymbol{X}}}} 向量,矩阵,张量 {\overset{\frown}{{\boldsymbol{Z}}}}(i,:,:) {\overset{\frown}{{\boldsymbol{Z}}}}的第i个水平切面 {\boldsymbol{I}} 单位矩阵 {\overset{\frown}{{\boldsymbol{Z}}}}(:,j,:) {\overset{\frown}{{\boldsymbol{Z}}}}的第j个侧切面 n 数据个数 {\overset{\frown}{{\boldsymbol{Z}}}}(:,:,k);{{\overset{\frown}{{\boldsymbol{Z}}}}^{(k)}} {\overset{\frown}{{\boldsymbol{Z}}}}的第k个正切面 v 第v个视角 {\left\| {\boldsymbol{Z}} \right\|_*} 矩阵{\boldsymbol{Z}}的核范数 V 视角个数 {\left\| {\boldsymbol{Z}} \right\|_{\text{F}}} 矩阵{\boldsymbol{Z}}的Frobenius
范数{d_v} 第v个视角的特征维度 {\left\| {\boldsymbol{Z}} \right\|_\infty } 矩阵{\boldsymbol{Z}}的无穷范数 {{\boldsymbol{X}}^{(v)}} \in {\mathbb{R}^{d \times N}} 第v个视角的特征矩阵 {\left\| {\boldsymbol{Z}} \right\|_{2,1}} 矩阵{\boldsymbol{Z}}的{l_{2,1}}范数 {\overset{\frown}{{\boldsymbol{Z}}}} \in {\mathbb{R}^{n \times V \times n}} 表示张量 {\left\| {\boldsymbol{Z}} \right\|_{1,2}} 矩阵{\boldsymbol{Z}}的{l_{1,2}}范数 {\mathop {\boldsymbol Z} \limits^ \smile}\in {\mathbb{R}^{n \times n \times V}} 表示张量旋转体 {\left\| {{\overset{\frown}{{\boldsymbol{Z}}}}} \right\|_ \circledast } 张量核范数 {\boldsymbol{A}} \in {\mathbb{R}^{n \times n}} 亲和矩阵 {{\overline{\boldsymbol{X}}}} = fft( {\overset{\frown}{\boldsymbol{X}}} ,[],3) {\overset{\frown}{\boldsymbol{X}}} 沿第3维度的
傅里叶变换{{\boldsymbol{E}}^{(v)}} \in {\mathbb{R}^{n \times n}} 噪声矩阵 {\overset{\frown}{{\boldsymbol{X}}}} = ifft({{\overline {\boldsymbol{X}}}},[],3) {{\overline {\boldsymbol{X}}}}沿第3维度的
傅里叶逆变换表 2 数据集描述
Table 2 Description of the Datasets
数据集 类别数 数据量 视角数 Yale 15 165 3 Extended Yale B 10 650 3 WebKB_2views 2 1 051 2 ORL 40 400 4 HW 10 2 000 6 BBC 5 685 4 BBCSport 5 544 2 MSRC_V1 7 210 5 Scene-15 15 4 485 3 表 3 在Yale数据集上的聚类结果(平均值)
Table 3 Clustering Results (Mean) on Yale Dataset
算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.657 0 0.676 9 0.657 0 0.508 5 0.527 5 0.475 4 AWP 0.587 9 0.647 6 0.587 9 0.491 3 0.529 7 0.455 7 CoregSC 0.618 2 0.657 6 0.618 2 0.489 2 0.509 1 0.454 7 MCGC 0.557 6 0.590 0 0.557 6 0.388 8 0.495 8 0.339 8 MVGL 0.624 2 0.671 2 0.630 3 0.497 8 0.545 5 0.462 1 WMSC 0.630 3 0.672 3 0.630 3 0.512 3 0.528 5 0.479 6 GBS 0.654 5 0.673 6 0.660 6 0.480 1 0.562 4 0.441 0 t-SVD-MSC 0.920 6 0.927 4 0.921 2 0.872 6 0.891 3 0.864 1 WTNNM 0.941 2 0.953 9 0.943 0 0.920 1 0.933 0 0.914 8 LSLMC 0.706 7 0.730 2 0.706 7 0.570 2 0.598 5 0.540 9 LSGMC 0.460 6 0.502 5 0.497 0 0.288 5 0.277 4 0.240 4 ATSVS-noL12
(本文)0.971 5 0.980 6 0.973 3 0.961 5 0.975 0 0.958 9 ATSVS(本文) 0.997 0 0.996 1 0.997 0 0.993 6 0.993 9 0.993 2 注:黑体数值表示最优结果. 表 4 在Extended Yale B数据集上的聚类结果(平均值)
Table 4 Clustering Results (Mean) on Extended Yale B Dataset
算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.631 1 0.664 8 0.632 6 0.498 6 0.628 3 0.430 9 AWP 0.307 7 0.329 3 0.320 0 0.255 5 0.303 1 0.159 6 CoregSC 0.398 6 0.387 4 0.410 8 0.270 4 0.314 9 0.177 9 MCGC 0.295 4 0.287 0 0.298 5 0.218 0 0.336 0 0.097 8 MVGL 0.347 7 0.320 1 0.350 8 0.212 8 0.327 9 0.091 9 WMSC 0.381 7 0.375 1 0.395 5 0.261 7 0.304 2 0.168 3 GBS 0.433 8 0.416 3 0.436 9 0.265 1 0.378 2 0.157 2 t-SVD-MSC 0.547 1 0.566 4 0.549 7 0.444 7 0.470 1 0.380 4 WTNNM 0.585 4 0.596 1 0.587 5 0.468 0 0.498 0 0.405 9 LSLMC 0.440 0 0.431 6 0.441 5 0.304 3 0.380 0 0.211 0 LSGMC 0.966 2 0.930 3 0.966 2 0.931 0 0.928 3 0.923 5 ATSVS-noL12
(本文)0.961 1 0.939 3 0.961 1 0.925 5 0.927 6 0.917 3 ATSVS(本文) 0.976 6 0.962 4 0.976 6 0.954 6 0.956 4 0.949 6 注:黑体数值表示最优结果. 表 5 在WebKB_2views数据集上的聚类结果(平均值)
Table 5 Clustering Results (Mean) on WebKB_2views Dataset
算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.833 5 0.161 7 0.833 5 0.821 7 0.973 5 0.256 2 AWP 0.815 4 0.089 8 0.815 4 0.806 5 0.954 3 0.194 5 CoregSC 0.819 2 0.100 6 0.819 2 0.808 3 0.950 3 0.214 2 MCGC 0.814 5 0.087 1 0.814 5 0.805 9 0.954 7 0.190 2 MVGL 0.820 2 0.118 4 0.820 2 0.813 4 0.978 6 0.193 1 WMSC 0.891 5 0.352 6 0.891 5 0.859 8 0.902 8 0.549 3 GBS 0.776 4 0.001 0 0.781 2 0.786 7 0.974 6 0.010 2 t-SVD-MSC 0.782 1 0.002 8 0.782 1 0.794 0 0.999 4 0.004 9 WTNNM 0.782 1 0.002 8 0.782 1 0.794 0 0.999 4 0.004 9 LSLMC 0.829 7 0.131 4 0.829 7 0.813 7 0.939 3 0.267 4 LSGMC 0.780 2 0.000 4 0.999 0 0.792 0 0.657 5 -0.001 4 ATSVS-noL12
(本文)0.949 6 0.679 1 0.949 6 0.924 2 0.887 9 0.794 5 ATSVS(本文) 0.980 0 0.830 9 0.980 0 0.969 7 0.953 7 0.914 2 注:黑体数值表示最优结果. 表 6 在ORL数据集上的聚类结果(平均值)
Table 6 Clustering Results (Mean) on ORL Dataset
算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.819 3 0.902 3 0.839 3 0.751 9 0.776 3 0.746 0 AWP 0.755 0 0.872 8 0.777 5 0.696 1 0.770 0 0.688 4 CoregSC 0.813 8 0.899 4 0.836 0 0.747 3 0.784 8 0.741 1 MCGC 0.590 0 0.727 5 0.660 0 0.245 5 0.762 8 0.215 8 MVGL 0.707 5 0.833 7 0.772 5 0.414 8 0.817 8 0.394 4 WMSC 0.823 5 0.902 5 0.847 0 0.758 7 0.791 7 0.752 9 GBS 0.632 5 0.803 5 0.715 0 0.359 9 0.801 1 0.336 7 t-SVD-MSC 0.966 0 0.989 9 0.975 0 0.965 6 0.984 8 0.964 8 WTNNM 0.979 3 0.994 4 0.985 0 0.980 0 0.992 5 0.979 5 LSLMC 0.820 5 0.910 6 0.849 5 0.760 9 0.804 8 0.755 1 LSGMC 0.782 5 0.880 9 0.807 5 0.694 2 0.656 0 0.686 7 ATSVS-noL12
(本文)0.966 0 0.990 6 0.975 0 0.967 3 0.988 4 0.966 5 ATSVS(本文) 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 注:黑体数值表示最优结果. 表 7 在HW数据集上的聚类结果(平均值)
Table 7 Clustering Results (Mean) on HW Dataset
算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.968 5 0.927 5 0.968 5 0.938 2 0.938 4 0.931 3 AWP 0.879 5 0.890 8 0.880 0 0.869 8 0.954 1 0.854 0 CoregSC 0.924 4 0.890 1 0.924 4 0.870 7 0.872 3 0.856 4 MCGC 0.591 5 0.701 3 0.593 0 0.642 9 0.968 4 0.588 1 MVGL 0.853 0 0.889 9 0.880 5 0.849 3 0.916 5 0.831 3 WMSC 0.841 4 0.859 5 0.866 9 0.829 3 0.887 7 0.809 1 GBS 0.881 0 0.892 3 0.881 0 0.865 4 0.900 8 0.849 9 t-SVD-MSC 0.997 5 0.993 5 0.997 5 0.995 0 0.995 0 0.994 5 WTNNM 0.995 0 0.987 2 0.995 0 0.990 0 0.990 1 0.988 9 LSLMC 0.968 5 0.931 1 0.968 5 0.938 2 0.938 6 0.931 4 LSGMC 0.977 5 0.947 4 0.977 5 0.955 6 0.955 4 0.950 7 ATSVS-noL12
(本文)0.999 5 0.998 6 0.999 5 0.999 0 0.999 0 0.998 9 ATSVS(本文) 0.999 5 0.998 6 0.999 5 0.999 0 0.999 0 0.998 9 注:黑体数值表示最优结果. 表 8 在BBC数据集上的聚类结果(平均值)
Table 8 Clustering Results (Mean) on BBC Dataset
算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.439 7 0.230 2 0.496 4 0.354 8 0.494 4 0.103 9 AWP 0.389 8 0.199 3 0.458 4 0.344 5 0.551 8 0.032 3 CoregSC 0.407 7 0.234 1 0.492 4 0.341 0 0.468 4 0.060 8 MCGC 0.327 0 0.005 2 0.331 4 0.378 4 0.986 3 −0.001 3 MVGL 0.346 0 0.039 2 0.365 0 0.374 5 0.915 4 0.002 2 WMSC 0.423 5 0.238 3 0.504 4 0.355 8 0.493 5 0.080 3 GBS 0.693 4 0.485 2 0.693 4 0.633 3 0.860 0 0.478 9 t-SVD-MSC 0.937 2 0.861 6 0.937 2 0.893 6 0.863 6 0.862 4 WTNNM 0.902 9 0.813 7 0.902 9 0.833 2 0.782 7 0.786 3 LSLMC 0.849 6 0.680 7 0.849 6 0.783 1 0.778 7 0.717 2 LSGMC 0.890 5 0.754 3 0.890 5 0.833 2 0.851 7 0.783 5 ATSVS-noL12
(本文)0.992 7 0.974 9 0.992 7 0.986 7 0.980 7 0.982 6 ATSVS(本文) 0.994 2 0.980 7 0.986 2 0.989 4 0.994 2 0.984 7 注:黑体数值表示最优结果. 表 9 在BBCSport数据集上的聚类结果(平均值)
Table 9 Clustering Results (Mean) on BBCSport Dataset
算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.560 7 0.427 1 0.652 6 0.463 6 0.508 1 0.275 6 AWP 0.634 2 0.442 6 0.704 0 0.563 6 0.743 5 0.379 9 CoregSC 0.632 4 0.464 5 0.742 6 0.534 0 0.507 5 0.397 8 MCGC 0.404 4 0.109 0 0.433 8 0.391 4 0.871 5 0.034 1 MVGL 0.409 9 0.097 8 0.432 0 0.399 2 0.913 5 0.042 1 WMSC 0.610 3 0.471 0 0.680 5 0.519 0 0.528 1 0.364 9 GBS 0.807 0 0.722 6 0.843 8 0.794 3 0.875 3 0.721 8 t-SVD-MSC 0.965 1 0.896 7 0.965 1 0.933 0 0.915 2 0.912 5 WTNNM 0.973 5 0.916 8 0.973 5 0.948 8 0.934 4 0.933 1 LSLMC 0.944 9 0.854 4 0.944 9 0.886 3 0.878 7 0.851 1 LSGMC 0.935 7 0.849 1 0.935 7 0.862 1 0.870 3 0.819 4 ATSVS-noL12
(本文)0.970 6 0.915 4 0.970 6 0.939 8 0.925 5 0.921 3 ATSVS(本文) 0.985 3 0.955 1 0.985 3 0.976 6 0.970 6 0.969 4 注:黑体数值表示最优结果. 表 10 在MSRC_V1数据集上的聚类结果(平均值)
Table 10 Clustering Results (Mean) on MSRC_V1 Dataset
算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.761 9 0.642 5 0.761 9 0.609 8 0.634 5 0.544 1 AWP 0.742 9 0.671 2 0.747 6 0.676 3 0.783 3 0.615 7 CoregSC 0.804 8 0.719 5 0.804 8 0.694 7 0.704 8 0.644 7 MCGC 0.742 9 0.632 5 0.747 6 0.619 1 0.715 9 0.547 8 MVGL 0.747 6 0.721 4 0.776 2 0.673 6 0.792 1 0.611 7 WMSC 0.761 9 0.712 4 0.800 0 0.686 7 0.709 0 0.634 4 GBS 0.895 2 0.816 4 0.895 2 0.799 7 0.814 4 0.766 8 t-SVD-MSC 0.919 0 0.870 0 0.919 0 0.856 0 0.861 1 0.832 7 WTNNM 0.990 5 0.978 3 0.990 5 0.980 5 0.981 0 0.977 3 LSLMC 0.795 2 0.695 0 0.795 2 0.664 9 0.674 9 0.610 0 LSGMC 0.833 3 0.728 5 0.833 3 0.709 3 0.700 9 0.661 8 ATSVS-noL12
(本文)0.995 2 0.989 2 0.995 2 0.990 3 0.990 5 0.988 8 ATSVS(本文) 0.995 2 0.989 2 0.995 2 0.990 3 0.990 5 0.988 8 注:黑体数值表示最优结果. 表 11 在Scene-15数据集上的聚类结果(平均值)
Table 11 Clustering Results (Mean) on Scene-15 Dataset
算法 Accuracy NMI Purity F-score Recall ARI SCbest 0.361 9 0.389 5 0.414 0 0.268 4 0.276 1 0.212 5 AWP 0.366 3 0.356 4 0.402 0 0.249 6 0.273 5 0.188 6 CoregSC 0.410 9 0.395 0 0.457 7 0.289 3 0.293 2 0.235 8 MCGC 0.156 3 0.103 1 0.158 8 0.154 2 0.853 6 0.032 6 MVGL 0.196 2 0.181 0 0.210 9 0.188 3 0.693 9 0.078 1 WMSC 0.432 6 0.434 0 0.466 9 0.314 4 0.323 3 0.261 9 GBS 0.218 5 0.151 2 0.836 6 0.147 0 0.077 8 0.018 0 t-SVD-MSC 0.763 8 0.766 6 0.815 2 0.707 3 0.716 7 0.685 3 WTNNM 0.680 0 0.456 2 0.534 2 0.374 5 0.372 4 0.328 7 LSLMC 0.533 6 0.575 0 0.602 0 0.457 5 0.472 2 0.430 5 LSGMC 0.473 6 0.480 9 0.534 2 0.370 3 0.354 0 0.321 2 ATSVS-noL12(本文) 0.861 1 0.853 2 0.890 5 0.825 4 0.829 9 0.812 3 ATSVS(本文) 0.929 8 0.887 8 0.871 7 0.880 6 0.882 4 0.878 8 注:黑体数值表示最优结果. -
[1] 刘金花,王洋,钱宇华. 基于谱结构融合的多视图聚类[J]. 计算机研究与发展,2022,59(4):922−935 doi: 10.7544/issn1000-1239.20200875 Liu Jinhua, Wang Yang, Qian Yuhua. Multi-view clustering with spectral structure fusion[J]. Journal of Computer Research and Development, 2022, 59(4): 922−935 (in Chinese) doi: 10.7544/issn1000-1239.20200875
[2] 姜火文,曾国荪,胡克坤. 一种遗传算法实现的图聚类匿名隐私保护方法[J]. 计算机研究与发展,2016,59(10):2354−2364 doi: 10.7544/issn1000-1239.2016.20160435 Jiang Huowen, Zeng Guosun, Hu Kekun. A graph-clustering anonymity method implemented by genetic algorithm for privacy-preserving[J]. Journal of Computer Research and Development, 2016, 59(10): 2354−2364 (in Chinese) doi: 10.7544/issn1000-1239.2016.20160435
[3] 刘仁伟,岳林. 基于双谱熵和聚类分析的转子系统故障诊断 [J]. 振动测试与诊断,2023,43(1):188−193+205 Liu Renwei, Yue Lin. Rotor system fault diagnosis based on bispectrum entropy and clustering analysis [J]. Journal of Vibration, Measurement & Diagnosis, 2023, 43(1): 188−193+205 (in Chinese)
[4] 张航. 基于模糊聚类与卷积神经网络的图像分割方法研究及其应用 [D]. 长沙:湖南大学,2022 Zhang Hang. Fuzzy clustering and convolutional neural networks-based image segmentation algorithm research and its application [D]. Changsha: Hunan University, 2022 (in Chinese)
[5] Chen Mei,Chen Yongxu,Zhu Hongyu,et al. Analysis of pollutants transport in heavy air pollution processes using a new complex-network-based model [J]. Atmospheric Environment,2023,292:119395
[6] 胡世哲,娄铮铮,王若彬,等. 一种双重加权的多视角聚类方法[J]. 计算机学报,2020,43(9):1708−1720 doi: 10.11897/SP.J.1016.2020.01708 Hu Shizhe, Lou Zhengzheng, Wang Ruobin, et al. Dual-weighted multi-view clustering[J]. Chinese Journal of Computers, 2020, 43(9): 1708−1720 (in Chinese) doi: 10.11897/SP.J.1016.2020.01708
[7] 程士卿,郝问裕,李晨,等. 低秩张量分解的多视角谱聚类算法[J]. 西安交通大学学报,2020,54(3):119−125,133 Cheng Shiqing, Hao Wenyu, Li Chen, et al. Multi-view clustering by low-rank tensor decomposition[J]. Journal of Xi’an Jiaotong University, 2020, 54(3): 119−125,133 (in Chinese)
[8] Gao Hongchang, Nie Feiping, Li Xuelong, et al. Multi-view subspace clustering[C]//Proc of the IEEE Int Conf on Computer Vision. Piscataway, NJ: IEEE, 2015: 4238−4246
[9] Zhang Changqing, Hu Qinghua, Fu Huazhu, et al. Latent multi-view subspace clustering[C]//Proc of the IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2017: 4279−4287
[10] Zhou Yiyang, Zheng Qinghai, Wang Yifei, et al. MCoCo: Multi-level consistency collaborative multi-view clustering[J]. Expert Systems with Applications, 2024, 238: 121976
[11] Nie Feiping,Shi Shaojun,Li Xuelong. Auto-weighted multi-view co-clustering via fast matrix factorization [J]. Pattern Recognition,2020,102:107207
[12] Zhang Changqing,Fu Huazhu,Liu Si,et al. Low-rank tensor constrained multiview subspace clustering [C] //Proc of the IEEE Int Conf on Computer Vision. Piscataway,NJ:IEEE,2015:1582−1590
[13] Xie Yuan,Tao Dacheng,Zhang Wensheng,et al. On unifying multi-view self-representations for clustering by tensor multi-rank minimization [J]. International Journal of Computer Vision,2018,126:1157−1179
[14] Gao Quanxue,Xia Wei,Wan Zhizhen,et al. Tensor-SVD based graph learning for multi-view subspace clustering [C] //Proc of the AAAI Conf on Artificial Intelligence. Palo Alto, CA:AAAI,2020:3930−3937
[15] Xia Wei, Zhang Xiangdong, Gao Quanxue, et al. Multiview subspace clustering by an enhanced tensor nuclear norm[J]. IEEE Transactions on Cybernetics, 2021, 52(9): 8962−8975
[16] Brbić M,Kopriva I. Multi-view low-rank sparse subspace clustering [J]. Pattern Recognition,2018,73:247−258
[17] Fu Lele,Yang Jinghua,Chen Chuan,et al. Low-rank tensor approximation with local structure for multi-view intrinsic subspace clustering [J]. Information Sciences,2022,606:877−891
[18] Zhao Peng,Wu Hongjie,Huang Shudong. Multi-view graph clustering by adaptive manifold learning [J]. Mathematics,2022,10(11):1821
[19] Kilmer M E, Braman K, Hao Ning, et al. Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging[J]. SIAM Journal on Matrix Analysis and Applications, 2013, 34(1): 148−172 doi: 10.1137/110837711
[20] Zhang Zemin, Ely G, Aeron S, et al. Novel methods for multilinear data completion and de-noising based on tensor-SVD[C]//Proc of the IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2014: 3842−3849
[21] Kang Zhao,Peng Chong,Cheng Jie,et al. Logdet rank minimization with application to subspace clustering [J]. Computational Intelligence and Neuroscience,2015,2015:68
[22] Kang Zhao, Peng Chong, Cheng Qiang. Robust subspace clustering via smoothed rank approximation[J]. IEEE Signal Processing Letters, 2015, 22(11): 2088−2092 doi: 10.1109/LSP.2015.2460737
[23] Ming Di, Ding C. Robust flexible feature selection via exclusive L21 regularization [C] //Proc of the 28th Int Joint Conf on Artificial Intelligence. San Francisco: Margan Kaufmann, 2019: 3158−3164
[24] Kong Deguang, Fujimaki R, Liu Ji, et al. Exclusive feature learning on arbitrary structures via l1, 2-norm [C] //Proc of the 27th Int Conf on Neural Information Processing Systems. Cambridge, MA: MIT, 2014: 1655−1663
[25] Ming Di,Ding C,Nie Feiping. A probabilistic derivation of LASSO and L12-norm feature selections [C] //Proc the AAAI Conf on Artificial Intelligence. Palo Alto ,CA:AAAI,2019:4586−4593
[26] Xie Deyan,Gao Quanxue,Yang Ming. Enhanced tensor low-rank representation learning for multi-view clustering [J]. Neural Networks,2023,161:93−104
[27] Von Luxburg U. A tutorial on spectral clustering [J]. Statistics and Computing,2007,17:395−416
[28] Nie Feiping, Tian Lai, Li Xuelong. Multiview clustering via adaptively weighted procrustes [C] //Proc the 24th ACM SIGKDD Int Conf on Knowledge Discovery & Data Mining. New York: ACM, 2018: 2022−2030
[29] Kumar A, Rai P, Daume H. Co-regularized multi-view spectral clustering [C] //Proc of the 25th Int Conf on Neural Information Processing Systems. Cambridge, MA: MIT, 2011: 1413−1421
[30] Zhan Kun, Nie Feiping, Wang Jing, et al. Multiview consensus graph clustering[J]. IEEE Transactions on Image Processing, 2018, 28(3): 1261−1270
[31] Zhan Kun, Zhang Changqing, Guan Junpeng, et al. Graph learning for multiview clustering[J]. IEEE Transactions on Cybernetics, 2017, 48(10): 2887−2895
[32] Zong Linlin,Zhang Xiaochao,Liu Xinyue,et al. Weighted multi-view spectral clustering based on spectral perturbation [C] //Proc of the AAAI Conf on Artificial Intelligence. Palo Alto ,CA:AAAI,2018:2887−2895
[33] Wang Hao,Yang Yan,Liu Bing,et al. A study of graph-based system for multi-view clustering [J]. Knowledge-Based Systems,2019,163:1009−1019
[34] Xie Deyan,Xia Wei,Wang Qianqian,et al. Multi-view clustering by joint manifold learning and tensor nuclear norm [J]. Neurocomputing,2020,380:105−114
[35] Lan Wei, Yang Tianchuan, Chen Qingfeng, et al. Multiview subspace clustering via low-rank symmetric affinity graph [J/OL]. IEEE Transactions on Neural Networks and Learning Systems, [2024-05-16]. https://ieeexplore.ieee.org/abstract/document/10089426
[36] Van der Maaten L, Hinton G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research, 2008, 9(11): 2579−2605