Market Basket Analysis and Apriori Algorithm

(a) Concept Behind Market Basket Analysis

Market Basket Analysis is a data mining technique used to discover associations and relationships between items purchased together by customers.

Key Concepts:

1. Purpose:

• Identifies which products are frequently bought together
• Discovers customer purchasing patterns and behavior
• Helps in product placement, cross-selling, and promotional strategies

2. Core Idea:

• Analyzes transaction data to find item combinations
• Determines how often certain items co-occur in transactions
• Establishes rules like "if customer buys X, they likely buy Y"

3. Business Applications:

• Supermarket shelf arrangement (placing related items near each other)
• Recommendation systems (suggesting complementary products)
• Bundle pricing and promotional campaigns
• Inventory management and stock optimization

4. Association Rules:

• Expressed as: If {Item A} then {Item B}
• Measured using metrics like support, confidence, and lift
• Helps predict customer behavior and increase sales

---

(b) Generating Frequent Itemsets Using Apriori Algorithm

Algorithm Overview:

The Apriori Algorithm generates frequent itemsets by iteratively finding itemsets that appear in at least a minimum support threshold of transactions.

Key Principle:

"If an itemset is frequent, then all of its subsets must also be frequent" (Apriori property)

Steps:

Step 1: Set Minimum Support Threshold

• Define minimum support (e.g., 50% or 2 transactions out of 4)
• Only itemsets meeting this threshold are considered frequent

Step 2: Generate 1-Itemsets (L₁)

• Count occurrences of each individual item
• Keep items with support ≥ minimum support
• Example: {A}, {B}, {C}, {D}

Step 3: Generate Candidate k-Itemsets (Cₖ)

• Join frequent (k-1)-itemsets to create candidate k-itemsets
• Apply pruning: remove candidates containing infrequent subsets
• Example: From {A}, {B}, {C} → candidates {A,B}, {A,C}, {B,C}

Step 4: Count Support for Candidates

• Scan database to count occurrences of each candidate itemset
• Calculate support = (frequency of itemset) / (total transactions)

Step 5: Filter by Minimum Support

• Keep only candidates with support ≥ threshold
• These become frequent k-itemsets (Lₖ)

Step 6: Repeat Until No New Itemsets

• Continue with k+1 until no new frequent itemsets are generated

Example:

With minimum support = 50% (2 transactions):

• L₁: {A}(3), {B}(3), {C}(3) - all frequent
• C₂: {A,B}, {A,C}, {B,C}
• L₂: {A,B}(2), {A,C}(2), {B,C}(2) - all frequent
• C₃: {A,B,C}
• L₃: {A,B,C}(1) - NOT frequent (support < 50%)

Result: Frequent itemsets are {A}, {B}, {C}, {A,B}, {A,C}, {B,C}

Advantages:

• Efficient pruning reduces search space
• Guarantees finding all frequent itemsets
• Widely used in practice

Model Answer: Viral Marketing and Densification Power Law

1. Viral Marketing (2 marks)

Definition:

Viral marketing is a marketing strategy that leverages social networks and word-of-mouth communication to promote products, services, or content. It relies on users voluntarily sharing information with their networks, causing exponential growth in message reach and brand awareness with minimal paid advertising.

Key characteristics:

• Self-replicating and spreads organically through networks
• Users become active promoters by sharing content
• Achieves rapid, widespread dissemination at low cost
• Often uses emotionally engaging or novel content

---

2. Densification Power Law (3 marks)

Definition and Description:

The densification power law is an empirical observation about the growth patterns of real-world networks (social networks, web graphs, etc.). It states that the number of edges in a network grows superlinearly with the number of nodes over time.

Mathematical Expression:

$$E(t) \propto N(t)^a$$

where:

• E(t) = number of edges at time t
• N(t) = number of nodes at time t
• a = densification exponent (typically 1 < a < 2)

Key Implications:

1. Superlinear Growth: As networks grow, they become denser (average degree increases)
2. Exponent Range: For most real networks, a ≈ 1.1 to 1.6
3. Network Evolution: Networks don't just add nodes; they add edges at a faster rate, meaning nodes form more connections over time
4. Practical Significance: Explains why social networks become increasingly interconnected as they scale

This law has been observed empirically in online social networks, citation networks, and the World Wide Web.