Association Rule Mining

Overview

The package smile.association provides efficient mining of frequent item sets via the FP-Growth algorithm and association rules with support, confidence, lift, and leverage metrics.

Association rule mining discovers meaningful co-occurrence patterns in large transaction databases. Let I = {i1, i2,…, in} be a set of binary attributes called items, and D = {t1, t2,…, tm} a set of transactions. An association rule is an implication X ⇒ Y where X, Y ⊆ I and X ∩ Y = ∅. X is the antecedent (LHS) and Y the consequent (RHS).

For example, the rule {onions, potatoes} ⇒ {burger} in supermarket data suggests customers buying onions and potatoes together are also likely to buy burger — useful for product placement and promotion strategy.

Rules are usually required to satisfy a user-specified minimum support and minimum confidence. Generation is split into two steps:

ClassRole
FPTreeCompact transaction index (prefix tree + header table)
FPGrowthFrequent item set mining via FP-Growth
ItemSetFrequent item set with raw support count
ARMAssociation rule mining from the T-tree
AssociationRuleRule with antecedent, consequent, and metrics

Typical workflow:

import smile.association.*;
import java.util.stream.Stream;

// transactions  →  FPTree.of(minSupport, ...)
//               →  FPGrowth.apply(tree)        // Stream<ItemSet>
//               →  ARM.apply(confidence, tree) // Stream<AssociationRule>

FPTree tree = FPTree.of(0.3, transactions);
Stream<ItemSet> sets = FPGrowth.apply(tree);
Stream<AssociationRule> rules = ARM.apply(0.5, tree);

Core Concepts

Transaction
A set of item IDs (one basket / purchase / document).
Item set
A subset of items appearing together in transactions.
Support supp(X)
Proportion of transactions containing X. Raw count in ItemSet; fraction in AssociationRule.
Rule X ⇒ Y
X (antecedent) and Y (consequent) are disjoint item sets.
Confidence conf(X ⇒ Y)
supp(X ∪ Y) / supp(X) — estimated P(Y | X).
Lift lift(X ⇒ Y)
supp(X ∪ Y) / (supp(X) · supp(Y)) — ratio versus statistical independence. > 1 positive correlation; = 1 independent; < 1 negative.
Leverage lev(X ⇒ Y)
supp(X ∪ Y) − supp(X) · supp(Y) — absolute deviation from independence.

Finding all frequent item sets is hard because the search space is the power set of I (size 2n − 1). Efficient search relies on the downward-closure (anti-monotonicity) property of support: every subset of a frequent item set is frequent, and all supersets of an infrequent item set are infrequent.

An item set is maximal frequent if none of its immediate supersets is frequent. Maximal sets omit the support of subsets, which matters for rule mining. An item set is closed frequent if none of its immediate supersets has the same support — preferred when the goal is association rules.

Well-known algorithms include Apriori (breadth-first candidate generation), Eclat (depth-first set intersection), and FP-Growth. SMILE uses FP-Growth: an extended prefix tree (FP-tree) stores the database in compressed form, then a divide-and-conquer pattern-growth method avoids Apriori’s costly candidate generation and testing.

Data Format

Transactions are int[] arrays of non-negative item IDs. Prefer compact IDs in [0, n) where n is the number of distinct items.

int[][] transactions = {
    {1, 3},
    {2},
    {4},
    {2, 3, 4},
    {2, 3},
    {2, 3},
    {1, 2, 3, 4},
    {1, 3},
    {1, 2, 3},
    {1, 2, 3}
};

Rules for encoding:

Build an FP-Tree

Class smile.association.FPTree is a compact transaction index: a prefix tree plus a header table used by FP-Growth and ARM.

In-Memory Construction

