Int. J. of Granular Computing, Rough Sets and Intelligent Systems   »   2012 Vol.2, No.3

 

 

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

 

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

 

Date of acceptance: 23 Sep 2011
Available online: 27 May 2012

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article