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

• Автор: Хачумов, Михаил Вячеславович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 106 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. АНАЛИЗ ПРОБЛЕМНЫХ ВОПРОСОВ КЛАСТЕРИЗАЦИИ И
КЛАССИФИКАЦИИ СЛАБО СТРУКТУРИРОВАННЫХ ДАННЫХ
1Л. Модели представления слабоструктурированной информации
1.1.1. Табличный способ задания исходных данных
1.1.2. Мультимножества для описания многопризнаковых данных
1.1.3. Фазовые траектории для описания многомодальных данных
1.2. Постановка задач кластеризации и классификации
1.2.1. Постановка задачи кластеризации
1.2.2. Постановка задачи классификации
1.3. Анализ мер близости и расстояний. Основные понятия и определения
1.4. Методы выбора первоначального числа кластеров
1.4.1. Метод последовательного сокращения числа кластеров
1.4.2. Метод последовательного увеличения числа кластеров
1.4.3. Метод выбора числа кластеров направленным объединением
1.5. Проблема и модели начального расположения кластеров
1.5.1. Сферическая (пространственная) модель размещения кластеров
1.5.2. Модель линейных зависимостей
1.6. Методы кластерного анализа
1.6.1. Классификация на основе метода МГУ А
1.6.2. Неиерархические методы кластеризации. Алгоритм к-теат
1.6.3. Иерархические методы кластеризации
1.6.4. Искусственные нейронные сети
1.7. Особенности задачи кластеризации документов
1.7.1.Методы кластеризации документов
1.7.2.Постановка задачи классификации текстов на естественном языке
1.7.3.Проблемные вопросы и совершенствование методов кластерного анализа
1.8. Основные выводы по Главе
ГЛАВА 2. АНАЛИЗ МЕТРИК И ПОСТРОЕНИЕ МОДЕЛЕЙ РАЗМЕЩЕНИЯ ТОЧЕК НА СФЕРЕ ДЛЯ РЕШЕНИЯ ЗАДАЧ ГЕОМЕТРИЧЕСКОЙ КЛАСТЕРИЗАЦИИ
2.1. Метрика Махаланобиса. Предварительные исследования
2.2. Квазиметрика для измерения расстояний между классами
2.2.1. Принцип объединения матриц ковариаций
2.2.2. Построение квазиметрики для измерения расстояния между классами
2.3. Задача об оптимальном размещении точек на сфере
2.4. Основные выводы по Главе
ГЛАВА 3. РАЗРАБОТКА МЕТОДОВ КЛАСТЕРНОГО АНАЛИЗА НА ОСНОВЕ СЕТЕВОЙ МОДЕЛИ И ВАРЬИРОВАНИЯ РАЗМЕРНОСТИ ПРИЗНАКОВОГО ПРОСТРАНСТВА
3.1. Метод геометрической кластеризации на основе сетевой модели
3.1.1.Постановка задачи
3.1.2. Общая схема метода
3.2. Применение сетевой модели для решения задачи коммивояжера
3.2.1. Задача коммивояжера
3.2.2. Решение задачи при равномерном размещением кластеров
3.2.3. Стратегии движения нейронов
3.2.4. Экспериментальные исследования сетевой модели
3.3. Оценки необходимого числа кластеров
3.3.1. Оценка числа кластеров для задачи о коммивояжере
3.3.2. Оценка числа кластеров для задачи кластеризации
3.4. Бинарная кластеризация на основе контура минимальной длины
3.5. Метод классификации на основе варьирования размерности пространства признаков
3.6. Совместное применение методов кластерного анализа
3.7. Основные выводы по Главе
ГЛАВА 4. ПРАКТИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧ КЛАССИФИКАЦИИ И КЛАСТЕРИЗАЦИИ СЛАБОСТРУКТУРИРОВАННОЙ ИНФОРМАЦИИ
4.1. Анализ документов, представленных полутоновыми снимками
4.1.1.Постановка задачи двухэтапной кластеризации
4.1.2.Распознавание и кластеризация полутоновых изображений
4.1.3.Бинарная классификация полутоновых изображений
4.2. Особенности выделения букв и слов на полутоновых снимках
4.2.1. Особенности выделения букв
4.2.2. Особенности выделения ключевых слов
4.2.3. Применение ИНС для кластеризации текстов и изображений
4.3. Кластеризация текстовых документов на основе набора метрик
4.31. Извлечение корпуса релевантных текстовых документов
4.3.2. Образование учебной выборки и предварительный сбор статистики
4.3.3. Векторизация документов
4.3.4. Алгоритм кластеризации
4.3.5. Аннотирование кластеров
4.3.6. Распределение всех документов корпуса по кластерам (классификация)
4.3.7. Анализ качества выполнения кластеризации
Основные выводы по Г лаве
ЗАКЛЮЧЕНИЕ
Список литературы

