Minimierung der Fehlersumme der repräsentativen ganzen Zahlen

Question

Bei n ganzen Zahlen zwischen [0,10000] als D ₁ ,D ₂ ...,D _n , wobei es Duplikate geben kann und n sehr groß sein kann:

Ich möchte k verschiedene repräsentative ganze Zahlen (zum Beispiel k=5) zwischen [0,10000] als R ₁ ,R ₂ ,...,R _k , so dass die Summe der Fehler aller repräsentativen ganzen Zahlen minimiert wird.

Der Fehler einer repräsentativen ganzen Zahl wird im Folgenden definiert:

Angenommen, wir haben k repräsentative ganze Zahlen in aufsteigender Reihenfolge als {R ₁ ,R ₂ ...,R _k }, der Fehler von R _i ist:

und ich möchte die Summe der Fehler der k repräsentativen ganzen Zahlen minimieren:

Wie kann dies effizient durchgeführt werden?

EDIT1: Die kleinste der k repräsentativen ganzen Zahlen muss die kleinste Zahl in {D ₁ ,D ₂ ...,D _n }

EDIT2: Die größte der k repräsentativen ganzen Zahlen muss die größte Zahl in {D ₁ ,D ₂ ...,D _n } plus 1. Wenn zum Beispiel die größte Zahl in {D ₁ ,D ₂ ...,D _n } 9787 ist, dann ist R _k ist 9788.

EDIT3: Ein konkretes Beispiel finden Sie hier:

D={1,3,3,7,8,14,14,14,30} und wenn k=5 und R als {1,6,10,17,31} gewählt wird, dann ist die Summe der Fehler :

Summe der Fehler=(1-1)+(3-1)*2+(7-6)+(8-6)+(14-10)*3+(30-17)=32

Dies liegt daran, dass 1<=1,3,3<6 , 6<=7,8<10, 10<=14,14,14<17, 17<=30<31

Answer 1

Diese es ist ähnlich wie eindimensional k -Medien-Clustering .

Das von mir vorgeschlagene DP wird nicht funktionieren; ich denke, wir brauchen eine Tabelle von (n', k', i) zur optimalen Lösung auf D ₁ D _n' mit k' Repräsentanten, von denen der größte i ist. Angesichts der Schranken für D liegt die Laufzeit in der Größenordnung von n 2 k mit einer sehr großen Konstante, so dass man wahrscheinlich eine der Heuristiken anpassen sollte, die man für k -Bedeutung.

Answer 2

Vielleicht möchten Sie sich informieren über Ward'sche Methode unter Verwendung Ihrer speziellen Distanzfunktion.

Answer 3

Ein erster offensichtlicher Punkt ist, dass Ihre Rs unter Ihren Ds ausgewählt werden müssen. (wenn du ein R wählst, das ein beliebiges D - 1 ist (aber kein anderes D), verbesserst du die Antwort, indem du dein R um 1 erhöhst)

ein zweiter Punkt ist, dass Ihr letztes R nutzlos ist und sein Fehler immer 0 sein wird