特征选择方法

​ 和上一章的降维有点类似，同样是样本的属性太多，在进行距离计算或者其他训练推理的计算过程中，会大大的增加计算量。所以通过某些规则选择出相对重要的一些属性出来，从而实现降维。

​ 另外，去除掉一些七七八八的属性，就凸显出了关键的属性，对一些业务的开展更有指导意义。比如在智能决策系统中，只给出5个影响因素总比给出50个影响因素要好理解的多。

​ 如果样本有$d$个属性，为了知道哪几个属性能代表整个样本。最简单的办法就是把所有的属性选择子集全部试一遍：那么子集的个数就会是$C_d^1+C_d^2+\cdots +C_d^d$。我们通常是在$d$非常大的时候才做这个特征选择，但$d$很大的话，刚才的这个公式是个天文数字，很明显无法采用这种方法。

​ 所以特征选择就是一个属性子集的挑选过程：

子集选择方法一：候选子集方法

​ 候选子集方法是基于贪心策略的，过程如下：

• 将所有的单个属性作为一个候选子集，第一轮就有$d$个候选子集。根据某种评价标准选出其中最优的，比如是 { x 2 } \lbrace x_2 \rbrace { x2​}

• 在第一轮选出的子集上再增加一个属性，那么此轮就只有$d-1$个候选子集： { x 2 , x i ( i ≠ 2 ) } \lbrace x_2, x_{i(i\neq2)}\rbrace { x2​,xi(i​=2)​}，在这$d-1$个候选子集中再根据同样的标准选出最优的一个。这里可以用之前提到的信息熵的方法来进行两个子集的评价：

• 依次类推，知道第$n,n<d$轮，所有的$d-n$个候选子集都没有上一轮的好，那么就停止，以$n-1$轮选择出来的那个子集作为特征选择的输出结果。

• 搞过算法的朋友们都知道，基于贪心的是容易进入到局部最优的，可能 { x 2 , x 3 , x 5 } \lbrace x_2, x_3, x_5 \rbrace { x2​,x3​,x5​}在就是最好的子集，但是另外一种组合 { x 2 , x 4 , x 6 } \lbrace x_2,x_4,x_6 \rbrace { x2​,x4​,x6​}是更好的，是因为$x_4$和$x_6$加起来比$x_3$和$x_5$号。这个是贪心算法无法解决的，不过好像可以通过动态规划去解决，后续再研究去。

子集选择方法二：Relief方法

​ 该方法是基于最近邻算法的，基本的Relief方法是面向二分类问题的，假设样本集为$(x_1,y_1),\dots (x_m,y_m)$：

• 对于每个样本$x_i$，首先根据某种距离度量方法，找到两个最近邻：样本类别相同的最近邻$x_{i,nh}$，称为“猜中近邻(near_hit)”。样本不同的最近邻$x_{i,nm}$，称为"猜错近邻(near_miss)"。

• 对于样本集中的某个属性$j$，计算$j$的一个统计值：
  $${\delta }_j=\sum _{i=1}^m-diff(x_i^j,x_{i,nh}^j{)}^2+diff(x_i^j,x_{i,hm}{)}^2$$
  其中$diff$函数是计算两个样本之间的差异，如果属性$j$为离散型，那么只有当两个样本的属性$j$相同时，$diff$函数等于1，否则等于0。如果$j$是连续属性，那么$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$在属性$j$上与猜中近邻的距离小于与猜错近邻上的距离，那么说明这个属性是对于分类有益的，就需要增大这个值，反之就需要减少这个统计值。从公式上看，如果样本$x_i$在属性$j$上与猜中近邻的距离小于与猜错近邻上的距离，这个统计值就为正数，反之为负数。

  然后针对这个属性$j$，把所有的样本全部进行求和，就得到了这个属性$j$在样本集上的统计值。

• 对于样本集中的所有$d$个属性，全部根据上面的公式进行计算，得到一个统计向量： { δ 1 , δ 2 … δ d } \lbrace \delta_1,\delta_2\dots \delta_d \rbrace { δ1​,δ2​…δd​}。可以通过两种方法来从中选属性子集了。

  • 要求为统计值不小于$\tau$的所有属性
  • 要求为前top N的所有属性

​ 该算法如果是针对多分类问题，那么上面提到的最近邻就不适用了，需要做点改造。

• 假设是k分类问题，猜中近邻就是和样本$x_i$类别相同的，猜错近邻变成了从其他$k-1$类中都找出一个来。通过：
  $${\delta }_j=\sum _{i=1}^m-diff(x_i^j,x_{i,nh}^j{)}^2+\sum _{l\ne k}{p}_l\ast diff(x_i^j,x_{i,l,hm}{)}^2$$
  公式来计算。

• 其中的$p_l$为$l$类样本在数据集中所占的比例。

​

​ 像Relief这种纯粹从样本本身的规律来找子集的方法被称为过滤式选择方法，也就是先过滤再训练学习器。

子集选择方法三：LVW(Las Vegas Wrapper)

​ LVW方法思路很简单，就是子集好不好，试了才知道，直接用放到学习器中去测试一下就知道了。

• 一般采用最大循环次数来控制计算过程
• 每次循环都是在上一次的基础上随机产生特征子集
• 如果错误率降低了，或者说错误率相同，但是本次的属性数比上一次的少，也算成功。

​ 这种直接用学习器来评价的，称作嵌入式方法。这种明显的会提高某种学习器的性能，毕竟是量身定做，但是费得计算量就比较高了。

稀疏表达与字典学习

​ 如果把数据集看成一个矩阵，矩阵的每一行代表一个样本，每一列为一个属性。那么特征选择就是在矩阵中挑选出一些列去掉。如果列比较多，而没用的列也比较多，可以看成是一个稀疏的矩阵。

​ 而更加普遍的一种稀疏矩阵是指矩阵中有很多零元素。书中是提到一个例子，也就是文本分类的例子：

• 每个文本是一个样本，也就是矩阵中的一行

• 矩阵的列的话是一个字典组合，拿文本的例子来说的话，就是比如新华字典之类，新化字典中的每个字或者词可以成为一个列

• 矩阵中的元素$m_{ij}$表示样本中某个词的出现次数。当然，字典中的列必须把样本中所有的字或者词包含进去，或者有单独的处理办法。至于是分词还是分字咱在这不考虑这个问题。

• 那么字典学习是想通过一种学习方式学得一个字典，有足够的稀疏性(是可以线性可分，在SVM那一章提到过，如果低维无法线性可分，升维就可以，增加字典的字数就是在增加属性数，增加样本维度)；但有不能太多维，一是浪费存储空间，二是增加了也不一定有用。

  通过优化目标：
  $$\underset{B,{\alpha }_i}{\min }\sum _{i=1}^m||x_i-B{\alpha }_i|{|}_2^2+\lambda \sum _{i=1}^m||\alpha |{|}_1$$
  经过一些看不到的骚操作解出字典矩阵$B\in R^{d\ast k}$，k为字典的维数。

​ 我这里只记录一下这个字典学习的思路，后续有需要了再回头来看。