Алгоритм ZET

Пусть задана таблица экспериментальных данных , ,  типа „объект-свойство”:

Таблица экспериментальных данных

где  – количество строк-объектов,  – количество столбцов-свойств,  - пропуск, причем количество таких пропусков в таблице может быть довольно большим.

Ставится задача восстановления отсутствующих (пропущенных) значений @ в таблице .

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

В основе его функционирования лежат три предположения (гипотезы):

1.      Гипотеза избыточности: предполагается, что в таблице  присутствует избыточность в строках (объекты могут быть похожи между собой) и столбцах (между свойствами могут быть зависимости). При отсутствии избыточности все строки и столбцы имеют одинаковый вес при прогнозировании и смысл локальности алгоритма теряется.

2.      Гипотеза аналогичности: предполагается, что если два объекта «похожи» по значениям () свойств, то они «похожи» и по -му свойству.

3.      Гипотеза локальной компетентности: предполагается, что избыточность строк и столбцов носит локальный характер, то есть для каждого пропущенного значения имеется только некоторое количество объектов – аналогов объекта с пропуском и свойств – аналогов свойства с пропуском. Поэтому предлагается использовать для прогнозирования только такие «компетентные» объекты и свойства, которые выбираются для каждого пропуска отдельно.

Основные этапы алгоритма ZET для обработки таблицы  с  пропусками:

1.      Предварительная обработка начальных данных.

2.      Прогнозирование пропуска - выполняется  раз:

2.1.   Формирование компетентной матрицы.

2.2.   Подбор параметров модели прогнозирования.

2.3.   Прогнозирование пропуска.

Рассмотрим подробнее каждый этап.

1.      Вначале столбцы матрицы  нормируются по дисперсиям для приведения различных свойств объектов к единой шкале:

.

2.      Следующие этапы выполняют  раз. Пусть координаты текущего элемента с пропуском ,

2.1.   Формирование компетентной матрицы

2.1.1.      Задать размеры компетентной матрицы , , , ,  

.

2.1.2.      Выбрать  компетентных строк для строки с пропуском.

Компетентность  строки  по отношению к строке с пропуском  определяется по формуле

,

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

2.1.3.      Выбрать  компетентных столбцов для столбца с пропуском.

Компетентность  столбца  по отношению к столбцу с пропуском  определяется по формуле

,

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

2.2.   Подбор параметров моделей прогнозирования  (по строкам) и  (по столбцам) – коэффициенты регулирующие влияние компетентности на результат предсказания.

2.2.1.      Задаем пределы изменения коэффициентов  и  и шаг их изменения.

2.2.2.      Находим оптимальные коэффициенты  и   для прогноза пропуска по

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

, ,

где  - реальное значение элемента  строки (столбца)  с пропуском,  - прогноз этого элемента с помощью компетентных строк (столбцов).  рассчитываются по формуле

,

где  для строк и  для столбцов,  - прогноз для известных значений строки (столбца) с пропуском  с помощью -й строки (столбца), рассчитывается с помощью линейной регрессии вида  по МНК.

2.3.   Прогнозирование пропуска

2.3.1.      Прогнозирование пропуска по столбцам выполняется по формуле

.

2.3.2.      Прогнозирование пропуска по столбцам выполняется по формуле

.

2.3.3.      Общий прогноз получается усреднением прогнозов по строкам и столбцам

.

Программы заполнения пробелов могут работать в одном из  следующих режимов: 

1.      Заполнение всех пробелов в таблице по указанному алгоритму. 

2.      Заполнение только тех пробелов, ожидаемая ошибка для которых не превышает заданной величины. Для  определения  ожидаемой  ошибки предсказания вычисляется дисперсия значений подсказок , получаемых от всех столбцов и  строк компетентной подматрицы.

3.      Заполнение пробелов только на базе информации, имеющейся в исходной таблице.

4.      Заполнение каждого следующего пробела с использованием исходной информации и прогнозных значений ранее заполненных пробелов.

Список использованных источников

1.      Загоруйко Н.Г. Методы распознавания и их применение. – М.: Советское Радио, 1972.

2.      http://math.nsc.ru/AP/oteks/index.html.