Comparative Study of Association Rule Algorithms

Unlock access to all the studying documents.

View Full Document

Title to Paper: Comparative Study of Association Rule Algorithms

Abstract: Association rules are commonly considered the simplest of the data mining

techniques. Many individuals not familiar with the intricacies of association rules do not

know the multitude of algorithms available. In this paper we will discuss some of the

association rule algorithms available for this popular data mining technique. The paper will

discuss in detail how the different algorithms are calculated and the positives and negatives

of each algorithm. We will analyze the necessity of association rule algorithms to be

efficient as possible due to the large number of calculations needed for association rules.

Table of Contents

Cover Page…………………………………………………………………………………………………………1

Abstract……………………………………………………………………………………………………………..2

Table of Contents………………………………………………………………………………………………..3

Term Paper Introduction………………………………………………………………………………………4

Purpose of Paper………………………………………………………………………………………4

Background……………………………………………………………………………………………..4

Defenitions………………………………………………………………………………………………5

Algorithms…………………………………………………………………………………………………………10

Brute-Force Technique……………………………………………………………………………..10

Apriori Algorithm…………………………………………………………………………………….12

Frequent Pattern Growth Algorithm……………………………………………………………15

CHARM Algorithm………………………………………………………………………………….18

Algorithms Performance………………………………………………………………………………………20

Conclusion…………………………………………………………………………………………………………21

Restatement of association rule mining……………………………………………………….21

Benefits of understanding the four algorithms………………………………………………22

Work Cited (Bibliography)…………………………………………………………………………………..23

Introduction

Purposes of Assignment

The purpose of this paper is to analyze the different types of algorithms used in association

rules mining. When reviewing the rules that apply to association rules, it can be described

as “Association rule mining is a popular data mining method that is commonly used as an

example to explain what data mining is and what it can do to a technologically less-savvy

audience”, Turban, Sharda, Delen & King (2010, p166). I believe this saying comes from

the simple way association rules algorithms are calculated. Most corporate or small

business employees understand the concept behind an excel spreadsheet or database and

they have the understanding of how association rules algorithms would associate two

products together by scanning through a database. When looking further into this way of

understanding, the simplicity stops with association rules algorithms and having a more

technical understanding begins. This paper is to show that using association rules to its

fullest capacity will take a technical savvy individual that understands the best association

rule algorithm to use based on the desired performance wanted. As well as looking into the

rules of algorithms, we will review the technical workings as well as determine the

positives and negatives of the algorithms, and review the resource constraints the

algorithms can cause due to performance issues.

Background

Association rules are important data mining techniques, that look through traditional

transaction based records and finds statistical associations between items. The transactions

that are analyzed using association rules can be found in a company’s data warehouse or

application used to process the company’s point of sale transactions. Association rules are

commonly called a market-basket analysis which is the name associated to the data

mining’s technique commonly use in retail or e-commerce which works with tracking of

common products or services purchased together.

It is important to have a basic definition of association rules before better understanding

the different type of algorithms that can be used. A simplistic definition of the rule can be

found by the author Ponniah, P. (2010, p446).

Associations are affinities between items. Association’s discovery algorithms find

combinations where the presence of one item suggests the presence of another. When you

apply these algorithms to the shopping transactions at the supermarket, they will uncover

affinities among products that are likely to be purchased together.

Association rules helps marketing departments better understand where to locate their

products and what products to put on sale, so that the company can maximize profits.

Turban et al., (2010, p167) provides 3 techniques that marketing departments can utilize to

maximize revenue and profits.

(1) putting the items next to each other to make it more convenient for the customers to

pick them up together and not forgot to buy one when buying the others (increasing sales

volume); (2) promoting the items as a package (do not put one on sale if the other(s) is on

sale); and (3) placing them apart from each other so that the customer has to walk the

aisles to search for it, and by doing so potentially seeing and buying other items.”

It is important to understand the how the business will utilize association rules to clearly

understand the advantages and disadvantages of the algorithms that will be discussed

