题目内容

工位抽检会留下若干条样本记录，每条记录给出该次抽检中同时出现的互异零件编号。产线侧希望按给定的最小支持计数，筛出频繁共现组合。请实现 $Apriori$ 算法，挖掘全部频繁项集。

1. 输入定义

• records：二维列表，records[t] 是一条抽检记录的整数编号列表，元素不重复；记录条数 $n$ 满足 $1\le n\le 24$，列表 records[t] 的数据元素数量不超过 $4$
• min_cnt：最小支持计数（正整数，即 $\ge 1$）

2. $Apriori$ 过程

候选生成

• $k=1$：统计所有记录中每个单项编号的总出现次数，得到频繁 $1$-项集集合 $G_1$
• $k\ge 2$：用 $G_{k-1}$ 两两连接并剪枝生成候选集合 $D_k$
  • 连接条件：两项均已按编号升序存放；前 $k-2$ 个元素对应相同，且第一项的末元素小于第二项的末元素，连接结果为前 $k-2$ 个元素再加上这两个末元素
  • 剪枝：若 $D_k$ 中某候选的任何一个 $(k-1)$ 元子集不在 $G_{k-1}$ 中，则丢弃该候选

扫描计数

• 对每条记录，检查候选是否为其子集，据此累计 $D_k$ 中所有候选的支持计数。候选 $X$ 的支持计数定义为包含它的记录条数：

• 筛选：满足 $\mathrm{sup}(X)\ge \textit{min\_cnt}$ 的候选进入 $G_k$
• 直到 $G_k$ 为空终止，合并全部 $G_k$ 得到频繁项集全集 $U$

3. 输出排序

• 先按项集大小升序
• 若大小相同则按字典序（编号升序比较）
• 每个项集输出为升序编号列表，并附带支持计数

输入描述

{
    "records": [[1,2], [1,2], [1,3], [2,3]],
    "min_cnt": 2
}

输出描述

单行 JSON 数组，元素结构 `[[id1,...], support]`；示例
[[[1], 3], [[2], 3], [[3], 2], [[1, 2], 2]]

补充说明

为了确保通过测试用例，只能使用 numpy / pandas / scikit-learn。

样例1

输入

{"records":[[1,2],[1,2],[1,3],[2,3]],"min_cnt":2}

输出

[[[1], 3], [[2], 3], [[3], 2], [[1, 2], 2]]

说明

四条记录中，编号 $1,2,3$ 的出现次数分别为 $3,3,2$，均不低于 $2$，故进入 $G_1$。二元候选里只有 $\{1,2\}$ 出现 $2$ 次，其余 $\{1,3\}$、$\{2,3\}$ 各出现 $1$ 次被丢掉。$G_2$ 仅含一项，无法再连接出三元候选，过程结束。按大小再按字典序输出上述四项。

样例2

输入

{"records":[[2,3,5],[2,3,5],[2,3],[3,5]],"min_cnt":2}

输出

[[[2], 3], [[3], 4], [[5], 3], [[2, 3], 3], [[2, 5], 2], [[3, 5], 3], [[2, 3, 5], 2]]

说明

单项支持为 $\mathrm{sup}(\{2\})=3$、$\mathrm{sup}(\{3\})=4$、$\mathrm{sup}(\{5\})=3$。二元三项 $\{2,3\}$、$\{2,5\}$、$\{3,5\}$ 的支持分别为 $3,2,3$，全部进入 $G_2$。连接 $\{2,3\}$ 与 $\{2,5\}$ 得到 $\{2,3,5\}$，其三个二元子集均在 $G_2$ 中，支持计数为 $2$，进入 $G_3$。之后 $G_3$ 无法再连接，输出上述七项。