автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Эволюционная система извлечения знаний на реляционных базах данных

Введение.

1. Обзор ситуации, типовых решений и методов извлечения знаний.

1.1. Проблема извлечения знаний в больших информационных системах.

1.1.1. Проблемы обработки информации.

1.1.2. Понятие знания.

1.1.3. Различные типы знаний.

1.2. Методы извлечения знаний.

1.2.1. Классификация методов.

1.2.2. Методы поиска ассоциативных правил.

1.2.3. Методы классификации.

1.2.4. Методы кластеризации.

1.3. Программные системы извлечения знаний.

1.4. Методы эволюционных вычислений.

1.4.1. Генетические алгоритмы.

1.4.2. Генетическое программирование.

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

1.4.4. Эволюционные стратегии.

1.5. Цель и задачи исследования.

2. Разработка генетических алгоритмов построения ассоциативных правил и классификаций

2.1. Определение ассоциаций данных.

2.2. Прямые и обратные задачи на базах данных.

2.3. Построение ассоциаций путем генерации запросов.

2.3.1. Использование управляемых запросов.

2.3.2. Применение генетического программирования.

2.3.3. Применение генетического алгоритма.

3. Программно-алгоритмический комплекс построения и исследования ассоциаций данных.

3.1. Архитектура системы эволюционных вычислений.

3.1.1. Ядро системы.

3.1.2. Модуль агрегирования базы данных.

3.1.3. Модуль генетического алгоритма.

3.1.4. Модуль оценки индивидуумов.

3.1.5. Модуль выделения ассоциативных правил.

3.1.6. Семантическая метабаза данных.

3.1.7. Агент.

3.2. Реализация системы эволюционных вычислений.

3.2.1. Описание структуры программы.

3.2.2. Реализация объектов базы данных.

3.2.3. Реализация объектов генетического алгоритма.

3.2.4. Реализация абстракций действия.

4. Исследование системы эволюционных вычислений.

4.1. Описание экспериментальной базы данных.

4.2. Динамика алгоритма поиска ассоциативных правил.

4.3. Извлечение ассоциативных правил в различных задачах.

4.4. Классификация.

4.5. Исследование влияния параметров алгоритма.

4.5.1. Исследование влияния функции пригодности.

4.5.2. Исследование влияния методов отбора.

4.6. Рекомендации по внедрению системы эволюционных вычислений в банковские информационные системы.

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

В последние годы в мире оформился ряд новых концепций хранения и анализа корпоративных данных [5,14]:

1. Хранилища данных, или Склады данных (Data Warehouse);

2. Оперативная аналитическая обработка (On-Line Analytical Processing, OLAP);

3. Интеллектуальный анализ данных - ИАД (Data Mining).

Все три технологии тесно связаны между собой. Поэтому наилучшим 0 вариантом является комплексный подход к их внедрению.

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

Очень часто информационно-аналитические системы, создаваемые в расчете на непосредственное использование лицами, принимающими решения, оказываются чрезвычайно просты в применении, но жестко ограничены в функциональности. Такие статические системы называются в литературе Информационными системами руководителя (ИСР), или Executive ^ Information Systems (EIS). Они содержат в себе предопределенные множества запросов и, будучи достаточными для повседневного обзора, неспособны ответить на все вопросы к имеющимся данным, которые могут возникнуть при принятии решений. Результатом работы такой системы, как правило, являются многостраничные отчеты, после тщательного изучения которых у аналитика появляется новая серия вопросов. Однако каждый новый запрос, непредусмотренный при проектировании такой системы, должен быть сначала формально описан, закодирован программистом и только затем выполнен. Время ожидания в таком случае может составлять часы и дни, что не всегда приемлемо. Таким образом, внешняя простота статических систем поддержки принятия решений (СППР), за которую активно борется большинство заказчиков информационно-аналитических систем, оборачивается катастрофической потерей гибкости.

Динамические СППР, напротив, ориентированы на обработку нерегла-ментированных (ad hoc) запросов аналитиков к данным. Наиболее глубоко требования к таким системам рассмотрел Е.Ф. Кодд в работе, положившей начало концепции OLAP [35]. Работа аналитиков с этими системами заключается в интерактивной последовательности формирования запросов и изучения их результатов.

Но динамические СППР могут действовать не только в области оперативной аналитической обработки (OLAP); поддержка принятия управленческих решений на основе накопленных данных может выполняться в трех базовых сферах.