throughout the paper. Without understanding the key elements that a data scientist would

use the algorithm for, the ability to further improve on new algorithms could not be

foreseen.

Definitions

Before diving into the many algorithms that can be used in association rule mining,

establishing definitions is needed to better understand the differences in the association

rules algorithms. Shmueli, Patel & Bruce (2010, p265) definition of association rules states

“The idea behind association rules is to examine all possible rules between items in an

if-then format and select only those that are most likely to be indicators of true

dependence”. Shmueli, et al., (2010, p266) helps explain how association rules processes

data.

The first step in affinity analysis is to generate all the rules that would be candidates for

indicating associations between items. Ideally, we might want to look at all possible

combinations of items in a database with p distinct item. This means finding all

combinations of single items, pairs of items, triplets of items, and so on in the transaction

database.

There are two parts of the association rule equation. The first part of the equation is the (if)

calculation or the antecedent, also called the left handed side or LHS. The second part of

the equation is the (then) calculation or the consequent, also called the right handed side or

RHS.

Algorithms are described by Shmueli et al., (2010, p7), as a “specific procedure used to

implement a particular data mining technique: classification tree, discriminant analysis and

the like.” An algorithm can be defined as a step by step computer procedure that follows a

calculation to solve problems. The association rule algorithms that this paper analyzes are

the Brute Force, Apriori, Apriori-Hybrid, Apriori-Tid, Frequent Pattern Growth and the

Charm algorithm.

A model according to Shmueli et al., (2010), is an algorithm that is applied to a dataset,

complete with the models settings. Typically a model has parameters that the users adjusts

to maximize the performance of the algorithm. For example each time the parameters are

adjusted a new model is created. Models are created by applying the algorithms and the

parameters to the training data.

To understand association rules algorithms there is a need to define what a frequent itemset

is. A frequent itemset is a solution to a common performance issue found while using

association rules. Generating all possible combinations in the if-then statement can be

expensive on the I/O and CPU. According to Shmueli et al., (2010), a good solution would

be to only look for combinations that occur with a high frequency in the database, this is

called frequent itemsets. The use of frequent itemsets is an important concept that is the

basis of how the different association rules algorithms process data. An example database

with two transactions that are (A, B, C, D) and (A, B, C, D, E, F), each letter representing

an item purchased in the transaction. When looking at the terminology, we can clearly

define the definition known as support, assuming the upkeep for the association rule model

is set at fifty percent. The association rules model would have to calculate sixty three

frequent itemsets. The frequent itemsets that would be calculated in the models algorithm

would include (A), (B), (C), (A, B), (A, C), ….., (A, B, C, D, E, F). The calculation of

multiple frequent itemsets can become cumbersome and large, this causes performance

issues.

Frequent itemsets are important to association rule mining, but some algorithms only

search another type of frequent itemset, which are called closed frequent itemsets. Closed

frequent itemsets are recurrent itemsets that are not redundant. This is important as the

ability to only mine closed frequent itemsets would greatly reduce the number of

calculations in association rules. A frequent itemset Z would be closed if there are no

itemsets of X where every transaction of Z is also contained in X, and X include Y. An

example from the frequent itemset with the two transactions (A, B, C, D) and (A, B, C, D,

E, F) and a fifty percent support model, the frequent itemsets (A, B) and (A, B, C, D) will

be used. Itemset (A, B) would not be a closed frequent itemset where (A, B, C, D) would

be closed frequent itemset. Frequent itemset (A, B) subsumes in closed frequent itemset

(A, B, C, D), frequent itemset (A, B) would not be considered a closed frequent itemset.

There are four important measurements that determine how strong the correlation is for

every if-then frequent itemset. The first being confidence, Turban et al., (2010, p168)

describes confidence as “In association rules, the conditional probability of finding the

RHS of the rule present in a list of transactions where the LHS of the rule exists”. The

formula for confidence is the percentage of the antecedent transactions that have the

consequent item set. The confidence formula does not take the frequency of the item into