基于多列目标的Pandas DataFrame高效子采样优化方案求助

我正在处理一个含50万行的Pandas DataFrame，每行对应一个地理多边形，34列分别代表不同土地覆盖类型的覆盖面积（单位：平方公里）。需求是筛选出一个多边形子集，使其各土地覆盖类型的累计面积尽可能接近或满足预设的目标需求。

当前采用的迭代方法（含权重计算、随机采样top0.5%、容忍度设置）存在两个核心问题：

• 速度极慢：仅能完成10次迭代/秒
• 误差控制差：累计面积远超目标却仍未达到容忍阈值

这本质是0-1整数规划问题（每个多边形只有选或不选两种状态），以下是针对大规模数据的可行优化方案：

附最小可复现示例：

import pandas as pd

# 创建示例DataFrame
data = {
    'Polygon': ['Polygon A', 'Polygon B', 'Polygon C', 'Polygon D'],
    'Landcover 1': [10, 5, 7, 3],
    'Landcover 2': [15, 8, 4, 6],
    'Landcover 3': [20, 12, 9, 14]
}
df = pd.DataFrame(data)

# 目标需求示例
target_requirements = {
    'Landcover 1': 15,
    'Landcover 2': 20,
    'Landcover 3': 25
}

方案1：贪心算法（快速可行解） #

核心思路 #

每次迭代选择能最大程度缩小当前累计面积与目标差距的多边形：

1. 初始化累计面积为0，已选多边形集合为空
2. 计算每个多边形对当前未满足目标的贡献优先级（优先填补缺口最大的覆盖类型）
3. 选择优先级最高的多边形加入集合，更新累计面积
4. 重复步骤2-3，直到所有覆盖类型的累计面积满足目标，或无更多有效多边形可选

代码实现 #

import pandas as pd

def greedy_selection(df, target):
    # 提取土地覆盖列
    lc_cols = [col for col in df.columns if col.startswith('Landcover')]
    # 初始化累计面积和已选索引
    current_total = pd.Series([0]*len(lc_cols), index=lc_cols)
    selected_indices = []
    # 目标转为Series
    target_series = pd.Series(target)
    
    while True:
        # 计算当前缺口
        gaps = target_series - current_total
        gaps[gaps < 0] = 0  # 已满足的类型缺口设为0
        
        if gaps.sum() == 0:
            break  # 所有目标满足
        
        # 计算每个多边形的优先级：对缺口的总贡献（仅考虑未满足的类型）
        polygon_contrib = df[lc_cols] * gaps
        polygon_priority = polygon_contrib.sum(axis=1)
        
        # 跳过对当前缺口无贡献的多边形
        polygon_priority = polygon_priority[polygon_priority > 0]
        if polygon_priority.empty:
            break
        
        # 选择优先级最高的多边形
        best_idx = polygon_priority.idxmax()
        selected_indices.append(best_idx)
        current_total += df.loc[best_idx, lc_cols]
    
    return df.loc[selected_indices], current_total

# 测试示例
selected_df, final_total = greedy_selection(df, target_requirements)
print("已选多边形：")
print(selected_df)
print("\n最终累计面积：")
print(final_total)

优势 #

• 速度极快：50万行数据的迭代次数通常在几百次以内，秒级完成
• 逻辑简单，易于调整优先级规则（比如给特定覆盖类型更高权重）

方案2：遗传算法（全局较优解） #

核心思路 #

通过模拟自然选择过程，在大规模解空间中搜索接近全局最优的子集：

1. 初始化一批随机子集作为种群
2. 计算每个子集的适应度（与目标的误差越小，适应度越高）
3. 通过选择、交叉、变异操作生成下一代种群
4. 迭代直到适应度不再提升或达到预设迭代次数

代码实现（基于deap库） #

from deap import base, creator, tools, algorithms
import pandas as pd
import random

