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