每日算法 — 使用java实现Apriori：关联规则挖掘与频繁项集发现

可莉爸爸 AI算法

一、背景介绍

1.1 什么是关联规则挖掘

关联规则挖掘（Association Rule Mining）是数据挖掘领域的重要技术，用于发现大量数据集中项集之间有趣的关联关系。最经典的应用是”购物篮分析”——通过分析顾客的购物记录，发现哪些商品经常被一起购买。

经典案例：沃尔玛发现啤酒和尿布经常被一起购买，因为年轻爸爸在买尿布时会顺便买啤酒。

1.2 基本概念

  • 项集（Itemset）：项的集合，如 {牛奶, 面包, 鸡蛋}
  • 支持度（Support）：包含某项集的事务占总事务的比例
  • Support(X) = 包含X的事务数 / 总事务数
  • 置信度（Confidence）：在包含X的事务中，同时包含Y的比例
  • Confidence(X→Y) = Support(X∪Y) / Support(X)
  • 频繁项集：支持度大于等于最小支持度阈值的项集
  • 关联规则：形如 X→Y 的蕴含式，其中X和Y是不相交的项集

1.3 Apriori算法简介

Apriori算法由Rakesh Agrawal和Ramakrishnan Srikant于1994年提出，是最经典的频繁项集挖掘算法。

核心思想（Apriori先验原理）：

如果一个项集是频繁的，那么它的所有子集也都是频繁的。
反过来，如果一个项集是非频繁的，那么它的所有超集也都是非频繁的。

利用这个原理，可以大幅减少需要检查的候选项集数量。

二、核心算法原理

2.1 算法流程

Apriori算法采用逐层搜索的迭代策略：

  1. 第1步：扫描数据库，找出所有频繁1项集（L1）
  2. 第k步：
  3. 连接：用 L(k-1) 自连接生成候选k项集 Ck
  4. 剪枝：利用先验原理，删除那些子集不频繁的候选项
  5. 计数：扫描数据库，计算每个候选项集的支持度
  6. 筛选：保留支持度 ≥ 最小支持度的项集，得到 Lk
  7. 终止：当无法生成新的频繁项集时停止

2.2 连接步骤

两个 (k-1) 项集可以连接生成 k 项集的条件：
– 它们的前 k-2 个项相同
– 第 k-1 个项不同（按字典序比较）

例如：
– {A, B} 和 {A, C} 可以连接生成 {A, B, C}
– {A, B} 和 {C, D} 不能连接（前0项都不同… 实际上k=2时，前k-2=前0项都相同，所以任意两个1项集都能连接）

2.3 剪枝步骤

对于每个候选 k 项集，检查它的所有 (k-1) 项子集是否都在 L(k-1) 中：
– 如果有任何一个子集不在 L(k-1) 中，则该候选项一定不频繁，直接剪枝
– 这利用了Apriori先验原理的逆否命题

2.4 关联规则生成

得到所有频繁项集后，从每个频繁项集中生成关联规则：
1. 对于每个频繁项集 L，生成所有非空真子集
2. 对每个子集 X，计算置信度 Confidence(X → L-X)
3. 如果置信度 ≥ 最小置信度阈值，则输出规则 X → L-X

三、完整Java实现

import java.util.*;

/**
 * Apriori算法完整实现
 * 包含频繁项集发现、关联规则生成、超市购物篮案例
 */
public class Apriori {

    // 事务类：一条购物记录
    static class Transaction {
        int id;
        Set<String> items;

        public Transaction(int id, Set<String> items) {
            this.id = id;
            this.items = items;
        }

        public boolean containsAll(Set<String> itemset) {
            return items.containsAll(itemset);
        }
    }

    // 频繁项集类
    static class FrequentItemset {
        Set<String> items;
        double support;
        int count;

        public FrequentItemset(Set<String> items, int count, int totalTransactions) {
            this.items = items;
            this.count = count;
            this.support = (double) count / totalTransactions;
        }

        @Override
        public String toString() {
            return items + " (支持度: " + String.format("%.2f%%", support * 100) + ", 计数: " + count + ")";
        }
    }

    // 关联规则类
    static class AssociationRule {
        Set<String> antecedent; // 前件 X
        Set<String> consequent; // 后件 Y
        double support;         // 支持度
        double confidence;      // 置信度
        double lift;            // 提升度

