Research in the area of fuzzy-rough set theory and its application to various areas of learning have generated great interest in recent years. In particular, there has been much work in the area of feature or attribute selection. Indeed, as the number of dimensions increases, the number of data objects required in order to generate accurate models increases exponentially. Thus, feature selection (FS) has become an increasingly necessary step in model learning. The use of fuzzy-rough sets as dataset pre-processors offers much in the way of flexibility, however the underlying complexity of the subset evaluation metric often presents a problem and can result in a great deal of potentially unnecessary computational effort. This paper proposes two different novel ways to address this problem using a neighbourhood approximation step in order to alleviate the processing overhead and reduce the complexity of the evaluation metric. The experimental evaluation demonstrates that much computational effort can be avoided, and as a result the efficiency of the FS process can be improved considerably.