 Open Access
 Total Downloads : 516
 Authors : Vintee Chaudhary, Aparna Choudhary, Nawagata Nilambari, Manika Tyagi
 Paper ID : IJERTV3IS042032
 Volume & Issue : Volume 03, Issue 04 (April 2014)
 Published (First Online): 29042014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Review on Association Rule Mining: A Survey
Vintee Chaudhary Aparna Choudhary
M.Tech(CS&E) M.Tech(CS&E)
School of Computing Science and Engineering School of Computing Science and Engineering Galgotias University, Greater Noida, U.P . Galgotias University, Greater Noida, U.P.
Nawagata Nilambari Manika Tyagi
M.Tech(CS&E) M.Tech(CS&E)
School of Computing Science and Engineering School of Computing Science and Engineering Galgotias University, Greater Noida, U.P. Galgotias University, Greater Noida, U.P.
Abstract: Association rule mining plays important role in the field of data mining. Association rule mining is a technique that helps to prepare the way to improve the mining technique. It is a method to discover relationships among variables in the database. Association rule basically divided into two different parts (a) an antecedent and (b) a consequent. In association rule mining different types of approaches and algorithms have been designed but it is very important to know which approach is best and suitable for association rule. So In this paper, we present a complete survey on different algorithms and approaches used in association rule mining in different domain.
Keywords Association rules, Apriori, Confidence, Support, Frequent itemsets, Minimum support.

INTRODUCTION
Data mining is used to extract potentially useful, meaningful and valid information from large databases. Data mining plays important role in analyzing large database and extract relevant information from a data repository. Database, data warehouse, the other information repository is a data source .Association rule is used for mining data for frequent itemsets. Association can also define as finding frequent patterns. Frequent pattern is item sets which occur frequently in the data.
There are various data mining technology which is link mining, clustering, statistical learning, association rule mining and classification .Using data mining technology data analyzing and pattern extraction is accomplished. All of these have their importance in development and data research. GUHA procedure, FPgrowth algorithm Eclat algorithm, ASSOC, OPUS search are algorithm which is used for association rule mining. But APRIORI is the best algorithm to generate association rule[1].

Association Rule Mining
Association rule can be defined as the relationship between items with confidence and support. Association rule can be represented as AC in which A is an antecedent and C is consequent .It follows if and then statement where the antecedent is if and consequent is then [2].
Before discussing association rule it is necessary to define APRIORI algorithm. There are some terms which help to understand the concept of APRIORI algorithm. These terms describe below:
Itemsets:
Item sets are a group of items together in a single transaction. It is the accumulation of item sets. If database contains n items than there are 2n item sets
Support:
Support is defined as no. of transaction containing that item. Support of rule can be defined as no. of transaction containing both antecedent and consequent. Support of
AC is defined as No. of transaction that contain both A and C.
Confidence:
Confidence of rule is defined as no. of transaction containing both antecedent and consequent divided by No
.of transaction containing antecedent. Support of AC is No. of transaction that contain both A and C divided by No. of transaction containing A.
Frequent itemsets:
If support of itemsets is greater than or equal to minimum support then it is called frequent item sets otherwise item sets are infrequent.

APRIORI Algorithm
APRIORI algorithm is a classical algorithm. APRIORI algorithm is used to find frequent itemsets from large databases. APRIORI algorithm has two steps which are

Join step

Prune step

Join step
To find Lk, joining Lk1 with itself to generate Ck. Ck is collection of candidate item set of size k. Lk is collection of frequent item sets of size k.
Prune step
In this step find all frequent item sets. Lk is the subset of Ck but it is not necessary that all items in Ck are frequent. To determine the support count of each candidate in Ck scans the database. If support count of item sets is greater than or equal to minimum support then item sets are frequent which belongs to Lk. And if support count of item sets is not greater than or equal to minimum support then it is not frequent. After this item set which are not frequent eliminates from Ck. This process continues until all frequent items occur in Lk[3].
Example of candidate itemset and frequent itemsets generation with minimum support is 2.The transaction database is given below.
TID
Items
T1
ABC
T2
BD
T3
BC
T4
ABD
T5
AC
T6
BC
T7
AC
T8
ABCE
T9
ABC
T10
F
Candidate 1 itemsets (C1)
Itemsets
Support Count
A
6
B
7
C
7
D
2
E
1
F
1
Frequent 1 itemsets (L1)
Itemsets
Support Count
A
6
B
7
C
7
D
2
Candidate 2 itemsets(C2)
Itemsets
Support Count
AB
4
AC
5
AD
1
BC
5
BD
2
CD
0
Frequent 2 itemsets (L2)
Itemsets
Support Count
AB
4
AC
5
BC
5
BD
2
Candidate 3 itemsets (C3)
Itemsets
Support Count
ABC
3
ABD
1
BCD
1
Frequent 3 itemsets (L3)
Itemsets
Support Count
ABC
3
ABC is frequent itemsets. These frequent itemsets is used to generate association rules that satisfied minimum support and minimum confidence criteria.