        public AssociationRule(Set<String> antecedent, Set<String> consequent,
                               double support, double confidence, double lift) {
            this.antecedent = antecedent;
            this.consequent = consequent;
            this.support = support;
            this.confidence = confidence;
            this.lift = lift;
        }

        @Override
        public String toString() {
            return antecedent + " → " + consequent +
                   " [支持度: " + String.format("%.2f%%", support * 100) +
                   ", 置信度: " + String.format("%.2f%%", confidence * 100) +
                   ", 提升度: " + String.format("%.2f", lift) + "]";
        }
    }

    // 事务列表
    private List<Transaction> transactions;
    // 最小支持度
    private double minSupport;
    // 最小置信度
    private double minConfidence;
    // 各层频繁项集：k -> 频繁k项集列表
    private Map<Integer, List<FrequentItemset>> frequentItemsets;
    // 频繁项集快速查找：项集字符串 -> 支持度
    private Map<String, FrequentItemset> itemsetMap;

    public Apriori(double minSupport, double minConfidence) {
        this.transactions = new ArrayList<>();
        this.minSupport = minSupport;
        this.minConfidence = minConfidence;
        this.frequentItemsets = new HashMap<>();
        this.itemsetMap = new HashMap<>();
    }

    /**
     * 添加事务
     */
    public void addTransaction(int id, Set<String> items) {
        transactions.add(new Transaction(id, items));
    }

    /**
     * 添加事务（字符串数组形式）
     */
    public void addTransaction(int id, String[] items) {
        transactions.add(new Transaction(id, new HashSet<>(Arrays.asList(items))));
    }

    // ==========================================
    // 第一部分：生成频繁1项集
    // ==========================================

    /**
     * 找出所有频繁1项集
     */
    private List<FrequentItemset> findFrequent1Itemsets() {
        // 统计每个单项的出现次数
        Map<String, Integer> itemCount = new HashMap<>();
        for (Transaction txn : transactions) {
            for (String item : txn.items) {
                itemCount.merge(item, 1, Integer::sum);
            }
        }

        List<FrequentItemset> L1 = new ArrayList<>();
        int minCount = (int) Math.ceil(minSupport * transactions.size());

        for (Map.Entry<String, Integer> entry : itemCount.entrySet()) {
            if (entry.getValue() >= minCount) {
                Set<String> itemset = new HashSet<>();
                itemset.add(entry.getKey());
                FrequentItemset fi = new FrequentItemset(itemset, entry.getValue(), transactions.size());
                L1.add(fi);
                itemsetMap.put(itemsetToString(itemset), fi);
            }
        }

        // 按字典序排序，方便后续连接操作
        L1.sort((a, b) -> {
            String itemA = a.items.iterator().next();
            String itemB = b.items.iterator().next();
            return itemA.compareTo(itemB);
        });

        return L1;
    }

    // ==========================================
    // 第二部分：连接 + 剪枝（生成候选项集）
    // ==========================================

