双重结构的最小二乘回归子空间聚类算法

doi:10.13232/j.cnki.jnju.2022.06.013

双重结构的最小二乘回归子空间聚类算法

卢桂馥^,, 汤荣, 姚亮

安徽工程大学计算机与信息学院，芜湖，241000

Double structure least squares regression subspace clustering

Lu Guifu^,, Tang Rong, Yao Liang

School of Computer and Information，AnHui Polytechnic University, Wuhu，241000，China

通讯作者: E-mail：lu-guifu@ahpu.edu.cn

收稿日期: 2022-07-04

基金资助:

国家自然科学基金. 61976005
安徽省自然科学基金. 1908085MF183

Received: 2022-07-04

摘要

最小二乘回归（Least Square Regression，LSR）算法是一种流行的子空间聚类方法，在处理计算机视觉和机器学习的相关问题中的应用十分普遍.然而，当数据含有噪声时，其求得的亲和矩阵不是块对角化的，还存在一定的噪声，这使亲和矩阵不够鲁棒可靠，因而降低了算法的聚类性能.为了解决以上不足，提出一种双重结构的最小二乘回归子空间聚类算法（Double Structure Least Squares Regression Subspace Clustering，DSLSR）.首先对原始数据实施LSR算法，由于其生成的亲和矩阵往往不是块对角矩阵且含有噪声，需要对求得的亲和矩阵再次实施LSR算法来去除亲和矩阵中的噪声，使亲和矩阵更干净可靠，从而提升算法的聚类性能.最后，把两次LSR过程纳入一个统一的算法框架，设计一个统一的目标函数.此外，还采取了增广拉格朗日乘子方法对目标函数进行优化求解.在一些数据集上的实验证实，DSLSR算法比现有算法的性能更卓越.

关键词： 子空间聚类 ; 目标函数 ; 最小二乘回归 ; 亲和矩阵

Abstract

The Least Square Regression (LSR) algorithm is a popular subspace clustering approach，which is widely used in dealing with problems related to computer vision and machine learning. However，when the data is noisy，the affinity matrix is not block diagonal with some noise，which makes the affinity matrix not robust enough. To resolve the above issues，this paper researches a double structure least squares regression subspace clustering (DSLSR). In DSLSR，the LSR algorithm is first conducted on the original data. Because the original data contains noise，the generated affinity matrix is often not block diagonal matrix and contains noise. Therefore，it is necessary to implement LSR again on the generated affinity matrix to remove the noise and make the affinity matrix cleaner and more reliable，which can improve the clustering performance of the algorithm. Finally，the two LSR processes are incorporated into a unified algorithm framework，and a unified objective function is designed. In addition，a useful approach based on augmented Lagrange multiplier is employed to optimize the objective function. Experiments on some datasets exhibit that the DSLSR acquires better property than existing algorithms.

Keywords： subspace clustering ; objective function ; least squares regression ; affinity matrix

