转自：连续特征离散化达到更好的效果,特征选择的工程方法
连续特征的离散化：在什么情况下将连续的特征离散化之后可以获得更好的效果？
Q:CTR预估，发现CTR预估一般都是用LR，而且特征都是离散的。为什么一定要用离散特征呢？这样做的好处在哪里？
A:
在工业界，很少直接将连续值作为逻辑回归模型的特征输入，而是将连续特征离散化为一系列0、1特征交给逻辑回归模型，这样做的优势有以下几点：
0、 离散特征的增加和减少都很容易，易于模型的快速迭代。(离散特征的增加和减少，模型也不需要调整，重新训练是必须的，相比贝叶斯推断方法或者树模型方法迭代快)
1、稀疏向量内积乘法运算速度快，计算结果方便存储，容易扩展；
2、离散化后的特征对异常数据有很强的鲁棒性：比如一个特征是年龄>30是1，否则0。如果特征没有离散化，一个异常数据“年龄300岁”会给模型造成很大的干扰；离散化后年龄300岁也只对应于一个权重，如果训练数据中没有出现特征"年龄-300岁"，那么在LR模型中，其权重对应于0，所以，即使测试数据中出现特征"年龄-300岁",也不会对预测结果产生影响。特征离散化的过程，比如特征A，如果当做连续特征使用，在LR模型中，A会对应一个权重w,如果离散化，那么A就拓展为特征A-1，A-2，A-3...,每个特征对应于一个权重，如果训练样本中没有出现特征A-4，那么训练的模型对于A-4就没有权重，如果测试样本中出现特征A-4,该特征A-4也不会起作用。相当于无效。但是，如果使用连续特征，在LR模型中，y = w*a,a是特征，w是a对应的权重,比如a代表年龄，那么a的取值范围是[0..100]，如果测试样本中,出现了一个测试用例，a的取值是300，显然a是异常值，但是w*a还是有值，而且值还非常大，所以，异常值会对最后结果产生非常大的影响。
3、逻辑回归属于广义线性模型，表达能力受限；单变量离散化为N个后，每个变量有单独的权重，相当于为模型引入了非线性，能够提升模型表达能力，加大拟合；在LR模型中，特征A作为连续特征对应的权重是Wa。A是线性特征，因为y = Wa*A,y对于A的导数就是Wa,如果离散化后，A按区间离散化为A_1,A_2,A_3。那么y = w_1*A_1+w_2*A_2+w_3*A_3.那么y对于A的函数就相当于分段的线性函数，y对于A的导数也随A的取值变动，所以，相当于引入了非线性。
4、 离散化后可以进行特征交叉，加入特征A 离散化为M个值，特征B离散为N个值，那么交叉之后会有M*N个变量，进一步引入非线性，提升表达能力；
5、特征离散化后，模型会更稳定，比如如果对用户年龄离散化，20-30作为一个区间，不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反，所以怎么划分区间是门学问；按区间离散化，划分区间是非常关键的。
6、特征离散化以后，起到了简化了逻辑回归模型的作用，降低了模型过拟合的风险。(当使用连续特征时，一个特征对应于一个权重，那么，如果这个特征权重较大，模型就会很依赖于这个特征，这个特征的一个微小变化可能会导致最终结果产生很大的变化，这样子的模型很危险，当遇到新样本的时候很可能因为对这个特征过分敏感而得到错误的分类结果，也就是泛化能力差，容易过拟合。而使用离散特征的时候，一个特征变成了多个，权重也变为多个，那么之前连续特征对模型的影响力就被分散弱化了，从而降低了过拟合的风险。)
 
