Finding Small Sets of Essential Attributes in Binary Data
Endre Boros, Takashi Horiyama, Toshihide Ibaraki, Kazuhisa Makino, Yagiura Mutsunori · 2000
We consider the problem of nding support sets (i.e., sets of essential attributes) in a given data set, which consists of n-dimensional binary vectors of positive examples and negative examples. A set of attributes is a support set if positive examples and negative examples can be separated by using only the attributes in the set. Finding small support sets is an important topic in such elds as knowledge discovery, data mining, learning theory and logical analysis of data. Based on several measures of separation, we discuss why nding small support sets is important, and how to nd such sets, together with results of some computational experiment. Theoretical analysis of the approximation ratios of the proposed algorithms is also provided.