Stability of feature selection from high-dimensional data is an important and active research area. Ensemble feature selection has emerged as an effective method to improve the stability of feature selection. However, it results in a significant increase of computational cost in many real world applications. In this paper, we propose an improved ensemble feature selection framework using random sampling and random feature selection to improve the stability and to reduce the computational cost. The proposed framework is implemented in the context of multi-reliefF. Experiments on eight high-dimensional small-sample data sets show that under the proposed framework the computational cost is reduced dramatically while the stability improved slightly.