无监督特征选择算法的分析与总结

郭双乐 张建光 赵鑫 耿玉菊 石龙

摘要    高维无标记数据的出现不仅使数据处理的时间和空间复杂度增加，同时还会使训练模型出现过拟合，因此对高维无标记数据降维变得越来越必要。特征选择是数据降维的有效方法，本文给出了几种具有代表性的无监督特征选择方法，并指出了这些算法的优缺点，为进一步研究基于无监督的特征选择提供了理论基础。

【关键词】降维 特征选择 无监督

1 引言

在计算机视觉、多媒体分析等领域需要处理的数据往往具有很高的维数，对高维数据的处理增加了运算的时间和空间复杂度，同时也会导致学习模型的过拟合现象。流形学习的观点认为由于数据内部特征的限制，一些高维数据会产生维度上的冗余，实际上这些数据只要使用比较低的维度就能唯一的表示。另外，并不是所有的特征都和学习任务相关。以上两点说明对这些高维数据的降维成为必要和可能。

特征选择是常用的一种降维方法，它通过一定的算法从特征集合中选择出一组与分类有关的特征，使用选择的特征来进行模型学习。该方法不改变数据的原始表示，并且当所选择特征决定后，只要直接在原始特征集合里面对特征进行简单的提取即可。

特征选择方法按照训练数据中是否存在分类信息可分為监督特征选择方法和无监督特征选择方法。在现实世界中存在大量的非标记数据，并且对数据进行标记需要付出昂贵的代价，所以对无监督特征选择方法的研究具有很大的现实意义。本文主要针对无监督特征选择方法进行探讨。

2 无监督特征选择

无监督特征选择按照和学习算法的关系可分为有过滤式（Filter）、嵌入式（Embeded）和包裹式（wrapped）三大类，由于包裹式特征选择方法的时间复杂度一般较高，所以我们只对其他两种方法进行介绍。

2.1 过滤式

过滤式特征选择方法独立于具体的学习算法，它主要按照统计特性对特征的重要性进行排序，把重要性小的特征过滤掉，选择重要性大的特征作为原始数据的表示。由于该方法独立于具体的学习算法，所以其具有运算效率高的优点。

PCA得分法（PCAScore）和拉普拉斯得分法（LapScore）是常见的无监督的过滤式特征选择方法。下面分别对这两类算法给出简单介绍。

PCA得分法对原始数据的每一维特征的方差进行排序，特征的方差越大对原始数据的表示能力越强，从而就被选择出来。PCA得分法只用了数据的统计特性，而没有考虑到数据的流形特性，在将所选特征应用到具体的学习算法时效果受到影响。

拉普拉斯得分法选择最能够保持原始数据流形的特征。该方法首先根据训练数据建立关联矩阵S，在S的基础上建立对角矩阵D，其中D的对角元素Dii为S的第i行元素的和，根据S和D生成拉普拉斯矩阵L=D-S，每个特征的拉普拉斯得分计算如下：

基于流形的特征提取方法，首先都要计算关联矩阵S。关联矩阵的计算通常有如下三方法：

2.1.1 0-1权重

如果当第i个结点在第j个结点的p近邻内则Sij=1，否则Sij=0。这种方法最简单并且计算容易。

2.1.2 热核权重

当第i个结点在第j个结点的p近邻内则

基于流形的特征选择方法很好的保持了数据的流形特性，所选特征应用到具体学习算法时，取得了较好的效果，但是存在如下问题，

（1）对某些特征来说，它们单独和任务的相关性不是很大，但是它们的组合可能和任务的相关性很大，应用该方法进行特征选择，可能会出现对这些类特征的遗漏;

（2）该方法没考虑特征之间的相关性，从而造成了特征的冗余。

2.2 嵌入式

嵌入式特征选择方法把一个具体的分类器看做是一个白盒子，把特征选择融入分类模型，所以其分类效果通常要好，同时该类方法可以实现对多个特征的选择。MCFS和TRACK等都属于这类选择算法。

MCFS首先计算出数据在嵌入空间中的表示，之后通过线性回归的系数来确定各维特征的重要性。数据在嵌入空间中的表示是通过求解广义特征问题Ly=λDy获得的。令Y=[y1，...yk]，yk是最小的特征值对应的特征向量，K是嵌入空间的维数。

线性回归的系数通过求解以下问题来得到：

对每一个特征通过MCFS得分来确定其重要性，MCFS得分由以下公式获得：

该算法能够有效的对多簇数据进行特征选择。文献[9]提出的TRACK算法是基于无监督迹比值和k均值来实现嵌入式特征选择。TRACK算法的目标函数是：

其中，G是类指示矩阵，W为投影矩阵，X为样本矩阵，St为总体散布矩阵。该目标函数使把迹比值和k均值有机统一在一起，选择的特征具有很强的判别能力。

3 结论

在当今数据大爆发时代，大量高维无标记数据的出现，使数据处理面临着极大的挑战，所以非监督的特征选择十分必要。本文对几类非监督特征选择做了介绍，并比较详细的给出了过滤式和嵌入式两类特征选择方法中具有代表性的算法，同时指出了每种算法的优缺点，为进一步研究基于无监督的特征选择提供了理论基础。

参考文献

[1]Li J， Cheng K， Wang S， et al. Feature selection： A data perspective[J]. ACM Computing Surveys （CSUR）， 2018， 50（6）： 94.

[2]Roweis S T， Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]. science， 2000， 290（5500）： 2323-2326.

[3]Li Z， Yang Y， Liu J， et al. Unsupervised feature selection using nonnegative spectral analysis[C]// Twenty-Sixth AAAI Conference on Artificial Intelligence. 2012.

[4]Hou C， Nie F， Li X， et al. Joint embedding learning and sparse regression： A framework for unsupervised feature selection[J]. IEEE Transactions on Cybernetics， 2014， 44（6）： 793-804.

[5]Qian M， Zhai C. Robust unsupervised feature selection[C]//Twenty-Third International Joint Conference on Artificial Intelligence. 2013.

[6]Cohen I， Xiang Q T， Sean Zhou X S， et al. Feature selection using principal feature analysis[J]. 2002.

[7]He X， Cai D， Niyogi P. Laplacian score for feature selection[C]// Advances in neural information processing systems. 2006： 507-514.

[8]Cai D， Zhang C， He X. Unsupervised feature selection for multi-cluster data[C]//Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2010： 333-342.

[9]Wang D， Nie F， Huang H. Unsupervised feature selection via unified trace ratio formulation and k-means clustering （track）[C]//Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer， Berlin， Heidelberg， 2014： 306-321.