Use absolute frequency counts or a relative fraction of the database. The two forms produce identical trees when the percentage rounds to the same integer count.

                import smile.association.FPTree;

                int[][] transactions = {
    {1, 3},
    {2},
    {4},
    {2, 3, 4},
    {2, 3},
    {2, 3},
    {1, 2, 3, 4},
    {1, 3},
    {1, 2, 3},
    {1, 2, 3}
};

                // Absolute minimum support (frequency count)
                FPTree tree = FPTree.of(3, transactions);   // minSupport = 3

                // Relative minimum support (fraction of transactions)
                FPTree tree2 = FPTree.of(0.3, transactions); // 30% of 10 = 3

                System.out.println(tree.size());       // number of transactions
                System.out.println(tree.minSupport()); // effective integer threshold

10
3

Streaming Construction

For large datasets that cannot fit in memory, pass a Supplier<Stream<int[]>>. The supplier is called twice — once for frequency counting and once for tree construction — so it must reopen the source on each call.

import smile.association.FPTree;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Arrays;
import java.util.function.Supplier;
import java.util.stream.Stream;

Supplier<Stream<int[]>> supplier = () -> {
    try {
        return Files.lines(Path.of("transactions.dat"))
                .map(line -> Arrays.stream(line.split("\\s+"))
                        .mapToInt(Integer::parseInt)
                        .toArray());
    } catch (Exception ex) {
        throw new RuntimeException(ex);
    }
};

FPTree tree = FPTree.of(1500, supplier);   // absolute support
FPTree tree2 = FPTree.of(0.003, supplier); // relative (0.3%)

Input Validation

FPTree.of enforces these preconditions, throwing IllegalArgumentException on violation:

VariantCondition checked
of(int, …)minSupport >= 1
of(double, …)minSupport in (0, 1]
Bothstream must not be empty
Java 
FPTree.of(0, transactions);    // throws — minSupport must be >= 1
FPTree.of(0.0, transactions);  // throws — percentage must be > 0
FPTree.of(1.1, transactions);  // throws — percentage must be <= 1

Empty-tree handling: when minSupport is larger than the total transaction count, no items are frequent. FPGrowth.apply and ARM.apply both return empty streams without error — this is the correct and tested behavior.

Mine Frequent Item Sets (FP-Growth)

Class smile.association.FPGrowth returns a lazy sequential Stream<ItemSet>. ItemSet is an immutable record:

Java 
record ItemSet(int[] items, int support) { ... }
FieldTypeMeaning
items()int[]Item IDs in frequency-descending order
support()intRaw transaction count

ItemSet.equals / hashCode include both items and support. toString produces e.g. ItemSet([3, 2], support=6).

                import smile.association.*;
                import java.util.Arrays;

                int[][] transactions = {
    {1, 3},
    {2},
    {4},
    {2, 3, 4},
    {2, 3},
    {2, 3},
    {1, 2, 3, 4},
    {1, 3},
    {1, 2, 3},
    {1, 2, 3}
};

                FPTree tree = FPTree.of(3, transactions);
                FPGrowth.apply(tree).forEach(set ->
                    System.out.printf("%s  (support=%d)%n",
                            Arrays.toString(set.items()), set.support())
                );

[4]  (support=3)
[1]  (support=5)
[2, 1]  (support=3)
[3, 2, 1]  (support=3)
[3, 1]  (support=5)
[2]  (support=7)
[3, 2]  (support=6)
[3]  (support=8)

Mine Association Rules (ARM)

Class smile.association.ARM generates rules from the FP-tree’s total-support tree. AssociationRule is an immutable record holding antecedent, consequent, and four metrics.

Java 
record AssociationRule(int[] antecedent, int[] consequent,
                       double support, double confidence,
                       double lift, double leverage) { ... }

Confidence Threshold

                import smile.association.*;

                int[][] transactions = {
    {1, 3},
    {2},
    {4},
    {2, 3, 4},
    {2, 3},
    {2, 3},
    {1, 2, 3, 4},
    {1, 3},
    {1, 2, 3},
    {1, 2, 3}
};

                FPTree tree = FPTree.of(3, transactions);

                // All rules with confidence >= 0.5
                ARM.apply(0.5, tree).forEach(System.out::println);

                // Deterministic rules only
                ARM.apply(1.0, tree);

                // All generated rules
                ARM.apply(0.0, tree);

                // Filter for positive, meaningful correlation
                ARM.apply(0.5, tree)
                   .filter(r -> r.lift() > 1.1 && r.leverage() > 0.01)
                   .forEach(System.out::println);

