Глава 7 Заполнение пробелов и обнаружение ошибок в эмпирических таблицах

§ 1. Обзор работ по проблеме заполнения пробелов [93]

Реальные таблицы данных часто содержат пробелы: у некоторых объектов  значение того или иного признака  может отсутствовать. В результате на вход программ анализа данных подается таблица с одним или несколькими пустыми клеточками. Большинство известных методов анализа данных не рассчитано на обработку «некомплектных» таблиц, в связи с чем стали делаться попытки решать задачи заполнения содержащихся в них пробелов.

Решению этих задач посвящено большое число работ. Самые первые из них появились еще в докомпьютерное время (до 1960 года) и, начиная с классической работы С. Уилкса [150], носили в основном теоретический характер и были посвящены большей частью оценкам максимального правдоподобия (МП-оценкам) по некомплектным выборкам. На практике же в это время использовались примитивные способы борьбы с пробелами. Так, в одной из первых работ на эту тему [144] дается рекомендация при анализе табличных данных удалять те строки и те столбцы, в которых имеется хотя бы один пробел. Однако в практике встречаются таблицы, содержащие по несколько пробелов в каждой строке и в каждом столбце, и такие таблицы перед обработкой следовало бы вычеркивать полностью и по несколько раз. Если это не желательно, то рекомендуется заполнять пробелы средними значениями величин, имеющихся в данном столбце. Очевидно, что это самый простой, но не самый точный метод заполнения пробелов. Полный обзор работ этого периода можно найти в [7].

С распространением ЭВМ были предложены более сложные машинные алгоритмы, основанные на методе наименьших квадратов: регрессионный метод [9,151], метод главных компонент [40], пошаговая регрессия [157], метод многомерной линейной экстраполяции [137], метод прогностических переменных [61]. Учитывая тот факт, что оценки первых двух моментов полностью определяют оценки регрессии, многие авторы сосредоточились на проблеме оценивания ковариационной матрицы по данным с отсутствующими значениями [39,160,167].

Со второй половины 70-х годов особых успехов добилось направление, связанное с оценками максимального правдоподобия (МП-оценками), особенно в рамках нормальных распределений. Появились практические алгоритмы, вычисляющие МП-оценки пробелов, например [16, 148, 159]. В работе [46] предложена мощная вычислительная процедура: ЕМ-алгоритм для решения общей задачи оценивания параметров в условиях некомплектной выборки. К настоящему времени эти методы интенсивно развиваются, созданы эффективные робастные варианты ЕМ-алгоритма [114]. Возобладала тенденция поиска для всех классических статистических методов аналогов, способных работать с некомплектными данными, не заполняя пробелов [115, 161, 164]. Более полный обзор теории и практики содержится в монографиях [52, 113].

Методы, упомянутые выше, действуют глобально: в них предполагается, что зависимость заданного (например, линейного) типа реализована на всех объектах, поэтому и в оценивании зависимостей участвуют все строки и столбцы. Локальные алгоритмы, оценивающие зависимости по некомплектной выборке в некоторой окрестности предсказываемого объекта, были впервые предложены в работах [83,85]. Постановку задачи предсказания значений пропущенных элементов можно пояснить на примере обработки таблицы размером , не содержащей пробелов.

Пусть в нашем распоряжении имеется набор различных стратегий (алгоритмов) , предназначенных для предсказания значений пропущенных элементов. Закроем в таблице известный элемент , стоящий на пересечении строки  и столбца , и предскажем его с помощью всех алгоритмов  поочередно. Каждый алгоритм  предскажет свое значение , которое будет отличаться от исходного («истинного») значения на величину .

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

Алгоритмы из набора  могут отличаться друг от друга лежащими в их основании эвристическими предположениями (гипотезами). Ниже описаны некоторые из этих гипотез и основанные на них алгоритмы двух семейств — ZET и WANGA.