一、特征选择
一般来说，数据集有很多的冗余特征（即没什么用的属性），如果能把这些特征筛选出去，那么我们的程序运行效率就可以得到极大地提高。当然有的时候我们也会人为保留或者创造一些冗余特征，当且仅当这些冗余特征对应了完成任务所需要的“中间概念”时。
那么，如何筛选特征？我们目前常用的特征选择方法有三种：过滤式filter、包裹式wrapper、嵌入式embedding。
1.过滤式选择：
先对初始特征进行过滤，再用过滤后的特征来训练模型。
Relief（Relevant Features）是一种著名的过滤式特征选择方法，它的关键是如何确定相关统计量：先找出“猜中近邻”（near-hit），再找出“猜错近邻”（near-miss），然后根据以下公式算出相关统计量对应于某属性的分量，接着调整属性所对应的统计量分量，最后对基于不同样本得到的估计结果进行平均，就得到各属性的相关统计量分量。
分量值越大，则对应属性的分类能力就越强。
Relief算法的相关代码：
import numpy as np
import pandas as pd
dataset=pd.read_csv('/home/parker/watermelonData/watermelon_3.csv', delimiter=",")
del dataset['编号']
print(dataset)
attributeMap={}
attributeMap['浅白']=0
attributeMap['青绿']=0.5
attributeMap['乌黑']=1
attributeMap['蜷缩']=0
attributeMap['稍蜷']=0.5
attributeMap['硬挺']=1
attributeMap['沉闷']=0
attributeMap['浊响']=0.5
attributeMap['清脆']=1
attributeMap['模糊']=0
attributeMap['稍糊']=0.5
attributeMap['清晰']=1
attributeMap['凹陷']=0
attributeMap['稍凹']=0.5
attributeMap['平坦']=1
attributeMap['硬滑']=0
attributeMap['软粘']=1
attributeMap['否']=0
attributeMap['是']=1
data=dataset.values
m,n=np.shape(data)
for i in range(m):
for j in range(n):
if data[i,j] in attributeMap:
data[i,j]=attributeMap[data[i,j]]
else: data[i,j]=round(data[i,j],3)
X=data[:,:-1]
y=data[:,-1]
m,n=np.shape(X)
# print(X,y)
near=np.zeros((m,2))#near[i,0] is nearHit, near[i,1] is nearMiss
# print(near)
def distance(x1,x2):
return sum((x1-x2)**2)
for i in range(m):
hitDistance=99999 #init as INF
missDistance=99999
for j in range(m):
if j==i:continue
curDistance=distance(X[i],X[j])
if y[i]==y[j] and curDistance<hitDistance:
hitDistance=curDistance
near[i,0]=j
if y[i]!=y[j] and curDistance<missDistance:
missDistance=curDistance
near[i,1]=j
#P250--(11.3)
relief=np.zeros(n)
for j in range(n):
for i in range(m):
relief[j]+=(X[i,j]-X[int(near[i,1]),j])**2-(X[i,j]-X[int(near[i,0]),j])**2
print(relief)
（这里作者把西瓜数据集都处理成连续值了，因为要求最近邻，必须要把数据处理一下，离散值要处理成单独的一个属性或者是连续值。）
（来自：https://blog.csdn.net/qdbszsj/article/details/79161080）
结果：
可见，纹理得分4.25，很关键，脐部、色泽也很重要。
Relief运行效率高，并且结果也比较令人满意，但也有其局限性——只能处理两类别数据，所以对其进行扩展得到Relief-F算法，该算法用于处理目标属性为连续值的回归问题。
Relief-F算法：
2.包裹式选择：
直接把最终将要使用的学习器的性能作为特征子集的评价准则。
从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，但它需多次训练学习器，所以计算开销比过滤式特征选择大得多。
LVW（Las Vegas Wrapper）是一个典型的包裹式特征选择方法。算法描述如下：
需注意，若初始特征数很多，则可能会运行很长时间都达不到停止条件（LVW结束循环的条件是连续T次随机出来的特征都比当前最优特征集合要差），即若有时间限制，可能给不出解，这也是它与蒙特卡罗方法的主要区别。
3.嵌入式选择：
将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。
嵌入式特征选择方法的优化目标在样本数相对较少时很容易陷入过拟合，需要结合正则化来缓解过拟合（过拟合是无法彻底避免的，只能“缓解”）。
若使用L2范数正则化，则涉及到“岭回归”（ridge regression）。岭回归是一种改良的最小二乘估计法，通过放弃最小二乘法的无偏性，以损失部分信息、降低精度为代价获得回归系数更为符合实际、更可靠的回归方法。
注：L1范数比L2范数正则化更易于获得“稀疏”（sparse）解。
那么为什么不用L0范数正则化呢？因为L0范数是不连续的，而且是非凸函数，无法通过优化直接求解，必须采用遍历的方式，会导致这个问题是个NP难问题。
二、稀疏表示与字典学习：
特征选择所考虑的问题是特征具有“稀疏性”，即通过特征选择去除数据集中与学习任务无关的属性，减少涉及的输入因素，使模型所建立的“输入-输出”关系更清晰。
比如，在《康熙字典》中有47035个汉字、《现代汉语常用字表》有3500个汉字，然后给定一个汉语文档，相当多字典中的字是不出现在这个文档中的，也就是存在大量的零元素，即样本文档具有稀疏表达形式。
需注意的是，我们所希望的稀疏表示是“恰当稀疏”，而不是“过度稀疏”。
显然，在一般的学习任务中并没有类似《现代汉语常用字表》的数据集可用，那么就需要我们学习出这样一个“字典”，通常称为“字典学习”（dictionary learning），亦称“码书学习”（sparse coding）。
表达为优化问题的话，字典学习的最简单形式为：
其中xi为第i个样本，B为字典矩阵，aphai为xi的稀疏表示，lambda为大于0参数。
三、压缩感知：
在实践中我们经常需要对采样的数字信号进行压缩来传输，压缩就意味着有丢包的可能，而压缩感知（compressed sensing）就是为解决此类问题而产生的。
与特征选择、稀疏表示不同，压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为“感知测量”和“重构恢复”这两个阶段。
总的来说，感知测量是对信号进行处理得到稀疏样本，重构恢复是根据稀疏样本基于稀疏性恢复程原信号。
目前，压缩感知的重构算法主要分为两大类：
（1）贪婪算法，它是通过选择合适的原子并经过一系列的逐步递增的方法实现信号矢量的逼近，此类算法主要包括匹配跟踪算法、正交匹配追踪算法、补空间匹配追踪算法等。
（2）凸优化算法，它是把0范数放宽到1范数通过线性规划求解的，此类算法主要包括梯度投影法、基追踪法、最小角度回归法等。
凸优化算法比贪婪算法所求的解更加精确，但是需要更高的计算复杂度。
其数学表达式如下：
补充：字典学习与压缩感知对稀疏性利用的异同
1.字典学习通过学习出的字典使属性适度稀疏，使得文本数据在字频上线性可分，从而提升如SVM获得更好的性能。
2.压缩感知则是希望原始信号本身虽然不稀疏，但是他内部是高度相关的。
四、总结
总的来说，在训练学习器的时候进行特征选择，是为了使程序运行效率更高、学习器拟合更好（既不欠拟合，也尽量缓解过拟合）。而特征选择要考虑的是特征是否具有“稀疏性”，如果具有“稀疏性”，又要怎样进行学习？于是引出“字典学习“，我们缺少的正是一个像《现代汉语常用字表》的数据集，才能相对来说体现出特征的“稀疏性”。而压缩感知是基于稀疏性对压缩信号进行恢复。
参考资料：
- L1 相比于L2 为什么容易获得稀疏解？ https://www.zhihu.com/question/37096933
- 压缩感知 https://blog.csdn.net/qq_42570457/article/details/82179065
- 稀疏表示以及字典学习 https://blog.csdn.net/m0_37407756/article/details/68059453
- 特征选择之relief及reliefF算法 https://blog.csdn.net/littlely_ll/article/details/71614826