AssociationRule([3] => [2], support=60.0%, confidence=75.0%, lift=1.07, leverage=0.040)
…

Input Validation

ARM.apply validates that confidence is in [0, 1]:

Java 
ARM.apply(-0.1, tree);  // throws IllegalArgumentException
ARM.apply(1.1,  tree);  // throws IllegalArgumentException

Interpret Rule Metrics

Given rule X ⇒ Y over a database of N transactions:

MetricFormulaInterpretation
supportcount(X ∪ Y) / NFraction of transactions containing both X and Y
confidencecount(X ∪ Y) / count(X)Estimated P(Y | X)
liftsupport / (supp(X) · supp(Y))> 1 positive; = 1 independent; < 1 negative
leveragesupport − supp(X) · supp(Y)Absolute gain over independence

Example — rule {3} ⇒ {2} from the 10-transaction dataset:

QuantityValue
count({3})8 → supp({3}) = 0.8
count({2})7 → supp({2}) = 0.7
count({3,2})6 → support = 0.6
confidence6/8 = 0.75
lift0.6 / (0.8 × 0.7) ≈ 1.071
leverage0.6 − 0.8 × 0.7 = 0.04

Note on equals/hashCode: two AssociationRule objects are equal if they have the same antecedent, consequent, support, and confidence. lift and leverage are derived metrics and are intentionally excluded from equality comparisons, so floating-point drift in those fields does not break equality.

End-to-End Examples

In-Memory Transactions

                import smile.association.*;
                import java.util.Arrays;

                int[][] transactions = {
    {1, 3},
    {2},
    {4},
    {2, 3, 4},
    {2, 3},
    {2, 3},
    {1, 2, 3, 4},
    {1, 3},
    {1, 2, 3},
    {1, 2, 3}
};

                FPTree tree = FPTree.of(0.3, transactions);
                System.out.println("Transactions: " + tree.size());
                System.out.println("Min support:  " + tree.minSupport());

                System.out.println("\nFrequent item sets:");
                FPGrowth.apply(tree).forEach(set ->
                    System.out.printf("  %s  support=%d%n",
                        Arrays.toString(set.items()), set.support())
                );

                System.out.println("\nAssociation rules (conf >= 0.5):");
                ARM.apply(0.5, tree).forEach(rule ->
                    System.out.printf(
                        "  %s => %s  supp=%.2f conf=%.2f lift=%.3f lev=%.3f%n",
                        Arrays.toString(rule.antecedent()),
                        Arrays.toString(rule.consequent()),
                        rule.support(), rule.confidence(),
                        rule.lift(), rule.leverage())
                );

Transactions: 10
Min support:  3

Frequent item sets:
  [4]     support=3
  [1]     support=5
  [1, 3]  support=5
  …
  [3, 2]  support=6
  [3]     support=8

Association rules (conf >= 0.5):
  [3] => [2]     supp=0.60 conf=0.75 lift=1.071 lev=0.040
  [3] => [1]     supp=0.50 conf=0.63 lift=1.250 lev=0.100
  …

Supplier-Based Large File Mining

Use the Supplier<Stream<int[]>> API when the dataset does not fit in memory. The supplier is called twice internally.

import smile.association.*;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Arrays;
import java.util.function.Supplier;
import java.util.stream.Stream;

Supplier<Stream<int[]>> data = () -> {
    try {
        return Files.lines(Path.of("transactions.dat"))
                .map(line -> Arrays.stream(line.split("\\s+"))
                        .mapToInt(Integer::parseInt)
                        .toArray());
    } catch (Exception ex) {
        throw new RuntimeException(ex);
    }
};

FPTree tree = FPTree.of(0.003, data);  // 0.3% of transactions

