数学问题：缩放图形，使其与另一个匹配

我有两个值表，并且想要缩放第一个图表，以便它尽可能匹配第二个图表。两者长度相同。如果两者在图表中都以图表形式绘制，则应尽可能彼此接近。但我不想要二次的，但简单的线性权重。我的问题是，我不知道如何实际计算最佳比例因子，因为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

数学问题：缩放图形，使其与另一个匹配

回答

相关问题