Разработка и исследование методов и алгоритмов кластеризации для систем анализа данных тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Елизаров, Сергей Иванович

• Елизаров, Сергей Иванович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Елизаров, Сергей Иванович

Содержание.

Введение.

Глава 1. Интеллектуальный анализ данных и задача кластеризации.

1.1 Понятие об интеллектуальном анализе данных.

1.2 Формальное описание задач интеллектуального анализа данных.

1.2.1 Задачи регрессии и классификации.

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

1.2.3 .Задача кластеризации.

1.3 Методы интеллектуального анализа данных.

1.3.1 Математический аппарат интеллектуального анализа данных

1.3.2 Алгоритмические особенности решения задач интеллектуального анализа данных.

1.4. Первичный анализ данных и задача кластеризации.

1.4.1 Сравнение данных.

1.4.2 Методы и алгоритмы кластеризации.

Выводы.

Глава 2. Разработка метода нецентроидной нечеткой кластеризации.

2.1 Анализ свойств нечетких бинарных отношений применительно к анализу данных.

2.1.1 Отношения и свойства отношений.

2.1.2 Сравнение данных.

2.1.3 Нечеткое отношение толерантности.

2.1.4 Нечеткое отношение эквивалентности.

2.2 Построение шкалы нечеткого отношения эквивалентности как алгоритм анализа данных.

Выводы.

Глава 3. Адаптивная кластеризация.

3.1 Выбор параметров решения задачи кластеризации.

3.1.1 Расстояние.

3.1.2 Целевая функция, алгоритм.

3.1.3 Количество кластеров.

3.2 Критерии оценки качества решения задачи кластеризации (центроидные методы).

3.2.1 Коэффициент разбиения.

3.2.2 Энтропийные критерии.

3.2.3 Эффективность разбиения.

3.3 Исследование критериев на предопределенных наборах (центроидные методы).

3.3.1 Искусственный набор данных.

3.3.2 Ирисы (Fisher's irises).

3.4 Критерий оценки качества решения задачи кластеризации (метод нечеткого отношения эквивалентности).

3.4.1 Представление результатов решения задачи кластеризации при использовании нечеткого отношения эквивалентности.

3.4.2 Построение критерия оценки качества разбиения, полученного с использованием нечеткого отношения эквивалентности.

3.5 Исследование критериев на предопределенных наборах (метод нечеткого отношения эквивалентности).

3.5.1 Искусственный набор данных.

3.5.2 Ирисы (Fisher's irises).

3.6 Методика адаптивной кластеризации.

3.6.1 Предварительная подготовка данных.

3.6.2 Определение целей анализа.

3.6.3 Определение средств анализа и способа представления результатов.

3.6.4 Подготовка данных.

3.6.5 Формулировка ограничений, критериев оценки качества решения.

3.6.6 Применение адаптивной кластеризации и анализ результатов

Выводы.

Глава 4. Практическое применение адаптивной кластеризации.

4.1 Контроль качества программного обеспечения.

4.2 Методики анализа данных как необходимый элемент зрелости организации.

4.3 Пример применения методики адаптивной кластеризации.

4.3.1 Постановка задачи анализа данных.

4.3.2 Уточнение целей и инструментария.

4.3.3 Нормировка данных, подготовка к кластеризации.

4.3.4 Формулировка ограничений, критериев оценки качества решения.

4.3.5 Адаптивная кластеризация.

4.3.6 Анализ результатов, корректировка исходных данных, повторная кластеризация, заключение по анализу.

4.4 Многоагентная система интеллектуального анализа данных.

4.4.1 Системы мобильных агентов.

4.4.2 Описание методики проектирования многоагентной системы

4.4.3 Задача интеллектуального анализа распределенных данных.

4.4.4 Разработка многоагентной системы интеллектуального анализа данных.

Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование методов и алгоритмов кластеризации для систем анализа данных»

Актуальность. Настоящая работа посвящена разработке и исследованию методов и алгоритмов кластеризации, широко используемой в системах интеллектуального анализа данных. Синонимами термина интеллектуальный анализ данных являются добыча данных (data mining), обнаружение знаний (knowledge discovery) [1,2]. Интеллектуальный анализ данных связан с поиском в данных скрытых нетривиальных и полезных закономерностей, позволяющих получить новые знания об исследуемых данных. Особенный интерес к методам анализа данных возник в связи с развитием средств сбора и хранения данных, позволившим накапливать большие объемы информации. Перед специалистами из разных областей человеческой деятельности встал вопрос об обработке собираемых данных, превращения их в знания. Известные статистические методы покрывают лишь часть нужд по обработке данных, и для их использования необходимо иметь четкое представление об искомых закономерностях. В такой ситуации методы интеллектуального анализа данных приобретают особую актуальность. Их основная особенность заключается в установлении наличия и характера скрытых закономерностей в данных, тогда как традиционные методы занимаются главным образом параметрической оценкой уже установленных закономерностей. Среди методов интеллектуального анализа данных особое место занимают классификация и кластеризация. Классификация, при известной заранее группировке данных на подмножества (классы), устанавливает закономерность, по которой данные группируются именно таким образом. Кластеризация же, основываясь на установленном отношении схожести элементов, устанавливает подмножества (кластеры), в которые группируются входные данные. В широком круге задач нашли свое применение методы нечеткой кластеризации, в которых элементы входного множества относят к тому или иному кластеру на основании значения функции принадлежности. Нечеткая кластеризация одна из наиболее проработанных методик интеллектуального анализа данных. Однако, традиционные методы нечеткой кластеризации не дают приемлемых решений на данных со сложной внутренней структурой. Это связано с рядом допущений, закладываемых в эти методы: кластеры имеют заданную форму и особую внутреннюю точку - центр кластера; разбиение определяется, исходя из взаимосвязей между данными и центрами кластеров. Так как кластеры в общем случае могут быть произвольной формы и не иметь центров, актуальной является разработка метода кластеризации, свободного от указанных допущений и обеспечивающего разбиение только на базе отношений на исследуемых данных.

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

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

В процессе достижения поставленной цели решались следующие задачи:

1) анализ проблем, возникающих при применении методов кластеризации;

2) разработка метода и алгоритма кластеризации на базе нечеткого отношения эквивалентности;

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

