A novel filter feature selection algorithm based on relief

The Relief algorithm is a feature selection algorithm that uses the nearest neighbor to weight attributes. However, Relief only considers the correlation between features, which leads to a low classification accuracy on noisy datasets whose interaction effect is weak. To overcome the weaknesses of Relief, a novel feature selection algorithm, named Multidirectional Relief (MRelief), is proposed. The MRelief algorithm includes four improvements. First, the multidirectional neighbor search method, which finds all neighbors within a distance threshold from different orientations, is included to obtain regularly distributed neighbors. Therefore, the weights provided by MRelief are more accurate than those provided by Relief. Second, a novel objective function that incorporates the instances' force coefficients is introduced to reduce the influence of noise. Thus, the new objective function improves the classification accuracy of MRelief. Third, subset generation is introduced to the MRelief algorithm and combined with the maximum Pearson maximum distance (MPMD) to generate a promising candidate subset for feature selection. Finally, a novel multiclass margin definition is proposed and introduced to the MRelief algorithm to handle multiclass data. As demonstrated by extensive experiments on eleven UCI datasets and eleven real-world gene expression benchmarking datasets, MRelief is significantly better than other algorithms including LPLIR, ReliefF, LLH-Relief, MultiSURF, MSLIR-NN, MRMR, MPMD and STIR in our study.