APRIORI ALGORITHM IN MACHINE LEARNING/PYTHON/ARTIFICIAL INTELLIGENCE

 Apriori Algorithm

• Introduction and Objective
• Components of Apriori Algorithm
• Steps of the Apriori Algorithm
• Advantages of the Apriori Algorithm
• Efficient for Large Datasets
• Identifies Frequent itemset
• Simple and Understandable
• Disadvantages of the Apriori Algorithm
• Computational Complexity
• Generation on Numerous candidate itemset
• Apriori Property Dependency
• Sensitive to Support Threshold 
• Inefficient Handling of Large Dataset.

The Apriori algorithm stands out in association rule mining by identifying relationships between objects. Introduced by R. Agrawal and R. Srikant in 1994, it aims to discover frequent item sets within datasets. Named "Apriori" due to its utilization of prior knowledge about repeating items, this algorithm employs repeated or specific level approach to find k+1 itemsets based on k-frequent itemsets.

Its primary goal is to establish associations among different objects. Often referred to as frequent pattern mining, an illustrative example occurs in supermarkets where common items like butter, bread, and milk are placed together. This strategic arrangement is based on the likelihood that if a customer buys bread, they might also purchase milk and butter, enhancing both convenience for customers and the supermarket's sales performance.

Operating on large transactional databases like supermarket purchase records, the Apriori algorithm association rule mining efficiently generates frequent item sets by employing the Apriori property, which reduces the search space. It aids customers in their purchases and enhances sales performance wherever it's applied.

By the a priori property, every nonempty subset must also be frequent. The anti-monotonicity of the support measure, which asserts that all supersets of rare subsets must likewise be uncommon, is crucial to this tactic. The apriori algorithm in machine learning and apriori algorithm data science are the main fields of machine learning.

Real-World Example for Apriori Algorithm

Let’s look at an apriori algorithm example, Emily a grocery store owner faced the challenge of optimizing her inventory and boosting sales. She wanted to know which of the many things she had on her shelf her clients most frequently purchased together.

To overcome this challenge, she uses the Apriori algorithm, a powerful tool for association rule mining. Emily employed the algorithm to analyze her transaction data, uncovering patterns of co-occurrence among different products.

To her delight, Emily discovered that customers who bought milk were also likely to buy bread and eggs. Similarly, those who buy pasta often buy pasta sauce too. After knowing these insights, Emily rearranged her store layout, placing complementary items closer together to encourage additional purchases.

Emily also uses the knowledge she gained from the Apriori algorithm association rules to design targeted promotions. She offered discounts on items frequently bought together, like chips and soda or cookies and milk, enticing customers to purchase more items during their visit.

Components of the Apriori algorithm

There are three components in the apriori algorithm.

1. Support
2. Confidence
3. Lift

Support - it is the innate degree of a product's interest. The frequency with which a specific group of items appears in a dataset is referred to as "support". It displays the overall dataset frequency of a group of items.

Mathematically, the support of an itemset A is calculated as:

Support(A)=(Transactions containing A)/(Total number of transactions)

For example, We can divide the total number of transactions by the number of transactions where both milk and bread were purchased to find the support for a set of items in purchase data. {milk, bread} is our set of items in this instance. within the database.

An essential statistic in the Apriori method, support aids in the identification of frequent item groups. Apriori concentrates on itemsets meeting a certain minimal support criterion to reduce the search space. The number of combinations to be investigated is reduced and the computational efficiency in identifying frequent itemsets and association rules is improved when itemsets that do not match this threshold are deemed infrequent and are removed from further investigation.

confidence – it is referred to as the possibility of anything bought together with other things or things or we can say that confidence is a measure used to evaluate the strength of association between items in association rules. It represents the conditional probability that a rule is true given that its antecedent (the items on the left-hand side) is present.

Mathematically, the confidence of a rule {A} -> {B}  is calculated as:

Confidence (A →B)=  Support(A∪B)/(Support (A))

In the above equation Support(A∪B) represents the frequency of occurrence of both items A and B together in the dataset, on the other hand, Support(A) shows the frequency of item A appearing alone.

High confidence shows a strong relationship between items A and B, it means that if someone buys item A then, there’s a high likelihood that they also buy item B. However, it’s necessary to set a threshold for confidence, as high confidence doesn’t necessarily guarantee the usefulness or significance of a rule. Adjusting the confidence threshold helps in filtering out less meaningful rules and focusing on those with stronger associations.

