优化变量组合以最大化分类

Question

我正在处理一个数据集，其中用户通过应用程序或网站进行交互，我需要确定变量的最佳组合

(x1, x2, ... xn)

，这将最大限度地增加被归类为“应用程序爱好者”的用户数量。根据商业规则，如果用户使用应用程序的时间超过 66%，则被视为“应用爱好者”。

这是数据结构的简化示例：

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

指的是函数

(e.g., x1, x2, x3)

，Favorite 表示该函数是通过应用程序还是网站执行的。

我通过数据透视来计算通过 APP 或 WEB 执行的操作数量：

(
    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   │
└─────┴─────┴─────┘

接下来，我计算每个用户的应用程序使用比例并对其进行分类：

(
    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 个不同的 x 变量。昨天问，我尝试迭代这些变量的所有可能组合，以过滤掉那些导致“APP爱好者”数量最多的组合，但是组合的数量

(2^19)

太大，无法有效计算。

问题：如何有效地确定xn个变量的最佳组合，使“APP爱好者”的数量最大化？我正在寻找有关如何在算法优化或更有效的迭代方面解决此问题的指导。

Answer 1

这是我的建议，获取数据：

df = pl.DataFrame({
    "id": [1, 2, 3, 1, 2, 3, 1, 2, 3],
    "variable": ["x1", "x1", "x1", "x2", "x2", "x2", "x3", "x3", "x3"],
    "favorite": ["APP", "APP", "WEB", "APP", "WEB", "APP", "APP", "APP", "WEB"]
})

如果用户

xi

主要通过应用程序使用该操作，则对其进行旋转，使列

true

变为

id

：

action_through_app = (
    df
    .with_columns(pl.col.favorite == "APP")
    .pivot(index="id", on="variable", values="favorite")
)

例如：

shape: (3, 4)
┌─────┬───────┬───────┬───────┐
│ id  ┆ x1    ┆ x2    ┆ x3    │
│ --- ┆ ---   ┆ ---   ┆ ---   │
│ i64 ┆ bool  ┆ bool  ┆ bool  │
╞═════╪═══════╪═══════╪═══════╡
│ 1   ┆ true  ┆ true  ┆ true  │
│ 2   ┆ true  ┆ false ┆ true  │
│ 3   ┆ false ┆ true  ┆ false │
└─────┴───────┴───────┴───────┘

现在，如果给定一些组合变量，我们可以通过对相关列求和并检查它们的总和是否 >= 0.6 * 列数来有效查询有多少用户会成为应用程序爱好者。

def num_app_lovers(combination):
    return (pl.sum_horizontal(combination) >= 0.6*len(combination)).sum()

action_through_app.select(
    num_app_lovers([pl.col.x1]).alias("x1"),
    num_app_lovers([pl.col.x2]).alias("x2"),
    num_app_lovers([pl.col.x3]).alias("x3"),
    num_app_lovers([pl.col.x1, pl.col.x2]).alias("x12"),
    num_app_lovers([pl.col.x2, pl.col.x3]).alias("x23"),
    num_app_lovers([pl.col.x1, pl.col.x3]).alias("x13"),
    num_app_lovers([pl.col.x1, pl.col.x2, pl.col.x3]).alias("x123"),
)

shape: (1, 7)
┌─────┬─────┬─────┬─────┬─────┬─────┬──────┐
│ x1  ┆ x2  ┆ x3  ┆ x12 ┆ x23 ┆ x13 ┆ x123 │
│ --- ┆ --- ┆ --- ┆ --- ┆ --- ┆ --- ┆ ---  │
│ u32 ┆ u32 ┆ u32 ┆ u32 ┆ u32 ┆ u32 ┆ u32  │
╞═════╪═════╪═════╪═════╪═════╪═════╪══════╡
│ 2   ┆ 2   ┆ 2   ┆ 1   ┆ 1   ┆ 2   ┆ 2    │
└─────┴─────┴─────┴─────┴─────┴─────┴──────┘

现在，您可以批量查询组合，但这仍然不能很好地扩展到 2^19 个可能的组合。对于这个问题，我建议使用进化编程。

用 x1, x2, x3, ... xn 初始化一个可能的组合池。然后，向池中的每个组合随机添加或删除一列（如果 > 1 列），并使用上述查询对其进行测试。保留前 100 个组合。重复这个过程进行多次迭代，直到结果不再改善，然后返回。