§ 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. Заполнение каждого следующего пробела с использованием исходной информации и прогнозных значений ранее заполненных пробелов.

Для каждого из этих вариантов имеется несколько режимов выдачи промежуточных и окончательных результатов на печать.