Abstract: The feature subset selection problem has long been the focus in the area of artificial intelligence. Especially, in the past few years it has received considerable attention from machine learning and data mining. There are always noises in the real world datesets. Unfortunately, in most of the current feature subset selection algorithms, datasets have been assumed to be entirely perfect, that is, they have no noises. This makes it very difficult for these algorithms to obtain better results from the real world datasets. A new algorithm, the noise tolerant algorithm for feature subset selection （NFS）, is proposed. Clustering approach is applied to processing noises. And Gini index and Mexico hat function are used to select feature subset. Compared with the current heuristic algorithms, NFS can not only find feature subset containing lesser features efficiently, but also give higher accuracy for the learning system in the dataset described only by selected features. This implies that NFS can select more representative features and tolerate noises in the real world datasets effectively.