In rough set theory, forward heuristic algorithm selects the most important feature in the process of feature selection until the given constraint is satisfied. However, the feature subset selected by such strategy may bring us over-fitting. To solve this problem, a new heuristic algorithm is designed. The importance of the feature is obtained by cross validation and then the early stopping is employed to terminate the algorithm when over-fitting occurs. Based on the neighborhood rough set, the new method is compared with the heuristic algorithm over several UCI data sets. The experimental results show that: the proposed algorithm can effectively reduce the degree of over-fitting, and the feature subset obtained by the new algorithm may offer better classification performances.