    /**
     * 从 L(k-1) 生成候选 k 项集 Ck
     * 包含连接步骤和剪枝步骤
     */
    private List<Set<String>> generateCandidates(List<FrequentItemset> L_prev, int k) {
        List<Set<String>> candidates = new ArrayList<>();
        int n = L_prev.size();

        // 连接步骤：将 L(k-1) 中的项集两两连接
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                Set<String> set1 = L_prev.get(i).items;
                Set<String> set2 = L_prev.get(j).items;

                // 检查前 k-2 个项是否相同（按排序后的列表比较）
                List<String> list1 = new ArrayList<>(set1);
                List<String> list2 = new ArrayList<>(set2);
                Collections.sort(list1);
                Collections.sort(list2);

                boolean canJoin = true;
                for (int m = 0; m < k - 2; m++) {
                    if (!list1.get(m).equals(list2.get(m))) {
                        canJoin = false;
                        break;
                    }
                }

                if (canJoin) {
                    // 合并两个项集
                    Set<String> candidate = new HashSet<>(set1);
                    candidate.addAll(set2);

                    // 剪枝步骤：检查所有 (k-1) 项子集是否都频繁
                    if (hasInfrequentSubset(candidate, L_prev)) {
                        continue; // 有非频繁子集，剪枝
                    }

                    candidates.add(candidate);
                }
            }
        }

        return candidates;
    }

    /**
     * 检查候选项集是否有非频繁的 (k-1) 项子集
     * 利用先验原理进行剪枝
     */
    private boolean hasInfrequentSubset(Set<String> candidate, List<FrequentItemset> L_prev) {
        // 生成所有 (k-1) 项子集
        List<Set<String>> subsets = generateSubsets(candidate, candidate.size() - 1);

        for (Set<String> subset : subsets) {
            String key = itemsetToString(subset);
            if (!itemsetMap.containsKey(key)) {
                return true; // 存在非频繁子集
            }
        }
        return false;
    }

    /**
     * 生成指定大小的所有子集
     */
    private List<Set<String>> generateSubsets(Set<String> set, int size) {
        List<Set<String>> result = new ArrayList<>();
        List<String> list = new ArrayList<>(set);
        generateSubsetsHelper(list, size, 0, new HashSet<>(), result);
        return result;
    }

    private void generateSubsetsHelper(List<String> list, int size, int start,
                                       Set<String> current, List<Set<String>> result) {
        if (current.size() == size) {
            result.add(new HashSet<>(current));
            return;
        }
        for (int i = start; i < list.size(); i++) {
            current.add(list.get(i));
            generateSubsetsHelper(list, size, i + 1, current, result);
            current.remove(list.get(i));
        }
    }

    // ==========================================
    // 第三部分：计算支持度 + 筛选频繁项集
    // ==========================================

    /**
     * 扫描事务数据库，计算候选项集的支持度
     * 并筛选出频繁项集
     */
    private List<FrequentItemset> countAndFilter(List<Set<String>> candidates) {
        Map<String, Integer> countMap = new HashMap<>();
        int minCount = (int) Math.ceil(minSupport * transactions.size());

        // 初始化计数器
        for (Set<String> candidate : candidates) {
            countMap.put(itemsetToString(candidate), 0);
        }

        // 扫描所有事务，计数
        for (Transaction txn : transactions) {
            for (Set<String> candidate : candidates) {
                if (txn.containsAll(candidate)) {
                    String key = itemsetToString(candidate);
                    countMap.put(key, countMap.get(key) + 1);
                }
            }
        }

        // 筛选频繁项集
        List<FrequentItemset> Lk = new ArrayList<>();
        for (Set<String> candidate : candidates) {
            String key = itemsetToString(candidate);
            int count = countMap.get(key);
            if (count >= minCount) {
                FrequentItemset fi = new FrequentItemset(candidate, count, transactions.size());
                Lk.add(fi);
                itemsetMap.put(key, fi);
            }
        }

        return Lk;
    }

    // ==========================================
    // 第四部分：Apriori主算法
    // ==========================================

    /**
     * 执行Apriori算法，找出所有频繁项集
     */
    public void mineFrequentItemsets() {
        itemsetMap.clear();
        frequentItemsets.clear();

        // 第1步：找出频繁1项集
        List<FrequentItemset> L1 = findFrequent1Itemsets();
        frequentItemsets.put(1, L1);
        System.out.println("L1: " + L1.size() + " 个频繁1项集");

        int k = 2;
        while (true) {
            List<FrequentItemset> L_prev = frequentItemsets.get(k - 1);
            if (L_prev == null || L_prev.isEmpty()) {
                break;
            }

            // 生成候选项集
            List<Set<String>> Ck = generateCandidates(L_prev, k);
            if (Ck.isEmpty()) {
                break;
            }
            System.out.println("C" + k + ": " + Ck.size() + " 个候选项集");

            // 计算支持度并筛选
            List<FrequentItemset> Lk = countAndFilter(Ck);
            if (Lk.isEmpty()) {
                System.out.println("L" + k + ": 空，算法结束");
                break;
            }

            frequentItemsets.put(k, Lk);
            System.out.println("L" + k + ": " + Lk.size() + " 个频繁" + k + "项集");
            k++;
        }
    }

    // ==========================================
    // 第五部分：生成关联规则
    // ==========================================

    /**
     * 从频繁项集中生成所有满足最小置信度的关联规则
     */
    public List<AssociationRule> generateAssociationRules() {
        List<AssociationRule> rules = new ArrayList<>();

        // 从2项集开始，因为1项集无法生成规则
        for (int k = 2; k <= frequentItemsets.size(); k++) {
            List<FrequentItemset> Lk = frequentItemsets.get(k);
            if (Lk == null) continue;

            for (FrequentItemset fi : Lk) {
                generateRulesFromItemset(fi, rules);
            }
        }

        // 按置信度降序排序
        rules.sort((a, b) -> Double.compare(b.confidence, a.confidence));

        return rules;
    }

    /**
     * 从一个频繁项集中生成所有可能的关联规则
     */
    private void generateRulesFromItemset(FrequentItemset itemset, List<AssociationRule> rules) {
        Set<String> items = itemset.items;
        int n = items.size();

        // 生成所有非空真子集作为前件
        for (int size = 1; size < n; size++) {
            List<Set<String>> subsets = generateSubsets(items, size);
            for (Set<String> antecedent : subsets) {
                // 后件 = 项集 - 前件
                Set<String> consequent = new HashSet<>(items);
                consequent.removeAll(antecedent);

                // 计算置信度
                FrequentItemset antecedentFI = itemsetMap.get(itemsetToString(antecedent));
                if (antecedentFI == null) continue;

                double confidence = itemset.support / antecedentFI.support;
                if (confidence >= minConfidence) {
                    // 计算提升度
                    FrequentItemset consequentFI = itemsetMap.get(itemsetToString(consequent));
                    double lift = (consequentFI != null) ? confidence / consequentFI.support : 0;

                    rules.add(new AssociationRule(antecedent, consequent,
                            itemset.support, confidence, lift));
                }
            }
        }
    }

    // ==========================================
    // 辅助方法
    // ==========================================

    /**
     * 将项集转换为字符串键（用于HashMap查找）
     */
    private String itemsetToString(Set<String> itemset) {
        List<String> list = new ArrayList<>(itemset);
        Collections.sort(list);
        return String.join(",", list);
    }

    /**
     * 获取所有频繁项集
     */
    public List<FrequentItemset> getAllFrequentItemsets() {
        List<FrequentItemset> all = new ArrayList<>();
        for (List<FrequentItemset> list : frequentItemsets.values()) {
            all.addAll(list);
        }
        return all;
    }

    // ==========================================
    // 主方法：超市购物篮案例演示
    // ==========================================

    public static void main(String[] args) {
        System.out.println("╔══════════════════════════════════════╗");
        System.out.println("║   Apriori 关联规则挖掘演示系统       ║");
        System.out.println("║      （超市购物篮分析案例）          ║");
        System.out.println("╚══════════════════════════════════════╝\n");

        // 设置最小支持度 20%，最小置信度 60%
        Apriori apriori = new Apriori(0.20, 0.60);

        // 添加超市购物记录（10条事务）
        apriori.addTransaction(1, new String[]{"牛奶", "面包", "鸡蛋"});
        apriori.addTransaction(2, new String[]{"牛奶", "面包", "黄油", "鸡蛋"});
        apriori.addTransaction(3, new String[]{"面包", "黄油", "果酱"});
        apriori.addTransaction(4, new String[]{"牛奶", "鸡蛋", "黄油"});
        apriori.addTransaction(5, new String[]{"牛奶", "面包", "鸡蛋", "果酱"});
        apriori.addTransaction(6, new String[]{"面包", "鸡蛋", "黄油"});
        apriori.addTransaction(7, new String[]{"牛奶", "面包", "咖啡"});
        apriori.addTransaction(8, new String[]{"牛奶", "鸡蛋", "咖啡"});
        apriori.addTransaction(9, new String[]{"面包", "黄油", "咖啡"});
        apriori.addTransaction(10, new String[]{"牛奶", "面包", "鸡蛋", "黄油"});

        System.out.println("【事务数据】");
        System.out.println("----------------------------");
        for (Transaction txn : apriori.transactions) {
            System.out.println("T" + txn.id + ": " + txn.items);
        }
        System.out.println("总事务数: " + apriori.transactions.size());
        System.out.println("最小支持度: " + String.format("%.0f%%", apriori.minSupport * 100));
        System.out.println("最小置信度: " + String.format("%.0f%%", apriori.minConfidence * 100));
        System.out.println();

        // 执行Apriori算法
        System.out.println("【频繁项集挖掘过程】");
        System.out.println("----------------------------");
        apriori.mineFrequentItemsets();
        System.out.println();

        // 输出所有频繁项集
        System.out.println("【所有频繁项集】");
        System.out.println("----------------------------");
        List<FrequentItemset> allItemsets = apriori.getAllFrequentItemsets();
        allItemsets.sort((a, b) -> {
            if (a.items.size() != b.items.size()) {
                return a.items.size() - b.items.size();
            }
            return Double.compare(b.support, a.support);
        });
        for (FrequentItemset fi : allItemsets) {
            System.out.println("  " + fi);
        }
        System.out.println();

        // 生成关联规则
        System.out.println("【关联规则（按置信度排序）】");
        System.out.println("----------------------------");
        List<AssociationRule> rules = apriori.generateAssociationRules();
        if (rules.isEmpty()) {
            System.out.println("  未找到满足条件的关联规则");
        } else {
            for (int i = 0; i < rules.size(); i++) {
                System.out.println("  " + (i + 1) + ". " + rules.get(i));
            }
        }
        System.out.println();

        // 规则解读
        System.out.println("【规则解读】");
        System.out.println("----------------------------");
        System.out.println("• 支持度：规则在所有交易中出现的频率");
        System.out.println("• 置信度：购买前件的顾客中，同时购买后件的比例");
        System.out.println("• 提升度：置信度 / 后件的支持度。>1表示正相关，=1表示独立");
        System.out.println();

        // 找出提升度最高的规则
        System.out.println("【最强关联规则（Top 3 by 提升度）】");
        System.out.println("----------------------------");
        rules.sort((a, b) -> Double.compare(b.lift, a.lift));
        for (int i = 0; i < Math.min(3, rules.size()); i++) {
            System.out.println("  " + (i + 1) + ". " + rules.get(i));
        }
    }
}

