如何高效优化变量组合以最大化APP Lover分类数量

业务背景 #

目标是从用户APP/网站交互数据中，筛选出变量（x1、x2…xn）的最优组合，使得被分类为"APP Lover"的用户数量最多。判定规则为：用户在选中变量范围内的APP使用占比超过66%，即标记为"APP Lover"。

数据示例与现有处理流程 #

简化数据结构 #

import polars as pl
df = pl.DataFrame({
    "ID": [1, 2, 3, 1, 2, 3, 1, 2, 3],
    "variable": ["x1", "x1", "x1", "x2", "x2", "x2", "x3", "x3", "x3"],
    "Favourite": ["APP", "APP", "WEB", "APP", "WEB", "APP", "APP", "APP", "WEB"]
})

• ID：用户唯一标识
• variable：功能模块（如x1、x2）
• Favourite：用户执行该功能的渠道（APP/WEB）

现有统计与分类流程 #

1. 透视统计每个用户的APP/WEB操作次数：

df2 = (
    df
    .pivot(
        index=["ID"],
        on="Favourite",
        values=["variable"],
        aggregate_function=pl.col("Favourite").len()
    ).fill_null(0)
)

输出：

shape: (3, 3)
┌─────┬─────┬─────┐
│ ID  ┆ APP ┆ WEB │
│ --- ┆ --- ┆ --- │
│ i64 ┆ u32 ┆ u32 │
╞═════╪═════╪═════╡
│ 1   ┆ 3   ┆ 0   │
│ 2   ┆ 2   ┆ 1   │
│ 3   ┆ 1   ┆ 2   │
└─────┴─────┴─────┘

2. 计算APP使用占比并分类：

df_classified = (
    df2
    .with_columns(Total = pl.col("APP") + pl.col("WEB"))
    .with_columns(Proportion = pl.col("APP") / pl.col("Total"))
    .with_columns(
        pl.when(pl.col("Proportion") >= 0.6).then(pl.lit("APP Lover"))
        .when(pl.col("Proportion") > 0.1).then(pl.lit("BOTH"))
        .otherwise(pl.lit("Inactive"))
    )
)

输出：

shape: (3, 6)
┌─────┬─────┬─────┬───────┬────────────┬───────────┐
│ ID  ┆ APP ┆ WEB ┆ Total ┆ Proportion ┆ literal   │
│ --- ┆ --- ┆ --- ┆ ---   ┆ ---        ┆ ---       │
│ i64 ┆ u32 ┆ u32 ┆ u32   ┆ f64        ┆ str       │
╞═════╪═════╪═════╪═══════╪════════════╪═══════════╡
│ 1   ┆ 3   ┆ 0   ┆ 3     ┆ 1.0        ┆ APP Lover │
│ 2   ┆ 2   ┆ 1   ┆ 3     ┆ 0.666667   ┆ APP Lover │
│ 3   ┆ 1   ┆ 2   ┆ 3     ┆ 0.333333   ┆ BOTH      │
└─────┴─────┴─────┴───────┴────────────┴───────────┘

核心挑战 #

真实数据集包含至少19个变量，遍历所有2^19（约52万）种组合计算量极大，无法通过暴力枚举实现。

高效解决方案 #

1. 预处理：提前计算用户-变量级别的交互统计 #

先按用户和变量聚合，得到每个用户在单个变量下的APP/WEB操作数，后续组合计算时可直接累加，避免重复遍历原始数据：

# 按ID和variable聚合，得到每个用户-变量的APP/WEB计数
user_var_stats = df.group_by(["ID", "variable"]).agg(
    APP=pl.col("Favourite").filter(pl.col("Favourite") == "APP").count(),
    WEB=pl.col("Favourite").filter(pl.col("Favourite") == "WEB").count()
).fill_null(0)

# 转宽表，方便快速查询每个用户的各变量APP/WEB数
user_var_wide = user_var_stats.pivot(
    index="ID",
    columns="variable",
    values=["APP", "WEB"],
    aggregate_function="sum"
).fill_null(0)

2. 贪心算法（快速获取近似最优解） #

通过逐步添加/移除变量，每次选择对"APP Lover"数量提升最大（或减少最小）的变量，时间复杂度为O(n²)，适合快速得到可用解：

def compute_app_lovers(selected_vars, user_data):
    # 计算选中变量组合下的APP/WEB总数
    app_total = sum(user_data[f"APP_{var}"] for var in selected_vars)
    web_total = sum(user_data[f"WEB_{var}"] for var in selected_vars)
    total = app_total + web_total
    # 计算占比并统计APP Lover数量（排除无交互的用户）
    proportion = app_total / total.where(total > 0, pl.lit(0))
    return (proportion >= 0.6).sum()

# 贪心正向选择：从空组合开始，逐步添加最优变量
all_vars = [f"x{i}" for i in range(1, 20)]  # 假设变量为x1到x19
current_selected = []
current_max = compute_app_lovers(current_selected, user_var_wide)

while True:
    best_gain = 0
    best_var = None
    for var in all_vars:
        if var not in current_selected:
            temp_count = compute_app_lovers(current_selected + [var], user_var_wide)
            gain = temp_count - current_max
            if gain > best_gain:
                best_gain = gain
                best_var = var
    if best_gain <= 0:
        break  # 无提升空间，停止迭代
    current_selected.append(best_var)
    current_max = temp_count

print(f"贪心最优组合：{current_selected}，APP Lover数量：{current_max}")

3. 分支定界算法（获取全局最优解） #

通过搜索树+剪枝策略，避免遍历所有组合，适合19个变量的规模：

• 核心思路：每次分支时计算当前组合的理论最大可能APP Lover数（上界），如果上界小于当前已知最优解，直接剪枝该分支，减少无效计算。
• 实现要点：
  1. 先按变量对APP Lover的提升潜力排序，优先搜索高潜力分支；
  2. 快速计算上界：假设添加剩余所有变量后，所有非APP Lover用户都转化为APP Lover，得到理论最大值，若该值小于当前最优，直接放弃该分支。

4. 启发式搜索（遗传算法/模拟退火） #

适合变量更多的场景，通过迭代优化找到接近全局最优的解：

• 遗传算法：生成初始变量组合种群，通过选择（保留优质组合）、交叉（组合优质特征）、变异（引入新特征）迭代，逐步收敛到最优解；
• 模拟退火：从随机组合开始，逐步降低"接受较差解"的概率，避免陷入局部最优，最终得到较优解。

内容的提问来源于stack exchange，提问作者Simon