Lift–lift is a measure used to assess the strength of association between two items in an association rule beyond what would be expected based on the individual item frequencies.

The lift of a rule {A} → {B} is calculated as

Lift(A→B)=  Support(A∪B)/(Support(A)×Support(B) )

Left measures how much more often items A and B occur together in transactions compared to what would be expected if their occurrences were statistically independent.

Interpretation of lift values:

Lift = 1: indicates independence. It means that the occurrence of A does not affect the occurrence of B, and vice versa.

Lift > 1: it means that there is a positive correlation between items A and B, it means that if someone takes item A then there is a high chance that they also take item B and vice versa. 

Lift < 1: suggests an avoidance or negative connection between A and B by showing that the presence of A adversely affects the presence of B (and vice versa).

High lift values generally suggest a strong association between the items in the rule. In the context of association rule mining, lift is used alongside support and confidence to evaluate and select meaningful rules, for analysis and decision-making.

Steps of the Apriori Algorithm

1. Initialization
1. Identify all unique items present in the dataset.
2. Determine the minimal level of support (frequency) required for an item to be considered frequent.
2. Generating candidate itemsets
1. Create candidate itemsets of length 1 (single items) containing all unique items from the dataset.
2. Filter these candidates based on the minimum support threshold to obtain frequent items of length 1.
3. Generating longer itemsets
1. Using the two most common itemsets of length 1, create candidate itemsets of length 2 (item pairs).
2. Prune item pairs that contain subsets that are not frequent.
3. Again, filter these candidates based on the minimum support threshold to obtain frequent itemsets of length 2.
4. Iterative process for longer itemsets
1. Repeat the process of generating candidate itemsets and filtering them to obtain frequent itemsets of higher lengths (length>2).
2. Each iteration involves generating candidate itemsets, pruning based on the Apriori property (eliminating subsets that are not frequent), and filtering based on the support threshold.
5. Association rule generation
1. From the frequent itemsets obtained, generate association rules.
2. Create rules that have both high confidence and support, reflecting strong associations between items.
3. Association rules are in the form of “if X then Y”, where X and Y are itemsets.
6. Evaluation and Pruning
1. Evaluate generated rules based on predefined metrics like support, confidence, and lift.
2. Prune rules that do not meet the minimum threshold criteria to derive meaningful and actionable rules.
7. Repeat or Terminate
1. The algorithm terminates when no new frequent itemsets can be generated or when the desired itemset length is reached.
2. Otherwise, iterate through the process until no more frequent itemsets can be found.

Let’s look at these steps with an example and in detail.

Let us have the following dataset shown in the below image and we need to find the frequent itemsets and association rules generated for them.

From the above image, we can see that the minimum number of supports is two, and the least confidence is 60%.

Step-1: (I) ie. K=1 - In this step, we create a table with the support number for each product. is in the table/dataset above. It is called C1 (candidate set).

TID	Items_count
L1	6
L2	7
L3	6
L4	2
L5	2

(II) now we compare the support count of candidate set items with their least support count (here minimum support is 2), if we get any candidate set element support_count less than minimum support then we have to remove those items. After the process of getting items L1.

TID	Items_count
L1	6
L2	7
L3	6
L4	2
L5	2

Step – 2: here K = 2

• At this point we need to generate another set of candidates using C2 L1. This is called a joi tap. The condition to join L_(k-1) and L_(k-1) (L subscript (k-1)) is that there are (K-2) elements in common between them.
• Now we have to check all the subsets of the set of common elements, or not. If the target set is not common, we remove it.
• Then we need to find support for those targets by searching the dataset.

TID	Items_count
L1, L2	4
L1, L3	4
L1, L4	1
L1, L5	2
L2, L3	4
L2, L4	2
L2, L5	2
L3, L4	0
L3, L5	1
L4, L5	0

(II) Now that we have compared the candidates (C2) items, we delete the candidates whose support_number is less than min_support. This procedure yields the elementary set L2.

TID	Items_count
L1, L2	4
L1, L3	4
L1, L5	2
L2, L3	4
L2, L4	2
L2, L5	2

Step – 3: 

