Заполнить пробелы 2D-массива

Question

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

Я посмотрел на билинейную интерполяцию и бикубическую интерполяцию, но есть ли другие?

 | 1 | 2 | 3 | 4 | 5 | 6 | 7 
--------------------------------------------------------------------------------- 
1 | 
2 | 
3 |    55 
4 |    50          12   6 
5 |    45            19 
6 |    xxx 
7 |    35  45  50  yyy 
8 | 
9 | 
10 | 
11 | 
12 |      zzz 
13 | 
14 | 
15 | 

Например, я бы ожидать, ххх, чтобы быть в непосредственной близости от 40, а YYY находиться в непосредственной близости от 50. ZZZ однако может иметь более случайное значение. Обратите внимание: я хотел бы заполнить каждое пустое пространство, а не только xxx, yyy и zzz. И иметь возможность сделать это для любого малонаселенного массива.

Существует ли такой алгоритм?

Answer 1

Существует миллион таких алгоритмов. Поэтому в первую очередь у вас есть некоторый словарь известных значений, как это:

known_values = { 
    (2, 3): 55.0, 
    (2, 4): 50.0, 
    (2, 5): 45.0, 
    (2, 7): 35.0, 
    (3, 7): 45.0, 
    (4, 7): 50.0, 
    (6, 4): 12.0, 
    (7, 4): 6.0, 
    (7, 5): 19.0, 
} 

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

def interpolate(known_values, p): 
    total_weight = 0.0 
    total_sum = 0.0 
    for q, value in known_values: 
     if p == q: 
      return value 
     d_square = (p[0] - q[0])**2 + (p[1] - q[1])**2 
     total_weight = total_weight + 1.0/d_square 
     total_sum = total_sum + value/d_square 
    return total_sum/total_weight 

Это решение будет работать до тех пор, как матрица имеет ANY заполнены данными.

Однако, судя по тому, как вы задали этот вопрос, вам может потребоваться гладкая интерполяция, которая приблизительно линейна в любой небольшой области. Один из способов сделать это - найти (a, b, c) так, чтобы функция a*x + b*y + c минимизировала взвешенную сумму квадратов ошибок, при этом вес был 4-й степенью расстояния от вашей нужной точки до известной точки. (Первые 2 силы отменяют квадрат области, а остальные два - близлежащие точки).

Причина использования наименьших квадратов для ошибки здесь заключается в том, что математика работает просто. Вы свести к минимуму точно, когда небольшое изменение в a, b или c не сильно изменит значение, что означает, что частная производная равна 0. Таким образом, три частные производные дают вам три набора линейных уравнений. Решение 3 уравнений из 3 переменных достаточно просто.

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

Answer 2

Эта проблема может быть рассмотрена как «проблема двумерной интерполяции», и в этой области есть тонны исследований. Вы можете искать «Многомерную интерполяцию» в Wiki и искать алгоритмы в разделе «2 измерения».

Среди различных методов билинейная/бикубическая интерполяция требует, чтобы данные формировали сетку, что не относится к вашим данным. Метод триангуляции Delaunay не подходит для экстраполяции по мере необходимости в вашем случае. Методы обратного взвешенного расстояния легко внедряются и подходят для экстраполяции, но результат часто не является удовлетворительным. Я лично рекомендовал бы использовать функцию радиальной базы, если у вас слишком много точек данных (например, тысяч).