Найти и исправить неправильные значения в простом линейном наборе данных

Question

Это, вероятно, простой вопрос, но я не смог найти хороший подход.

У меня есть ограниченное количество упорядоченных значений int, которые должны быть на одинаковом расстоянии друг от друга, например: 32, 42, 52, 62, 72, 82.

Однако в действительности некоторые значения неверны. Мы могли бы в конечном итоге с 32, 51, 62, 66, 71, 83.

Как найти явно неправильное значение (в данном случае 66) и переместить его в правильное положение (42)?

• Можно предположить, что большинство данных все еще действительны, поэтому все еще можно рассчитать правильное предположение о правильном расстоянии между точками (здесь: 10).
• Количество точек известно и правильно (т. Е. Нам просто нужно двигаться, но не добавлять и не удалять точки).
• Границы данных слева и справа неизвестны, поведение в крайних случаях может быть определено свободно.

---

Когда я писал вопрос, я думал о чем-то. Идея может состоять в том, чтобы извлечь функцию f(x) = a + x * b (это легко) и выполнить итерацию по известному количеству точек. Элемент с наибольшим расстоянием до итерированной точки удаляется и вставляется в итеративную позицию, которая имеет наибольшее расстояние до исходной точки.

Answer 1

Вы можете использовать робастную регрессию , которая является не более чем причудливым термином для "подгонки прямой линии к группе точек таким образом, что точки, которые не подходят хорошо, удаляются изящно" .

Если вы не хотите писать код нелинейной оптимизации, вы можете использовать итеративно повторно взвешенные наименьшие квадраты , чтобы использовать любой существующий взвешенный код линейной регрессии, который у вас есть.

Идея состоит в том, что вы делаете взвешенные наименьшие квадраты , чтобы подогнать прямую линию к вашим точкам. Затем вы назначаете вес каждой точке, которая измеряет, считаете ли вы, что это выброс , слишком сильно отклоняющийся от линии регрессии (например, с помощью функции потерь Хьюбера ). Затем вы возвращаете регрессию с весами. Вы получите новую строку и, следовательно, можете вычислить новый набор весов. Повторите до сходимости (или максимальное количество итераций). Вы останетесь с весами, которые сообщают вам, какие точки являются плохими, и линией, которая хорошо соответствует оставшимся точкам, и которую можно использовать для замены выбросов.

Я думаю, что реализация не намного длиннее, чем текстовое описание выше.

Answer 2

Я экспериментировал с множеством разных подходов, вот чем я и закончил. Основная идея состоит в том, чтобы назначить хорошие, действительные значения массиву ожидаемых значений. Значения, которые не могут быть назначены, исправляются путем использования отсутствующих ожидаемых значений.

Приведен список фактических данных 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, работали хуже и часто показывали мне плохое поведение.

Answer 3

Я постараюсь описать алгоритм (я не знаю, даст ли он правильный результат для каждой входной последовательности, поэтому представьте его как идею):

Вход для алгоритма упорядоченпоследовательность R.Например, {32, 51, 62, 66, 71, 83}

1. Найти расстояние d между точками.Я думаю о:

   • Сортировать различия между элементами и взять медиану.
     Сортировать различия = {4, 5, 11, 12, 19} -> Медиана = 11
   • Или вычислите среднее значение разностей.
     Среднее значение = 10,2 -> Округленное среднее значение = 10

2. Постройте среднее значение m элементов R.
   В нашем примере (32 + 51 + 62 + 66 + 71 + 83) / 6 = 30,2
   Округлено = 30

3. Создайте сравнительную последовательность S, где первый элемент S_0 имеет значение m - (n / 2) * d (где n - количество элементов), а любой следующий элемент S_i имеет значение S_1 + i * d.
   .пример S = {30, 40, 50, 60, 70, 80}

4. Поскольку элементы во входной последовательности могли переместиться в другую позицию, постройте каждую перестановку из R

5. Найти перестановку, где число выбросов минимально (выброс - это элемент, где разница элементов больше 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.

Answer 4

Если неверен только один элемент данных и предполагается увеличение значений (как в вашем примере): Данные идут в 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);
}