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

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

От каждого элемента подтаблицы получается своя подсказка, которая учитывается в счетчике голосов «за» и «против» с весом соответствующей компетентности. Если величины  для всех имен окажутся отрицательными, то делается вывод о том, что пропущенное имя не входит в состав  имеющихся имен. Среди имен, имеющих положительную величину , выбирается имя с ,  и это имя вставляется в пустую клеточку таблицы. Мерой доверия к принятому решению служит энтропия распределения голосов. Если в исходной таблице более чем один пропуск, то предсказывать можно каждый пропущенный элемент независимо от других (параллельная стратегия) или поочередно с использованием всех элементов как исходных, так и предсказанных на предыдущих шагах (последовательная стратегия). При последовательной стратегии нужно начинать с предсказания того элемента, для которого получаемая степень доверия максимальна.