基于大数据挖掘的无损维规约技术

维规约也叫属性规约或降维，就是指减少或者压缩数据特征维度数目，摒弃不重要的维度特征，尽量只用少数的关键特征来描述数据。人们总是希望看到的现象主要是由少数的关键特征造成的，找到这些关键特征也是数据分析的目的。如果数据经过规约处理得当，不影响数据重新构造且不丢失任何信息，则该数据归约是无损的维规约技术。从数学角度讲就是，对于给定p维的数据向量X＝{x1，x2，x3，...，xn}，在某种条件下，寻找一个能反映原始数据信息的较低维的表示，即S＝{s1，s2，s3，...，sm}，其中n≥m。维规约技术，其形式分为两种：特征选择（属性选择）和特征提取（又称维变换），前者通过选择属性子集代表原属性集来达到维规约目的，后者则通过线性或非线性方法将高维属性空间变换到低维属性空间从而达到维规约目的^[32]。

1.特征选择

（1）特征选择概述。所谓特征选择就是从一组数量为N的特征中选择出一组数量为M的最优特征（N＞M），主要包括：选择一个判断最优特征的标准、找到一个好的算法来选择出这组最优特征。特征选择的主要目的是去除特征中的无关特征和冗余特征，如图4-11所示。

图4-11　特征选择

无关特征：指与当前学习任务无关的特征（该特征所提供的信息对当前学习任务无用），如对于罪犯数据而言，编号则是无关特征。

冗余特征：指该特征所包含的信息能从其他特征推演出来，如“面积”这个特征能通过“长”和“宽”得出，则它是冗余特征。

特征选择主要有两个功能：

①减少特征数量、降维，使模型泛化能力更强，减少过拟合；

②增强对特征和特征值之间的理解。

（2）特征选择一般过程：

①生成子集：搜索特征子集，为评价函数提供特征子集；

②评价函数：评价特征子集的好坏；

③停止准则：与评价函数相关，一般是阈值，当评价函数达到这个阈值后就可停止搜索；

④验证过程：在验证数据集上验证选出来的特征子集的有效性。

特征选择流程如图4-12所示。

图4-12　特征选择流程

（3）特征选择子集的搜索方法。常见的搜索策略主要有三种：

①完全搜索(www.xing528.com)

也就是枚举特征集中的所有特征组合，从而选出最优的特征子集，复杂度为O（2n），因此实际应用中几乎不采用。

②启发式搜索

启发式搜索策略主要有序列前向选择（SFS，Sequential Forward Selection）和序列后向选择（SBS，Sequential Backward Selection）等。假定原始特征集是f，挑选出来的特征子集是fsub。序列前向搜索策略首先把特征子集fsub初始化为空集，每一步从f-fsub（余下的特征集）中选择使得评价函数J（fsub＋x）最优的特征x，直至评价函数J无法改进，该算法便认为得到了最优的属性子集。与序列前向搜索策略相反的是，序列后向搜索策略搜索特征子集fsub从全集开始，每次删除一个属性x，重复该过程，直到评价函数J（fsub-x）最优。序列前向搜索策略和序列后向搜索策略的思想都为贪心思想，因此有时候容易陷入局部最优的情况中。也可把上述两种方法结合在一起称为双向搜索，此外还有决策树归纳算法等，具体内容见表4-4所示。

表4-4　特征选择常用方式

续表

（4）特征选择方法。特征选择主要有三种方法：

①过滤式（filter）方法。过滤式特征选择通常选择和类别相关度较大的特征或者特征子集，过滤式特征选择的研究者认为，相关度较大的特征或者特征子集在分类器上可以获得较高的准确率。过滤式特征选择的评价标准分为四种，即距离度量、信息度量、关联度度量以及一致性度量。其主要思想是：依据评价标准对每一维的特征“打分”，该分值就代表着该维特征的重要性，然后依据此分值排序。过滤式特征选择的评价标准从数据集本身的内在性质获得，与特定的学习算法无关，因此具有较好的通用性。

优点：算法的通用性强，省去了分类器的训练步骤；算法复杂性低，因而适用于大规模数据集；可以快速去除大量不相关的特征，作为特征的预筛选器非常合适。

缺点：没有考虑到特征之间的关联作用，可能把有用的关联特征误过滤掉。

过滤式特征选择算法中比较经典的有拉氏算法、SPEC算法、Relief算法、T-score算法、基于最大相关最小冗余的算法等，之后很多算法在这些经典算法的基础上，针对不同的领域的数据特征进行了优化和适应性变换^[33]。

