第17卷第2期 智能系统学报 Vol.17 No.2 2022年3月 CAAI Transactions on Intelligent Systems Mar.2022 D0:10.11992/tis.202012033 网络出版地址：https:/ns.cnki.net/kcms/detail/23.1538.TP.20211015.0035.002.html 联合不相关回归和非负谱分析的无监督特征选择 朱星宇1，陈秀宏 (1.江南大学人工智能与计算机学院，江苏无锡214122,2.江南大学江苏省蝶体设计与软件技术重点实验 室，江苏无锡214122) 摘要：在无标签高维数据普遍存在的数据挖掘和模式识别任务中，无监督特征选择是必不可少的预处理步 骤。然而现有的大多数特征选择方法忽略了数据特征之间的相关性，选择出具有高冗余、低判别性的特征。本 文提出一种基于联合不相关回归和非负谱分析的无监督特征选择方法(joint uncorrelated regression and nonnegat-- ive spectral analysis for unsupervised feature selection),在选择不相关且具有判别性特征的同时，自适应动态确定数 据之间的相似性关系，从而能获得更准确的数据结构和标签信息。而且，模型中广义不相关约束能够避免平凡 解，所以此方法具有不相关回归和非负谱聚类两种特征选择方法的优点。本文还设计出一种求解模型的高效 算法，并在多个数据集上进行了大量实验与分析，验证模型的优越性。 关键词：不相关回归；非负谱分析；冗余特征；局部结构学习；无监督学习；自适应图：特征选择；判别性特征 中图分类号：TP391.4文献标志码：A文章编号：1673-4785(2022)02-0303-11 中文引用格式：朱星宇，陈秀宏.联合不相关回归和非负谱分析的无监督特征选择.智能系统学报，2022,17(2)：303-313. 英文引用格式：ZHU Xingyu,CHEN Xiuhong.Joint uncorrelated regression and non-negative spectral analysis for unsupervised feature selection[J].CAAI transactions on intelligent systems,2022,17(2):303-313. Joint uncorrelated regression and non-negative spectral analysis for unsupervised feature selection ZHU Xingyu',CHEN Xiuhong (1.School of Artificial Intelligence and Computer Science,Jiangnan University,Wuxi 214122,China;2.Jiangsu Key Laboratory of Media Design and Software Technology,Jiangnan University,Wuxi 214122,China) Abstract:Unsupervised feature selection is an essential preprocessing step in the data mining and pattern recognition tasks of unlabeled high-dimensional data.However,most existing feature selection methods ignore the correlation between data features and select features with high redundancy and low discrimination.This paper proposes an unsuper- vised feature selection method based on joint uncorrelated regression and non-negative spectral analysis (Joint uncorrel- ated regression and nonnegative spectral analysis for unsupervised feature selection).It adaptively and dynamically de- termines the similarity relationship between data while selecting uncorrelated and discriminant features,so that more ac- curate data structure and label information can be obtained.Moreover,the generalized uncorrelated constraints in the model can avoid trivial solutions,so this method has the advantages of two feature selection methods:uncorrelated re- gression and non-negative spectral clustering.An efficient algorithm for solving the model is also designed,and a large number of experiments and analyses are carried out on multiple data sets to verify the superiority of the model. Keywords:uncorrelated regression;non-negative spectral analysis;redundant features;local structure learning;unsu- pervised learning,adaptive graph;feature selection;discriminant feature 收稿日期：2020-12-18.网络出版日期：2021-10-15. 基金项目：江苏省研究生科研与实践创新计划项目(NKYI9074). 在信息时代背景下产生了海量的高维数据， 通信作者：陈秀宏.E-mail:xiuhongc(@jiangnan.edu..cm 然而这些数据通常含有大量冗余特征和噪声，降
DOI: 10.11992/tis.202012033 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20211015.0035.002.html 联合不相关回归和非负谱分析的无监督特征选择 朱星宇1 ，陈秀宏2 （1. 江南大学 人工智能与计算机学院，江苏 无锡 214122; 2. 江南大学 江苏省媒体设计与软件技术重点实验 室，江苏 无锡 214122） 摘 要：在无标签高维数据普遍存在的数据挖掘和模式识别任务中，无监督特征选择是必不可少的预处理步 骤。然而现有的大多数特征选择方法忽略了数据特征之间的相关性，选择出具有高冗余、低判别性的特征。本 文提出一种基于联合不相关回归和非负谱分析的无监督特征选择方法 (joint uncorrelated regression and nonnegative spectral analysis for unsupervised feature selection)，在选择不相关且具有判别性特征的同时，自适应动态确定数 据之间的相似性关系，从而能获得更准确的数据结构和标签信息。而且，模型中广义不相关约束能够避免平凡 解，所以此方法具有不相关回归和非负谱聚类两种特征选择方法的优点。本文还设计出一种求解模型的高效 算法，并在多个数据集上进行了大量实验与分析，验证模型的优越性。 关键词：不相关回归；非负谱分析；冗余特征；局部结构学习；无监督学习；自适应图；特征选择；判别性特征 中图分类号：TP391.4 文献标志码：A 文章编号：1673−4785(2022)02−0303−11 中文引用格式：朱星宇, 陈秀宏. 联合不相关回归和非负谱分析的无监督特征选择 [J]. 智能系统学报, 2022, 17(2): 303–313. 英文引用格式：ZHU Xingyu, CHEN Xiuhong. Joint uncorrelated regression and non-negative spectral analysis for unsupervised feature selection[J]. CAAI transactions on intelligent systems, 2022, 17(2): 303–313. Joint uncorrelated regression and non-negative spectral analysis for unsupervised feature selection ZHU Xingyu1 ，CHEN Xiuhong2 (1. School of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi 214122, China; 2. Jiangsu Key Laboratory of Media Design and Software Technology, Jiangnan University, Wuxi 214122, China) Abstract: Unsupervised feature selection is an essential preprocessing step in the data mining and pattern recognition tasks of unlabeled high-dimensional data. However, most existing feature selection methods ignore the correlation between data features and select features with high redundancy and low discrimination. This paper proposes an unsupervised feature selection method based on joint uncorrelated regression and non-negative spectral analysis (Joint uncorrelated regression and nonnegative spectral analysis for unsupervised feature selection). It adaptively and dynamically determines the similarity relationship between data while selecting uncorrelated and discriminant features, so that more accurate data structure and label information can be obtained. Moreover, the generalized uncorrelated constraints in the model can avoid trivial solutions, so this method has the advantages of two feature selection methods: uncorrelated regression and non-negative spectral clustering. An efficient algorithm for solving the model is also designed, and a large number of experiments and analyses are carried out on multiple data sets to verify the superiority of the model. Keywords: uncorrelated regression; non-negative spectral analysis; redundant features; local structure learning; unsupervised learning; adaptive graph; feature selection; discriminant feature 在信息时代背景下产生了海量的高维数据， 然而这些数据通常含有大量冗余特征和噪声，降 收稿日期：2020−12−18. 网络出版日期：2021−10−15. 基金项目：江苏省研究生科研与实践创新计划项目（JNKY19_074）. 通信作者：陈秀宏. E-mail：xiuhongc@jiangnan.edu.cn. 第 17 卷第 2 期 智 能 系 统 学 报 Vol.17 No.2 2022 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2022
·304· 智能系统学报 第17卷 低了算法的性能。因此，如何从高维数据中选出 尽管上述无监督特征选择方法已经在各种应 最有效的特征即特征选择已成为一项研究热点， 用中取得了良好的性能，但仍有以下不足：1)上 特征选择旨在通过去除冗余、不相关和有噪声的 述基于谱特征选择的方法构造的相似图是从原始 特征，找到一组简洁且具有良好泛化能力的特征， 数据得到且是静态的，而现实世界的数据始终包 由此产生的方法已在机器学习)、数据挖掘)和 含大量噪声，这使得静态相似矩阵很不可靠，进 生物信息学等领域得到了广泛的应用。基于是 而破坏局部流形结构；2)最优相似矩阵应具有精 否使用标签，特征选择方法可分为有监督学习山 确的c个连通分量(c是类簇数)，它能更准确地 和无监督学习问。 揭示数据的局部邻域结构：3)通过传统正交约束 有监督学习依赖于数据的标签信息，并利用 选择出的特征虽达到了低冗余的目的，但会丢失 它直接指导学习过程。然而，从未标记数据中提 一些判别性的特征，这些特征在分类任务中往往 取最有判别性的信息是一个具有挑战性的问题， 能起到关键作用。 由于无监督特征选择可以根据原始数据的潜在属 综合上述分析，本文联合广义不相关回归、结 性来确定特征的重要性，因此近年来越来越受到 构化最优图和非负谱分析，提出一个联合不相关 研究人员的关注。本文主要研究无监督特征选择 回归和非负谱分析的无监督特征选择模型。模型 方法。 中对相似矩阵增加包含精确的c个连通分量的约 基于谱分析的无监督特征选择因其出色的性 束，可以用来动态学习结构化最优图，进而更准 能引起了广泛关注，本节将回顾一些比较经典的 确地揭示数据之间的局部结构信息；同时通过非 谱特征选择方法。无监督的判别特征选择(L2,~ 负谱聚类可以学习到更真实准确的聚类指标；利 norm regularized discriminative feature selection for 用广义不相关约束的正则回归方法选择不相关和 unsupervised learning)联合使用判别分析和 判别性的特征，有效避免不相关约束导致的平凡 L2!范数进行无监督特征选择，它虽然可以选择判 解。在不同数据集上的实验表明所提出的方法是 别性的特征，但却忽略了数据间的内在结构。 有效的，且该模型在无监督二维图像的特征选择 Nie等m提出了灵活流形嵌入(flexible manifold 领域，如：医学图像分类、人脸识别、模式识别等 embedding:a framework for semi-supervised and un- 计算机视觉任务方面有着广泛的应用价值。 supervised dimension reduction)作为降维的一般框 架，非负判别特征选择(unsupervised feature selec- 1相关工作 tion using nonnegative spectral analysis) 给定输人数据集X=[x12…xn]∈R,x;表示 FME框架中结合特征选择和谱聚类学习，它具有 第i个样本，并且这些数据点属于c个不同的类 鲁棒非负矩阵分解、局部学习和鲁棒特征学习的 簇。记r(M)为矩阵的迹；M为矩阵M的转置； 优势。联合嵌人学习和稀疏回归(joint embedding IMle为矩阵M的F范数：m表示矩阵M的第i行向 learning and sparse regression:a framework for unsu- 量；m,表示矩阵M的第j列向量；m,表示矩阵M的 pervised feature selection)是基于FME和L2:范数 第i行，第j列元素；给定矩阵M∈R,它的L21范 的特征选择方法，它致力于嵌入学习高维样本的 低维表示。最近，Nie等o提出了结构最优图特 数定义为IMl21= ∑∑=∑ml,其中 征选择(unsupervised feature selection with struc-. =1 = tured graph optimization),该方法同时执行特征选 表示向量m的L2范数；I为单位矩阵；1=[11…1 择和局部结构学习，同时它可以自适应地确定数 eR。中心矩阵H定义为H=I--严。 1 据间的相似性矩阵，但过于严格的正交约束选择 1.1广义不相关回归模型 出的特征会丢失一定程度的判别性，从而降低他 无监督特征选择也可以表示为回归模型， 们在聚类或分类任务中的性能。自适应图的广义 从而正则化回归模型也广泛应用在无监督特征 不相关回归(generalized uncorrelated regression 选择中。但是，已有工作忽略了特征的不相关 with adaptive graph for unsupervised feature selec- 性。尤其是当只需少量特征时，需要选择最具判 tion)通过最大嫡来自适应地构造相似图，进而 别性的特征。Li等)提出的以下广义不相关回 同时进行特征选择和谱聚类，但它在学习相似图 归模型(generalized uncorrelated regression model,, 时采用标签矩阵学习，没有考虑原始数据的类簇 GURM)可以获得具有判别性且不相关的流形 结构，这显然不是很合理。 结构：
低了算法的性能。因此，如何从高维数据中选出 最有效的特征即特征选择已成为一项研究热点， 特征选择旨在通过去除冗余、不相关和有噪声的 特征，找到一组简洁且具有良好泛化能力的特征， 由此产生的方法已在机器学习[1] 、数据挖掘[2] 和 生物信息学[3] 等领域得到了广泛的应用。基于是 否使用标签，特征选择方法可分为有监督学习[4] 和无监督学习[5]。 有监督学习依赖于数据的标签信息，并利用 它直接指导学习过程。然而，从未标记数据中提 取最有判别性的信息是一个具有挑战性的问题， 由于无监督特征选择可以根据原始数据的潜在属 性来确定特征的重要性，因此近年来越来越受到 研究人员的关注。本文主要研究无监督特征选择 方法。 基于谱分析的无监督特征选择因其出色的性 能引起了广泛关注，本节将回顾一些比较经典的 谱特征选择方法。无监督的判别特征选择 (L2,1- norm regularized discriminative feature selection for unsupervised learning)[ 6 ] 联合使用判别分析和 L2,1 范数进行无监督特征选择，它虽然可以选择判 别性的特征，但却忽略了数据间的内在结构。 Nie 等 [7] 提出了灵活流形嵌入 (flexible manifold embedding: a framework for semi-supervised and unsupervised dimension reduction) 作为降维的一般框 架，非负判别特征选择 (unsupervised feature selection using nonnegative spectral analysis)[8] 则在 FME 框架中结合特征选择和谱聚类学习，它具有 鲁棒非负矩阵分解、局部学习和鲁棒特征学习的 优势。联合嵌入学习和稀疏回归 (joint embedding learning and sparse regression: a framework for unsupervised feature selection)[9] 是基于 FME 和 L2,1 范数 的特征选择方法，它致力于嵌入学习高维样本的 低维表示。最近，Nie 等 [10] 提出了结构最优图特 征选择 (unsupervised feature selection with structured graph optimization)，该方法同时执行特征选 择和局部结构学习，同时它可以自适应地确定数 据间的相似性矩阵，但过于严格的正交约束选择 出的特征会丢失一定程度的判别性，从而降低他 们在聚类或分类任务中的性能。自适应图的广义 不相关回归 (generalized uncorrelated regression with adaptive graph for unsupervised feature selection)[11] 通过最大熵来自适应地构造相似图，进而 同时进行特征选择和谱聚类，但它在学习相似图 时采用标签矩阵学习，没有考虑原始数据的类簇 结构，这显然不是很合理。 尽管上述无监督特征选择方法已经在各种应 用中取得了良好的性能，但仍有以下不足：1) 上 述基于谱特征选择的方法构造的相似图是从原始 数据得到且是静态的，而现实世界的数据始终包 含大量噪声，这使得静态相似矩阵很不可靠，进 而破坏局部流形结构；2) 最优相似矩阵应具有精 确的 c 个连通分量（c 是类簇数），它能更准确地 揭示数据的局部邻域结构；3) 通过传统正交约束 选择出的特征虽达到了低冗余的目的，但会丢失 一些判别性的特征，这些特征在分类任务中往往 能起到关键作用。 综合上述分析，本文联合广义不相关回归、结 构化最优图和非负谱分析，提出一个联合不相关 回归和非负谱分析的无监督特征选择模型。模型 中对相似矩阵增加包含精确的 c 个连通分量的约 束，可以用来动态学习结构化最优图，进而更准 确地揭示数据之间的局部结构信息；同时通过非 负谱聚类可以学习到更真实准确的聚类指标；利 用广义不相关约束的正则回归方法选择不相关和 判别性的特征，有效避免不相关约束导致的平凡 解。在不同数据集上的实验表明所提出的方法是 有效的，且该模型在无监督二维图像的特征选择 领域，如：医学图像分类、人脸识别、模式识别等 计算机视觉任务方面有着广泛的应用价值。 1 相关工作 X = [x1 x2 ··· xn] ∈ R d×n xi tr(M) MT M ∥M∥F M F mi M mj M mi j M M ∈ R d×c L2,1 ∥M∥2,1 = ∑d i=1 vt∑c j=1 m 2 i j = ∑d i=1 m i 2 mi 2 mi L2 I 1 = [1 1 ··· 1]T ∈ R n×1 H H = I− 1 n I T 给定输入数据集 ， 表示 第 i 个样本，并且这些数据点属于 c 个不同的类 簇。记 为矩阵的迹； 为矩阵 的转置； 为矩阵 的 范数； 表示矩阵 的第 i 行向 量； 表示矩阵 的第 j 列向量； 表示矩阵 的 第 i 行，第 j 列元素；给定矩阵 ，它的 范 数定义为 ，其中 表示向量 的 范数； 为单位矩阵； 。中心矩阵 定义为 。 1.1 广义不相关回归模型 无监督特征选择也可以表示为回归模型， 从而正则化回归模型也广泛应用在无监督特征 选择中。但是，已有工作忽略了特征的不相关 性。尤其是当只需少量特征时，需要选择最具判 别性的特征。Li 等 [11] 提出的以下广义不相关回 归模型 (generalized uncorrelated regression model， GURM) 可以获得具有判别性且不相关的流形 结构： ·304· 智 能 系 统 学 报 第 17 卷
第2期 朱星宇，等：联合不相关回归和非负谱分析的无监督特征选择 ·305· 盟x'W+1b-F+pwIb 分量时（即它仅含有c个对角分块），则每个样本 (1) s.t.WTSGW=I 的近邻是最佳的。但是，问题(3)（式(3）)的解一般 不具备此性质，大多数情况下其解只包含1个连 式中：W∈R是回归矩阵，b∈R1是偏差项，FeR 是学习的嵌入聚类结构；正则化项W2,可使得 通分量2。 受文献[14]的启发，对拉普拉斯矩阵Ls=Ds W的行是稀疏的，进而选择重要的特征；B是正则 S+ST 化参数，B越大，W行越稀疏；S=S,+BG为广义散 的秩进行约束可使得矩阵S具有个连通分 2 度矩阵，G为d×d对角矩阵，其对角元素定义为 量。这时，问题(3)转化为 Gi= =,(8>0,i=1,2,…,d (2) 2+ min∑-x6s+alIs i.j-1 (4) 这里，8>0是一个很小的值，可避免因W的行 st.i,∑sy=l,5≥0，rank(Ls)=n- 稀疏而导致的分母为0的情形；S=XHX是样本 数据的总散度矩阵。一般地，当样本数量小于数 然而，问题(4)（式(4）)很难直接求解，因为秩 据维度时，S,是奇异的，而S总是正定的，这样约 约束是一个复杂的非线性约束。假设半正定矩阵 束条件WS9W=I可使数据在投影子空间中是统 Ls的n个非负特征值依次由小到大排列σ(Ls)≤ 计不相关的，这样可以很好地保留数据的全局结 σ2(Ls)≤…≤σ(Ls),则问题(4)可转化为 构。当B很小时，可使投影后样本之间高度不相 关，因此，约束条件WTSW=I在描述样本的不相 关性时要优于正交约束WW=I和传统不相关约 mm2k-6y+as呢+2n2u园 束WrS,W=I。 s.t. 1.2局部结构学习 研究表明，相似性矩阵可用来描述数据间的 局部结构。然而，大多数构造相似性矩阵的方法 其中，是一个充分大的正数，使得∑（化）=0咀 并没有考虑原始数据中的冗余特征和噪声，从而 矩阵Ls的秩等于n-c。根据KyFan's理论 导致所学习到的局部结构不够准确，最终影响特 立aL)=明nFLP (6) 征选择的结果。本节采用一种自适应确定相似度 矩阵的方法，可以同时执行特征选择和局部结 这里F∈Rx是类指标矩阵。故问题(5)（式 构学习。 (5)可重写为 两个数据样本相邻的概率可以用来描述它们 之间的相似度，记相似度矩阵为S∈R,其中元 min∑lx-xsy+als形+2：tr(F'Ls) i.l 素s表示相似性图中与样本x:和x,相对应的结点 (7) 之间相连的概率。样本x和x越接近，则对应的连接 S.t. ∑=l≥0FF=Lr20 概率s越大，它与对应结点之间的距离成反比。 相似度矩阵S∈R可通过以下优化问题得到： 正交非负约束可使得F的每一行只有一个元 素大于0，其他元素都等于0。从而得到的类指标 min∑k-x6s+alSf 矩阵F更准确，且获得更具判别性的信息。此外， 求解问题(7)（式(7）)得到的S包含精确的c个连通 S.L 时=1，≥0 (3) 分量，能够捕获更准确的局部结构信息。 1 这里，约束条件乃=1使得相似矩阵S的第 2联合不相关回归和非负谱分析模 i=l 型(JURNFS) i行元素之和等于1，表示与x:对应的总连接概率 为1，s衡量样本x和xj之间的局部相似度；α≥0 2.1模型建立 是正则化参数，可以自适应来确定1；正则化项 根据流形学习的理论，希望原始空间中样本 IS可以避免出现平凡解。 的近邻关系在低维投影空间中得到保持，为此， 1.3结构化最优图学习 本文讨论在低维空间内学习最优图。设W∈R 如果学习得到的相似矩阵恰好包含c个连通 是投影矩阵，则由()可得到以下模型：
min W,F,b X TW +1b T − F 2 F +β∥W∥2,1 s.t. WTS G t W = I (1) W ∈ R d×c b ∈ R c×1 F ∈ R n×c ∥W∥2,1 W β β W S G t = St +βG G d ×d 式中： 是回归矩阵， 是偏差项， 是学习的嵌入聚类结构；正则化项 可使得 的行是稀疏的，进而选择重要的特征； 是正则 化参数， 越大， 行越稀疏； 为广义散 度矩阵， 为 对角矩阵，其对角元素定义为 Gii = 1 2 √ ∥wi∥ 2 2 +ε ,(ε > 0,i = 1,2,··· ,d) (2) ε > 0 W St = XHXT St S G t WTS G t W = I β WTS G t W = I WTW = I WTStW = I 这里， 是一个很小的值，可避免因 的行 稀疏而导致的分母为 0 的情形； 是样本 数据的总散度矩阵。一般地，当样本数量小于数 据维度时， 是奇异的，而 总是正定的，这样约 束条件 可使数据在投影子空间中是统 计不相关的，这样可以很好地保留数据的全局结 构。当 很小时，可使投影后样本之间高度不相 关，因此，约束条件 在描述样本的不相 关性时要优于正交约束 和传统不相关约 束 。 1.2 局部结构学习 研究表明，相似性矩阵可用来描述数据间的 局部结构。然而，大多数构造相似性矩阵的方法 并没有考虑原始数据中的冗余特征和噪声，从而 导致所学习到的局部结构不够准确，最终影响特 征选择的结果。本节采用一种自适应确定相似度 矩阵的方法[12] ，可以同时执行特征选择和局部结 构学习。 S ∈ R n×n si j xi xj xi xj si j S ∈ R n×n 两个数据样本相邻的概率可以用来描述它们 之间的相似度，记相似度矩阵为 ，其中元 素 表示相似性图中与样本 和 相对应的结点 之间相连的概率。样本 和 越接近，则对应的连接 概率 越大，它与对应结点之间的距离成反比。 相似度矩阵 可通过以下优化问题得到： min∑n i, j=1 xi − xj 2 2 si j +α∥S∥ 2 F s.t. ∑n j=1 si j = 1,si j ⩾ 0 (3) ∑n j=1 si j = 1 S xi si j xi xj α ⩾ 0 ∥S∥ 2 F 这里，约束条件 使得相似矩阵 的第 i 行元素之和等于 1，表示与 对应的总连接概率 为 1， 衡量样本 和 之间的局部相似度； 是正则化参数，可以自适应来确定[13] ；正则化项 可以避免出现平凡解。 1.3 结构化最优图学习 如果学习得到的相似矩阵恰好包含 c 个连通 分量时（即它仅含有 c 个对角分块），则每个样本 的近邻是最佳的。但是，问题 (3)(式 (3)) 的解一般 不具备此性质，大多数情况下其解只包含 1 个连 通分量[12]。 LS = DS− S+S T 2 S 受文献 [14] 的启发，对拉普拉斯矩阵 的秩进行约束可使得矩阵 具有 c 个连通分 量。这时，问题 (3) 转化为 min∑n i, j=1 xi − xj 2 2 si j +α∥S∥ 2 F s.t. ∀i, ∑n j=1 si j = 1,si j ⩾ 0,rank(LS) = n−c (4) LS σ1(LS) ⩽ σ2(LS) ⩽ ··· ⩽σn(LS) 然而，问题 (4)(式 (4)) 很难直接求解，因为秩 约束是一个复杂的非线性约束。假设半正定矩阵 的 n 个非负特征值依次由小到大排列 ，则问题 (4) 可转化为 min∑n i, j=1 xi − xj 2 2 si j +α∥S∥ 2 F +2λ ∑c i=1 σi(LS) s.t. ∀i, ∑n j=1 si j = 1,si j ⩾ 0 (5) λ ∑c i=1 σi(LS) = 0 LS n−c 其中， 是一个充分大的正数，使得 且 矩阵 的秩等于 。根据 KyFan’s 理论[15] ： ∑c i=1 σi(LS) = min F∈Rn×c ,FTF=I tr(F T LSF) (6) F ∈ R 这里 n×c是类指标矩阵。故问题 (5)(式 (5)) 可重写为 min∑n i, j=1 xi − xj 2 2 si j +α∥S∥ 2 F +2λ ·tr(F T LSF) s.t. ∀i, ∑n j=1 si j = 1,si j ⩾ 0, F TF = I,F ⩾ 0 (7) F F S 正交非负约束可使得 的每一行只有一个元 素大于 0，其他元素都等于 0。从而得到的类指标 矩阵 更准确，且获得更具判别性的信息。此外， 求解问题 (7)(式 (7)) 得到的 包含精确的 c 个连通 分量，能够捕获更准确的局部结构信息。 2 联合不相关回归和非负谱分析模 型 (JURNFS) 2.1 模型建立 W ∈ R d×c 根据流形学习的理论，希望原始空间中样本 的近邻关系在低维投影空间中得到保持，为此， 本文讨论在低维空间内学习最优图。设 是投影矩阵，则由 (7) 可得到以下模型： 第 2 期 朱星宇，等：联合不相关回归和非负谱分析的无监督特征选择 ·305·
·306· 智能系统学报 第17卷 min W'x-Wxsu+l+2-(FLsF) 此时，问题(12)（式(12）)等价于以下问题： (8) minlH(XW-Fw'x-wx ll sy+BlWl. %∑=l,w≥0PF=1F≥0 s.t. s.t.W(S,+BG)W=I (13) 将模型(8)（式(8）)与稀疏回归模型(1)相结 合，得到本文联合不相关回归和非负谱分析模型： 令d2w-w四·并定义矩阵5中的元 映lXW+1h-F+∑Iwx-wx+ 素为=d,则问题(13)（式(13）)可等价于以下 i.j=l 问题： allsl +BllWlk+2-tr(FTLsF) (9) s.LW(S,+BG)W=L,FrF=L,F≥0， mintr(W(S,+BG)W-2WXHF+FHF)+ (14) 2=1.w≥0 t(WTXLXTW) s.t.W(S,+BG)W=I 其中，a、B、A是正则化参数。在式(9)中，第 式中：图拉普拉斯矩阵L=D-S,对角矩阵D的对 1项、第4项和第5项刻画了无监督不相关回归 D。=∑S加再由约束WS,+月 和非负谱分析，用于学习稀疏投影矩阵和预测标 签矩阵，且L2!范数可使得W保持行稀疏，从而能 及固定的F,问题(14)式(14)又可转化为 够选择出更具有价值和判别性的特征；第2项和 mintr(WTXLXW-2WTXHF) (15) 第3项用于学习数据的局部结构，确保原始空间 s.t.WT(S,+BG)W=I 内数据的相似结构在投影子空间内得到保持。这 该问题将不相关性表现为流形结构，且具有 里第2项未采用L2范数距离的平方，这是考虑到 闭式解。问题(15)式(15)》可表示为 若原始数据中有噪声，平方会扩大噪声对模型学 mintr(WTAW-2WTB) (16) 习与分类的影响。 s.t.WW=I 令问题(9)（式(9）)关于b的拉格朗日函数为 其中， (b)=XW+1bT-F+T(W.F.S) (10) W=VS,+BGW,A=CXLX'C. 其中，「(W,F,S)表示式(9)中依赖于W、F、S但又 B=CXHF.C=(S,+BG)" (17) 独立于b的项。取2%(b)关于b的导数并令其等于 问题(16)（式(16）)可以利用广义幂迭代方法 0,得 求解，详细过程见算法1。 b=(F-WXI (11) 算法1求解问题(14) 在实际应用中，数据结构总是多模态的，为了 输入数据矩阵X∈R,总散度矩阵S,∈Rd, 在多模态数据上获得更好的性能，可以研究图的 类指标矩阵FeRc,对角矩阵GeR,图拉普拉 局部性。假设S的每一行有一个具体的α，1，再结 斯矩阵立eRmx"。 合式(11)，问题(9)可重写为 输出投影矩阵WeR。 lXw-P啡+∑dwx-wxyt 初始化满足WW=I的随机矩阵W∈R, i,=1 根据等式(I7)计算A∈Rd和B∈R,定义随机v, as)+驯W21+2Atr(FLsF) 通过幂方法使得A=vl-A∈Rd为正定矩阵。 (12) s.t.W(S,+BGW=I,FrF=I,F≥0， 重复： %=1.5≥0 ①更新R←-2AW+2B: ②设矩阵R的满SVD分解为R=U∑V,则更 此时，参数可以控制每个样本自适应近邻 新W←Ur; 的数量。 直到收敛。 2.2模型求解 当求得式(16)的最优解之后，问题(14)的最 由于式(12)中的目标函数是凸的，故它有全 优解W可通过下述公式获得： 局最优解，但直接求其全局解比较困难。本节给 W-CW (18) 出一种交替优化方法来迭代求解它。 2)固定W和S,更新F 1)固定F和S,更新W 此时，问题(12)等价于：
min∑n i, j=1 WT xi −WT xj 2 2 si j +α∥S∥ 2 F +2λ ·tr(F T LSF) s.t. ∀i, ∑n j=1 si j = 1,si j ⩾ 0, F TF = I,F ⩾ 0 (8) 将模型 (8)(式 (8)) 与稀疏回归模型 (1) 相结 合，得到本文联合不相关回归和非负谱分析模型： min W,F,b,S X TW +1b T − F 2 F + ∑n i, j=1 WT xi −WT xj 2 si j+ α∥S∥ 2 F +β∥W∥2,1 +2λ ·tr(F T LSF) s.t.WT (St +βG)W = I,F TF = I,F ⩾ 0, ∀i, ∑n j=1 si j = 1,si j ⩾ 0 (9) α、β、λ L2,1 W L2 其中， 是正则化参数。在 式 ( 9 ) 中 ,第 1 项、第 4 项和第 5 项刻画了无监督不相关回归 和非负谱分析，用于学习稀疏投影矩阵和预测标 签矩阵，且 范数可使得 保持行稀疏，从而能 够选择出更具有价值和判别性的特征；第 2 项和 第 3 项用于学习数据的局部结构，确保原始空间 内数据的相似结构在投影子空间内得到保持。这 里第 2 项未采用 范数距离的平方，这是考虑到 若原始数据中有噪声，平方会扩大噪声对模型学 习与分类的影响。 令问题 (9)(式 (9)) 关于 b 的拉格朗日函数为 Ωb(b) = X TW +1b T − F 2 F + Γ(W,F,S) (10) Γ(W,F,S) W、F、S b Ωb(b) b 其中， 表示式 (9) 中依赖于 但又 独立于 的项。取 关于 的导数并令其等于 0，得 b = 1 n (F T −WTX)1 (11) S αi 在实际应用中，数据结构总是多模态的，为了 在多模态数据上获得更好的性能，可以研究图的 局部性。假设 的每一行有一个具体的 [13] ，再结 合式 (11)，问题 (9) 可重写为 min W,F,S H(X TW − F) 2 F + ∑n i, j=1 ( WT xi −WT xj 2 si j+ αis 2 i j)+β∥W∥2,1 +2λ ·tr(F T LSF) s.t.WT (St +βG)W = I,F TF = I,F ⩾ 0, ∀i, ∑n j=1 si j = 1,si j ⩾ 0 (12) 此时，参数αi可以控制每个样本自适应近邻 的数量[12]。 2.2 模型求解 由于式 (12) 中的目标函数是凸的，故它有全 局最优解，但直接求其全局解比较困难。本节给 出一种交替优化方法来迭代求解它。 1) 固定 F 和 S ，更新 W 此时，问题 (12)(式 (12)) 等价于以下问题： min W H(X TW − F) 2 F + ∑n i, j=1 WT xi −WT xj 2 si j +β∥W∥2,1 s.t.WT (St +βG)W = I (13) di j = 1 2 WT xi −WT xj 2 S˜ s˜i j = di jsi j 令 ，并定义矩阵 中的元 素为 ，则问题 (13)(式 (13)) 可等价于以下 问题： min W tr(WT (St +βG)W −2WTXHF+ F THF)+ tr(WTXLX˜ TW) s.t. WT (St +βG)W = I (14) L˜ = D˜ −S˜ D˜ D˜ ii = ∑n j=1 S˜ i j WT (St +βG)W = I F 式中：图拉普拉斯矩阵 ，对角矩阵 的对 角元素为 。再由约束 以 及固定的 ，问题 (14)(式 (14)) 又可转化为 min W tr(WTXLX˜ TW −2WTXHF) s.t. WT (St +βG)W = I (15) 该问题将不相关性表现为流形结构，且具有 闭式解。问题 (15)(式 (15)) 可表示为 min W¯ tr(W¯ TAW¯ −2W¯ TB) s.t. W¯ TW¯ = I (16) 其中， W¯ = √ St +βGW, A = C TXLX˜ TC, B = C TXHF, C = ( √ St +βG )−1 (17) 问题 (16)(式 (16)) 可以利用广义幂迭代方法[16] 求解，详细过程见算法 1。 算法 1 求解问题 (14) X ∈ R d×n St ∈ R d×d F ∈ R n×c G ∈ R d×d L˜ ∈ R n×n 输入 数据矩阵 ，总散度矩阵 ， 类指标矩阵 ，对角矩阵 ，图拉普拉 斯矩阵 。 W¯ ∈ R 输出 投影矩阵 d×c。 W¯ TW¯ = I W¯ ∈ R d×c A ∈ R d×d B ∈ R d×c v A˜ = νI− A ∈ R d×d 初始化 满足 的随机矩阵 ， 根据等式 (17) 计算 和 ，定义随机 ， 通过幂方法使得 为正定矩阵。 重复： ①更新 R ← 2A˜W¯ +2B ； R = UΣV T W¯ ← UVT ②设矩阵 R 的满 SVD 分解为 ，则更 新 ； 直到收敛。 W 当求得式 (16) 的最优解之后，问题 (14) 的最 优解 可通过下述公式获得： W = CW¯ (18) ２) 固定 W 和 S ，更新 F 此时，问题 (12) 等价于： ·306· 智 能 系 统 学 报 第 17 卷
第2期 朱星宇，等：联合不相关回归和非负谱分析的无监督特征选择 ·307· mintr(FTEF)-2tr(FTM) 矩阵S,∈Rd,正则化参数a和B及足够大的参数d。 (19) s.LFF=I,F≥0 输出计算w,i=1,2,…,d)并按照降序排 其中，E=H+2Ls,M=HXW。 序，然后选择前∫个排好序的特征作为特征选择 此问题可采用乘性更新规则7来求解。首先 的结果。 考虑它的松驰问题： 初始化通过K-means聚类初始化矩阵F, 定义随机矩阵W,通过求解问题(3)初始化相似矩 mint(FEF)-2u(FM)+FF- (20) 阵S,并计算图拉普拉斯矩阵LseR和L∈Rxm, s.t.F≥0 令G=Ikdo 其中，y为充分大的正数，由KKT最优性条件得 重复： 2EF-2M+yF(FTF-I)-=0 (21) ①由算法1求解式(16)得W,并由式(18)更 9F=0 (22) 新W; 这里，为对应于约束F≥0的非负拉格朗日 ②根据式(2)更新G; 乘子。于是有以下更新规则： ③由式(23)更新F; (M+yF) ④求解(26)更新S; F←FEF+yFFF (23) ⑤更新-n,-S 再对F的每一列归一化使得它满足条件(FTF):= ⑥更新矩阵5及对应的拉普拉斯矩阵i=D-5: 1,i=1,2,…,o 直到收敛。 3)固定W和F,更新S 2.3时间复杂度分析 此时，由于加月-户r-尾.故同题 在以上算法中，主要的计算复杂度为步骤 ①中的奇异值分解和矩阵求逆，故本算法时间复 (12)等价于以下问题： 杂度最高为O(d),假设算法迭代T次，则该部分 m呼w-wxsoi)+A/-f 的时间复杂度为O(Td),从而整个算法的时间复 杂度为0(Tm2d)。 st2=1断≥0 (24) 3实验及分析 其中，和f分别为F的第i行和第j行。该问题 3.1实验方案 可分解为以下n个独立的子问题： 在本节中，通过进行大量实验以充分验证本 mn∑wrx-wrxl+a+a∑V-f 文所提出方法的有效性和优越性。在展示结果之 前，首先提供一些详细的实验方案。 1)数据集：实验中使用了6个公共数据集，包 25) 括2个人脸数据集OL和BIOP0,1个物体数据 令e=wx,-wx2,F-f,则式(25) 集COIL202,1个手写字数据集BA2,1个树叶 转化为 数据集LEAVES四以及1个生物学数据集LUNGP网。 数据集的详细信息见表1及图1所示。 表1数据集信息 (26) Table 1 Detail introduction to datasets S.t. =1w≥0 j1 数据集 样本数特征数类别数 选择特征数 其中，m=(ea+f,…,em+fm)o ORL 400 1024 40 50、100、…、300 该问题可利用文献[18]中的方法求解，并可 BIO 1460 1024 22 50、100、…、300 自适应地确定式(9)中参数α1，进而获得具有精 确k个非零分量的最优解s。 C0L201440 1024 20 20、40、…、120 以上3步可迭代地进行，直到目标函数收敛 BA 1404 320 哈 20、40、、120 或满足终止条件，整个过程概括为算法2。 LEAVES 400 1024 10 50、100、…、300 算法2 JURNFS 输入数据矩阵X∈R,聚类数量c,总散度 LUNG 203 3312 5 100、150、…、350
min F tr(F TEF)−2tr(F TM) s.t. F TF = I,F ⩾ 0 (19) E = H +2λLS M = HX 其中， ， TW。 此问题可采用乘性更新规则[17] 来求解。首先 考虑它的松驰问题： min F tr(F TEF)−2tr(F TM)+ γ 2 F TF− I 2 F s.t. F ⩾ 0 (20) 其中， γ 为充分大的正数，由 KKT 最优性条件得 2EF−2M +γF(F TF− Ic)−Φ = 0 (21) φi jFi j = 0 (22) 这里， φi j 为对应于约束 Fi j ⩾ 0 的非负拉格朗日 乘子。于是有以下更新规则： Fi j ← Fi j (M +γF)i j (EF+γFFT F)i j (23) (F TF)ii = 1, i = 1,2,··· ,n 再对 F 的每一列归一化使得它满足条件 。 3) 固定 W 和 F ，更新 S 2tr(F T LSF) = ∑n i, j=1 f i − f j 2 2 此时，由于 si j ，故问题 (12) 等价于以下问题： min S ∑n i, j=1 ( WT xi −WT xj 2 si j +αis 2 i j) +λ ∑n i, j=1 f i − f j 2 2 si j s.t. ∀i, ∑n j=1 si j = 1,si j ⩾ 0 (24) f i f j 其中， 和 分别为 F 的第 i 行和第 j 行。该问题 可分解为以下 n 个独立的子问题： min si j ∑n j=1 ( WT xi −WT xj 2 si j +αis 2 i j) +λ ∑n j=1 f i − f j 2 2 si j s.t. ∑n j=1 si j = 1,si j ⩾ 0 (25) ei j = WT xi −WT xj 2 fi j f i − f j 2 令 2 ， ， 则 式 (25) 转化为 min s i s i + mi 2ai 2 2 s.t. ∑n j=1 si j = 1,si j ⩾ 0 (26) mi = (eil +λ fil,··· , ein +λ f 其中， in)。 α s i 该问题可利用文献 [18] 中的方法求解，并可 自适应地确定式 (9) 中参数 [13] ，进而获得具有精 确 k 个非零分量的最优解 。 以上 3 步可迭代地进行，直到目标函数收敛 或满足终止条件，整个过程概括为算法 2。 算法 2 JURNFS X ∈ R 输入 数据矩阵 d×n，聚类数量 c，总散度 St ∈ R d×d 矩阵 ，正则化参数α和 β 及足够大的参数 λ。 w i 2 输出 计算 (i = 1,2,··· ,d) 并按照降序排 序，然后选择前 f 个排好序的特征作为特征选择 的结果。 F W S LS ∈ R n×n L˜ ∈ R n×n G = Id×d 初始化 通过 K-means 聚类初始化矩阵 ， 定义随机矩阵 ，通过求解问题 (3) 初始化相似矩 阵 ，并计算图拉普拉斯矩阵 和 ， 令 。 重复： W¯ W ①由算法 1 求解式 (16) 得 ，并由式 (18) 更 新 ； ②根据式 (2) 更新 G ； ③由式 (23) 更新 F ； ④求解 (26) 更新 S ； LS = DS − S+S T 2 ⑤更新 ； ⑥更新矩阵 S˜及对应的拉普拉斯矩阵 L˜ = D˜ −S˜； 直到收敛。 2.3 时间复杂度分析 O(n 2d) T O(T n2d) O(T n2d) 在以上算法中，主要的计算复杂度为步骤 ①中的奇异值分解和矩阵求逆，故本算法时间复 杂度最高为 ，假设算法迭代 次，则该部分 的时间复杂度为 ，从而整个算法的时间复 杂度为 。 3 实验及分析 3.1 实验方案 在本节中，通过进行大量实验以充分验证本 文所提出方法的有效性和优越性。在展示结果之 前，首先提供一些详细的实验方案。 1) 数据集：实验中使用了 6 个公共数据集，包 括 2 个人脸数据集 ORL[19] 和 BIO[20] ，1 个物体数据 集 COIL20[21] ，1 个手写字数据集 BA[22] ，1 个树叶 数据集 LEAVES[23] 以及 1 个生物学数据集 LUNG[24]。 数据集的详细信息见表 1 及图 1 所示。 表 1 数据集信息 Table 1 Detail introduction to datasets 数据集 样本数 特征数 类别数 选择特征数 ORL 400 1 024 40 50、100、···、300 BIO 1 460 1 024 22 50、100、···、300 COIL20 1 440 1 024 20 20、40、···、120 BA 1 404 320 36 20、40、···、120 LEAVES 400 1 024 10 50、100、···、300 LUNG 203 3 312 5 100、150、···、350 第 2 期 朱星宇，等：联合不相关回归和非负谱分析的无监督特征选择 ·307·