Содержание к диссертации
Введение
ГЛАВА 1. Методы и средства интеллектуального анализа данных 10
1.1. Обоснование применения автоматизированной выработки правил для увеличения эффективности процесса принятия решений 10
1.2. Типы возможных закономерностей в методологии обработки данных 12
1.3. Методы поиска логических закономерностей 17
1.4. Средства интеллектуального анализа данных 19
1.5. Генетический алгоритм как средство интеллектуального анализа данных 27
1.5.1. Обоснование выбора генетического алгоритма как средства Data Mining для автоматического выявления логических правил 28
1.5.2. Основные понятия и принципы генетических алгоритмов 29
1.6. Выводы 34
ГЛАВА 2. Автоматизированный поиск элементарных событий и логических закономерностей генетическим алгоритмом 36
2.1. Анализ способов классификации в задачах САПР 36
2.1.1. Процедура предъявления правил для классификации 39
2.1.2. Правила классификации 40
2.1.3. Варианты описания объектов 41
2.1.4. Байессовская процедура классификации 42
2.2. Методы поиска логических закономерностей для решения задач САПР 45
2.2.1. Деревья решений 46
2.2.2. Алгоритм CLS 55
2.2.3. Алгоритм Кора 56
2.2.4. Случайный поиск с адаптацией 57
2.3. Основные характеристики генетических алгоритмов 59
2.4. Различные варианты генетического алгоритма в качестве инструментариев интеллектуального анализа данных 67
2.4.1. Комбинированный генетический алгоритм 68
2.4.2. Поколенческий генетический алгоритм 69
2.4.3. Адаптивный генетический алгоритм 71
2.4.4. Многоуровневый генетический алгоритм 73
2.5. Генетический алгоритм для определения элементарных событий и поиска логических закономерностей 75
2.6. Выводы 80
ГЛАВА 3. Алгоритм представления логических закономерностей и информационная реализация генетического алгоритма для поиска логических закономерностей 81
3.1. Информационная и объектно-ориентированная модели 81
3.1.1. Разработка объектно-ориентированной модели для описания генетического алгоритма 85
3.1.2. Алгоритм формирования логических закономерностей в рамках объектно-ориентированной модели 86
3.1.3. Разработка структуры Базы Данных для хранения промежуточных данных и результатов работы генетического алгоритма 89
3.2. Осуществление вывода и формирование логических закономерностей в терминах конъюнкции элементарных событий 95
3.3. Выводы 98
ГЛАВА 4. Разработка программного и информационного обеспечения генетического алгоритма 100
4.1. Программные средства и СУБД для реализации генетического алгоритма 100
4.2. Конструирование генетического алгоритма для поиска логических закономерностей с помощью разработанной системы классов 103
4.3. Программная реализация генетического алгоритма для поиска логических закономерностей 106
4.3.1. Создание соединения с Базой Данных проекта 107
4.3.2. Инициализация характеристик генетического алгоритма 109
4.3.3. Формирование признаков классов и предобработка данных 110
4.3.4. Поиск логических закономерностей с помощью генетического алгоритма 112
4.3.5. Программное формирование логических правил 114
4.4. Выводы 118
Заключение 120
Список Литературы
- Обоснование применения автоматизированной выработки правил для увеличения эффективности процесса принятия решений
- Анализ способов классификации в задачах САПР
- Информационная и объектно-ориентированная модели
- Программные средства и СУБД для реализации генетического алгоритма
Введение к работе
При конструкторской и технологической подготовке производства новых изделий, создании технических, программных и информационных систем объемы проектирования постоянно увеличиваются, что требует больших затрат и времени в проектно-конструкторских и технологических разработках. Повышение эффективности связано с использованием систем автоматизированного проектирования (САПР). Проектировщик пользуется средствами САПР для выполнения конкретной проектной процедуры или получения сведений, необходимых для принятия обоснованных решений. Эти функции не могут быть выполнены без специального программного (ПО) и информационного (ИО) обеспечения. При этом перед проектировщиком встает задача выбора подходов и методов, которые целесообразно использовать, сокращения области получения приемлемых решений, выявления факторов, влияющих на их качество. Однако очень часто эта проблема решается на уровне здравого смысла, что связано с неполнотой и нечеткостью, имеющихся на момент начала проектных работ, знаний. Поэтому актуальной становится задача автоматизированной выработки правил, позволяющих повысить эффективность процесса принятия решений на всех этапах проектирования. Именно решению этой задачи с использованием методов интеллектуального анализа данных и посвящена данная диссертационная работа.
Интеллектуальный анализ данных (Data Mining) представляет собой процесс обнаружения в данных ранее неизвестных, нетривиальных, практически полезных, доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Одной из задач, решаемых с помощью методов интеллектуального анализа данных, является поиск логических закономерностей в той или иной форме (деревья решений, конъюнкция элементарных событий, система продукций и т.д.).
Существует целый ряд алгоритмов и систем, позволяющих строить логические правила. Однако, они не лишены определенных недостатков, к которым можно отнести:
1. не решается вопрос о точности и полноте правил;
2. ограниченный размер правил (в среднем не более 4 элементарных событий);
3. проблема определения элементарных событий;
4. специальную подготовку пользователя для предобработки и кодирования данных.
В связи с этим становится актуальной задача разработки механизма построения правил, лишенного этих недостатков.
В качестве такого механизма в работе предлагается использование генетического алгоритма (ГА), который выявляет правила произвольной длины (количество элементарных событий, входящих в правило) с заданной точностью и полнотой (для класса решений), и который определяет автоматически элементарные события в ходе своего выполнения.
Цель работы. Целью настоящей работы является разработка и реализация алгоритма для повышения эффективности поиска логических закономерностей в наборах данных на всех этапах проектирования, основанного на генетическом алгоритме и включающего в себя механизм предобработки данных, направленной на сегментацию найденных закономерностей, с целью выявления элементарных событий. Разработанный алгоритм поиска должен производить вывод логических закономерностей в терминах элементарных событий с определением их точности и полноты. Научная новизна полученных в диссертации результатов теоретических и экспериментальных исследований заключается в следующем:
1. На основе анализа методов для поиска логических закономерностей, предложено использование подхода, основанного на применении ГА, позволяющего выделять элементарные логические события, получаемые в результате предобработки данных с последующим формированием системы логических правил с определением их точности и полноты.
2. Разработан ГА, его структура и вид операций для построения системы правил с заданной точностью и полнотой.
3. Разработана система классов и информационная модель для представления генетических алгоритмов.
Практическая ценность. Практическая ценность полученных результатов заключается в следующем:
1. Исследованы структура и основные характеристики ГА для выявления логических закономерностей.
2. На основе разработанных информационной и объектно-ориентированной моделей, определена структура базы данных приложения для хранения описаний ГА, а также найденных логических правил, полученных с их помощью.
3. Реализовано приложение, осуществляющее автоматизированный поиск закономерностей в наборах данных в зависимости от информации, хранящейся в базе данных, и требований, предъявляемых пользователем. Основные практические результаты работы использованы в ООО «Северные ветры дистрибьюшн» при разработке рекомендованного плана отгрузок товара с заводов на дистрибьюторские склады.
На основе разработанного ГА для поиска логических закономерностей был разработан программный продукт, предназначенный для создания оптимального плана отгрузок товара с заводов на дистрибьюторские склады и последующей оптимизации складских остатков. Применение данного продукта, на основе Генетического Алгоритма, позволило выявить Профицит и Дефицит товара на складе, что привело к значительной оптимизации складских остатков, сведя складские объёмы к нормативным величинам с запасом продаж на одну неделю вперёд.
Технический эффект от внедрения результатов диссертационной работы оценивается нормализацией остатков на складе, равномерным распределением мощностей заводов на отгрузку товара дистрибьюторам, достоверностью планов отгрузок и своевременностью доставки товара на склады дистрибьюторов.
Выполненные сравнительные испытания предложенного продукта, на основе Генетического Алгоритма и традиционных вычислений формул на листах среды MS Excel показали, что применение предложенного продукта обеспечивает:
1. Значительное снижение трудоемкости вычисления плана отгрузок в 1.5-2 раза.
2. Уменьшения затрачиваемого времени на разработку такого плана в 2-3 раза и исключения ошибок, связанных с человеческим фактором. На защиту выносятся следующие основные положения:
1. Использование генетических алгоритмов как средства интеллектуального анализа данных при построении логических правил, используемых в задачах проектирования.
2. Разработанный ГА, проводящий предобработку данных, заключающуюся в их сегментации и выделении наиболее значимых значений признаков и их сочетаний для выявления логических закономерностей.
3. Разработанная информационная модель ГА для хранения признаков классов и логических закономерностей в базе данных и объектно-ориентированная модель, применимая для описания широкого класса генетических алгоритмов
4. Разработанное программное и информационное обеспечение приложения для создания и использования ГА для выбора логических закономерностей в задачах проектирования.
Апробация работы. Результаты работы докладывались на научно-технических конференциях студентов, аспирантов и молодых специалистов МИЭМ (Москва, 2003-2006 гг.); научно-практических семинарах «Новые информационные технологии» (Москва, 2006 гг.). Результаты работы публиковались в журналах "Информационные технологии" №7 (Москва, 2005 гг.), "Качество и ИПИ (СА1)-технологии" №1 (Москва, 2006 гг.), "Технологии ЭМС (Электромагнитной совместимости)" №1 (Москва, 2006 гг.) и сборнике научных трудов "Проектирование телекоммуникационных и информационных систем" (Москва, 2006 гг.).
Публикации. Материалы, отражающие основное содержание диссертации, изложены в трех статьях и пяти тезисах докладов Объем работы. Общий объем диссертации 130 стр. машинописного текста, включая список цитируемой литературы, и содержит 29 иллюстраций и 7 таблиц. Работа состоит из введения, четырех глав, заключения и списка литературы, включающего 104 работы отечественных и зарубежных авторов.
Обоснование применения автоматизированной выработки правил для увеличения эффективности процесса принятия решений
Сфера применения проектирования САПР постоянно увеличивается, что требует развития методов информационного обеспечения и новых подходов к поиску необходимых данных на всех этапах проектирования.
Под проектированием понимается комплекс работ исследовательского, расчетного и конструкторского характера, связывающие научные исследования и практическую реализацию новых или реконструкции старых технических объектов. При этом в качестве объектов проектирования могут выступать как изделия, так и процессы (технологические или вычислительные).
От сроков и качества проектирования в значительной степени зависят сроки внедрения и качество готовой продукции. Современная мировая тенденция - значительное сокращение сроков проектирования. Повышение эффективности связано с использованием САПР. Автоматизированное проектирование - это такой способ проектирования, при котором все этапы проектирования осуществляются при помощи компьютера.
Перед проектировщиком встает задача выбора подходов и методов, которые целесообразно использовать, сокращения области получения приемлемых решений, выявления факторов, влияющих на их качество. Однако очень часто эта проблема решается на уровне здравого смысла, что связано с неполнотой и нечеткостью, имеющихся на момент начала проектных работ, знаний. Поэтому актуальной становится задача автоматизированной выработки правил, позволяющих повысить эффективность процесса принятия решений на всех этапах проектирования. Именно решению этой задачи с использованием методов интеллектуального анализа данных и посвящена данная диссертационная работа.
В последующих параграфах первой главы будут рассмотрены основные методы и средства Data Mining. При анализе таких подходов будет показано, что решение задач классификации по выявлению признаков и наборов правил, характеризующих группу, имеют ряд значительных недостатков. В связи с этим становится актуальной задача разработки механизма построения правил, лишенного этих недостатков.
В качестве такого механизма в работе предлагается использование генетического алгоритма (ГА).
Совершенствование технологий записи и хранения данных привело к стремительному развитию хранилищ информации и росту объемов данных в этих хранилищах. Развитие хранилищ происходит в самых различных областях (производственной, коммерческой, медицинской, научной и т.д.). Они обладают большими потенциальными возможностями по извлечению практически полезной аналитической информации, которая в последствии послужит основой для выявления скрытых закономерностей, тенденций и приведет к нахождению новых решений. При этом подразумевается, что данные могут быть разнотипными (количественными, качественными, текстовыми) и многомерными. Существует проблема, заключающаяся в том, что могут встречаться пробелы в данных (не внесенные или утерянные данные), а так же малый объем или полное отсутствие априорной информации, как правило, при этом подразумевается высокая сложность в определении зависимостей в наборах данных. Все большую актуальность приобретают системы обработки информации, которые позволяют не просто складировать данные, но и позволяют осуществлять их анализ и предобработку данных, находить скрытые закономерности, производить прогнозирование рядов данных и выдавать результаты в доступном для человека виде.
Анализ способов классификации в задачах САПР
Согласно актуальности данной работы, рассмотренной в Главе 1, для повышения эффективности процесса принятия решений необходимо автоматически вырабатывать отношения в виде конъюнкции элементарных событий для последующей классификации объектов. На основе полученных логических закономерностей будет производиться классификация объектов при решении различных задач САПР. При этом полученные отношения будут порождать разбиение множества решений, для которого они определены, на непересекающиеся классы. При выполнении свойства рефлексивности, симметричности и транзитивности такие отношения называется отношениями эквивалентности. Если же выполняются только отношения рефлексивности и симметричности, то отношение называется отношением толерантности. Объекты, попадающие в общий класс эквивалентности в известном смысле неразличимы, то есть одинаковы. Отношение же толерантности выделяет сходные, но все же различающиеся объекты. Поэтому упрощенно класс/образ можно определить следующим образом. Объекты, для которых выполняется отношение эквивалентности или по крайней мере толерантности (по некоторому набору свойств), в своей совокупности составляют класс/образ.
Как правило, при решении задачи САПР по классификации различных объектов имеется набор или алфавит заданных классов: А = {А1, ...,Ат}. (2.1) Где Ai - отдельный класс, т - общее число классов. Каждый класс может быть представлен некоторым набором объектов или реализаций. Совокупность различных реализаций для всех классов образует множество возможных реализаций: В = {Ы ЬТ}. (2.2) В основном Т » т.
Выше при определении понятия класса указывалось, что в класс объединяются объекты, имеющие эквивалентные или толерантные свойства. Все эти свойства и составляют признаки класса. Обычно признаки задаются своими количественными значениями. Для простоты считают, что все классы характеризуются одним и тем же количеством признаков N. Если для некоторого класса признаки отсутствуют, то как правило им задают нулевые значения или значение null. Обозначим совокупность признаков: Х={х1, ...,xNJ. (2.3) Числовые значения признаков изменяются в некоторых пределах. При дискретном рассмотрении, каждый признак Хк может принимать одно значение из совокупности.
Рассматриваемая задача классификации графически проиллюстрирована на рисунке 2.1 ячейкой А, которая включает в себя те задачи, в которых классификация должна вырабатываться на основе единственной выборки, при условии, что каждый объект задается единственной точкой в евклидовом пространстве, при этом для построения правил классификации может потребоваться полное описание объекта [22,52]. Задачу классификации можно охарактеризовать тремя параметрами: способом, которым представляется обучающее множество; типом правила классификации, которое должен построить классификатор; видом описания классифицируемых объектов. Данные параметры будут раскрыты в следующих параграфах, с учетом поставленных в работе задач.
В работе такая процедура предъявления рассматривается двумя случаями: 1. Классификация на основе единственной выборки. 2. Классификация на основе последовательности выборок.
В случае единственной выборки: для принятия обоснованных решений пользователю, после генерации системой логических закономерностей, необходимо выбрать несколько объектов из известных классов и предъявить их системе. На основе наблюдений этой выборки находится наилучшее правило классификации, применяемое затем к объектам, которые предопределяются этой выборкой, но в ней не содержатся. Само правило классификации далее не меняется, даже когда наблюдается ошибка классификации.
При использовании последовательности выборок, информация, получаемая первоначальной выборкой, является лишь предварительной, и учитывается при построении соответствующего правила классификации. Затем берется новая выборка (возможно из одного объекта), к ней применяется имеющееся правило классификации. Оценивается результат и если нужно отыскивается новое правило. Эту процедуру можно повторять сколько угодно, пока не будет удовлетворен некоторый критерий работы правила.
Информационная и объектно-ориентированная модели
Для автоматизированного поиска логических закономерностей в исходных наборах данных была разработана информационная система, состоящая из следующих основных блоков: 1. Основной блок поиска логических закономерностей 2. Блок Запросов к Базе Данных 3. База Данных (Промежуточные данные) 4. База Данных (Итоговые данные) 5. Блок Формирования логических правил
Наглядно выше изложенное можно представить рисунком: Основной блок поиска логических закономерностей - основной рабочий модуль всей системы. Данный блок позволяет заносить исходную обучающую последовательность с возможнбостью дополнять ее новыми признаками для каждого класса. С помощью блока запросов он осуществляет сохранение наиболее интересных наборов данных или позволяет загружать ранее сохраненные примеры. После загрузки признаков классов (инициализации данных) запускается обработчик исходных данных. Над данными производят операции мутации, редукции, выбор родительских пар, миграция и кроссовер. В результате Блок поиска производит сохранение кодовых последовательностей, с наилучшими показателями целевой функции, в Базе Данных. Данный блок способен сохранять наиболее удачные примеры кодовых последовательностей под именами, указанными пользователем. Как было сказано выше, на начальных этапах инициализации данных возможна загрузка сохраненных примеров. Блок автоматизированного поиска логических закономерностей наглядно можно представить следующим рисунком:
Блок запросов обеспечивает формирования запросов к Базе Данных, результаты выполнения которых после последующей предобработки и кодирования сохраняются в таблицах. Для работы с записями использовались комбинированные запросы в синтаксисе SQL. Каждая СУБД вносит свои изменения в синтаксис SQL, но в основных понятиях он не изменен [54]. Запрос определяет: поля, которые следует обработать, содержащие эти поля таблицы, диапазон записей, а при получении записей -порядок их представления. При получении записей S L-onepaTop возвращает их в виде динамического набора. Динамический набор представляет собой обновляемый набор записей, содержащий указатели на базовые записи.
База данных системы разделена на две составляющие. Первая из них служит для хранения результатов работы программы - особей, удовлетворяющих критериям отбора. Во второй хранятся промежуточные данные. Промежуточные данные рассматриваются как исходные данные, сохраненные ранее обучающие выборки и промежуточные таблицы для внесения изменений во время начальной установки признаков особей.
Таблицы или отношения базы данных подсистемы проектировались таким образом, чтобы исключить появление аномалий обновления и нарушений целостности базы. Для этого использовался процесс нормализации, представляющий собой формальный метод анализа отношений на основе их первичного ключа (потенциальных ключей) и существующих функциональных зависимостей [9,12,30]. Он включает ряд правил, которые могут применяться для проверки отдельных отношений таким образом, чтобы вся база данных могла быть нормализована. Если некоторое требование не удовлетворяется, то нарушающее данное требование отношение должно быть декомпозировано на отношения, каждое из которых в отдельности удовлетворяет всем требованиям нормализации. Тем самым, формат отношений становится все более строгим и менее уязвимым по отношению к аномалиям обновления. В работе используемые таблицы приводились к нормальной форме Бойса-Кодда (НФБК) [30], которая наряду с исключением частичных или транзитивных зависимостей от первичного ключа, также учитывает функциональные зависимости, в которых участвуют все потенциальные ключи отношения, т.е. отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом.
Блок Формирования логических правил открывает сохраненные особи из Базы Данных. Данные особи удовлетворяют условия останова работы генетического алгоритма. Проверка таких условий осуществляется в блоке автоматического поиска наилучших решений. Данные особи представляются в виде элементарных конъюнкций и отображаются на экране сохраненным в Базе Данных сохраненным отчетом. В качестве средства реализации использовалась База Данных с реляционной структурой.
Программные средства и СУБД для реализации генетического алгоритма
Для реализации предполагаемого алгоритма по поиску логических закономерностей использовался язык программирования высокого уровня Visual Basic, а в качестве Базы Данных использовалась среда MS Access 2000, что обусловлено ее широким распространением, простотой использования и доступностью. Среду MS Visual Basic 6 следует рассматривать как одно из возможных средств реализации, с помощью которого удалось продемонстрировать особенности предлагаемого подхода.
В данной работе среда Visual Basic 6 рассматривается как основной подход компании Microsoft к разработке приложений с применением Баз Данных для конечного пользователя [9,83]. В настоящее время наиболее используются РСУБД Jet (Access) [44] или Microsoft SQL Server. При этом импортирование данных и внутренних структур из MS Access в любую другую систему предусмотрено, почти во всех современных Базах Данных.
Выбранное для реализации средство создания Баз Данных Jet - MS Access обладает визуальным интерфейсом для настройки таблиц, индексов, запросов и отношений. С помощью встроенного конструктора создавались все таблицы и отношения между ними в данной работе. Нормализацию данных в разработанной Базе Данных добились за счет исключения избыточной информации из самой базы данных, созданием подчиненных таблиц и внешних ключей реляционной связи.
Среда Visual Basic 6 позволила упростить создание пользовательского интерфейса за счет встроенных средств визуализации. Такие средства представлены интегрированной средой разработки {Integrated Development Environment - IDE) Visual Basic. Примером может служить PictureBox, MS FlexGriad Control, TextBoxes, CommandButtoms и Tekst-Labels. При этом остается возможным и создание своих собственных элементов управления с помощью технологии ActiveX[25].
При создании СУБД был реализован программный код для работы с DAO (Data Access Object). Все объекты DAO функционируют как внутренние представление физических данных, сохраненных в базе данных определенного типа, управляемой ядром базы данных. Такие объекты DAO представлены как определенные переменные в памяти компьютера [29]. Перебор записей (отображение информации), хранящейся в Базе Данных, осуществляется с помощью набора записей Recordset. При этом доступ к информации осуществляется вплоть до каждого поля каждой записи.
Для получения хранимой информации или осуществления записи в Базу Данных применяется свойство RecordSource, в параметрах которого моно указывать оператор SQL или запрос Query , хранимый в области запросов БД. Другим подходом может служить метод Execute соединения {Connection). Следует отметить возможность использования и комбинированных запросов SQL [12,93]. С примерами таких запросов можно ознакомиться в Главе 4. Данные могут возвращаться как в статистическом виде, так и динамическом виде.
Обрабатываемую информацию можно графически отображать с помощью стандартных средств управления среды Visual Basic 6 [20,21]. Примером может служить элемент PictureBox. На области данного элемента с помощью методов Pset, Line, Print и т.д. реализовано отображение особей и признаков каждого класса в различных цветовых представлениях на данном элементе управления.
Наглядное представление найденных логических закономерностей в виде конъюнкции элементарных событий (признаков), хранимых в Базе Данных, можно осуществить с помощью упрощенного редактора отчетов среды MS Access - Crystal Report для каждого правила каждого класса [3]. Создание данного отчета не потребовало написание каких-либо сложных запросов к Базе Данных, так как все основные операции по виду представления данных задавались в коде программы [26,33,48]. Таким образом, использование вышеизложенных возможностей программной среды Visual Basic 6 и среды MS Access 2000 позволило осуществить отладку и реализацию генетического алгоритма для поиска логических закономерностей. При этом стоит отметить, что использование MS Access 2000 также позволяет с помощью методологии DAO достаточно легко осуществить переход к другим СУБД (таким как MS SQL, Interbase, Oracle и т.д.) в том числе и для анализа информации в клиент - серверных базах данных [97,98].
