Minimieren Sie die Varianz python

Question

Nicht sicher, wie Sie damit fortfahren. Ich habe eine Liste von Zahlen (eine Liste von Listen von Zahlen, um genau zu sein), aber diese Zahl haben eine Zweideutigkeit: x, x + 1 und x-1 sind genau das gleiche für mich. Ich möchte jedoch die Varianz der Liste minimieren, indem ich die Elemente ändere. Hier ist, was ich dachte bisher (mit einer Probe-Liste, die ich weiß, dass es nicht funktioniert):

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 

Was die Funktion macht hinzufügen 1 bis 3. Element. Die minimale Varianz tritt jedoch auf, wenn Sie 1 vom 4. und 5. subtrahieren. Dies geschieht, weil ich die Varianz nach jedem Element minimiere und nicht mehrere Änderungen zulasse. Wie könnte ich mehrere Änderungen implementieren, vorzugsweise ohne alle möglichen Lösungen zu betrachten (3 ** n wenn ich mich nicht irre)? Vielen Dank

Answer 1

Sie dies als Problem betrachten können die delta zu finden, die var((x + delta) % 1) wo x Ihre Array von Werten minimiert. Dann addieren und subtrahieren Sie ganze Zahlen von Ihren Werten, bis sie im Bereich delta - 1 <= x[i] < delta liegen. Dies ist keine kontinuierliche Funktion von delta, Sie können also keine Solver wie in scipy.optimize verwenden. Aber wir können die Information verwenden, dass sich der Wert von var((x + delta) % 1) nur bei jedem Wert von x ändert, was bedeutet, dass wir nur jeden Wert in x als möglich delta testen müssen und einen finden, der die Varianz minimiert.

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) 

Für dieses Beispiel findet es Ihre gewünschte Lösung von [ 0.474 0.122 0.0867 -0.104 -0.021 ] mit einer Varianz von 0.0392.

Answer 2

die neue var jedes Mal die Berechnung zu vermeiden (O (n²)) können Sie sehen, dass, wenn Sie ein Element x-x+u beeinflussen, wird die var wie u*(u/2+x-m-u/n) betroffen.

So, hier ist eine quasi-lineare Zeit Lösung:

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)) 

und der Lauf:

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