KDD2017精选（1）如何筛选特征

来自：Feature Selection: A Data Perspective

目的：

相对于算法本身的改进，特征工程往往对效果有更直接的提升。特征工程以降维为手段，重点解决以下问题：

1. 过拟合；

2. 随着特征增加，稀疏性呈指数爆炸。由于大多数算法假设数据特征独立同分布，稀疏性会干扰最终结果；

3. PAC Learning Theory：我们对实际问题的假设在多大程度上背离目标方程;

实际应用中，针对具体问题，我们通常能找到最佳特征数：

1. 特征提取：将数据从原始的高位空间投向低维，得到的新特征通常没有物理意义；

1.1 线性投影：PCA，ICA，LDA等；

1.2 非线性投影：ISOMAP，LLE等；

2. 特征筛选：基于相关性和冗余性，从原始特征择优；

从y值考虑，特征工程可分为有监督，无监督和半监督3类；从x考虑，特征工程可分为wraper，filter，embedder 3类。本文从数据角度，对特征工程做如下分类：

1. Similarity based methods：基于相似性的方法通过保持原始数据相关性的能力评估特征的重要性。好特征不能导致数值大小的随机性，同时好特征可以令邻近的数据数值接近，邻近由相关矩阵定义。假设相关矩阵在实数空间内，为了找到相关性最高的特征，需要最大化效用矩阵，通常需要用最小二乘法得到其最大值。

优点：1. 特征得分计算简单，2. 选出的的特征可直接用于后续学习任务；

缺点：没有有效解决特征冗余；

1.1 Laplacian Score [He et al., 2005]

1.1.1 首先：这种方法搭建X的对角矩阵（构建多样性）和拉普拉斯矩阵（构建相似性）， 不考虑Y；

1.1.2 好的特征需要同时保证X的相似性特征（越小越好）和特征的多样性（越大越好）；

1.1.3 拉普拉斯得分越小越好；

1.2 Spectral Feature Selection [Zhao and Liu, 2007]

1.2.1 相似矩阵的特征向量代表了X的分布；

1.2.2 特征的相似性由特征向量的内积衡量，特征值对X在该特征上的赋值由下图灰度表示，邻近的数据赋值相近；

1.2.3 谱特征得分越大越好；

1.3 Fisher Score [Duda et al., 2001]

1.3.1 这种方法考虑Y，构建类内和类间拉普拉斯矩阵，该矩阵每个元素越大，对应的x越相似；

1.3.2 好特征使不同类的数据相远，使同类数据相近；

1.3.3 费舍得分越大越好

1.4. Trace Ratio Criteria [Nie et al., 2008]

1.4.1. 费舍得分单独地衡量每个特征，可能陷入局部最优

1.4.2. 迹比准则还衡量特征子集；

1.4.3. 迹比得分越大越好，所得特征没有物理意义；

2. Information Theoretical based Methods：使用启发式筛选方法挑特征，以总体最优为目标。找到最好的特征子集是NP-难的问题，通常基于熵，冗余性和信息增益，使用前向和后向搜索找特征。

优点：1. 兼顾相关性和冗余性，2. 选出的的特征可直接用于后续学习任务；

缺点：1. 大部分方法只能用于监督学习，2. 只能处理离散数据；

2.1. Information Gain [Lewis, 1992]

2.1.1. 信息增益仅通过衡量基于Y的X的相关性来衡量特征重要性；

2.1.2. 仅考虑单个特征，且不考虑特征间的互信息；

2.1.3. 信息增益越大越好；

2.2. Mutual Information Feature Selection [Battiti, 1994]

2.2.1. 信息增益仅考虑单个特征和Y的相关性；

2.2.2. 互信息还考虑特征间的信息冗余；

2.2.3. 互信息越大越好；

2.3. Minimum Redundancy Maximum Relevance [Peng et al., 2005]

2.3.1. 直观上，MRMR基于相似矩阵，动态减小信息冗余对特征集的影响；

2.3.2. 同时，增强特征子集对Y的相关性的影响；

2.3.3. MRMR得分越大越好，所得特征没有物理意义；

2.4.4. Conditional Infomax Feature Extraction [Lin and Tang, 2006]

2.4.1. 类内相关性越大于总体类间相关性，相关特征越有用；

2.4.2. 相关特征不一定冗余；

2.4.3. 条件信息得分越大越好，所得特征没有物理意义；

3. Sparse Learning based Methods：上述方法不一定适用于某一具体任务。稀疏学习方法通常用于嵌入。该方法通常使用损失项和惩罚项，有极强的理论支撑，适用数据的类型较为广泛，且使用灵活。

