ASSOCIATION RULE TECHNIQUE

Let us first understand the basic methodology of the Association Rule Theory. Let I be a set of literals called items, D be a set of transactions where each transaction T is a set of items such that T is a subset of I. If X is a set of some items in I and if X is a subset of T then we can say that T contains X. Association Rule Theory is a proposition of the form X => Y where X, Y both are subsets of I and X∩Y = Φ. For the rule X => Y, if c% of the transactions in D that contain X also contain Y then we can say that for that rule the confidence is c and the support for the rule is s if s% of the transactions in D contain X U Y. Itemsets with minimum support are called as large itemsets and those with support less than minimum support are referred to as small itemsets. For a given set of transactions D, the problem of mining association rules is to generate all the association rules that have confidence and support greater than the user specified minimum confidence and support.

BACKGROUND

Association Rule Discovery, a data mining technique, was formally introduced by Rakesh Agarwal, Ramakrishnan Srikant and Imielinski in the year 1993. The research on this technique was carried out under the “Quest Project at IBM Almaden Research Center” and at the “University of Helsinki”. The technique association rules works on the principle of finding relationships between transactions in a database. Since each transaction contains a set of items the algorithm specifies to find an item x such that every occurrence of x specifies occurrence of another item say y. Hence the association rule x=>y will hold true if the confidence and support for this rule is greater than the user specified minimum confidence (minconf) and minimum support (minsup). Support is counted as the percentage of transactions containing the itemset to the total number of transactions in the database. Confidence is the percentage of transactions containing an itemset to the number of transactions containing the subset of the itemset. Basically, there are two steps involved in finding out the association rules in the transactional databases. First is to generate the frequent k itemsets. Second is to generate the association rules between those itemsets which will hold true if they satisfy the minimum support and minimum confidence.

Association Rule Discovery is one of the most famous and widely accepted strategies of data mining that focuses on detecting interesting associations between items in the large databases. Commonly used for market basket analysis in order to determine the likely combinations of items that will appeal to a consumer based on prior records, it has also been used to create predictive association rules for classification problems. The information collected using Association Rule Discovery technique also help the companies in making decisions, forecasting sales, determining frauds, etc.

The paper below summarizes the basic methodology of association rules along with the mining association algorithms in the third section. The algorithms include the most basic Apriori algorithm along with other algorithms such as AprioriTid, AprioriHybrid, MiRABit, Inverted Hashing and Pruning and Perfect Hashing and Pruning. Fourth section of the paper includes two case studies which demonstrate the usefulness of association rule technique in the real world. The first case study relates to the continuous analysis of the market basket data in retail organizations in order to help the management to take decisions based on the associations revealed between various products. The second case study addresses the crucial problem of traffic safety in Belgium and explains the use of association rules as an effective data mining technique for outlining the main spots and zones which are highly prone to accidents in Belgium. This case study also use association rules to discover the discriminatory characteristics that exist between the high frequency accident locations and the low frequency accident locations. The fifth and the final section contains the conclusion for the paper.

INTRODUCTION ASSOCIATION RULE DISCOVERY

T.S.Eliot, the famous poet, once said “Where is the wisdom we have lost in knowledge? Where is the knowledge we have lost in information?” . In every sphere of life, important decisions have to be taken in order to overcome the problems or to make profits in business. The information required for taking such decisions comes from the study of the data which is stored in large databases. Without rigorous analysis of these databases, it is not possible to extract important information underlying in that data. The sudden increase in the size of databases has resulted in the need for the development of such tools and techniques that are able to extract useful knowledge automatically by analyzing these large transactional databases in an efficient manner. Discovering the different patterns and behavior in these large databases is called knowledge discovery in database or data mining. Data Mining has been described as “"The non trivial extraction of implicit, previously unknown, and potentially useful information from data"”. It is used to find out some trends in real life which may not have been noticed but can be highly significant once they are discovered.

Most of the times the term “Data Mining” is confused with the term “Statistics” as both aims at exploring the structure of the data. While the groundwork was laid in the traditions of a statistician’s penchant for exhaustive collections of data, data mining techniques differ fundamentally from the conventional methods of analysis. Central to this difference is the weightage placed on the algorithm rather than the model. There are various data mining techniques used in the industry which can be broadly classified into classical techniques and next generation techniques. Some of them are clustering, decision trees, bayesian network, classification rules, data summarization, neural networks and many others. Association Rule Discovery is one such dimension of data mining which comes under the next generation techniques.