分散を最小化するpython

Question

これを進める方法がわかりません。私は数字のリスト（正確な数字のリスト）を持っていますが、これらの数字にはあいまいさがあります.x、x + 1、x-1はまったく同じものです。しかし、私は要素の変更によってリストの分散を最小限に抑えたいと思います。ここで私は（私はそれが動作しません知っているサンプルリストで）これまでに考えたものだ：

import numpy as np 
from scipy import stats 

lst = [0.474, 0.122, 0.0867, 0.896, 0.979] 
def min_var(lst): 
    mode = np.mean(lst) 
    var = np.var(lst) 
    result = [] 
    for item in list(lst): 
     if item < mean: # not sure this is a good test 
      new_item = item + 1 
     elif item > mean: 
      new_item = item - 1 
     else: 
      new_item = item 
     new_list = [new_item if x==item else x for x in lst] 
     new_var = np.var(new_list) 
     if new_var < var: 
      var = new_var 
      lst = new_list 
    return lst 

何の機能がないことは第三の要素に1を追加することです。ただし、最小分散は、4と5から1を引いたときに発生します。これは、各項目の後の分散を最小限に抑え、複数の変更を許可しないために発生します。どのように私は複数の変更を実装することができます（可能であればすべての解決策を見ることなく）（3 ** n私は間違っていない場合）？ ありがとうございました

Answer 1

var((x + delta) % 1)xあなたの値の配列を最小にするdeltaを見つける問題としてこれを考えることができます。次に、数値が0から255の範囲に入るまで、数値を加算して減算します。これはdeltaの連続関数ではないため、scipy.optimizeのようなソルバーを使用することはできません。しかし、var((x + delta) % 1)の値がxの各値でのみ変化するという情報を使うことができます。つまり、xの各値をdeltaとしてテストし、分散を最小にする必要があるだけです。この例では

import numpy as np 

x = np.array([0.474, 0.122, 0.0867, 0.896, 0.979]) 

# find the value of delta 
delta = x[0] 
min_var = np.var((x - delta) % 1) 
for val in x: 
    current_var = np.var((x - val) % 1) 
    if current_var < min_var: 
     min_var = current_var 
     delta = val 

print(delta) 

# use `delta` to subtract and add the right integer from each value 
# we want values in the range delta - 1 <= val < delta 
for i, val in enumerate(x): 
    while val >= delta: 
     val -= 1. 
    while val < delta - 1.: 
     val += 1. 
    x[i] = val 

print(x) 

、それは0.0392の分散と[ 0.474 0.122 0.0867 -0.104 -0.021 ]のご希望のソリューションを見つけました。

Answer 2

毎回新しい変数（O（n²））を計算しないようにするには、x〜x+uのアイテムに影響すると、varはu*(u/2+x-m-u/n)のように影響を受けることがわかります。

l=np.array([0.474, 0.122, 0.0867, 0.896, 0.979]) 
l.sort() 
n=len(l) 
m=np.mean(l) 
print(l,np.var(l)) 
u=1 # increase little terms 

for i in range(n): 
    if u*(u/2+l[i]-m-u/n) < 0: 
     l[i]= l[i] + u 
     m = m+u/n # mean evolution 
    else: u = -1 # decrease big terms 

print(l,np.var(l)) 

と実行：だからここ

は準線形時間ソリューションです

[ 0.0867 0.122 0.474 0.896 0.979 ] 0.1399936064 
[ 1.0867 1.122 1.474 0.896 0.979 ] 0.0392256064