李沐曾经说过：模型是使用离散特征还是连续特征，其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型，也可以用连续特征加深度学习。就看是喜欢折腾特征还是折腾模型了。通常来说，前者容易，而且可以n个人一起并行做，有成功经验；后者目前看很赞，能走多远还须拭目以待。
http://www.zhihu.com/question/28641663/answer/41653367
机器学习中，有哪些特征选择的工程方法？
特征选择是特征工程中的重要问题（另一个重要的问题是特征提取），坊间常说：数据和特征决定了机器学习的上限，而模型和算法只是逼近这个上限而已。由此可见，特征工程尤其是特征选择在机器学习中占有相当重要的地位。机器学习做得好不好，被数据和模型共同影响，比如说，数据本身不可分，那么SVM等分类算法再牛逼，也不能完全正确分开。数据集本身是有内在特性的，数据集本身的特征决定了机器学习的上限。所以，一个机器学习算法可能在数据集A上效果很好，但在数据集B上效果很差，这是很正常的现象，因为数据集A和B的内在特性不一样。我以前学别人使用GBDT提取特征，别人使用GBDT提取特征，可以使分类效果提升，但是，我使用了GBDT提特征，并没有使效果提升。因为数据集特性不一样。所以，数据集的特性决定了算法能达到效果的上限。

通常而言，特征选择是指选择获得相应模型和算法最好性能的特征集，工程上常用的方法有以下：
1.计算每一个特征与响应变量的相关性：工程上常用的手段有计算皮尔逊系数和互信息系数，皮尔逊系数只能衡量线性相关性而互信息系数能够很好地度量各种相关性，但是计算相对复杂一些，好在很多toolkit里边都包含了这个工具（如sklearn的MINE），得到相关性之后就可以排序选择特征了.(其实就是计算输出关于输入的导数，如果某个特征很大程度上影响了输出，那么该特征就会比较重要)。
2. 构建单个特征的模型，通过模型的准确性为特征排序，借此来选择特征，另外，记得JMLR'03上有一篇论文介绍了一种基于决策树的特征选择方法，本质上是等价的。当选择到了目标特征之后，再用来训练最终的模型；
3. 通过L1正则项来选择特征：L1正则方法具有稀疏解的特性，因此天然具备特征选择的特性，但是要注意，L1没有选到的特征不代表不重要，原因是两个具有高相关性的特征可能只保留了一个，如果要确定哪个特征重要应再通过L2正则方法交叉检验；
4. 训练能够对特征打分的预选模型：RandomForest和Logistic Regression等都能对模型的特征打分，通过打分获得相关性后再训练最终模型；
5. 通过特征组合后再来选择特征：如对用户id和用户特征最组合来获得较大的特征集再来选择特征，这种做法在推荐系统和广告系统中比较常见，这也是所谓亿级甚至十亿级特征的主要来源，原因是用户数据比较稀疏，组合特征能够同时兼顾全局模型和个性化模型，这个问题有机会可以展开讲。
6. 通过深度学习来进行特征选择：目前这种手段正在随着深度学习的流行而成为一种手段，尤其是在计算机视觉领域，原因是深度学习具有自动学习特征的能力，这也是深度学习又叫unsupervisedfeature learning的原因。从深度学习模型中选择某一神经层的特征后就可以用来进行最终目标模型的训练了。
 
http://www.zhihu.com/question/34271604
在广告LR模型中，为什么要做特征组合？
 在业界，LR模型之所以很受欢迎，主要是因为LR模型本质是对数线性模型，实现简单，易于并行，大规模扩展方便，迭代速度快，同时使用的特征比较好解释，预测输出在0与1之间契合概率模型。（模型的可解释性举例，比如A-B的权重比较大，A代表用户，B代表物品，那么可以认为A是对B比较感兴趣的）但是，线性模型对于非线性关系缺乏准确刻画，特征组合正好可以加入非线性表达，增强模型的表达能力。另外，广告LR中，基本特征可以认为是用于全局建模，组合特征更加精细，是个性化建模，因为在这种大规模离散LR中，单对全局建模会对部分用户有偏，对每一用户建模又数据不足易过拟合同时带来模型数量爆炸，所以基本特征+组合特征兼顾了全局和个性化。比如特征向量中，有用户A，B，C，物品E,F,G。基本的特征A,B.C.E.F.G对应的权重，对应的是每个对象的偏置权重，但如果A偏好E,B偏好F，那么组合特征A-E,B-F就是对用户的个性进行建模，组合特征A-E,B-F的权重就是代表A对E的喜好，和B-F的喜好。

