Source-linked AI summary
An Improved Apriori Algorithm for Association Rules
Mohammed Al-Maolegi, Bassam Arkok
TL;DR
Apriori is useful for discovering frequent itemsets and association rules, but repeatedly scanning transactions can waste time. The paper improves Apriori by recording transaction IDs and scanning only relevant transactions for candidate support counts, reporting a 67.38% reduction in time compared with the original algorithm.
Problem
Original Apriori repeatedly scans the database and can generate vast numbers of candidates, making it time-consuming and inefficient when support is low or itemsets are large.
Method
The improved Apriori records each item's support count and transaction IDs in L1, then uses these IDs to scan only relevant transactions when counting candidate support.
Results
67.38% average reduction in time consuming was reported for the improved Apriori compared with the original Apriori.
Takeaways & Limitations
The improved Apriori makes candidate support counting less time-consuming than the original Apriori in the reported experiments.
Takeaways & Limitations
Apriori becomes inefficient when memory capacity is limited, particularly with low minimum support or large itemsets.
Abstract
from arXiv · showhide
There are several mining algorithms of association rules. One of the most popular algorithms is Apriori that is used to extract frequent itemsets from large database and getting the association rule for discovering the knowledge. Based on this algorithm, this paper indicates the limitation of the original Apriori algorithm of wasting time for scanning the whole database searching on the frequent itemsets, and presents an improvement on Apriori by reducing that wasted time depending on scanning only some transactions. The paper shows by experimental results with several groups of transactions, and with several values of minimum support that applied on the original Apriori and our implemented improved Apriori that our improved Apriori reduces the time consumed by 67.38% in comparison with the original Apriori, and makes the Apriori algorithm more efficient and less time consuming.
1. INTRODUCTION
Data mining extracts useful and interesting patterns from large data repositories through an interdisciplinary KDD process and coordinated system components.
- Data mining discovers hidden and interesting patterns from massive datasets stored in warehouses, OLAP systems, databases, and other repositories.The paper notes that datasets may exceed terabytes.
- KDD integrates statistics, neural networks, database technology, machine learning, and information retrieval.The paper also calls data mining knowledge discovery in databases (KDD).
- The KDD process includes data cleaning, selection, transformation, preprocessing, mining, and pattern evaluation.
- A data-mining system combines repositories, a server, knowledge base, mining engine, pattern evaluation module, and graphical user interface.The mining engine includes characterization, classification, clustering, association, regression, and evolution-analysis modules.
2. ASSOCIATION RULE MINING
Association mining extracts rules from transaction data by first finding frequent itemsets and then generating rules, with applications across several sectors.
- Association mining extracts rules describing relationships among items in sales-transaction databases.The paper identifies association-rule extraction as a core data-mining activity.
- The process has two phases: detecting frequent itemsets and generating association rules.
- An itemset is frequent when its items occur together at least as often as the minimum support threshold.
- Association rules support detection of unknown relationships and can provide a basis for decision making and prediction.
- Association-rule research spans applications including telecommunications, banking, health care, and manufacturing.
3. RELATED WORK
Frequent-itemset mining is central to association mining and related pattern-discovery tasks, with algorithms organized into candidate-generation and pattern-growth approaches.
- Frequent-itemset mining discovers itemsets that recur in transaction databases and forms a core of association mining.
- Frequent-itemset mining supports tasks including association rules, episodes, classifiers, clustering, and correlation analysis.
- Frequent-itemset algorithms fall into candidate-generation and pattern-growth classes.
- Apriori generates length (k+1) candidate itemsets from length (k) frequent itemsets, whereas FP-growth uses an FP-tree and does not explicitly generate candidates.
4. APRIORI ALGORITHM
Apriori repeatedly counts itemset occurrences across the database, using frequent k-itemsets to generate candidates for the next size and pruning infrequent patterns.
- Apriori scans the database to count item occurrences and identify frequent 1-itemsets.
- Frequent k-itemsets are used to generate candidate (k+1)-itemsets in successive searches.
- Each candidate is evaluated against the minimum support threshold to determine whether it is frequent.
- If an itemset is not frequent, its larger supersets can be pruned from the database search space.
5. LIMITATIONS OF APRIORI ALGORITHM
Apriori’s main limitation is the time wasted generating and testing vast numbers of candidate itemsets. The paper proposes reducing database-search time for frequent itemsets.
- Apriori can waste substantial time handling candidate sets, especially with low minimum support or large itemsets.The paper describes costly candidate generation, testing, and accumulation as the number of candidates grows.
- 104 frequent 1-itemsets can require more than 10^7 candidates for 2-itemsets.
- Finding a frequent pattern of size 100 may require generating 2^100 candidate itemsets.
- The paper proposes an approach to reduce time spent searching database transactions for frequent itemsets.
6. THE IMPROVED ALGORITHM OF APRIORI
The improved Apriori reduces candidate-support scanning by using transaction IDs from L1 to scan only relevant transactions. Experiments compare its time consumption with original Apriori across transaction-group sizes and minimum-support values.
- Improved approach: The method uses L1 to store each item’s support count and transaction IDs, then reuses this information when generating larger candidate itemsets.L1 supports generation of L2, L3, and subsequent candidate itemsets.
- Improved approach: For each Ck, the algorithm selects the item with minimum support and scans only transactions containing that item.Candidate counts are incremented using the targeted transaction subset rather than all database transactions.
- Example: For (I1, I2), the improved algorithm searches only transactions containing the lower-support item, rather than scanning all nine transactions.The example targets transactions T1, T4, T5, T7, T8, and T9.
- Example: As k increases, the gap in scanned transactions and time consumption between improved and original Apriori increases.The number of transactions scanned for 1-itemsets is the same in both methods.
- Experiments: 67.38% average time reduction was reported across transaction groups, increasing from 61.88% for T1 to 77.80% for T5.The transaction groups contain 555 to 3000 transactions, and the reduction rate increases with transaction count.
- Experiments: 68.39% average time reduction was reported across minimum-support values, decreasing from 84.09% at 0.02 to 56.02% at 0.10.The reported reduction rate decreases as minimum support increases.
7. CONCLUSION
The improved Apriori reduces transaction scanning and candidate support-counting time compared with the original, with savings varying by itemset size and minimum support.
- 67.38%: The improved Apriori reduces time consumption compared with the original Apriori.The paper attributes the reduction to scanning fewer transactions when searching for candidate itemsets.
- Larger k-itemsets widen the time-consumption gap between the improved and original Apriori algorithms.
- Higher minimum support narrows the time-consumption gap between the improved and original Apriori algorithms.
- Candidate support counting takes less time in the improved Apriori than in the original Apriori.
Conference, Konstanz, Germany, 2000.
The supplied passages identify the authors and their academic backgrounds and research interests.
- Mohammed Al-Maolegi obtained a master’s degree in computer science in 2014 and a bachelor’s degree in computer information systems in 2010.
- Both authors list software engineering, software metrics, data mining, and wireless sensor networks among their research interests.
- Bassam Arkok obtained a master’s degree in computer science in 2014 and a bachelor’s degree in computer science from Alhodidah University.