Effective elimination of redundant association rules |
| |
Authors: | James Cheng Yiping Ke Wilfred Ng |
| |
Affiliation: | (1) Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China |
| |
Abstract: | It is well-recognized that the main factor that hinders the applications of Association Rules (ARs) is the huge number of ARs returned by the mining process. In this paper, we propose an effective solution that presents
concise mining results by eliminating the redundancy in the set of ARs. We adopt the concept of δ
tolerance to define the set of δ-Tolerance ARs (δ-TARs), which is a concise representation for the set of ARs. The notion of δ-tolerance is a relaxation on the closure defined on the support of frequent itemsets, thus allowing us to effectively prune
the redundant ARs. We devise a set of inference rules, with which we prove that the set of δ-TARs is a non-redundant representation of ARs. In addition, we prove that the set of ARs that is derived from the δ-TARs by the inference rules is sound and complete. We also develop a compact tree structure called the δ-TAR tree, which facilitates the efficient generation of the δ-TARs and derivation of other ARs. Experimental results verify the efficiency of using the δ-TAR tree to generate the δ-TARs and to query the ARs. The set of δ-TARs is shown to be significantly smaller than the state-of-the-art concise representations of ARs. In addition, the approximation
on the support and confidence of the ARs derived from the δ-TARs are highly accurate. |
| |
Keywords: | Association rules Redundancy elimination Concise representation |
本文献已被 SpringerLink 等数据库收录! |
|