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

Проблема обработки и восстановления пропущенных значений в данных свойственна многим практическим задачам. Чаще всего она возникает при идентификации зависимостей, априорная информация о значении параметров которых является неполной. Объективными при­чинами этого являются поломки оборудования при измерении значений технических характеристик процессов, потеря ретроспективной инфор­мации, экстремальный характер функционирования, ограниченный доступ и другие. Субъективные причины указывают на невозможность получения полной и точной информации вследствие влияния психоло­гических аспектов и особенностей памяти.

Адекватная аналитическая обработка информации с пропусками осложняется из-за невозможности построения адекватных математиче­ских моделей и их использования для прогнозирования и решения со­путствующих задач.

1. Изъятие некомплектных строк из таблицы. Строка или столбец таблицы данных называется некомплектным, если в нем отсутст­вует хотя бы одно значение. Метод применяется при большой раз­мерности таблицы и незначительном количестве пропусков.В других случаях метод ведет к смещенности оценок, поскольку строки с пропущенными значениями содержат новую информацию, необхо­димую для анализа.

2. Заполнение пропусков средними значениями. В результате приме­нения такого метода несколько значений одного фактора оказы­ваются одинаковыми, что указывает на его низкую точность.

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

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

5. Метод максимальной правдоподобности и ЕМ-алгоритм [2]. Требует проверки гипотез о распределении значений факторов. Применение осложняется в случае большого количества пропущен­ных значений фактора.

6. Алгоритм ZET [3]. Главная идея алгоритма заключается в подборе „компетентной матрицы”, используя данные из которой дальше на­ходят параметры зависимости, которая используется для прогнози­рования пропущенного значения. Недостатком алгоритма является его локальность, поскольку для вычисления отсутствующего значе­ния используются не все данные таблицы, а лишь их часть. Субъек­тивизм определения размерности „компетентной матрицы” приво­дит к учету неинформативных „шумовых” факторов и смещению оценки неизвестного значения.

7. Алгоритм ZetBraid [3]. Основное отличие от алгоритма ZET за­ключается в определении оптимального размера „компетентной матрицы”. Для оценки „качества” такой матрицы используется дис­персионный метод и метод „креста”. Все другие недостатки, в том числе и статистическая оценка неизвестного значения исключительно на основе корреляционно-регрессионного анализа, оста­ются.

8. Метод Бартлетта [1]. Неитеративный метод, который применя­ется для заполнения пропусков в векторе значений результирующей характеристики в допущении, что значения входных факторов яв­ляются комплектными. Его недостатком является базирование на предположении о линейной зависимости, но отсутствие обоснова­ния применимости метода наименьших квадратов приводит к ошиб­кам.

9. Resampling [1]. Метод имеет те же недостатки, что и предыдущий. Он является итеративным и имеет две модификации. В первой из них некомплектные строки случайным образом заменяют на ком­плектные из исходной матрицы и рассчитывают уравнение регрес­сии. Во втором варианте уравнение регрессии получают из ком­плектной подматрицы, находят оценки неизвестных значений заменяют пропуски на – значения ошибок предыдущих шагов. Ищут уравнение регрессии. После определенного количества итераций значения коэффициентов ус­редняют. Информационная избыточность на фоне малой мощности множества комплектных данных в первой модификации resampling и информационная недостаточность в композиции со случайным формированием значений исходной характеристики не позволяют получать приемлемые результаты. Кроме того, отсутствуют проце­дуры оптимизации метода.

10. Моделирование неполных данных многообразиями малой раз­мерности [4]. Методы, представляющие данное направление, раз­работаны учеными Красноярской школы нейроматематики под ру­ководством проф. Горбаня О.М. Их главная идея заключается в том, что набор точек, который является многообразием при наличии пропусков, позволяет строить линейные и нелинейные приближе­ния - модели, посредством которых возобновляют пропущенные значения. Результаты алгоритмизации этих методов и эксперимен­тальных проверок засвидетельствовали достаточно высокую точ­ность. Проведенные исследования указывают на удовлетворитель­ное функционирование алгоритма при 10-15% пропусков. В то же время, математические изложения базируются на достаточно силь­ных предположениях о распределении входных данных, гладкости функций и обусловленности матрицы исходных значений. К недостаткам следует также отнести сложность реализации и верификации алгоритма.

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

