Research in the area of fuzzy-rough set theory, and its application to feature or attribute selection in particular, has enjoyed much attention in recent years. Indeed, with the growth of larger and larger data dimensionality, the number of data objects required in order to generate accurate models increases exponentially. Thus, for model learning, feature selection has become increasingly necessary. The use of fuzzy-rough sets as dataset pre-processors offer 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 and attribute grouping in order to alleviate the processing overhead and reduce complexity. A series of experiments are conducted on benchmark datasets which demonstrate that much computational effort can be avoided, and as a result the efficiency of the feature selection process for fuzzy-rough sets can be improved considerably.