[ссылки] [литература] [проекты] [программы] [методические указания] [монографии и статьи] [вопросы и ответы] [школы] [учебники]
ENG  |   Карта сайта
Информация
Проект преследует цель популяризации идей применения природных механизмов функционирования для решения задач прогнозирования, оптимизации и поддержки принятия решений

Cписок рассылки
Открыть в новом окне

  1. Введение
  2. Генетические алгоритмы (1)
  3. Генетические алгоритмы (2)
  4. Генетические алгоритмы (3)
  5. Тренды
  6. Полиномиальные тренды
  7. Тригонометрические тренды
  8. Нейронные сети
  9. Метод наименьших квадратов
  10. Метод обратного распространения ошибки
  11. Множественная линейная модель
  12. Нестандартный выпуск. Анкета
  13. МЛМ. Пример расчета
  14. RBF-сеть
  15. Сеть встречного распространения
  16. Первая интерполяционная формула Ньютона
  17. МГУА (1)
  18. Вторая интерполяционная формула Ньютона
  19. Метод Брандона
  20. МГУА (2)
  21. Интерполяционные формулы Гаусса
  22. Интерполяционные формулы Стирлинга и Лагранжа
  23. МГУА (3)
  24. МГУА (4)
  25. Предварительная обработка данных (1)
  26. Предварительная обработка данных (2)
  27. Предварительная обработка данных (3)
  28. Box-counting
  29. Гетероскедастичность
  30. Введение в нечеткую логику
  31. Обобщённый метод наименьших квадратов
  32. Прогнозирование с помощью функций с гибкой структурой
  33. Автокорреляция
  34. Дистрибутивно-лаговые модели (1)
  35. Дистрибутивно-лаговые модели (2)
  36. Дистрибутивно-лаговые модели (3)
  37. Моделирование данных при помощи кривых для восстановления пробелов в таблицах (1)
  38. Нестандартный выпуск. Анонс книги Цейтлина Н.А."Опыт аналитического статистика"
  39. Алгоритм ZET
  40. Алгоритм ZetBraid
  41. Метод эволюционной кластеризации
  42. Эволюционный метод восстановления пропусков в данных
  43. Алгоритмы кластеризации класса FOREL

ЭВОЛЮЦИОННЫЙ МЕТОД ВОССТАНОВЛЕНИЯ ПРОПУСКОВ В ДАННЫХ

 

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

      В общей постановке задача восстановления пропусков в таблицах данных  является такой:

Пусть  - вектор входных факторов  - вектор результирующих характеристик,  - количество экспериментов или периодов ретроспективы,  - матрица исходной инфор­мации. Она имеет пропуски, обозначенные звездочками (табл. 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]. Количество хромосом в генеральной совокупности определяется заданной точностью результата, в выборочной – исследователем.

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

     Процедура восстановления пропусков будет такой:

Шаг 1. Инициализация  хромосом-решений выборочной последова­тельности.

Шаг 2.

Шаг 3. Обучение НС на точках обучающей последователь­ности, где значения пропусков заполнены значениями -й хромосомы.

При этом решается задача поиска

где − матрица весовых коэффициентов НС, − количество образов в обучающей последовательности.

Шаг 4. Вычисление целевой функции ГА (fitness-function):

где − количество образов контрольной последовательности. Если  то переход на шаг 7.

Шаг 5.  Если где − количество элементов в выборочной последовательности, то переход на шаг 6, иначе переход на шаг 3.

Шаг 6. Выполнение процедур кроссовера, мутации, определение и от­бор хромосом следующей эпохи. Переход на шаг 2.

Шаг 7. Вывод результатов. Конец.

 

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

данных может иметь произвольную размерность и структуру пропусков. 

     Перспективным представляется исследование эффективности ис­пользования НС с неитеративными алгоритмами обучения. Необходимо выяснить влияние распределения значений факторов на точность вос­становления пропусков.

     Как уже было указано выше, тенденция к увеличению точности идентификации с ростом количества пропусков также требует своего объяснения. С какой точностью возможно восстановления пропусков, если их количество составляет 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 с.

 

 

Материал составлен на основе статьи автора рассылки «Эволюционный метод восстановления пропусков в данных» (скачать статью PDF, 213 Kb)

Аукцион и интернет-распродажа мебели со склада.

Цифровой синтезатор casio ctk доступен каждому.

Водоемы водная архитектура искусственная архитектура. Супер цены
Сайт создан в системе uCoz