深入C++序列挖掘算法（从零开始掌握频繁序列发现与数据挖掘实战）

什么是序列挖掘？

序列挖掘（Sequential Pattern Mining）是指从一系列有序事件中找出频繁出现的子序列。例如：

• 用户A：浏览商品 → 加入购物车 → 下单
• 用户B：搜索商品 → 浏览商品 → 下单

通过序列模式挖掘，我们可以发现“浏览商品 → 下单”是一个高频模式，这对优化产品推荐非常有价值。

常用算法简介

最经典的序列挖掘算法是 AprioriAll 和 GSP（Generalized Sequential Pattern）。本文将基于简化版 GSP 思想，用 C++ 实现一个基础版本。

C++实现步骤详解

我们将完成以下任务：

1. 定义序列数据结构
2. 统计所有长度为1的频繁项
3. 逐层生成候选序列并剪枝
4. 输出最终的频繁序列

1. 定义数据结构

首先，我们需要表示一个序列。每个序列由多个“事件项”组成，比如 {A, B, C}。我们可以用 vector<string> 表示一个序列，用 vector<vector<string>> 表示整个数据库。

#include <iostream>#include <vector>#include <map>#include <string>#include <algorithm>using namespace std;// 数据库：每个元素是一个序列（如 {"A", "B", "C"}）typedef vector<string> Sequence;typedef vector<Sequence> Database;

2. 统计频繁1-项集

遍历所有序列，统计每个单项出现的次数，保留支持度大于阈值的项。

// 计算频繁1-项集map<string, int> getFrequentItems(const Database& db, int min_support) {    map<string, int> freq;    for (const auto& seq : db) {        for (const string& item : seq) {            freq[item]++;        }    }    // 过滤低于最小支持度的项    map<string, int> result;    for (const auto& p : freq) {        if (p.second >= min_support) {            result[p.first] = p.second;        }    }    return result;}

3. 生成候选k-序列

以频繁(k-1)-序列为基础，通过连接操作生成候选k-序列。为简化，我们只考虑按字典序连接且无重复项的情况。

// 生成候选2-序列（简化版）vector<Sequence> generateCandidates(const map<string, int>& freq1) {    vector<Sequence> candidates;    vector<string> items;    for (const auto& p : freq1) {        items.push_back(p.first);    }    sort(items.begin(), items.end());    for (size_t i = 0; i < items.size(); ++i) {        for (size_t j = i + 1; j < items.size(); ++j) {            candidates.push_back({items[i], items[j]});        }    }    return candidates;}

4. 检查候选序列是否频繁

// 判断序列 seq 是否包含子序列 cand（顺序匹配）bool contains(const Sequence& seq, const Sequence& cand) {    size_t i = 0; // cand 的索引    for (const string& item : seq) {        if (i < cand.size() && item == cand[i]) {            i++;        }    }    return i == cand.size();}// 计算候选序列的支持度map<Sequence, int, SequenceCompare> getFrequentSequences(    const Database& db,    const vector<Sequence>& candidates,    int min_support) {        map<Sequence, int, SequenceCompare> freq;    for (const auto& cand : candidates) {        int count = 0;        for (const auto& seq : db) {            if (contains(seq, cand)) {                count++;            }        }        if (count >= min_support) {            freq[cand] = count;        }    }    return freq;}

注意：C++ 的 map 默认不能直接用 vector<string> 作 key，需自定义比较函数：

struct SequenceCompare {    bool operator()(const Sequence& a, const Sequence& b) const {        return a < b;    }};

5. 主函数整合

int main() {    // 示例数据库    Database db = {        {"A", "B", "C"},        {"A", "C"},        {"B", "C"},        {"A", "B", "C", "D"},        {"B", "D"}    };    int min_support = 2; // 最小支持度    // 步骤1：找频繁1-项    auto freq1 = getFrequentItems(db, min_support);    cout << "频繁1-项集:\n";    for (const auto& p : freq1) {        cout << p.first << ": " << p.second << "\n";    }    // 步骤2：生成候选2-序列    auto candidates = generateCandidates(freq1);    // 步骤3：筛选频繁2-序列    auto freq2 = getFrequentSequences(db, candidates, min_support);    cout << "\n频繁2-序列:\n";    for (const auto& p : freq2) {        cout << "{";        for (size_t i = 0; i < p.first.size(); ++i) {            if (i > 0) cout << ", ";            cout << p.first[i];        }        cout << "}: " << p.second << "\n";    }    return 0;}

总结与进阶

通过本教程，你已经掌握了如何用 C++ 实现一个基础的频繁序列发现程序。虽然我们只实现了2-序列挖掘，但你可以在此基础上扩展到更长的序列（使用递归或队列逐层生成）。实际项目中，可结合 STL、智能指针和更高效的数据结构（如 Trie 树）来优化性能。

记住，C++数据挖掘教程的核心在于理解算法逻辑，而非语言本身。一旦掌握原理，迁移到 Python 或 Java 也会非常容易。

动手实践是掌握C++序列挖掘算法的最佳方式！尝试修改数据库和最小支持度，观察结果变化吧。