§ 5. Алгоритмы семейства WANGА
Алгоритмы
семейства WANGA [85], как и
семейства ZET, основаны на
гипотезе локальной компактности, но предназначены для заполнения пробелов в
таблицах с разнотипными переменными. Начнем с описания алгоритмов для таблицы,
все
признаков
в которой измерены в одной и той же шкале отношений.
5.1. Алгоритм WANGA—R. Пусть
— таблица с пропущенным
элементом
. Все другие
элементы таблицы известны. Для выбора компетентной подтаблицы размером в
строк и
столбцов
воспользуемся следующей процедурой. Выберем элемент
,. На пересечениях
-й
и
-й строк с
-м
и
-м столбцами находятся четыре
элемента таблицы:
,
,
и неизвестный
элемент
.
Если
признаки связаны сильной прямой зависимостью, то отношение двух элементов
-го столбца будет
таким же или почти таким, как и отношение двух элементов
-го столбца. Тогда из
предполагаемого равенства отношений
можно получить вариант
оценки («подсказки»)
заполняемого элемента:
. Повторив эту процедуру для всех других
элементов таблицы, мы получим
вариантов
подсказок:
Выделим из них
подсказки, полученные с участием элементов
-й строки, и найдем их дисперсию
.
Величину
примем в качестве меры
компетентности
-й
строки.
достигает
максимального значения единицы, если дисперсия
равна нулю, и
убывает с ростом дисперсии, оставаясь положительной величиной. Аналогично по
дисперсии
подсказок с участием всех элементов
-го
столбца найдем его компетентность
. Сформируем компетентную подтаблицу
, включив в нее
самых
компетентных строк и
самых
компетентных столбцов.
Процесс
заполнения пробела алгоритмом WANGA-R состоит в
следующем. Присоединяем к таблице
элементы
-го столбца и
-й
строки. Перебираем все четверки элементов, которые находятся на пересечении
двух столбцов:
-го
и
-го
и двух строк:
-й
и
-й.
Неизвестный элемент
,
входящий
в состав всех этих четверок, вычисляем по описанному выше способу и получаем
вариантов
подсказок:
.
Окончательное
решение о значении пропущенного элемента получаем в виде средневзвешенной
суммы подсказок:
для всех
и
.
Здесь
весовой коэффициент подсказки от элемента
равен его
компетентности:
. Степень
доверия
к полученному решению можно
оценить через величину дисперсии
всех
подсказок:
.
5.2. Алгоритм WANGA—I. Если данные в
таблице
замерены в шкале интервалов,
то минимальным подсказывающим элементом в алгоритме WANGA-I будет
подматрица, состоящая из шести элементов, стоящих на пересечениях двух столбцов
(
и
) и трех строк (
-,
- и
-й).
Инвариантом шкалы интервалов является отношение разностей двух любых пар
элементов одного и того же столбца. Основываясь на этом и на гипотезе о прямой
связи между
-м
и
-м столбцами, можно записать:
Отсюда получаем
вариант подсказки пропущенного элемента:
Повторив эти
операции с участием всех парных сочетаний из
строк и всех
столбцов, получим
подсказок, где
Выделим
подсказки, полученные с участием элементов
-й
строки (их будет
штук),
определим их дисперсию
и по ней — компетентность
-й
строки
.
Основываясь на таких оценках, выберем
наиболее
компетентных строк.
Аналогичным
способом найдем и
наиболее
компетентных столбцов, сформировав в итоге компетентную подматрицу
.
Компетентность
каждого элемента этой подматрицы
.
Описанным
выше методом найдем подсказки от элементов этой подматрицы и получим
окончательный вариант заполнения пропущенного элемента, усреднив подсказки с
их весами
. О доверии к
этому результату можно судить по величине
, где
— дисперсия всех подсказок от
компетентной подматрицы.
5.3. Алгоритм WANGA—0. Если все
признаки в таблице
измерены
в шкале порядка, то пробелы в ней заполняются алгоритмом WANGA-0. Преобразуем все
столбцы, приведя их значения к шкале нормированных рангов. Инвариантным к
преобразованиям шкалы порядка являются суждения такого рода: если
то и
. Отсюда
получается один из трех возможных вариантов подсказки:
, если
;
, если
, и
, если
.
Использование
всех элементов столбцов
и
даст
вариант подсказок, которые
могут не совпадать или даже противоречить друг другу. Оценивать общий
результат будем по следующему правилу. Поставим в соответствие
ранговым номерам
накопителей
. Если подсказка
говорит, что неизвестный элемент равен
, то добавим
единицу в
-й накопитель. Если подсказка
говорит, что искомый ранг больше
,
то
в каждый накопитель с номером, большим
, добавим величину, равную
. Если же подсказка
,
то
в ячейки от первой до
-й добавим величину,
равную
. В
итоге в каждой ячейке накопится величина, отражающая «число голосов» за
принадлежность предсказываемого значения к тому или иному рангу. После
нормировки суммы всех «голосов» к единице неопределенность подсказок можно
оценить по энтропии
где
— доля голосов за ранг
.
Компетентность
-го столбца примем равной
. При «единодушном»
голосовании за один и тот же ранг положительная величина
достигает максимального значения,
равного единице.
Если
в процессе работы со всеми столбцами накапливать подсказки, получавшиеся при
участии элементов
-й
строки, то описанным выше путем можно получить оценку ее компетентности
.
Пользуясь
этими оценками, можно выбрать компетентную подтаблицу
, содержащую
строк и
столбцов. Компетентность
каждого элемента
этой
подтаблицы примем равной
-
Повторим
определение подсказок с участием всех
элементов из
. Теперь для получения общего
результата в накопители добавляем соответствующие доли не от единицы, а от
величины
. Распределение
набранных рангами голосов позволяет найти окончательное решение: пропущенному
значению присваивается ранг, набравший наибольшее количество голосов. Энтропия
полученного распределения голосов
позволит нам оценить степень доверия
к этому результату:
.
5.4. Алгоритм WANGA—N. Рассмотрим
таблицу
, признаки в которой измерены
в шкале наименований. Имя пропущенного элемента
может быть одним
из
имен
, содержащихся
в
-м
столбце, либо новым
-м именем
. Просмотрим все
подсказывающие четверки элементов, стоящие на пересечении строк
и
и столбцов
и
. Подсказку будем искать, исходя из
предположения: если
-й
и
-й элементы
-го столбца названы одним и тем
же именем, то и в
-м
столбце элементы
-й
и
-й строк
должны иметь одинаковые имена, т. е. если
, то
. И наоборот, если
, то
. Найдем подсказки от всех
таких четверок и
выберем подсказки, полученные с участием элементов
-го
столбца. Подсчитаем среди них число подсказок, голосовавших за каждое из
имен
и против каждого
из них
. Вычтем голоса
«против» из голосов «за»:
. Добавив к полученным результатам
величину
, получим
неотрицательных чисел
.
Умножим
их на нормирующий коэффициент
такой, что
при
.
Теперь
можно найти энтропию значений
и через нее компетентность
-го столбца:
.
Собрав
подсказки, полученные с участием всех элементов
-й строки, мы аналогичным способом найдем
ее компетентность
.
Таким
путем выбирается подтаблица из
строк и
,
имеющих
наибольшие компетентности. Компетентность
каждого элемента
этой подтаблицы равна
.
От
каждого элемента подтаблицы получается своя подсказка, которая учитывается в
счетчике голосов «за» и «против» с весом соответствующей компетентности. Если
величины
для всех имен
окажутся отрицательными, то делается вывод о том, что пропущенное имя не входит
в состав
имеющихся имен. Среди имен,
имеющих положительную величину
,
выбирается имя с
, и это имя
вставляется в пустую клеточку таблицы. Мерой доверия к принятому решению
служит энтропия распределения голосов. Если в исходной таблице более чем один
пропуск, то предсказывать можно каждый пропущенный элемент независимо от
других (параллельная стратегия) или поочередно с использованием всех элементов
как исходных, так и предсказанных на предыдущих шагах (последовательная
стратегия). При последовательной стратегии нужно начинать с предсказания того
элемента, для которого получаемая степень доверия максимальна.