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

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

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

Answer 4

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

Вход для алгоритма - упорядоченная последовательность 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.