4) разработка методики адаптивной кластеризации.

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

Основные положения, выносимые на защиту:

1) Определения нечетких отношений, порождаемых только на основании свойств исследуемых данных.

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

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

Научную новизну работы составляют:

1) определения нечетких отношений толерантности и эквивалентности, позволяющие порождать их из свойств исследуемых данных;

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

3) критерии качества кластеризации, пригодные для построения адаптивной системы;

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

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

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

Реализация и внедрение результатов работы. Результаты диссертационного исследования внедрены в отделе контроля качества петербургского филиала ЗАО «Моторола ЗАО», что подтверждено актом о внедрении. Кроме того, результаты работы использованы в рамках реализации проекта министерства образования и науки Российской Федерации по теме: «Многоагентная технология интеллектуального анализа данных и извлечения знаний», код проекта 75103, а также проекта «Разработка теории и методов исследования самовосстанавливающихся систем» аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» министерства образования и науки Российской Федерации, код проекта 2.1.2.7828.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на международных конференциях по мягким вычислениям и измерениям 8СМ'2006 и 8СМ'2007, Санкт-Петербург, 2006-2007 г. г, конференциях профессорско-преподавательского состава СПбГЭТУ «ЛЭТИ», Санкт-Петербург, 2004-2007 г.г.

Публикации. Основные теоретические и практические результаты диссертации опубликованы в 4 работах, среди которых 1 работа в ведущих рецензируемых изданиях, рекомендуемых в действующем перечне ВАК, 2 -разделы книг, 1 работа - в материалах международной конференции.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав с выводами и заключения. Она изложена на 147 листах машинописного текста и содержит 61 рисунок, 5 таблиц, 2 приложения, список литературы из 59 наименований.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Елизаров, Сергей Иванович

ВЫВОДЫ.

1) Адаптивная кластеризация является важным этапом первичного анализа данных, в частности, помогает в выработке методов анализа данных для целей контроля качества программного обеспечения.

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

3) Методика адаптивной кластеризации внедрена в отделе контроля качества петербургского филиала ЗАО «Моторола ЗАО», что подтверждает ее востребованность.

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

120

ЗАКЛЮЧЕНИЕ.

Данная диссертационная работа посвящена разработке и исследованию методов и алгоритмов кластеризации. Особое внимание было уделено адаптивной кластеризации. Итогом работы стали следующие основные научные и практические результаты:

