Алгоритм ZETBraid

Алгоритм ZetBraid [1] является усовершенствованной версией алгоритма ZET, рассмотренного в предыдущей рассылке [2]. Основным недостатком последнего является процедура формирования компетентной матрицы, а именно:

1.      Попадание в компетентную матрицу неинформативных строк или столбцов.

2.      Фиксированность размера компетентной матрицы.

Алгоритм ZetBraid позволяет избавиться от указанных недостатков путем усовершенствования процедуры формирования компетентной матрицы методом плетения (англ. braid – плести, плетение).

Постановка задачи.

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

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

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

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

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

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

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

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

Рассмотрим основные этапы алгоритма ZET [2]:

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

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

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

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

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

Алгоритм ZetBraid отличается только пунктом 2.1, который подробно рассмотрен ниже.

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

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

Шаг 1. Задаем начальный размер компетентной матрицы (обычно берут 3). Это необходимо для избежания ошибок в начале «плетения».

Шаг 2. Определяем самую близкую строку (не входящую в компетентную матрицу) к целевой строке и добавляем ее в компетентную матрицу. Определяем ошибку прогнозирования новой матрицы. Если ошибка уменьшилась, то запоминаем компетентную матрицу, иначе возвращаемся к предыдущей матрице и переходим на шаг 3.

Шаг 3. Определяем самый близкий столбец (не входящий в компетентную матрицу) к целевому столбцу и добавляем его в компетентную матрицу. Определяем ошибку прогнозирования новой матрицы. Если ошибка уменьшилась, то запоминаем компетентную матрицу, иначе возвращаемся к предыдущей матрице и переходим на шаг 2.

Если нельзя добавить ни строку, ни столбец, то конец алгоритма.

Для применения алгоритма необходимо  решить следующие задачи:

1. Определение расстояния между строками.

2. Определение расстояния между столбцами.

3. Вычисление критерия оценки качества компетентной матрицы.

1. Расстояние между строками вычисляем по формуле

,

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

При вычислении коэффициентов ,  полагаются на три принципа:

1. Все весовые коэффициенты столбцов, которые входят в компетентную матрицу, равны.
2. Все весовые коэффициенты столбцов, которые не входят в компетентную матрицу, равны.
3. Сумма весовых коэффициентов столбцов, которые входят в компетентную матрицу разделенная на сумму весовых коэффициентов столбцов, которые не входят в компетентную матрицу есть константой  (параметр алгоритма).

Если из  столбцов  принадлежат компетентной матрице, то весовой коэффициент столбца:

            2. Для нахождения расстояния между столбцами необходимо построить уравнение линейной регрессии. Пусть  и  − столбцы, тогда необходимо получить уравнение .

Для нахождения коэффициентов  и  необходимо минимизировать функцию

,

где весовые коэффициенты строк ,  находятся аналогично весовым коэффициентам столбцов, то есть

 − количество строк, которые принадлежат компетентной матрице.

            3. Критерием оценки адекватности компетентной матрицы есть оценка качества предсказания неизвестного элемента.

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

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

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

1.      http://www.zetbraid.narod.ru