Восстановление пропущенных данных в эмпирических таблицах

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

Задача восстановления пропусков в эмпирических таблицах является тра­диционной в классе задач обработки данных, таких, например, как задачи обуче­ния распознаванию образов. Но и во многих других направлениях практической деятельности, в которых так или иначе используется индуктивный подход, эта задача встречается довольно часто. В индуктивных методах делается попытка по отдельным эмпирическим фактам предсказать поведение некоторых параметров в области, которая не была охвачена экспериментом. Здесь будет рассмотрен один из самых распространенных случаев, когда эмпирические данные могут быть представлены в виде таблицы «объект - свойство»:

.                                     

В [1] приведена задача обнаружения закономерностей равенства в таблицах эмпирических данных. В приведенной работе с этой целью применяется метод предельных упрощений (МПУ), основанный на принципе редукции, в соответствии с которым на первом этапе задача предельно упрощается, а затем находится прос­тейшее ее решение.

 Задача обнаружения закономерностей равенства решается последовательно путем решения задачи восстановления функции, указывающей зависимость отдельных столбцов таблицы от всех ее остальных столбцов. Каждый раз используется МПУ в интерпретации решения задачи ОРО, с указанием допустимого «коридора» отклонений и вероятности невыхода из этого «коридора» с заранее заданной надежностью для выборок небольшого объема. Если задача обнаружения и восстановления закономерности равенства будет решена, то решение задачи восстановления пропусков может быть решено при помощи этой закономерности. При невозможности решения задачи восстановления закономерностей равенства с заданными параметрами можно указать величину «коридора», в котором эти параметры могут быть достижимы. Если же «коридор» будет слишком «широким», то об этом будет сообщено пользователю, который может сделать выбор, стоит ли вообще решать задачу обнаружения предлагаемым способом. Этим же методом может быть решена задача обнаружения ошибок, но в этом случае нужно лишь указать на то, что «коридор» оказался слишком «большим», или в некоторой клетке соответст­вующий параметр вышел за пределы «коридора». Обнаружение закономерностей равенства подробно изложено в [1], и поэтому в настоящей статье эта задача рассматриваться не будет.

y = F(x),                                                     (2)

где у - скаляр, X = X(x1,…, x_m) - вектор. Задана исходная выборка векторов (табл. 1). Зададим конкретное значение «ширины коридора» Е, = const. Требуется ответить на вопрос: существует ли в рамках выбранного значения Е, закономерность, связываю­щая отдельные столбцы со всеми остальными столбцами таблицы? Другими слова­ми, нужно ответить на вопрос: существуют ли такие f , связывающие столбцы табли­цы так, чтобы восстановленные зависимости укладывались в «коридор» ±£? При этом, в случае недостаточности линейных членов, т.е. столбцов таблицы, надо ис­пользовать сложные нелинейные свойства, механизм синтеза которых описан в [1]. И если такие зависимости будут восстановлены, то каждый элемент каждого столбца будет предсказуем в рамках выбранного значения Е, . Для этого нужно выбрать соот­ветствующую функцию f , подставить все соответствующие значения x_ij и вычислить значение интересующего нас элемента таблицы.

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

Формирование обучающей таблицы

