1 , y ~ 1 ) , ( x 2 , y ~ 2 ) , ⋯ , ( x N , y ~ N )} , y ~ i ∈ { 0 , 1 } 。 对于每个样本x ⃗ i \mathbf{\vec x}_i x i :Relief
先在x ⃗ i \mathbf{\vec x}_i x i 同类样本中寻找其最近邻x ⃗ n h i \mathbf{\vec x}_{nh_i} x n h i ,称作猜中近邻near-hit
。
然后从x ⃗ i \mathbf{\vec x}_i x i 的异类样本中寻找其最近邻x ⃗ n m i \mathbf{\vec x}_{nm_i} x n m i ,称作猜错近邻near-miss
。
然后相关统计量对应于属性j j j 的分量为:
δ j = ∑ i = 1 N ( − diff ( x i , j , x n h i , j ) 2 + diff ( x i , j , x n m i , j ) 2 ) \delta_j=\sum_{i=1}^{N}\left(-\text{diff}(x_{i,j},x_{nh_i,j})^2+\text{diff}(x_{i,j},x_{nm_i,j})^{2}\right) δ j = i = 1 ∑ N ( − diff ( x i , j , x n h i , j ) 2 + diff ( x i , j , x n m i , j ) 2 )
其中diff ( x a , j , x b , j ) \text{diff}(x_{a,j},x_{b,j}) diff ( x a , j , x b , j ) 为两个样本在属性j j j 上的差异值,其结果取决于该属性是离散的还是连续的:
如果属性j j j 是离散的,则:
diff ( x a , j , x b , j ) = { 0 , if x a , j = x b , j 1 , e l s e \text{diff}(x_{a,j},x_{b,j})=\begin{cases} 0,&\text{if}\quad x_{a,j}=x_{b,j}\\ 1,&else \end{cases} diff ( x a , j , x b , j ) = { 0 , 1 , if x a , j = x b , j e l se
如果属性j j j 是连续的,则:
diff ( x a , j , x b , j ) = ∣ x a , j − x b , j ∣ \text{diff}(x_{a,j},x_{b,j})=| x_{a,j}-x_{b,j}| diff ( x a , j , x b , j ) = ∣ x a , j − x b , j ∣
注意:此时x a , j , x b , j x_{a,j},x_{b,j} x a , j , x b , j 需要标准化到 [0,1]
区间。
从公式
δ j = ∑ i = 1 N ( − diff ( x i , j , x n h i , j ) 2 + diff ( x i , j , x n m i , j ) 2 ) \delta_j=\sum_{i=1}^{N}\left(-\text{diff}(x_{i,j},x_{nh_i,j})^2+\text{diff}(x_{i,j},x_{nm_i,j})^{2}\right) δ j = i = 1 ∑ N ( − diff ( x i , j , x n h i , j ) 2 + diff ( x i , j , x n m i , j ) 2 )
可以看出:
如果x ⃗ i \mathbf{\vec x}_i x i 与其猜中近邻x ⃗ n h i \mathbf{\vec x}_{nh_i} x n h i 在属性j j j 上的距离小于x ⃗ i \mathbf{\vec x}_i x i 与其猜错近邻x ⃗ n m i \mathbf{\vec x}_{nm_i} x n m i 的距离,则说明属性j j j 对于区分同类与异类样本是有益的,于是增大属性j j j 所对应的统计量分量。 如果x ⃗ i \mathbf{\vec x}_i x i 与其猜中近邻x ⃗ n h i \mathbf{\vec x}_{nh_i} x n h i 在属性j j j 上的距离大于x ⃗ i \mathbf{\vec x}_i x i 与其猜错近邻x ⃗ n m i \mathbf{\vec x}_{nm_i} x n m i 的距离,则说明属性j j j 对于区分同类与异类样本是起负作用的,于是减小属性j j j 所对应的统计量分量。 最后对基于不同样本得到的估计结果进行平均,就得到各属性的相关统计量分量。分量值越大,则对应属性的分类能力越强。 Relief
是为二分类问题设计的,其扩展变体 Relief-F
能处理多分类问题。假定数据集D \mathbb D D 中的样本类别为:c 1 , c 2 , ⋯ , c K c_1,c_2,\cdots,c_K c 1 , c 2 , ⋯ , c K 。对于样本x ⃗ i \mathbf{\vec x}_i x i ,假设y ~ i = c k \tilde y_i=c_k y ~ i = c k 。
Relief-F
先在类别c k c_k c k 的样本中寻找x ⃗ i \mathbf{\vec x}_i x i 的最近邻x ⃗ n h i \mathbf{\vec x}_{nh_i} x n h i 作为猜中近邻。
然后在c k c_k c k 之外的每个类别中分别找到一个x ⃗ i \mathbf{\vec x}_i x i 的最近邻x ⃗ n m i l , l = 1 , 2 , ⋯ , K ; l ≠ k \mathbf{\vec x}_{nm_i^l} ,l=1,2,\cdots,K;l\ne k x n m i l , l = 1 , 2 , ⋯ , K ; l = k 作为猜错近邻。
于是相关统计量对应于属性j j j 的分量为:
δ j = ∑ i = 1 N ( − diff ( x i , j , x n h i , j ) 2 + ∑ l ≠ k ( p l × diff ( x i , j , x n m i l , j ) 2 ) ) \delta_j=\sum_{i=1}^{N}\left(-\text{diff}(x_{i,j},x_{nh_i,j})^{2}+\sum_{l\ne k}\left(p_l\times\text{diff}(x_ {i,j},x_{nm_i^l,j})^{2}\right)\right) δ j = i = 1 ∑ N ⎝ ⎛ − diff ( x i , j , x n h i , j ) 2 + l = k ∑ ( p l × diff ( x i , j , x n m i l , j ) 2 ) ⎠ ⎞
其中p l p_l p l 为第l l l 类的样本在数据集D \mathbb D D 中所占的比例。
优点 :运行速度快,是一种非常流行的特征选择方法。
缺点 :无法提供反馈,特征选择的标准规范的制定是在特征搜索算法中完成,学习算法无法向特征搜索算法传递对特征的需求。另外,可能处理某个特征时由于任意原因表示该特征不重要,但是该特征与其他特征结合起来则可能变得很重要。
包裹式Wrapper 单变量特征选择方法独立的衡量每个特征与响应变量之间的关系,另一种主流的特征选择方法是基于机器学习模型的方法。有些机器学习方法本身就具有对特征进行打分的机制,或者很容易将其运用到特征选择任务中,例如回归模型,SVM,决策树,随机森林等等。 主要思想 :包裹式从初始特征集合中不断的选择特征子集,训练学习器,根据学习器的性能来对子集进行评价,直到选择出最佳的子集。包裹式特征选择直接针对给定学习器进行优化。主要方法 :递归特征消除算法, 基于机器学习模型的特征排序与过滤式特征选择不考虑后续学习器不同,包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。其目的就是为给定学习器选择最有利于其性能、量身定做的特征子集。
LVW:Las Vegas Wrapper
是一个典型的包裹式特征选择方法。它是Las Vegas method
框架下使用随机策略来进行子集搜索,并以最终分类器的误差作为特征子集的评价标准。
LVW
算法:
由于LVW
算法中每次特征子集评价都需要训练学习器,计算开销很大,因此算法设置了停止条件控制参数T T T 。但是如果初始特征数量很多、T T T 设置较大、以及每一轮训练的时间较长, 则很可能算法运行很长时间都不会停止。即:如果有运行时间限制,则有可能给不出解。
优点:从最终学习器的性能来看,包裹式比过滤式更好;对特征进行搜索时围绕学习算法展开的,对特征选择的标准规范是在学习算法的需求中展开的,能够考虑学习算法所属的任意学习偏差,从而确定最佳子特征,真正关注的是学习问题本身。由于每次尝试针对特定子集时必须运行学习算法,所以能够关注到学习算法的学习偏差 / 归纳偏差,因此封装能够发挥巨大的作用。
缺点:由于特征选择过程中需要多次训练学习器,因此包裹式特征选择的计算开销通常比过滤式特征选择要大得多。
嵌入式Embedded 在过滤式和包裹式特征选择方法中,特征选择过程与学习器训练过程有明显的分别。而嵌入式特征选择在学习器 训练过程中自动地进行特征选择。嵌入式选择最常用的是 L1 正则化与 L2 正则化。在对线性回归模型加入两种正则化方法后,他们分别变成了岭回归与 Lasso 回归。 主要思想 :在模型既定的情况下学习出对提高模型准确性最好的特征。也就是在确定模型的过程中,挑选出那些对模型的训练有重要意义的特征。主要方法 :简单易学的机器学习算法–岭回归(Ridge Regression),就是线性回归过程加入了 L2 正则项。L1 正则化有助于生成一个稀疏权值矩阵,进而可以用于特征选择 L2 正则化在拟合过程中通常都倾向于让权值尽可能小,最后构造一个所有参数都比较小的模型。因为一般认为参 数值小的模型比较简单,能适应不同的数据集,也在一定程度上避免了过拟合现象。可以设想一下对于一个线性 回归方程,若参数很大,那么只要数据偏移一点点,就会对结果造成很大的影响;但如果参数足够小,数据偏移 得多一点也不会对结果造成什么影响,专业一点的说法是『抗扰动能力强』。 在过滤式和包裹式特征选择方法中,特征选择过程与学习器训练过程有明显的分别。
嵌入式特征选择是将特征选择与学习器训练过程融为一体,两者在同一个优化过程中完成的。即学习器训练过程中自动进行了特征选择。
以线性回归模型为例。
给定数据集D = { ( x ⃗ 1 , y ~ 1 ) , ( x ⃗ 2 , y ~ 2 ) , ⋯ , ( x ⃗ N , y ~ N ) } , y ~ i ∈ R \mathbb D=\{(\mathbf{\vec x}_1,\tilde y_1),(\mathbf{\vec x}_2,\tilde y_2),\cdots,(\mathbf{\vec x}_N,\tilde y_N)\}, \tilde y_i \in \mathbb R D = {( x 1 , y ~ 1 ) , ( x 2 , y ~ 2 ) , ⋯ , ( x N , y ~ N )} , y ~ i ∈ R 。 以平方误差为损失函数,则优化目标为:
min w ⃗ ∑ i = 1 N ( y ~ i − w ⃗ T x ⃗ i ) 2 \min_{\mathbf{\vec w}} \sum_{i=1}^{N}(\tilde y_i-\mathbf{\vec w}^{T}\mathbf{\vec x}_i)^{2} w min i = 1 ∑ N ( y ~ i − w T x i ) 2
如果使用L 2 L_2 L 2 范数正则化,则优化目标为:
min w ⃗ ∑ i = 1 N ( y ~ i − w ⃗ T x ⃗ i ) 2 + λ ∣ ∣ w ⃗ ∣ ∣ 2 2 , λ > 0 \min_{\mathbf{\vec w}} \sum_{i=1}^{N}(\tilde y_i-\mathbf{\vec w}^{T}\mathbf{\vec x}_i)^{2}+\lambda||\mathbf{\vec w}||_2^{2},\quad\lambda\gt 0 w min i = 1 ∑ N ( y ~ i − w T x i ) 2 + λ ∣∣ w ∣ ∣ 2 2 , λ > 0
此时称作岭回归ridge regression
。
如果使用L 1 L_1 L 1 范数正则化,则优化目标为:
min w ⃗ ∑ i = 1 N ( y ~ i − w ⃗ T x ⃗ i ) 2 + λ ∣ ∣ w ⃗ ∣ ∣ 1 , λ > 0 \min_{\mathbf{\vec w}} \sum_{i=1}^{N}(\tilde y_i-\mathbf{\vec w}^{T}\mathbf{\vec x}_i)^{2}+\lambda||\mathbf{\vec w}||_1,\quad\lambda\gt 0 w min i = 1 ∑ N ( y ~ i − w T x i ) 2 + λ ∣∣ w ∣ ∣ 1 , λ > 0
此时称作LASSO:Least Absolute Shrinkage and Selection Operator
回归。
引入L 1 L_1 L 1 范数除了降低过拟合风险之外,还有一个好处:它求得的w ⃗ \mathbf{\vec w} w 会有较多的分量为零。即:它更容易获得稀疏解。
于是基于L 1 L_1 L 1 正则化的学习方法就是一种嵌入式特征选择方法,其特征选择过程与学习器训练过程融为一体,二者同时完成。
L 1 L_1 L 1 正则化问题的求解可以用近端梯度下降Proximal Gradient Descent:PGD
算法求解。
对于优化目标:min x ⃗ f ( x ⃗ ) + λ ∣ ∣ x ⃗ ∣ ∣ 1 \min_{\mathbf{\vec x}} f(\mathbf{\vec x})+\lambda||\mathbf{\vec x}||_1 min x f ( x ) + λ ∣∣ x ∣ ∣ 1 ,若f ( x ⃗ ) f(\mathbf{\vec x}) f ( x ) 可导且∇ f \nabla f ∇ f 满足L-Lipschitz
条件,即存在常数L > 0 L \gt 0 L > 0 使得:
∣ ∣ ∇ f ( x ⃗ ) − ∇ f ( x ⃗ ′ ) ∣ ∣ 2 2 ≤ L ∣ ∣ x ⃗ − x ⃗ ′ ∣ ∣ 2 2 , ∀ ( x ⃗ , x ⃗ ′ ) ||\nabla f(\mathbf{\vec x})-\nabla f(\mathbf{\vec x}^{\prime})||_2^{2} \le L ||\mathbf{\vec x}-\mathbf{\vec x}^{\prime} ||_2^{2},\;\forall( \mathbf{\vec x},\mathbf{\vec x}^{\prime}) ∣∣∇ f ( x ) − ∇ f ( x ′ ) ∣ ∣ 2 2 ≤ L ∣∣ x − x ′ ∣ ∣ 2 2 , ∀ ( x , x ′ )
则在x ⃗ 0 \mathbf{\vec x}_0 x 0 附近将f ( x ⃗ ) f(\mathbf{\vec x}) f ( x ) 通过二阶泰勒公式展开的近似值为:
f ^ ( x ⃗ ) ≃ f ( x ⃗ 0 ) + ∇ f ( x ⃗ 0 ) ⋅ ( x ⃗ − x ⃗ 0 ) + L 2 ∣ ∣ x ⃗ − x ⃗ 0 ∣ ∣ 2 2 = L 2 ∣ ∣ x ⃗ − ( x ⃗ 0 − 1 L ∇ f ( x ⃗ 0 ) ) ∣ ∣ 2 2 + c o n s t \hat f(\mathbf{\vec x})\simeq f(\mathbf{\vec x}_0)+\nabla f(\mathbf{\vec x}_0)\cdot (\mathbf{\vec x}-\mathbf{\vec x}_0)+\frac L2|| \mathbf{\vec x}-\mathbf{\vec x}_0||_2^{2}\\ =\frac L2||\mathbf{\vec x}- (\mathbf{\vec x}_0-\frac 1L\nabla f(\mathbf{\vec x}_0) ) ||_2^{2}+const f ^ ( x ) ≃ f ( x 0 ) + ∇ f ( x 0 ) ⋅ ( x − x 0 ) + 2 L ∣∣ x − x 0 ∣ ∣ 2 2 = 2 L ∣∣ x − ( x 0 − L 1 ∇ f ( x 0 )) ∣ ∣ 2 2 + co n s t
其中c o n s t const co n s t 是与x ⃗ \mathbf{\vec x} x 无关的常数项。
若通过梯度下降法对f ( x ⃗ ) f(\mathbf{\vec x}) f ( x ) 进行最小化,则每一步梯度下降迭代实际上等价于最小化二次函数f ^ ( x ⃗ ) \hat f(\mathbf{\vec x}) f ^ ( x ) 。
同理,若通过梯度下降法对f ( x ⃗ ) + λ ∣ ∣ x ⃗ ∣ ∣ 1 f(\mathbf{\vec x})+\lambda||\mathbf{\vec x}||_1 f ( x ) + λ ∣∣ x ∣ ∣ 1 进行最小化,则每一步梯度下降迭代实际上等价于最小化函数:f ^ ( x ⃗ ) + λ ∣ ∣ x ⃗ ∣ ∣ 1 \hat f(\mathbf{\vec x})+\lambda||\mathbf{\vec x}||_1 f ^ ( x ) + λ ∣∣ x ∣ ∣ 1 。
则每一步迭代为:
x ⃗ = arg min x ⃗ L 2 ∣ ∣ x ⃗ − ( x ⃗ − 1 L ∇ f ( x ⃗ ) ) ∣ ∣ 2 2 + λ ∣ ∣ x ⃗ ∣ ∣ 1 \mathbf{\vec x}^{}= \arg\min_{\mathbf{\vec x}}\frac L2||\mathbf{\vec x}- (\mathbf{\vec x}^{}-\frac 1L\nabla f(\mathbf{\vec x}^{}) ) ||_2^{2} +\lambda||\mathbf{\vec x} ||_1 x = arg x min 2 L ∣∣ x − ( x − L 1 ∇ f ( x )) ∣ ∣ 2 2 + λ ∣∣ x ∣ ∣ 1
其中x ⃗ < k > \mathbf{\vec x}^{<k>} x < k > 为x ⃗ \mathbf{\vec x} x 的第k k k 次迭代的值。
该问题有解析解,因此通过PGD
能够使得LASSO
和其他基于L 1 L_1 L 1 范数最小化的方法能够快速求解。
常见的嵌入式选择模型:
优点 :对特征进行搜索时围绕学习算法展开的,能够考虑学习算法所属的任意学习偏差。训练模型的次数小于 Wrapper 方法,比较节省时间。
缺点 :运行速度慢。
主成分分析 (Principle Components Analysis ,PCA) 和线性评判分析(Linear Discriminant Analysis,LDA)是特征抽取的两种主要经典方法。
对于特征抽取,有两种类别:
(1)Signal representation(信号表示): The goal of the feature extraction mapping is to represent the samples accurately in a low-dimensional space. 也就是说,特征抽取后的特征要能够精确地表示样本信息,使得信息丢失很小。对应的方法是 PCA.
(2)Signal classification(信号分类): The goal of the feature extraction mapping is toenhance the class-discriminatory information in a low-dimensional space. 也就是说,特征抽取后的特征,要使得分类后的准确率很高,不能比原来特征进行分类的准确率低。对与线性来说,对应的方法是 LDA . 非线性这里暂时不考虑。
可见, PCA 和 LDA 两种方法的目标不一样,因此导致他们的方法也不一样。PCA 得到的投影空间是协方差矩阵的特征向量,而 LDA 则是通过求得一个变换 W, 使得变换之后的新均值之差最大、方差最大(也就是最大化类间距离和最小化类内距离),变换 W 就是特征的投影方向。
降维方法(特征提取) 主成分分析(PCA) PCA(Principal Component Analysis),即主成分分析 方法,是一种使用最广泛的数据降维 算法。
降维就是一种对高维度特征数据预处理方法。降维是将高维度的数据保留下最重要的一些特征,去除噪声和不重要的特征,从而实现提升数据处理速度的目的 。在实际的生产和应用中,降维在一定的信息损失范围内,可以为我们节省大量的时间和成本。降维也成为应用非常广泛的数据预处理方法。降维的算法有很多,比如奇异值分解 (SVD)、主成分分析 (PCA)、因子分析 (FA)、独立成分分析 (ICA)。
PCA 的主要思想是将 n 维特征映射到 k 维上 ,这 k 维是全新的正交特征也被称为主成分,是在原有 n 维特征的基础上重新构造出来的 k 维特征。
PCA 的工作就是从原始的空间中顺序地找一组相互正交的坐标轴,新的坐标轴的选择与数据本身是密切相关的。其中,第一个新坐标轴选择是原始数据中方差最大的方向 ,第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的,第三个轴是与第 1,2 个轴正交的平面中方差最大的。依次类推,可以得到 n 个这样的坐标轴。通过这种方式获得的新的坐标轴,我们发现,大部分方差都包含在前面 d 个坐标轴中,后面的坐标轴所含的方差几乎为 0。于是,我们可以忽略余下的坐标轴,只保留前面 d 个含有绝大部分方差的坐标轴。
算法与思想 PCA 是基于最近重构性 和最大可分性 而得到的方法。
PCA 通过协方差矩阵的特征值分解来找到这些坐标轴(特征向量),其算法描述为:
推导 数据中心化
首先,我们先对我们的数据中心化。
x i = x i − 1 m ∑ i = 1 m x i x_i = x_i - \frac{1}{m}\sum_{i=1}^mx_i x i = x i − m 1 i = 1 ∑ m x i
最近重构性
我们假定我们的数据(d 维特征)经过了一个投影变换,投影变换后,得到的新坐标系为w 1 , w 2 , … , w d {w_1,w_2,…,w_d} w 1 , w 2 , … , w d ,其中w i w_i w i 是标准正交基向量,∣ ∣ w i ∣ ∣ 2 = 1 ||w_i||_2=1 ∣∣ w i ∣ ∣ 2 = 1 且w i T w j = 0 ( i ≠ j ) w_i^Tw_j=0(i\ne j) w i T w j = 0 ( i = j ) 。
我们可以丢弃新坐标系中的部分坐标,即将维度降低到d ’ < d d’<d d ’ < d 。那么样本点x i x_i x i 在低维空间坐标系中的投影为z i = ( z i 1 ; z i 2 ; … ; z i d ’ ) z_i=(z_{i1};z_{i2};…;z_{id’}) z i = ( z i 1 ; z i 2 ; … ; z i d ’ ) ,其中z i j = w j T x i z_{ij}=w_j^Tx_i z ij = w j T x i 是x i x_i x i 在低维坐标系下第j j j 维的坐标,若基于z i z_i z i 来重构x i x_i x i ,则会得到x i ^ = ∑ j = 1 d ’ z i j w j \hat{x_i} = \sum_{j=1}^{d’}z_{ij}w_j x i ^ = ∑ j = 1 d ’ z ij w j 。
考虑整个训练集,原样本点x i x_i x i 与基于投影重构的样本点x i ^ \hat{x_i} x i ^ 的距离为:
∑ i = 1 m ∣ ∣ ∑ j = 1 d ′ z i j w j − x i ∣ ∣ 2 2 = ∑ i = 1 m [ ( ∑ j = 1 d ′ z i j w j ) 2 − 2 ∑ j = 1 d ′ z i j w j x i + x i 2 ] = ∑ i = 1 m [ z i T z i − 2 z i T W T x i + x i 2 ] = ∑ i = 1 m z i T z i − 2 ∑ i = 1 m z i T W T x i + c o n s t ∝ − t r ( W T ( ∑ i = 1 m x i x i T ) W ) \begin{equation} \begin{split} \sum_{i=1}^m||\sum_{j=1}^{d'}z_{ij}w_j - x_i||_2^2 &=\sum_{i=1}^m[(\sum_{j=1}^{d'}z_{ij}w_j)^2 - 2\sum_{j=1}^{d'}z_{ij}w_jx_i + x_i^2]\\ &=\sum_{i=1}^m[z_i^Tz_i - 2z_i^TW^Tx_i + x_i^2]\\ &=\sum_{i=1}^mz_i^Tz_i - 2\sum_{i=1}^mz_i^TW^Tx_i + const\\ &\propto -tr(W^T(\sum_{i=1}^mx_ix_i^T)W)\\ \end{split} \end{equation} i = 1 ∑ m ∣∣ j = 1 ∑ d ′ z ij w j − x i ∣ ∣ 2 2 = i = 1 ∑ m [( j = 1 ∑ d ′ z ij w j ) 2 − 2 j = 1 ∑ d ′ z ij w j x i + x i 2 ] = i = 1 ∑ m [ z i T z i − 2 z i T W T x i + x i 2 ] = i = 1 ∑ m z i T z i − 2 i = 1 ∑ m z i T W T x i + co n s t ∝ − t r ( W T ( i = 1 ∑ m x i x i T ) W )
其中W = ( w 1 , w 2 , … , w d ’ ) W = (w_1,w_2,…,w_{d’}) W = ( w 1 , w 2 , … , w d ’ ) 。
根据最近重构性,上面的式子应该被最小化,我们知道w j w_j w j 是标准正交基,且∑ i x i x i T \sum_ix_ix_i^T ∑ i x i x i T 是协方差矩阵,所以我们的目标函数 为:
m i n W − t r ( W T X X T W ) s . t . W T W = I \begin{equation} \begin{split} min_W& \quad \ -tr(W^TXX^TW)\\ s.t.& \quad \ W^TW=I \\ \end{split} \end{equation} mi n W s . t . − t r ( W T X X T W ) W T W = I
最大可分性
我们知道,样本点x i x_i x i 在新空间中超平面上的投影是W T x i W^Tx_i W T x i ,若所有样本点的投影能尽可能分开,则应该使投影后样本点的方差最大化,而投影点后的方差是∑ i W T x i x i T W \sum_iW^Tx_ix_i^TW ∑ i W T x i x i T W ,于是基于最大可分性,我们得到的目标函数依然是:
m i n W − t r ( W T X X T W ) s . t . W T W = I \begin{equation} \begin{split} min_W& \quad \ -tr(W^TXX^TW)\\ s.t.& \quad \ W^TW=I \\ \end{split} \end{equation} mi n W s . t . − t r ( W T X X T W ) W T W = I
特征向量求解
我们对上面的目标函数使用拉格朗日乘子法可得:
X X T W = λ W XX^TW = \lambda W X X T W = λW
于是,我们只需要对协方差矩阵X X T XX^T X X T 进行特征值分解,讲求得的特征值排序:λ 1 ≥ λ 2 ≥ … λ d \lambda_1 \ge \lambda_2 \ge …\lambda_d λ 1 ≥ λ 2 ≥ … λ d ,再取前d ’ d’ d ’ 个特征值对应的特征向量构成W = ( w 1 , w 2 , … , w d ’ ) W=(w_1,w_2,…,w_{d’}) W = ( w 1 , w 2 , … , w d ’ ) ,这就是主成分分析的解。
d‘的选取
降维后低维空间的维数d ’ d’ d ’ 通常是由用户事先制定,我们可以设置一个阈值t = 95 t=95% t = 95 ,使得d ’ d’ d ’ 满足:
∑ i = 1 d ′ λ i ∑ i = 1 d λ i ≥ t \frac{\sum_{i=1}^{d'}\lambda_i}{\sum_{i=1}^{d}\lambda_i} \ge t ∑ i = 1 d λ i ∑ i = 1 d ′ λ i ≥ t
降维的优点 :
使得数据集更易使用。
降低算法的计算开销。
去除噪声。
使得结果容易理解。
优点 :
仅仅需要以方差衡量信息量,不受数据集以外的因素影响。 各主成分之间正交,可消除原始数据成分间的相互影响的因素。 计算方法简单,主要运算是特征值分解,易于实现。 缺点:
主成分各个特征维度的含义具有一定的模糊性,不如原始样本特征的解释性强。 方差小的非主成分也可能含有对样本差异的重要信息,因降维丢弃可能对后续数据处理有影响。
线性判别分析(LDA) 线性判别分析(Linear Discriminant Analysis,LDA)是一种经典的降维方法。和主成分分析 PCA 不考虑样本类别输出的无监督降维技术不同,LDA 是一种监督学习的降维技术,数据集的每个样本有类别输出。LDA 算法的思想是将数据投影到低维空间之后,使得同一类数据尽可能的紧凑,不同类的数据尽可能分散 。LDA 也是一种线性分类器,其不需要迭代式的进行训练,可以根据数据集,利用优化算法直接得到权重。
LDA 有如下两个假设:
原始数据根据样本均值 进行分类。
不同类的数据拥有相同的协方差矩阵。
LDA 分类思想简单总结如下:
多维空间中,数据处理分类问题较为复杂,LDA 算法将多维空间中的数据投影到一条直线上,将 d 维数据转化成 1 维数据进行处理。 对于训练数据,设法将多维数据投影到一条直线上,同类数据的投影点尽可能接近,异类数据点尽可能远离。 对数据进行分类时,将其投影到同样的这条直线上,再根据投影点的位置来确定样本的类别。 如果用一句话概括 LDA 思想,即 “投影后类内方差最小,类间方差最大”。 假设有红、蓝两类数据,这些数据特征均为二维,如下图所示。我们的目标是将这些数据投影到一维,让每一类相近的数据的投影点尽可能接近,不同类别数据尽可能远,即图中红色和蓝色数据中心之间的距离尽可能大。
左图和右图是两种不同的投影方式。
左图思路:让不同类别的平均点距离最远的投影方式。 右图思路:让同类别的数据挨得最近的投影方式。 从上图直观看出,右图红色数据和蓝色数据在各自的区域来说相对集中,根据数据分布直方图也可看出,所以右图的投影效果好于左图,左图中间直方图部分有明显交集。
以上例子是基于数据是二维的,分类后的投影是一条直线。如果原始数据是多维的,则投影后的分类面是一低维的超平面。
算法 对于 N 分类问题,模型输入x x x ,模型参数w w w ,模型输出h ( x ) h(x) h ( x ) (N 维向量),预测标签y y y
h ( x ) = w T x + w 0 y = a r g m a x k h ( x ) h(x) = w^Tx + w_0 \\ y = argmax_k\ h(x) h ( x ) = w T x + w 0 y = a r g ma x k h ( x )
我们先以二分类任务为例,进行数学公式的推导。D D D 表示数据集,D i D_i D i 表示类别i i i 的数据。
计算类别 i 数据的原始中心点 :
μ i = 1 n i ∑ x ∈ D i x \mu_i = \frac{1}{n_i}\sum_{x \in D_i} x μ i = n i 1 x ∈ D i ∑ x
计算类别 i 数据投影后的中心点 :
μ i ~ = w T ⋅ μ i \tilde{\mu_i} = w^T·\mu_i μ i ~ = w T ⋅ μ i
其用来衡量投影后,不同类别间的距离
得到每个数据投影后的点 :
z = w T x z = w^Tx z = w T x
计算类别 i 数据投影后的方差(数据之间的分散程度)
s i ~ 2 = ∑ z ∈ Z i ( z − μ i ~ ) 2 \tilde{s_i}^2 = \sum_{z\in Z_i}(z - \tilde{\mu_i})^2 s i ~ 2 = z ∈ Z i ∑ ( z − μ i ~ ) 2
其用来衡量投影后,同一类别内数据的距离
最终,得到投影后的损失函数(二分类)
J ( w ) = ( μ 1 ~ − μ 2 ~ ) 2 s 1 ~ 2 + s 2 ~ 2 J(w) = \frac{(\tilde{\mu_1} - \tilde{\mu_2})^2}{\tilde{s_1}^2+\tilde{s_2}^2} J ( w ) = s 1 ~ 2 + s 2 ~ 2 ( μ 1 ~ − μ 2 ~ ) 2
对上面的式子进行带入展开
J ( w ) = ( w T μ 1 − w T μ 2 ) 2 ∑ x ∈ D 1 ( w T x − w T μ 1 ) 2 + ∑ x ∈ D 2 ( w T x − w T μ 2 ) 2 = w T ( μ 1 − μ 2 ) ( μ 1 − μ 2 ) T w ∑ x ∈ D 1 ( w T ( x − μ 1 ) ( x − μ 1 ) T w ) + ∑ x ∈ D 2 ( w T ( x − μ 2 ) ( x − μ 2 ) T w ) J(w) = \frac{(w^T\mu_1 - w^T\mu_2)^2}{\sum_{x\in D_1}(w^Tx-w^T\mu_1)^2+\sum_{x\in D_2}(w^Tx-w^T\mu_2)^2} \\ \qquad =\frac{w^T(\mu_1 - \mu_2)(\mu_1 - \mu_2)^Tw}{\sum_{x\in D_1}(w^T(x - \mu_1)(x - \mu_1)^Tw)+\sum_{x\in D_2}(w^T(x - \mu_2)(x - \mu_2)^Tw)} J ( w ) = ∑ x ∈ D 1 ( w T x − w T μ 1 ) 2 + ∑ x ∈ D 2 ( w T x − w T μ 2 ) 2 ( w T μ 1 − w T μ 2 ) 2 = ∑ x ∈ D 1 ( w T ( x − μ 1 ) ( x − μ 1 ) T w ) + ∑ x ∈ D 2 ( w T ( x − μ 2 ) ( x − μ 2 ) T w ) w T ( μ 1 − μ 2 ) ( μ 1 − μ 2 ) T w
我们记S B = ( μ 1 − μ 2 ) ( μ 1 − μ 2 ) T S_B=(\mu_1 - \mu_2)(\mu_1 - \mu_2)^T S B = ( μ 1 − μ 2 ) ( μ 1 − μ 2 ) T ,S i = ∑ x ∈ D i ( x − μ i ) ( x − μ i ) 2 S_i = \sum_{x\in D_i}(x-\mu_i)(x-\mu_i)^2 S i = ∑ x ∈ D i ( x − μ i ) ( x − μ i ) 2 ,S w = ∑ i N S i S_w = \sum_i^NS_i S w = ∑ i N S i
则上面的式子,我们可以简化为:
J ( w ) = w T S B w w T S w w J(w) = \frac{w^TS_Bw}{w^TS_ww} J ( w ) = w T S w w w T S B w
推广到多分类
在多分类任务中,S B S_B S B 等于所有的μ \mu μ 两两相减的平方 的加和,S w S_w S w 等于所有的S i S_i S i 的加和
使用拉格朗日乘子法求解权重
在拉格朗日乘子法中,我们需要对分母进行限制,限制其等于 1。这个限制条件跟 SVM 中的限制是一个道理,是为了防止权重的倍数增长而造成的有无穷多个解的问题,比如 1/1=1, 而 2/2=1,我们加了限制条件,就只有了第一种可能性,这让我们可以使用拉格朗日算法
c ( w ) = w T S B w − λ ( w T S w w − 1 ) ⇒ d c d w = 2 S B w − 2 λ S w w = 0 ⇒ 2 S B w = 2 λ S w w c(w) = w^TS_Bw - \lambda(w^TS_ww-1) \\ \Rightarrow \frac{dc}{dw} = 2S_Bw - 2\lambda S_ww = 0 \\ \Rightarrow 2S_Bw = 2\lambda S_ww c ( w ) = w T S B w − λ ( w T S w w − 1 ) ⇒ d w d c = 2 S B w − 2 λ S w w = 0 ⇒ 2 S B w = 2 λ S w w
我们可以利用线性代数求特征值的方法求解 w
优点
缺点
当数据不是高斯分布时候,效果不好,PCA 也是。 降维之后的维数最多为 类别数 - 1,因为在进行拉格朗日求解时,我们能够得到的特征向量的数目为 x 的秩 - 1。
比较这两种方法 降维的必要性:
多重共线性和预测变量之间相互关联。多重共线性会导致解空间的不稳定,从而可能导致结果的不连贯。 高维空间本身具有稀疏性。一维正态分布有 68% 的值落于正负标准差之间,而在十维空间上只有 2%。 过多的变量,对查找规律造成冗余麻烦。 仅在变量层面上分析可能会忽略变量之间的潜在联系。例如几个预测变量可能落入仅反映数据某一方面特征的一个组内。 降维的目的:
减少预测变量的个数。 确保这些变量是相互独立的。 提供一个框架来解释结果。相关特征,特别是重要特征更能在数据中明确的显示出来;如果只有两维或者三维的话,更便于可视化展示。 数据在低维下更容易处理、更容易使用。 去除数据噪声。 降低算法运算开销。 LDA 和 PCA 区别
KPCA pass
参考 https://zhuanlan.zhihu.com/p/134089340
https://github.com/Vay-keen/Machine-learning-learning-notes
https://github.com/familyld/Machine_Learning
https://zhuanlan.zhihu.com/p/25994179
https://leovan.me/cn/2018/12/ensemble-learning/
https://easyai.tech/ai-definition/ensemble-learning/
https://zhuanlan.zhihu.com/p/72415675
https://www.zhihu.com/question/63492375
https://www.zhihu.com/question/27068705
https://www.zhihu.com/question/19725590/answer/241988854
https://tangshusen.me/2018/10/27/SVM/
https://www.joinquant.com/view/community/detail/a98b7021e7391c62f6369207242700b2
https://zhuanlan.zhihu.com/p/79531731
https://github.com/Charmve/PaperWeeklyAI/blob/master/03_Maiwei AI PaperWeekly/03_机器学习%26深度学习理论/机器学习算法之——K最近邻(k-Nearest Neighbor,KNN)分类算法原理讲解.md
https://blog.csdn.net/zc02051126/article/details/49618633
https://zhuanlan.zhihu.com/p/127022333
https://0809zheng.github.io/2020/03/30/ridge.html
https://www.cnblogs.com/wuliytTaotao/p/10837533.html
https://link.springer.com/referenceworkentry/10.1007/978-1-4899-7687-1_910#Sec13186
http://palm.seu.edu.cn/zhangml/files/mla11-mll.pdf
https://blog.csdn.net/zwqjoy/article/details/80431496
https://ryuchen.club/posts/0x000034/ (推荐)
https://zhuanlan.zhihu.com/p/78798251
https://zhuanlan.zhihu.com/p/622244758
https://www.biaodianfu.com/hierarchical-clustering.html
https://zhuanlan.zhihu.com/p/411533418
https://zhuanlan.zhihu.com/p/33196506
https://www.cnblogs.com/wry789/p/13125658.html
https://blog.csdn.net/qq_41485273/article/details/113178117
https://www.jianshu.com/p/7d4323c28716
http://lunarnai.cn/2019/01/02/watermelon-chap-13/
【周志华机器学习】十三、半监督学习
https://zhuanlan.zhihu.com/p/411533418
https://www.huaxiaozhuan.com/统计学习/chapters/12_semi_supervised.html
https://blog.csdn.net/tyh70537/article/details/80244490
https://zhuanlan.zhihu.com/p/37747650
7125messi.github.io
https://blog.csdn.net/qq_40722827/article/details/104515955
https://www.cnblogs.com/dyl222/p/11055756.html
https://www.zhihu.com/tardis/zm/art/392908965
https://blog.csdn.net/j123kaishichufa/article/details/7679682
https://www.cnblogs.com/heaad/archive/2011/01/02/1924088.html
https://www.cnblogs.com/stevenlk/p/6543628.html
baidinghub.github.io-PCA
baidinghub.github.io-LDA
等等
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ZWN's blog !