具有结构保持特性的数据特征选择方法

摘要

本发明公开了一种具有结构保持特性的数据特征选择方法，本发明可以得到一种更有效的无监督特征选择算法，该算法利用自表达模型对特征选择问题进行建模，从而避免因学习伪标签数据带来的噪声问题，进一步通过加入结构保持特性提高算法的鲁棒性，从而得到精度较高的聚类结果。其实现步骤是：(1)确定原始数据集X，构造原始数据集X的自表达模型；(2)自表达模型加入局部流形结构保持约束；(3)对加入局部流形结构保持约束的重构系数矩阵W进行约束，得到目标函数表达式；(4)对目标函数表达式进行优化求解；(5)对求解得到的特征选择矩阵进行特征选择。

权利要求

1.一种具有结构保持特性的数据特征选择方法，其特征在于，包括以下步骤：步骤1，确定原始数据集X，构造原始数据集X的自表达模型；其中，原始数据集X为COIL20人脸数据集或MNIST手写字符数据集或TOX_171生物学数据集；

X＝N×d,其中，N为数据个数，d为数据特征维度；N和d均为正整数；

具体构造方法是：

对于原始数据集X的第i个特征，构建自表达模型：其中wji为表达系数，fi表示原始数据集X的i个特征，|·|p为原始数据集X的p范数，fj表示原始数据集X的j个特征；

原始数据集X的自表达模型为：

min||W||p,X＝XW,  (2)d×d

其中,W∈R ，W为重构表达系数矩阵；

考虑到表达式(2)中原始数据集X通常包含噪声，因此表达式(2)为：其中，E表示原始数据集X中的噪声项，表达式(3)等同于：其中α为权重系数；

步骤2，对表达式(4)加入局部流形结构保持约束；

在原始数据集X中选定任意两个数据点xm和xn，其对应的权重可以表示为：结合表达式(4)和(5)得到表达式(6)：为保持局部流形结构，数据点xm和xn对应的重构数据WTxm和WTxn，WTxm代表XW的第m个重构数据点的转置，WTxn代表XW的第n个重构数据点的转置；

步骤3，对表达式(6)中的重构系数矩阵W进行约束，得到目标函数表达式；

对重构系数矩阵W进行l2,1正则约束，保证求得的重构系数矩阵W是行稀疏的，目标函数表达式为：步骤4，对目标函数表达式进行优化求解；

考虑到需要对式(7)进行求导，将式(7)中的第三项进行简化，具体为：因此目标函数式(7)可以转换为以下形式：其中，LS＝D-S表示S对应的Laplacian矩阵，考虑到W是行稀疏的，同时||wi||2有可能为零，因此将||wi||2写为 ε为趋近于0的正数，可以得到：令

对W求导并令导数为零，可以得到：其中，Q∈Rd×d是一个对角矩阵，其中的每一个对角元素Qii的形式如下：固定Q，可以得到W的表达式为：

W＝(βXTLSX+XTX+αQ)-1XTX.  (13)采用式(12)和(13)对Q和W进行求解，并判断式(10)中的 是否达到收敛条件；所述收敛条件是 若 则认为达到收敛，输出最终的特征选择矩阵W*；若则认为未达到收敛，则继续采用式(12)和(13)对Q和W进行迭代求解，直到 其满足收敛条件；

步骤5，根据W*，进行特征选择；

对于每一个特征i，求解 然后根据降序进行排序，选择前h个最大值对应的特征作为最后原始数据集X的特征选择结果，其余对应的特征剔除。

说明书

具有结构保持特性的数据特征选择方法

技术领域

[0001] 本发明属于信息处理技术领域，具体涉及一种具有结构保持特性的数据特征选择方法。

背景技术

[0002] 特征选择是一种非常有效的数据分析技术，目前受到了很多学者的关注和研究，在许多实际任务中取得了较好的效果，已经应用到图像处理和计算机视觉等领域，如人脸聚类、手写字符识别和物体分类。从是否使用标签数据的方面来看，可以将特征选择分为三类：有监督的特征选择、半监督的特征选择和无监督的特征选择。

[0003] 有监督的特征选择通过对具有标签的数据进行训练，然后在测试样本上进行实验验证，因为有监督的特征选择方法用到了大量的先验信息，所以可以取得精确度较高的特征选择结果。

[0004] 半监督的特征主要利用少量的标签信息，然后结合没有标签的数据共同学习，得到特征选择模型。考虑到实际应用中的数据都是无标签的，而且对数据进行标定的成本是非常昂贵的，因此无监督的特征选择方法得到了大量研究者的关注，近几年也得到了快速的发展。