最常见的两种方法就是欧拉法和塔斯汀法(Tustin's method，也叫bilinear transformation)。

欧拉法即为：


将传递函数中的s用这个替换即可。

这是因为s在拉普拉斯变换里面是微分，而


而z变换里面的z运算符即为：


微分关系即变为：



但是欧拉法用的是积分的矩形法则，效果有时并不好。所以又提出了根据梯形法则的塔斯汀法：


将C(s)里面的s都替换掉，变成z和C(z)就行了。


可以再matlab里面用c2d函数进行运算:

[numZ denZ]=c2d(num,den,'tustin')%bilinear method

欧拉法在matlab里面貌似已经是不支持了。


再说下z域里怎么写成差分方程。如果我们有控制器：


且n≥m,

将分式转换：


两边同除以


注意


让Y(z)=Y(k),U(z)=U(k)


那么就能得到k时刻Y的值了。



举个例子：


分式上下均除以z的平方：


进一步整理：


再把左边的部分项挪过来：


这样就知道k时刻控制器的输出是多少了，能在程序里面进行实现了。

目录

 

什么是离散化

如何离散化

手动版

STL版

小技巧

离散化的例子

图片面积

坐标离散化

小技巧

代码

什么是离散化

你是否经历过MLE（超空间）的绝望？你是否还在为数组无法开到那么大而烦恼？只要你学了离散化，一切都不叫问题！

我们举个例子吧！如果有N个数，每个数不超过INT范围，而恰好这道题，你要开最大的数这么多个数组，那岂不就爆了？

如果N在很小的范围，我们就可以离散化了。举个例子，有4个数，5,200,154200,456987123，我们怎么离散化？按他们的大小来排就行啦！离散化后四个数就变成了，1,2,3,4。比如有3个坐标，{100,200}，{20,50000}，{1,400}，离散化后就是{3,4}，{2,6}，{1,5}，这样就大大节省了空间，相应的也节省了时间。

如何离散化

手动版

#include <cstdio>
#include <algorithm>
using namespace std;
int n, r[105];
struct node{
    int x, id;
    bool operator < (const node &rhs)const {
        return x < rhs.x;
    }
}a[105];
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i].x);
        a[i].id = i;
    }
    sort(a+1,a+1+n);
    int tot = 0;
    for(int i = 1; i <= n; i++){
        if(a[i].x != a[i-1].x){
            r[a[i].id] = ++tot;
        }
        else {
            r[a[i].id] = tot;
        }
    }
    for(int i = 1; i <= n; i++){
        printf("%d ", r[i]);
    }
    return 0;
}


其中的a[i].x!=a[i-1].x我们是在去重。当然我们也可以用STL

STL版

#include <cstdio>
#include <algorithm>
using namespace std;
int n, lsh[105], a[105];
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        lsh[i] = a[i];
    }
    sort(lsh+1,lsh+1+n);
    int cut = unique(lsh+1, lsh+1+n) - lsh - 1;
    for(int i = 1; i <= cut; i++){
        a[i] = lower_bound(lsh+1, lsh+1+n, a[i]) - lsh;
    }
    for(int i = 1; i <= n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}


cut是去重后元素的个数，由于unique函数返回的是最后一个元素下一个元素的指针，所以要减去数组头指针，还要减去一个1

如果你是从0开始的，那就不用-1了。lower_bound函数返回的是数组中第一个比a[i]大于或等于的数的指针，如果你是从0开始，

那么要+1，也可以直接用upper_bound函数（返回第一个大于的数的指针）。

小技巧

我在这里给一个小技巧，一个数组A，upper_bound(A+1,A+1+n,5)-lower_bound(A+1,A+1+n,5)就可以找到数组中等于5的个数

离散化的例子