- Сфера детализированных данных. Это область действия большинства систем, нацеленных на поиск информации. В большинстве случаев реляционные СУБД отлично справляются с возникающими здесь задачами. Общепризнанным стандартом языка манипулирования реляционными данными является SQL. Информационно-поисковые системы, обеспечивающие интерфейс конечного пользователя в задачах поиска детализированной информации, могут использоваться в качестве надстроек как над отдельными базами данных транзакционных систем, так и над общим хранилищем данных.

- Сфера агрегированных показателей. Комплексный взгляд на собранную в хранилище данных информацию, ее обобщение и агрегация, гиперкубическое представление и многомерный анализ являются задачами систем оперативной аналитической обработки данных (OLAP). Здесь можно или ориентироваться на специальные многомерные СУБД, или оставаться в рамках реляционных технологий. Во втором случае заранее агрегированные данные могут собираться в БД звездообразного вида, либо агрегация информации может производиться на лету в процессе сканирования детализированных таблиц реляционной БД.

- Сфера закономерностей. Интеллектуальная обработка производится методами интеллектуального анализа данных (ИАД, Data Mining), главными задачами которых являются поиск функциональных и логических закономерностей в накопленной информации, построение моделей и правил, которые объясняют найденные аномалии и/или прогнозируют развитие некоторых процессов. Такие методы относятся к методам извлечения знаний из баз данных (knowledge discovery in databases) и получили сегодня наибольшее распространение.

Некоторые авторы [5,8] выделяют в отдельную область анализ откло-^ нений (например, в целях отслеживания колебаний биржевых курсов). В качестве примера может быть приведен статистический анализ рядов динамики. Чаще, однако, этот тип анализа относят к области закономерностей.

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

Существующая теория баз и хранилищ знаний, основанная и развиваемая в работах М. Ш. Цаленко, JI.A. Калиниченко, Б. И. Плоткина, Е. М. Бе-ниаминова, содержит ряд фундаментальных результатов, касающихся принципов моделирования и извлечения знаний. Однако математически строгие Ф модели знаний имеют абстрактно - алгебраическую природу и практическое применение используемых здесь таких понятий как категория, топос, функтор в их непосредственном виде невозможно и требует специальных исследований. Поэтому большинство работающих в настоящее время систем извлечения знаний извлекают не знания в строгом смысле, а специальные объекты, трактуемые как знания. К основным таким объектам относятся: ассоциативные правила, классификации и кластеры. Развитие таких систем применительно к базам данных часто идет по пути создания новых форматов хранения данных, что приводит к появлению новых типов баз данных.

Сфе/ia demajnuiupoeaMwefx Сфера агрегированных Сфера данных показателей закономерностей

Рис. 1. Структура корпоративной информационно-аналитической системы

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

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

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

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

На основании выше изложенного объектом исследования в работе являются реляционные базы данных.

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

Целью работы является повышение эффективности экспертных решений за счет использования эволюционных методов извлечения знаний из реляционных баз данных.

Поставленная цель достигается решением следующих задач:

1. Формализация понятия знания в виде ассоциативных правил и классификаций средствами реляционной теории.

2. Исследование способов реализации методов эволюционных вычислений в реляционных базах данных.

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

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

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

Структура работы

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

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

По результатам проведенного обзора ставятся актуальные задачи исследования.

Во второй главе формализуются задачи исследования и рассматриваются способы их решения.

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

Вводится понятие обобщенных ассоциативных правил, а задача их поиска формулируется как обратная задачам извлечения данных.

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

В третьей главе описывается разработанная система эволюционных вычислений (СЭВ): ее архитектура, состав функциональных блоков, алгоритмические и программные решения. Рассматриваются особенности реализации архитектуры экспертных систем. Предлагаются алгоритмы для решения основных и вспомогательных задач исследования. Рассматриваются осо-^ бенности программной реализации системы.

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

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

В заключении приводятся основные результаты работы.

Результаты работы докладывались и обсуждались на:

- 4-й международной конференции "Интерактивные системы: Проблемы человеко-компьютерного взаимодействия / ИС-2001", Россия, Ульяновск, 2001;

- 3-й всероссийской научной конференции "Современные проблемы математики, механики, информатики", Россия, Тула, 2002.

- всероссийской научной конференции УИТ-2003 "Управление и информационные технологии", Россия, Санкт-Петербург, 2003.

- 5-й международной научно-технической конференции "Интерактивные системы: Проблемы человеко-компьютерного взаимодействия / ИС-2003", Россия, Ульяновск, 2003.

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

