Feature weight estimation based on dynamic representation and neighbor sparse reconstruction

Relief-like algorithms have been widely used as feature selection to reduce the dimension of high-dimensional data which involves thousands of irrelevant variables because of their low computational cost and high accuracy. Classical Relief algorithms have not exactly shown the dynamic procedure that updates weight iteratively. This paper proposes an innovative feature weight estimation method, called dynamic representation and neighbor sparse reconstruction-based Relief (DRNSR-Relief). Similar to the classical Relief algorithms, the goal of DRNSR-Relief is to maximize the expected margin in the weighted feature space. A dynamic representation framework is introduced to show the dynamic relationship between the expected margin vector and the weight vector. To achieve better neighbor reconstruction, DRNSR-Relief decomposes a nonlinear problem into a set of locally linear ones through local hyperplane with l1 regularization and then estimates feature weights in a large margin framework. With the help of gradient ascent method, we can guarantee the convergence of DRNSR-Relief. To demonstrate the validity and the effectiveness of our formulation for feature selection in supervised learning, we perform extensive experiments on synthetic and real-world datasets. Experimental results indicate that DRNSR-Relief is very promising.