PDF (1281KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

卢桂馥, 汤荣, 姚亮. 双重结构的最小二乘回归子空间聚类算法. 南京大学学报（自然科学）[J], 2022, 58(6): 1050-1058 doi:10.13232/j.cnki.jnju.2022.06.013

Lu Guifu, Tang Rong, Yao Liang. Double structure least squares regression subspace clustering. Journal of nanjing University[J], 2022, 58(6): 1050-1058 doi:10.13232/j.cnki.jnju.2022.06.013

大数据潮流中的数据基本都是高维度的，在处理时其高维性质往往是研究进程中的障碍^［1-2］，为此，研究人员提出基于子空间的表示算法来解决这一难题^［3-4］.子空间表示的方法十分流行的原因是其算法模型简单^［5-6］，但现实中仅用一个子空间表示一组冗杂的高维数据有困难，所以人们提出一种更加符合实际的假设，即高维数据通常存在于多个子空间的并集上，这就引出了子空间分割或子空间聚类的问题.例如：对于一个三维数据，它实际上由平面数据和直线数据组成，则在低维子空间（平面或直线）中，该数据的本质特征能更好地被体现，这有利于数据的聚类.过去的20多年里，研究人员探索了许多子空间聚类的相关方法，这些方法可以分为四类：迭代方法^［7-8］、代数方法^［9-10］、基于谱聚类方法^［11-12］和统计方法^［13-14］.

谱聚类方法中自表达的子空间聚类方法是最有代表性的，如低秩表示法（Low⁃Rank Representation，LRR）^［15］、稀疏子空间聚类（Sparse Subspace Clustering，SSC）^{［11，16］}、最小二乘回归子空间聚类（Least Squares Regression，LSR）^［17］等.SSC的主要思想是使亲和矩阵尽量稀疏，它的局限性在于亲和矩阵可能过于稀疏，使SSC不能对原数据进行正确的划分.LRR试图考虑数据的全局性，它不再寻求最稀疏表达，而是把方向转到亲和矩阵的秩上面.LSR采用Frobenius范数来规范亲和矩阵，使数据能更好地聚合到一起，并且改善了噪音的鲁棒性.

李海洋和王恒远^［18］提出一种基于TL1范数的聚类方法（Subspace Clustering Method Based on TL1 Norm Constraints），使用TL1范数使系数矩阵更加稀疏并解决了噪声的鲁棒性问题.李波等^［19］提出基于局部图拉普拉斯约束的鲁棒低秩表示聚类方法（Robust Low Rank Subspace Clustering Based on Local Graph Laplace Constraint），通过图像局部相似性的约束，使矩阵成分块对角，并加强了亲和矩阵的稀疏性.Zheng et al^［20］提出图正则化稀疏编码方法（Graph Regularized Sparse Coding for Image Representation，GraphSC），很好地体现了数据的几何构造.依据GraphSC的研究，Long et al^［21］提出转移稀疏编码算法（Transfer Sparse Coding for Robust Image Representation，TSC），该算法习得的稀疏亲和矩阵具有鲁棒性，可以提高交叉分布图像的分类准确性.Nie et al^［22］提出自适应邻域聚类与投影聚类（Clustering and Projected Clustering with Adaptive Neighbors，CAN），首先通过自动分配的最优邻居来学习样本的亲和矩阵，然后采用秩约束来规范亲和矩阵的拉普拉斯矩阵，使数据中的每一个连通分量都能很好地对应一个类.Xu et al^［23］提出缩放单纯型表示（Scaled Simplex Representation，SSR），通过非负约束亲和矩阵并将非负的亲和矩阵的每个列向量和约束为 $s (0 < s < 1)$ ，不仅保证数据的相关结构，而且可以通过调整s来寻找聚类的最佳性能.

然而，上述方法中，只有在数据不含噪声时，其求得的亲和矩阵才是块对角化的，而现实中的数据往往含有噪声，使其亲和矩阵的块对角特性不明显，并且存在噪声.为此，本文提出具有双重结构的最小二乘回归子空间聚类（Double Structure Least Squares Subspace Clustering，DSLSR）算法，其双重结构在于：首先，对原始数据实施LSR算法；然后，对LSR算法求得的亲和矩阵再次实施LSR算法来去除亲和矩阵中的噪声，使亲和矩阵更干净可靠；最后，把两次LSR过程纳入一个统一的算法框架，设计一个统一的目标函数.此外，本文还利用增广拉格朗日乘子法（Augmented Lagrangian Multiplier，ALM）^［24-25］来优化求解DSLSR，并通过在数据集上的实验验证了DSLSR算法性能的卓越性和优异性.

本文的新颖性和贡献：

（1）提出一种具有双重结构的子空间聚类算法DSLSR，通过两次LSR使亲和矩阵更干净可靠，从而提升了算法的聚类性能，并设计了一个统一的目标函数.

（2）对于DSLSR的目标函数，采用ALM来高效优化求解，实验进一步证明DSLSR模型在子空间聚类问题上有较好的效果.

1 相关工作

给定一组数据，将其按照列排序并作为矩阵 $X$ 的列向量，即 $X = [x_{1}, x_{2}, x_{3}, \dots, x_{n}] \in R^{m \times n}$ ，其中，m是数据的维数，n是数据的样本数.对于矩阵 $X$ ， $X^{T}$ 表示矩阵的转置， $t r (X)$ 表示矩阵的秩.假设所有数据都来自k个相互正交的子空间，如 $[X_{1 k_{1}}, X_{2 k_{1}}, X_{3 k_{2}}, \dots, X_{n k}]$ ，则第 $k_{j}$ 类图像归属于子空间 $S_{j}$ （ $j = 1,2, 3, \dots, k$ ）.根据数据的特性精确地把每幅图像 $X_{i}$ 划分到它相应的种类 $S_{j}$ 中是聚类的目的.

1.1　低秩表示(LRR)

LRR通过核范数来规范亲和矩阵，促使亲和矩阵尽量低秩.给定一组数据 $X = [x_{1}, x_{2}, x_{3}, \dots, x_{n}]$ ，LRR的亲和矩阵可由式（1）求得：

\underset{Z}{m i n} {‖Z‖}_{*}, s . t . X = X Z

(1)

其中， $Z \in R^{n \times n}$ 为亲和矩阵， ${‖Z‖}_{*}$ 是矩阵 $Z$ 的核范数， ${‖Z‖}_{*}$ 与 $Z$ 矩阵奇异值的和等价.

数据中有噪声时LRR重述为：

\underset{Z}{m i n} {‖E_{X}‖}_{2,1} + λ {‖Z‖}_{*}, s . t . X = X Z + E_{X}

(2)

其中， $E_{X} \in R^{m \times n}$ 是 $X$ 的重构误差， $λ$ 是平衡误差矩阵和亲和矩阵的正则化参数.学习到的亲和矩阵 $Z$ 用于构建聚类方法需要的邻接矩阵 $W \in R^{n \times n} =$

$\frac{1}{2} (|Z| + |Z^{T}|)$ ，然后通过 $W$ 矩阵来得到聚类结果.

1.2　最小二乘回归子空间聚类算法(LSR)　LSR采用Frobenius范数来规范亲和矩阵，使亲和矩阵具有分组效应.给定一组数据 $X = [x_{1}, x_{2}, x_{3},$

$\dots, x_{n}]$ ，LSR的表达式如下：

\underset{Z}{m i n} {‖Z‖}_{F}^{2}, s . t . X = X Z

(3)

其中， ${‖Z‖}_{F}$ 表示系数矩阵 $Z$ 的Frobenius范数：

{‖Z‖}_{F} = {(\sum_{i = 1}^{n} \sum_{j = 1}^{n} {Z_{i j}}^{2})}^{\frac{1}{2}}

(4)

其中， $Z_{i j}$ 表示系数矩阵 $Z$ 的第i行第j列对应的值.

当数据含杂噪声时，LSR可以表示为：

\underset{Z}{m i n} {‖E_{X}‖}_{F}^{2} + λ {‖Z‖}_{F}^{2}, s . t . X = X Z + E_{X}

(5)

其中， $λ$ 为正则化参数，可以平衡式（5）中的两项.解析解 $Z = {(X^{T} X + λ I)}^{- 1} X^{T} X$ ， $I$ 为单位矩阵.然后按照LRR中构建 $W$ 矩阵的方法来实现聚类.

2 双重结构的最小二乘回归子空间聚类算法及优化

2.1　双重结构的最小二乘回归子空间聚类算法(DSLSR)

LSR作为一种谱聚类算法，它通过Frobenius范数来约束亲和矩阵，虽然可以将数据高度地聚合到一起，但由于数据本身含有噪音，所以LSR求得的亲和矩阵也伴随着噪音.为此，本文提出一种新的双重结构的子空间聚类算法.

首先，利用式（3）得到的亲和矩阵Z，继续对亲和矩阵去除噪音，目标函数如下：

\underset{C}{m i n} {‖C‖}_{F}^{2}, s . t . Z = Z C

(6)

其中， $C \in R^{n \times n}$ 为干净的亲和矩阵，当数据带有噪声时，其表示为：

\underset{C}{m i n} {‖E_{Z}‖}_{F}^{2} + λ {‖C‖}_{F}^{2}, s . t . Z = Z C + E_{Z}

(7)

然后，将式（5）和式（7）纳入同一个框架，得到的目标函数为：

\begin{array}{l} \underset{C}{m i n} {‖E_{X}‖}_{F}^{2} + λ_{1} {‖E_{Z}‖}_{F}^{2} + λ_{2} {‖C‖}_{F}^{2} \\ s . t . X = X Z + E_{X}, Z = Z C + E_{Z} \end{array}

(8)

其中， $E_{X} \in R^{n \times n}$ 和 $E_{Z} \in R^{n \times n}$ 分别是 $X$ 和 $Z$ 的重构系数误差， $λ_{1}$ 和 $λ_{2}$ 是平衡参数.

最后，用习得的干净的亲和矩阵 $C$ 来构造谱聚类需要的邻接矩阵 $W = \frac{1}{2} (|C| + |C^{T}|)$ ，并通过 $W$ 矩阵来得到聚类结果.

2.2　优化方案

详细描述式（8）的优化过程.固定其他变量，只改变 $Z, C, E_{Z} 和 E_{X}$ 中的一个变量，则每个变量的子问题都是凸优化问题，因此，可以采取基于ALM的交替方向最小化方法来有效地求解目标问题.式（8）对应的ALM问题如下：

\begin{array}{l} L (E_{X}, E_{Z}, C, Z, Y_{1}, Y_{2}) = \\ {‖E_{X}‖}_{F}^{2} + λ_{1} {‖E_{Z}‖}_{F}^{2} + λ_{2} {‖C‖}_{F}^{2} + \\ 〈Y_{1}, X - X Z - E_{X}〉 + \frac{μ}{2} {‖X - X Z - E_{X}‖}_{F}^{2} + \\ 〈Y_{2}, Z - Z C - E_{Z}〉 + \frac{μ}{2} {‖Z - Z C - E_{Z}‖}_{F}^{2} \end{array}

(9)

其中， $Y_{1} \in R^{m \times n} 和 Y_{2} \in R^{n \times n}$ 是拉普拉斯乘数， $μ$ 表示一个正的自适应惩罚参数， $〈A, B〉$ 表示 $A^{T} B$ 的迹.

由于本文采用了交替方向最小化策略来最小化ALM问题，所以问题（9）可以被分解成多个子问题，且这些子问题是凸的，可以有效地优化.

2.2.1　更新 $E_{X}$

固定除 $E_{X}$ 外的所有变量，优化以下问题：

\begin{array}{l} \underset{E_{X}}{m i n} {‖E_{X}‖}_{F}^{2} + 〈Y_{1}, X - X Z - E_{X}〉 + \\ \frac{μ}{2} {‖X - X Z - E_{X}‖}_{F}^{2} \end{array}

(10)

式（10）可化为：

\begin{array}{l} \underset{E_{X}}{m i n} t r (E_{X}^{T} E_{X}) - Y_{1}^{T} E_{X} + \frac{μ}{2} t r [- E_{X}^{T} (X - X Z) + \\ E_{X}^{T} E_{X} - (X^{T} - Z^{T} X^{T}) E_{X}] \end{array}

(11)

令式（11）对 $E_{X}$ 的偏导为0，得出 $E_{X}$ 如下：

E_{X} = \frac{[Y_{1} + μ (X - X Z)]}{2 + μ}

(12)

2.2.2　更新 $E_{Z}$

固定除 $E_{Z}$ 的所有变量，优化以下问题：

\begin{array}{l} \underset{E_{Z}}{m i n} λ_{1} {‖E_{Z}‖}_{F}^{2} + 〈Y_{2}, Z - Z C - E_{Z}〉 + \\ \frac{μ}{2} {‖Z - Z C - E_{Z}‖}_{F}^{2} \end{array}

(13)

式（13）可化为下式：

\begin{array}{l} λ_{1} t r (E_{Z}^{T} E_{Z}) - Y_{2}^{T} E_{Z} + \frac{μ}{2} t r [- (Z^{T} - C^{T} Z^{T}) E_{Z} + \\ E_{Z}^{T} E_{Z} - E_{Z}^{T} (Z - Z C)] \end{array}

(14)

令式（14）对 $E_{Z}$ 的偏导等于0，得出 $E_{Z}$ 如下：

E_{Z} = \frac{Y_{2} + μ (Z - Z C)}{2 λ + μ}

(15)

2.2.3　更新 $Z$

当其他变量固定时，关于 $Z$ 的子问题可以写成如下形式：

\begin{array}{l} \underset{Z}{m i n} 〈Y_{1}, X - X Z - E_{X}〉 + \frac{μ}{2} {‖X - X Z - E_{X}‖}_{F}^{2} + \\ 〈Y_{2}, Z - Z C - E_{Z}〉 + \frac{μ}{2} {‖Z - Z C - E_{Z}‖}_{F}^{2} \end{array}

(16)

上式对 $Z$ 求偏导并令其等于0，可以得出以下等式，该方程的解是这个子问题的优化：

T_{A} * Z + Z * T_{B} = T_{C}

(17)

其中， $T_{A}, T_{B} 和 T_{C}$ 的表达式如下：

\begin{array}{l} T_{A} = X^{T} X + I \\ T_{B} = C C^{T} - C - C^{T} \\ T_{C} = X^{T} X - X^{T} E_{X} + E_{Z} - E_{Z} C^{T} + \\ \frac{1}{μ} X^{T} Y_{1} + \frac{1}{μ} (Y_{2} C^{T} - Y_{2}) \end{array}

(18)

式（17）是一个Sylvester方程，其求解方法可以参考文献［26］.

2.2.4　更新 $C$

当其他变量固定时，关于 $C$ 的子问题可以写成如下形式：

\begin{array}{l} \underset{C}{m i n} λ_{2} {‖C‖}_{F}^{2} + 〈Y_{2}, Z - Z C - E_{Z}〉 + \\ \frac{μ}{2} {‖Z - Z C - E_{Z}‖}_{F}^{2} \end{array}

(19)

式（19）可化为下式：

\begin{array}{l} λ_{2} t r (C^{T} C) + Y_{2}^{T} (- Z C) + \frac{μ}{2} t r [C^{T} Z^{T} (Z - E_{Z}) + \\ C^{T} Z^{T} Z C - (Z^{T} - E_{Z}^{T}) Z C] \end{array}

(20)

上式对 $C$ 求偏导并令其导数等于0，求得 $C$ 的优化如下：

C = {(2 λ_{2} + μ Z^{T} Z)}^{- 1} [Z^{T} Y_{2} + μ Z^{T} (Z - E_{Z})]

(21)

2.2.5　更新拉格朗日乘子 $Y_{1}$ , $Y_{2}$ 和 $μ$

由式（9）， $Y_{1}$ ， $Y_{2}$ 和 $μ$ 的更新如下：

\begin{array}{l} Y_{1} = Y_{1} + μ (X - X Z - E_{X}) \\ Y_{2} = Y_{2} + μ (Z - Z C - E_{Z}) \\ μ = m i n (ρ μ, μ_{m a x}) \end{array}

(22)

其中， $ρ > 1$ ，单调增加ρ直达最大值max.

下面概述DSLSR优化的整个过程.

算法 DSLSR的优化算法

输入：原始数据集 $X$

初始化： $E_{X} = 0, E_{Z} = 0, C = 0, Y_{1} = 0, Y_{2} = 0, μ = 10^{- 4}, μ_{m a x} = 10^{6}, ε = 10^{- 6};$ 随机初始化 $Z$ ；

迭代：按照式（12）更新 $E_{X}$ ；按照式（15）更新 $E_{Z}$ ；按照式（17）更新 $Z$ ；按照式（21）更新 $C$ ；按照式（22）更新 $Y_{1}$ ， $Y_{2}$ 和 $μ$ ；

直到： ${‖X - X Z - E_{X}‖}_{\infty} < ε, {‖Z - Z C - E_{Z}‖}_{\infty} < ε$ ；

输出： $C, Z, E_{X} 和 E_{Z}$

2.3　复杂度及收敛性分析

如以上算法所示，DSLSR的计算主要分五个部分，即对四个子问题和拉格朗日乘子的更新.计算复杂度， $E_{X}$ 为 $O (m n^{2})$ ， $E_{Z}$ 为 $O (n^{3})$ ， $Z$ 为 $O (n^{3} + m n^{2})$ ， $C$ 为 $O (n^{3})$ ， $Y_{1}$ 为 $O (m n^{2})$ ， $Y_{2}$ 为 $O (n^{3})$ ， $μ$ 为 $O (1)$ .因此，DSLSR每次迭代的复杂度为 $O (n^{3} + m n^{2})$ .

DSLSR算法从理论上来分析其收敛性存在一定的困难^［27］，但是实验表明本算法具有非常稳定的收敛表现，具体见3.6.

3 实验

介绍DSLSR在真实数据集上的实验并讨论其实验结果.软件：matlab 2016a，处理器：Intel（R） Core（TM） i7⁃10750H CPU @ 2.60 GHz 2.59 GHz.

3.1　实验设置

为了评估DSLSR的性能，使用三个真实世界的数据集：ORL，Yale和Ceu数据集.同时，采用三个指标来评估DSLSR的性能，分别为归一化互信息（NMI）、准确度（ACC）和F分数（F⁃score），这些指标常用于评测视图聚类的性能.

ORL：包含400张人脸图像，共40个人，每个人10张图像.本实验中，将图像处理成 $32 \times 32$ 的大小.

Yale：包含15个人的人脸图像，每个人11张图像，在不同情况下形成，如神情（开心、悲伤、正常）、照明位置（左边、右边、中间），图像被处理成 $32 \times 32$ 的大小.

Ceu：包含53个人的人脸数据，每个人有22张不同的图片，共1166张图片.本实验中，将图像处理成 $32 \times 32$ 的大小.

这些数据集的样本图片如图1、图2和图3所示.为了消除实验的随机性，对每个真实数据集进行15次实验，实验结果以NMI，ACC和F⁃score平均值的形式给出.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 ORL的代表性图片

Fig.1 Representative pictures of ORL dataset

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 Yale的代表性图片

Fig.2 Representative pictures of Yale dataset

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 Ceu的代表性图片

Fig.3 Representative pictures of Ceu dataset

3.2　算法比较

在ORL，Yale和Ceu数据集上运行K⁃means，SSC，LSR，LRR，CAN，SSR算法，并与DSLSR进行对比.

K⁃means^［28］：将k个样本点分成n个类，并使这n个类内的k个样本点到各自的类中心距离之和最小.

SSC^［11］：通过 $L_{0}$ 或者 $L_{1}$ 范数来规范亲和矩阵，使亲和矩阵尽可能稀疏.

LSR^［17］：通过Frobenius范数对亲和矩阵进行约束，使亲和矩阵对噪音具有鲁棒性.

LRR^［15］：使用核范数来约束亲和矩阵，使亲和矩阵尽可能低秩.

CAN^［22］：采用自适应分配的最优邻居来学习亲和矩阵.

SSR^［23］：是最近新提出的一种算法，对亲和矩阵进行非负约束，并使亲和矩阵的每项列和约束于 $s (0 < s < 1)$ ，通过调整s来寻找最佳的聚类性能.

六种算法中，K⁃means是经典的聚类算法，SSC，LSR和LRR是经典的子空间聚类算法，CAN是最近提出的具有自适应邻域的子空间聚类算法，SSR是2021年刚提出的具有较好性能的子空间聚类算法.

3.3　亲和矩阵的可视化

由于K⁃means算法没有亲和矩阵，所以这部分实验没有与K⁃means进行比较.图4是DSLSR和其他算法（除K⁃means以外）在ORL数据集上亲和矩阵的可视化.由图可见，DSLSR算法的亲和矩阵比其他算法的亲和矩阵对角化更强，更干净.与LSR相比，更加凸显了DSLSR的亲和矩阵对角化明显和干净的特点，从而验证了本文算法的有效性.

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 不同算法在ORL数据集上的亲和矩阵可视化

Fig.4 Visualization of affinity matrix of different algorithms on ORL dataset

3.4　对比实验

为了验证DSLSR的性能，将DSLSR与这六种算法进行比较，实验结果如表1所示，表中黑体字表示DSLSR和性能最好的方法以及其对应的数值.

表1 不同数据集上的算法性能比较

Table 1 Performance of different algorithms on different datasets

数据集	方法	ACC	NMI	F⁃score
ORL_32×32	K⁃means	0.4442	0.6472	0.3294
	SSC	0.6784	0.8173	0.5433
	LSR	0.6631	0.8144	0.5348
	LRR	0.6047	0.7793	0.4781
	CAN	0.6250	0.7926	0.4881
	SSR	0.7026	0.8372	0.5819
	DSLSR	0.7133	0.8409	0.6012
Yale_32×32	K⁃means	0.4497	0.5323	0.3160
	SSC	0.5319	0.5639	0.3706
	LSR	0.5203	0.5454	0.3434
	LRR	0.5127	0.5280	0.3204
	CAN	0.4764	0.5177	0.3034
	SSR	0.4917	0.5330	0.3261
	DSLSR	0.5818	0.5971	0.4179
Ceu	K⁃means	0.2702	0.5666	0.1693
	SSC	0.9440	0.9869	0.9453
	LSR	0.9611	0.9926	0.9627
	LRR	0.9838	0.9968	0.9842
	CAN	0.6501	0.8787	0.6086
	SSR	0.9468	0.9901	0.9523
	DSLSR	0.9785	0.9957	0.9782

新窗口打开| 下载CSV

从实验结果可以得出以下结论：

（1）DSLSR的性能基本优于其他算法.在ORL数据集上DSLSR的ACC，NMI和F⁃score比最新的SSR算法分别高1.07%，0.37%和1.93%.在Yale数据集上，DSLSR的ACC，NMI和F⁃score比SSR算法分别高9.01%，6.41%和9.18%.在Ceu数据集上，DSLSR的ACC，NMI和F⁃score比SSR算法分别高3.17%，0.56%和2.59%.

（2）与LSR算法相比，DSLSR在三个数据集上的性能都更优.从亲和矩阵的对比图还可以看出，DSLSR比LSR算法获得的亲和矩阵对角化更明显和干净可靠，能提高算法的聚类性能.

（3）DSLSR有两个参数，与只有一个参数的K⁃means，SSC，LSR以及LRR算法相比，虽然不具有参数优势，但在ORL和Yale数据集上，DSLSR的性能优于这些方法.在Ceu数据集上，尽管DSLSR的性能是次优的，但与性能最好的LRR算法相差很小.与同样有两个参数的CAN和SSR算法相比，DSLSR在三个数据集上都更优.

综上所述，DSLSR方法具有较好的性能.

此外，本文还采用了t⁃SNE算法对相关方法进行特征点表示，如图5所示，其中不同的颜色代表不同类别的样本.由图可见，尽管其他方法的样本点在边缘部分聚类得较紧凑，但中间部分样本点的聚类没有DSLSR理想.

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 各种算法的t⁃SNE算法特征图比较

Fig.5 t⁃SNE feature diagrams of different algorithms

总体上看，DSLSR的样本点聚类优于其他算法.

3.5　参数敏感度

在ORL数据集上进行调节参数的实验，DSLSR算法中的两个参数 $λ_{1}$ 和 $λ_{2}$ 按照0.01，0.1，1，10，100，1000，10000进行调整，实验结果如图6所示.由图可见， $λ_{1} = 0.1, λ_{2} = 0.1$ 时，ACC，NMI和F⁃score均比较理想.

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6 在ORL数据库上参数 $λ_{1}$ 和 $λ_{2}$ 对DSLSR算法性能的影响

Fig.6 The effect of parameters $λ_{1}$ and $λ_{2}$ on the capability of DSLSR algorithm on ORL dataset

3.6　收敛性分析

由于DSLSR需要对多个变量进行优化，使DSLSR算法从理论上来分析其收敛性存在较大困难^［25］.然而，在三个数据集上的收敛实验表明，DSLSR算法基本上在30次迭代内收敛，其收敛过程如图7所示.

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7 DSLSR在三种数据集上的收敛曲线

Fig.7 Convergence curves of DSLSR on ORL，Yale and Ceu datasets

4 结论

本文提出一种新的双重结构子空间聚类算法DSLSR，能够去除亲和矩阵中的噪声，有利于数据聚类，从而提高聚类性能.此外，本文还设计了一种基于ALM的有效算法，对目标函数进行优化求解.在数据集上的实验表明，DSLSR算法的性能比现有的方法更卓越.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Cai

T T

， Shen

X T

. High⁃dimensional data analysis. Singapore：World Scientific，2011：320.