Scalable Analytics: Chapter 3

Association Rule Discovery and the Market-Basket Model

• Goal of Supermarket Shelf Management: To identify items that are purchased together by a sufficiently large number of customers to optimize product placement and inventory.

• Methodology: Sales data collected via barcode scanners is processed to find dependencies among various items.

• The Market-Basket Model Components:

  • Items: A large set of distinct products (e.g., milk, coke, bread).

  • Baskets: A large set of transactions, where each basket is a small subset of the total item set.

• Input Example Table:

  • TID 1: {Bread, Coke, Milk}

  • TID 2: {Beer, Bread}

  • TID 3: {Beer, Coke, Diaper, Milk}

  • TID 4: {Beer, Bread, Diaper, Milk}

  • TID 5: {Coke, Diaper, Milk}

• Output Association Rule Examples:

  • $\{Milk\} \rightarrow \{Coke\}$

  • $\{Diaper, Milk\} \rightarrow \{Beer\}$

Broad Applications of Large-Scale Analytics

• Market Baskets: Large chain stores maintain terabytes (TB) of data regarding customer purchasing habits.

• Plagiarism Detection:

  • Items: Sentences.

  • Baskets: Documents containing those specific sentences.

• Medical Research:

  • Items: Prescription drugs and observed side effects.

  • Baskets: Patients.

  • Goal: Identifying side-effect patterns occurring across different patients.

• Abstract Mapping: Frequent itemset mining describes a general many-to-many mapping or association between two distinct categories of data.

Defining Frequent Itemsets and Association Rules

• Frequent Itemsets: The simplest analytical question is identifying sets of items that appear together in baskets frequently.

• Support: The support for itemset $I$ is the specific number of baskets that contain all items in $I$.

• Support Threshold ($s$): A user-defined value. Itemsets that appear in at least $s$ baskets are classified as frequent itemsets.

  • Example: In a data set where {Beer, Bread} appear in TID 2 and TID 4, the support of {Beer, Bread} is $2$.

• Association Rule Format: An "if-then" rule regarding basket contents, represented as $\{i_1, i_2, \dots, i_k\} \rightarrow j$.

• Confidence Calculation: The probability of item $j$ being in a basket given that the set of items $I = \{i_1, \dots, i_k\}$ is present.

  • $\text{conf}(I \rightarrow j) = \frac{\text{support}(I \cup \{j\})}{\text{support}(I)}$

• Interesting Association Rules: Not all high-confidence rules provide useful information. The "Interest" of a rule is the difference between its confidence and the overall probability of item $j$ occurring in any basket regardless of context.

  • $\text{Interest}(I \rightarrow j) = \text{conf}(I \rightarrow j) - P(j)$

• Calculated Example:

  • Baskets: 8 total ($B_1$ to $B_8$). Coke ($c$) appears in 5 out of 8 baskets ($P(j) = \frac{5}{8}$).

  • Rule: $\{m, b\} \rightarrow c$.

  • If support for $\{m, b\}$ is $4$ and support for $\{m, b, c\}$ is $2$, then $\text{confidence} = \frac{2}{4} = 0.5$.

  • $\text{Interest} = |0.5 - \frac{5}{8}| = \frac{1}{8}$.

Computational Implementation of Association Rule Mining

• Primary Problem: Finding all rules with support $\ge s$ and confidence $\ge c$. The most computationally intensive part is finding the frequent itemsets themselves.

• Steps for Mining:

  1. Step 1: Find all frequent itemsets $I$.

  2. Step 2: Rule generation. For every subset $A$ of a frequent itemset $I$, generate a rule $A \rightarrow I \setminus A$.

• Rule Generation Observations:

  • If $I$ is frequent, its subset $A$ is also frequent.

  • If a rule $A, B, C \rightarrow D$ is below the confidence threshold, any rule with a smaller subset as the antecedent (e.g., $A, B \rightarrow C, D$) will also be below confidence.

The Computational Model and Memory Bottlenecks

• Data Storage: Data is typically stored in flat files on a disk, organized basket-by-basket. Baskets are generally small, but the total number of items and baskets is massive.

• True Cost Metric: The cost of mining disk-resident data is measured by the number of disk I/O operations (passes over the data), where a pass involves reading all baskets in order.

• Main-Memory Constraint: Main memory is the critical resource. As baskets are read, counts must be stored in memory. Swapping counts in and out of disk is extremely inefficient and should be avoided.

Techniques for Counting Pairs in Memory

