【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.过滤式选择
过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。这相当于先用特征选择过程对初始特征进行“过滤”，再用过滤后的特征来训练模型。
Relief（Relevant Features）是一种著名的过滤式特征选择方法，该方法设计了一个“相关统计量”来度量特征的重要性。该统计量是一个向量，其每个分量分别对应于一个初始特征，而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定。于是，最终只需指定一个阈值$\tau$，然后选择比$\tau$大的相关统计量分量所对应的特征即可；也可指定欲选取的特征个数$k$，然后选择相关统计量分量最大的$k$个特征。
显然，Relief的关键是如何确定相关统计量。给定训练集$\{ (\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_m,y_m) \}$，对每个示例$\mathbf{x}_i$，Relief先在$\mathbf{x}_i$的同类样本中寻找其最近邻$\mathbf{x}_{i,nh}$，称为“猜中近邻”（near-hit），再从$\mathbf{x}_i$的异类样本中寻找其最近邻$\mathbf{x}_{i,nm}$，称为“猜错近邻”（near-miss），然后，相关统计量对应于属性$j$的分量为：
\[\delta^j = \sum_{i} -\text{diff} (x_i^j,x_{i,nh}^j)^2+\text{diff} (x_i^j,x_{i,nm}^j)^2 \tag{1}\]其中$x_a^j$表示样本$\mathbf{x}_a$在属性$j$上的取值，$\text{diff}(x_a^j,x_b^j)$取决于属性$j$的类型：若属性$j$为离散型，则$x_a^j=x_b^j$时$\text{diff}(x_a^j,x_b^j)=0$，否则为1；若属性$j$为连续型，则$\text{diff}(x_a^j,x_b^j)=\lvert x_a^j-x_b^j \rvert$，注意$x_a^j,x_b^j$已规范化到$[0,1]$区间。
从式(1)可看出，若$\mathbf{x}_i$与其猜中近邻$\mathbf{x}_{i,nh}$在属性$j$上的距离小于$\mathbf{x}_i$与其猜错近邻$\mathbf{x}_{i,nm}$的距离，则说明属性$j$对区分同类与异类样本是有益的，于是增大属性$j$所对应的统计量分量；反之，若$\mathbf{x}_i$与其猜中近邻$\mathbf{x}_{i,nh}$在属性$j$上的距离大于$\mathbf{x}_i$与其猜错近邻$\mathbf{x}_{i,nm}$的距离，则说明属性$j$起负面作用，于是减小属性$j$所对应的统计量分量。最后，对基于不同样本得到的估计结果进行平均，就得到各属性的相关统计量分量，分量值越大，则对应属性的分类能力就越强。
式(1)中的$i$指出了用于平均的样本下标。实际上Relief只需在数据集的采样上而不必在整个数据集上估计相关统计量。显然，Relief的时间开销随采样次数以及原始特征数线性增长，因此是一个运行效率很高的过滤式特征选择算法。
Relief是为二分类问题设计的，其扩展变体Relief-F能处理多分类问题。假定数据集$D$中的样本来自$\lvert \mathcal{Y} \rvert$个类别。对示例$\mathbf{x}_i$，若它属于第$k$类（$k \in \{1,2,…,\lvert \mathcal{Y} \rvert \}$），则Relief-F先在第$k$类的样本中寻找$x_i$的最近邻示例$\mathbf{x}_{i,nh}$并将其作为猜中近邻，然后在第$k$类之外的每个类中找到一个$\mathbf{x}_i$的最近邻示例作为猜错近邻，记为$\mathbf{x}_{i,l,nm}$（$l=1,2,…,\lvert \mathcal{Y} \rvert; l\neq k$）。于是，相关统计量对应于属性$j$的分量为：
\[\delta^j = \sum_i - \text{diff}(x_i^j,x_{i,nh}^j)^2 + \sum_{l\neq k} (p_l \times \text{diff} (x_i^j,x_{i,l,nm}^j)^2) \tag{2}\]其中$p_l$为第$l$类样本在数据集$D$中所占的比例。
