Computational Complexity of Finding Highly Co-occurrent Itemsets in Market Basket Databases
スポンサーリンク
概要
- 論文の詳細を見る
Data mining is to analyze all the data in a huge 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 sales transactins. The problem of mining meaningful association rules is to find all the large itemsets first, and then to construct meaningful association rules from the large itemsets. In our previous work, we have shown that it is NP-complete to decide whether there exists a large itemset with a given size. Also, we have proposed a subclass of databases, called k-sparse databases, for which we can efficiently find all the large itemsets. Intuitively, k-sparsity of a database means that the supports of itemsets of size k or more are sufficiently low in the database. In this paper, we introduce the notion of (k, c)-sparsity, which is strictly weaker than the k-sparsity in our previous work. The value of c represents a degree of sparsity. Using (k, c)-sparsity, we propose a larger subclass of databases for which we can still efficiently find all the large itemsets. Next, we propose alternative measures to the support. For each measure, an itemset is called highly co-occurrent if the value indicating the correlation among the items exceeds a given threshold. In this paper, we define the highly co-occurrent itemset problem formally as deciding whether there exists a highly co-occurrent itemset with a given size, and show that the problem is NP-complete under whichever measure. Furthermore, based on the notion of (k, c)-sparsity, we propose subclasses of databases for which we can efficiently find all the highly co-occurrent itemsets.
- 社団法人電子情報通信学会の論文
- 2000-12-25
著者
-
Kwon Y‐d
Korea Credit Guarantee Fund Kor
-
Ito M
Nara Inst. Sci. And Technol. Nara Jpn
-
KWON Yeon-Dae
the Graduate School of Information Science, Nara Institute of Science and Technology
-
ISHIHARA Yasunori
the Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osak
-
SHIMIZU Shougo
the Graduate School of Information Science, Nara Institute of Science and Technology
-
ITO Minoru
the Graduate School of Information Science, Nara Institute of Science and Technology
-
Ishihara Y
Osaka Univ. Toyonaka‐shi Jpn
-
Ishihara Y
Osaka Univ. Osaka Jpn
-
SHIMIZU Shougo
Graduate School of Information Science, Nara Institute of Science and Technology
-
Shimizu Shougo
Graduate School Of Information Science Nara Institute Of Science And Technology
関連論文
- Computational Complexity of Finding Meaningful Association Rules
- Computational Complexity of Finding Highly Co-occurrent Itemsets in Market Basket Databases
- A Formal Approach to Detecting Security Flaws in Object-Oriented Databases (Special Issue on New Generation Database Technologies)
- An Authorization Model for Object-Oriented Databases and Its Efficient Access Control
- Assignment of Data Types to Words in a Natural Language Specification
- Implementation of Natural Language Specifications of Communication Protocols by Executable Specifications
- A Translation Method from Natural Language Specifications of Communication Protocols into Algebraic Specifications Using Contextual Dependencies
- Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas
- Mole Fraction Control of Poly(3-Hydroxybutyric-Co-3-Hydroxyvaleric Acid in Fed-Batch Culture of Alcaligenes eutrophus
- 343 Mole Fraction Control of PHA in Fed-Batch Culture of Alcaligenes eutrophus
- Characteristics of Ice-nucleation Activity in Fusarium avenaceum IFO 7158
- Dynamics of the Hydration of Amino Alcohols and Diamines in Aqueous Solution
- Dynamics of the Hydration of Halogenoalcohols in Aqueous Solution