ЗАКЛЮЧЕНИЕ

В работе получены следующие основные результаты :

1. Задачи извлечения знаний в виде ассоциативных правил и классификаций сформулированы как обратные задачи извлечения данных на реляционных базах данных.

2. Разработаны генетические алгоритмы для решения задач извлечения знаний в виде обобщенных ассоциативных правил и классификации на реляционных базах данных.

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

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

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

1. Формализация задач извлечения знаний в виде ассоциативных правил и классификаций как обратных задач обработки данных на реляционных базах данных.

2. Эволюционный подход к решению задач построения ассоциативных правил и классификаций

3. Генетические алгоритмы построения ассоциативных правил и классификаций на реляционных базах данных.

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

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

Практическая значимость работы состоит в следующем:

- решение нового класса задач извлечения знаний обеспечивает более глубокую обработку данных, хранящихся в реляционных базах данных;

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

1. Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995.

2. Вениаминов Е. М. Основания категорного подхода к представлению знаний II Изв. АН СССР, Техн. кибернетика.—1988,— № 2.— С. 21-33.

3. Богатырёв М.Ю. Моделирование генетических алгоритмов. Изв. ТулГУ. Сер. Вычислительная техника. Автоматика. Управление. Т. 4, вып. 1. Вычислительная техника. - Тула, 2002. - С. 139-146.

4. Богатырёв М.Ю. , Латов В.Е. Исследование генетических алгоритмов кластеризации. Изв. ТулГУ. Сер. Математика. Механика. Информатика. Том 8, вып. 3 . Информатика. - Тула, 2002. - С. 9- 14.Л

5. Буров К. Обнаружение знаний в хранилищах данных // Открытые системы 1999. - №05-06.

6. Городецкий В.И., Самойлов В.В., Малов А.О. Современное состояние технологии извлечения знаний из баз и хранилищ данных. // Новости искусственного интеллекта, 2002, №3, 4.

7. Джексон Г. Проектирование реляционных баз данных для использования с микроЭВМ. М.: Мир, 1991.-252 с.

8. Дюк В., Самойленко A. DataMining: учебный курс. СПб: Питер, 2001, 386с.

9. Киселев М., Соломатин Е. Средства добычи знаний в бизнесе и финансах // Открытые системы, 1997. -№ 4.

10. Ю.Мейер Д. Теория реляционных баз данных М.: Мир, 1987. - 608с.11 .Плоткин Б. И. Алгебраическая модель базы данных — автомата // Латв. мат. ежегодник.—Рига, 1983.—Вып. 27.—С. 216—232.

11. Растригин Л.А. Адаптация сложных систем. Рига: Зинатне, 1981. -375 с.

12. Цаленко М.Ш. Моделирование семантики в базах данных. М.: Наука. Гл. ред. физ-мат. лит., 1989. - 288 с.

13. Щавелёв Л.В. Оперативная аналитическая обработка данных: концепции и технологии, http://www.citforum.ru/seminars/olap/olapru/sch.htm

14. Agrawal R., Imielinsky Т., Swami A. Mining Association Rules between Sets of Items in Large Databases. Proceeding of ACM GIGMOD, 1993, pp. 207-216.

15. Agrawal R., Srikant R. Fast Algorithms for Mining Association Rules in Large Databases. Proceeding of the 20th International Conference on Very Large Data Bases, 1994, pp. 478-499.

16. Agrawal R., Mehta M., Shafer J., Srikant R., Arning A., Bollinger T. The Quest data mining system. In Proc. 1996 Int. Conf. Data Mining and Knowledge Discovery (KDD'96), Portland, Oregon, August 1996, pp. 244-249.

17. Alander J. T. An Indexed Bibliography of Genetic Algorithms Papers. -University of Vaasa, Department of Information Technology and Production Economics, 1999. 76 p.

18. AH K., Manganaris S., Srikant R. Partial Classification using Association Rules. In Proc. of the 3rd Int'l Conference on Knowledge Discovery in Databases and Data Mining. 4 pp.

19. Back Th., Hoffmeister F., Schwefel H.-P. Applications of evolutionary algorithms. Report of the Systems Analysis Research Group SYS-2/92, Univer-sitat Dortmund, Fachbereich Informatik, 1992, 47 pp.

20. Back Т., Rudolph G., Schwefel H.-P. Evolutionary Programming and Evolution Strategies: Similarities and Differences. Evolutionary Programming Society, San Diego, С A, 1993, pp. 11-22.

21. Back Th., Schwefel H.-P. Evolutionary computation: an overview. In Proc. of the 1996 IEEE Int'l Conf. on Evolutionary Computation (ICEC'96), Na-goya, Japan, IEEE Press, New York, NY 10017-2394, 1996, pp. 20-29.

