最小化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

正如其他人所说，最佳解决方案可能是不可能的，所以我将重点关注特定情况。

首先，我假设每列的分布是独立的。

然后我研究累加器空间以减少数据大小并加快代码速度。

我将每个-1作为0并将每行视为一个数字，然后添加 1 以避免使用 0 作为索引，例如：

data(1,:)=[-1 1 -1 1 -1 1 -1 1 -1 1] -> '0101010101' -> 341 -> 342

这样我们就可以将数据累积为：

function accum=mat2accum(data)

[~,n]=size(data);
indexes=bin2dec(num2str((data+1)/2))+1;
accum=accumarray(indexes,1,[2^n 1]);

我考虑的第一种情况是，当每列的总和与数据大小相比较小时，这意味着所有列中的 1 和 -1 数量相似。

sum(data) << size(data)

对于这种情况，您可以找到所有相互抵消的对，例如：

data(1,:)=[-1 1 -1 1 -1 1 -1 1 -1 1] -> '0101010101' -> 341 -> 342
data(2,:)=[1 -1 1 -1 1 -1 1 -1 1 -1] -> '1010101010' -> 682 -> 683

我们知道每对都将位于累加器索引中的镜像位置，因此我们可以通过以下方式获得所有可能的对：

function [accumpairs, accumleft]=getpairs(accum)

accumpairs=min([accum,accum(end:-1:1)],[],2);
accumleft=accum-accumpairs;

通过随机生成的数据，我能够在 250k 行的集合中获得 >100k 对，并且每列中的一个子集的总和等于 0。因此，如果 1 和 -1 均匀分布，这可能就足够了。

我考虑的第二种情况是每列的总和远离零，这意味着 1 和 -1 之间存在很大的不成比例。

abs(sum(data)) >> 0

通过反转总和为负的每一列，这不会影响数据，因为最后可以再次反转这些列。可以强制不比例中 1 的数量多于 -1 的数量。通过首先提取该数据的可能对，这种不比例甚至更加明显。

通过这样准备的数据，可以将问题处理为最小化所需集合中 1 的数量。为此，我们首先随机化可能的索引，然后计算并排序每个索引的汉明权重（二进制表示中 1 的数量），然后收集可能具有最小汉明权重的数据。

function [accumlast,accumleft]=resto(accum,m)

[N,~]=size(accum);
columns=log2(N);
indexes=randperm(N)'; %'
[~,I]=sort(sum((double(dec2bin(indexes-1,columns))-48),2));
accumlast=zeros(N,1);

for k=indexes(I)' %'
    accumlast(k)=accum(k);
    if sum(accumlast)>=m
        break
    end
end

accumleft=accum-accumlast;

对于随机生成的数据，其中 1 的数量大约是 -1 的 2 倍，并且每列的总和约为 80k，我可以找到 100k 数据的子集，每列中的总和约为 5k。

第三种情况是某些列的总和接近零而有些则不是。在这种情况下，您将列分为总和较大的列和总和较小的列，然后按大总和列的汉明权重对数据进行排序，并获取每个大列索引内的小总和列对。这将为大总和列的每个索引创建一个矩阵，其中包含可能对的数量、不成对行的数量以及小列的不成对行的总和。

现在，您可以使用该信息来保存运行总和，并查看大总和列的哪些索引要添加到您的子集中，以及是否值得在每种情况下添加寓言或不可配对的数据。

function [accumout,accumleft]=getseparated(accum, bigcol, smallcol, m)

data=accum2mat(accum);

'indexing'
bigindex=bin2dec(num2str((data(:,bigcol)+1)/2))+1;
[~,bn]=size(bigcol);
[~,sn]=size(smallcol);

'Hamming weight'
b_ind=randperm(2^bn)'; %'
[~,I]=sort(sum((double(dec2bin(b_ind-1,bn))-48),2));

temp=zeros(2^bn,4+sn);