1) определения нечетких отношений толерантности и эквивалентности, порождаемых из свойств исследуемых данных и составляющих основу предложенного метода кластеризации;

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

3) критерии качества кластеризации, пригодные для построения адаптивной системы;

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

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

Список литературы диссертационного исследования кандидат технических наук Елизаров, Сергей Иванович, 2008 год

1. Negnivitsky М. Artificial Intelligence A Guide to Intelligent Systems Текст. -Harlow: Addison-Wesley, Pearson Education Limited, 2002. 394 c.

2. Data Mining, Web Mining, Text Mining, and Knowledge Discovery Электронный ресурс. :KDnuggets Электрон, дан. - KDnuggets - Режим доступа: http://kdnuggets.com. — Загл. с экрана.

3. Барсегян А. А. Методы и модели анализа данных: OLAP и Data Mining Текст. / Барсегян А. А., Куприянов М. С., Степаненко В. В., Холод И. И. СПб.: БХВ-Петербург, 2004. 336с.

4. Балтрашевич В. Э. Методы оптимизации Текст. / Балтрашевич В. Э., Барабанов Н. Е. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2001. 80с

5. Holland J. Н. Adaptation in Natural and Artificial Systems Текст. -Cambridge, MA: MIT, 1992. 211 c.

6. Ю.Уиллиамс У. Т., Ланс Д. Н. Методы иерархической классификации Текст. // Статистические методы для ЭВМ / Под ред. М. Б. Малютов -М.: Наука, 1986. С. 269-301.

7. Nelles О. Nonlinear System Identification: From Classical Approaches to Neural Networks and Fuzzy Models Текст. Berlin: Springer, 2001. 785 c.

8. Jang J.-S.R. Neuro-fuzzy and Soft Computing. A Computational Approach to Learning and Machine Intelligence Текст./ Jang J.-S.R., Sun C.-T., Mizutani E. New Jersey: Prentice Hall, 1997. 614 c.

9. Miyamoto S. Algorithms for Fuzzy Clustering: Methods in C-Means Clustering with Applications Текст. / S. Miyamoto, H. Ichihashi, K. Honda Berlin: Springer, 2008. 260 c.

10. Fuller R. Neural Fuzzy Systems Электронный ресурс. / Fuller R. -Электрон, дан. Abo: Abo Akademi University, 1995. - Режим доступа: http://www.cs.elte.hu/~rfuller/lnl.pdf- Загл. с экрана.

11. Носов В.А. Комбинаторика и теория графов Электронный ресурс.: учебное пособие / Носов В.А. — Электрон, дан. М: МИЭМ, 1999 -Режим доступа: http://intsys.msu.ru/staff/vnosov/combgraph.zip - Загл. с экрана.

12. Musat G. Fuzzy Clustering Электронный ресурс. / Musat G. Электрон, дан. - Laboratoire Leprince-Ringuet, 2002. - Режим доступа: http://web.archive.org/web/20050415100541/http://polywww.m2p3 .fr/activites /info/doc/glast/fc.htm - Загл. с экрана.

13. Kan S. Metrics and Models in Software Quality Engineering, Second Edition Текст. Addison Wesley, 2002. 528 c.

14. Humphrey W. Managing the Software Process Текст. Addison-Wesley, 1989. 494 c.

15. Capability Maturity Model Integration (CMMI) Электронный ресурс.: CMMI Models and Reports Электрон, дан. - Pittsburgh: CMU/SEI, 2007. -Режим доступа: http://www.sei.cmu.edu/cmmi/models/index.html - Загл. с экрана.

16. Елизаров С. И. Адаптивные методы нечеткой кластеризации Текст. // Сб. докл.: Международная конференция по мягким вычислениям и измерениям SCM, 2007. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2007. - Т.2. -С.234-237.

17. Барсегян А. А. Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP. 2-ое издание Текст. / Барсегян А. А., Куприянов М. С., Степаненко В. В., Холод И. И. СПб.: БХВ-Петербург, 2007. 384 с.

18. Tryllian Mobile Agents:Going beyond the Web. Электронный ресурс.: A Commercial White Paper, Version 1.0, Tryllian Solutions BV Электрон, дан. - 2000. - Режим доступа: http://www.tryllian.com - Загл. с экрана.

