| The application of association rules, which specify relationships among large sets of items, is a fundamental data mining technique used for various applications. In this dissertation, we present an efficient method of using association rules for identifying rules from a stream of transactions consisting of a collection of items purchased, referred to as market basket data. A common problem encountered with market basket analysis is that it results in a number of weakly associated rules that are of little interest to the user. To mitigate this problem, we propose an efficient approach to managing the data so that only a reasonable number of rules need to be analyzed. First, we apply an ontology, a hierarchical structure that defines the relationships among concepts at different abstraction levels, to minimize the search space, thereby allowing the user to avoid having to search the large original result set for useful and important rules. Next, we apply a novel metric called relevance to categorize the rules using the Hierarchical Association Rule Categorization (HARC) algorithm, an algorithm that efficiently categorizes association rules by searching the compact generalized rules first and then the specific rules that belong to them, rather than scanning the entire list of rules. The efficiency and effectiveness of our approach is demonstrated in our experiments on high-dimensional synthetic data sets. |