• The Problem of Pairs: Finding frequent pairs $\left(\{i_1, i_2\}\right)$ is often the hardest stage of the process.

• Naive Approach: Count all pairs once in main memory. This fails if the number of items $n$ results in $n^2$ pairs that exceed memory capacity.

• Method 1: Triangular Matrix:

  • Used only if items are ordered i < j.

  • Counts are kept in lexicographical order: $\text{\{1, 2\}, \{1, 3\}, \dots, \{1, n\}, \{2, 3\}, \dots}$

  • Formula for the position of pair $\text{\{i, j\}}$: $(i - 1) \times (n - \frac{i}{2}) + j - 1$.

  • Requires $4$ bytes per pair. Total bytes required is approximately $2n^2$.

• Method 2: Triples/Dictionary:

  • Stores data as $[i, j, c]$ where $c$ is the count.

  • Requires $12$ bytes per occurring pair. This is more efficient only if the data is sparse (few pairs actually appear).

The A-Priori Algorithm

• Key Principle: Monotonicity: If an itemset $I$ appears at least $s$ times, every subset $J$ of $I$ must also appear at least $s$ times.

• Contrapositive: If an item $i$ does not appear at least $s$ times, then no pair or larger set involving $i$ can be frequent.

• Two-Pass Approach:

  • Pass 1: Read baskets and count occurrences of individual items. Identify "frequent items" that meet the threshold $s$.

  • Pass 2: Read baskets again, but only count pairs where both items were identified as frequent in Pass 1. This significantly reduces the memory needed to store pair counts.

• Frequent k-tuples Procedure:

  • $C_k$ = Candidate k-tuples (potential frequent sets based on information from the $k-1$ pass).

  • $L_k$ = Truly frequent k-tuples (sets verified as satisfying support $s$ after a pass).

  • For market-basket data with a $1\%$ support threshold, the $k=2$ pass usually requires the most memory.

The PCY (Park-Chen-Yu) Algorithm

• Observation: During Pass 1 of the A-Priori algorithm, substantial memory remains idle while only individual items are being counted.

• PCY Pass 1:

  • Maintains item counts.

  • Simultaneously maintains a hash table using remaining memory. Every pair of items in a basket is hashed to a bucket, and the count for that bucket is incremented.

• Refining Buckets:

  • A bucket is "frequent" if its total count is $\ge s$.

  • If a pair is frequent, the bucket it hashes to must be frequent.

  • If a bucket is not frequent, none of the pairs inside it can be frequent.

• PCY Pass 2:

  • Replace the hash table buckets with a bit-vector (bitmap). A bit is $1$ if the bucket was frequent, and $0$ otherwise.

  • Only count a pair $\text{\{i, j\}}$ if:

    1. Both $i$ and $j$ are frequent items (A-Priori condition).

    2. The pair $\text{\{i, j\}}$ hashes to a frequent bucket (Bit-vector value is $1$).

Frequent Itemsets in Fewer Than Two Passes

• Standard algorithms take $k$ passes to find itemsets of size $k$. Certain methods aim for two or fewer passes for all sizes, though they may miss some results.

• Random Sampling:

  • Takes a random sample of baskets and runs the algorithm in main memory.

  • Support threshold is reduced proportionally to the sample size.

  • Verification can be done in a second pass to avoid false positives, though false negatives (missing items frequent in the whole but not the sample) may remain.

• SON (Savasere, Omiecinski, and Navathe) Algorithm:

  • Repeatedly reads small subsets of baskets into memory and identifies frequent itemsets within each subset.

  • An itemset is a "candidate" for the full data set if it is frequent in at least one subset.

  • Monotonicity Idea: An itemset cannot be frequent in the whole unless it is frequent in at least one subset.

  • Distributed Version: Can be implemented via MapReduce; each node computes local frequent itemsets and then candidates are distributed and counted across all nodes.

• Toivonen’s Algorithm:

  • Pass 1: Run a random sample with a slightly lowered threshold. Find frequent itemsets in the sample.

  • Negative Border Concept: Add the negative border to the candidate list. An itemset is in the negative border if it is not frequent in the sample, but all of its immediate subsets are frequent in the sample.

  • Pass 2: Count all candidates and the negative border in the full data.

  • Theorem: If any itemset $S$ is frequent in the full data but missed by the sample, at least one itemset in the negative border must be frequent in the full data. If no itemset in the negative border is frequent in the full data, the algorithm is guaranteed to have found all frequent itemsets.