def genetic_selection(df, target, pop_size=50, n_gen=20):
    lc_cols = [col for col in df.columns if col.startswith('Landcover')]
    target_series = pd.Series(target)
    n_polygons = len(df)
    
    # 定义适应度函数：最小化与目标的绝对误差之和
    creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
    creator.create("Individual", list, fitness=creator.FitnessMin)
    
    toolbox = base.Toolbox()
    toolbox.register("attr_bool", random.randint, 0, 1)
    toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, n=n_polygons)
    toolbox.register("population", tools.initRepeat, list, toolbox.individual)
    
    def evaluate(individual):
        selected = df[lc_cols].iloc[[i for i, val in enumerate(individual) if val == 1]]
        if selected.empty:
            return (float('inf'),)
        total = selected.sum()
        # 计算误差：仅考虑未满足的部分，同时惩罚超额过多的情况
        gaps = target_series - total
        gaps[gaps < 0] = gaps[gaps < 0] * 1.5  # 超额惩罚系数可调整
        error = abs(gaps).sum()
        return (error,)
    
    toolbox.register("mate", tools.cxTwoPoint)
    toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
    toolbox.register("select", tools.selTournament, tournsize=3)
    toolbox.register("evaluate", evaluate)
    
    # 运行算法
    pop = toolbox.population(n=pop_size)
    hof = tools.HallOfFame(1)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", lambda x: sum(x)/len(x))
    stats.register("min", min)
    
    algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=n_gen, stats=stats, halloffame=hof, verbose=True)
    
    # 获取最优解
    best_ind = hof[0]
    selected_indices = [i for i, val in enumerate(best_ind) if val == 1]
    return df.loc[selected_indices], df[lc_cols].iloc[selected_indices].sum()

# 测试示例
selected_df_ga, final_total_ga = genetic_selection(df, target_requirements)
print("已选多边形：")
print(selected_df_ga)
print("\n最终累计面积：")
print(final_total_ga)

优势 #

• 能找到比贪心算法更优的解，误差控制更精准
• 支持多目标权重调整（比如给关键覆盖类型更高的误差惩罚）
• 适合大规模数据，通过调整种群大小和迭代次数平衡速度与精度

方案3：线性规划近似（高精度近似解） #

核心思路 #

将0-1整数规划问题松弛为线性规划（允许多边形被部分选择），求解后通过阈值取整得到子集：

1. 定义变量：每个多边形的选择比例（0≤x≤1）
2. 目标函数：最小化与目标的误差
3. 求解线性规划后，将x≥0.5的多边形纳入子集

代码实现（基于scipy.optimize.linprog） #

from scipy.optimize import linprog
import pandas as pd
import numpy as np

def lp_approx_selection(df, target):
    lc_cols = [col for col in df.columns if col.startswith('Landcover')]
    target_vals = np.array(list(target.values()))
    lc_matrix = df[lc_cols].values
    n_polygons = len(df)
    
    # 目标函数：最小化绝对误差，转为线性规划形式（引入误差变量）
    c = np.zeros(n_polygons + len(lc_cols)*2)
    c[n_polygons:] = 1  # 误差变量的权重
    
    # 约束条件：累计面积 + 负误差 - 正误差 = 目标
    A_eq = np.zeros((len(lc_cols), len(c)))
    A_eq[:, :n_polygons] = lc_matrix.T
    A_eq[:, n_polygons:n_polygons+len(lc_cols)] = -np.eye(len(lc_cols))
    A_eq[:, n_polygons+len(lc_cols):] = np.eye(len(lc_cols))
    b_eq = target_vals
    
    # 变量边界：x∈[0,1]，误差变量≥0
    bounds = [(0,1)]*n_polygons + [(0, None)]*(len(lc_cols)*2)
    
    # 求解线性规划
    res = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='highs')
    
    # 取整：选择比例≥0.5的多边形
    selected_indices = np.where(res.x[:n_polygons] >= 0.5)[0]
    return df.loc[selected_indices], df[lc_cols].iloc[selected_indices].sum()

# 测试示例
selected_df_lp, final_total_lp = lp_approx_selection(df, target_requirements)
print("已选多边形：")
print(selected_df_lp)
print("\n最终累计面积：")
print(final_total_lp)

优势 #

• 解的精度较高，适合对误差控制要求严格的场景
• 数学模型严谨，可通过调整约束条件适配复杂需求

方案选择建议 #

额外优化技巧 #

• 数据预处理：提前过滤掉所有土地覆盖类型面积为0的多边形，减少计算量
• 并行计算：遗传算法和贪心算法的部分步骤可通过multiprocessing加速
• 误差惩罚调整：根据业务需求调整超额惩罚系数，避免累计面积远超目标

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