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.
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 *