在数据分析和机器学习领域，我们经常需要将一个大型数据集（超集）划分为多个小型数据集（子集），以便进行交叉验证、并行处理或分组实验。一个常见的需求是确保这些子集在统计特性上与原始超集尽可能一致，特别是它们的均值。本文将深入探讨如何在满足子集大小预设要求的同时，实现子集均值与超集均值的最大程度接近。
假设我们有一个包含 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免费学习笔记（深入）”；
线性规划（Linear Programming, LP）是一种强大的优化工具，可以用来找到满足一系列线性约束的线性目标函数的最佳值。对于我们的问题，我们可以将其建模为一个整数线性规划问题。
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
注意事项：
当精确求解的计算成本过高时，启发式算法提供了一种快速获得近似解的方法。Karmarkar-Karp 算法（也称为最大差值法）是解决数集划分问题的一种著名启发式算法，其目标是将一组数字划分为两部分，使两部分的和尽可能接近。
Karmarkar-Karp 算法通常用于将一个集合划分为指定数量的子集，使其各子集的和尽可能相等。然而，它不直接支持预设子集大小的约束。这意味着，虽然它能尝试使子集的均值接近（通过使和接近），但它无法保证每个子集都包含特定数量的元素。
因此，Karmarkar-Karp 算法不完全符合我们原始问题中“创建 N 个包含 x0, ..., xn 元素的子集”的要求，但可以作为一种快速探索均值均衡分配的思路，或者在子集大小约束不那么严格时使用。
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] 并不匹配。
根据问题的规模和对精确度的要求，可以采用不同的策略：
以上就是Python数据划分策略：在指定子集大小下实现均值均衡的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
616
收藏
