arrays - 最小化Matlab中数组列的总和

Question

我有一个大数组(大约 250,000 x 10)。每行包含 1 或 -1。例如:

data(1, :) = [1, -1, -1, -1, -1, -1, -1, -1, 1, -1];

我需要选择 n 行的集合，以使列的绝对总和的平均值最小化(尽可能接近于零)。所以，在这个玩具示例中，其中 n=2:

[ 1  1  1  1]
[-1 -1 -1 -1]
[-1  1 -1  1]

我会选择第 1 行和第 2 行，因为它们的总和为 [0 0 0 0](均值 0)，这是 n=2 时可能的最小值。

---

我尝试了下面建议的方法(寻找互补对)，但对于我的数据集，这只能形成 23k 行的平衡子集。因此，我需要一个近似值，它生成大小为 n 行的子集，但具有列的绝对和的最小均值。

到目前为止，我发现的最佳方法如下:选择一个起始子集，迭代地将剩余的每一行添加到基数，如果它提高了列的绝对和的平均值，则保留它。这是非常粗糙的，我相信有更好的方法。它也很容易卡在错误的最小值，所以需要添加一个应急措施:

shuffle = randperm(size(data));
data_shuffled = data(shuffle, :);

base = data_shuffled(1:30000, :);
pool = data_shuffled(30001:end, :);

best_mean = mean(abs(sum(base, 1)));
best_matrix = base;
n = 100000;

for k = 1:20

    for i = 1:size(pool, 1)
        temp = pool (i, :);

        if(~isnan(temp(1)))
            temp_sum = sum(temp, 1);
            new_sum = temp_sum + sum(best, 1);
            temp_mean = mean(abs(new_sum));

            if(temp_mean < best_mean)
                best_mean = temp_mean;
                best_matrix = vertcat(best_matrix, temp);
                pool(i, :) = NaN(1, 10);            
            end
        end
    end

    if(size(best_matrix, 1) > n)
        return
    end

end

这实现了约 17,000 列的绝对总和的平均值，这还算不错。重复使用不同的种子可能会有所改善。

理想情况下，与其将新元素添加到 best_matrix 的末尾，不如将其与某些元素交换，以实现最佳改进。

更新:我不想给出数据集的具体细节，因为所有解决方案都应该适用于指定格式的任何矩阵。

感谢所有做出贡献的人!

Answer 1

下面的方法呢？由于 10 列只有 +1 和 -1 值，所以只有 1024 行可能。所以我们的数据现在是:

1. 一个 1024 x 10 矩阵 a(i,j)，系数为 -1 和 +1。该矩阵具有所有不同的可能(唯一)行。
2. 一个向量 v(i)，其中包含我们看到第 i 行的次数。

现在我们可以写一个简单的混合整数规划问题如下:

注意事项:

• 我们只有 1024 个整数变量
• 我们在 x(i) 上设置一个上限，表示可以选择一行的次数
• 我们使用所谓的变量拆分技术对绝对值进行建模并保持模型线性
• 最小化均值和最小化和是一样的(差是常数因子)
• 关于 optcr 的那行告诉 MIP 求解器找到经过验证的全局最优解
• 一个好的 MIP 求解器应该能够非常快速地找到解决方案。我使用 250k 行和 N=100 对一些随机数据进行了测试。 我实际上认为这是一个简单的问题。
• 重申:此方法提供经过验证的全局最优解。
• 可以找到更多详细信息here .