四、复杂度分析

4.1 时间复杂度

步骤 时间复杂度 说明
生成L1 O(N × w) N为事务数，w为平均事务宽度
生成候选集 O( L(k-1)² × k ) 两两连接 + 子集检查
支持度计数 O( Ck × N × k ) 扫描所有事务，检查每个候选项
规则生成 O( 2^k × k ) 每个频繁k项集生成 2^k – 2 条规则

总体复杂度：O( 2^|I| × N × |I| )，其中|I|是项的总数。
– 最坏情况下（所有项集都频繁），是指数级复杂度
– 实际应用中，最小支持度阈值会大幅限制频繁项集的数量

4.2 空间复杂度

  • 事务存储：O(N × w)
  • 频繁项集存储：O(Σ Lk × k)
  • 候选项集存储：O(Ck × k)

4.3 优化技术

  1. 哈希树：用哈希树加速候选项集的支持度计数
  2. 事务压缩：不包含任何频繁k项集的事务，后续扫描可以跳过
  3. 分区：将数据分区，局部频繁项集可能是全局频繁的
  4. 抽样：在样本上挖掘，减少扫描次数
  5. FP-Growth：不生成候选项集，直接用FP树挖掘（Apriori的改进版）

五、应用拓展

5.1 经典应用场景

领域 应用案例
零售 购物篮分析、商品摆放、捆绑销售
电商 推荐系统、个性化推荐
医疗 疾病与症状关联、药物相互作用
金融 信用卡欺诈检测、股票关联分析
互联网 网页点击流分析、用户行为模式
生物信息 基因表达分析、蛋白质相互作用

5.2 相关算法对比

算法 特点 适用场景
Apriori 简单直观，需多次扫描数据库 小规模数据
FP-Growth 不生成候选项集，2次扫描 中大规模数据
Eclat 垂直数据格式，交集计算 稀疏数据集
GSP 序列模式挖掘 时序数据

5.3 评估指标拓展

除了支持度和置信度，还有更多评估关联规则质量的指标：

  1. 提升度（Lift）：Conf(X→Y) / Supp(Y)

  2. Lift > 1：正相关；Lift = 1：独立；Lift < 1：负相关

  3. 确信度（Conviction）：(1 – Supp(Y)) / (1 – Conf(X→Y))

  4. 衡量规则的意外程度

  5. 杠杆率（Leverage）：Supp(X∪Y) – Supp(X) × Supp(Y)

  6. 衡量X和Y同时出现与独立假设的差异

  7. 全置信度（All-Confidence）：Supp(X∪Y) / max(Supp(X), Supp(Y))

  8. 衡量规则的双向置信度
Tagged with: