Association Rule Mining

A sophisticated intuition of Association Rule Mining and Apriori Algorithm

Association rule mining is a type of data mining that helps find patterns or links between different things in a set of data. It is used a lot in marketing, retail, and e-commerce, among other places, to find interesting connections between different products or services. The goal of association rule mining is to find groups of items in a transactional dataset that are often found together. These groups of items are called "itemsets," and they can be used to make "association rules" that describe how different items are related to each other.

Association rule mining has been done for a long time with the Apriori algorithm. It is a two-step algorithm that starts by finding all of the frequently occurring itemsets in a dataset. These itemsets are then used to make association rules. The algorithm is based on the idea that any subset of a set of frequently occurring items must also be a set of frequently occurring items. This lets the algorithm narrow down the search space and avoid making sets of items that don't come up very often. The Apriori algorithm is a recursive algorithm that starts with 1-itemsets and makes bigger ones until there are no more frequent 1-itemsets.

Concepts Behind the Measures

Support is the number of times an itemset shows up in a dataset. It is worked out by looking at the number of transactions that include the itemset. For example, if a dataset has 1,000 transactions and 200 of them have both items A and B, then the support for the itemset "A, B" is 0.2, or 20%.

Confidence is the chance that an item B will be bought if an item A is bought. It is found by dividing the number of votes for the set of items "A, B" by the number of votes for the set of items "A." For example, if the support for the set "A, B" is 0.2 and the support for the set "A" is 0.5, then the confidence for the rule "A > B" is 0.4, or 40%.

Lift is a measure of how strongly the occurrence of item A is linked to the occurrence of item B, beyond what you would expect by chance. It is worked out by comparing the support for the itemset "A, B" to the support for the itemsets "A" and "B" together. For instance, if the support for the itemset "A, B" is 0.2, the support for the itemset "A" is 0.5, and the support for the itemset "B" is 0.4, then the lift for the rule "A B" is 1.0 (or 100%).

In ARM, a rule is a statement of the form A B, where A and B are both sets of items. When a rule has a high support, a high confidence, and a high lift, it is said to be interesting. People often use the Apriori algorithm to find association rules. It works by first finding groups of items that are used together often, and then using those groups to come up with possible rules.

The steps of the Apriori algorithm are called "iterations." In the first iteration, it looks through the dataset to find all of the individual items that show up at least a certain number of times. These are called "frequent one-item sets." The algorithm uses the frequent itemsets from the previous iteration to make candidate itemsets of length k+1 in the next iteration. The algorithm then goes through the dataset again to find out which candidate itemsets have the most support. If a candidate itemset doesn't get at least the minimum number of votes, it is thrown out. If not, it is added to the list of often-used items.

Once all of the frequent item sets have been found, the algorithm combines them to make candidate rules. Then, it looks at how each candidate rule does in terms of support, confidence, and lift. The final output of the algorithm is the set of interesting rules that meet the minimum thresholds for each of these measures.

Apriori Illustration by Loginom

Association Rule Mining - Chicago Crime

The above transactional data on crime in Chicago is a useful example for using the Apriori algorithm, which may be used to make predictions about the relationship between various sorts of crimes that occur in a given area and time period. With transactional data, association rules may be used to illustrate the connections between objects, in this example, the many criminal categories.

An example/anticipated rule set is described as follows.

Theft => Assualt (confidence = 0.85, support = 0.40)

This rule means that 75% of the transactions where a burglary occurred also included a theft. The support of 0.20 indicates that this association occurs in 20% of all transactions in the dataset.

These association rules can be used to make predictions about future crime patterns and help inform crime prevention strategies. For example, the above association rule suggests that if a burglary occurs, there is a high likelihood that a theft will also occur, which could be useful information for law enforcement to keep in mind when patrolling an area.

Here's a tutorialised description of Association Rule Mining on Crime dataset.

Read the Historic Crime Records data. At this phase the data is cleaned through 3 iterations ( as referenced by the Data Cleaning section ). The current iteration of cleaned data is called `crime_cleaned_v3.csv`.
To perform Association Rule Mining on the a Record Style Dataset, we need to transform the data into Transactional/Basket format.
- To achieve the format of the above mentioned anticipated rule set, the data is transformed/grouped by each day of the year and the Crime Types recorded. This gives each day of the year, i.e., 01/01/2018, and all the Crimes Reported that day.
Post grouping, parameterise this transactionally formatted dataset to `arules` subroutine in the R Language Paradigm.

The following set of visualisations are the resultant of the above process described graphically.

Data Set Formatting

Before Transactional Formmatting

After Transactional Formmating

The following dropboxes hold the top15 rules generated by the variations in parameters like

→ conf, minlen, maxlen.

rules <- apriori(transactions, parameter = list(supp=0.2, conf=0.6, maxlen=3, minlen=3, target= "rules"))

Top15 rules on Lift

lhs rhs support confidence coverage lift count

[1] {OFFENSE INVOLVING CHILDREN,

PROSTITUTION} => {CRIM SEXUAL ASSAULT} 0.2011963 0.6813996 0.2952692 1.7236505 370

[2] {NARCOTICS,