Наиболее полно, по-видимому, проблема восстановления пропусков методами, которые названы их авторами локальными, исследована в нашей стране (Загоруйко Н.Г., Лбов Г.В., Елкина В.Н., Тимеркаев В.С., Ульянов Г.В.). По сути, то, что называется алгоритмами семейства ZET, является детально проработанной и апробированной технологией верификации экспериментальных данных, основанной на гипотезе их избыточности.

В алгоритме ZET каждое отдельно взятое пропущенное значение x_ij в матрице данных X(m,n), т.е. отсутствующий j-й признак у i-го объекта, оценивается по предсказывающей подматрице, составленной из некоторого заранее заданного числа m₀ наиболее похожих объектов и некоторого заранее заданного числа n₀ наиболее похожих признаков. Пропущенное значение восстанавливается по уравнению регрессии для каждой пары строк подматрицы, одна из которых содержит пропуск. Аналогично, пропущенное значение восстанавливается и для каждой пары столбцов, один из которых содержит тот же пропуск. Окончательная оценка получается усреднением предварительных оценок с весами, значения которых зависят от некоторых параметров.

Необходимость задания размеров предсказывающей подматрицы m₀ и n₀, а также других важных параметров, привела к необходимости убедиться в правдоподобности восстановленных значений. Именно поэтому в современных версиях алгоритмов семейства ZET реализована многоуровневая и многошаговая технология подбора всех необходимых параметров на основе проверки качества прогноза восстанавливаемых значений. Данная технология имеет самостоятельную ценность и адекватна целому ряду задач прогностического характера.

С другой стороны очевидно, что было бы удобно определить размер предсказывающей подматрицы, например, соответствующими кластером и группой после построения некоторой кластеризации объектов и группировки признаков. Следовательно, мы снова должны решить проблему выбора числа кластеров и групп. Рассмотрим применение метода неиерархических разбиений для восстановления пропусков в матрице данных.

Обозначим пропуск символом ·. При вычислении сходства d_ij элементов  w_i и w_j  все некомплектные пары значений (x_il, x_jl), l=1,...n не учитываются. Напомним, что в некомплектной паре пропущено хотя бы одно из значений. Возьмем d_ij = d^·_ij при вычислении корреляций и d_ij = d^·_ij n/(n-n^·) при вычислении евклидовых расстояний, где d^·_ij - сходство при наличии некомплектных пар, n^· - число некомплектных пар, n^· < n.

Пусть выполнено разбиение множества W . В задаче кластеризации будем восстанавливать пропуск значения  x_ij  у объекта x_i по j-й характеристике средним этой характеристики c^k_j по кластеру W_k, полагая, что x_iОW_k.

В задаче группировки будем восстанавливать пропуск значения x_ij у признака x_i по j-у наблюдению средневзвешенным этого наблюдения c^k_j по признакам в группе W_k, x_iОW_k. Напомним, что в задаче группировки нам удобно рассматривать матрицу X(m,n), в которой признаки расположены по строкам. Пропущенное значение x_ij можно восстановить по уравнению линейной регрессии
        (x_ij - m(x_i)) / s(x_i) = d_iq(x_qj - m(x_q)) / s(x_q)
для признаков x_i и x_q как нормированную величину
        x^q_ij = d_iq(x_qj - m(x_q)) / s(x_q),
где m(x_q) и s(x_q) - среднее и ско признака x_q (в строке). Тогда пропущенное значение оценивается как величина
        x_ij = m(x_i) + c^k_j s(x_i),
        c^k_j = S x^q_ij |d_iq| / S |d_ip|   по   x_qОW_k, x_pОW_k,  где x_qj, x_pjП·.
Если окажется, что пропущены значения x_lj для всех x_lОW_k, то пропущенное значение x_ij не восстанавливается.

Алгоритм 3. Построим полную последовательность разбиений алгоритмом 2 и сформируем таблицу восстановленных значений пропусков. Столбцы таблицы соответствуют элементам x_ij, содержащим пропуски, а строки - восстановленным значениям пропусков для каждого устойчивого разбиения в последовательности. Просмотрим таблицу по столбцам снизу вверх и восстановим каждый пропуск x_ij первым значением, которое отличается от значения пропуска.

Очевидно, что данный алгоритм стремится восстановить пропущенное значение у некоторой характеристики элемента w_i просто как значение соответствующей характеристики самого похожего на него элемента w_q. Это сразу же видно для агломеративного варианта алгоритма 3.

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

