Trouver le meilleur compromis sur une courbe

dans le cas où quelqu'un a besoin d'un travail Python version de la Matlab code posté par Jonas ci-dessus.

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)

La pointe de l'information de théorie de la sélection de modèle est qu'il tient déjà compte du nombre de paramètres. Par conséquent, il n'est pas nécessaire de trouver un coude, il suffit de trouver le minimum.

trouver le coude de la courbe n'est pertinent que lorsqu'on utilise l'ajustement. Même alors, la méthode que vous choisissez de sélectionner le coude est en un sens la définition d'une pénalité pour le nombre de paramètres. Pour sélectionner le coude, vous voulez minimiser la distance de l'origine à l' courbe. La pondération relative des deux dimensions dans le calcul de la distance créera un terme de pénalité inhérent. Information théorique critère de cette métrique basée sur le nombre de paramètres et le nombre d'échantillons de données utilisées pour estimer le modèle.

recommandation fondamentale: utiliser BIC et prendre le minimum.

tout d'abord, un examen de calcul rapide: le premier dérivé f' de chaque graphique représente la vitesse à laquelle la fonction f étant graphique change. Le second dérivé f'' représente le taux auquel f' change. Si f'' est petit, cela signifie que le graphique change de direction à un rythme modeste. Mais si f'' est grand, cela signifie que le graphique change rapidement de direction.

vous voulez isoler le points où f'' est le plus grand sur le domaine du graphique. Ce seront des points candidats à sélectionner pour votre modèle optimal. Quel point vous choisissez devra être à vous, puisque vous n'avez pas précisé exactement combien vous la valeur fitness par rapport à la complexité.

donc une façon de résoudre cela serait deux deux lignes ajustables à la L de votre coude. Mais puisqu'il n'y a que quelques points dans une partie de la courbe (comme je l'ai mentionné dans le commentaire), line fitting prend un coup sauf si vous détectez quels points sont espacés et interpoler entre eux pour fabriquer une série plus uniforme et puis utilisez RANSAC pour trouver deux lignes pour s'adapter à la L - un peu alambiqué mais pas impossible.

donc voici une solution plus simple - les graphiques que vous avez mis en place regardent la façon dont ils font grâce à l'échelle de MATLAB (évidemment). Donc tout ce que j'ai fait c'est minimiser la distance entre "l'origine" et vos points en utilisant les informations de l'échelle.

s'il vous Plaît note: L'origine de l'estimation peut être considérablement améliorée, mais je vais laisser cela à vous.

voici le 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*');

résultats:

aussi pour la courbe Fit(maximize) vous devrez changer l'origine en [x_axis(1) ticks(end)] .

Voici la solution donnée par Jonas mis en œuvre dans 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))
}

d'une manière simple et intuitive nous pouvons dire que

si l'on trace deux lignes à partir d'un point quelconque de la courbe jusqu'aux deux extrémités de la courbe, le point auquel ces deux lignes font le plus petit angle en degrés est le point désiré.

Ici, les deux lignes peuvent être visualisés comme les bras et le point le coude!

la méthode double dérivée. Cela ne semble toutefois pas bien fonctionner pour les données bruyantes. Pour la sortie vous trouvez simplement la valeur maximale de d2 pour identifier le coude. Cette mise en œuvre se trouve au point 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))
}

j'ai travaillé sur la détection des points du genou et du coude pendant un certain temps. En aucun cas, je suis un expert. Quelques méthodes qui peuvent pertinent à ce problème.

DFDT signifie Dynamic First Derivate Threshold. Il calcule la première dérivée et utilise un algorithme de seuil pour détecter le point genou/coude. DSDT est similaire mais utilise le second dérivé, mon évaluation montre qu'ils ont des performances similaires.

S-méthode est une extension de la L-method. La méthode L ajuste deux lignes droites à votre courbe, l'interception entre les deux lignes est le point genou/coude. Le meilleur ajustement est obtenu en bouclant les points globaux, en ajustant les lignes et en évaluant le MSE (erreur carrée moyenne). La méthode S s'adapte à 3 lignes droites, ce qui améliore la précision mais nécessite également un peu plus de calcul.

tout mon code est disponible sur GitHub . De plus, cet article de peut vous aider à trouver plus d'informations sur le sujet. Il ne fait que quatre pages et devrait donc être facile à lire. Vous pouvez utiliser le code, et si vous voulez discuter de l'une des méthodes hésitez pas à le faire.