A probabilistic approach to apriori algorithm. (1st January 2012)

• Record Type: Journal Article
• Authors: Sharma, Vaibhav; Sufyan Beg, M.M.
• Is Part Of: International journal of granular computing, rough sets and intelligent systems. Volume 2:Number 3(2012)
• Page Start: 225
• Page End: 243
• Publication Date: 2012-01-01
• Subjects: data mining -- knowledge discovery in databases -- KDD -- association rules -- frequent itemsets -- probability -- statistics -- apriori algorithm; Intelligent agents (Computer science) -- Periodicals; 006.3
• Languages: English
• ISSNs: 1757-2703

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.