特征选择方法

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

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

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

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

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

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

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

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

• 依次类推，知道第 n , n < d n, n<d n,n<d轮，所有的 d − n d-n d−n个候选子集都没有上一轮的好，那么就停止，以 n − 1 n-1 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_4 x4​和 x 6 x_6 x6​加起来比 x 3 x_3 x3​和 x 5 x_5 x5​号。这个是贪心算法无法解决的，不过好像可以通过动态规划去解决，后续再研究去。

子集选择方法二：Relief方法

​ 该方法是基于最近邻算法的，基本的Relief方法是面向二分类问题的，假设样本集为 ( x 1 , y 1 ) , … ( x m , y m ) (x_1,y_1),\dots (x_m,y_m) (x1​,y1​),…(xm​,ym​)：

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

• 对于样本集中的某个属性 j j j，计算 j j j的一个统计值：
  δ j = ∑ i = 1 m − d i f f ( x i j , x i , n h j ) 2 + d i f f ( x i j , x i , h m ) 2 \delta_j = \sum_{i=1}^m{-diff(x_i^j,x_{i,nh}^j)^2+diff(x_i^j,x_{i,hm})^2} δj​=i=1∑m​−diff(xij​,xi,nhj​)2+diff(xij​,xi,hm​)2
  其中 d i f f diff diff函数是计算两个样本之间的差异，如果属性 j j j为离散型，那么只有当两个样本的属性 j j j相同时， d i f f diff diff函数等于1，否则等于0。如果 j j j是连续属性，那么 d i f f ( x a j , x b j ) = ∣ x a j − x b j ∣ , x a j , x b j 已 规 范 化 到 [ 0 , 1 ] 区 间 diff(x_a^j,x_b^j)=|x_a^j-x_b^j|, x_a^j, x_b^j已规范化到[0,1]区间 diff(xaj​,xbj​)=∣xaj​−xbj​∣,xaj​,xbj​已规范化到[0,1]区间。

  那么对于某个样本 x i x_i xi​来说，公式中两部分的含义为：如果样本 x i x_i xi​在属性 j j j上与猜中近邻的距离小于与猜错近邻上的距离，那么说明这个属性是对于分类有益的，就需要增大这个值，反之就需要减少这个统计值。从公式上看，如果样本 x i x_i xi​在属性 j j j上与猜中近邻的距离小于与猜错近邻上的距离，这个统计值就为正数，反之为负数。

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

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

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

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

• 假设是k分类问题，猜中近邻就是和样本 x i x_i xi​类别相同的，猜错近邻变成了从其他 k − 1 k-1 k−1类中都找出一个来。通过：
  δ j = ∑ i = 1 m − d i f f ( x i j , x i , n h j ) 2 + ∑ l ≠ k p l ∗ d i f f ( x i j , x i , l , h m ) 2 \delta_j = \sum_{i=1}^m{-diff(x_i^j,x_{i,nh}^j)^2+\sum_{l\neq k}{p_l*diff(x_i^j,x_{i,l,hm})^2}} δj​=i=1∑m​−diff(xij​,xi,nhj​)2+l​=k∑​pl​∗diff(xij​,xi,l,hm​)2
  公式来计算。

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

​

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

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

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

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

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

稀疏表达与字典学习

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

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

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

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

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

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

  通过优化目标：
  min ⁡ B , α i ∑ i = 1 m ∣ ∣ x i − B α i ∣ ∣ 2 2 + λ ∑ i = 1 m ∣ ∣ α ∣ ∣ 1 \min_{B,\alpha_i}{\sum_{i=1}^m{||x_i-B\alpha_i||_2^2+\lambda\sum_{i=1}^m{||\alpha||_1}}} B,αi​min​i=1∑m​∣∣xi​−Bαi​∣∣22​+λi=1∑m​∣∣α∣∣1​
  经过一些看不到的骚操作解出字典矩阵 B ∈ R d ∗ k B\in R^{d*k} B∈Rd∗k，k为字典的维数。

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