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

• Бояркин, Михаил Игоревич
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Бояркин, Михаил Игоревич

Введение.

1. Основные принципы применения методов кластерного анализа для обработки данных.

1.1 Основные методы теории кластерного анализа и их свойства.

1.2 Анализ oq3aHH4eHHfi на выбор элементов модели кластеризации.

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

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

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

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

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

Наибольший научно-практический интерес данная задача группировки многомерных данных представляет в условиях, приближенных к реальным:

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

- не существует заранее классифицированной обучающей выборки,

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

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

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

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

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

- исследование и анализ существующих методов кластерного анализа;

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

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

- разработка модели кластеризации многомерных данных на основе не-формализуемого критерия ассоциативного сходства смыслового содержания обрабатываемой информации;

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

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

Исследование качества работы разработанных моделей проведено на основе методов теории вероятностей и математической статистики. Для синтеза и анализа системы группировки специализированных многомерных данных использовался пакет инженерных вычислений MATLAB®. Научная новизна.

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

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

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

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

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

- разработан алгоритм индексации графической информации с учетом критерия визуального сходства изображений. Показана эффективность работы алгоритма индексации, выполняющего качественную классификацию графической информации со значительно меньшими затратами вычислительных ресурсов по сравнению с системами распознавания образов. Алгоритм использован в виде компонентов автоматизированной системы индексации и поиска графической информации; Реализация результатов работы. Результаты диссертационных исследований использованы при разработке автоматизированной системы индексации больших массивов графических данных с учетом критерия визуального сходства изображений с данными, поступающими в режиме реального времени, в конструкторском отделе промышленного предприятия ООО «Эллипс» (г. Самара), а также в учебном процессе подготовки магистрантов по направлению 22.00.00 «Автоматика и управление» в дисциплинах «Интеллектуальные технологии в системах управления» и «Системное моделирование» в ГОУ ВПО «Самарский государственный технический университет».

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на XXXI Самарской областной научной конференции (Самара, 2005); II Всероссийской научной конференции «Математическое моделирование и краевые задачи» (Самара, 2005); V Всероссийской межвузовской конференции «Практика применения научного программного обеспечения в образовании и исследованиях» (Санкт-Петербург, 2007); VI Всероссийской научно-технической конференции «Научное программное обеспечение в образовании и научных исследованиях» (Санкт-Петербург, 2008); X Международной конференции «Проблемы управления и моделирования в сложных системах» (Самара, 2008). Работа поддержана грантом РФФИ по проекту 07-08-00401-а.

Публикации. По теме диссертации опубликовано 9 печатных работ. Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 115 страницах машинописного текста, содержит 21 рисунок, 1 таблицу, список литературы из 80 наименований и 2 приложения.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Бояркин, Михаил Игоревич

4.6 Основные результаты и выводы

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Произведено внедрение разработанной распределенной системы индексации и поиска изображений в конструкторском подразделении на предприятии ООО «Эллипс».

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

1. Бояркин, М.И. Исследование поведения динамической системы распознавания образов при спонтанном изменении конфигурации Р2Р-сети / М.И. Бояркин, А.А. Юдашкин // Вестник СамГТУ. Сер.: техн. науки. Самара: СамГТУ. 2007. - № 2(20). - С. 5-11.

2. Бояркин, М.И. Формирование интеллектуальных критериев в задачах кластеризации сложной графической информации / М.И. Бояркин // Вестник СамГТУ. Сер.: техн. науки. Самара: СамГТУ. 2008. - № 1(21). - С. 178-180. ISSN 1991-8542.

3. Лоскутов, А.Ю. Введение в синергетику / А.Ю. Лоскутов, А.С. Михайлов. -М.: Наука, 1990.-272 с.

4. Фаулер, М. Архитектура корпоративных программных приложений / М. Фаулер. М.: Издательский дом «Вильяме», 2007. - 544 с.

5. Юдашкин, А.А. Бифуркации стационарных решений в синергетической нейронной сети и управление распознаванием образов / А.А. Юдашкин //Автоматика и Телемеханика, 1996.-№ 11.- С. 139-147.