LITRETURE SURVEY
In this section, we discussed on some approaches and algorithms used in association rule mining.

An Approach to Improve Apriori Algorithm Based On Association rule Mining [1]. proposed a new algorithm, improve APRIORI algorithm which is used to reducethe limitation of APRIORI algorithm.Task is divided into two parts. In a first part eliminates bad or duplicate data from database to improve database consistency and in second part proposed algorithm applied to filtered datasets. Proposed algorithm computes support count of candidate itemsets like a APRIORI algorithm compute. It generates frequent itemsets, candidate itemsets. Improve algorithm applied to the dataset and eliminate infrequent itemsets from each transaction. Horizontal partitioning also applied to datasets.It takes less time to generate association rule and generate fewer rule as compared to an original APRIORI algorithm.

Mining Association Rule from Data with Missing Values by Database Partition and Boolean Matrix[4]. elaborates a Database Partitioning & Boolean Matrix. This algorithm applied on data which have missing values for mining association rule. To generate frequent itemsets very quickly, proposed algorithm used Boolean matrix and conjunction operation. For mining association rule from large dataset it takes less memory space and time.

An Improved Tree Algorithm for Association Rule Mining Using Transaction Reduction [5]. presents a new algorithm which is used to overcome the limitation of APRIORI algorithm. This proposed algorithm is used to increase the execution time of processing and reduce candidate item sets. Hash table used to reduce multiple time scanning of the database.

An Integrated Approach to Derive Effective Rules from Association Rule Mining Using Genetic algorithm [6]. proposed an algorithm which is the combination of APRIORI algorithm and Genetic algorithm. The Proposed algorithm is used to overcome the drawback of classical algorithm. Using the classical algorithm , find frequent item sets with single minimum support but using proposed algorithm , multiple minimum support is consider to find frequent item sets. APRIORI algorithm with multiple minimum supports is used to find frequent item set and generate association rules. To find reduced set of association rule, genetic algorithm is used. Lift factor is also used to find a strong association rule. It generates less association rule.

A Parallel Algorithm of Association Rules Based on Cloud Computing [7]. new method parallel association rule mining based on cloud computing is proposed. To reduce inter processor communication and I/P overhead. Proposed algorithm takes up the separation strategy which is used to visit a local database only once. A framework for a cloud computing platform system are proposed. With the cloud environment this framework helps to use cloud nodes
to protect data privacy. A PFP(Parallel Frequent Pattern) growth model is used to mine maximal frequent itemsets and frequent closed itemsets. For cloud computing platform, a cloud based PFP growth model is combined with Map Reduce Model. Meanwhile Map Reduce Model is used to mine data from the database and build local FP tree to improve efficiency of data mining and reduce communication overhead and offer good speed up.

An Improved Algorithm for Mining Association Rules in Large Database[8]. elaborates a novel approach for association rule mining which can be used for generating association rule effectively for large database. To reduce the execution time of algorithm, features of items and weight of candidate item sets are used. Transaction database is transformed into features matrix. Transformation is used to reduce the no. of I/P access and speeding up mining process. In this proposed algorithm leverage measures is used to find interestingness of rule. Leverage measure is used to reduce the candidate item sets generation and reduce the memory space requirement which is used to store useless candidate item sets.

Hybrid AssociationClassification Algorithm for Anomaly Extraction [9].A hybrid algorithm which is the combination of fuzzy algorithm and a classification algorithm that is used to generate an association rule. Frequent item sets are generated using a fuzzy APRIORI algorithm and then CART algorithm is applied on frequent item sets to generate lesser rules and for better network anomalies. It takes less time and give less error rate and also provide higher accuracy.

Association Rule Mining based on APRIORI Algorithm in Minimizing Candidate Generation [10]. To improve the APRIORI algorithm, two factors which are set size and set frequency are added in APRIORI algorithm where set size is no. of items per transaction and set frequency is the no. of transaction that contain at least a set size items. Set size and set frequency are used to remove useless candidate generation. Using these factors, the proposed algorithm minimized candidate generation in an efficient and effective way. These factors helped to generate frequent item sets very quickly. It takes less execution time as compared to APRIORI algorithm.

MRA for Association Rule Mining used for Cooperative Learning [11]. APRIORI algorithm with multiple level used to generate frequent item sets. The Proposed algorithm is called Multilevel Relationship Algorithm(MRA). Multilevel APRIORI algorithm and Bayesian Probability is combined together to generate an association rule. The new algorithm is applied to various datasets and find frequent item sets and external
dependencies. In this proposed work generate association rule more efficiently.

Programming Parallel Apriori Algorithm for Mining Association Rules[12]. There are various parallel programming languages that provide low level construct but some difficulties occur when implement, design, debug, and maintain these programming languages. A parallel programming using a sequential programming language helps the programmer to debug, design and implement. The parallel paradigm gives high level language construct to implement distributed and parallel algorithm. To avoid that processor s speed is not slow down when generating frequent item sets , dataset and item set is partitioned into different parts and give to the processor. This proposed algorithm improves the efficiency of original APRIORI algorithms.

