Введение к работе
Актуальность темы
В процессе поиска информации в Интернет или базах данных часто требуется найти и разбить документы на тематические группы определенного назначения - кластеры. Под кластерным анализом будем понимать решение задач кластеризации (построения классов (кластеров) по заданному множеству объектов) и классификации (распознавания), т.е. отнесения объектов к одному из классов с помощью решающего правила или измерения расстояний. Кластерный анализ предполагает также проверку гипотез и сокращение признакового пространства. Применительно к слабоструктурированным данным он предназначен для анализа текстов и изображений с помощью векторно-пространственных моделей (vector space model).
Геометрическая кластеризация (geometric clustering) относится к методам получения минимального или заданного числа компактных групп, реализуемых с помощью матриц расстояний и графов. В задаче геометрической кластеризации представлены точки потенциально высокоразмерного пространства, на котором определена метрика. Существенное значение имеет здесь сокращение размерности данных и визуализация результатов.
Исследования геометрической кластеризации, в основном, представлены работами зарубежных ученых США: Still S., Bialek W., Bottou L., Sun J., Yao Y., Matousek J., Японии: Imai I., Inaba M., Imai H., Sadakane К. и др. Большой вклад в развитие общей теории кластерного анализа внесли Moore A.W., Gray A.G., Pelleg D., Tryon R.C., Bailey D.E., Jain A.K., Dubes R.C. (алгоритмы и техника кластеризации); Ball G.H., Hall D.J., MacQueen J., Lloyd Stuart P. (методы k-средних); Jordan M.I.; Moore A.W., Trevor H., Tibshirani R., Friedman J. (иерархические методы); Hardin R.H., Sloane N.J.A., Smith W.D., Sokal R.R., Sneath, P.H. (центроидный метод) и др. Заметный вклад в развитие методов кластерного анализа внесли и отечественные ученые: Дорофеюк А.А., Мучник И.Б., Растригин Л.А., Загоруйко Н.Г и др.
Разработанные методы не учитывают возможность одновременной обработки графических и текстовых разделов документов. В то же время существенную поддержку системам поиска могут оказать подходы, использующие анализ графических образов, содержащихся во многих документах. Несмотря на разную природу текстов и изображений, многие методы их анализа являются общими. В частности, это касается моделей геометрического представления кластеров, выбора метрик и методов классификации. Большой вклад в развитие теории распознавания образов внесли зарубежные ученые Duba R., Hart Р., Той J.T., Gonsales R.C, Fukunaga К., Patrick E., Rosenblatt Frank (персептрон) Breiman L., Friedman J.H., Olshen R.A., Stone C.T., Quinlan J.R. (деревья решений) и отечественные ученые: Айвазян С. А., Айзерман М.А., Браверман Э.М. (метод потенциальных функций), Розоноэр Л.И., Вапник В.Н., Червоненкис А.Я. (статистическая теория распознавания). Ю.И.Журавлев (алгебраическая
теория распознавания) и др. Вопросами классификации и кластеризации искусственными нейронными сетями (ИНС) занимались Rosenblatt F., Kohonen Т.К., Hopfield J.J., VermaB., Haykin S., MahoneyM., Cheng H., Wosserman F., Горбань A.H., Ясницкий Л.Н. и другие исследователи. Вопросами одновременной обработки текста, графики и звука в рамках единой модели представления данных занимался отечественный исследователь Харламов А. А.
В настоящее время существует множество методик, осуществляющих кластеризацию документов. Назовем некоторые из них: Custom Search Folders, Latent Semantic Analysis/Indexing (LSA/LSI); Suffix Tree Clustering (STC); Single Link, Complete Link, Group Average; Scatter/Gather, K-means, Concept Indexing (CI); Self-Organizing Maps (SOM).
Несмотря на очевидный прогресс в этой области, до сих пор далеки от окончательного решения следующие проблемные теоретические вопросы: выбор первоначального расположения ядер кластеров, обоснование выбора метрик; создание метода унифицированной обработки текстов и графики; управление размерностью данных; ускорение процессов и повышение точности кластеризации. Это определяет актуальность темы исследования направленной на создание универсальных методов анализа слабоструктурированной информации.
Цель работы
Целью работы является развитие методов кластерного анализа слабоструктурированных данных на основе совершенствования математических моделей, метрик и алгоритмов. Цель достигается решением следующих задач:
1. Теоретическое исследование свойств метрик пространства rp и
построение на этой основе методов решения задач кластеризации и
классификации;
2. Исследование теоретических вопросов первоначального размещения
кластеров в многомерном пространстве.
3. Разработка и исследование метода кластерного анализа с
расширенным набором метрик и способов начального размещения
кластеров;
4. Разработка и исследование метода кластерного анализа на основе
варьирования размерности пространства;
Методы исследования
В диссертационной работе использованы методы теории множеств, теории алгоритмов, методы обработки изображений. Исследования базируются на теории искусственных нейронных сетей, методах алгебраической теории распознавания изображений и моделирования многообъектных структур на ЭВМ.
Научная новизна
Научная новизна заключается в построении новых методов и алгоритмов, обеспечивающих решение задач кластерного анализа текстов и изображений:
Доказаны утверждения о том, что функции Махаланобиса и Евклида-Махаланобиса являются квазиметриками, что позволяет решать задачи измерения расстояний как внутри, так и между классами, а также между произвольной точкой и классами.
Доказана теорема о размещении точек в р -мерном шаре при выполнении критерия максимального суммарного расстояния между точками. Выдвинута гипотеза о квазиравномерности размещения точек при том же критерии, которая частично подтверждена теоремами о равномерном размещении точек в круге и четырех точек в трехмерной сфере, что позволяет решать проблему первоначального размещения ядер кластеров, в том числе для задачи коммивояжера.
Разработан и исследован метод кластерного анализа данных, основанный на модифицированной сетевой модели с набором метрик и способов начального размещения кластеров, обеспечивающий единый подход к решению задач классификации и кластеризации слабоструктурированных данных.
Разработан и исследован метод бинарной кластеризации, основанный на варьировании пространства признаков, который позволяет решать прямую и обратную задачи преобразования пространства признаков с представлением в них решающих функции.
Практическая значимость
Теория и алгоритмы геометрической кластеризации могут быть практически использованы в системах анализа слабоструктурированной информации. Предложенная математическая модель классификатора с набором метрик, включая квазиметрику Евклида-Махаланобиса, существенно расширяет возможности решения задач кластеризации и классификации за счет универсального представления разнородных данных и возможности выбора адекватной функции расстояния.
Разработанный метод варьирования размерности пространства признаков позволяет строить более простые модели (за счет уменьшения размерности) представления информации и разделяющих функций. Полученные результаты в целом могут найти широкое применение в современных Интернет-системах, осуществляющих поиск и раскладку документов, обеспечивая большую релевантность за счет одновременного учета текстовой и графической информации. Кроме того, методы целесообразно использовать в системах распознавания графических образов широкого назначения.
Апробация работы
Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:
Четвертая международная научно-техническая конференция «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 02-05 октября, 2007 г.);
XVI Международная конференция по вычислительной механике и современным прикладным программным системам (Алушта,
ВМСППС'2009, 25-31 мая 2009 г.);
Третья Всероссийская научная конференция «Нечеткие системы и мягкие вычисления» НСМВ-2009 (Волгоград, 21-24 сентября 2009 г.);
II Международная научно-практическая конференция «Наука и современность - 2010» (Новосибирск, 16 апреля 2010 г.);
Девятая международная научно-практическая конференция «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 22-23 апреля 2010 г.);
Первая всероссийская научная конференция с международным участием (SASM-2011) «Системный анализ и семиотическое моделирование» (Казань, 24-28 февраля 2011г.);
Всероссийская конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологических систем» (Москва, 18-22 апреля 2011 г.);
8. Всероссийская конференция с элементами научной школы для
молодежи «Интеграция науки и образования как фактор
опережающего развития профессионального образования» (Москва,
20 сентября 2011 года).
Публикации
Основные результаты диссертационной работы изложены в 13 печатных работах, в том числе четыре статьи опубликованы в рецензируемых изданиях, рекомендованных ВАК РФ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 85 наименований. Основная часть изложена на 106 страницах машинописного текста, иллюстрируется 25 рисунком и 19 таблицами.