6. Anderberg, M.R. Cluster Analysis for Applications / M.R. Anderberg. -Academic Press, 1973.

7. Ball, G.H. A clustering technique for summarizing multivariate data / G.H. Ball, D.J. Hall // Behavioral Science. March 1967. - Vol. 12. - Pp. 153155.

8. Bezdek, J.C. A convergence theorem for the fuzzy Isodata clustering algorithms / J.C. Bezdek // IEEE Transactions on PAMI. 1980. - Vol. 2(1). -Pp. 1-8.

9. Boberg, J. General formulation and evaluation of agglomerative clustering methods with metric and non-metric distances / J. Boberg, T. Salakoski // Pattern Recognition. 1993. - Vol. 26(9). - Pp. 1395-1406.

10. Bobrowski, L. c-Means clustering with 11 and loo norms / L. Bobrowski, J.C. Bejdek // IEEE Transactions on Systems Man and Cybernetics. May/June 1991.-Vol. 21(3).-Pp. 545-554.

11. Brockett, P.L. Information theoretic analysis of questionnaire data / P.L. Brockett, P.D. Haaland, A. Levine // IEEE Transactions on Information Theory. 1981. - Vol. 27. - Pp. 438-445.

12. Calinski, R.B. A dendrite method for cluster analysis / R.B. Calinski, J. Harabasz // Communications in Statistics. 1974. - Vol. 3. - Pp. 1-27.

13. Carpenter, G.A. Adaptive Resonance Theory / G.A. Carpenter, S. Grossberg. MA: MIT Press, 2003. - 2nd ed. - Pp. 87-90.

14. Carpenter, G.A. ART2: Self-organization of stable category recognition codes for analog input patterns / G.A. Carpenter, S. Grossberg // Applied Optics. 1987. - Vol. 26. - Pp. 4919-4930.

15. Clarke, C. Dynamic Inverted Indexes for a Distributed Full-Text Retrieval System / C. Clarke, G. Cormack // TechRep MT-95-01. University of Waterloo. 1995.

16. Dave, R.N. Generalized fuzzy c-shells clustering and detection of circular and elliptical boundaries / R.N. Dave // Pattern Recognition. 1992. - Vol. 25(7).- Pp. 713-721.(6)

17. Dave, R.N., Adaptive fuzzy c-shells clustering and detection of ellipses / R.N. Dave, K. Bhaswan // IEEE Transactions on Neural Networks. 1992. -Vol. 3(5). - Pp. 643-662. (a)

18. Deerwester, S. Indexing by Latent Semantic Analysis / S. Deerwester et al. // Journal of the American Society for Information Science. 1990. -Vol. 41(6).-Pp. 391^107.

19. Dixon, J.K. Pattern recognition with partly missing data / J.K. Dixon // IEEE Transactions on Systems Man and Cybernetics. 1979. - Vol. SMC 9. - Pp. 617-621.

20. Duda, R.O. Pattern Classification and Scene Analysis / R.O. Duda, P. Hart. John Wiley & Sons, 1973.

21. El-Gazzar, A. The taxonomy of Salvia: A test of two radically different numerical methods / A. El-Gazzar, L. Watson, W.T. Williams, G. Lance // J. Linn. Soc. (Bot.). 1968. - Vol. 60. - Pp. 237-250.

22. Everitt, B. Cluster Analysis / B. Everitt. Halsted Press, 1981. - 2nd ed.

23. Frigui, H. A comparison of fuzzy shell clustering methods for the detection of ellipses / H. Frigui, R. Krishnapuram // IEEE Transactions on Fuzzy Systems. May 1996. - Vol. 4(2).

24. Frigui, H. Clustering by competitive agglomeration / H. Frigui, R. Krishnapuram // Pattern Recognition. 1997. - Vol. 30(7). - Pp. 1109-1119.

25. Fu, L. Real-time adaptive clustering of flow cytometric data / L. Fu et al. // Pattern Recognition. 1993. - Vol. 26(2). - Pp. 365-373.

26. Fuchs, A. Pattern recognition and associative memory as dynamical processes in a synergetic system / A. Fuchs, H. Haken // Biol. Cybern. 1988. — Vol. 60, №. l.-Pp. 17-22.

