A data reduction device (150) for and a method of reducing a data set based on a subset of variables from a set of variables are provided. Instances of the plurality of variables comprise information to predict an instance of a further type of data. The device comprises a first data set unit (102), a second data set unit (104), a searching unit (110) and a data reduction unit (152). The first data set unit obtains a first set comprising tuples of instances of data. The second data set unit obtains a second set comprising instances of the further type of data. Each instance of the second set corresponds to one of the tuples of the first set. The searching unit obtains a reduced set of variables that represents an at least local optimum of an optimization function being a combination of a first mutual information value between the reduced first set and the second set and a penalty value being based on a number of variables in the reduced set of variables.