A novel hypothesis-margin based approach for feature selection with side pairwise constraints
A novel hypothesis-margin based approach for feature selection with side pairwise constraints
复制标题
一种基于假设边际的新颖方法，用于具有侧面成对约束的特征选择
DOI：
10.1016/j.neucom.2010.08.006
复制
发表时间：
2010-10-01
期刊：
影响因子：
6
通讯作者：
Song, Jing
中科院分区：
文献类型：
--
作者：
Yang, Ming;Song, Jing
特征选择是模式分类系统中的一个重要问题。与无监督的特征选择方法相比，有监督的特征选择方法具有更好的性能。然而，几乎所有现有的监督的使用类标签作为监督信息，很少的工作已经做了其他形式的监督信息，如成对约束，它指定一对数据样本是否属于同一类（必须链接约束）或不同的类（不能链接约束）。在现实中，成对的约束可以很容易地通过指定一些对的例子是否属于同一个类或不。为此，提出了一种新的基于成对约束的特征选择过滤方法--约束评分。不幸的是，约束得分不考虑只给出不能链接约束的情况。另外，约束得分算法给出的“必须连接约束比不能连接约束更重要”的结论还有待进一步验证，因为从假设裕度或裕度的角度看，“不能连接约束”似乎比“必须连接约束”更重要。此外，与现有的监督特征选择方法一样，目前提出的基于假设边缘的特征选择方法（称为Simba）也利用类标签作为监督信息。在本文中，为了进一步研究针对成对约束的特征选择问题，我们引入了一种新的基于假设的边成对约束的特征选择方法，称为Simba-sc，它只使用cannot-link约束作为监督信息。我们比较我们的算法与著名的约束得分，费舍尔得分和拉普拉斯得分算法。使用三种不同的分类器在6个UCI数据集上进行了实验。实验结果表明，在一些不能链接的约束条件下，Simba-sc在所有训练数据上都达到了与Fisher Score相似甚至更高的性能，并且具有比Constraint Score更好或相当的性能。(C)2010 Elsevier B. V.保留所有权利。
Feature selection is an important problem for pattern classification systems. As compared to unsupervised feature selection methods, the supervised ones have better performance. However, almost all existing supervised ones use class labels as supervised information, very less work has been done for other forms of supervision information such as pairwise constraints, which specifies whether a pair of data samples belongs to the same class (must-link constraints) or different classes (cannot-link constraints). In reality, pairwise constraints can be easily obtained by specifying whether some pairs of examples belong to the same class or not. Therefore, a new filter method for feature selection with pairwise constraints, called Constraint Score, was proposed. Unfortunately, Constraint Score does not consider the case where only cannot-link constraints are given. Also, the conclusion 'must-link constraints are more important than cannot-link constraints' given by Constraint Score algorithm needs to be further verified, since 'cannot-link constraints' seems more important than 'must-link constraints' from the viewpoint of hypothesis-margin or margin. In addition, like the existing supervised feature selection methods, the currently proposed hypothesis-margin based approach for feature selection, called Simba, also utilizes class labels as supervision information. In this paper, to further study the feature selection problem aiming at pairwise constraints, we introduce a novel hypothesis-margin based approach for feature selection with side pairwise constraints, called Simba-sc, which only uses cannot-link constraints as supervision information. We compare our algorithm with the well-known Constraint Score, Fisher Score and Laplacian Score algorithms. Experiments are carried out on 6 UCI data sets using three different classifiers. Experimental results show that, with a few cannot-link constraints, Simba-sc achieves similar or even higher performance than Fisher Score with full class labels on all training data, and has better or comparable performance than Constraint Score. (C) 2010 Elsevier B.V. All rights reserved.