在数据分析和机器学习领域，我们经常需要将一个大型数据集（超集）划分为多个小型数据集（子集），以便进行交叉验证、并行处理或分组实验。一个常见的需求是确保这些子集在统计特性上与原始超集尽可能一致，特别是它们的均值。本文将深入探讨如何在满足子集大小预设要求的同时，实现子集均值与超集均值的最大程度接近。
问题定义与数学建模
假设我们有一个包含 M 个元素的超集 S，其中的元素是实数（通常是正浮点数）。我们的目标是将 S 无重复地划分为 N 个子集 S_0, S_1, ..., S_{N-1}，每个子集 S_i 包含 x_i 个元素，且 sum(x_0, ..., x_{N-1}) == M。核心约束是使每个子集 S_i 的均值 mean(S_i) 尽可能接近超集的均值 mean(S)。
为了量化“接近程度”，我们可以定义一个误差函数。一个直观且“公平”的方法是最小化所有子集均值与超集均值之间绝对差值的总和。由于子集大小 x_i 是固定的，最小化均值差的绝对值之和等价于最小化子集元素和与目标和的绝对差值之和。具体来说，如果超集均值为 μ_S，则子集 S_i 的目标和为 x_i * μ_S。
这个优化问题可以归类为集合划分问题（Set Partitioning Problem）的一个变种，通常通过整数线性规划（ILP）来解决。
立即学习“Python免费学习笔记（深入）”；
解决方案一：基于线性规划的精确求解 (使用 PuLP)
线性规划（Linear Programming, LP）是一种强大的优化工具，可以用来找到满足一系列线性约束的线性目标函数的最佳值。对于我们的问题，我们可以将其建模为一个整数线性规划问题。
核心思路
- 决策变量： 为超集中的每个元素 j 和每个子集 i 定义一个二进制决策变量 v_{ij}。如果元素 j 被分配到子集 i，则 v_{ij} = 1；否则 v_{ij} = 0。
- 目标函数： 最小化所有子集均值与超集均值绝对差值的总和。为了在线性规划中处理绝对值，我们引入辅助变量 abs_err_i，并通过两个不等式约束来表示 abs_err_i >= err_i 和 abs_err_i >= -err_i。
-
约束条件：
- 子集大小约束： 每个子集 S_i 必须包含预设的 x_i 个元素。即 sum(v_{ij} for all j) = x_i。
- 元素唯一性约束： 超集中的每个元素 j 只能被分配到一个且仅一个子集。即 sum(v_{ij} for all i) = 1。
PuLP 实现示例
PuLP 是一个 Python 库，用于建模和解决线性规划问题。以下代码展示了如何使用 PuLP 解决上述问题。
from statistics import mean
import pulp
def solve_subset_partitioning(superset_data, set_sizes):
"""
使用PuLP解决子集划分问题，使各子集均值尽可能接近超集均值。
Args:
superset_data (list): 包含所有元素的超集列表。
set_sizes (list): 包含每个子集所需元素数量的列表。
Returns:
tuple: (list of lists) 划分后的子集, (float) 超集均值
"""
# 计算超集均值和总和
superset_mean = mean(superset_data)
target_total_sum = sum(superset_data) # 实际上我们关心的是均值，但PuLP更方便处理总和
N = len(set_sizes)
if sum(set_sizes) != len(superset_data):
raise ValueError("所有子集大小之和必须等于超集元素总数。")
# 初始化PuLP问题
set_partitioning_model = pulp.LpProblem("Set_Partitioning_Model", pulp.LpMinimize)
# 决策变量：covering[s][i] = 1 如果超集中的第i个元素被分配给子集s
covering = {}
for s_idx in range(N):
vals = []
for i, v in enumerate(superset_data):
vals.append(
pulp.LpVariable(
f"covering_set_{s_idx}_value_idx_{i:>02}_val_{v}",
lowBound=0,
upBound=1,
cat=pulp.LpInteger, # 0或1的整数变量
)
)
covering[s_idx] = vals
# 辅助变量：用于处理绝对误差
abs_sum_errs = []
for s_idx in range(N):
set_sum_err_abs = pulp.LpVariable(f"set_{s_idx}_sum_error_abs", lowBound=0)
abs_sum_errs.append(set_sum_err_abs)
# 目标函数：最小化所有子集与超集目标和的绝对误差之和
# 注意：这里我们最小化的是子集总和与超集总和的误差，因为超集总和是固定的。
# 实际上，更直接的应该是最小化子集和与 (子集大小 * 超集均值) 的误差。
# 为了简化，我们可以最小化子集和与一个“理想”总和的误差。
# 或者，如原问题所述，最小化子集总和与 target_sum 的误差，这在某些情况下可能不够精确反映均值目标。
# 让我们调整为最小化子集总和与 (子集大小 * 超集均值) 的误差。
set_partitioning_model += pulp.lpSum(abs_sum_errs), "Total_Absolute_Error"
for s_idx, st_vars in covering.items():
# 计算当前子集s的元素总和
current_set_sum = pulp.lpSum([p * superset_data[i] for i, p in enumerate(st_vars)])
# 计算子集s的目标总和（基于超集均值和子集大小）
target_set_sum = set_sizes[s_idx] * superset_mean
# 计算子集s的总和误差
set_sum_err = pulp.LpVariable(f"set_{s_idx}_sum_error")
set_partitioning_model += set_sum_err == current_set_sum - target_set_sum, \
f"Set_{s_idx}_Sum_Error_Definition"
# 定义绝对误差的约束
set_partitioning_model += abs_sum_errs[s_idx] >= set_sum_err, \
f"Set_{s_idx}_Abs_Error_Upper_Bound_Pos"
set_partitioning_model += abs_sum_errs[s_idx] >= -set_sum_err, \
f"Set_{s_idx}_Abs_Error_Upper_Bound_Neg"
# 约束：每个子集的大小是预设的
for n, st_vars in zip(set_sizes, covering.values()):
set_partitioning_model += pulp.lpSum(st_vars) == n, \
f"Set_Size_Constraint_{set_sizes.index(n)}"
# 约束：超集中的每个元素只能被使用一次
for i, _ in enumerate(superset_data):
set_partitioning_model += (
pulp.lpSum([covering[s_idx][i] for s_idx in range(N)]) == 1,
f"Element_{i}_Used_Once"
)
# 求解模型
set_partitioning_model.solve(pulp.PULP_CBC_CMD(msg=False)) # msg=False 减少输出
# 解析结果
result_subsets = [[] for _ in range(N)]
for s_idx in range(N):
for i, var in enumerate(covering[s_idx]):
if var.value() == 1:
result_subsets[s_idx].append(superset_data[i])
return result_subsets, superset_mean
# 示例 1: 完美分配
superset1 = [100]*5 + [101]*10 + [102]*5
set_sizes1 = [2, 4, 14]
result_subsets1, superset_mean1 = solve_subset_partitioning(superset1, set_sizes1)
print("--- 示例 1 结果 ---")
print(f"超集均值: {superset_mean1}")
for i, subset in enumerate(result_subsets1):
print(f"子集 {i}: {subset}, 均值: {mean(subset)}")
# 示例 2: 最佳拟合（无法完美分配）
superset2 = [100]*5 + [103]*10 + [104]*5
set_sizes2 = [2, 4, 14]
result_subsets2, superset_mean2 = solve_subset_partitioning(superset2, set_sizes2)
print("\n--- 示例 2 结果 ---")
print(f"超集均值: {superset_mean2}")
for i, subset in enumerate(result_subsets2):
print(f"子集 {i}: {subset}, 均值: {mean(subset)}")示例 1 运行结果:
--- 示例 1 结果 --- 超集均值: 101 子集 0: [100, 102], 均值: 101 子集 1: [100, 100, 102, 102], 均值: 101 子集 2: [100, 100, 100, 101, 101, 101, 101, 101, 101, 101, 101, 102, 102, 102], 均值: 101
示例 2 运行结果:
--- 示例 2 结果 --- 超集均值: 102.5 子集 0: [103, 103], 均值: 103 子集 1: [100, 100, 104, 104], 均值: 102 子集 2: [100, 100, 100, 103, 103, 103, 103, 103, 103, 103, 103, 104, 104, 104], 均值: 102.57142857142857
注意事项：
- 计算复杂度： 线性规划求解器在理论上是多项式时间复杂度的，但在实际应用中，对于大规模的整数线性规划问题（变量数量和约束数量都很大），求解时间可能会显著增加。当超集元素数量和子集数量都很大时，可能无法在1秒内得到结果。
- 绝对值处理： 在线性规划中，目标函数或约束中不能直接包含绝对值。通过引入辅助变量和一对不等式约束，可以将 |x| 转换为线性形式：y >= x 和 y >= -x，其中 y 是要最小化的变量。
- PuLP求解器： PuLP 默认使用 CBC 求解器，这是一个开源的混合整数规划求解器。对于更复杂的商业求解器（如 Gurobi, CPLEX），可能需要额外的配置。
解决方案二：启发式算法 (Karmarkar-Karp)
当精确求解的计算成本过高时，启发式算法提供了一种快速获得近似解的方法。Karmarkar-Karp 算法（也称为最大差值法）是解决数集划分问题的一种著名启发式算法，其目标是将一组数字划分为两部分，使两部分的和尽可能接近。
算法特点与局限性
Karmarkar-Karp 算法通常用于将一个集合划分为指定数量的子集，使其各子集的和尽可能相等。然而，它不直接支持预设子集大小的约束。这意味着，虽然它能尝试使子集的均值接近（通过使和接近），但它无法保证每个子集都包含特定数量的元素。
因此，Karmarkar-Karp 算法不完全符合我们原始问题中“创建 N 个包含 x0, ..., xn 元素的子集”的要求，但可以作为一种快速探索均值均衡分配的思路，或者在子集大小约束不那么严格时使用。
numberpartitioning 库示例
numberpartitioning 是一个 Python 库，实现了 Karmarkar-Karp 算法。
from statistics import mean
from numberpartitioning import karmarkar_karp
superset = [100]*5 + [103]*10 + [104]*5
# 注意：Karmarkar-Karp算法不接受预设的子集大小
# 它会尝试将超集划分为指定数量的子集，使它们的和（或均值）尽可能接近。
print("--- Karmarkar-Karp 算法示例 ---")
print(f"超集均值: {mean(superset)}")
# 将超集划分为 3 个部分
for p in karmarkar_karp(superset, num_parts=3).partition:
print(f"子集: {p}, 均值: {mean(p)}")运行结果:
--- Karmarkar-Karp 算法示例 --- 超集均值: 102.5 子集: [104, 104, 103, 103, 103, 100], 均值: 102.83333333333333 子集: [100, 103, 104, 103, 103, 103, 100], 均值: 102.28571428571429 子集: [100, 104, 104, 103, 103, 103, 100], 均值: 102.42857142857143
从结果可以看出，Karmarkar-Karp 算法确实生成了均值相对接近的子集，但这些子集的大小（分别为 6, 7, 7）与我们预设的 [2, 4, 14] 并不匹配。
性能考量与策略选择
根据问题的规模和对精确度的要求，可以采用不同的策略：
-
小规模问题（超集元素少，子集数量少）：
- 策略： 直接使用线性规划（如 PuLP 方案）。它能找到最优解，确保均值偏差最小。
- 适用场景： 超集元素数量在几百以内，子集数量在几十以内。
- 优势： 结果