Optimizing network traffic by generating association rules using Hybrid AprioriGenetic algorithm [2]. APRIORI and Genetic algorithm are used This algorithm applied on network traffic data sets. It generates less frequent item sets and takes less computational time. Then it generates less rules for the network traffic as compared to an original APRIORI algorithm.

An Efficient Approach Using Rule Induction and Association Rule Mining Algorithm in Data Mining [13].
Rule induction algorithm helps to find the best result. To cover large data from the dataset, it used Decision List Induction algorithm. It used Induction Rule algorithm to generate association rule with less error rate. Then find a reduced set of rule.

An Improved APRIORI Algorithm for Association Rules [14]. Improve APRIORI algorithm is used to reduce the limitation of the original APRIORI algorithm. The proposed algorithm reduces the wasting time which is used to scan the whole database for generating frequent itemsets. It scans only some transaction. This algorithm generates association rules efficiently with less time.

A Study on Various Data Mining Approaches of Association Rules[15]. To remove the replicas from data sets, preprocessing is applied on datasets to find desired data set. From desired data set, candidate item sets are found. For finding frequent item sets, candidate item sets is scanned. Strong Association rules are generated from frequent item sets. For time complexity and space complexity, Hash tree and Hash Mapping table is used.


CONCLUSION AND FUTURE WORK Association Rule Mining is a good topic for the
research in data mining. In this paper we present the
complete survey of Association Rule Mining algorithms
and approaches. From this survey we found that there are various new nd improved algorithms which are used for generating association rule. But there are some problem occurs for generating association rules that are solved by data mining researchers in the upcoming times.
REFERENCES

Chanchal Yadav, Shuliang Wang and Manoj Kumar, An Approach to Improve Apriori Algorithm Based On Association rule Mining. 4th ICCCNT – 2013 July 46, 2013, Tiruchengode, India

Surendra Kumar Chadokar, Divakar Singh and Anju Singh Optimizing network traffic by generating association rules using Hybrid AprioriGenetic algorithm 2013 IEEE.

Mrs. R. Sumithra and Sujni Paul. Using distributed apriori association rule and classical apriori mining algorithms for grid based knowledge discovery 2010 Second International conference on Computing, Communication and Networking Technologies, IEEE, 2010.

Jayanti Dansana, Shailender Kumar, Abhilash Kumar Srivastava,
Mining Association Rule from Data with Missing Values by Database Partition and Boolean Matrix ,IEEE – International Conference on Research and Development Prospects on Engineering and Technology (ICRDPET 2013) Vol.5 March 29, 30 – 2013 .

Krishna Balan, Karthiga and Sakthi Priya, An Improved Tree Algorithm for Association Rule Mining Using Transaction Reduction, International Journal of Computer Application Technology and Research, Volume2, Issue2, 166169, 2013.

Kannika Nirai M and E Ramaraj, An Integrated Approach to Derive effective rules from Association Rule Mining using Genetic Algorithm, 2013 International Confrence on Pattern Recognition, Informatics and Mobile Engineering (PRIME) February 2122.

Wang Yong, Zhang Zhe and Wang Fang, A Parallel Algorithm of Association Rules Based on Cloud Computing, 2013 8th International Confrence on Communication and Networking in China (CHINACOM).

Farah Hanna ALZawaidah, Yosef Hasan Jabara and Marwan AL Abed AbuZanona, An Improved Algorithm for Mining Association Rules in Large Database, World of Compuer Science and Information Technology Journal(WCSIT) ISSN: 22210741 Vol.1, No. 7, 311316, 2011.

Gaurav Shelke, Anurag Jain and Shubha Dubey, Hybrid Association Classification Algorithm for Anomaly Extraction, 4th ICCCNT 2013 July 46 2013 Tiruchengode, India.

Sheila A. Abaya, Association Rule Mining based on Apriori Algorithm in Minimizing Candidate Generation, International Journal of Scientific & Engineering Research, Volume 3, Issue 7, July 2012 ISSN 22295518.

Deepak A Vidhate and Parag Kulkarni, Multilevel Relationship Algorithm for Association Rule Mining used for Cooperative Learning, International Journal of Computer Applicatio(0975 8887), Volume 86, No. 4, January 2014.

Chia Chu Chiang, Programming Parallel Apriori Algorithm for Mining Association Rules, 2010 International Confrence on System Science And Engineering.

Kapil Sharma and Sheveta Vashisht, An Efficient Apporach Using Rule Induction and Association Rule Mining Algorithms in Data Mining, Graduate Research in Engineering and Technology: An International Journal ISSN 23206632, Volume1, Issue2, 2013.

Hassan M.Najadat, Mohammed ALMaolegi, Bassam Arkok, An Improved Apriori Algorithm For Association Rules, International Research Journal of Computer Science and Application Vol.1, No.1, June 2013, PP: 0108.

Rachna Somkunwar, A Study on Various Data Mining Approaches of Association Rules,International Journal of Advanced Research in Computer Science and Software Engineering Volume.2, Issue9, September 2012, pp.141144.