Data mining эволюционное программирование

4.10. Эволюционное программирование

Эволюционное программирование — на сегодня это самая молодая, интересная и наиболее перспективная ветвь data mining. Суть метода заключается в том, что гипотезы о виде зависимости целевой переменной от других переменных формулируются системой в виде программ на некотором внутреннем языке программирования. Если это универсальный язык, то в принципе на нем можно выразить любую четко определенную зависимость.

Все рассмотренные до этого методы отличались одной присущей им всем слабой стороной — а именно, выразительной слабостью используемого ими языка представления обнаруживаемых знаний и, как следствие, узостью класса зависимостей, которые в принципе могут быть этими методами обнаружены. Например, алгоритмы деревьев решений могут получать только классификационные правила в виде формул исчисления высказываний, включающих элементарные операторы отношений ( > , < , =). Линейная регрессия может находить зависимости только в виде линейных формул. И так практически каждый метод KDD привязан к некоторому узкому языку представления знаний. Это существенное ограничение, и единственный кардинальный способ его преодолеть - это попробовать искать законы и правила не в виде формул некоторого фиксированного декларативного формализма, а в виде алгоритмов и программ, выражающих способ вычисления значение целевой переменной, исходя из значений независимых переменных.

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

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

Понятно, что поскольку пространство поиска чрезвычайно широко и внутренний язык поиска также может очень сильно различаться, число принципиально возможных реализаций эволюционного метода также практически неограниченно. Вместе с тем, ввиду сложности и ресурсоемкости метода, только одна из существующих коммерческих систем KDD, а именно программа PolyAnalyst фирмы «Мегапьютер Интеллидженс», предоставляет возможность использовать этот метод для анализа данных. В то же время популярность этого метода непрерывно растет, практически все ведущие научные форумы в области data mining и knowledge discovery in databases включают в программу работы секции по эволюционному программированию.

За возможность обнаружить и формализовать разнообразные многомерные нелинейные зависимости, естественно, приходится платить очень большим объемом производимых вычислений. Эти программы строят сложные формулы, выражающие зависимости в данных, комбинируя более простые формулы, и в конечном итоге находят достаточно точную формулу, выражающую искомое отношение. В качестве примера подобного рода систем мы можем упомянуть FAHRENHEIT (Zytkow and Zhu, 1991), ARE (Shen, 1990), 49er (Zembowicz and Zytkow, 1992). Вероятно одно из самых крайних положений в этом ряду в настоящее время занимает система интеллектуального анализа данных PolyAnalyst (Киселев 1994; Киселев и Арсеньев 1996; Киселев и др., 1997). Ниже мы рассмотрим эволюционное программирование и его возможности на ее примере систем 49er и PolyAnalyst.

Источник

8) Эволюционное программирование

Эволюционное программирование – на сегодня это самая молодая, интересная и наиболее перспективная ветвь data mining. Суть метода заключается в том, что гипотезы о виде зависимости целевой переменной от других переменных формулируются системой в виде программ на некотором внутреннем языке программирования. Если это универсальный язык, то в принципе на нем можно выразить любую четко определенную зависимость.

Вопрос 14. Задачи, модели и проблемы человеко-машинного взаимодействия

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

Отдельно выделим свойства, связанные с ресурсами и особенностями взаимодействия со средой

• Коммуникативность — существование сложной системы коммуникаций со средой в виде иерархии.
• Адаптивность — стремление к состоянию устойчивого равновесия, которое предполагает адаптацию параметров системы к изменяющимся параметрам внешней среды (однако «неустойчивость» не во всех случаях является дисфункциональной для системы, она может выступать и в качестве условия динамического развития).
• Надёжность — способность системы сохранять свой уровень качества функционирования при установленных условиях за установленный период времени.

Несмотря на то, что реальный окружающий нас мир есть бесконечное множество объектов и отношений (связей) между ними, очевидно, простейшим и наиболее удобным будет представление о реальной действительности в виде взаимодействия только двух элементов: в одном из них сосредоточено все то, что нас интересует в настоящее время; в другом – все остальное. Бесконечное множество связей между этими элементами можно свести к одной входной и одной выходной связи, которые являются самыми существенными в определенном отношении. Интересующий нас элемент назовем системой, другой элемент – внешней средой или просто средой. На рис. 1.1 представлена простейшая схема взаимодействия системы и внешней среды.

Рис. 1.1. Схема взаимодействия «система-среда»

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

Элементы, передаваемые системой во внешнюю среду, называются конечными продуктами системы, а из среды в систему – ресурсами.

С точки зрения внешней среды система нужна этой среде как источник удовлетворения своих потребностей в конечных продуктах. Отсюда вывод: новую систему порождает наличие неудовлетворенной потребности – проблемной ситуации.

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

Во взаимоотношениях между системой и средой можно выделить два основных характерных режима:

1. Система полностью удовлетворяет имеющиеся потребности среды. Имеет место функционирование системы.

2. Система не удовлетворяет внешние потребности среды. Возникает потребность в развитии системы путем замены ее глобальной цели.

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

Первый и второй способ деятельности системы будем рассматривать как ее внешнюю функцию. Функция определяется как способ достижения системой поставленной цели.

Задание способа достижения цели – функции системы предопределяют внутреннее устройство, конструкцию системы.

Главной характеристикой внутреннего устройства системы является структура системы – совокупность внутренних связей между элементами системы. Потребности системы в восстановлении элементов, вышедших из строя, в новых элементах, обеспечивающих перестройку структуры в случае развития системы, удовлетворяются внешней средой. Источник восполнения и дополнения элементов структуры системы через внешнюю среду называется внешними условиями.

Система называется устойчивой, если она сохраняет тенденцию стремления к тому состоянию, которая наиболее соответствует целям системы, целям сохранения качества без изменения структуры или не приводящим к сильным изменениям структуры системы на некотором заданном множестве ресурсов (например, на временном интервале). Понятие “сильное изменение” каждый раз должно быть конкретизировано, детерминировано.

Источник

Эволюционное программирование как класс систем Data Mining

Принципы добычи текстов из больших массивов данных. Разработка программ для распознавания образов искусственным интеллектом. Классификация способов Data Mining, метод эволюционного программирования. Изучение криптового языка символьных правил PolyAnalyst.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

HTML-версии работы пока нет.
Cкачать архив работы можно перейдя по ссылке, которая находятся ниже.

Подобные документы

Описание функциональных возможностей технологии Data Mining как процессов обнаружения неизвестных данных. Изучение систем вывода ассоциативных правил и механизмов нейросетевых алгоритмов. Описание алгоритмов кластеризации и сфер применения Data Mining.

Data mining, developmental history of data mining and knowledge discovery. Technological elements and methods of data mining. Steps in knowledge discovery. Change and deviation detection. Related disciplines, information retrieval and text extraction.

Совершенствование технологий записи и хранения данных. Специфика современных требований к переработке информационных данных. Концепция шаблонов, отражающих фрагменты многоаспектных взаимоотношений в данных в основе современной технологии Data Mining.

Основы для проведения кластеризации. Использование Data Mining как способа «обнаружения знаний в базах данных». Выбор алгоритмов кластеризации. Получение данных из хранилища базы данных дистанционного практикума. Кластеризация студентов и задач.

Перспективные направления анализа данных: анализ текстовой информации, интеллектуальный анализ данных. Анализ структурированной информации, хранящейся в базах данных. Процесс анализа текстовых документов. Особенности предварительной обработки данных.

Источник