[0005] 目前无监督的方法主要分为三大类：基于滤波的方法、基于封装的方法和基于嵌入的方法。因为基于嵌入的方法可以将特征选择问题整合到模型重建中，所以基于嵌入的方法可以更好的探索数据的不同特性，如流形结构保持、数据形式性保持等。

[0006] 一是基于滤波的特征选择方法，此类方法通常使用一些统计特性来选择重要的特征。代表性的工作是He，Cai和Niyogi在“X.He,D. Cai,P.Niyogi,Laplacian score for feature selection,in Neural Information Processing Systems,pp.507-514,2005.”上提出的工作。该工作主要是通过每个特征的局部保持能力来衡量特征的重要性。该方法首先计算样本点之间的距离，找到每个样本点对应的k近邻数据，构建相似度矩阵，然后根据相似度矩阵求解度矩阵，并构建对应的Laplacian图，最后求解每个特征的Laplacian Score，求得的值的大小即代表特征的重要性，然后选出h个最重要的特征。

[0007] 二是基于封装的特征选择方法，这些方法通常利用一个预测模型或者是学习方法进行特征选择，根据预定的学习算法对特征的重要性进行评价。考虑到聚类是无监督学习中的重要研究问题，一些基于聚类的标准用来检验特征选择以及对其聚类的结果。代表性的工作有 Dy和Brodley在“J.G.Dy,C.E.Brodley,Feature selection for unsupervised learning,Journal of Machine Learning Research, vol.5,pp.845-889,2004.”中提出的方法，该方法将特征选择问题封装到一个聚类算法中，然后用了两个评价指标去筛选候选的特征子集，这两个评价指标分别为散射可分性和最大似然估计。

[0008] 三是基于嵌入的特征选择方法，此类方法主要是将无监督特征选择问题嵌入到模型重建中，然后利用数据的结构保持、相似性保持等性质进行特征选择。考虑到谱分析已经成功运用到无监督学习的很多问题中，基于谱分析的无监督特征选择方法也被提出，而且取得了较好的结果。基于谱分析的方法主要是通过构建数据的相似度矩阵，学习到数据的伪标签矩阵，然后通过伪标签矩阵指导无监督的特征选择，所以如何得到高质量的伪标签矩阵是基于谱分析的方法的核心所在。代表性的工作有Li，Yang，et al.在“Z.Li,Y.Yang,J.Liu, X.Zhou,H.Lu,Unsupervised feature selectionusing nonnegative spectral analysis,in:Proceedings of Conference onArtificial Intelligence,2012.”上提出的非负可分的特征选择方法，该方法主要是通过在谱分析的基础上引入非负约束，从而反映出数据中的可分性信息，然后利用可分性信息学习数据的伪标签矩阵，并指导后面的特征选择过程。

[0009] 虽然基于滤波的方法比较容易实现，但是此类方法是分别对特征进行评价，往往忽视了全局信息，因此在一些任务上不能取得较好的特征选择结果。基于封装的方法往往有较大的时间复杂度，而且容易引起过拟合，从而降低特征选择的结果。基于嵌入的方法通常需要学习一个类标签矩阵，但是真正的类标签矩阵是由离散值组成，难以求解，因此目前的方法都是通过连续值来近似离散值，从而会引入噪声，得到不稳定的特征选择结果。

发明内容

[0010] 本发明的目的在于针对背景技术中现有方法的不足，提出一种具有结构保持特性的数据特征选择方法。该方法主要是利用原始数据集 X的自表达模型对特征选择问题进行建模，然后加入局部流形结构保持约束，相对于传统的基于嵌入的方法，本算法不需要学习数据的伪标签，从而避免引入噪声，影响到特征选择结果。本发明可以有效地 探索原始数据集X中数据之间的相似性关系，对数据的局部流形结构进行较好的保持，从而得到更加精确的特征选择结果。

[0011] 实现本发明的基本是思路是：

[0012] (1)根据原始数据集的自表达模型，构造适用于无监督特征选择问题的目标函数式。每个特征可以用其他的特征进行线性表达，采用常用的Frobenius范数对重构误差项进行约束，这样不仅可以对数据中的噪声进行处理，而且也方便对优化问题进行求解。

[0013] (2)考虑到局部结构通常优于全局特征，本发明通过构造局部流形结构保持约束使得重构后的数据可以保持在原始空间中的结构关系，从而提高特征选择算法的鲁棒性。

[0014] (3)因为本发明的目的是进行特征选择，所以需要对特征选择矩阵进行l2,1正则约束，保证求得的特征选择矩阵是行稀疏的，从而可以根据特征选择矩阵描述特征的重要性。

[0015] (4)对目标函数式进行优化求解。考虑到不能直接得到目标函数式的闭合解，本发明采用交替迭代算法对模型进行求解，得到最优的特征选择矩阵，求解算法的收敛性在实验部分也得到了很好的验证。

