Created by potrace 1.13, written by Peter Selinger 2001-2015

特征选择

特征选择的原理通常有两种:

方法1,根据模型的评估结果,尝试不同的特征组合,从而选择出最优的特征集.
一开始我们只选择一个属性 a_1 ,然后增加随机增加属性 a_1,a_3 ,如果评估结果比之前好的话就保留增加的属性,否则换其他属性.这种选择方法叫做向前搜索.
向前搜索是逐个往属性集中添加属性,那么一开始使用所有的属性,然后根据评估结果的好坏随机剔除属性的方法叫做向后搜索.

方法2,根据特征对分类起到的作用来选择最优的特征集.
我们可以通过计算每个属性的信息增益来确定,哪个属性对分类最有用:
Gain(D,a) = Ent(D) - \sum_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v)

通过将以上两种方案相结合,即是特征选择方法.常见的特征选择方法有过滤式、包裹式、嵌入式.

过滤式选择

过滤式选择采用的是第二种方法,也就是在模型训练之前,把特征选择出来.

直接计算所有属性的信息增益的话会产生类似决策树一样的算法.事实上可以使用决策树来做特征选择.不过我们这里介绍一个更加高效的特征选择算法Relief.

Relief算法设计了一个"相关统计量"来度量特征特征的重要性。属性j的相关统计量为:

\delta^j=\sum_i{-diff(x_i^j, x_{i,nh}^j)^2+ diff(x_i^j, x_{i,nm}^j)^2}

其中， x_a^j 代表样本 x_a 在属性 j 上的取值， x_{i,nh} 为 x_a^j 同类别的最近邻称为是"猜中近邻", x_{i,nm} 为 x_a^j 非同类别的最近邻称为是"猜错近邻".

diff(x_a^j,x_b^j) 的计算取决于属性 j 的类型:
对离散型属性

diff(x_a^j,x_b^j)= \begin{cases} 0, & x_a^j=x_b^j \\ 1, & otherwise \end{cases}

对连续型属性:

diff(x_a^j,x_b^j)=| x_a^j-x_b^j |
x_a^j ， x_b^j 已经规范化到 [0,1] 区间

若 x_i 与其猜中近邻 x_{i,nh} 在属性 j 上的距离小于 x_i 与其非同类别的最近邻 x_{i,nm} 的距离，则说明属性 j 对区分同类与异类样本是有利的，反之则不利，因此相关统计量的值越大则说明该属性的分类能力越强。最后，对基于不同样本得到的估计结果进行平均,就得到各属性的相关统计量分量,分量值越大，则对应属性的分类能力就越强.

实际上Relief算法只需在数据集的采样上运行即可,不必在整个数据集上运行.

Relief 算法只能直接处理两分类的特征选择，改进的 Relief-F 算法能够处理多分类问题，它将多分类视为是一类对多类直接加以解决。其方法是寻找当前样本的各类最近邻点并综合加以计算.

假设数据集为 D，该数据集一共包含 |y|个类别，对示例 x_i ，若它属于第 k 类 k\in\{1,2,\cdots, |{\cal y}|\} ，则 Relef-F 算法先在第 k 类的样本中寻找 x_i 的最近邻 x_{i,nh} ，作为样本 x_i 的猜中近邻，然后在第 k 类之外的每个类别的样本中寻找 x_i 的最近邻 x_{i,l,nm} (l=1,2,\cdots, |{\cal y}|;l\neq k) ，作为样本 x_i 的猜错近邻，则相关统计量对应于属性 j 的分量为:

\delta^j=\sum_i{-diff(x_i^j, x_{i,nh}^j)^2+\sum_{l\neq k} (p_l \times diff(x_i^j, x_{i,l,nm}^j)^2)}

其中， p_l 为第 l 类样本在数据集 D 中所占的比例。

包裹式选择

包裹式选择使用方法1来做特征选择,著名的算法有拉斯维加斯方法与蒙特卡洛方法.

以下是LVW算法的描述:

image

包裹式选择每次迭代都需要重新训练模型,计算开销很大,不过由于其量身定制的特点,最终的模型性能比过滤式选择要好.

嵌入式选择

嵌入式选择是在模型训练的过程中同时完成特征选择的.常见的方法有L1正则化及L2正则化.

其主思想为讲特征选择参数添加到模型的代价函数J()中,在迭代优化J()的过程中,也会完成特征选择.

L1正则化在代价函数加入参数 \omega 的L1范数.
J(\omega) = J(\omega) + \lambda||\omega||_1

L2正则化在代价函数加入参数 \omega 的L2范数.
J(\omega) = J(\omega) + \lambda||\omega||_2^2

其中 \lambda 为正则化参数.

编程实现:
https://www.kaggle.com/swimmingwhale/relief

参考:
周志华<机器学习>
https://blog.csdn.net/icefire_tyh/article/details/52254562
https://blog.csdn.net/victoriaw/article/details/78532797

posted @ 2018-07-26 20:18:04
评论加载中...
发表评论