在简单的线性数据集中查找并修复错误的值

| 这可能是一个简单的问题，但我找不到一个好的方法。我有数量有限的有序整数值，这些值应该彼此具有相似的距离，例如：32, 42, 52, 62, 72, 82。但实际上，某些价值观是错误的。我们可能以ѭ1end结尾。如何找到明显错误的值（在这种情况下为66）并将其移动到正确的位置（42）？可以假设大多数数据仍然有效，因此仍然有可能计算出点之间正确距离的正确猜测（此处为10）。点数是已知且正确的（即，我们只需要移动即可，而无需添加或删除点）。左侧和右侧的数据边界是未知的，可以自由定义边缘情况下的行为。在写问题时，我想到了一些东西。一个想法可能是提取一个函数f(x) = a + x * b（很简单）并遍历已知的点数。到迭代点的距离最大的基准被删除并插入到到原始点的距离最大的迭代位置。

已邀请:

4 个回复

埃输林桨铃

您可以使用健壮的回归，这仅仅是“用一条直线拟合一堆点，这样可以很好地去除不合适的点”的幻想术语。如果您不想编写非线性优化代码，则可以使用迭代式加权最小二乘法来利用现有的任何加权线性回归代码。这个想法是您对最小二乘加权，以使直线适合您的点。然后，您可以为每个点分配一个权重，以衡量您是否认为它是一个离群值，从而偏离回归线太多（例如，通过Huber损失函数）。然后，您可以使用权重重做回归。您将获得一条新行，因此可以计算出一组新的权重。重复直到收敛（或最大迭代次数）。您将获得权重，这些权重告诉您哪些点不好，以及一条可以很好地拟合其余点并且可以用来替代异常值的线。我认为该实现不会比上面的文字描述长很多。

届甸衬丝蚕

如果只有一个基准是错误的，并假设数值增加（如您的示例所示）：数据进入DATA和DATA_SIZE，THRESHOLD是允许的偏差

#include <stdio.h>
#define THRESHOLD 3

#define DATA 32, 51, 62, 66, 71, 83
#define DATA_SIZE 6
void main()
{
    int data[]={DATA}; int size = DATA_SIZE;
    int skip = 0, diffs, curDif, maxDif, lastItem, item, dif, maxPos;
    int maxDiffs = 10000, location, newPosition, newValue;
    for(skip = 0; skip < size; skip++)
    {
      diffs = 0;
      curDif = 0;
      maxDif = 0;
      maxPos = -1;
      lastItem = (skip == 0);
      for(item = lastItem+1; item < size; item++)
      {
        if(item == skip)continue;
        dif = data[item]-data[lastItem];
        if(abs(dif - curDif) > THRESHOLD)
        {
          curDif = dif;
          diffs++;
          if(curDif > maxDif)
          {
            maxDif = curDif;
            maxPos = item;
          }
        }
        lastItem = item;
      }

      if(diffs < maxDiffs)
      {
          maxDiffs = diffs;
          location = skip;
          newPosition = maxPos;
          newValue = data[maxPos-1]+(maxDif>>1);
      }
    }
    printf(\"Found... \\nindex %d\\nValue: %d\\nGoes in:%d\\nNew value:%d\\n\", location, data[location], newPosition, newValue);
}

焙恍挝厂熄

我尝试了许多不同的方法，这就是我最终得到的结果。基本思想是为期望值数组分配良好的有效值。无法分配的值将通过使用缺少的期望值来固定。给出的是实际数据peaks的列表。建立预期数据清单

var expected = Enumerable
    // 19 is the known number of values
    .Range (0, 19)
    // simply interpolate over the actual data
    .Select (x => peaks.First () + x * (peaks.Last () - peaks.First ()) / 18)
    .ToList ();

建立所有点的距离矩阵

var distances = expected.SelectMany (dst => peaks.Select (src => new {
    Expected = dst,
    Original = src,
    Distance = Math.Abs (dst - src)
}));

重复

for (;;)
{

选择最佳距离

var best = distances
    // ignore really bad values
    .Where (x => x.Distance < dAvgAll * 0.3)
    .OrderBy (x => x.Distance).FirstOrDefault ();

如果找不到好的分配，请退出

if (best == null) {
    break;
}

否则，存储比赛

expected.Remove (best.Expected);
peaks.Remove (best.Original);

}

我们已识别并删除了源中所有有效的条目。我们仅使用期望集中的剩余值，而忽略剩余的原始值即可完成最终数据集。其他尝试的方法（包括从gusbro改版的方法）效果不佳，并且经常对我表现出不良行为。

痰嫉

我将尝试概述一种算法（我不知道对于每个输入序列它是否都能给出正确的结果，因此请考虑一下）：该算法的输入是有序序列“ 11”。例如{32，51，62，66，71，83} 找到点之间的距离distance12ѭ。我在想：对元素之间的差异进行排序，然后取中位数。排序后的差异= {4，5，11，12，19}->中位数= 11 或计算差异的平均值。平均值= 10.2->舍入平均值= 10 建立R元素的平均值m。在我们的示例中（32 + 51 + 62 + 66 + 71 + 83）/ 6 = 30.2 取整= 30 建立比较序列S，其中第一个元素S_0具有值 m - (n / 2) * d（其中n是元素的数量），任何其他元素S_i的值都为S_1 + i * d。在我们的示例中，S= {30，40，50，60，70，80} 由于输入序列中的元素可能已经移动到另一个位置，建立ѭ11的每个排列找到离群点数量最小的排列（离群点是元素，元素差较大的元素0.3 * d

                     S = { 30, 40, 50, 60, 70, 80 } 
    permutation x of R = { 32, 51, 62, 66, 71, 83 } three outliers
    permutation y of R = { 32, 66, 51, 62, 71, 83 } one outlier
    permutation z of R = ...

在该示例中，算法的结果将是置换y，并由此找到元素66的正确位置。

要回复问题请先登录或注册

在简单的线性数据集中查找并修复错误的值

4 个回复

发起人

error_correction

algorithm

问题状态

在简单的线性数据集中查找并修复错误的值

与内容相关的链接

4 个回复

发起人

error_correction

algorithm

问题状态