22. Back Th. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, Oxford, 1996.

23. Baralis E., Widom J. An Algebraic Approach to Rule Analysis in Expert Database Systems. In Proc. 20th Int. Conf. on Very Large Data Bases, Santiago de Chile, September 1994. 25 pp.

24. Bayardo R. J. Jr., Agrawal R. Mining the Most Interesting Rules. Proc. of the Fifth ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining, 1999, pp. 145-154.

25. Beasley D., Bull D. R., Martin R. R. An Overview of Genetic Algo-rithms:Part I, Fundamentals, University Computing, Vol. 15, No. 2, 1993, pp. 58-69.

26. Beasley D., Bull D., Martin R. An overview of genetic algorithms: Part 2, Research topics, University Computing, Vol. 15, No. 4, 1993, pp. 170-181.

27. Berkhin P. Survey of clustering data mining techniques. Accrue Software Research Paper. 2002. 53 pp.

28. Blickle Т., Thiele L. A Comparison of Selection Schemes Used in Genetic Algorithms, TIK Report Nr. 11, 2nd Edition, Swiss Federal Institute of Technology, 1995, 67 pp.

29. Cabena P. and International Business Machines Corporation. Discovering data mining: from concept to implementation. Upper Saddle River, New Jersey: Prentice Hall, 1998, 195 pp.

30. Ceri S., Gottlob G. Translating SQL into relational algebra: Optimization, semantics, and equivalence of SQL queries. IEEE Transactions on Software Engineering, 11(4), 1985, pp. 324-345.

31. Chen M.S., Han J., P.S. Yu. Data Mining: An Overview from a Database Perspective. IEEE Transactions on Knowledge and Data Engineering, 1996, pp. 866-883.

32. Cheung D.W., Fu A. W.-C., Han J. Knowledge discovery in databases: A rule-based attribute-oriented approach. In Proc. Int'l Symp. on Methodologies for Intelligent Systems, , Charlotte, North Carolina, October 1994, pp. 164-173.

33. Codd E. F., Codd S. В., Salley С. T. Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate. Technical Report. E. F. Codd & Associates, 1993.

34. DBMiner: A System for Mining Knowledge in Large Relational Databases. Tech. Rep. Simon Fraser University, 1996. 6 pp.

35. Fayyad U.M., Piatetsky-Shapiro G., Smyth P., Uthurusamy R. Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996.

36. Feng L., Lu H., Han J. Beyond intra-transaction association analysis: Mining multi-dimensional intertransaction association rules. Submitted for publication, February 1998, 30pp.

