Relief算法的数据以及代码：https://github.com/qdbszsj/Relief

西瓜书第十一章，主要讲了一下特征选择的方法，通常来说，有很多冗余特征，如果能把这些特征从我们的数据集中筛选出去，那么可以极大地提高我们的程序运行效率，当然有的时候我们还需要人为保留或者创造一些冗余特征，当且仅当这些冗余特征恰好对应了完成任务所需要的“中间概念”。比如要求一个立方体的体积时，输入数据只有长宽高，如果能人为创造一个“底面积”或者“侧面积”这样的冗余特征，那么更容易求解，这个冗余特征要分情况来确定。

这里我们不主要探讨冗余特征，而是多说一些如何筛选特征，也就是搜索一个特征子集，让这个子集训练出来的模型最棒，这个问题显然是NP的，一切搜索方法都有局限性，那么目前我们常用的特征选择方法有三种：过滤式filter、包裹式wrapper、嵌入式embedding。

过滤式选择:

先对数据集进行特征选择，再训练学习器，特征选择与后续学习无关，我这个Relief算法就是一种经典的过滤式选择，Relief是先把每个个体的最近邻求出来，这里有几个分类结果就要求几个对应的近邻，分为猜中近邻（near-hit）和猜错近邻（near-miss），然后根据式11.3求一下各个属性的值就行，分量值越大，对应属性的能力就越强。

包裹式选择：

直接把最终要使用的学习器的性能作为特征子集的评价准则，量身定做特征子集，这里就是固定好学习器，然后随机的选子集，哪个子集误差小就用哪个，著名的有LAW拉斯维加斯wrapper。

嵌入式选择：

说白了就是用L1正则化来求解目标函数，比较容易得到稀疏解，然后有的分量可能取值就为0了，于是这个分量对应的属性就相当于被筛掉了。

这里重点说一下正则化：

正则化是用来防止过拟合的工具，样本特征多，样本数量少，很容易陷入过拟合，这时候我们加一个正则化项，希望求到一个尽量平滑、权值和较小的解，这里通常有L2、L1、L0正则化，L2范数就是求w的欧式距离，L1对应曼哈顿距离，L0对应切比雪夫距离，这些距离都是类闵可夫斯基距离，就是各个分量差的p次方之和再开p次根，在二维空间里，如果距离为1，欧式距离可以理解为一个半径为1的圆，曼哈顿距离能画出一个旋转了45度的正方形，对角线长度是2，边长根2，切比雪夫就是一个边长为2的正方形，在三维空间里，若距离为1，L2就是半径为1的球，L1就是一个边长根2的正八面体，L0就是一个边长为2的立方体。于是L1和L0更容易在顶点处与误差项相交（L0比L1更容易），从而获得稀疏解，而L2更容易获得各个分量都很均衡的解。这里我们通常不用L0正则，因为L0正则是不连续的，没法求导，无法优化求解。（书P253页的图很棒）

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,0]),j])**2
print(relief)