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
ABSTRACT
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