19. White J. Mobile Agents White Paper Электронный ресурс. / White J. — Электрон, дан. General Magic, 1996 - Режим доступа: http://www.cis.upenn.edu/~bcpierce/courses/629/papers/White-Telescript.ps.gz- Загл. с экрана.

20. Sundsted Т. Agents on the move Электронный ресурс // Java World 7/98 — Электрон. дан. Java World, 1998. - Режим доступа: http://www.javaworld.com/jw-07-1998/jw-07-howto.html - Загл. с экрана.

21. Chandy К. М. Parallel Program Design: A Foundation Текст. / Chandy К. М., Misra J. Massachusetts: Addison-Wesley, 1988. 516 c.

22. Modeling early requirements in Tropos: a transformation based approach Текст. / Bresciani P., Perini A., Giorgini P. и др. // Agent-Oriented Software Engineering. Montreal, 2001. - C. 67-75.

23. Johansen D., Schneider F. В., Renesse R. What TACOMA Taught Us Текст. // Mobility, Mobile Agents and Process Migration An edited Collection. -NY, Addison Wesley Publishing Company, 1999. C. 564 - 566

24. CRISP-DM 1.0. Step-by-step data mining guide Электронный ресурс. / Chapman P., Clinton J., Kerber R. и др. Электрон, дан. - SPSS, 2000. -Режим доступа: http://www.crisp-dm.org/CRISPWP-0800.pdf - Загл. с экрана.

25. Agent Technology in ОМА Электронный ресурс.: OMG Request For Information, OMG Document # ec/99-03-10 Электрон, дан. - OMG, 1999. -Режим доступа: ftp://ftp.omg.org/pub/docs/ec/99-03-10.htrn - Загл. с экрана.

26. Sundsted Т. An introduction to agents Электронный ресурс. / Sundsted Т. // Java World 6/98 — Электрон, дан. JavaWorld, 1998. - Режим доступа: http://www.javaworld.com/javaworld/jw-06-1998/jw-06-howto.html - Загл. с экрана.

27. Flores-Mendez R. Towards a Standardization of Multi-Agent System Frameworks Электронный ресурс. / Flores-Mendez R. — Электрон, дан. -2001. Режим доступа: www.acm.org/crossroads/xrds5-4/multiagent.html -Загл. с экрана.

28. FIPA Abstract Architecture Specification Электронный ресурс.: Foundation for Intelligent Physical Agents. Электрон, дан. - FIPA, 2001. - Режим доступа: http://www.fipa.org/specs/fipa00001 - Загл. с экрана.

29. Mobile Agent Facility Specification Электронный ресурс. Mobile Agent Facility VI.0 Электрон, дан. - IBM, 2000. - Режим доступа: ftp://ftp.omg.org/pub/docs/fornial/00-01-02.pdf- Загл. с экрана.

30. Caire G. Agent Oriented Analysis using MESSAGE/UML Текст. / Caire G., Leal F., Chainho P. и др. // Agent-Oriented Software Engineering. Montreal. 2001.-C. 101-108.

31. Jazayeri M. Gypsy: A Component-based Mobile Agent System / Jazayeri M., Lugmayr W.// Technical report TUV-1841-99-09. Distributed Systems Group -Vienna: Technical University of Vienna, 1999. 10 c.

32. Common Warehouse Metamodel (CWM) Specification Электронный ресурс.: Catalog of OMG Modeling and Metadata Specifications. Электрон, дан. - OMG, 2001. - Режим доступа: http://www.omg.org/technology/ documents/modelingspeccatalog.htm - Загл. с экрана.

33. Фомичев В. С. Проблемы построения систем мобильных агентов Текст. / Фомичев В. С., Холод И.И. // Известия Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им. В. И. Ульянова (Ленина), №1 2002. СПбГЭТУ «ЛЭТИ», 2002.

34. Farley S. Mobile Agent System Architecture / Farley S. // Java Report, 5/97 -SIGS Publications, 1997.

35. FIPA Agent Communication Language Specifications Электронный ресурс.: Foundation for Intelligent Physical Agents. Электрон, дан. - FIPA, 2002. -Режим доступа: http://fipa.org/repository/aclspecs.html — Загл. с экрана.

36. PMML Version 3.0 Электронный ресурс.: Data Mining Group Электрон, дан. - DMG - Режим доступа: http://www.dmg.org/pmml-v3-0.html - Загл. с экрана.