37. Feng L., Lu H., Yu X. J., J. Han. Mining Inter-Transaction Associations with Templates In Proc. 1999 Int. Conf. on Information and Knowledge Management (CIKM'99), Kansas City, Missouri, Nov 1999, pp. 225-233.

38. Fidelis M.V., Lopes, H.S., Freitas A.A., Discovering comprehensible classification rules with a genetic algorithm. Proc. 2000 Congress on Evolutionary Computation (CEC-2000), 2000, pp. 805-810. La Jolla, CA, USA.

39. Flockhart I.W., Radcliffe N.J. A Genetic Algorithm-Based Approach to Data Mining // Proc. of the Second International Conference on Knowledge Discovery and Data Mining, 1996.

40. Frawley W. J., Piatetsky-Shapiro G., Matheus C. J. Knowledge discovery in databases: An overview. In G. Piatetsky-Shapiro, W. J. Frawley, editors, Knowledge Discovery in Databases, AAAI/MIT Press, 1991, pp. 1-27.

41. Freitas A.A. Evolutionary Algorithms. To appear in: Zytkow, J. and Klos-gen, W. (Eds.) Handbook of Data Mining and Knowledge Discovery. Oxford University Press, 2001.

42. Freitas A.A. A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery. To appear in: Ghosh, A. and Tsutsui, S. (Eds.) Advances in Evolutionary Computation. Springer-Verlag, 2001.

43. Georgescu I. A. Categorial approach to knowledge-based systems. Computers and Artificial Intelligence, V.3, N2, 1984, pp. 105-113.

44. Goebel M., Gruenwald L. A survey of data mining and knowledge discovery software tools. SIGKDD Explorations. ACM SIGKDD, Vol. 1, Issue 1, June 1999, pp. 20-33.

45. Goldberg D.E. Real-Coded Genetic Algorithms, Virtual Alphabets, and Blocking. Complex Systems 5, 1991, pp. 139-167.

46. Goldberg D. E. Genetic and Evolutionary Algorithms in the Real World. -IlliGAL Report No. 99013 Department of General Engineering. University of Illinois, March 1999, 11 pp.

47. Haataja J. Comparing global optimization methods. Proceedings of the 1NWGA, Vaasa, Finland, 9 12 January 1995, pp 189-204.

48. Han J., Cai Y., Cercone N. Concept-based data classification in relational databases. In 1991 AAAI Workshop on Knowledge Discovery in Databases, Anaheim, CA, July 1991, pp. 77-94.

49. Han J., Kamber M., Data Mining. Morgan Kaufmann Publ., 2001.

50. Han J., Kamber M., Tung A.K.H. Spatial Clustering Methods in Data Mining: A Survey. 1997, pp. 29.

51. Han J., Lakshmanan L., Ng R. T. Constraint-Based, Multidimensional Data Mining. IEEE Computer. Vol. 32(8): 1999, pp. 46-50.

52. Hirji К. Discovering Data Mining: From Concept to Implementation // ACM SIGKDD, June 1999. Volume 1, Issue 1, 1999, pp.44-45

53. Horn J., Goldberg D.E. Genetic Algorithm Difficulty and the Modality of Fitness Landscapes III To appear in the proceedings of the Foundations of Genetic Algorithms (FOGA) 3 workshop, 1994, 18 pp.

54. Khuri S., Beack Th., Heitkeotter J. An evolutionary approach to combinatorial optimization problems. In D. Cizmar, editor, Proceedings of the 22nd Annual ACM Computer Science Conference. ACM Press, New York. Phoenix, 1994, pp. 66-73.

55. Koza J. R. Genetic Programming. MIT Press/Bradford Books, Cambridge MA, 1992.

56. Koza J.R. Genetic programming II: Automatic discovery of reusable programs. MIT Press. 1994.

57. Kraft D.H., Petry F.B., Buckles B.P., Sadasivan T. The use of genetic Programming to Build Queries for Information Retrieval. Handbook of Evolutionary Computation. IOP Publishing Ltd and Oxford University Press, 1997, 6 pp.

58. Kursawe F., Evolution strategies for vector optimization, In Proc. 10th Int'l Conf. on Multiple Criteria Decision Making, Tapei, Taiwan, July 19-24, Vol. 3, 1992, pp. 187-193.

59. Kwedlo W., Kretowski M. Discovery of Decision Rules from Databases: An Evolutionary Approach. In Proc. of the 2nd European Symp. on Principles of Data Mining and Knowledge Discovery, Nantes, France, 1998, pp. 370378.

60. Langdon W.B. Genetic Programming and Data Structures. A dissertation for the degree of Doctor of Philosophy. Department of Computer Science. University College, London. 1996, 350 pp.

61. Li W. Classification based on multiple association rules. M.Sc. Thesis, Simon Fraser University, April 2001.

62. Liu В., Hsu W., Ma Y. Integrating classification and association rule mining. In KDD'98, New York, NY, 1998.

63. Mannila H., Toivonen H., Verkamo A. I. Improved Methods for Finding Association Rules. In AAAI Workshop on Knowledge Discovery, Seattle, Washington, July 1994, pp. 181-192.

64. Marmelstein R, Lamont G. Pattern Classification using a Hybrid Genetic Program-Decision Tree Approach. In Proceedings of the Third Annual Genetic Programming Conference, 1998, pp. 223-231.

65. Marmelstein R. E. Evolving Compact Decision Rule Sets. Ph.D. diss., Air Force Institute of Technology. 1999, 273 pp.

66. Marmelstein R.E. Application of Genetic Algorithms to Data Mining. Department of Electrical and Computer Engineering. Air Force Institute of Technology, 1997. 5 pp.

67. Megiddo N., Srikant R. Discovering Predictive Association Rules. In kdd98, August 1998, pp. 274-278.72.0racle9i Data Mining Concepts, Release 9.0.1. 2001, Oracle Corporation. 84 pp.

68. Piatetsky-Shapiro G., Frawley W.J. Knowledge Discovery in Databases. AAAI/MIT Press, 1991.

69. Petry F.E., Buckles B.P., Kraft D.H., Prabhu D., Sadasivan Th. The use of genetic programming to build queries for information retrieval // Handbook of Evolutionary Computation. IOP Publishing Ltd and Oxford University Press, 1997

70. Ray ward-Smith V.J., Osman I.H., Reeves C.R., Smith G.D. (eds.). Modern Heuristic Search Methods. Wiley, New York, 1996.

71. Ryu T.W., Eick C.F. Deriving Queries from Results using Genetic Programming. In Proceedings of the 2nd Int. Conf. on Knowledge Discovery and Data Mining. Portland, Oregon, 1996.

72. Ryu T.W., Eick C.F. MASSON: Discovering Commonalities of a Set of Objects Using Genetic Programming. In Proc. Genetic Programming Conference, Stanford, California, July 1996.

73. Ryu T.W., Eick C.F. Deriving Queries From Examples Using Genetic Programming. Department of Computer Science, University of Houston, 1997.

74. Ryu T. W., Eick C.F. Automated Discovery of Discriminant Rules for a Group of Objects in Databases. In Proc. Conference on Automated Learning and Discovery (CONALD*98), Pittsburgh(PA), June 1998.

75. Ryu T.W., Eick C.F. Discovering Discriminant Characteristic queries using Genetic Programming. In Proc. Fourth International Conference on Computer Science and Informatics (CS&T98), Research Triangle Park, North Carolina, October 1998

76. Ryu T.W., Eick C.F. Similarity Measures for Multi-valued Attributes for Database Clustering. In Proc. ANNIE'98, St. Louis, November 1998.

77. Ryu T.W., Z. Wu, Eick C.F. Methodologies, Techniques, and Tools for Database Clustering. In proc KDD'99, San Diego, August 1999.

78. Sanz W., R. Zhang, Eick C.F. A Genetic Programming System for Building Block Analysis to Enhance Data Analysis and Data Mining Techniques", In proc. SPIE Conference On Data Mining and Knowledge Discovery, Orlando, April 1999.

79. Sarafis, I., Zalzala, A.M.S., and Trinder, P.W. A genetic rule-based data clustering toolkit. To be published in Congress on Evolutionary Computation (CEC), Honolulu, USA, 2002.

80. Sastry K., Xiao G. Cluster Optimization Using Extended Compact Genetic Algorithm. IlliGAL Report No. 2001016. Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 2001, 13 pp.

81. Shine W. В., Eick C.F. Visualizing the Evolution of Genetic Algorithm Search Processes. In Proc. IEEE International Conference on Evolutionary Computation, April 1997.

82. Shyu M-L., Chen S-C. Kashyap R. L. Database Clustering and Data Warehousing. ICS Workshop on Software Engineering and Database Systems, Dec. 17-19, 1998, pp. 30-27.

83. Spears W., Jong K. D., Back Т., Fogel D., Garis H. An Overview of Evolutionary Computation, Proceedings of the 1993 European Conference on Machine Learning, 1993,18 pp.

84. Srikant R., Agrawal R. Mining Quantitative Association Rules in Large Relational Tables. In Proceedings of the ACM SIGMOD Conference on Management of Data, Montreal, Canada, June 1996, pp. 1-12.

85. Srikant R., Vu Q., Agrawal R. Mining Association Rules with Item Constraints. Proc. 3rd Int. Conf. Knowledge Discovery and Data Mining, KDD. 1997,7 pp.

86. Steele R., Powers D. Evolution and Evaluation of Document Retrieval Queries. In D.M.W. Powers (ed.) NeMLaP3/CoNLL98: New Methods in Language Processing and Computational Natural Language Learning, ACL, 1998, pp 163-164.

87. Tung A., Lu H., Han J., Feng L. Breaking the barrier of transactions: Mining inter-transaction association rules. In Proc. of the Fifth Int'l Conferenceon Knowledge Discovery in Databases and Data Mining, San Diego, CA, August 1999, pp. 297-301.

88. Yao X., Liu Y. Fast evolution strategies. In P. J. Angeline, R. G. Reynolds, J. R. McDonnell, and R. Eberhart, editors, Proceedings of the Sixth Annual Conference on Evolutionary Programming, Springer, Berlin, 1997, pp. 151161.

89. Zilles S.N. Introduction to data algebras. Lect. Notes Comput. Sci., V.86, Springer-Verlag, 1980.

90. ЦЕНТРАЛЬНЫЙ БАНК РОССИЙСКОЙ ФЕДЕРАЦИИ (Банк России)

91. Главное управление по Тульской области 300041, г. Тула, ул. Советская, 88