27. Gersho, A. Vector Quantization and Signal Compression / A. Gersho, R.M. Gray. Kluwer Academic Publishers, 1992.

28. Goodall, D.W. A new similarity index based on probability / D.W. Goodall // Biometrics. 1966. - Vol. 22. - Pp. 882-907.

29. Gowda Chidananda, K. Divisive clustering of symbolic objects using the concepts of both similarity and dissimilarity / K. Gowda Chidananda, T.V. Ravi // Pattern Recognition. 1995. - Vol. 28(8). - Pp. 1277-1282.

30. Gower J.C. A general coefficient of similarity and some of its properties / J.C. Gower // Biometrics. 1971. - Vol. 27. - Pp. 857-872.

31. Gower, J.C. A comparison of some methods of cluster analysis / J.C. Gower // Biometrics. 1967. - Vol. 23. - Pp. 623-628.

32. Gray, R.M. Vector quantization / R.M. Gray // IEEE ASSP Magazine. -1984.-Vol. l.-pp. 4-29.

33. Haken H. Synergetic computers and cognition: A top-down approach to neural nets/H. Haken. Berlin: Springer-Verlag, 1991.

34. Hall, A.V. Methods for demonstrating resemblance in taxonomy and ecology / A.V. Hall // Nature. 1967. - Vol. 214. - Pp. 830-831.

35. Hopfield J. J. Neural networks and physical systems with emergant collective computation abilities // Proc. Natl. Acad. Sci. USA, 1982. Vol. 79. -P. 2554-2558.

36. Horn, B.K.P. Robot Vision / B.K.P. Horn. MIT Press, 1986.

37. Hubert, L.J. A general statistical framework for assessing categorical clustering in free recall / L.J. Hubert, J.R. Levin // Psychological Bulletin. -1976.-Vol. 83.-Pp. 1072-1080.

38. Jain, A.K. Algorithms for Clustering Data / A.K. Jain, R.C. Dubes // Prentice Hall, 1988.

39. Jain, A.K. Data clustering: a review / A.K. Jain, M.N. Murty, P.J. Flynn // ACM Computing Surveys. 1999. - Vol. 31(3). - Pp 264 - 323.

40. Johnson, S.C. Hierarchical clustering schemes / S.C. Johnson // Psycho-metrika. 1967. - Vol. 32. - Pp. 241-254.

41. Kanlcanhalli, M.S. Cluster-based color matching for image retrieval / M.S. ' Kanlcanhalli, B.M. Mehtre, J.K. Wu // Pattern Recognition. 1996. - Vol. 29(4).-Pp. 701-708.

42. Karen, D. Describing complicated objects by implicit polynomials / D. Karen, D. Cooper, J. Subrahmonia // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1994. - Vol. 16(1). - pp. 38-53.

43. Koutroumbas, K. Neural network architectures for selecting the maximum input / K. -Koutroumbas, N. Kalouptsidis // International Journal of Computer Mathematics. 1998. - Vol. 68(1-2).

44. Krishnapuram, R. A possibilistic approach to clustering / R. Krishnapuram, J.M. Keller // IEEE Transactions on Fuzzy Systems. 1993. - Vol. 1(2). -Pp. 98-110.

45. Krishnapuram, R. The possibilistic c-means algorithm: Insights and recommendations / R. Krishnapuram, J.M. Keller // IEEE Transaction on Fuzzy Systems. 1996. - Vol. 4(3). - Pp. 385-393.

46. Kurita, T. An efficient agglomerative clustering algorithm using a heap / T. Kurita // Pattern Recognition. 1991. - Vol. 24. - Pp. 205-209.

47. Lance, G.N. A general theory of classificatory sorting strategies II. Clustering systems / G.N. Lance, W.T. Williams // Computer Journal. 1967. — Vol. 10.-Pp. 271-277.

48. Li, X. Parallel algorithms for hierarchical clustering and cluster validity / X. Li // IEEE Transactions on Pattern Analysis and Machine Intelligence. -1990.-Vol. 12(11).-Pp. 1088-1092.

