§ 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. Рассмотрим таблицу
, признаки в которой измерены в шкале наименований. Имя пропущенного элемента
может быть одним из
имен
, содержащихся в
-м столбце, либо новым
-м именем
. Просмотрим все подсказывающие четверки элементов, стоящие на пересечении строк
и
и столбцов
и
. Подсказку будем искать, исходя из предположения: если
-й и
-й элементы
-го столбца названы одним и тем же именем, то и в
-м столбце элементы
-й и
-й строк должны иметь одинаковые имена, т. е. если
, то
. И наоборот, если
, то
. Найдем подсказки от всех
таких четверок и выберем подсказки, полученные с участием элементов
-го столбца. Подсчитаем среди них число подсказок, голосовавших за каждое из
имен
и против каждого из них
. Вычтем голоса «против» из голосов «за»:
. Добавив к полученным результатам величину
, получим
неотрицательных чисел
. Умножим их на нормирующий коэффициент
такой, что
при
. Теперь можно найти энтропию значений
и через нее компетентность
-го столбца:
.
Собрав подсказки, полученные с участием всех элементов
-й строки, мы аналогичным способом найдем ее компетентность
. Таким путем выбирается подтаблица из
строк и
, имеющих наибольшие компетентности. Компетентность
каждого элемента
этой подтаблицы равна
.
От каждого элемента подтаблицы получается своя подсказка, которая учитывается в счетчике голосов «за» и «против» с весом соответствующей компетентности. Если величины
для всех имен окажутся отрицательными, то делается вывод о том, что пропущенное имя не входит в состав
имеющихся имен. Среди имен, имеющих положительную величину
, выбирается имя с
, и это имя вставляется в пустую клеточку таблицы. Мерой доверия к принятому решению служит энтропия распределения голосов. Если в исходной таблице более чем один пропуск, то предсказывать можно каждый пропущенный элемент независимо от других (параллельная стратегия) или поочередно с использованием всех элементов как исходных, так и предсказанных на предыдущих шагах (последовательная стратегия). При последовательной стратегии нужно начинать с предсказания того элемента, для которого получаемая степень доверия максимальна.