Разработка и исследование методов кластерного анализа слабоструктурированных данных

Актуальность темы

.

В процессе поиска информации в Интернет или базах данных часто требуется найти и разбить документы на тематические группы определенного назначения — кластеры. Под кластерным анализом будем понимать решение задач кластеризации (построения классов (кластеров) по заданному множеству объектов) и классификации (распознавания), т. е. отнесения объектов к одному из классов с помощью решающего правила или измерения расстояний. Кластерный анализ предполагает также проверку гипотез и сокращение признакового пространства. Применительно к слабоструктурированным данным он предназначен для анализа текстов и изображений с помощью векторно-пространственных моделей (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 Р. (методы 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. (центроидный метод) и др. Заметный вклад в развитие методов кластерного анализа внесли и отечественные ученые: Дорофеюк A.A., Мучник И. Б., Растригин ДА., Загоруйко Н. Г и др.

Разработанные методы не учитывают возможность одновременной обработки графических и текстовых разделов документов. В то же время существенную поддержку системам поиска могут оказать подходы, использующие анализ графических образов, содержащихся во многих документах. Несмотря на разную природу текстов и изображений, многие методы их анализа являются общими. В частности, это касается моделей геометрического представления кластеров, выбора метрик и методов классификации. Большой вклад в развитие теории распознавания образов внесли зарубежные ученые 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., Verma В., HaykinS., MahoneyM., Cheng H., Wosserman F., Горбань A.H., Ясницкий JI.H. и другие исследователи. Вопросами одновременной обработки текста, графики и звука в рамках единой модели представления данных занимался отечественный исследователь Харламов A.A.

В настоящее время существует множество методик, осуществляющих кластеризацию документов. Назовем некоторые из них: Custom Search Folders, Latent Semantic Analysis/Indexing (LSA/LSI) — Suffix Tree Clustering (STC) — Single Link, Complete Link, Group AverageScatter/Gather, K-means, Concept Indexing (CI) — Self-Organizing Maps (SOM).

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

Цель работы.

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

1 .Теоретическое исследование свойств метрик пространства Rp и построение на этой основе методов решения задач кластеризации и классификации;

2.Выдвижение гипотез и исследование теоретических вопросов первоначального размещения кластеров в многомерном пространстве;

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

4.Применение разработанных методов для решения задач кластеризации и классификации на основе анализа текстовых и графических данных.

Методы исследования.

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

Научная новизна.

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

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

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

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

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

Практическая значимость.

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

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

Апробация работы.

Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

1. Четвертая международная научно-техническая конференция «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 02−05 октября, 2007 г.);

2. XVI Международная конференция по вычислительной механике и современным прикладным программным системам (Алушта, ВМСППС'2009, 25−31 мая 2009 г.);

3. Третья Всероссийская научная конференция «Нечеткие системы и мягкие вычисления» НСМВ-2009 (Волгоград, 21−24 сентября 2009 г.);

4. II Международная научно-практическая конференция «Наука и современность -2010» (Новосибирск, 16 апреля 2010 г.);

5. Девятая международная научно-практическая конференция «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 22−23 апреля 2010 г.);

6. Первая всероссийская научная конференция с международным участием (ЭЛвМ-2011) «Системный анализ и семиотическое моделирование» (Казань, 24−28 февраля 2011 г.);

7. Всероссийская конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологических систем» (Москва, 18−22 апреля 2011 г.).

8. Всероссийская конференция с элементами научной школы для молодежи «Интеграция науки и образования как фактор опережающего развития профессионального образования» (Москва, 20 сентября 2011 года).

Публикации.

Основные результаты диссертационной работы изложены в 13 печатных работах, в том числе четыре статьи опубликованы в рецензируемых изданиях, рекомендованных ВАК РФ.

Структура и объем диссертации

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

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

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

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

3. Доказана теорема о размещении ядер кластеров в р-мерном шаре при выполнении критерия максимального суммарного расстояния между ядрами.

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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