Data Mining is extracting knowledge from data. Knowledge may be presented using rules which express relationships between sets of items involved in the rule. The nature and strength of the relationship is determined by an evaluation measure used to evaluate the rules. A relationship may correspond to an association, an implication, a correlation, a causality, a dependency, etc. This thesis considers the problem of finding the strongest N rules from transaction data. Existing algorithms (e.g. Apriori) employ search techniques based on Best-First Search methods which impose high demands on memory. Searching Depth-First solves this memory problem but can demand long execution time. This drawback can be avoided by using iterative deepening search where the Depth-First Search is run with a progressively relaxed search bound on each successive iteration. Relaxing the search bound can be based on various characteristics of the search space, such as a change in the tree depth (MSDD algorithm), or a change in the quality of states being explored. The key issue is the strategy by which the search bound is relaxed for subsequent iterations. We propose an iterative deepening search algorithm IDGmax using a search bound strategy based on the quality of states explored. We explore different methods for relaxing the search bound to improve the performance. We present experimental results to evaluate the performance of these search bound relaxation strategies and compare them to the MSDD algorithm. We also show that the choice of the search bound relaxation method can significantly influence the performance of the rule mining algorithm in both memory and time.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/9205 |
| Date | January 2001 |
| Creators | Elazmeh, William Wasim. |
| Contributors | Holte, Robert, |
| Publisher | University of Ottawa (Canada) |
| Source Sets | Université d’Ottawa |
| Detected Language | English |
| Type | Thesis |
| Format | 143 p. |
Page generated in 0.0055 seconds