优点：1. 数据利用充分，2. 直观，可解释性好；

缺点：1. 泛化性弱，2. 非平滑最优，计算量大；

3.1. Lasso [Tibshirani, 1996]

3.1.1. 该方法基于特征权重的l1正则化项；

3.1.2. 该方法通过补偿最小二乘法的损失确定得分大小；

3.1.3. Lasso得分越大越好；

3.2. Multi-Cluster Feature Selection (MCFS) [Cai et al., 2011]

3.2.1. 该方法寻找X内部聚类的向量，检测其聚类结构；

3.2.2. 对每个类计算lasso，并组合类的特征系数；

3.2.3. MCFS得分越大越好；

3.3.3. Nonnegative Unsupervised Feature Selection (NDFS) [Li et al., 2012]

3.3.1. 该方法同时执行聚类和特征选择；

3.3.2. 类的权重矩阵由RBF核构造，之后将该矩阵嵌入特征选择；

3.3.3. NDFS得分越大越好；

4. Statistical based Methods：基于一系列统计检测，通常用于特征筛选，不考虑冗余性，在离散数据上效果较好。

优点：1. 直观，2. 选出的特征可直接用于后续学习任务；

缺点：1. 没解决特征冗余，2. 数据需要离散化，3. 在高维空间计算量大；

4.1. T-Score [Davis and Sampson, 1986]

4.1.1. 用于二分类；

4.1.2. 检测特征对样本间均值是否显著；

4.1.3. T得分越高越好；

4.2. Chi-Square Score [Liu and Setiono, 1995]

4.2.1. 检测特征对Y的独立性；

4.2.2. 不考虑类间关系；

4.2.3. 卡方得分越高越好；

5. FS with Structured Features：常见的数据结构有时序，图，群，树等。流行的方法是最小化因结构正则化而受到惩罚的拟合误差

优点：1. 提高学习效率，2. 提高可解释性；

缺点：1. 需要统一的标注规则，2. 需要计算非凸优化，计算量大；

5.1. Group Structure – Group Lasso [Yuan and Lin, 2006]

5.1.1. 该数据结构常用于脑功能，基因组的编码；

5.1.2. 需要全选或全不选某个群；

5.1.3. 以群的损失和惩罚为依据；

5.2. Sparse Group Lasso [Friedman et al., 2010]

5.2.1. 用于挑选有代表性的群；

5.2.2. 同时基于群和特征构建得分；

5.2.3. SGL得分越高越好；

5.3. Granger Causality Score [Granger, 2003]

5.3.1. 用于计量时序数据，检测过去信息对现在的最小二乘方差；

5.3.2. 检测前提是通过平稳检测和协整检测；

5.3.3. 因果性得分越高越好；

5.4. Tree-Guided Group Lasso [Liu and Ye, 2010]

5.4.1. 树状结构用于人脸识别，基因表达，部分词向量的编码；

5.4.2. 子叶节点是单独特征，内部节点是群特征，

5.4.3. 基于权重检测和每个子树的相关性；

5.5. Graph Lasso [Ye and Liu, 2012]

5.5.1. 图结构用于同义反义词，基因的相互制约等场景的编码；

5.5.2. 如果两个节点特征被连接，则这两个特征可能会被同时选择；

5.5.3. 节点权重需要加惩罚项；

5.6. Graph-Guided Fused Lasso (GFLasso) [Kim and Xing, 2009]

5.6.1. Graph Lasso假设连接的特征具有相近特征系数，但是该系数可能为负；

5.6.2. GFL显示地构造正相关和负相关，两个相关项基于特征矩阵动态调整；

5.6.3. GFL得分越高越好；

6. Feature Selection with Heterogeneous Data：传统特征分析单一来源数据，这些数据通常满足独立同分布假设。异构数据来源广泛，比如互联网，物联网，天文观测，基因测序，人际网络等。该方法主要应对如何为关联信息建模，如何融合异构信息，如何在标签缺失的问题。

优点：适应多中来源数据；

缺点：不同来源的数据可能有噪声，甚至相互矛盾；

6.1. Feature Selection on Networks (FSNet) [Gu and Han, 2011]

6.1.1. 使用线性分类器分别捕捉X和Y的关系；

6.1.2. 使用Graph lasso建立不同来源X之间的关系；

6.1.3. 以FSNet为目标方程获得权重矩阵；

6.2. Linked Feature Selection (LinkedFS) [Tang and Liu, 2012]

6.2.1. 以社交网络行为：转发，共同关注，共同被关注，和关注来编码数据；

6.2.2. 基于统制社交理论，假设这些行为的人具有相同兴趣；

