2017-03-28 7 views
4

Angenommen, ich habe zwei Arrays, die die x- und y-Koordinaten einer Kalibrierungskurve angeben."Sinnvoll" Punkte in einer Python-Liste entfernen

X = [1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,30,40,50] 
Y = [2,4,6,8,10,12,14,16,18,20,24,28,32,36,40,60,80,100] 

Meine Beispiel-Arrays oben enthalten 18 Punkte. Sie werden feststellen, dass die x-Werte nicht linear beabstandet sind. es gibt mehr Punkte bei niedrigeren Werten von x.

Nehmen wir an, ich muss die Anzahl der Punkte in meiner Kalibrierungskurve auf 13 Punkte reduzieren. Natürlich könnte ich nur die ersten fünf oder die letzten fünf Punkte entfernen, aber das würde meinen gesamten Bereich von x-Werten verkürzen. Um den Bereich beizubehalten und den Abstand zwischen x-Werten zu minimieren, würde ich vorzugsweise die Werte x = 2,4,6,8,10 entfernen. Das Entfernen dieser x-Punkte und ihrer jeweiligen y-Werte würde 13 Punkte in der Kurve nach Bedarf lassen.

Wie kann ich diese Punktauswahl und -entfernung automatisch in Python vornehmen? I.e. Gibt es einen Algorithmus, um die besten x Punkte aus einer Liste auszuwählen, wobei "am besten" definiert ist, die Punkte so nahe wie möglich zu halten, während der Gesamtbereich beibehalten wird und die neue Anzahl von Punkten eingehalten wird.

Bitte beachten Sie, dass die verbleibenden Punkte in den ursprünglichen Listen sein müssen, so dass ich die 18 Punkte auf einem Raster mit 13 Punkten nicht interpolieren kann.

+0

Entschuldigung - Ich habe meine ursprüngliche Frage bearbeitet, um (hoffentlich!) Dinge zu klären. Grundsätzlich möchte ich die Anzahl der Werte reduzieren, aber über den gesamten Bereich halten (d. H. Min x und max x). Um dies zu erreichen, möchte ich naheliegende Punkte entfernen – Mark

Antwort

1
X = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 30, 40, 50] 
Y = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 24, 28, 32, 36, 40, 60, 80, 100] 

assert len(X) == len(set(X)), "Duplicate X values found" 

points = list(zip(X, Y)) 
points.sort() # sorts by X 

while len(points) > 13: 
    # Find index whose neighbouring X values are closest together 
    i = min(range(1, len(points) - 1), key=lambda p: points[p + 1][0] - points[p - 1][0]) 
    points.pop(i) 

print(points) 

Ausgang:

[(1, 2), (3, 6), (5, 10), (7, 14), (10, 20), (12, 24), (14, 28), (16, 32), (18, 36), (20, 40), (30, 60), (40, 80), (50, 100)] 

Wenn Sie die Original-Serie wollen wieder:

X, Y = zip(*points) 
0

Ein Algorithmus, der das erreichen würde:

  1. konvertieren jede Zahl in die Summe der absoluten Differenz der Anzahl nach links und nach rechts. Wenn eine Nummer fehlt, erster oder letzter Fall, verwenden Sie MAX_INT. Zum Beispiel würde 1 MAX_INT werden; 2 würde 2 werden, 10 würde 3 werden.
  2. Entfernen Sie den ersten Fall mit der niedrigsten Summe.
  3. Wenn Sie benötigen, um weitere Nummern zu entfernen, gehen Sie zu 1.

Diese 2,4,6,8,10,3 entfernen würde, ...

0

Hier ist ein rekursive Ansatz, den Punkt wiederholt entfernt, die die am wenigsten verfehlt werden:

def mostRedundantPoint(x): 
    #returns the index, i, in the range 0 < i < len(x) - 1 
    #that minimizes x[i+1] - x[i-1] 
    #assumes len(x) > 2 and that x 
    #is sorted in ascending order 

    gaps = [x[i+1] - x[i-1] for i in range(1,len(x)-1)] 
    i = gaps.index(min(gaps)) 
    return i+1 

def reduceList(x,k): 
    if len(x) <= k: 
     return x 
    else: 
     i = mostRedundantPoint(x) 
     return reduceList(x[:i]+x[i+1:],k) 

X = [1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,30,40,50] 
print(reduceList(X,13)) 
#prints [1, 3, 5, 7, 10, 12, 14, 16, 18, 20, 30, 40, 50] 

Diese Liste im Wesentlichen übereinstimmt mit Ihrer beabsichtigten Ausgabe seit 7 vs. 8 den gleichen Netto-Effekt. Es ist relativ schnell in dem Sinne, dass es fast augenblicklich ist, sorted([random.randint(1,10**6) for i in range(1000)]) von 1000 Elementen auf 100 Elemente zu reduzieren. Die Tatsache, dass es rekursiv ist, impliziert, dass es den Stack sprengen wird, wenn Sie versuchen, mehr Punkte als das zu entfernen, aber mit dem, was Ihre beabsichtigte Problemgröße zu sein scheint, sollte das kein Problem sein. Bei Bedarf könnten Sie die Rekursion natürlich durch eine Schleife ersetzen.

3

Dies würde die Quadratwurzelabstände zwischen den ausgewählten Punkten maximieren. In gewissem Sinne verbreitet es die Punkte so weit wie möglich.

import itertools 
list(max(itertools.combinations(sorted(X), 13), i 
     key=lambda l: sum((a - b) ** 2 for a, b in zip(l, l[1:])))) 

Beachten Sie, dass dies nur für kleine Probleme möglich ist. Die Zeitkomplexität zum Auswählen von k Punkten ist O(k * (len(X) choose k)), also im Wesentlichen O(exp(len(X)).Denken Sie also nicht einmal darüber nach, dies beispielsweise für len(X) == 100 und k == 10 zu verwenden.

+1

Das ist eine sehr schlaue Idee mit einer intuitiven Motivation, also +1. Für die gegebene Problemgröße wird es gut funktionieren, obwohl es natürlich schnell unbrauchbar wird, wenn 18 viel größer wird. Ich bin mir nicht sicher, wie Sie das in solchen Fällen berechnen würden. Vielleicht würde ein Hill-Climbing-Ansatz funktionieren oder zumindest eine vernünftige Heuristik bieten. –

+0

Natürlich hast du recht. Ich habe der Antwort eine Notiz hinzugefügt. –

+0

Es ist immer noch ein gutes Kriterium, auch für die 100, 10 Fall. Du brauchst nur einen nicht-brutalen Weg, um es zu finden, oder, wenn es das nicht schafft, approximiere es zumindest. –

Verwandte Themen