With the boom in IT technology, the data sets used in application are more and more larger and are described by a huge number of attributes, therefore, the feature selection become an important discipline in Knowledge discovery and data mining, allowing the experts to select the most relevant features to improve the quality of their studies and to reduce the time processing of their algorithm. In addition to that, the data used by the applications become richer. They are now represented by a set of complex and structured objects, instead of simple numerical matrixes. The purpose of our algorithm is to do feature selection on rich data, called Boolean Symbolic Objects (BSOs). These objects are described by multivalued features. The BSOs are considered as higher level units which can model complex data, such as cluster of individuals, aggregated data or taxonomies. In this paper we will introduce a new feature selection criterion for BSOs, and we will explain how we improved its complexity.