Discovering associations in very large databases by approximating

Zhang Schichao and Zhang Chengqi: Discovering associations in very large databases by approximating. In: Acta cybernetica, (16) 1. pp. 155-177. (2003)

[thumbnail of cybernetica_016_numb_001_155-177.pdf]
Cikk, tanulmány, mű

Download (1MB) | Preview


Mining association rules has posed great challenge to the research community. Despite efforts in designing fast and efficient mining algorithms, it remains a time consuming process for very large databases. In this paper, we adopt a slightly different approach to this problem, which can mine approximate association rules quickly. By considering the database as a set of records that are randomly appended, we can apply the central limit theorem to estimate the size of a random subset of the database, and discover both positive and negative association rules by generating all possible useful itemsets from the random subset. However, because of approximation errors, it is possible for some valid rules to be missed, while other invalid rules may be generated. To deal with this problem, we adopt a two phase approach. First, we discover all promising approximate rules from a random sample of the database. Second, these approximate results are used as heuristic information in an efficient algorithm that requires only one-pass of the database to validate rules that have support and confidence close to the desired support and confidence values. We evaluated the proposed technique, and our experimental results demonstrate that the approach is efficient and promising.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2003
Volume: 16
Number: 1
ISSN: 0324-721X
Page Range: pp. 155-177
Language: English
Place of Publication: Szeged
Related URLs:
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2022. Jun. 15. 08:43

Actions (login required)

View Item View Item