②包裹式（wrapper）方法。包裹式特征选择把特征选择看作一个特征子集搜索问题，筛选各种特征子集，用模型评估效果。典型的包裹型算法为递归特征删除算法。例如，在逻辑回归中，用全量特征训练一个模型，然后根据线性模型的系数（体现相关性），删掉5%～10%的弱特征，观察准确率AUC的变化，逐步进行，直至准确率AUC出现大的下滑为止。

③嵌入式（embedding）方法。嵌入式特征选择有别于过滤式和包裹式，是根据模型来分析特征的重要性。在嵌入式特征选择中，特征选择算法本身作为组成部分嵌入到学习算法里。最典型的即决策树算法，如ID3、C4.5以及CART算法等，决策树算法在树增长过程的每个递归步都必须选择一个特征，将样本集划分成较小的子集，选择特征的依据通常是划分后子节点的纯度，划分后子节点越纯，则说明划分效果越好，可见决策树生成的过程也就是特征选择的过程。

2.特征提取

特征提取也叫维变换或特征降维，是指基于某种算法使用映射（或变换）的方法将原始数据的高维特征映射到较少的低维新数据特征上的过程。常见的特征提取算法分为线性与非线性方法。通过线性方法得到的低维数据仍可保持高维数据之间的线性关系。线性方法主要包括主成分分析法（PCA）、线性判别分析法（LDA）、局部保留投影法（LPP）等^[34]。但是针对高度非线性结构的数据集合，非线性特征提取（降维）方法更能揭示数据的主特征。非线性特征提取方法主要有多维尺度分析法（MDS）、等距映射法（Isomap）^[35]、局部线性嵌入法（LLE）^[36]、拉普拉斯特征映射法（Laplacian Eigenmaps）^[37]等。

（1）主成分分析法（PCA）。PCA可将高维数据映射到低维空间中，它是通过协方差矩阵进行特征分解，得出数据的主成分和权值，再根据数据的权值选择具有代表性的特征向量。它用数据投影后方差的大小衡量特征代表信息量的多少，方差越大，代表携带的信息就越多。选取前k维方差较大的特征，投影后的数据满足方差最大化，即数据点的分布稀疏，便于分类，此种特征提取方法可最大程度接近原始数据，但其并不着重探索数据的内部结构特征。PCA是一种无监督的线性特征提取方法，适用于有线性关系的数据，在人脸识别和图像处理中被广泛地应用。该方法概念简单，计算方便，时间复杂度较低，特征提取后的数据保留了大部分原始数据特征，但数据维度的确定没有明确准则。

（2）线性判别分析法（LDA）。LDA又叫Fisher线性判别法，其基本原理是通过Fisher准则函数选择某一个最佳的投影方向，使得样本投影到该方向后有最大的类间区分度和最小的类内离散度，以达到抽取分类信息和类别之间最佳的可分离性。此方法的输入数据带有标签，为有监督的特征提取方法。线性判别分析法（LDA）能够保证投影后模式样本在新的空间中有最小的类内距离和最大的类间距离，即模式在该空间中有最佳的可分离性，该方法属于监督学习的算法，但是对于不满足高斯分布的样本并不适用。

（3）多维尺度分析法（MDS）。MDS降维算法可以解决非线性数据的特征提取问题，它的原理是通过输入相似程度矩阵，在低维空间中找到相对位置坐标，利用欧氏距离来计算两点之间的距离，根据距离的长短来判断相似程度。它的基本思想是保留数据之间的相似性，可以分为经典MDS、度量性MDS和非度量性MDS。多维尺度分析法是一种将多维空间的研究对象（样本或变量）简化到低维空间进行定位、分析和归类，同时又保留对象间原始关系的数据分析方法。它不仅适用于探索变量之间的潜在规律性联系，也能处理名称变量和顺序变量数据，且不要求数据满足多元正态分布假设，现已被广泛应用于各研究领域。

（4）等距映射法（Isomap）。Isomap可从原始高维特征数据中提取出低维度的、强鉴别能力的嵌入式数据特征，显著地提高了识别精度。Isomap是对MDS算法的一种改进，MDS算法适用于欧式空间，它用欧式距离来衡量两点之间的距离大小。而对于流形结构，欧氏距离不再适用，故Isomap采用测地线来计算流形中的距离。Isomap算法对非线性的高维数据具有较好的处理能力，将相距较近的点之间的测地距离用欧式距离表示，相距很远的点间的测地距离采用最短路径逼近，并最大限度地保留特征提取后的数据样本间的全局测地距离信息，该方法在保证误差最小的同时，可实现特征数据的提取，因此该方法常应用于特征数据的非线性特征提取处理。