計算數組中給出最小標準差的子集

讓我們有一個大小爲N的向量。例如：計算數組中給出最小標準差的子集

x = rand(N,1)

我想計算長度K在矢量的子集的最低標準偏差。

當N和K都很小，很容易找到最好的子集，因爲我可以用nchoosek(N,K)列舉所有可能的子集。但是當N和K的值比我們說的N=50和K=25大時，nchoosek無法計算組合，因爲可能子集的大小很大。

我不知道是否有更好的算法來計算給出陣列中最小標準偏差的子集。例如通過動態編程。有任何想法嗎？

更新：

我在一個循環aftter答案實現了它和比較，組合解決方案。結果總是相同，但速度增益是前所未有的。

n = 20; 
k = 10; 
x = rand(n,1); 
C = nchoosek(x, k); 

tic 
mins = realmax; 
for i = 1:size(C,1) 
    s = std(C(i,:)); 
    if s < mins 
     mins = s; 
     bestC = C(i,:); 
    end 
end 
toc 

tic 
[x2, j] = sort(x); 
mins2 = realmax; 
for i = 1:(n-k+1) 
    s = std(x2(i:(i+k-1))); 
    if s < mins2 
     mins2 = s; 
     idx = j((i:(i+k-1))); 
    end 
end 
toc 

if mins == mins2 
    'Equal' 
end

給出

Elapsed time is 7.786579 seconds. 
Elapsed time is 0.002068 seconds. 

ans = 

Equal

來源

2013-11-22 petrichor

排序陣列，然後用軋製長度K的窗口計算此在一次通過。

我相信這會給你正確的答案，會認爲如果我能證明它。

手工波浪捲髮的說法，用在「擴展這個」部分在邏輯上可能的差距：

考慮從你的列表中的元素x。我們試着找出包含這個元素的一組大小爲2的最小標準偏差。我們將通過選擇x和與x最接近的元素來獲得。將其擴展爲k元素，我們將獲得一組包含x的排序列表的連續部分。爲了挑選k元素的最小子集（即，對於任何x），因此我們只需如前所述遍歷排序列表。

來源

2013-11-22 11:33:03 YXD

我認爲你是正確的，我認爲我發佈的解決方案使用'conv'而不是matlab循環（這可能會也可能不會更快）。但我也無法證明這一點。 – Dan

@Dan發佈了一個理由，但我認爲它不完整。 – YXD

這種歸納方法證明，添加最接近的元素會導致波動性的最小增加。然而，它並沒有說它會給你一套規模爲n + 1的波動最小的集合。很明顯，情況並非如此，因爲從異常點開始並不一定要引導您設定最低波動率。這是從每個點開始反駁，但在這裏還沒有證明這是否足夠。 - 直覺上它確實覺得這個答案是對的，所以我會給你我的投票，希望它是正確的。 –

計算數組中給出最小標準差的子集

回答

相關問題