Finding essential attributes in binary data?

Endre Boros, Takashi Horiyama, Toshihide Ibaraki, Kazuhisa Makino, Mutsunori Yagiura

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Given a data set, consisting of n-dimensional binary vectors of positive and negative examples, a subset S of the attributes is called a support set if the positive and negative examples can be distinguished by using only the attributes in S. In this paper we consider several selection criteria for evaluating the “separation power” of supports sets, and formulate combinatorial optimization problems for finding the “best and smallest” support sets with respect to such criteria. We provide efficient heuristics, some with a guaranteed performance rate, for the solution of these problems, analyze the distribution of small support sets in random examples, and present the results of some computational experiments with the proposed algorithms.

Original languageEnglish (US)
Title of host publicationIntelligent Data Engineering and Automated Learning - IDEAL 2000
Subtitle of host publicationData Mining, Financial Engineering, and Intelligent Agents - 2nd International Conference, Proceedings
EditorsHelen Meng, Kwong Sak Leung, Lai-Wan Chan
PublisherSpringer Verlag
Pages133-138
Number of pages6
ISBN (Print)3540414509, 9783540414506
StatePublished - Jan 1 2000
Event2nd International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2000 - Shatin, N.T., Hong Kong
Duration: Dec 13 2000Dec 15 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1983
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2000
CountryHong Kong
CityShatin, N.T.
Period12/13/0012/15/00

Fingerprint

Binary Data
Combinatorial optimization
Attribute
Experiments
Combinatorial Optimization Problem
Computational Experiments
n-dimensional
Heuristics
Binary
Subset

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Boros, E., Horiyama, T., Ibaraki, T., Makino, K., & Yagiura, M. (2000). Finding essential attributes in binary data? In H. Meng, K. S. Leung, & L-W. Chan (Eds.), Intelligent Data Engineering and Automated Learning - IDEAL 2000: Data Mining, Financial Engineering, and Intelligent Agents - 2nd International Conference, Proceedings (pp. 133-138). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1983). Springer Verlag.
Boros, Endre ; Horiyama, Takashi ; Ibaraki, Toshihide ; Makino, Kazuhisa ; Yagiura, Mutsunori. / Finding essential attributes in binary data?. Intelligent Data Engineering and Automated Learning - IDEAL 2000: Data Mining, Financial Engineering, and Intelligent Agents - 2nd International Conference, Proceedings. editor / Helen Meng ; Kwong Sak Leung ; Lai-Wan Chan. Springer Verlag, 2000. pp. 133-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{4d744a2d88cf44168417577802eceaac,
title = "Finding essential attributes in binary data?",
abstract = "Given a data set, consisting of n-dimensional binary vectors of positive and negative examples, a subset S of the attributes is called a support set if the positive and negative examples can be distinguished by using only the attributes in S. In this paper we consider several selection criteria for evaluating the “separation power” of supports sets, and formulate combinatorial optimization problems for finding the “best and smallest” support sets with respect to such criteria. We provide efficient heuristics, some with a guaranteed performance rate, for the solution of these problems, analyze the distribution of small support sets in random examples, and present the results of some computational experiments with the proposed algorithms.",
author = "Endre Boros and Takashi Horiyama and Toshihide Ibaraki and Kazuhisa Makino and Mutsunori Yagiura",
year = "2000",
month = "1",
day = "1",
language = "English (US)",
isbn = "3540414509",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "133--138",
editor = "Helen Meng and Leung, {Kwong Sak} and Lai-Wan Chan",
booktitle = "Intelligent Data Engineering and Automated Learning - IDEAL 2000",
address = "Germany",

}

Boros, E, Horiyama, T, Ibaraki, T, Makino, K & Yagiura, M 2000, Finding essential attributes in binary data? in H Meng, KS Leung & L-W Chan (eds), Intelligent Data Engineering and Automated Learning - IDEAL 2000: Data Mining, Financial Engineering, and Intelligent Agents - 2nd International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1983, Springer Verlag, pp. 133-138, 2nd International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2000, Shatin, N.T., Hong Kong, 12/13/00.

Finding essential attributes in binary data? / Boros, Endre; Horiyama, Takashi; Ibaraki, Toshihide; Makino, Kazuhisa; Yagiura, Mutsunori.

Intelligent Data Engineering and Automated Learning - IDEAL 2000: Data Mining, Financial Engineering, and Intelligent Agents - 2nd International Conference, Proceedings. ed. / Helen Meng; Kwong Sak Leung; Lai-Wan Chan. Springer Verlag, 2000. p. 133-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1983).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Finding essential attributes in binary data?

AU - Boros, Endre

AU - Horiyama, Takashi

AU - Ibaraki, Toshihide

AU - Makino, Kazuhisa

AU - Yagiura, Mutsunori

PY - 2000/1/1

Y1 - 2000/1/1

N2 - Given a data set, consisting of n-dimensional binary vectors of positive and negative examples, a subset S of the attributes is called a support set if the positive and negative examples can be distinguished by using only the attributes in S. In this paper we consider several selection criteria for evaluating the “separation power” of supports sets, and formulate combinatorial optimization problems for finding the “best and smallest” support sets with respect to such criteria. We provide efficient heuristics, some with a guaranteed performance rate, for the solution of these problems, analyze the distribution of small support sets in random examples, and present the results of some computational experiments with the proposed algorithms.

AB - Given a data set, consisting of n-dimensional binary vectors of positive and negative examples, a subset S of the attributes is called a support set if the positive and negative examples can be distinguished by using only the attributes in S. In this paper we consider several selection criteria for evaluating the “separation power” of supports sets, and formulate combinatorial optimization problems for finding the “best and smallest” support sets with respect to such criteria. We provide efficient heuristics, some with a guaranteed performance rate, for the solution of these problems, analyze the distribution of small support sets in random examples, and present the results of some computational experiments with the proposed algorithms.

UR - http://www.scopus.com/inward/record.url?scp=84944104290&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944104290&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84944104290

SN - 3540414509

SN - 9783540414506

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 133

EP - 138

BT - Intelligent Data Engineering and Automated Learning - IDEAL 2000

A2 - Meng, Helen

A2 - Leung, Kwong Sak

A2 - Chan, Lai-Wan

PB - Springer Verlag

ER -

Boros E, Horiyama T, Ibaraki T, Makino K, Yagiura M. Finding essential attributes in binary data? In Meng H, Leung KS, Chan L-W, editors, Intelligent Data Engineering and Automated Learning - IDEAL 2000: Data Mining, Financial Engineering, and Intelligent Agents - 2nd International Conference, Proceedings. Springer Verlag. 2000. p. 133-138. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).