图片面积

       大意是给定平面上的n个矩形（坐标为整数，矩形与矩形之间可能有重叠的部分），求其覆盖的总面积。平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”（把矩形所在的位置填上True）。可惜这个想法在这里有些问题，因为这个题目中坐标范围相当大（坐标范围为-10^8到10^8之间的整数）。但我们发现，矩形的数量n<=100远远小于坐标范围。每个矩形会在横纵坐标上各“使用”两个值，100个矩形的坐标也不过用了-10^8到10^8之间的200个值。也就是说，实际有用的值其实只有这么几个。这些值将作为新的坐标值重新划分整个平面，省去中间的若干坐标值没有影响。我们可以将坐标范围“离散化”到1到200之间的数，于是一个200*200的二维数组就足够了。实现方法正如本文开头所说的“排序后处理”。对横坐标（或纵坐标）进行一次排序并映射为1到2n的整数，同时记录新坐标的每两个相邻坐标之间在离散化前实际的距离是多少。这道题同样有优化的余地。（百度百科）

      我们来看一张图片吧！



T就是有矩形覆盖的区域，你说如何知道一块区域等于原来的多少，用一个array of size就可以了

你说怎么操作，你自己也能找到规律吧，用循环不就解决了（I believe you！）

坐标离散化



上面就分了6个区域

怎么做，先离散化，由于这道题不一样，一条直线可能就会分成2个区域，所以我们要改变一下离散化的方法。

就是左边和右边包括自己都要存起来，以免出现离散后将区域给减小了。

打个比方吧，如果只有一条直线（平行于Y轴），如果你按照原来的离散方法，我们就会把后直线后面的截掉，而且也会把前面截掉，因为你离散化后直线就在X=1处，我们离散肯定要把范围减小，减到了最后一条直线时就把后面的区域给剪掉了，所以要左右都考虑。



 你看下面的代码就会发现，离散后不像上图一样。这就说明了离散不够。经过我反复推敲，我认为只需要考虑前面就可以了，而最后面的直线单独考虑后面。（因为中间直线的后面和下一个直线的前面其实是差不多的）

小技巧

sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());

此代码可以去重（XS是vector）

另外，find也可以找到某个数的位置，返回的是指针(其实与lower_bound差不多)

代码

借鉴书上的（由于深搜浪费了时间，所以用广搜）

​
int W, H, N;
int X1[MAX_N], X2[MAX_N], Y1[MAX_N], Y2[MAX_N];
 
bool fld[MAX_N * 3][MAX_N * 3]
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
 
