Содержание к диссертации
Введение
1. Обзор ситуации, типовых решений и методов извлечения знаний 11
1.1. Проблема извлечения знаний в больших информационных системах 11
1.1.1. Проблемы обработки информации 11
1.1.2. Понятие знания 13
1.1.3. Различные типы знаний 14
1.2. Методы извлечения знаний 16
1.2.1. Классификация методов 16
1.2.2. Методы поиска ассоциативных правил 17
1.2.3. Методы классификации 21
1.2.4. Методы кластеризации 23
1.3. Программные системы извлечения знаний 24
1.4. Методы эволюционных вычислений 32
1.4.1. Генетические алгоритмы 34
1.4.2. Генетическое программирование 37
1.4.3. Эволюционное программирование 41
1.4.4. Эволюционные стратегии 43
1.5. Цель и задачи исследования 44
2. Разработка генетических алгоритмов построения ассоциативных правил и классификаций 47
2.1. Определение ассоциаций данных 47
2.2. Прямые и обратные задачи на базах данных 54
2.3. Построение ассоциаций путем генерации запросов 56
2.3.1. Использование управляемых запросов 56
2.3.2. Применение генетического программирования 59
2.3.3. Применение генетического алгоритма 67
3. Программно-алгоритмический комплекс построения и исследования ассоциаций данных 74
3.1. Архитектура системы эволюционных вычислений 74
3.1.1. Ядро системы 77
3.1.2. Модуль агрегирования базы данных 77
3.1.3. Модуль генетического алгоритма 79
3.1.4. Модуль оценки индивидуумов 80
3.1.5. Модуль выделения ассоциативных правил 81
3.1.6. Семантическая метабаза данных 83
3.1.7. Агент 85
3.2. Реализация системы эволюционных вычислений 87
3.2.1. Описание структуры программы 87
3.2.2. Реализация объектов базы данных 88
3.2.3. Реализация объектов генетического алгоритма 92
3.2.4. Реализация абстракций действия 94
4. Исследование системы эволюционных вычислений 96
4.1. Описание экспериментальной базы данных 96
4.2. Динамика алгоритма поиска ассоциативных правил 97
4.3. Извлечение ассоциативных правил в различных задачах 102
4.4. Классификация 105
4.5. Исследование влияния параметров алгоритма 106
4.5.1. Исследование влияния функции пригодности 107
4.5.2. Исследование влияния методов отбора 110
4.6. Рекомендации по внедрению системы эволюционных
вычислений в банковские информационные системы 115
Заключение 118
Список литературы 120
Приложение 128
- Методы поиска ассоциативных правил
- Построение ассоциаций путем генерации запросов
- Модуль агрегирования базы данных
- Извлечение ассоциативных правил в различных задачах
Введение к работе
Современный уровень развития аппаратных и программных средств с некоторых пор сделал возможным повсеместное ведение баз данных оперативной информации на разных уровнях управления. В процессе своей деятельности промышленные предприятия, корпорации, ведомственные структуры, органы государственной власти и управления накопили большие объемы данных. Они содержат в себе большие потенциальные возможности по извлечению полезной аналитической информации, на основе которой можно выявлять скрытые тенденции, строить стратегию развития, находить новые решения.
В последние годы в мире оформился ряд новых концепций хранения и анализа корпоративных данных [5,14]:
Хранилища данных, или Склады данных (Data Warehouse);
Оперативная аналитическая обработка (On-Line Analytical Processing, OLAP);
Интеллектуальный анализ данных - ИАД (Data Mining).
Все три технологии тесно связаны между собой. Поэтому наилучшим вариантом является комплексный подход к их внедрению.
Для того чтобы существующие хранилища данных способствовали принятию управленческих решений, информация должна быть представлена аналитику в нужной форме, то есть он должен иметь развитые инструменты доступа к данным хранилища и их обработки.
Очень часто информационно-аналитические системы, создаваемые в расчете на непосредственное использование лицами, принимающими решения, оказываются чрезвычайно просты в применении, но жестко ограничены в функциональности. Такие статические системы называются в литературе Информационными системами руководителя (ИСР), или Executive Information Systems (EIS). Они содержат в себе предопределенные множества запросов и, будучи достаточными для повседневного обзора, неспособны от-
5 ветить на все вопросы к имеющимся данным, которые могут возникнуть при принятии решений. Результатом работы такой системы, как правило, являются многостраничные отчеты, после тщательного изучения которых у аналитика появляется новая серия вопросов. Однако каждый новый запрос, непредусмотренный при проектировании такой системы, должен быть сначала формально описан, закодирован программистом и только затем выполнен. Время ожидания в таком случае может составлять часы и дни, что не всегда приемлемо. Таким образом, внешняя простота статических систем поддержки принятия решений (СППР), за которую активно борется большинство заказчиков информационно-аналитических систем, оборачивается катастрофической потерей гибкости.
Динамические СППР, напротив, ориентированы на обработку нерегла-ментированных (ad hoc) запросов аналитиков к данным. Наиболее глубоко требования к таким системам рассмотрел Е.Ф. Кодд в работе, положившей начало концепции OLAP [35]. Работа аналитиков с этими системами заключается в интерактивной последовательности формирования запросов и изучения их результатов.
Но динамические СППР могут действовать не только в области оперативной аналитической обработки (OLAP); поддержка принятия управленческих решений на основе накопленных данных может выполняться в трех базовых сферах.
- Сфера детализированных данных. Это область действия большинства систем, нацеленных на поиск информации. В большинстве случаев реляционные СУБД отлично справляются с возникающими здесь задачами. Общепризнанным стандартом языка манипулирования реляционными данными является SQL. Информационно-поисковые системы, обеспечивающие интерфейс конечного пользователя в задачах поиска детализированной информации, могут использоваться в качестве надстроек как над отдельными базами данных транзакционных систем, так и над общим хранилищем данных.
Сфера агрегированных показателей. Комплексный взгляд на собранную в хранилище данных информацию, ее обобщение и агрегация, гиперкубическое представление и многомерный анализ являются задачами систем оперативной аналитической обработки данных (OLAP). Здесь можно или ориентироваться на специальные многомерные СУБД, или оставаться в рамках реляционных технологий. Во втором случае заранее агрегированные данные могут собираться в БД звездообразного вида, либо агрегация информации может производиться на лету в процессе сканирования детализированных таблиц реляционной БД.
Сфера закономерностей. Интеллектуальная обработка производится методами интеллектуального анализа данных (ИАД, Data Mining), главными задачами которых являются поиск функциональных и логических закономерностей в накопленной информации, построение моделей и правил, которые объясняют найденные аномалии и/или прогнозируют развитие некоторых процессов. Такие методы относятся к методам извлечения знаний из баз данных (knowledge discovery in databases) и получили сегодня наибольшее распространение.
Некоторые авторы [5,8] выделяют в отдельную область анализ отклонений (например, в целях отслеживания колебаний биржевых курсов). В качестве примера может быть приведен статистический анализ рядов динамики. Чаще, однако, этот тип анализа относят к области закономерностей.
Полная структура информационно-аналитической системы, построенной на основе хранилища данных, показана на рис. 1. В конкретных реализациях отдельные компоненты этой схемы часто отсутствуют.
Существующая теория баз и хранилищ знаний, основанная и развиваемая в работах М. Ш. Цаленко, Л.А. Калиниченко, Б. И. Плоткина, Е. М. Бе-ниаминова, содержит ряд фундаментальных результатов, касающихся принципов моделирования и извлечения знаний. Однако математически строгие модели знаний имеют абстрактно - алгебраическую природу и практическое применение используемых здесь таких понятий как категория, топос, функ-
тор в их непосредственном виде невозможно и требует специальных исследований. Поэтому большинство работающих в настоящее время систем извлечения знаний извлекают не знания в строгом смысле, а специальные объекты, трактуемые как знания. К основным таким объектам относятся: ассоциативные правила, классификации и кластеры. Развитие таких систем применительно к базам данных часто идет по пути создания новых форматов хранения данных, что приводит к появлению новых типов баз данных.
Сфера деюалишрованнвіх данных.
Сфера агрегированненх пока same лей
Сфера закономерностей
Генераторы запросов.
инф ормационно-поиско вые
системы
-^
Системы оперативной
аналитической обработки
данных (ОLAP)
^Ч
Системы интеллектуального анализа данных (ИАД)
2^^
Хранилище данных
Информационные л
системы руководителя
(ИСР) V
Витрины данных
Сбор, очистка и согласование данных из внешних источников
Транзакционные системы, источники данных
^ЕК=}&
Рис. 1. Структура корпоративной информационно-аналитической системы
Вместе с тем подавляющее большинство эксплуатируемых на практике СУБД являются реляционными. Возможности реляционной модели данных далеко не исчерпаны, а реляционная теория остается наиболее развитым математическим инструментом исследования структур баз данных. Поэтому исследование и проектирование систем извлечения знаний применительно к реляционным базам данных представляет собой актуальную научную задачу, имеющую также важное практическое значение.
Многие задачи извлечения знаний допускают оптимизационную постановку. Тогда процедура извлечения знаний представляет собой построе-
8 ние подмножества данных, семантический критерий близости которых, заданный в виде некоторой функции, стремится к максимуму.
В задачах оптимизации выбор конкретного метода оптимизации опирается на свойства оптимизируемой функции. Однако природа задач извлечения знаний такова, что свойства оптимизируемой функции априорно не известны. Более того, в ряде случаев семантический критерий близости данных не может быть непосредственно задан в числовой форме. Это стимулирует развитие специальных подходов к решению задач оптимизации, связанных с извлечением знаний.
Одним из перспективных подходов к решению задач оптимизации в методах извлечения знаний является применение эволюционных вычислений. Эволюционные вычисления, основанные на генетических алгоритмах, в минимальной степени используют свойства оптимизируемой функции и доказали свою эффективность при решении широкого спектра задач комбинаторной оптимизации.
На основании выше изложенного объектом исследования в работе являются реляционные базы данных.
Предметом исследования являются модели знаний в виде обобщенных ассоциативных правил и классификаций, а также эволюционные алгоритмы.
Целью работы является повышение эффективности экспертных решений за счет использования эволюционных методов извлечения знаний из реляционных баз данных.
Поставленная цель достигается решением следующих задач:
Формализация понятия знания в виде ассоциативных правил и классификаций средствами реляционной теории.
Исследование способов реализации методов эволюционных вычислений в реляционных базах данных.
Разработка эволюционных алгоритмов извлечения ассоциативных правил и классификаций на реляционных базах данных.
9 4. Разработка и экспериментальное исследование инструментального программного обеспечения, использующего предложенный метод поиска обобщенных ассоциативных правил и классификаций.
В качестве основных методов исследования предполагается использовать методы теории отношений, эволюционные методы и методы реляционной теории баз данных. Программные решения будут получены методом объектно-ориентированного программирования.
Структура работы
В первой главе дается обзор существующих решений в области извлечения знаний из баз данных. Рассматриваются модели знаний и методы их извлечения из баз данных. Приводятся сравнительные характеристики наиболее популярных программных комплексов извлечения знаний с описанием их функциональных возможностей.
Рассматриваются типовые эволюционные алгоритмы как перспективное направление в области извлечения знаний. Рассматривается общая схема эволюционного алгоритма и приводится описание 4-х классических алгоритмов: генетического алгоритма, генетического программирования, эволюционного программирования и эволюционных стратегий.
По результатам проведенного обзора ставятся актуальные задачи исследования.
Во второй главе формализуются задачи исследования и рассматриваются способы их решения.
Рассматриваются структурный и операционный подходы интерпретации знаний на реляционных базах данных. Ставится задача анализа ассоциаций и показывается принципиальная возможность ее реляционного решения.
Вводится понятие обобщенных ассоциативных правил, а задача их поиска формулируется как обратная задачам извлечения данных.
В работе предлагается эволюционный подход к решению обратных задач в области извлечения знаний. Для решения задачи поиска обобщенных
10 ассоциативных правил предлагается использовать генетические алгоритмы. Разрабатывается способ кодирования входной информации, и строятся генетические операции. Конструируется функция пригодности, наиболее точно отражающая пространство поиска.
В третьей главе описывается разработанная система эволюционных вычислений (СЭВ): ее архитектура, состав функциональных блоков, алгоритмические и программные решения. Рассматриваются особенности реализации архитектуры экспертных систем. Предлагаются алгоритмы для решения основных и вспомогательных задач исследования. Рассматриваются особенности программной реализации системы.
В четвертой главе приводятся результаты вычислительных экспериментов с системой эволюционных вычислений и ее апробации в банковской информационной системе. Рассматривается в динамике процесс нахождения нового знания и процесс нахождения "смысловых ниш".
Исследуется работа алгоритма в различных задач для разных классов входных данных. Приводятся рекомендации по настройке алгоритма и его применению в банковской сфере.
В заключении приводятся основные результаты работы.
Методы поиска ассоциативных правил
Пусть имеется база данных продаж. Необходимо найти важные ассоциации между данными, такие, что наличие некоторых объектов в транзакции влечет наличие других объектов в той же транзакции. Математическая модель была представлена Р. Агравалом в [15] для представления проблемы извлечения ассоциативных правил. Пусть R—{I\, h,---, Лп} будет набор атрибутов, также называемых объектами, определенными на бинарном множестве {0, 1}. Входной вектор r={t\,..., tn) - это отношение на реляционной схеме R, например, множество двоичных векторов размерности т. Каждая строка может рассматриваться как набор свойств или объектов. Пусть WciR - набор атрибутов, a ter - строка в отношении. Если f[A]=l для всех А є И7, можно записать ґ[Ж]=1. Ассоциативное правило на г есть выражение W= B, где W zR и BER\W. Правило W= B поддерживается с доверием у, если Правило W= B имеет распространенность j, если То есть, доля строк из г имеющих 1 во всех атрибутах WB не менее а, и доля строк имеющих 1 одновременно в ивйне менее у. Для заданного набора атрибутов X говорят, что X это покрытие, если То есть, доля строк в отношении, имеющих 1 во всех атрибутах X не менее О". Доверие обозначает мощность правила, а распространенность показывает частоту попадания образцов в правило.
Часто желательно обращать внимание только на такие правила, которые имеют разумно большую распространенность. Такие правила с высоким доверием и распространенностью называются сильные правила [15,73]. Задача извлечения ассоциативных правил в основном состоит в том, чтобы находить сильные правила в больших базах данных. В [15,16] проблема извлечения ассоциативных правил декомпозируется на следующих два этапа: 1. Поиск всех возможных покрытий. 2. Использование этих покрытий для создания ассоциативных правил в базе данных. Агаравал в своей работе [25] доказывает, что общая производительность методов извлечения ассоциативных правил определяется первым шагом. После того, как найдены покрытия, соответствующие ассоциативные правила могут быть определены непосредственно проверкой выполнения правила Х\ {В} = Б с достаточной степенью доверия. Ниже представлены два наиболее распространенных метода Априори и DHP. Алгоритм Априори В качестве примера рассмотрим фрагмент транзакционной базы данных (рис. 1.1). На каждой итерации алгоритм Априори создает множество кандидатов в покрытия, подсчитывает число появлений каждого кандидата, и затем определяет набор покрытий, основываясь на заданной минимальной распространенности. На первом шаге Априори просто сканирует все транзакции, чтобы посчитать число вхождений каждого объекта.
Множество кандидатов в одноэлементные покрытия показано на рис. 1.2. Полагая, что минимально необходимо 2 транзакции (например, при распространенности 8=40%), можем определить набор покрытий L\, составленный из кандидатов с минимально необходимой распространенностью. Для поиска множества кандидатов второго шага, ввиду факта, что любое подмножество покрытия также должно иметь минимальную распространенность, Априори использует операцию L\ L\ для создания множества кандидатов С2, где в данном случае операция конкатенации. В общем случае двух элементных наборов. На втором шаге скани v2 у руются все транзакции из D и подсчитывается значение распространенности для каждого кандидата из С2 (см. рис. 1.2). Далее определяется множество двухэлементных покрытий L2 на основании распространенности каждого кандидата из С2. Множество кандидатов Сз создается из L2 следующим образом. Из L2 вначале выделяются два набора с одинаковыми первыми элементами, {ВС} и {BE}. Затем алгоритм Априори проверяет возможность создания двухэлементного набора из их вторых элементов. Так как {СЕ} уже определенный набор, то все подмножества {В С Е} являются подходящими наборами элементов. Следовательно, {В С Е} становиться трехэлементным кандидатом. Других кандидатов в трехэлементные наборы в L2 нет. Априори сканирует все транзакции и по результатам оценки создает конечное покрытие L3 (см. рис. 1.2). Так как из Z3 нельзя построить четырехэлементные наборы, то алгоритм заканчивает поиск покрытий. Алгоритм DHP Аналогично алгоритму Априори, метод DHP генерирует к-элементные наборы из Lk.\. Однако DHP использует хеширующую таблицу, которая строится на предыдущем шаге, для проверки пригодности k-элементного набора. Вместо включения всех k-элементных наборов из Lk. Lk.x в Ск, DHP добавляет очередной набор, только если он присутствует в таблице в строке со значением больше или равным минимально необходимой распространенности транзакции. Таким образом, размер множества k-элементных наборов-кандидатов Ск может быть значительно сокращен. Такая фильтрация особенно эффективна в сокращении размера множества Съ DHP также постепенно сокращает размер базы данных не только за счет уменьшения размера каждой отдельной транзакции, но и за счет сокращения числа транзакций в базе данных. Оба алгоритма Априори и DHP итеративны по своей природе - в них k-элементные наборы строится на основе (к-1)-элементных наборов.
Построение ассоциаций путем генерации запросов
Снова рассмотрим задачу поиска связи между двумя объектами а и b, а затем перейдем к более общему случаю.
Как показано выше (см. разд. 2.1), все информация о заданных объектах содержится в универсальном отношении U. Однако реальные базы данных далеки от того, чтобы считать их универсальными отношениями. Они представляют собой наборы связанных и несвязанных таблиц. Используя реляционные связи, можно произвести агрегирование базы данных и получить отношение RczU. В общем случае таких отношений может оказаться несколько, а их соединение будет давать подмножество U. Если в R выбрать ассоциацию данных, то в полученном множестве может быть запущен алгоритм поиска обобщенных ассоциативных правил.
Так как запросы на языке SQL являются единственным инструментом извлечения данных в реляционных базах данных, то алгоритм поиск ассоциативных правил сводится к поиску запросов вида (2.5), которые возвращали бы заданное множество объектов.
Метод извлечения знаний путем управления запросами при помощи внешнего алгоритма естественным образом возникает как способ решения задач добычи данных и упоминается в литературе [33,61,76-80,91].
Как показано в разд. 2.1 ассоциативные правила могут описываться характеристическим SQL-запросом.
Характеристический запрос - SQL-запрос, который возвращает все заданное множество объектов.
Ассоциативные правила могут быть получены путем анализа всех характеристических запросов и исключения лишних данных.
Поиск характеристических запросов может быть осуществлен через реализацию управляемых запросов.
Концепция эволюционных вычислений выглядит хорошей альтернативной полному перебору, который должен быть выполнен на операторах запросов для решения рассмотренной задачи. В технологиях извлечения знаний эффективно применяются эволюционные вычисления в первую очередь как средство решения задач комбинаторной оптимизации. Природа эволюционных вычислений позволяет использовать их в задачах оптимизации на нечисловых данных с критерием оптимальности, который может не существовать в виде аналитической функции.
Покажем, что задачи извлечения знаний допускают оптимизационную постановку. Имеем множество объектов, в данном случае - запросов, свойства которых необходимо изменять в соответствии с некоторым критерием пригодности найденных данных. Критерий пригодности связан с вопросом, присутствующим в постановке задачи. Изменения, влияющие на результаты запросов и изменяющие величину или лучше сказать состояние критерия пригодности, касаются структур и состава (параметров) запросов. Здесь вводится понятие изменяемого или управляемого запроса, являющегося инструментом реализации технологии оптимизации.
Рассмотрим следующие принципиальные положения. 1. Фиксируется множество объектов О, обладающих параметрами и связанных друг с другом посредством структуры. Среди этих объектов необходимо выбрать наилучшие в смысле некоторого критерия. Критерий оптимальности формируется на основе свойств объектов и не обязательно существует в виде аналитических выражений. Важно, что каждому объекту из множества О сопоставлено значение критерия F{0). 2. Природа исследуемого множества объектов произвольна, поэтому необходимо построить представление S исходного множества объектов в другом, конечном множестве, обладающем структурой, например, векторного пространства. Представление ф: О - S описывает связь между исследуемыми объектами, которые выступают в качестве потенциальных решений задачи поиска экстремума, и объектами, управлением и манипулированием которых занимается поисковый алгоритм.
Модуль агрегирования базы данных
Модуль позволяет выделить из предъявленной схемы базы данных группы связанных между собой в реляционном смысле таблиц, содержащих заданный набор объектов. Процесс агрегирования происходит в два этапа.
На первом этапе определяются центральные таблицы для агрегированного отношения, содержащие заданные объекты. Для поиска таких таблиц используется метод простого перебора. Так как заданные объекты в базе данных представлены категориальными (символьными) значениями, то для выделения центральной таблицы и полей, содержащих объекты достаточно перебрать все символьные поля базы данных. Опыт показывает, что число таких полей существенно меньше, чем число полей других типов, содержащих характеристики объектов. Следовательно, перебор будет сходиться за достаточно короткое время. Для проверки очередного поля необходимо выполнить запрос
Если такой запрос возвращает значение больше 0, значит, соответствующее поле содержит хотя бы один из объектов.
На втором этапе, на основании реляционной структуры базы данных, рекурсивно выделяется множество таблиц, связанных с таблицами, содержащими объекты. На основании полученной группы таблиц составляется базовый запрос (см. запрос 2.2). Такой запрос позволяет из множества связанных таблиц получить одно агрегированное отношение.
Каждое полученное отношение проверяется на содержание всего множества заданных объектов. Все множество отношений передается ядру системы для дальнейшего поиска ассоциативных связей.
Модуль генетического алгоритма реализует алгоритмы, описанные в разд. 2.3. Модуль позволяет производить гибкую настройку алгоритмов для оптимального решения конкретной задачи. Реализованы следующие настройки алгоритмов: размер популяции; максимальный размер индивидуума; тип отбора: пропорциональный, универсальный случайный, турнирный, с отсечением; тип мутации: простая, адаптивная релейная, адаптивная функциональная; функция пригодности; вероятность пересечения для блока; вероятность создания нового блока; число поколений, создаваемых при работе алгоритма.
Алгоритм работы модуля приведен на рис. 3.3. Модуль получает на вход очередное поколение индивидуумов и поочередно оценивает их на пригодность.
Модуль преобразует индивидуумы к запросу 2.1. Каждый полученный из индивидуума запрос должен быть выполнен в рабочей базе данных. Для того чтобы сократить число выполняемых запросов, в модуле реализован ал 81 горитм исключения повторных запросов. Такой алгоритм позволяет сильно уменьшить число запросов к базе данных, что существенно снижает время работы генетического алгоритма. Например, для поколения из 200 индивидуумов длины 5 при отборе с 10% отсечением и комплексной аддитивной функции мутации за 20 поколений должно быть выполнено порядка 24000 запросов к базе данных. Использование алгоритма исключения повторных запросов снижает это значение до 1635, что составляет 14,7% от общего числа запросов. Динамика изменения числа выполняемых запросов приведена на рис. 3.4.
Модуль выделения ассоциативных правил выбирает из общего числа созданных системой запросов характеристические запросы. Отобранные запросы преобразуются к понятному для пользователя виду с использованием семантической информации метабазы данных. Автоматизированная интерпретация полученных результатов представляет собой отдельную проблему.
Например, при задании в качестве входных параметров двух фирм был получен характеристический запрос "BANK"."NAME" = "ГУ ЦБ РФ" AND "COUNTRY"."SHORT" = "368" AND "CONTRACT". "SUM" 30 000 000 AND "CONTRACT"."DATE" BETWEEN 30.12.02 AND 02.01.03 Запрос содержит следующие знания: у выбранных фирм есть контракты, проведенные через ГУ ЦБ РФ, заключенные на сумму более 30000000 рублей с контрагентом в стране с кодом 368 и проведенные в интервале между 31 декабря 2002 года и 2 января 2003 года. Пользователь, немного знакомый с английским языком, в принципе может интерпретировать смысл данного запроса.
Однако если имена таблиц и полей не являются прозрачными с точки зрения понимания их смысла, то трактовка полученных результатов требует разработки отдельных решений и программирования. Как один из простейших вариантов можно ввести дополнительный справочник семантических понятий таблиц и полей (семантическую метабазу данных) и при выводе результатов на экран заменять служебные имена на их семантические понятия. Тогда приведенный выше пример выглядит следующим образом
Извлечение ассоциативных правил в различных задачах
Таким образом, через несколько шагов алгоритм находит множество незначительно отличающихся решений с близкой степенью пригодности. Такое множество называется в работе смысловой нишей. Смысловая ниша задает основную тему (основное знание) для входящих в нее решений (ассоциативных правил). Остальные элементы правил лишь уточняют незначительные детали о заданных объектах.
График изменения средней функции пригодности приведен на рис. 4.6. Рассмотрим 3 типовые задачи поиска ассоциативных правил и то, как они решаются каждым из предложенных алгоритмов.
Первая типовая задача - поиск ассоциативных правил для заданной пары объектов одной природы. Такого рода задачи наиболее часто встречаются на практике. Например, в задаче валютного контроля это могут быть фирмы, которые подозреваются в совместной незаконной деятельности.
Дополнительно к ранее рассмотренному случаю поиска взаимосвязи двух объектов одной природы, рассмотрен поиск для множества объектов одной природы. В качестве такого множества были взяты все фирмы-клиенты банка "Гамма-банк", всего 47 фирм. В результате работы алгоритма было найдено следующее решение: клиенты Гамма — банка
Жирным шрифтом выделено базовое решение для смысловой ниши. Найденное правило означает, что все фирмы имеют контракты на импорт товаров, заключенные после 15.02.2002 со способом оплаты инкассо и, самое главное, все эти контракты имеют нарушения по пункту Б валютного законодательства. Найденная таким образом информация говорит о том, что тщательной проверки требуют не только перечисленные фирмы, но и весь банк.
График средней пригодности приведен на рис. 4.7. Из-за большого числа объектов, подаваемых на вход системы, смысловая ниша находиться только лишь на 20-м шаге.
Кроме этого в работе рассматривается случай поиска взаимосвязи между двумя объектами разной природы. В качестве входных данных использовались фирма "Альфа" и банк "Гамма-банк". В результате работы алгоритма было найдено следующее решение:
Данное ассоциативное правило содержит детальную информацию о фирме, банке и одном из контрактов, который проведен указанной фирмой через указанный банк. График изменения средней пригодности индивидуумов в популяции приведен на рис. 4.8.
Таким образом, в работе доказана принципиальная возможность решения задач поиска ассоциативных правил в случае различного рода входных данных.
Кроме поиска ассоциативных правил, в главе рассматривается задача классификации всего множества объектов на основании обобщенных характеристик одного базового объекта с использованием того же алгоритма.
В качестве входных параметров системе была задана одна фирма "Альфа". Множество атрибутов агрегированного отношения было ограничено обобщенными характеристиками объекта. В результате работы алгоритма было получено следующее классификационное правило: График средней пригодности приведен на рис. 4.9.
По результатам применения полученного классификационного правила к объектам базы данных, было установлено, что данным характеристикам удовлетворяют 4 фирмы: "Альфа", "Омега", "Дельта" и "Пси". Таким образом, можно считать работоспособность данного алгоритма для нахождения классификационных правил доказанной.
Для выработки рекомендаций по настройке алгоритма, исследуем его поведение при различных входных параметрах.
В качестве тестового примера для исследования были выбраны 2 объекта одной природы - фирмы Альфа и Бета. При исследовании влияния различных параметров, остальные значения фиксировались в наиболее выгодных значениях, определенных ранее опытным путем. Функция пригодности является одним из важнейших параметров генетического алгоритма. От правильного выбора функции пригодности зависит не только скорость схождения алгоритма, но и в целом вся его работа.
Исследование проводилось с тремя вариантами функции пригодности: простая, комплексная аддитивная и комплексная мультипликативная.