[0016] (5)对于得到的特征选择矩阵，对其行进行求解，然后根据求和结果进行降序排列，选取前h个值对应的特征作为最后的特征选择结果。

[0017] 本发明的具体技术方案是：

[0018] 本发明提供了一种具有结构保持特性的数据特征选择方法，其特征在于，包括以下步骤：

[0019] 步骤1，确定原始数据集X，构造原始数据集X的自表达模型；原始数据集X为COIL20人脸数据集或MNIST手写字符数据集或TOX_171生物学数据集；

[0020] X＝N×d,其中，N为数据个数，d为数据特征维度；N和d均为正整数；

[0021] 具体构造方法是：

[0022] 对于原始数据集X的第i个特征，构建自表达模型：

[0023]

[0024] 其中wji为表达系数，fi表示原始数据集X的i个特征，|·|p为原始数据集X的p范数，fj表示原始数据集X的j个特征；

[0025] 原始数据集X的自表达模型为：

[0026] min||W||p,X＝XW,  (2)

[0027] 其中,W∈Rd×d，W为重构表达系数矩阵；

[0028] 考虑到表达式(2)中原始数据集X通常包含噪声，因此表达式(2) 为：

[0029]

[0030] 其中，E表示原始数据集X中的噪声项，表达式(3)等同于：

[0031]

[0032] 其中α为权重系数；

[0033] 步骤2，对表达式(4)加入局部流形结构保持约束；

[0034] 在原始数据集X中选定任意两个数据点xm和xn，其对应的权重可以表示为：

[0035]

[0036] 结合表达式(4)和(5)得到表达式(6)：

[0037]

[0038] 为保持局部流形结构，数据点xm和xn对应的重构数据WTxm和WTxn，[0039] WTxm代表XW的第m个重构数据点的转置，WTxn代表XW的第n个重构数据点的转置；

[0040] 步骤3，对表达式(6)中的重构系数矩阵W进行约束，得到目标函数表达式；

[0041] 对重构系数矩阵W进行l2,1正则约束，保证求得的重构系数矩阵W 是行稀疏的，目标函数表达式为：

[0042]

[0043] 步骤4，对目标函数表达式进行优化求解；

[0044] 考虑到需要对式(7)进行求导，将式(7)中的第三项进行简化，具体为：

[0045]

[0046] 因此目标函数式(7)可以转换为以下形式：

[0047]

[0048] 其中，LS＝D-S表示S对应的Laplacian矩阵，考虑到W是行稀疏的，同时||wi||2有可能为零，因此将||wi||2写为 (ε为趋近于0的正数)，可以得到：

[0049]

[0050] 令

[0051]

[0052] 对W求导并令导数为零，可以得到：

[0053]

[0054] 其中，Q∈Rd×d是一个对角矩阵，其中的每一个对角元素Qii的形式如下：

[0055]

[0056] 固定Q，可以得到W的表达式为：

[0057] W＝(βXTLSX+XTX+αQ)-1XTX.  (13)

[0058] 采用式(12)和(13)对Q和W进行求解，并判断式(10)中的 是否达到收敛条件；所述收敛条件是 若 则认为达到收敛，输出最终的特征选择矩阵W*；若则认为未达到收敛，则继续采用式(12)和(13)对Q和W进行迭代求解，直到 其满足收敛条件；

[0059] 步骤5，根据W*，进行特征选择。

[0060] 对于每一个特征i，求解 然后根据降序进行排序，选择前h 个最大值对应的特征作为最后原始数据集X的特征选择结果，其余对应的特征剔除。

[0061] 本发明的有益效果是：

[0062] 总体来说，本发明通过利用自表达模型探索数据之间的相似性关系，避免学习伪标签矩阵引入的噪声，将局部流形结构保持约束引入到自表达模型中，从而提高算法的鲁棒性，该算法不但可以保证最后的收敛性，而且可以更有效地 探索具有代表性的特征，从而得到最具有代表性的特征子集，在不同数据集上的实验结果也说明了本方法的鲁棒性和有效性。

附图说明

[0063] 图1为本发明的流程图；

[0064] 图2为本发明在COIL20人脸数据集上的收敛性实验结果；

[0065] 图3为本发明在MNIST手写字符数据集上的收敛性实验结果；

[0066] 图4为本发明在TOX_171生物学数据集上的收敛性实验结果；

具体实施方式

[0067] 下面结合附图，对本发明实现的步骤作进一步的详细描述：

[0068] 参照图1，本发明实现的步骤如下：

[0069] 步骤1，确定原始数据集X，构造原始数据集X的自表达模型；原始数据集X为COIL20人脸数据集或MNIST手写字符数据集或TOX_171生物学数据集；