Постановка задачи восстановления пропусков

(1)

Y = F(X) = F(X₁,X₂,...,X_n).                          (7)

А.Н Колмогоров и В.И. Арнольд доказали теорему [5-7] о том, что каж­дая непрерывная функция n переменных, заданная на единичном кубе n-мерного пространства, представима в виде





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

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

Если использовать бинарное представление решений и для формирова­ния популяции решений - элитный отбор, то теорема указывает на сходимость ГА по вероятности.
Для работы ГА необходимо сформировать генеральную и выбороч­ную совокупность хромосом-решений. Хромосома состоит из фрагмен­тов, которые отвечают пропускам в таблице данных:

^{Хr =< пропуск 1, пропуск 2,..., пропуск К > .}

Данные в таблице без учета пропущенных значений нормируем. Если в качестве активационной функции будет использован гиперболический тангенс, то нормирование предпочтительнее осуществлять в отрезок [-1; 1]. Количество хромосом в генеральной совокупности определяется заданной точностью результата, в выборочной - исследователем.

На следующем шаге формируем обучающую и контрольную после­довательность для обучения НС. Предлагается все образы с пропусками считать элементами обучающей последовательности. Для контрольной последовательности их использование является проблематичным, по­скольку невозможно использовать для верификации недостоверные значения. Соотношение мощности множеств образов обучающей и контрольной последовательности может быть разным, на что влияет соотношение образов с пропусками и без пропусков в исходной таб­лице.
Процедура восстановления пропусков будет такой:
Шаг 1. Инициализация К хромосом-решений выборочной последова­тельности.
Шаг 2. К = 1.
Шаг 3. Обучение НС на точках обучающей последовательности, где значения пропусков заполнены значениями К -й хромосомы. При этом решается задача поиска
где W - матрица весовых коэффициентов НС, Р₀ - количество образов в обучающей последовательности.
Шаг 4. Вычисление целевой функции ГА (fitness-function):
где Р_с - количество образов контрольной последовательности. Если G_K < G_min, то переход на шаг 7.
Шаг 5. К = К + 1. Если К>К_max, где K_max- количество элементов в выборочной последовательности, то переход на шаг 6, иначе переход на шаг 3.
Шаг 6. Выполнение процедур кроссовера, мутации, определение и от­бор хромосом следующей эпохи. Переход на шаг 2. Шаг 7. Вывод результатов. Конец.

Экспериментальное моделирование