ВВЕДЕНИЕ
Актуальность темы
В процессе поиска информации в Интернет или базах данных часто требуется найти и разбить документы на тематические группы определенного назначения - кластеры. Под кластерным анализом будем понимать решение задач кластеризации (построения классов (кластеров) по заданному множеству объектов) и классификации (распознавания), т.е. отнесения объектов к одному из классов с помощью решающего правила или измерения расстояний. Кластерный анализ предполагает также проверку гипотез и сокращение признакового пространства. Применительно к слабоструктурированным данным он предназначен для анализа текстов и изображений с помощью векторно-пространственных моделей (vector space model).
Геометрическая кластеризация (geometric clustering) относится к методам получения минимального или заданного числа компактных групп, реализуемых с помощью матриц расстояний и графов. В задаче геометрической кластеризации представлены точки потенциально высокоразмерного пространства, на котором определена метрика. Существенное значение имеет здесь сокращение размерности данных и визуализация результатов. Исследования геометрической кластеризации, в основном, представлены работами зарубежных ученых США: Still S., Bialek W., Bottou L., Sun J., Yao Y., Matousek J., Японии: Imai I., Inaba M., Imai H., Sadakane K. и др.
Большой вклад в развитие общей теории кластерного анализа внесли 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. (методы к-средних); 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 P., Tou J.T., Gonsales R.C., Fukunaga K., Patrick E

Концепт (concept) - описательная схема для класса вещей или конкретный пример такой схемы. Сравнительные характеристики некоторых алгоритмов кластеризации документов в соответствии с работой [52] приведены в табл. 1.4.
Таблица 1.4 - Сводка основных характеристик алгоритмов кластеризации документов
Название метода Наличие пересечения кластеров Используемые числовые характеристик и документов Предварительно e обучение Оценка сложности работы (N-число документов, k-число кластеров)
LSI - Tfidf - N2 k, (N=terms+docs, к-factors)
STC + - - 0(к2 N)
Single Link, Complete Link, Group Average Similarity matrix Single Link ~ 0(N2) Complete Link ~ 0(NJ) Group Average ~ 0(N2)
Scatter/Gather Similarity matrix Buckshot ~ O(kN), Fractionation ~ O(mN), m=0(k)
K-means - Tfidf - 0(N)
CI- необучаемый вариант Cl - обучаемый вариант Similarity matrix Similarity matrix или tfidf + 0(N*log k)
SOM (ИНС Кохонена) + Similarity matrix или tfidf +
В связи с созданием сверхбольших баз данных, появились новые требования,
которым должен удовлетворять алгоритм кластеризации. Основное из них -масштабируемость алгоритма. Отметим также другие свойства, которым должен удовлетворять алгоритм кластеризации: независимость результатов от порядка входных данных; независимость параметров алгоритма от входных данных. К таким алгоритмам, в которых методы иерархической кластеризации интегрированы с другими методами, относятся: BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies), Clarans (Clustering Large Applications based upon RANdomized Search), WaveCluster [49].
В настоящее время крупные Интернет-компании внедряют алгоритмы индексирования и кластеризации на базе нейронных сетей, что улучшает релевантность поисковой информации к запросу. Примером служит система обработки естественного языка DISCERN [55] поисковой информации к запросам пользователей. Нейронные сети приспособлены обрабатывать информацию, представленную числовыми векторами, поэтому для их применения в обработке текстов на естественном языке (ТЕЯ), тексты необходимо представлять в векторном виде.
1.7.2.Постановка задачи классификации текстов на естественном языке
Постановку задачи рассмотрим на основе работы [56]. Пусть имеется множество