Проект преследует цель популяризации идей применения природных
механизмов функционирования для решения задач прогнозирования,
оптимизации и поддержки принятия решений
ЭВОЛЮЦИОННЫЙ МЕТОД ВОССТАНОВЛЕНИЯ ПРОПУСКОВ В ДАННЫХ
Постановка задачи восстановления пропусков
В общей постановке задача восстановления
пропусков в таблицах данныхявляется
такой:
Пусть
- вектор входных факторов - вектор результирующих характеристик, - количество экспериментов или периодов ретроспективы, - матрица исходной информации. Она имеет пропуски,
обозначенные звездочками (табл. 1).
Таблица 1.
Структура исходной информации
.
.
1
.
.
2
.
.
3
.
.
.
.
.
.
.
.
.
.
.
.
.
p-1
.
P
.
Задача
восстановления пропусков в данных заключается в нахождении
(1)
где
и - векторы значений, полученные по идентифицированным зависимостям
(2)
и
приведенные в табл. 1,
соответственно. Задачу (2) детализируем и перепишем в виде
(3)
или
(4)
Если предположить, что зависимости (2)
являются линейными, то есть
(5)
то
задача восстановления пропусков заключается в нахождении
(6)
где
Решение задач (1)–(6) имеет первый этап,
который, в общем случае, заключается в идентификации зависимостей. Отметим, что
в задаче восстановления пропусков в таблицах данных процедуры идентификации и
оптимизации итеративно повторяются. С некоторыми особенностями решается задача
в зависимости от того, где находятся пропуски:
-
только среди значений входных факторов;
-
только среди значений результирующих характеристик;
-
среди значений и входных факторов, и результирующих характеристик;
-
среди значений таблицы, в которой входные факторы и результирующие
характеристики не выделены.
Модели и метод эволюционного восстановления данных
Предположим, что пропуски имеютсятолькосреди значений входныхфактороврезультирующая
характеристика одна и существуетзависимость
(7)
А.Н Колмогоров и В.И.
Арнольд доказали теорему [5-7] о том, что каждая непрерывная функция n переменных, заданная на единичном кубе n-мерного пространства, представима в виде
где
функции непрерывны, а функции , кроме того, еще и стандартны, т.е. не зависят от выбора функции
. В терминах теории нейронных сетей (НС)
теорема указывает на то, что любая непрерывная функция идентифицируема сетью с
одним, как минимум, скрытым шаром нейронов с нелинейными функциями активации.
Для идентификации (7) в качестве модели выберем прямосвязнуюНС с пороговым алгоритмом обратного распространения
ошибки. Структура сети и ее элементный базис в экспериментах остается
постоянной.
Посколькувходныеобразы для обучениянейронной сети имеют пропуски
значений, то необходиморешить
задачу параметрическойоптимизации.
В качестве метода оптимизациипредложеноиспользоватьгенетический алгоритм (ГА). В работе[8]доказана теорема:
Пусть выполнены следующие условия:
1.Последовательность
популяций генерируема ГА,
− монотонна, т.е.
2.Дляэлементдостижим из посредством мутации и кроссовера, т.е. через последовательность переходов в ряде
структур.
Тогда глобальный оптимум функции отыскивается с вероятностью
1:
Если
использовать бинарное представление решений и для формирования популяции
решений − элитный отбор, то теорема указывает на сходимость ГА по
вероятности.
Для работы ГА необходимо сформировать
генеральную и выборочную совокупность хромосом−решений.
Хромосома состоит из фрагментов, которые отвечают пропускам в таблице данных:
Данные в таблице без учета пропущенных
значений нормируем. Если в качестве активационной функции будет использован
гиперболический тангенс, то нормирование предпочтительнее осуществлять в
отрезок[-1; 1]. Количество хромосом
в генеральной совокупности определяется заданной точностью результата, в выборочной – исследователем.
На следующем шаге формируем обучающую и
контрольную последовательность для обучения НС.Предлагается все образы
с пропусками считать элементами обучающей последовательности. Для контрольной
последовательности их использование является проблематичным, поскольку
невозможно использовать для верификации недостоверные значения. Соотношение
мощности множеств образов обучающей и контрольной последовательности может
быть разным, на что влияет соотношение образов с пропусками и без пропусков в
исходной таблице.
Шаг 3. Обучение НС на точках обучающей
последовательности, где значения пропусков заполнены значениями -й хромосомы.
При этом решается задача поиска
где − матрица весовых коэффициентов НС,
− количество образов в обучающей последовательности.
Шаг 4. Вычисление целевой функции ГА (fitness-function):
где − количество образов контрольной последовательности.
Если то переход на шаг 7.
Шаг 5. Если где − количество элементов в выборочной последовательности,
то переход на шаг 6, иначе переход на шаг 3.
Шаг 6. Выполнение процедур кроссовера,
мутации, определение и отбор хромосом следующей эпохи. Переход на шаг 2.
Шаг 7. Вывод результатов. Конец.
Разработанный
эволюционный метод восстановления пропусков в данных имеет ряд преимуществ.
Так, его использование не требует выполнения ограничений на исходную
информацию. Таблица исходных
данных
может иметь произвольную размерность и
структуру пропусков.
Перспективным представляется исследование
эффективности использования НС с неитеративными
алгоритмами обучения. Необходимо выяснить влияние распределения значений
факторов на точность восстановления пропусков.
Как уже было указано выше, тенденция к
увеличению точности идентификации с ростом количества пропусков также требует
своего объяснения. С какой точностью возможно восстановления пропусков, если их
количество составляет 50% всех значений в таблице данных? Каким условиям должны
удовлетворять значения факторов, чтобы точность результатов была максимальной?
Ответы на эти вопросы позволят сформировать методику восстановления пропусков с
использованием эволюционного подхода.
Литература
1.Злоба
Е., Яцкив И. Статистические методы восстановления пропущенных
данных // ComputerModelling & NewTechnologies. −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 algorithms.–Wien:
TechnischeUniversitaet,
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 с.
Материал составлен на основе статьи автора рассылки
«Эволюционный метод восстановления пропусков в данных» (скачать статьюPDF, 213 Kb)