Для верификации разработанного метода проведена эксперимен­тальное моделирование с использованием Matlab 7.0. В качестве на­чальных данных для моделирования определены две выборки. Данные первой выборки сгенерированы искусственно, значения входных факто­ров имеют равномерное распределение, а результирующая характери­стика получена по формуле:
Вторая выборка является официальной статистикой национального информа­ционного центра энергетики США и содержит данные с 1949 до 2004 года [9], включающие производство твердого топлива, ядерной и другой энергии, импорт нефти и других энергоносителей, экспорт угля, газа, кокса и электроэнергии, потребление твердого топлива, ядерной и дру­гой энергии, а также общее потребление.
Первая выборка насчитывала 25 образов, из которых 20 отнесено в обучающую последовательность и 5 - в контрольную. Моделирование проводилось для разного количества пропусков при прочих равных условиях. Так, количество итераций обучения нейронной сети ограни­чено 50, а значение целевой функции составило 10. При моделировании установлено, что такая точность достигнута не была, и процесс обуче­ния прекращался из-за ограничения на количество итераций. Результаты приведены в табл. 2, где N - количество пропусков, NP - процентное соотношения количества пропусков, F - значение целевой функции, Er-относительная погрешность (в процентах). Зависимость значения отно­сительной погрешности от количества пропусков изображена на рис. 1.
Количество пропусков Рис. 1. Динамика относительной погрешности Статистическая информация, характеризующая состояние энерге­тики США, состояла из 11 входных факторов, одной результирующей характеристики и насчитывала 40 образов. Из них 35 отнесено в обу­чающую последовательность и 5 - в контрольную. Количество итера­ций установлено 150, значение целевой функции - 1. На второй вы­борке итерации прекращались из-за достижения указанного значения ошибки. Максимальное количество итераций, в отличие от первого случая,  достигнуто  не  было.  Результаты  моделирования  приведены  в табл. 3 и на рис. 2.
минут и от количества пропусков не зависело. Полученные результаты свидетельствуют о достаточно высокой точности метода, которую мож­но повысить, если увеличить количество итераций обучения нейронной сети. Динамика относительной погрешности, приведенная на рис. 1 и рис. 2 указывает на то, что пластичность метода, или способность НС к обобщению возрастает при увеличении количества пропусков (до неко­торого предела). Такая тенденция является необычной, ее объяснение требует дополнительных исследований.

Заключение

Разработанный эволюционный метод восстановления пропусков в данных имеет ряд преимуществ. Так, его использование не требует выполнения ограничений на исходную информацию. Таблица исходных данных может иметь произвольную размерность и структуру пропусков.
Перспективным представляется исследование эффективности ис­пользования НС с неитеративными алгоритмами обучения. Необходимо выяснить влияние распределения значений факторов на точность вос­становления пропусков.
Как уже было указано выше, тенденция к увеличению точности идентификации с ростом количества пропусков также требует своего объяснения. С какой точностью возможно восстановления пропусков, если их количество составляет 50% всех значений в таблице данных? Каким условиям должны удовлетворять значения факторов, чтобы точность результатов была максимальной? Ответы на эти вопросы позволят сформировать методику восстановления пропусков с использованием эволюционного подхода.

Литература

1. Злоба Е., Яцкие И. Статистические методы восстановления пропу­щенных данных // Computer Modelling & New Technologies. -2002. - Vol. 6.- № 1. - Pp. 51-61.
2. Хайкин С. Нейронные сеты: полный курс. - М.: “Вильямс”, 2006. —  1104 с.
3. Загоруйко Н.Г. Методы распознавания и их применение. - М.: Сов. радио, 1972. - 216 с.
4. Россиее А.А. Моделирование данных при помощи кривых для восстановления пробелов в данных. В кн. “Методы нейроинфор-матики” / Под ред. А.Н. Горбаня. - КГТУ: Красноярск, 1998. - С. 6-22.
5. Колмогоров А.Н. О представлении непрерывных функций не­скольких переменных суперпозициями непрерывных функций меньшего числа переменных // Докл. АН СССР. - 1956. - Т. 108. - № 2. - С. 179-182.
6. Арнольд В.И. О функциях трех переменных // Докл. АН СССР. - 1957. - Т. 114. - № 4. - С. 679-681.
7. Колмогоров А.Н. О представлении непрерывных функций не­скольких переменных в виде суперпозиции непрерывных функ­ций одного переменного // Докл. АН СССР. - 1957. - Т. 114. - № 5. - С. 953-956.
8. Harti R.E. A global convergence proof for class of genetic algo­rithms.- Wien: Technische Universitaet, 1990. - 136 p.
9. Annual Energy Report 2004 / Energy Information Administration USA: Washington, 2004. - 435 p. http://www.eia.doe.gov/aer
10. Люгер Ф. Док. Искусственный интеллект. Стратегии и методы ре­шения сложных проблем. - М.: “Вильямс”, 2003. - 864 с.