权自适应最小二乘回归子空间分割法*

简彩仁，吕书龙

(1.厦门大学 嘉庚学院,福建 漳州 363150; 2.福州大学 数学与计算机科学学院,福建 福州 350108)

权自适应最小二乘回归子空间分割法*

简彩仁1，吕书龙2

(1.厦门大学 嘉庚学院,福建 漳州 363150; 2.福州大学 数学与计算机科学学院,福建 福州 350108)

基于表示理论的子空间分割方法有着广泛的应用。经典的子空间分割方法通过不同的正则项求解仿射矩阵，而忽略了特征属性对子空间分割的影响。针对这些问题，通过特征权重自适应的思想对最小二乘回归子空间分割方法进行改进，提出权自适应最小二乘回归子空间分割方法。在6个数据集上的实验结果表明该方法是有效的。

聚类；最小二乘回归；权自适应 ；子空间分割

0 引言

子空间分割方法是近年来聚类方法研究的热点问题[1-7]，其目标是将数据集分割(或聚集)成几个簇，并使每一个簇对应于一个子空间。子空间分割方法已经成功应用在机器学习和计算机视觉等相关研究中。现实中的数据近乎可以视为是混合子空间，因此子空间分割方法在图像聚类、图像分割、运动物体识别和基因表达数据识别等领域有着广泛的应用[1-6]。

子空间分割方法是一种重要的聚类方法，在过去的二十几年里，已经提出许多经典的子空间分割方法。根据其表示方式的不同子空间分割方法可以粗略地分为四类[3]：代数方法、迭代方法、统计方法、谱聚类方法。

低秩表示子空间分割方法旨在通过秩最小化来构建相似矩阵，最小二乘回归子空间分割方法通过F-范数正则化达到内聚度，图正则化子空间分割方法通过拉普拉斯图正则化保持相似度。但是现实数据存在各类噪声，因此样本重构时，很容易受到噪声的影响，然而这些方法都忽略了样本重构时特征属性噪声对子空间分割的影响。为了弥补这一不足，利用特征属性加权的方法改进最小二乘回归子空间分割方法，并通过对特征权重进行非负限制达到自适应选择特征权重的目的。该方法可以实现自适应选择特征权重，并保持最小二乘回归子空间分割方法的聚集性。

1 相关研究

针对理想的无噪声数据集，最小二乘回归子空间分割方法为:

然而现实数据总是存在噪声，将该模型扩展为:

这是经典的岭回归模型，其解析解为Z*=(XTX+λI)-1XTX，其中，λ>0是正则参数，I是单位矩阵。

最小二乘回归子空间分割方法有很好的聚集性能，并且该方法有解析解，可以快速得到表示系数，然而它忽略了特征属性噪声对子空间分割的影响。

2 权自适应最小二乘回归子空间分割

最小二乘回归子空间分割方法用X=XZ来重构样本，然而现实数据的特征属性总是存在噪声，但是最小二乘回归子空间分割方法没有考虑特征属性噪声对子空间分割的影响。针对这一不足，提出权自适应最小二乘回归子空间分割方法，该方法可以自适应地选择特征的权重，而不改变最小二乘回归子空间分割方法的聚集性能。

2.1 目标函数

因此，原始数据集X可以变为新的数据集diag(w)X，对其应用最小二乘回归子空间分割方法得到权自适应最小二乘回归子空间分割模型：

(1)

其中，λ>0是给定的正则参数。式(1)的第一项是加权重构项，其中参数wi表示第i个特征的重要程度，从而可以优化特征属性，使该方法更利于子空间分割；第二项是正则F-范数，用以实现子空间分割的聚集性。

2.2 目标优化

目标函数有两个参数w和Z，采用交替优化的方法实现问题(1)的求解。

(1)固定Z，优化w

固定参数Z，并且将无关的正则项去掉，式(1)变为：

(2)

其中，Y=X-XZ。式(2)可以转化为：

(3)

(4)

下面的定理给出了求解方法。

于是，得到如下不等式：