long nSets  = FPGrowth.apply(tree).count();
long nRules = ARM.apply(0.5, tree).count();
System.out.printf("Frequent sets: %d, Rules: %d%n", nSets, nRules);

5634 (1000)
3805 (1001)
3376 (1001)
…
Frequent sets: …, Rules: …

Filter by Lift

Mining can produce thousands of rules; narrow them with stream operations and sort by lift:

                import smile.association.*;
                import java.util.Comparator;

                int[][] transactions = {
    {1, 3},
    {2},
    {4},
    {2, 3, 4},
    {2, 3},
    {2, 3},
    {1, 2, 3, 4},
    {1, 3},
    {1, 2, 3},
    {1, 2, 3}
};

                FPTree tree = FPTree.of(3, transactions);

                ARM.apply(0.5, tree)
                   .filter(r -> r.lift() > 1.1)
                   .filter(r -> r.leverage() > 0.01)
                   .sorted(Comparator.comparingDouble(AssociationRule::lift).reversed())
                   .limit(20)
                   .forEach(System.out::println);

Validation and Edge Cases

Empty tree (minSupport too high)

If minSupport exceeds the total number of transactions, no item is frequent. Both FPGrowth.apply and ARM.apply return empty streams gracefully:

Java 
FPTree tree = FPTree.of(11, transactions);  // only 10 transactions
assert FPGrowth.apply(tree).count() == 0;
assert ARM.apply(0.5, tree).count() == 0;

Duplicate items in one transaction

Items appearing more than once in a transaction are collapsed before indexing:

Java 
int[][] dup = {{1, 1, 2}, {1, 2}, {1, 1, 1, 2}};
FPTree tree = FPTree.of(2, dup);
// support of {1} = 3, {2} = 3, {1, 2} = 3  (not inflated)

Iterator contract

All three iterators (FPGrowth, TotalSupportTree, ARM) throw NoSuchElementException when next() is called after exhaustion, consistent with the Java Iterator contract.

AssociationRule equality

equals and hashCode use antecedent, consequent, support, and confidence. lift and leverage are derived values and are excluded, so two rules representing the same statistical relationship compare equal regardless of floating-point rounding in the derived metrics.

Performance Tips

TipRationale
Use compact integer IDs in [0, N)Avoids sparse array overhead in the header table
Use the supplier API for large filesThe two-pass design avoids loading all data into memory
Tune minSupport firstSupport pruning dominates runtime; lower = exponentially more work
Stream and filter immediatelyAvoid materializing millions of rules into a List
Percentage support for portability0.01 works for any database size; absolute counts are dataset-specific

API Quick Reference

Java 
// ── FP-Tree construction ──────────────────────────────────────────────────────

FPTree.of(int minSupport,    int[][] itemsets)
FPTree.of(double minSupport, int[][] itemsets)   // minSupport in (0, 1]
FPTree.of(int minSupport,    Supplier<Stream<int[]>> supplier)
FPTree.of(double minSupport, Supplier<Stream<int[]>> supplier)

int tree.size()          // number of transactions
int tree.minSupport()    // effective integer support threshold

// ── Frequent item sets ────────────────────────────────────────────────────────

Stream<ItemSet> FPGrowth.apply(FPTree tree)

// ItemSet (record)
int[]  items()     // item IDs
int    support()   // raw count

// ── Association rules ─────────────────────────────────────────────────────────

Stream<AssociationRule> ARM.apply(double confidence, FPTree tree)
// confidence must be in [0, 1]

// AssociationRule (record)
int[]  antecedent()   // LHS item IDs
int[]  consequent()   // RHS item IDs
double support()      // P(X ∪ Y)  — fraction
double confidence()   // P(Y | X)
double lift()         // correlation vs. independence (>1 = positive)
double leverage()     // absolute gain over independence

// Scala / Kotlin helpers (package smile.association)
// fptree(minSupport, supplier)
// fpgrowth(minSupport, itemsets) / fpgrowth(tree)
// arm(minSupport, confidence, itemsets) / arm(confidence, tree)