Эта задача представляет некоторое препятствие на пути применения альфа-процедуры при решении задачи восстановления пропущенных данных. Дело в том, что табл. 1 может иметь не один, а много пропусков. В таких условиях без дополнительных преобразований альфа-процедура работать не может. Требуется преобразовать таблицу так, чтобы выделить в ней фрагмент без пропусков, достаточный для надежного восстановления пропущенных данных. Для этой цели необходимо сделать некоторые предположения. Во-первых, нужно быть уверенным, что в таблице существует достаточное количество строк без пропусков, а во-вторых, нужно быть уверенным, что выделенный фрагмент достаточен для решения задачи.
Табл. 1 такова, что в ней можно беспрепятственно менять местами и строки, и столбцы без какого-либо влияния на векторы Х. Так, объекты, т.е. строки, могут быть произвольно расположены по вертикали таблицы. Не имеет значения и расположение столбцов по ширине таблицы, так как измерения на объектах могут производиться в произвольной последовательности. Больше того, для альфа-процедуры не имеет значения последовательность обработки отдельных столбцов.
Выберем столбец с пропущенными клетками и расположим его первым в левой части таблицы. В этом столбце могут быть незаполненными несколько клеток. Расположим строки таблицы так, чтобы все незаполненные клетки выбранного столб­ца оказались вверху таблицы, а сам столбец оказался первым слева столбцом таблицы. После этого находится столбец с пропущенной клеткой, расположенный ближе всего к первому столбцу. Этот столбец перемещается в правую часть таблицы так, чтобы он стал последним столбцом. При этом все остальные столбцы, кроме первого, перемещаются влево так, чтобы было заполнено место, оставленное столбцом, пере­мещенным в самый крайний правый конец таблицы. После этого снова находится ближайший к первому столбцу столбец с пропуском, и снова он перемещается в пра­вый конец таблицы. При этом все остальные столбцы с пропусками перемещаются влево до заполнения места перемещенного вправо столбца. Такая процедура продол­жается до тех пор, пока все столбцы с пропусками не сосредоточатся в правой части таблицы (табл. 2). В этой таблице строки и столбцы пронумерованы цифрами от 1 до 10. Столбец с пропусками, которые надо восстановить, обозначен цифрой 1. Пропуски этого столбца сосредоточены в верхней части таблицы (строки 1, 2, 3), строки 4, 5, 6, 7 не имеют пропусков. Все столбцы с пропусками сосредоточены в правой части таблицы (столбцы 7, 8, 9, 10). Пропуски имеются и в строках 8, 9, 10. В строках 1, 2, 3 в дополнение к пропускам в первом столбце имеются еще и пропуски в других столб­цах. В результате всех перестановок строк и столбцов порождается обучающая таб­лица, очерченная жирной линией. В этой таблице в первом столбце три строки с пропусками. Поэтому таблица обучения ограничена столбцами 2, 3, 4, 5, 6 и строками 4, 5, 6, 7, 8, 9, 10. В этой таблице в первом столбце расположен искомый параметр у. В результате обучения восстанавливается зависимость (2), т.е. синтезируется прост­ранство, размерность которого в каждом конкретном случае может быть различной [1]. Кроме того, зависимость может определяться различными столбцами, например, y = F(x₂, x₄, x₆) или y = F(x₃, x₅) и др. Когда такие зависимости будут восстановлены, появится возможность прогнозировать искомый параметр в клетках (1, 1; 1, 2; 1, 3), т.е. заполнить пропущенные клетки конкретными предсказываемыми числами.

Восстановление пропусков

На первом этапе выбирается столбец с пропуском, который предстоит вос­становить. Этот столбец помещается на место первого слева столбца таблицы. После этого проводятся все описанные ранее операции по формированию обучающей таб­лицы, в результате чего будет получена сокращенная, но полная табл. 2.

Таблица 2

По этой таблице восстанавливается зависимость (2) относительно выбранного столбца и выбранной строки. По этой зависимости могут быть восстановлены все пропуски, имеющиеся в выбранном столбце. После этого таблица перестраивается так, чтобы слева оказался тот столбец, в котором находятся подлежащие вос­становлению пропуски. Относительно нового столбца формируется обучающая таб­лица, и по ней восстанавливается функция (2) для столбца с пропусками. Если МПУ применяется в полном объеме, т.е. соблюдаются все рекомендации относительно объема обучающей выборки, разделяющей силы и размерности пространства, то в результате восстановления значения пропусков будут обладать установленными заранее значениями качества и надежности [1]. Если же восстановленные значения не будут укладываться в заданный «коридор» ± £,, то частота выхода из этого «ко­ридора» будет определять качество восстановления пропусков. В этом случае мож­но ослабить требования к качеству восстановления, «расширив коридор» ± £, , и тогда частота выхода за пределы нового «увеличенного коридора» будет определять новое качество восстановления. Увеличение «ширины коридора» будет повышать вероятность попадания в него, но это будет относительным повышением качества, так как при этом сильно расширяется свобода выбора. Здесь, по-видимому, дейст­вует такое общее правило: расширение свободы выбора относительно улучшает сис­тему. В [4] показано, что «величина коридора», определяемая величиной ± £, , име­ет оптимальное значение при фиксированных значениях размерности пространства и длины обучающей выборки. При малых значениях Е, качество восстановления низкое. Низкое оно и при слишком больших значениях Е, . Другими словами, при низкой свободе выбора низкое и качество. Расширение свободы выбора сначала по­вышает качество, а затем начинает ухудшать его. Между качеством восстановления и свободой выбора \Е) должен соблюдаться компромисс, обеспечивающий опти­мальное значение качества. Такую закономерность можно осторожно экстраполи­ровать и на более широкую область физических и даже социальных явлений: огра­ничение свободы снижает качество системы, но и чрезмерное ее увеличение к добру не приводит. Существует оптимальное значение свободы выбора.

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

