题解

题面描述

实现一个基于关联规则的市场篮子分析系统。要求如下：

1. 读取输入的交易数据，每个交易包含若干商品。
2. 计算每个商品对的支持度（$support$）。
3. 根据支持度阈值筛选出频繁的商品对。
4. 输出每个频繁商品对及其支持度，格式为三元组：($商品1$, $商品2$, $support$)，其中 $support$ 使用 round(x, 2) 保留两位小数。

题解思路

1. 数据输入
   输入数据为一个二维列表，其中每个列表代表一次交易。设交易数为 $N$（例如样例中 $N=5$）。

2. 生成商品对
   对于每笔交易，利用组合方法（如使用 itertools.combinations）生成所有可能的无序商品对。为了避免 ($商品1$, $商品2$) 与 ($商品2$, $商品1$) 被当作两个不同的组合，我们可以对商品进行排序后再生成组合。

3. 计算支持度
   使用字典记录每个商品对出现的次数。支持度定义为

   $$support = \frac{\text{商品对出现次数}}{N}$$

   即一个商品对在所有交易中出现的频率。

4. 筛选频繁商品对
   给定支持度的阈值（例如样例中阈值为 $0.6$），筛选出那些支持度大于等于此阈值的商品对。

5. 输出结果
   输出每个符合条件的商品对和其支持度，支持度保留两位小数。最终结果为一个包含多个三元组的列表，其中每个三元组格式为 ($商品1$, $商品2$, $support$)。

Python

import sys
import ast
from itertools import combinations


def market_basket_analysis(transactions, min_support=0.6):
    # 交易总数N
    N = len(transactions)
    # 用于记录每个商品对的出现次数的字典
    pair_counts = {}

    # 遍历每笔交易
    for transaction in transactions:
        # 对交易中商品进行排序，保证相同对只计数一次
        transaction = sorted(transaction)
        # 使用 combinations 生成二元组合
        for pair in combinations(transaction, 2):
            pair_counts[pair] = pair_counts.get(pair, 0) + 1

    # 用于存放满足支持度阈值的频繁商品对
    frequent_pairs = []
   
    for pair, count in pair_counts.items():
        support = count / N
        # 只有支持度大于等于最小阈值的商品对被记录
        if support >= min_support:
            frequent_pairs.append((pair[0], pair[1], round(support, 2)))

    return frequent_pairs


if __name__ == "__main__":
    # 一次性读取所有输入内容，适用于多行输入
    lines = sys.stdin.read().splitlines()
    # 去除空行
    lines = [line.strip() for line in lines if line.strip()]

    # 假设最后一行为支持度阈值，如果转换失败则使用默认阈值0.6
    try:
        min_support = float(lines[-1])
        trans_str = "\n".join(lines[:-1])
    except ValueError:
        min_support = 0.6
        trans_str = "\n".join(lines)

    # 将读取的字符串转换为二维列表
    transactions = ast.literal_eval(trans_str)

    # 调用市场篮子分析函数
    result = market_basket_analysis(transactions, min_support)
    for item in result:
        print(item)

题目内容

实现一个基于关联规则的市场篮子分析系统，具体要求如下：

1.读取输入的交易数据，每个交易包含若干商品。

2.计算每个商品对的支持度$(support)$。

3.根据支持度阈值筛选频繁商品对。

4.输出每个频繁商品对及其支持度。

输入描述

输入为一个二维列表，表示若干交易，每个交易包含若干商品。

输出描述

输出为一个包含频繁商品对及其支持度的列表，每个元素是一个三元组(商品$1$，商品$2$，支持度)，使用$round(x,2)$保留小数位。

样例1

输入

[
["milk","bread","butter"],
["bread","butter"],
["milk","bread"],
["milk","butter"],
["bread","butter","jam"]
]

输出

('bread', 'butter', 0.6)