Методы построения коллективных решений задачи кластерного анализа

• Автор: Бирюков, Андрей Сергеевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 100 с. : ил.

Содержание
Введение

Глава 1. Коллективные решения задачи кластерного анализа

1. Оптимальные комитетные решения, построенные по матрицам оценок

2. Построение оптимальных комитетных решений задач кластерного анализа

3. Подход к построению коллективного решения, основанный на повторной кластеризации результатов традиционными методами и их модификациями
4. Взаимосвязь комитетного синтеза и подхода, основанного на повторной кластеризации
Глава 2. Коллективные решения задачи кластерного анализа на основе восстановления компонент смеси по выборке объектов

1. Постановка задачи, идентифицируемость компонент

2. Одномерная задача восстановления параметров смеси

3. Алгоритмы решения задачи восстановления параметров смеси

4. Оптимальные коллективные решения на множествах одномерных решений
5. Практическая реализация алгоритмов решения задачи восстановления параметров смеси
Глава 3. Алгоритмы кластеризации, основанные на поиске оптимальных покрытий
1. Постановка задачи
2. Свойства задачи построения покрытия
3. Решение задачи построения оптимального покрытия
Глава 4. Результаты экспериментов
1. Сравнительные эксперименты на модельных задачах
2. Сравнительные эксперименты на реальных задачах Глава 5. Универсальная программная система интеллектуального анализа данных, распознавания и прогноза РАСПОЗНАВАНИЕ
1. Возможности системы РАСПОЗНАВАНИЕ 2. Структура программы 3. Практическое применение Заключение
Приложение 1. Идентифицируемость смесей, имеющих нормальную
плотность распределения объектов внутри классов
Приложение 2. Общие сведения о генетических алгоритмах
Приложение 3. Код Грея
Литература


В статистических моделях предполагается, что имеется конечное число / кластеров, априорные вероятности которых не известны. Для каждого кластера существует многомерная функция плотности распределения объектов, известная с точностью до набора числовых параметров. Считается, что кластеризуемая выборка объектов получена согласно данным вероятностным параметрам и функциям. Тогда задача нахождения неизвестных вероятностных параметров по заданной выборке объектов формулируется как задача поиска компонент смеси по заданной смеси. В ряде случаев, когда плотности компонент идентифицируемы, а функции плотностей являются дифференцируемыми, данная задача может быть успешно решена (например, с помощью метода максимального правдоподобия). После нахождения вероятностных параметров, кластеризация выборки осуществляется с помощью байесовского правила [1]. В методе динамических сгущений, являющимся далеким обобщением метода к -внутригрупповых средних, «среди всех разбиений на / кластеров следует найти разбиение, относительно каждого кластера которого заданное «ядро» оказалось бы наиболее представительным» []. Существуют подходы, основанные на использовании теории графов и различные эвристические подходы (метод к-эталонов, метод взаимного поглощения, и другие) []. Следует признать, что в настоящее время не существует универсальных методов кластерного, анализа. Основные проблемы их практического применения связаны с трудоемкостью и многоэкстремальностью возникающих оптимизационных задач, нахождением вырожденных решений, сложностью сравнения и интерпретации решений, полученных различными алгоритмами. Кроме того, как правило, для каждого известного метода кластеризации можно привести пример задачи, имеющей выраженную кластерную структуру, но при решении которой данным методом полученное решение не соответствует реально существующим группировкам данных. В ситуациях, когда при решении одной и той же задачи кластеризации различными алгоритмами находится множество существенно отличающихся решений, перспективным направлением исследований является разработка методов синтеза коллективных решений [2]. Коллективные подходы для решения задач кластерного анализа позволяют объединить в рамках единого формализма разнотипные алгоритмы кластеризации и находить оптимальные коллективные решения, в которых компенсируются неточности каждого из используемых базовых методов. Использование в качестве коллектива исходных решений набора локально-оптимальных кластеризаций позволяет существенно расширить размерности решаемых практических задач. В настоящей работе обобщается метод нахождения комитетных коллективных решений, а также исследуется подход к синтезу коллективных кластеризаций, основанный на исследовании внутригрупповых расстояний различных кластеров. Теория синтеза коллективных комитетных решений задачи кластерного анализа, впервые была предложена в [2]. Я - оператор, переводящий таблицу признаковых описаний в матрицу оценок степени близости объектов к каждому из кластеров, а г - решающее правило. Данная форма представления является аналогичной записи алгоритмов распознавания в алгебраической теории распознавания [, , ]. Для данного общего случая вводятся определения операторов синтеза коллективных комитетных решений и критерии их качества. Получена верхняя оценка вариации функционала качества и разработан эффективный алгоритм комитетного синтеза, основанный на последовательной минимизации данных оценок. Предложен подход для построения коллективных решений задачи кластерного анализа, основанный на использовании в качестве процедур коллективного синтеза известных методов кластеризации или их модификаций. Предложен и апробирован один алгоритм данного типа, основанный на идеях метода к-внугригрупповых средних. Обобщение комитетного синтеза коллективных кластеризаций на случаи, когда исходный коллектив алгоритмов вычисляет матрицы оценок объектов за каждый кластер, новые алгоритмы построения коллективных решений в задаче кластерного анализа и составляют содержание первой главы диссертации. Во второй главе рассматривается задача построения исходного набора кластеризаций.