[0070] X＝N×d,其中，N为数据个数，d为数据特征维度；N和d均为正整数；

[0071] 具体构造方法是：

[0072] 对于原始数据集X的第i个特征，构建自表达模型：

[0073]

[0074] 其中wji为表达系数，fi表示原始数据集X的i个特征，|·|p为原始数据集X的p范数，fj表示原始数据集X的j个特征；

[0075] 原始数据集X的自表达模型为：

[0076] min||W||p,X＝XW,    (2)

[0077] 其中,W∈Rd×d，W为重构表达系数矩阵；

[0078] 考虑到表达式(2)中原始数据集X通常包含噪声，因此表达式(2) 可以被修改为：

[0079]

[0080] 其中，E表示原始数据集X中的噪声项，表达式(3)等同于：

[0081]

[0082] 其中α为权重系数；

[0083] 步骤2，对表达式(4)加入局部流形结构保持约束；

[0084] 在原始数据集X中选定任意两个数据点xm和xn，其对应的权重可以表示为：

[0085]

[0086] 为保持局部流形结构，数据点xm和xn对应的重构数据WTxm和WTxn应该保持原始数据点的最近邻关系(因为XW中的每一行代表一个重构数据点，所以WTxm代表XW的第m个重构数据点的转置,WTxn代表 XW的第n个重构数据点的转置；)，因此通过结合表达式(4)和(5) 得到表达式(6)：

[0087]

[0088] 步骤3，对表达式(6)中的重构系数矩阵W进行约束，得到目标函数表达式；

[0089] 对重构系数矩阵W进行l2,1正则约束，此时的重构系数矩阵记为特征 选择矩阵保证求得的重构系数矩阵W是行稀疏的，具体的形式如下：

[0090]

[0091] 步骤4，对目标函数表达式进行优化求解；

[0092] 考虑到需要对式(7)进行求导，但是式(7)中的第三项求解过程复杂，为了方便问题的求导，可以将式(7)中的第三项进行简化，具体为：

[0093]

[0094] 因此目标函数式(7)可以转换为以下形式：

[0095]

[0096] 其中，LS＝D-S表示S对应的Laplacian矩阵，考虑到W是行稀疏的，同时||wi||2有可能为零，因此将||wi||2写为 (ε为趋近于0的正数)，可以得到：

[0097]

[0098] 令

[0099]

[0100] 对W求导并令导数为零，可以得到：

[0101]

[0102] 其中，Q∈Rd×d是一个对角矩阵，其中的每一个对角元素Qii的形式如下：

[0103]

[0104] 固定Q，可以得到W的表达式为：

[0105] W＝(βXTLSX+XTX+αQ)-1XTX.    (13)

[0106] 采用式(12)和(13)对Q和W进行求解，并判断式(10)中的 是否达到收敛条件；所述收敛条件是 若 则认为达到收敛，输出最终的特征选择矩阵W*；若则认为未达到收敛，则继续采用式(12)和(13)对Q和W进行迭代求解，直到 其满足收敛条件；

[0107] 步骤5，根据W*，进行特征选择。

[0108] 对于每一个特征i，求解 然后根据降序进行排序，选择前h 个最大值对应的特征作为最后的特征选择结果，其余对应的特征剔除。

[0109] 本发明的效果可以通过以下仿真实验做进一步的说明。

[0110] 1.仿真条件

[0111] 本发明是在中央处理器为Intel(R)Core i3-2130 3.40GHZ、内存16G、WINDOWS 7操作系统上，运用MATLAB软件进行的仿真。

[0112] 实验中采用了三个数据集，分别为COIL20人脸数据集，MNIST手写字符数据集和TOX_171生物学数据集，对于每个数据集，进行多次实验，求其均值和方差。

[0113] 2.仿真内容

[0114] 按照如下步骤用本发明方法进行数据的聚类分析：

[0115] 为了展示算法的有效性，选择了六种无监督特征选择算法进行比较，分别为Laplacian Score(LS)、多类特征选择算法(MCFS)、可分性的特征选择算法(UDFS)、非负特征选择算法(NDFS)、鲁邦的特征选择算法(RUFS)、嵌入的特征选择算法(EUFS)。图2、图3和图4 给出了本发明方法的收敛性结果，从收敛性结果图中可以看出，当迭代次数大于10时，本方法已经趋于稳定，因此验证了本方法的收敛性，也为方法的稳定性提供了保证。

[0116] 其次，将本发明方法求解的聚类精度(AC)与其他六种对比方法得到的值进行比较，结果如表1所示，从中可以看出，我们的方法在不同的数据集上都取得了最好的效果，验证了方法的有效性。

[0117] 表1不同特征选择算法在COIL20、MNIST和TOX_171上的聚类精度值 (AC％±std)[0118]