Title: A probabilistic approach to apriori algorithm

Authors: Vaibhav Sharma; M.M. Sufyan Beg

Addresses: Department of Electrical Engineering, Indian Institute of Technology, Kanpur, 208016, India. ' Department of Computer Engineering, Jamia Millia Islamia (A Central University), New Delhi, 110025, India

Abstract: We consider the problem of applying probability concepts to discover frequent itemsets in a transaction database. The paper presents a probabilistic algorithm to discover association rules. The proposed algorithm outperforms the apriori algorithm for larger databases without losing a single rule. It involves a single database scan and significantly reduces the number of unsuccessful candidate sets generated in apriori algorithm that later fails the minimum support test. It uses the concept of recursive medians to compute the dispersion in the transaction list for each itemset. The recursive medians are implemented in the algorithm as an Inverted V-Median Search Tree (IVMST). The recursive medians are used to compute the maximum number of common transactions for any two itemsets. We try to present a time efficient probabilistic mechanism to discover frequent itemsets.

Keywords: data mining; knowledge discovery; transaction databases; KDD; association rules; frequent itemsets; probability; statistics; apriori algorithms.

DOI: 10.1504/IJGCRSIS.2012.047017

International Journal of Granular Computing, Rough Sets and Intelligent Systems, 2012 Vol.2 No.3, pp.225 - 243

Received: 13 Jan 2011
Accepted: 23 Sep 2011
Published online: 29 Aug 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article