§ 2. Базовый алгоритм ZET заполнения пробелов
В основе алгоритма ZET [72,83] лежат три предположения. Первое (гипотеза избыточности) состоит в том, что реальные таблицы имеют избыточность, проявляющуюся в наличии похожих между собой объектов (строк) и зависящих друг от друга свойств (столбцов). Если же избыточность отсутствует (как, например, в таблице случайных чисел), то предпочесть один прогноз другому не возможно.
Второе предположение (гипотеза локальной компактности) состоит в утверждении, что для предсказания пропущенного элемента
нужно использовать не всю таблицу, а лишь ее «компетентную» часть, состоящую из элементов строк, похожих на строку
, и элементов столбцов, похожих на столбец
. Остальные строки и столбцы для данного элемента неинформативны. Их использование лишь разрушало бы локальную компактность подмножества компетентных элементов и ухудшало точность предсказания.
Третье предположение (гипотеза линейных зависимостей) заключается в том, что из всех возможных видов зависимостей между столбцами (строками) в алгоритме ZET используются только линейные зависимости. Если зависимости носят более сложный характер, то для их надежного обнаружения требуется такой большой объем данных, который в реальных задачах встречается нечасто. В работе алгоритма ZET можно выделить три этапа.
1. На первом этапе для данного пробела из исходной матрицы «объект-свойство», столбцы которой нормированы по дисперсии, выбирается подмножество компетентных строк и затем для этих строк — компетентных столбцов.
2. На втором этапе автоматически подбираются параметры в формуле, используемой для предсказания пропущенного элемента, при которых ожидаемая ошибка предсказания достигает минимума.
3. На третьем этапе выполняется непосредственно прогнозирование элемента по этой формуле.
Под компетентностью
-й строки по отношению к
-й понимается величина

Здесь
,
— евклидово расстояние между
-й и
-й строками, a
— коэффициент комплектности, равный числу свойств, значения которых известны как для
-й, так и для
-й строки. Компетентная строка не должна иметь пробела в
-м столбце.
Под компетентностью
-го столбца по отношению к
-му столбцу понимается величина

где
— модуль коэффициента корреляции между
-м и
-м столбцами, a
— коэффициент комплектности, равный числу объектов, у которых известны как
-e, так и
-е свойства. Компетентный столбец не должен иметь пробела в
-й строке.
По указанию пользователя программа выбирает компетентную подматрицу любого размера в пределах от 2х2 до
. Обычно используется подматрица, содержащая от 3 до 7 строк и столбцов.
В процессе предсказания значения пробела с использованием зависимостей между
-м и всеми остальными (
-ми) столбцами вырабатываются «подсказки»
. Для их получения используется уравнение линейной регрессии между
-м и
-м столбцами (см. рис. 25). Если в подматрице было
столбцов, то затем
подсказок усредняются с весом, пропорциональным компетентности соответствующего столбца. В итоге получается прогнозная величина
, порожденная избыточностью, содержащейся в столбцах:
(1)
Здесь
— коэффициент, регулирующий влияние компетентности на результат предсказания. При малых значениях
разница в компетентности сказывается мало, при больших
более компетентные столбцы влияют гораздо больше других. Выбор
и составляет суть этапа подбора формулы для прогнозирования: все известные элементы
-гo столбца предсказываются при разных значениях
и затем выбирается такое значение
, при котором ошибка прогноза
была минимальной.

Рис. 22
По формуле (1) с выбранным значением
делается прогноз
величины пропущенного элемента, а полученная при выборе
минимальная величина
в дальнейшем принимается в качестве оценки ожидаемой ошибки заполнения пробела по столбцам.
Процедура заполнения пробела с использованием связи между
-й строкой и всеми
другими (
-ми) строками
аналогична вышеописанной и выполняется по формуле
(2)
Для выбора
здесь используются все известные элементы
-й строки, и выбор делается при минимальном значении ошибки
их прогнозирования.
Общий прогноз
значения пропущенного элемента
получается выбором либо прогноза
, если
, либо прогноза
, если
. Возможно и их усреднение с весом, обратно пропорциональным величине ожидаемой ошибки:
(3)
Здесь
— константа, например, равная 0,01, введенная для предотвращения деления на нуль.
Как отмечалось, оценка ожидаемой ошибки заполнения пробела (отклонения предсказанного значения от истинного) может быть получена в процессе подбора коэффициента
. О величине ожидаемой ошибки
можно судить по ошибкам
и
предсказаний известных элементов
-й строки и
-го столбца при наилучшем значении
. Эксперименты показывают, что корреляция между средним значением этих ошибок
и ошибкой
всегда положительна.
Второй способ определения ожидаемой ошибки основан на оценке дисперсии «подсказок». Вычисляется дисперсия
величин подсказок
и
, получаемых от всех
столбцов и
строк компетентной подматрицы. Большая дисперсия указывает на отсутствие устойчивой закономерной связи между элементом
и другими элементами подматрицы, т. е. на отсутствие их компактности. Ясно, что в этих условиях рассчитывать на высокую точность предсказания величины
не приходится. Эксперименты показали, что коэффициент корреляции между дисперсией
и ошибкой предсказания
достигает величины +0,7. Прогнозы ожидаемой ошибки заполнения по дисперсионному критерию оказались более надежными, чем по критерию, основанному на оценках ошибок
.
Для различных прикладных задач были сделаны многочисленные модификации описанного выше базового алгоритма ZET, отличающиеся своим назначением и наборами разных режимов работы. Программы заполнения пробелов могут работать в одном из следующих режимов:
1. Заполнение всех пробелов.
2. Заполнение только тех пробелов, ожидаемая ошибка для которых не превышает заданной величины.
3. Заполнение пробелов только на базе информации, имеющейся в исходной таблице.
4. Заполнение каждого следующего пробела с использованием исходной информации и прогнозных значений ранее заполненных пробелов.
Для каждого из этих вариантов имеется несколько режимов выдачи промежуточных и окончательных результатов на печать.