w=waitbar(0,'Processing');
for k=1:2^bn;
    small_data=data(bigindex==b_ind(I(k)),smallcol);
    if small_data
        small_accum=mat2accum(small_data);
        [small_accumpairs, small_accum]=getpairs(small_accum);
        n_pairs=sum(small_accumpairs);
        n_non_pairs=sum(small_accum);
        sum_non_pairs=sum(accum2mat(small_accum));
    else
        n_pairs=0;
        n_non_pairs=0;
        sum_non_pairs=zeros(1,sn);
    end
    ham_weight=sum((double(dec2bin(b_ind(I(k))-1,bn))-48),2);
    temp(k,:)=[b_ind(I(k)) n_pairs n_non_pairs ham_weight sum_non_pairs];
    waitbar(k/2^bn);
end

close(w)

pair_ind=1;
nonpair_ind=1;
runningsum=[0 0 0 0 0 0 0 0 0 0];
temp2=zeros(2^bn,2);

while sum(sum(temp2))<=m
     if pair_ind<=2^bn
         pairsum=[(((double(dec2bin((temp(pair_ind,1)-1),bn))-48)*2)-1)*temp(pair_ind,2) zeros(1,sn)];
     end
     if nonpair_ind<=2^bn
         nonpairsum=[(((double(dec2bin((temp(nonpair_ind,1)-1),bn))-48)*2)-1)*temp(nonpair_ind,3) temp(nonpair_ind,5:5+sn-1)];
     end
     if nonpair_ind==(2^bn)+1
         temp2(pair_ind,1)=temp(pair_ind,2);
         runningsum=runningsum+pairsum;
         pair_ind=pair_ind+1;
     elseif pair_ind==(2^bn)+1
         temp2(nonpair_ind,2)=temp(nonpair_ind,3);
         runningsum=runningsum+nonpairsum;
         nonpair_ind=nonpair_ind+1;
     elseif sum(abs(runningsum+pairsum))<=sum(abs(runningsum+nonpairsum))
         temp2(pair_ind,1)=temp(pair_ind,2);
         runningsum=runningsum+pairsum;
         pair_ind=pair_ind+1;
     elseif sum(abs(runningsum+pairsum))>sum(abs(runningsum+nonpairsum))
         temp2(nonpair_ind,2)=temp(nonpair_ind,3);
         runningsum=runningsum+nonpairsum;
         nonpair_ind=nonpair_ind+1;
     end
end

accumout=zeros(2^(bn+sn),1);

for k=1:2^bn
    if temp2(k,:)
        small_data=data(bigindex==temp(k,1),smallcol);
        if small_data
            small_accum=mat2accum(small_data);
            [small_accumpairs, small_accum]=getpairs(small_accum);
            pairs=accum2mat(small_accumpairs);
            non_pairs=accum2mat(small_accum);
        else
            pairs=zeros(1,sn);
            non_pairs=zeros(1,sn);
        end
        if temp2(k,1)
            datatemp=zeros(temp2(k,1),sn+bn);
            datatemp(:,bigcol)=((double(dec2bin(ones(temp2(k,1),1)*(temp(k,1)-1),bn))-48)*2)-1;
            datatemp(:,smallcol)=pairs;
            accumout=accumout+mat2accum(datatemp);
        end
        if temp2(k,2)
            datatemp=zeros(temp2(k,2),sn+bn);
            datatemp(:,bigcol)=((double(dec2bin(ones(temp2(k,2),1)*(temp(k,1)-1),bn))-48)*2)-1;
            datatemp(:,smallcol)=non_pairs;
            accumout=accumout+mat2accum(datatemp);
        end
    end
end

accumleft=accum-accumout;

对于由第一种情况的 5 列和第二种情况的 5 列组成的数据，可以构造一组 100k 行，其中小总和列的总和小于 1k，而大总和列的总和在 10k 到 30k 之间。

值得注意的是，数据的大小、所需子集的大小以及 1 和 -1 的分布都会对该算法的性能产生很大影响。