Iterative RELIEF for feature weighting: Algorithms, theories, and applications
Iterative RELIEF for feature weighting: Algorithms, theories, and applications
复制标题
DOI：
10.1109/tpami.2007.1093
复制
发表时间：
2007-06-01
影响因子：
23.6
通讯作者：
Sun, Yijun
中科院分区：
文献类型：
--
作者：
Sun, Yijun
RELIEF 被认为是评估特征质量最成功的算法之一。在本文中，我们提出了一组新的特征加权算法，其性能明显优于 RELIEF，且不会大幅增加计算复杂度。我们的工作从对看似启发式 RELIEF 算法的数学解释开始，该算法是一种使用基于边际的目标函数解决凸优化问题的在线方法。这种解释解释了 RELIEF 在实际应用中的成功，并使我们能够识别并解决其以下弱点。 RELIEF 隐含地假设原始特征空间中找到的最近邻是加权空间中的最近邻，并且 RELIEF 缺乏处理离群数据的机制。我们提出了一种迭代 RELIEF (I-RELIEF) 算法，通过探索期望最大化算法的框架来缓解 RELIEF 的缺陷。我们通过使用新的多类边距定义将 I-RELIEF 扩展到多类设置。为了降低计算成本，还开发了在线学习算法。提出了所提出算法的收敛性分析。报告了UCI和微阵列数据集上的大规模实验结果，证明了所提出算法的有效性，并验证了所提出的理论结果。
RELIEF is considered one of the most successful algorithms for assessing the quality of features. In this paper, we propose a set of new feature weighting algorithms that perform significantly better than RELIEF, without introducing a large increase in computational complexity. Our work starts from a mathematical interpretation of the seemingly heuristic RELIEF algorithm as an online method solving a convex optimization problem with a margin-based objective function. This interpretation explains the success of RELIEF in real application and enables us to identify and address its following weaknesses. RELIEF makes an implicit assumption that the nearest neighbors found in the original feature space are the ones in the weighted space and RELIEF lacks a mechanism to deal with outlier data. We propose an iterative RELIEF (I-RELIEF) algorithm to alleviate the deficiencies of RELIEF by exploring the framework of the Expectation-Maximization algorithm. We extend I-RELIEF to multiclass settings by using a new multiclass margin definition. To reduce computational costs, an online learning algorithm is also developed. Convergence analysis of the proposed algorithms is presented. The results of large-scale experiments on the UCI and microarray data sets are reported, which demonstrate the effectiveness of the proposed algorithms, and verify the presented theoretical results.