(2)固定w，优化Z

(5)

关于Z求导，并令其为0：

从而得到解析解：

(6)

上述两个步骤都可以得到极小值，因此算法的收敛性可以得到保证，通过上述两个步骤的交替迭代过程可以得到式(2)的解。

2.3 权自适应最小二乘回归子空间分割方法的聚集性质

最小二乘回归子空间分割方法有缩小相关数据系数和聚集性质[3]。定理2证明了权自适应最小二乘回归子空间分割方法也有这样的性质。

定理2 给定一个向量y∈Rm，矩阵X∈Rm×n和参数λ>0，假设X已经按列标准化，z*是如下权自适应最小二乘回归子空间分割问题的解：

(7)

那么

因此有：

以上两式相减有：

(8)

定理2证明的权自适应最小二乘回归子空间分割方法的聚集能力表明模型的最优解是相关依赖的。假如xi和xj是高度相关的，即r=1，定理2表明xi和xj对应的表示系数zi和zj的不同程度为0，这样xi和xj就会聚成相同的簇。

2.4 权自适应最小二乘回归子空间分割算法

算法：权自适应最小二乘回归子空间分割算法(ALSR)

Input：数据矩阵X，正则参数λ，类数k

Output：k个类簇

(1)利用2.2小节的方法解决式(2)，求得Z*：

①固定Z，利用式(4)优化w；

②固定w，利用式(6)优化Z；

直到收敛；

(3)应用标准分割方法将数据分成k个子空间。

3 实验

为验证权自适应最小二乘回归子空间分割方法(ALSR)的有效性，与经典的子空间分割方法最小二乘回归子空间分割方法(LSR)[3]、图正则化子空间分割方法(GRSS)[5]、低秩表示子空间分割方法(LRR)[2]以及传统的聚类方法K均值(K-means)从聚类的准确率的角度进行比较。聚类准确率的计算公式[9]如下：

对一个给定的样本，令ri和si分别为聚类算法得到的类标签和样本自带的类标签，那么准确率的计算公式为：

其中，n为样本总数；δ(x,y)是一个函数，当x=y时，值为1，否则为0；map(ri)是一个正交函数，将每一个类标签ri映射成与样本自带的类标签等价的类标签。

3.1 数据集

本文选用6个来自UCI数据库的常用于模式识别研究的公开数据集breast、german、liver、pima、vote和wpbc为研究对象，表1简要给出了它们的相关信息，更多的数据集描述可以参考UCI数据库的说明。

3.2 实验结果与分析

本文的实验环境为Windows 7系统，内存2 GB，所有方法都用MATLAB 2011b编程实现。实验结果用聚类准确率进行比较。实验中子空间分割方法ALSR、LSR、GRSS和LRR的正则参数设置为0.000 1，0.001，0.01，0.1，1，2，3，4，5，10。实验过程中遍历这些参数，实验结果选取平均聚类准确率最高的参数。GRSS的近邻数量固定为5。

表1 数据集描述

图1 不同参数下的聚类结果

[5] Chen Xiaoyun,Jian Cairen.Gene expression data clustering based on graph regularized subspace segmentation[J].Neurocomputing,2014,143(16):44-50.

[6] 林莉媛,陈晓云,简彩仁.融入距离信息的最小二乘回归子空间分割[J].微型机与应用,2016,35(6):63-65.

[7] VIDAL R.A tutorial on subspace clustering[J].IEEE Signal Processing Magazine,2010,28(2):52-68.

