The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Les développements récents de la technologie informatique nous permettent d’analyser toutes les données d’une immense base de données. L'exploration de données est d'analyser toutes les données d'une telle base de données et d'obtenir des informations utiles pour les utilisateurs de la base de données. L'un des problèmes bien étudiés en matière d'exploration de données est la recherche de règles d'association significatives dans une base de données de paniers de consommation contenant des quantités massives de transactions. Une façon de trouver des règles d'association significatives consiste à rechercher d'abord tous les grands ensembles d'éléments, puis à trouver des règles d'association significatives à partir des grands ensembles d'éléments. Bien qu'un certain nombre d'algorithmes pour calculer tous les grands ensembles d'éléments aient été proposés, leur complexité de calcul est à peine discutée. Dans cet article, nous montrons qu’il est NP-complet de décider s’il existe un grand ensemble d’éléments ayant une cardinalité donnée. Nous proposons également des sous-classes de bases de données dans lesquelles toutes les règles d'association significatives peuvent être calculées dans un polynôme temporel de la taille d'une base de données.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Yeon-Dae KWON, Ryuichi NAKANISHI, Minoru ITO, Michio NAKANISHI, "Computational Complexity of Finding Meaningful Association Rules" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 9, pp. 1945-1952, September 1999, doi: .
Abstract: Recent developments in computer technology allow us to analyze all the data in a huge database. Data mining is to analyze all the data in such a database and to obtain useful information for database users. One of the well-studied problems in data mining is the search for meaningful association rules in a market basket database which contains massive amounts of transactions. One way to find meaningful association rules is to find all the large itemsets first, and then to find meaningful association rules from the large itemsets. Although a number of algorithms for computing all the large itemsets have been proposed, the computational complexity of them is scarcely disscussed. In this paper, we show that it is NP-complete to decide whether there exists a large itemset that has a given cardinality. Also, we propose subclasses of databases in which all the meaningful association rules can be computed in time polynomial of the size of a database.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_9_1945/_p
Copier
@ARTICLE{e82-a_9_1945,
author={Yeon-Dae KWON, Ryuichi NAKANISHI, Minoru ITO, Michio NAKANISHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computational Complexity of Finding Meaningful Association Rules},
year={1999},
volume={E82-A},
number={9},
pages={1945-1952},
abstract={Recent developments in computer technology allow us to analyze all the data in a huge database. Data mining is to analyze all the data in such a database and to obtain useful information for database users. One of the well-studied problems in data mining is the search for meaningful association rules in a market basket database which contains massive amounts of transactions. One way to find meaningful association rules is to find all the large itemsets first, and then to find meaningful association rules from the large itemsets. Although a number of algorithms for computing all the large itemsets have been proposed, the computational complexity of them is scarcely disscussed. In this paper, we show that it is NP-complete to decide whether there exists a large itemset that has a given cardinality. Also, we propose subclasses of databases in which all the meaningful association rules can be computed in time polynomial of the size of a database.},
keywords={},
doi={},
ISSN={},
month={September},}
Copier
TY - JOUR
TI - Computational Complexity of Finding Meaningful Association Rules
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1945
EP - 1952
AU - Yeon-Dae KWON
AU - Ryuichi NAKANISHI
AU - Minoru ITO
AU - Michio NAKANISHI
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 1999
AB - Recent developments in computer technology allow us to analyze all the data in a huge database. Data mining is to analyze all the data in such a database and to obtain useful information for database users. One of the well-studied problems in data mining is the search for meaningful association rules in a market basket database which contains massive amounts of transactions. One way to find meaningful association rules is to find all the large itemsets first, and then to find meaningful association rules from the large itemsets. Although a number of algorithms for computing all the large itemsets have been proposed, the computational complexity of them is scarcely disscussed. In this paper, we show that it is NP-complete to decide whether there exists a large itemset that has a given cardinality. Also, we propose subclasses of databases in which all the meaningful association rules can be computed in time polynomial of the size of a database.
ER -