數學問題：縮放圖形，使其與另一個匹配

我有兩個值表，並且想要縮放第一個圖表，以便它儘可能匹配第二個圖表。兩者長度相同。如果兩者在圖表中都以圖表形式繪製，則應儘可能彼此接近。但我不想要二次的，但簡單的線性權重。我的問題是，我不知道如何實際計算最佳比例因子，因爲Abs函數。數學問題：縮放圖形，使其與另一個匹配

一些僞代碼：

//given: 
float[] table1= ...; 
float[] table2= ...; 

//wanted: 
float factor= ???; // I have no idea how to compute this 

float remainingDifference=0; 
for(int i=0; i<length; i++) 
{ 
    float scaledValue=table1[i] * factor; 
    //Sum up the differences. I use the Abs function because negative differences are differences too. 
    remainingDifference += Abs(scaledValue - table2[i]); 
}

我想計算的比例係數，這樣的remainingDifference是最小的。

來源

2011-07-22 Zotta

如果任何人在未來絆倒在此，這裏是一些代碼（C++）訣竅是首先按比例因子對樣本進行排序，這樣可以使每個樣本最適合2個樣本。然後從兩端開始迭代到導致最小絕對偏差（L1-範數）的因子。除了排序

一切有線性運行時間=>運行時爲O（n * log n）的

/* 
* Find x so that the sum over std::abs(pA[i]-pB[i]*x) from i=0 to (n-1) is minimal 
* Then return x 
*/ 
float linearFit(const float* pA, const float* pB, int n) 
{ 
    /* 
    * Algebraic solution is not possible for the general case 
    * => iterative algorithm 
    */ 

    if (n < 0) 
     throw "linearFit has invalid argument: expected n >= 0"; 
    if (n == 0) 
     return 0;//If there is nothing to fit, any factor is a perfect fit (sum is always 0) 
    if (n == 1) 
     return pA[0]/pB[0];//return x so that pA[0] = pB[0]*x 

    //If you don't like this , use a std::vector :P 
    std::unique_ptr<float[]> targetValues_(new float[n]); 
    std::unique_ptr<int[]> indices_(new int[n]); 
    //Get proper pointers: 
    float* targetValues = targetValues_.get();//The value for x that would cause pA[i] = pB[i]*x 
    int* indices  = indices_.get();  //Indices of useful (not nan and not infinity) target values 
    //The code above guarantees n > 1, so it is safe to get these pointers: 
    int m = 0;//Number of useful target values 
    for (int i = 0; i < n; i++) 
    { 
     float a = pA[i]; 
     float b = pB[i]; 
     float targetValue = a/b; 
     targetValues[i] = targetValue; 
     if (std::isfinite(targetValue)) 
     { 
      indices[m++] = i; 
     } 
    } 
    if (m <= 0) 
     return 0; 
    if (m == 1) 
     return targetValues[indices[0]];//If there is only one target value, then it has to be the best one. 

    //sort the indices by target value 
    std::sort(indices, indices + m, [&](int ia, int ib){ 
     return targetValues[ia] < targetValues[ib]; 
    }); 

    //Start from the extremes and meet at the optimal solution somewhere in the middle: 
    int l = 0; 
    int r = m - 1; 

    // m >= 2 is guaranteed => l > r 
    float penaltyFactorL = std::abs(pB[indices[l]]); 
    float penaltyFactorR = std::abs(pB[indices[r]]); 
    while (l < r) 
    { 
     if (l == r - 1 && penaltyFactorL == penaltyFactorR) 
     { 
      break; 
     } 
     if (penaltyFactorL < penaltyFactorR) 
     { 
      l++; 
      if (l < r) 
      { 
       penaltyFactorL += std::abs(pB[indices[l]]); 
      } 
     } 
     else 
     { 
      r--; 
      if (l < r) 
      { 
       penaltyFactorR += std::abs(pB[indices[r]]); 
      } 
     } 
    } 

    //return the best target value 
    if (l == r) 
     return targetValues[indices[l]]; 
    else 
     return (targetValues[indices[l]] + targetValues[indices[r]])*0.5; 
}

來源

2014-11-15 21:14:32 Zotta

簡單的線性重量很難像你說的。

a_n = first sequence 
b_n = second sequence 
c = scaling factor

你的殘餘功能是（總和是從i = 1到N，點的數量）：以衍生物對於C產量

SUM(|a_i - c*b_i|)

：

d/dc SUM(|a_i - c*b_i|) 
= SUM(b_i * (a_i - c*b_i)/|a_i - c*b_i|)

設置爲0並解決c是困難的。我不認爲有這樣做的分析方法。你可能想嘗試https://math.stackexchange.com/看看他們是否有任何明智的想法。

不過，如果你有二次權重的工作，就變成顯著簡單：

d/dc SUM((a_i - c*b_i)^2) 
= SUM(2*(a_i - c*b_i)* -c) 
= -2c * SUM(a_i - c*b_i) = 0 
=> SUM(a_i) - c*SUM(b_i) = 0 
=> c = SUM(a_i)/SUM(b_i)

如果可以的話，我強烈建議後者的做法。

來源

2011-07-22 13:27:27 tskuzzy

1。實際上，對於最小絕對偏差迴歸沒有解析方法。在這種情況下，使用（非常簡單！）最小二乘法最可能是最好的方法。另請參閱：http://en.wikipedia.org/wiki/Least_absolute_deviations#Solving_Methods –

感謝您的參考！試圖找出一個解決方案，但想不出比迭代方法更好的東西。現在我知道爲什麼:) – tskuzzy

+1。我已經結束了非常類似的表述。據我所知，設置爲0不能很好地工作，因爲該函數具有尖銳的邊緣。在我的具體情況下，線性權重會好得多。但表現也非常重要。如果沒有人有另一個想法，我將再等幾個小時，接受這個。 – Zotta

我會建議嘗試牛頓拉夫森的某種變體。

構造函數Diff（k），查看固定標記A和B之間的兩個圖形之間的區域差異。

數學我想這將是積分（X = A到B）{F（X） - K * G（X）} DX

無論如何實際地你可以只減去的值，

像如果範圍從X = -10到10，並且[-10,10]中的每個整數i（即21個數據點）上有f（i）和g（i）的數據點，則

那麼你只是總和（i = -10到10）{f（i） - k * g（i）}

基本上你會認爲這個函數看起來像拋物線 - 會有一個最佳的K，並在任一方向稍微偏離它會增加整個區域差異

和較大的差別，你會期望越大差距

所以，這應該是一個相當光滑函數（如果有大量的數據點）

所以要儘量減少DIFF（K）

所以要找到是否衍生物即d/DK DIFF（K）= 0

剛剛做牛頓拉夫森o n這個新功能d'（k）的

開始它在k = 1，它應該在相當快的解決方案開發區

這可能會給你一個最佳的計算時間

，如果你想要簡單的東西，剛開始有些k1和k2是兩側0

這麼說DIFF（1.5）= -3和DIFF（2.9）= 7

，那麼你會選擇AK說，3/10的方式（10 = 7 - -3）在1.5和2.9之間

和取決於是否能產生正或負的值，把它作爲新的K1或K2，沖洗和重複

來源

2011-07-23 15:00:18

數學問題：縮放圖形，使其與另一個匹配

回答

相關問題