Для каждого восстановленного значения x_ij можно дополнительно потребовать, чтобы элемент w_i оказался в составе соответствующего подмножества W_k размером |W_k| = m₀, m₀< m. При этом одновременно восстановленные значения можно дополнительно упорядочить по убыванию плотности множеств W_k, где w_iОW_k.

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

Алгоритм 4. Упорядочим все пропуски алгоритмом 3. Восстановим первый или несколько первых пропусков. Будем повторять эти действия для оставшихся пропусков до тех пор, пока не будут восстановлены все пропуски.

Пусть для некоторой матрицы X(m,n) число объектов (строк) в достаточной степени превышает число признаков (столбцов). В этом случае будем полагать, что m >> n. Тогда для восстановления пропусков естественно применить алгоритм 4 к данной матрице. Когда n >> m, то естественно применить алгоритм 4 к матрице X^T. Если же m примерно равно n, можно использовать следующий алгоритм.

Алгоритм 5. Упорядочим алгоритмом 3 все пропуски в матрице X и отдельно в матрице X^T. Пусть некоторый пропуск x_ij оказался первым в одной последовательности и k-м в другой. Выберем последовательность, в которой ее первый пропуск имеет минимальную сумму мест 1+k, и восстановим его как средневзвешенное значений из двух последовательностей x_ij = x¹_ij k / (1+k) + x^k_ij / (1+k). Будем повторять эти действия для оставшихся пропусков до тех пор, пока не будут восстановлены все пропуски.

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

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

Литература  
• Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Классификация и снижение размерности. М.: Финансы и статистика, 1989.
• Браверман Э.М. Методы экстремальной группировки параметров и задача выделения существенных факторов// АиТ. 1970. №1. С. 123-132.
• Браверман Э.М., Мучник И.Б. Структурные методы обработки эмпирических данных. М.: Наука, 1983.
• Двоенко С.Д. Неиерархический дивизимный алгоритм группировки// АиТ. 1999. №9. С.47–57.
• Двоенко С.Д. Неиерархический дивизимный алгоритм кластеризации// АиТ. 1999. №4. С.117–124.
• Двоенко С.Д., Моттль В.В. Основы обработки данных. Тула: Издательство Тульского госуниверситета, 1997.
• Дорофеюк А.А. Алгоритмы автоматической классификации (обзор)// АиТ. 1971. № 12. С. 78-113.
• Дорофеюк А.А., Лумельский В.Я. Реализация алгоритмов обучения распознаванию образов без учителя на ЭВМ// Алгоритмы обучения распознаванию образов/ Под ред. Вапника В.Н. М.: Сов. радио, 1973, С.181-198.
• Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.
• Дюран Б., Оделл П. Кластерный анализ. М.: Статистика, 1977.
• Жуковская В.М., Мучник И.Б. Факторный анализ в социально-экономических исследованиях. М.: Статистика, 1976.
• Загоруйко Н.Г. Методы распознавания и их применение. М.: Сов. радио, 1972.
• Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд. Института математики, 1999.
• Загоруйко Н.Г., Елкина В.Н., Емельянов С.В., Лбов Г.С. Пакет прикладных программ ОТЭКС. М.: Финансы и статистика, 1986.
• Ким Дж.-О., Мьюллер Ч.У. Факторный анализ: статистические методы и практические вопросы// Факторный, дискриминантный и кластерный анализ. М.: Финансы и статистика, 1989. С. 5-77.
• Лоули Д., Максвелл А. Факторный анализ как статистический метод. М.: Мир, 1967.
• Лумельский В.Я. Группировка параметров на основе квадратной матрицы связей// АиТ. 1970. №1. С. 133-143.
• Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988.
• Миркин Б.Г. Анализ качественных признаков и структур. М.: Статистика, 1980.
• Олдендерфер М.С., Блэшфилд Р.К. Кластерный анализ// Факторный, дискриминантный и кластерный анализ. М.: Финансы и статистика, 1989. С. 139-214.
• Оре О. Теория графов. М.: Наука, 1968.
• Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.
• Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М.: Гостехиздат, 1963.
• Харман Г. Современный факторный анализ. М.: Статистика, 1972.

	часть 1 (RUS/ENG)  часть 2 (RUS/ENG)  часть 3 (RUS/ENG)  Пример