• Here we generate the candidate set C3 using L2 (merging). Here, the condition to combine L_(k-1) and L_(k-1) is that they must have (K-2) elements in common. Therefore, the first element of L2 must match.
• So, the set of elements created by merging L2 is {l1, l2, l3} {l1, l2, l5} {l1, l3, l5} {l2, l3, l4 } { l2, l4 , l5} {l2, l3, l5}.
• Now we check if all subsets of these elements are common or not, if they are not common then remove these elements. (Using the table above), we see that the subsets {l1, l2, l3} are {l1, l2,}, {l2, l3}, {l1, l2}, which are common. {l2, l3, l4} is a subset of { l3 , l4} is not frequent, so remove it. We check all the items in the same way.)
• Now we need to find the support number for the rest of these items by searching the dataset.

TID	Itmes_count
L1, L2, L3	2
L1, L2, L5	2

(II) Since min_support = 2 is also present here, we may compare it to the candidate support count (C3). We remove an item from the candidate collection if its support count is less than min_support. Thus, the set of elements L3 is what we have.

TID	Items_count
L1, L2, L3	2
L1, L2, L5	2

Step – 4

• The next action is to generate candidate set C4 using L3. Combining L_(k-1) and L_(k-1) (K=4) requires that the components have (k-2) in common. Thus, the first two items in L3 are anticipated to overlap.
• It is now necessary to confirm whether or not each subset of the tuple is frequent. Assuming the following: {l1, l2, l3, l5} makes up the tuple L3. Since {l1, l3, l5} is an uncommon member in its subset, we can conclude that C4 does not have an initial set.
• We must stop here because no more common initial set can be found.

Advantages of Apriori Algorithm

• Efficient for large datasets: it efficiently handles large datasets by reducing the search space for frequent item sets using candidate generation and pruning techniques.
• Identifies frequent itemset: it accurately identifies frequent itemsets based on user-defined support thresholds, helping uncover commonly occurring item combinations in the data.
• Simple and understandable: the algorithm’s concept and implementation are relatedly straightforward, making it scalable to distributed computing environments, which is useful for big data scenarios.
• Scalable and Parallelizable: Apriori can be parallelized, and various optimizations can be applied, making it scalable to distributed computing environments, which is useful for big data scenarios.
• The basis for rule generation: it serves as a foundation for generating association rules that reveal interesting and actionable patterns in the data.
• Flexible Thresholds: Users can set different support thresholds to discover itemsets of varying frequencies, allowing for flexibility in the exploration of different patterns within the dataset.
• Applications in various fields: the algorithm finds applications in various fields, such as market basket analysis, recommendation systems, bioinformatics, etc., and provides an overview of the relationships between products or events.
• Association Rule Generation: it generates association rules that express correlations between items, assisting in decision-making, targeted marketing, and business strategy formulation.
• There are various apriori algorithm applications in the real world and also apriori algorithm big data is used. 

Disadvantages of Apriori Algorithm

• Computational Complexity: For datasets with a large number of transactions or items, the apriori algorithm can become computationally expensive due to its need to generate and test a vast number of candidate itemsets.
• Storage and Memory Requirements: Maintaining a large number of candidate itemsets and support counts can require significant memory storage, particularly for datasets with numerous unique items.
• Generation of Numerous Candidate items: the algorithm may generate a considerable number of candidate itemsets, leading to a large search space and increased processing time, especially in cases where minimum support thresholds are low.
• Apriori Property Dependency: the Apriori algorithm relies on the Apriori property (i.e., if an item is infrequent, its supersets will also be infrequent), resulting in multiple scans of the dataset to generate candidate items, which might be inefficient.
• Sensitive to Support Threshold: Performance may vary significantly based on the chosen minimum support threshold. Setting a lower threshold might lead to the generation of numerous frequent item sets, while a higher threshold might result in missing some relevant patterns.
• Inefficient Handling of Large Dataset: For datasets with a high number of transactions but low-density itemsets, the algorithm might not perform optimally due to the large number of potentially infrequent itemsets.
• Static Threshold Settings: the need for predefined support thresholds requires prior knowledge or trial-and-error to set appropriate values, which can impact the quality and relevance of discovered itemsets.
• Lack of Handling Continuous Variables: Apriori primarily works with categorical or binary data and may require pre-processing for continuous variables.

Summary

The Apriori algorithm in data mining is a classic association rule mining method used to find common entities in datasets. Iteratively, it identifies recurring target sets, eliminates candidates that fall short of minimal support requirements, and keeps going. It effectively discovers relationships between objects or events, resulting in significant associative rules. Despite the challenges of scaling large datasets and the reliance on predefined support thresholds, Aprior is a core technique for discovering interesting patterns and relationships in data.

Python Code