DIMACS TR: 2000-10

Finding Small Sets of Essential Attributes in Binary Data

Authors: Endre Boros, Takashi Horiyama, Toshihide Ibaraki, Kazuhisa Makino and Mutsunori Yagiura


We consider the problem of finding 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 fields as knowledge discovery, data mining, learning theory and logical analysis of data. Based on several measures of separation, we discuss why finding small support sets is important, and how to find such sets, together with results of some computational experiment. Theoretical analysis of the approximation ratios of the proposed algorithms is also provided.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-10.ps.gz
DIMACS Home Page