寻找最接近特定测量值的一组测量值的算法

Question

我有一组测量值，例如：
测量 #1：{ 200、350、712、1023、1430、1555、1800、2036、2569 }
测量 #2：{ 165、400、974、1124、1600、1893、1919、2032、2654、2932 }
...
测量 #N: { 234, 454, 879, 1432, 1877, 2000, 2543, 2876 }

每次测量中元素的顺序很重要。
每个元素的值都将高于前一个。
每次测量中的元素数量可能会有所不同，
但它们应该相差不大。

现在我得到一个新的测量值作为输入
（假设：{ 212、354、978、1222、1454、1922、2013、2432、2987}）
并且应该从我已经拥有的测量集合中找到最接近的测量。

我的问题是我应该为这个任务使用什么算法？

更多：
1. 也可以在这样的情况下扩展任务，而不是输入一个测量值 i 将得到一小部分测量值。
2. 测量中的每个元素代表从开始开始经过的时间（以秒为单位）。
当达到 3600 秒（1 小时）时停止测量，因此最小可能值为 0，最大值为 3599。
在要创建的测量中创建每个元素的事件受人类行为的影响。

感谢您的帮助:)

Answer 1

在 collection 中计算每次测量的新测量误差的平方和。然后 return 你 collection 中误差最小的那个。

var measures = [
 [1, 2, 3, 4],
 [10, 20, 30, 40],
 [66, 77, 88, 99],
 [101, 202, 303, 404]
];

// ignores measurements that aren't the same length as the data
// uses the squared sum of differences (errors)
function findClosest(data) {
  var minError = 0x7FFFFFFF; // max 32bit signed int
  var result = null;
  for(var i=0; i < measures.length; i++) {
    if(data.length !== measures[i].length) { continue; }
    var error = 0;
    for(var j=0; j < data.length; j++) {
      error += Math.pow(measures[i][j] - data[j], 2);
    }
    if(error < minError) {
      minError = error;
      result = measures[i];
    }
  }
  return result;
}

// allows data that is different length than measurements by trying to best fit each element of data to an element of the tested measurement
// uses the squared sum of differences (error)
function findClosestV2(data) {
  var minError = 0x7FFFFFFF; // max 32bit signed int
  var result = null;
  for(var i=0; i < measures.length; i++) {
    var measure = measures[i];
    var error = 0;
    var minLocalError = 0x7FFFFFFF;
    for(var j=0; j < data.length; j++) {
      for(var k=0; k < measure.length; k++) {
        var localError = Math.pow(measure[k] - data[j], 2);
        if(localError < minLocalError) {
          minLocalError = localError;
        }
      }
      error += minLocalError;
    }
    if(error < minError) {
      minError = error;
      result = measures[i];
    }
  }
  return result;
}

// allows data that is different length than measurements by trying to best fit each element of data to an element of the tested measurement
// uses the average of the absolute error % using the previous measurement as the ideal value
function findClosestV3(data) {
  var minError = 0x7FFFFFFF; // max 32bit signed int
  var result = null;
  for(var i=0; i < measures.length; i++) {
    var measure = measures[i];
    var error = 0;
    var minLocalError = 0x7FFFFFFF;
    for(var j=0; j < data.length; j++) {
      for(var k=0; k < measure.length; k++) {
        var localError = Math.abs( (measure[k] - data[j]) / measure[k] );
        if(localError < minLocalError) {
          minLocalError = localError;
        }
      }
      error += minLocalError;
    }
    // average of sum of error percentages
    error /= data.length;
    if(error < minError) {
      minError = error;
      result = measures[i];
    }
  }
  return result;
}

console.log(findClosest([2,3,4,5])); // [1,2,3,4]
console.log(findClosest([70,80,90,100])); // [66,77,88,99]
console.log(findClosest([9,19,304,405])); // [101,202,303,404]

console.log(findClosestV2([404])); // [101,202,303,404]
console.log(findClosestV2([66,67,68,69])); // [66,77,88,99]
console.log(findClosestV2([9,19,304,405])); // [10,20,30,40]

console.log(findClosestV3([404])); // [101,202,303,404]
console.log(findClosestV3([66,67,68,69])); // [66,77,88,99]
console.log(findClosestV3([9,19,304,405])); // [10,20,30,40]

Answer 2

假设您的数据是 "fuzzy"，您可能想要研究的一个 class 算法是 dynamic programming。模糊我的意思是两组几乎对齐，但一组可能插入了额外的元素，与另一组相比删除了额外的元素并且匹配元素 "almost" 匹配。

在这些类型的算法中，您通常通过为比对中的 inserting/removing 元素定义惩罚和为不完全匹配的两个元素定义惩罚分数来定义距离分数。在您的情况下，您可以为插入额外的计时事件定义“100”秒的插入/删除惩罚，并将双元素距离分数定义为以秒为单位的绝对距离。根据该定义，您可以轻松找到并修改 needleman-wunsch 算法实现或类似的东西。这将在可接受的时间内为您提供两组小测量值之间的距离。但是，如果测量中的元素数量很大或集合数量很大，并且您需要以毫秒为单位的答案，那么除非您能为您的问题找到很多好的约束，否则这是一个相当困难的问题。

以上只是一个例子，一切都归结为上下文。您的数据嘈杂吗？如何 "noisy"，在中间有额外的元素，开始或结束或只是稍微偏离位置？加上一大堆其他问题。

选择和实施模糊算法的范围从相当容易到几乎不可能，这完全取决于上下文和您要使用结果的目的。是否需要精确或 "just good enough"。是否需要快等

寻找最接近特定测量值的一组测量值的算法

Algorithm for finding the closest set of measurment to certain measurment

algorithm

dynamic-programming