// 对 x1 数组和 x2 数组进行坐标离散化，并返回离散化之后的宽度
int compress (int* x1, int* x2, int w)
{
	vector<int> xs;
	
	for (int i = 0; i < N; i++)
	{
		for (int d = -1; d <= 1; d++)
		{
			int tx1 = x1[i] + d, tx2 = x2[i] + d;
			if (tx1 >= 1 && tx1 <= w) xs.push_back(tx1);
			if (tx2 >= 1 && tx2 <= w) xs.push_back(tx2);
		}
	}
	
	sort(xs.begin(), xs.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	
	for (int i = 0; i < N; i++)
	{
		x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
		x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
	}
	return xs.size();	
} 
/*这个函数对坐标进行了压缩：
1. 将坐标的值变成了“这是第几种坐标”(种类和区域个数有关，同个区域的就是同一种坐标),函数返回值是一共有多少种坐标
2. 起止行(列)的前后行(列)若在 w*w 的范围内，则压栈(其实是压入队列)其前后行(列)，因为每个黑行对数区域的影响，也就只有它的前后行和本身那行，对别的行是不会有影响的
*/
 
void solve()
{
	// 坐标离散化
	W = compress(X1, X2, W);
	H = compress(Y1, Y2, H);
	
	// 填充有直线的部分
	memset(fld, 0, sizeof(fld));
	
	for (int i = 0; i < N; i++)
	for (int y = Y1[i]; y <= Y2[i]; y++)
	for (int x = X1[i]; x <= X2[I]; x++)
	{
		fld[y][x] = true;
	}
	
	// 求区域的个数
	int ans = 0;
	for (int y = 0; y < H; y++)
	for (int x = 0; x < W; x++)
	{
		if (fld[y][x]) continue;
		ans++;
		
		// 宽度优先搜索
		queue<pair<int, int> > que;
		que.push(make_pair(x, y));
		
		while (!que.empty())
		{
			int sx = que.front().first, sy = que.front().second;
			que.pop();
			
			for (int i = 0; i < 4; i++)
			{
				int tx = sx + dx[i], ty = sy + dy[i];
				if (tx < 0 || tx >= W || ty < 0 || ty >= H) continue;
				if (fld[ty][tx]) continue;
				que.push(make_pair(tx, ty));
				fld[ty][tx] = true;
			}
			
		 } 
	}
	cout << ans << endl;
}

​

 

起始聚类离散化就是根据利用一定规则对数据进行分类，可以用分桶式或者k-means 等方法

这里用中医证型关联规则挖掘里面的离散化举例，k-means 举例

首先看下图的原数据，该病存在六种证型系数，为了后续的关联算法，需要先将其离散化。
import pandas as pd
from sklearn.cluster import KMeans #导入K均值聚类算法

datafile = '../data/data.xls' #待聚类的数据文件
processedfile = '../tmp/data_processed.xls' #数据处理后文件
typelabel ={u'肝气郁结证型系数':'A', u'热毒蕴结证型系数':'B', u'冲任失调证型系数':'C', u'气血两虚证型系数':'D', u'脾胃虚弱证型系数':'E', u'肝肾阴虚证型系数':'F'}
k = 4 #需要进行的聚类类别数

#读取数据并进行聚类分析
data = pd.read_excel(datafile) #读取数据
keys = list(typelabel.keys())
result = pd.DataFrame()

if __name__ == '__main__': #判断是否主窗口运行，这句代码的作用比较神奇，有兴趣了解的读取请自行搜索相关材料。
  for i in range(len(keys)):
    #调用k-means算法，进行聚类离散化
    print(u'正在进行“%s”的聚类...' % keys[i])
    kmodel = KMeans(n_clusters = k, n_jobs = 4) #n_jobs是并行数，一般等于CPU数较好
    kmodel.fit(data[[keys[i]]]) #训练模型
    print(kmodel.cluster_centers_)
    r1 = pd.DataFrame(kmodel.cluster_centers_, columns = [typelabel[keys[i]]]) #聚类中心
    #print('r1',r1,kmodel.labels_)
    r2 = pd.Series(kmodel.labels_).value_counts() #分类统计
    r2 = pd.DataFrame(r2, columns = [typelabel[keys[i]]+'n']) #转为DataFrame，记录各个类别的数目

    r = pd.concat([r1, r2], axis = 1).sort_values(typelabel[keys[i]]) #匹配聚类中心和类别数目
    r.index = [1, 2, 3, 4]
    print('r-1',r)
    r[typelabel[keys[i]]] = r[typelabel[keys[i]]].rolling(2).mean() #rolling_mean()用来计算相邻2列的均值，以此作为边界点。
    print('r-2', r)
    r.iloc[0,0] = 0.0 #这两句代码将原来的聚类中心改为边界点。
    print('r-3', r)
    result = result.append(r.T)

  result = result.sort_index() #以Index排序，即以A,B,C,D,E,F顺序排
  result.to_excel(processedfile)

例子二，通过cut进行离散化
import pandas as pd 
import numpy as np
 
index = pd.Index(data=["Tom", "Bob", "Mary", "James","kobe","kawayi"], name="name")
data = {
    "age": [15, 28, 23, 37,33,11]
}
user_info = pd.DataFrame(data=data, index=index)
pd.cut(user_info.age,3) #分成3段，
#[(10.974, 19.667] < (19.667, 28.333] < (28.333, 37.0]] 按照数据的最大值最小值为区间分成3分

当然还可以自定义进行划分
比如
qujian=[5,15,25,40]
pd.cut(user_info.age,qujian,labels=['child','youth','middle'])
#此时就不会按最大值最小值分成3分，而是按照5-15,15-25,25-40的固定区间分，同时会按labels对区间命名

#若想查看各区间的人数，可以用groupyby函数
pdd=pd.cut(user_info['age'],qujian)
user_info['age'].groupby(pdd).count()
#可以通过遍历来查看某一区间有哪些值，pdd相当于一个列名，在翻阅其他例子时发现假如某列就是离散的，可以直接用#groupby（"age"）

for i in user_info['age'].groupby(pdd):
		print（i）


参考文献：

1，Python数据分析与挖掘实战

2，本文借鉴了https://blog.csdn.net/weixin_37536446/article/details/82149772