Каждой серии экспериментов соответствует своя таблица (табл. 1), а каждой такой таблице может быть поставлено в соответствие пространство с координатами x₁, x₂,..., x_m, в котором вся серия экспериментов представлена векторами X = X(x₁,..., x_m). В задачах обучения распознаванию образов векторы Х представляют собой обучающую выборку, а каждая составляющая этих векторов есть свойство объектов, подлежащих распознаванию.

Ранее был использован прием для получения оценки пропущенных данных, использующий аналогии объектов, т.е. аналогии строк таблицы. Можно для этой же цели использовать аналогии свойств, т.е. столбцов таблицы. Для этой цели надо каждый столбец рассматривать  как  вектор,  составляющими  которого  яв­ляются значени я  одного  свойства, измеренного на одном объекте. Такой вектор X'(x ₁^' ,...,x_l ^') имеет размерность, равную l, каждая его составляющая представляет собой число, определяющее значение свойства x_i, измеряемого на определенном объекте.Так же, как и в предыдущем случае, предполагается, что в столбце, опреде­ляющем собой некоторое свойство, отсутствует измерение. Тогда из таблицы уда­ляется строка с пропущенным измерением, т.е. удаляется некий объект. При этом таблица уменьшается в размерности, но становится полной. Поместим столбец с пропущенным измерением в начало координат и будем рассматривать пространст­во с координатами x₁, …,x_l. В этом пространстве каждый столбец будет представлен вектором, удаленным от начала координат, т.е. от искомой строки, на некоторое расстояние. Это расстояние определяет «похожесть» каждого столбца на искомый, т.е. определяет аналогию каждого столбца со столбцом, в котором обнаружен про­пуск. В этом столбце вычеркивается одна строка, т.е. один объект, но без этого объекта таблица оказывается без пропусков.
Так же, как и ранее, определяется бли­жайший столбец, в котором присутствуют все измерения, и в нем находится кле­точка, соответствующая пропуску. Это и будет искомой оценкой пропущенного значения параметра. Среди аналогичных свойств для оценки параметра может быть выбрано одно, обладающее максимальной аналогией, а могут быть выбраны не­сколько свойств, и тогда используется одно из правил принятия коллективных ре­шений. Как и ранее, оценка может быть как по полной, так и по частичной аналогии.
Оценка по аналогии объектов, как правило, точно не совпадает с оценкой по аналогии свойств. В этом случае в качестве окончательного результата может быть принята усредненная оценка, которая будет представлять собой среднее значение оцениваемого пропущенного значения искомого параметра. Усреднение оценок можно осуществлять и с учетом меры аналогии, учитывающей либо отличие объектов, либо отличие свойств. Если аналогия объектов выше аналогии свойств, то больший вес придается оценкам, полученным по аналогии объектов, и наоборот.

1. Васильев В.И., Ланге Т.И., Шевченко А.И. Обнаружение и моделирование закономерностей сходства, равенства и порядка // Искусственный интеллект. - 2001 - № 3. - С. 26-39.
2. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. - Новосибирск: Изд-во Ин-та математики, 1999. - 270 с.