La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Computational Complexity of Finding Meaningful Association Rules Complexité informatique liée à la recherche de règles d'association significatives

Yeon-Dae KWON, Ryuichi NAKANISHI, Minoru ITO, Michio NAKANISHI

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.9 pp.1945-1952
Date de publication
1999/09/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Algorithmes et Structures de Données

Auteurs

Mots-clés

Table des matières