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

函数的作用是将第 3 个元素加 1。但是，当您从第 4 位和第 5 位减去 1 时，会出现最小方差。发生这种情况是因为我在每个项目之后最小化方差，不允许进行多次更改。我怎样才能实施多项更改，最好不要查看所有可能的解决方案（如果我没记错的话是 3**n）？非常感谢

Answer 1

您可以将此视为找到最小化 var((x + delta) % 1) 的 delta 的问题，其中 x 您的值数组。然后从您的值中添加和减去整数，直到它们位于 delta - 1 <= x[i] < delta 范围内。这不是 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.474 0.122 0.0867 -0.104 -0.021 ] 解，方差为 0.0392。

Answer 2

为了避免每次都计算新的变量（O(n²)），你可以看到当你影响一个从x到x+u的项目时，变量被影响为[=14] =].

所以这是一个准线性时间解：

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

最小化方差 python

Minimize variance python

python

variance

minimization