[8] Shi Jianbo,MALIK J.Normalized cuts and image segmenta-tion[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.

[9] Cai Deng,He Xiaofei,Wu Xiaoyun,et al.Non-negative matrix factorization on manifold[C].Proceedings of the 8th IEEE International Conference on Data Mining,Pisa,Italy,2008:63-72.

为避免随机性，每种方法运行10次取聚类准确率的平均值。表2以聚类准确率的均值±标准差(P值)的形式给出实验结果。

表2 聚类准确率对比

由实验结果得出以下结论：

(1)权自适应最小二乘回归子空间分割方法(ALSR)的聚类效果是理想的，除了在liver数据集上都取得最好的聚类准确率。其中，在liver数据集上聚类准确率不如图正则化子空间分割方法(GRSS)，但是P值大于0.05，显示两者的聚类准确率相差不大。

(2)与经典的最小二乘回归子空间分割方法(LSR)对比，ALSR的聚类准确率显著高于LSR。这一结果说明考虑特征权重对于改进LSR是有效的。此外，与其他经典的子空间分割方法GRSS和LRR对比，ALSR方法也有较理想的聚类准确率。因此，ALSR是一种有效的子空间分割方法。

(3)与传统的K-均值聚类方法(K-means)相比，ALSR在所有测试数据集上都可以取得更好的聚类准确率。尽管K-means聚类方法在某些数据集上有突出的聚类准确率，比如在vote数据集上可以达到86.90%的准确率，但是在其他数据集上聚类结果一般。因此，ALSR的聚类准确率比K-means聚类方法更突出。

3.3 参数选择

与LSR对比，ALSR通过自适应加权并没有增加新的参数，和LSR一样，ALSR只有一个参数：正则系数λ。图1的结果反映了正则参数λ对聚类准确率的影响。

从整体来看，聚类准确率对不同的正则参数λ较为敏感。但是从局部来看，ALSR的聚类准确率对不同的正则参数λ是相对稳定的，除了在vote数据集上，较小的正则参数λ具有较高的聚类准确率，这和文献[3]的研究结论是一致的。

4 结论

本文用权自适应的思想对最小二乘回归子空间分割方法进行改进，提出权自适应最小二乘回归子空间分割方法。在6个数据集上的实验结果表明权自适应最小二乘回归子空间分割方法通过考虑不同特征权重对数据集的影响，可以得到较为理想的聚类准确率。如何降低正则参数λ对聚类准确率的影响将是对ALSR进行进一步研究的一个方向。

[1] ELHAMIFAR E,VIDAL R.Sparse subspace clustering[C].Proceedings of 23rd IEEE Conference on Computer Vision and Pattern Recognition.Bonn,Germany,2009:2790-2797.

[2] Liu Guangcan,Lin Zhouchen,Yu Yong.Robust subspace segmentation by low-rank representation[C].Proceedings of the 27th International Conference on Machine Learning,Haifa,Israel,2010:663-670.

[3] Lu Canyi,Min Hai,Zhao Zhongqiu,et al.Robust and efficient subspace segmentation via least squares regression[C].Proceedings of the 12th European Conference on Computer Vision,Firenze,Italy,2012:347-360.

[4] 简彩仁,陈晓云.基于投影最小二乘回归子空间分割的基因表达数据聚类[J].模式识别与人工智能,2015,28(8):728-734.

Adaptive weight least square regression subspace segmentation

Jian Cairen1,Lv Shulong2

(1.Tan Kah Kee Colleage,Xiamen University,Zhangzhou 363105,China;2.College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China)

The subspace segmentation method based on the representation theory is widely used.The classical subspace segmentation methods are based on the different regularization terms to obtain the affine matrix.However,they neglect the influence of feature attributes on the subspace segmentation method.To solve these problems,the method based on adaptive weight least square regression subspace segmentation is improved.The experimental results on six data sets show that the proposed method is effective.

clustering; least square regression; adaptive weight; subspace segmentation

福建省中青年教师教育科研社科A类项目(JAS151395); 福州大学第九批高等教育教学改革工程项目(52001024)

TP311,TP371

A

10.19358/j.issn.1674- 7720.2017.10.016

简彩仁，吕书龙.权自适应最小二乘回归子空间分割法[J].微型机与应用，2017,36(10)：54-57,60.

2016-11-18)

简彩仁(1988-),男,硕士,主要研究方向：数据挖掘、模式识别等。

吕书龙(1977-),男,硕士，副教授,主要研究方向：数据挖掘,统计计算,应用统计分析等。