6.2.3. 以链接强度矩阵构建特征得分，越高越好；

6.3.3. Personalized Feature Selection [Li et al., 2017]

6.3.1. 以社交网络行为的不同来构造特征，关注不同兴趣和相同内同的不同含义‘苹果降价了’；

6.3.2. 通过鼓励群内特征竞争，抑制群间特征竞争来抑制过拟合；

6.3.3. 目标方程考虑节点连接的方向，组内群内权重和群间权重；

6.4. Linked Unsupervised Feature Selection (LUFS) [Tang and Liu, 2012]

6.4.1. 通过节点链接的权重，应对标注和特征定义不明的场景；

6.4.2. 通过社交维度的散布矩阵，最大化组内相似性同时最小化组间相似性，相似性由RBF核定义；

6.4.3. 目标：最小化Y的松弛谱同时对X各阶施加正则化项；

6.5. Robust Unsupervised on Networks (NetFS) [Li et al., 2016]

6.5.1. LUFS对网络构建和特征选择分开处理，NetFS将网络构建嵌入到特征选择中，对噪声链接有更好的鲁棒性；

6.5.2. 构建潜在表达矩阵，对网络构建和特征选择形成互补；

6.5.3. 使用Kmeans回溯NetFS和LUFS，前者对干扰的鲁棒性更好；

6.6. Feature Selection in Signed Networks (SignedFS) [Cheng et al., 2017]

6.6.1. 上述方法分析了社交网络里正向的用户互动，SignedFS独立地添加负向互动到目标函数中，基于三个假设：1. 正向互动的用户具有更高相似性，2. 朋友的朋友是朋友，3. 敌人的敌人是朋友。

6.6.2. 同时嵌入正负项的潜在表示到特征选择中；

6.6.3. 最终得到的特征在T检验下表现良好；

7. Multi-Source and Multi-View Feature Selection：前者选择不同的特征F，后者选择不同的X；

优点：不同来源数据互补，显著提升后续训练任务；

缺点：非凸优化计算量大，且涉及高位空间矩阵；

7.1. Multi-Source Feature Selection [Zhao and Liu, 2008]

7.1.1. 基于不同来源的地理信息数据的邻接矩阵，构建总体样本；

7.2.2. 对独立的数据源构建协方差矩阵来获得相关性；

7.3.3. 可以通过协方差矩阵的对角矩阵对特征排序，也可以直接用PCA来提取该矩阵的特征；

7.2. Multi-View Unsupervised Feature Selection (MVFS) [Tang et al., 2013]

7.2.1. MVFS兼顾聚类结构，相似性和相关性：

7.2.2. 对每个view考察其特征权重，同时考察该特征权重矩阵内部的稀疏性；

7.3.3. 最后使用谱聚类寻找无效标签；

7.3. Multi-View Clustering and Feature Learning [Wang et al., 2013]

7.3.1. 每个view的贡献需要区别对待，比如不同摄像头同一时间的数据；

7.3.2. 同时对view内和view间的稀疏性以实现上述目标；

7.3.3. 在该任务的稀疏矩阵的惩罚项上，l1比l2效果好；

8. Feature Selection with Streaming Data Instances and Features：主要挑战是数据流的大小和特征数量都未知，对实时性要求高，且难以批处理。特征流选择分两步：1. 是否使用新特征，2. 是否放弃老特征。

8.1. Grafting [Perkins and Theiler, 2003]

8.1.1. 加入新特征时加入新的惩罚项，当loss的下降超过特征矩阵的权重时，目标方程减小，此时加入新特征；

8.1.2. 如果新特征被加入，通过更新所有权重的共轭梯度下降来更新模型；

8.1.3. 此时如果有些特征的权重被归零，删掉；

8.2.2. Unsupervised Streaming Feature Selection (USFS) [Li et al., 2015]

8.2.1. 通过关联信息解决标注的缺失；

8.2.2. 通过在线的特征子集的变化来确定新特征是否被加入；

8.2.3. 得到的特征通常比较稳定；

8.3. Online Feature Selection (OFS) [Wang et al., 2014]

8.3.1. OFS基于线性分类器，每个特征的数据量设限不超过阈值；

8.3.2. 如果新数据的特征预测错误，则执行特征权重的梯度下降，

8.3.3. 在惩罚项下寻找已有的总体的新特征；

8.4. Feature Selection on Data Streams (FSDS) [Huang et al., 2015]

8.4.1. 基于matrix sketching [Liberty. 2013]获得低阶的特征矩阵；

8.4.2. 权重更新使用MCFS

8.4.3. 如果新的X正交，使用l2替换l1；

总结：