Den besten Kompromisspunkt auf einer Kurve finden

Sagen, ich hatte einige Daten, die ich will passen Sie einem parametrisierten Modell übernehmen. Mein Ziel ist es, den besten zu finden Wert für dieses Modell-parameter.

Ich mache Modell-Auswahl mit einem AIC/BIC/MDL Kriterium, das belohnt Modelle mit geringer Fehler-aber auch bestraft-Modelle mit hoher Komplexität (wir sind auf der Suche nach der einfachsten, aber am meisten überzeugende Erklärung für diese Daten so zu sprechen, a la Occam ' s razor).

Folgenden obige, dies ist ein Beispiel für die Art von Dingen, die ich für drei verschiedene Kriterien (zwei minimiert werden, und man maximiert werden):

Optisch können Sie leicht sehen, die Ellbogen-Form und Sie würde wählen Sie einen Wert für den parameter irgendwo in dieser region.
Das problem ist, dass ich Tue, tun dies für eine große Anzahl von Experimenten, und ich brauche einen Weg zu finden, diesen Wert ohne intervention.

Meine erste intuition war, zu versuchen, zeichnen Sie eine Linie im 45-Grad-Winkel von der Ecke und halten Sie bewegen Sie es, bis es den Schnittpunkt mit der Kurve, aber das ist leichter gesagt als getan 🙂 es kann Auch das verpassen die region von Interesse, wenn die Kurve ist etwas verzerrt.

Irgendwelche Gedanken auf, wie diese umzusetzen ist, oder bessere Ideen?

Hier die Beispiele benötigt, um zu reproduzieren eines der Grundstücke vor:

curve = [8.4663 8.3457 5.4507 5.3275 4.8305 4.7895 4.6889 4.6833 4.6819 4.6542 4.6501 4.6287 4.6162 4.585 4.5535 4.5134 4.474 4.4089 4.3797 4.3494 4.3268 4.3218 4.3206 4.3206 4.3203 4.2975 4.2864 4.2821 4.2544 4.2288 4.2281 4.2265 4.2226 4.2206 4.2146 4.2144 4.2114 4.1923 4.19 4.1894 4.1785 4.178 4.1694 4.1694 4.1694 4.1556 4.1498 4.1498 4.1357 4.1222 4.1222 4.1217 4.1192 4.1178 4.1139 4.1135 4.1125 4.1035 4.1025 4.1023 4.0971 4.0969 4.0915 4.0915 4.0914 4.0836 4.0804 4.0803 4.0722 4.065 4.065 4.0649 4.0644 4.0637 4.0616 4.0616 4.061 4.0572 4.0563 4.056 4.0545 4.0545 4.0522 4.0519 4.0514 4.0484 4.0467 4.0463 4.0422 4.0392 4.0388 4.0385 4.0385 4.0383 4.038 4.0379 4.0375 4.0364 4.0353 4.0344];
plot(1:100, curve)

BEARBEITEN

Nahm ich die Lösung gegeben durch Jonas. Im Grunde für jeden Punkt p auf der Kurve, finden wir das eine mit dem maximalen Abstand d gegeben durch:

Den besten Kompromisspunkt auf einer Kurve finden

InformationsquelleAutor der Frage Amro | 2010-01-07

Einen schnellen Weg zu finden, der Ellenbogen ist eine Linie zu ziehen von der ersten bis zu letzten Punkt der Kurve und dann finden die Daten zeigen, dass am weitesten entfernt ist von dieser Linie.

Dies ist natürlich etwas abhängig von der Anzahl der Punkte, die Sie in den flachen Teil der Strecke, aber wenn Sie testen Sie die gleiche Anzahl der Parameter jedes mal, es kommen sollte einigermaßen ok.

curve = [8.4663 8.3457 5.4507 5.3275 4.8305 4.7895 4.6889 4.6833 4.6819 4.6542 4.6501 4.6287 4.6162 4.585 4.5535 4.5134 4.474 4.4089 4.3797 4.3494 4.3268 4.3218 4.3206 4.3206 4.3203 4.2975 4.2864 4.2821 4.2544 4.2288 4.2281 4.2265 4.2226 4.2206 4.2146 4.2144 4.2114 4.1923 4.19 4.1894 4.1785 4.178 4.1694 4.1694 4.1694 4.1556 4.1498 4.1498 4.1357 4.1222 4.1222 4.1217 4.1192 4.1178 4.1139 4.1135 4.1125 4.1035 4.1025 4.1023 4.0971 4.0969 4.0915 4.0915 4.0914 4.0836 4.0804 4.0803 4.0722 4.065 4.065 4.0649 4.0644 4.0637 4.0616 4.0616 4.061 4.0572 4.0563 4.056 4.0545 4.0545 4.0522 4.0519 4.0514 4.0484 4.0467 4.0463 4.0422 4.0392 4.0388 4.0385 4.0385 4.0383 4.038 4.0379 4.0375 4.0364 4.0353 4.0344];

%# get coordinates of all the points
nPoints = length(curve);
allCoord = [1:nPoints;curve]';              %'# SO formatting

%# pull out first point
firstPoint = allCoord(1,:);

%# get vector between first and last point - this is the line
lineVec = allCoord(end,:) - firstPoint;

%# normalize the line vector
lineVecN = lineVec / sqrt(sum(lineVec.^2));

%# find the distance from each point to the line:
%# vector between all points and first point
vecFromFirst = bsxfun(@minus, allCoord, firstPoint);

%# To calculate the distance to the line, we split vecFromFirst into two 
%# components, one that is parallel to the line and one that is perpendicular 
%# Then, we take the norm of the part that is perpendicular to the line and 
%# get the distance.
%# We find the vector parallel to the line by projecting vecFromFirst onto 
%# the line. The perpendicular vector is vecFromFirst - vecFromFirstParallel
%# We project vecFromFirst by taking the scalar product of the vector with 
%# the unit vector that points in the direction of the line (this gives us 
%# the length of the projection of vecFromFirst onto the line). If we 
%# multiply the scalar product by the unit vector, we have vecFromFirstParallel
scalarProduct = dot(vecFromFirst, repmat(lineVecN,nPoints,1), 2);
vecFromFirstParallel = scalarProduct * lineVecN;
vecToLine = vecFromFirst - vecFromFirstParallel;

%# distance to line is the norm of vecToLine
distToLine = sqrt(sum(vecToLine.^2,2));

%# plot the distance to the line
figure('Name','distance from curve to line'), plot(distToLine)

%# now all you need is to find the maximum
[maxDist,idxOfBestPoint] = max(distToLine);

%# plot
figure, plot(curve)
hold on
plot(allCoord(idxOfBestPoint,1), allCoord(idxOfBestPoint,2), 'or')

InformationsquelleAutor der Antwort Jonas

Den Fall, dass jemand braucht ein funktionierendes Python version des Matlab code geschrieben von Jonas oben.

import numpy as np
curve = [8.4663, 8.3457, 5.4507, 5.3275, 4.8305, 4.7895, 4.6889, 4.6833, 4.6819, 4.6542, 4.6501, 4.6287, 4.6162, 4.585, 4.5535, 4.5134, 4.474, 4.4089, 4.3797, 4.3494, 4.3268, 4.3218, 4.3206, 4.3206, 4.3203, 4.2975, 4.2864, 4.2821, 4.2544, 4.2288, 4.2281, 4.2265, 4.2226, 4.2206, 4.2146, 4.2144, 4.2114, 4.1923, 4.19, 4.1894, 4.1785, 4.178, 4.1694, 4.1694, 4.1694, 4.1556, 4.1498, 4.1498, 4.1357, 4.1222, 4.1222, 4.1217, 4.1192, 4.1178, 4.1139, 4.1135, 4.1125, 4.1035, 4.1025, 4.1023, 4.0971, 4.0969, 4.0915, 4.0915, 4.0914, 4.0836, 4.0804, 4.0803, 4.0722, 4.065, 4.065, 4.0649, 4.0644, 4.0637, 4.0616, 4.0616, 4.061, 4.0572, 4.0563, 4.056, 4.0545, 4.0545, 4.0522, 4.0519, 4.0514, 4.0484, 4.0467, 4.0463, 4.0422, 4.0392, 4.0388, 4.0385, 4.0385, 4.0383, 4.038, 4.0379, 4.0375, 4.0364, 4.0353, 4.0344]
nPoints = len(curve)
allCoord = np.vstack((range(nPoints), curve)).T
np.array([range(nPoints), curve])
firstPoint = allCoord[0]
lineVec = allCoord[-1] - allCoord[0]
lineVecNorm = lineVec / np.sqrt(np.sum(lineVec**2))
vecFromFirst = allCoord - firstPoint
scalarProduct = np.sum(vecFromFirst * np.matlib.repmat(lineVecNorm, nPoints, 1), axis=1)
vecFromFirstParallel = np.outer(scalarProduct, lineVecNorm)
vecToLine = vecFromFirst - vecFromFirstParallel
distToLine = np.sqrt(np.sum(vecToLine ** 2, axis=1))
idxOfBestPoint = np.argmax(distToLine)

InformationsquelleAutor der Antwort rafaelvalle

8

Den point-of-information theoretischen Modell-Auswahl ist, dass es bereits Konten für die Anzahl der Parameter. Daher gibt es keine Notwendigkeit zu finden, ein Ellbogen, Sie brauchen nur zu finden, die minimale.

Finden die Ellenbogen der Kurve ist nur dann relevant, wenn mit fit. Auch dann ist die Methode, die Sie wählen, der Ellbogen ist in einem gewissen Sinne die Einstellung eine Strafe für die Anzahl der Parameter. Wählen Sie die Ellbogen Sie möchten, minimieren Sie den Abstand vom Ursprung an die Kurve. Die relative Gewichtung der beiden Dimensionen in der Distanz-Berechnung erstellen, die eine inhärente Strafe Begriff. Informationen theoretische Kriterium setzen diese Metrik basiert auf der Anzahl der Parameter und die Anzahl der Stichproben von Daten verwendet, um die Schätzung des Modells.

Bottom-line-Empfehlung: Nutzen Sie den BIC und das minimum.

InformationsquelleAutor der Antwort KennyMorton
7

Erste, eine schnelle Rechnung abgeben: die erste Ableitung f' jeder graph repräsentiert die rate, mit der die Funktion f wird grafisch dargestellt ändert. Die zweite Ableitung f'' repräsentiert die rate, mit der f' verändert. Wenn f'' klein ist, bedeutet dies, dass der graph die Richtung ändern zu einem bescheidenen Tempo. Aber wenn f'' ist groß, es bedeutet, der graph ist schnell die Richtung ändern.

Sie isolieren möchten die Punkte, an denen f'' größten ist, über die domain des Graphen. Diese werden dem Bewerber Punkte auswählen, die für Ihr optimales Modell. Die Stelle, die Sie wählen werden müssen, weil man noch nicht genau festgelegt, wie viel Sie Wert auf fitness versus Komplexität.

InformationsquelleAutor der Antwort John Feminella

Also eine Möglichkeit, dies zu lösen wäre zwei passen zwei Zeilen, um die L von Ihrem Ellenbogen. Aber da gibt es nur einige wenige Punkte, die in einem Teil der Kurve (wie ich bereits im Kommentar), line-Beschlag nimmt einen Treffer, es sei denn, Sie erkennen die Punkte verteilt werden und interpolieren zwischen diesen, zur Herstellung einer einheitlichen Serie und dann verwenden RANSAC zu finden, die zwei Zeilen passen die L - ein wenig verworren, aber nicht unmöglich.

So, hier ist eine einfachere Lösung - die Grafiken, die Sie haben sehen so aus, wie Sie Dank der MATLAB - Skalierung (offensichtlich). Also alles, was ich Tat, war die Minimierung der Distanz aus dem "origin", um Ihre Punkte anhand der Skala Informationen.

Bitte beachten Sie: Der Ursprung Einschätzung kann dramatisch verbessert, aber das überlasse ich Ihnen.

Hier der code:

%% Order
curve = [8.4663 8.3457 5.4507 5.3275 4.8305 4.7895 4.6889 4.6833 4.6819 4.6542 4.6501 4.6287 4.6162 4.585 4.5535 4.5134 4.474 4.4089 4.3797 4.3494 4.3268 4.3218 4.3206 4.3206 4.3203 4.2975 4.2864 4.2821 4.2544 4.2288 4.2281 4.2265 4.2226 4.2206 4.2146 4.2144 4.2114 4.1923 4.19 4.1894 4.1785 4.178 4.1694 4.1694 4.1694 4.1556 4.1498 4.1498 4.1357 4.1222 4.1222 4.1217 4.1192 4.1178 4.1139 4.1135 4.1125 4.1035 4.1025 4.1023 4.0971 4.0969 4.0915 4.0915 4.0914 4.0836 4.0804 4.0803 4.0722 4.065 4.065 4.0649 4.0644 4.0637 4.0616 4.0616 4.061 4.0572 4.0563 4.056 4.0545 4.0545 4.0522 4.0519 4.0514 4.0484 4.0467 4.0463 4.0422 4.0392 4.0388 4.0385 4.0385 4.0383 4.038 4.0379 4.0375 4.0364 4.0353 4.0344];
x_axis = 1:numel(curve);
points = [x_axis ; curve ]'; %' - SO formatting

%% Get the scaling info
f = figure(1);
plot(points(:,1),points(:,2));
ticks = get(get(f,'CurrentAxes'),'YTickLabel');
ticks = str2num(ticks);
aspect = get(get(f,'CurrentAxes'),'DataAspectRatio');
aspect = [aspect(2) aspect(1)];    
close(f);   

%% Get the "origin"
O = [x_axis(1) ticks(1)];

%% Scale the data - now the scaled values look like MATLAB''s idea of
% what a good plot should look like
scaled_O = O.*aspect;
scaled_points = bsxfun(@times,points,aspect);

%% Find the closest point
del = sum((bsxfun(@minus,scaled_points,scaled_O).^2),2);
[val ind] = min(del);
best_ROC = [ind curve(ind)];

%% Display
plot(x_axis,curve,'.-');
hold on;
plot(O(1),O(2),'r*');
plot(best_ROC(1),best_ROC(2),'k*');

Ergebnisse:

Den besten Kompromisspunkt auf einer Kurve finden

AUCH für die Fit(maximize) Kurve, die Sie ändern müssen, um die Herkunft zu [x_axis(1) ticks(end)].

InformationsquelleAutor der Antwort Jacob

Hier ist die Lösung gegeben durch Jonas implementiert in R:

elbow_finder <- function(x_values, y_values) {
  # Max values to create line
  max_x_x <- max(x_values)
  max_x_y <- y_values[which.max(x_values)]
  max_y_y <- max(y_values)
  max_y_x <- x_values[which.max(y_values)]
  max_df <- data.frame(x = c(max_y_x, max_x_x), y = c(max_y_y, max_x_y))

  # Creating straight line between the max values
  fit <- lm(max_df$y ~ max_df$x)

  # Distance from point to line
  distances <- c()
  for(i in 1:length(x_values)) {
    distances <- c(distances, abs(coef(fit)[2]*x_values[i] - y_values[i] + coef(fit)[1]) / sqrt(coef(fit)[2]^2 + 1^2))
  }

  # Max distance point
  x_max_dist <- x_values[which.max(distances)]
  y_max_dist <- y_values[which.max(distances)]

  return(c(x_max_dist, y_max_dist))
}

InformationsquelleAutor der Antwort Esben Eickhardt

2

In eine einfache und intuitive Art und Weise können wir sagen, dass

Wenn wir zeichnen Sie zwei Linien von jedem Punkt auf der Kurve, um die beiden Endpunkte der Kurve, der Punkt, an dem diese beiden Linien, die den kleinsten Winkel in Grad ist die gewünschte Stelle.

Hier, die beiden Linien können visualisiert werden, da die Arme und der Punkt als den Punkt des Ellenbogens!

InformationsquelleAutor der Antwort cHaTrU

Den doppelt abgeleiteten Methode. Es ist aber nicht zu funktionieren scheinen, auch bei verrauschten Daten. Für die Ausgabe, die Sie einfach finden Sie den maximalen Wert von d2 zu identifizieren, die Ellenbogen. Diese Implementierung ist in R.

elbow_finder <- function(x_values, y_values) {
  i_max <- length(x_values) - 1

  # First and second derived
  first_derived <- list()
  second_derived <- list()

  # First derived
  for(i in 2:i_max){
    slope1 <- (y_values[i+1] - y_values[i]) / (x_values[i+1] - x_values[i])
    slope2 <- (y_values[i] - y_values[i-1]) / (x_values[i] - x_values[i-1])
    slope_avg <- (slope1 + slope2) / 2
    first_derived[[i]] <- slope_avg 
  }
  first_derived[[1]] <- NA
  first_derived[[i_max+1]] <- NA
  first_derived <- unlist(first_derived)

  # Second derived
  for(i in 3:i_max-1){
    d1 <- (first_derived[i+1] - first_derived[i]) / (x_values[i+1] - x_values[i])
    d2 <- (first_derived[i] - first_derived[i-1]) / (x_values[i] - x_values[i-1])
    d_avg <- (d1 + d2) / 2
    second_derived[[i]] <- d_avg 
  }
  second_derived[[1]] <- NA
  second_derived[[2]] <- NA
  second_derived[[i_max]] <- NA
  second_derived[[i_max+1]] <- NA
  second_derived <- unlist(second_derived)

  return(list(d1 = first_derived, d2 = second_derived))
}

InformationsquelleAutor der Antwort Esben Eickhardt

0

Tummle ich mich auf Knie - /Ellenbogen-point-Erkennung für einige Zeit. Keineswegs bin ich ein Experte.
Einige Methoden, die für dieses problem relevant sind.

DFDT steht für Dynamisches Erste Derivat Schwelle. Es berechnet die erste Ableitung und setzt ein Thresholding Algorithmus zur Erkennung der Knie - /Ellbogen-Punkt. DSDT ist ähnlich, benutzt aber die zweite Ableitung, meine Bewertung zeigt, dass Sie ähnliche Leistungen.

S-Methode ist eine Erweiterung der L-Methode. Die L-Methode eignet sich für zwei geraden zu Kurve, dem abfangen, die zwischen den beiden Linien ist die Knie - /Ellbogen-Punkt. Der beste fit wird gefunden, indem die Schleife insgesamt Punkte, die Montage der Linien und Bewertung der MSE (Mean Square Error). Die S-Methode passt 3 gerade Linien, dies verbessert die Genauigkeit, aber erfordert auch etwas mehr Rechenzeit.

Alle mein code ist öffentlich verfügbar auf GitHub. Darüber hinaus ist dieses Artikel kann Ihnen helfen, mehr Informationen über das Thema. Es ist nur vier Seiten lang, so ist es sollte leicht zu Lesen sein. Sie können den code verwenden, und wenn Sie wollen, zu diskutieren, keine der Methoden fühlen Sie sich frei, dies zu tun.

InformationsquelleAutor der Antwort mariolpantunes

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.