TY - JOUR
T1 - Logical analysis of data with decomposable structures
AU - Ono, Hirotaka
AU - Makino, Kazuhisa
AU - Ibaraki, Toshihide
N1 - Funding Information:
This work was partially supported by the Scienti0c Grant-in-Aid by the Ministry of Education, Science, Sports and Culture of Japan. The authors thank the anonymous referee for their helpful comments which improved the presentation of this paper.
PY - 2002/10/30
Y1 - 2002/10/30
N2 - In such areas as knowledge discovery, data mining and logical analysis of data, methodologies to find relations among attributes are considered important. In this paper, given a data set (T,F) where T ⊆ {0,1}n denotes a set of positive examples and F⊆{0,1}n denotes a set of negative examples, we propose a method to identify decomposable structures among the attributes of the data. We first study computational complexity of the problem of finding decomposable Boolean extensions. Since the problem turns out to be intractable (i.e., NP-complete), we propose a heuristic algorithm in the second half of the paper. Our method searches a decomposable partition of the set of all attributes by using the error sizes of almost-fit decomposable extensions as a guiding measure, and then finds structural relations among the attributes in the obtained partition. Some results of numerical experiment on randomly generated data sets are also reported.
AB - In such areas as knowledge discovery, data mining and logical analysis of data, methodologies to find relations among attributes are considered important. In this paper, given a data set (T,F) where T ⊆ {0,1}n denotes a set of positive examples and F⊆{0,1}n denotes a set of negative examples, we propose a method to identify decomposable structures among the attributes of the data. We first study computational complexity of the problem of finding decomposable Boolean extensions. Since the problem turns out to be intractable (i.e., NP-complete), we propose a heuristic algorithm in the second half of the paper. Our method searches a decomposable partition of the set of all attributes by using the error sizes of almost-fit decomposable extensions as a guiding measure, and then finds structural relations among the attributes in the obtained partition. Some results of numerical experiment on randomly generated data sets are also reported.
UR - http://www.scopus.com/inward/record.url?scp=0037202055&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037202055&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(01)00413-3
DO - 10.1016/S0304-3975(01)00413-3
M3 - Conference article
AN - SCOPUS:0037202055
SN - 0304-3975
VL - 289
SP - 977
EP - 995
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2
T2 - Computing and Combinatorics (COCOON 2000)
Y2 - 1 July 2000 through 1 July 2000
ER -