49. Li, X. The first stage in two-stage template matching / X. Li, R.C. Dubes // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1985. — Vol. 7.-Pp. 700-707.

50. Lippmann, R.P. An introduction to computing with neural nets / R.P. Lippmann // IEEE ASSP Magazine. 1987. - Vol. 4(2). - Pp. 4-22.

51. Lloyd, S.P. Least squares quantization in PCM / S.P. Lloyd // IEEE Transactions on Information Theory. 1982. - Vol. 28(2).

52. MacNaughton-Smith, P. Dissimilarity analysis / P. MacNaughton-Smith, W.T. Williams, M.B. Dale, L.G. Mockett // Nature. 1964. - Vol. 202. -Pp. 1034-1035.

53. MacQuenir, J.B. Some methods for classification and analysis of multivariate observations / J.B. MacQuenn // Proceedings of the Symposium on

54. Mathematical Statistics and Probability. 5th Berkeley. University of California Press. 1967. - Vol. 1. - Pp. 281-297.

55. McQuitty, 'L.L. Multiple hierarchical classification of institutions and persons with reference to union-management relations and psychological well-being / L.L. McQuitty //Educ. Psychol. Measur.- 1962.-Vol.23.- pp. 55-61.

56. Milligan, G.W. An examination of procedures for determining the number of clusters in a data set / G.W. Milligan, M.C. Cooper // Psychometrika. -1985.-Vol. 50(2).-Pp. 159-179.

57. Murtagh, F. Multidimensional clustering algorithms / F. Murtagh // COMPSTAT Lectures. Vienna: Physica-Verlag. 1985. - Vol. 4.

58. Murthy, M.N. Knowledge-based clustering scheme for collection, management and retrieval of library books / M.N. Murthy, A.K. Jain // Pattern Recognition. 1995. - Vol. 28(7). - Pp. 949-963.

59. Nikolaou, N. Color image retrieval using a fractal signature extraction technique / N. Nikolaou, N. Papamarkos // Engineering Applications of Artificial Intelligence. 2002. - Vol. 15. - Pp. 81-96.

60. Pritchard, N.M. Observations on the use of cluster analysis in botany with an ecological example / N.M. Pritchard, A.J.B. Anderson // J. Ecol. 1971. -Vol. 59.-pp. 727-747.

61. Sheals, J.G. An application of computer techniques to Acrine taxonomy: A preliminary examination with species of the Hypoaspio-Androlaelaps complex Acarina / J.G. Sheals // Proc. Linn. Soc. Lond.-l965.-Vol.176. pp. 11-21.

62. Sneath, P.H.A. Numerical Taxonomy / P.H.A. Sneath, R.R. Sokal. San Francisco: W.H. Freeman & Co, 1973.

63. Solomon, H. Numerical taxonomy in Mathematics in the Archaeological and Historical Sciences / H. Solomon et al.. University Press, 1971.

64. Spath, H. Cluster Analysis Algorithms / Ii. Spath. Ellis Horwood, 1980.

65. Tanimoto, T. An elementary mathematical theoiy of classification and prediction / Т.-Tanimoto. Int. Rpt., IBM Corp., 1958.

66. Theodoridis, S. Pattern recognition / S. Theodoridis, K. Koutroumbas. Elsevier, 2003. - 2nd ed. -707 p.

67. Trahanias, P. An efficient sequential clustering method / P. Trahanias, E. Scordalakis // Pattern Recognition. 1989. - Vol. 22(4). - Pp. 449-453.

68. Viola, P. Object Detection using a Boosted Cascade of Simple Features / P. Viola, M. J. Jones // IEEE CVPR. 2001.

69. Wallace, C.S. An information measure for classification / C.S. Wallace, D.M. Boulton // Computer Journal. 1968. - Vol. 11. - Pp. 185-194.

70. Ward, J.IT. Plierarchical grouping to optimize an objective function / J.H. Ward // Journal of the American Statistical Association. 1963. - Vol. 58. — pp. 236-244.

71. Zadeh, L.A. Fuzzy sets / L.A. Zadeh // Information and Control. 1965. -Vol. 8.-Pp. 338-353.