Сеточный алгоритм кластеризации c использованием ансамблевого подхода к принятию решений для обработки больших массивов данных

Семинар: Информационные технологии
Начало заседания: 14:35

Дата выступления: 11 Май 2010

Организация: НГУ

Авторы: Рылов Сергей Александрович

При решении задач, связанных с мониторингом окружающей среды, часто возникает необходимость кластеризации больших массивов данных при отсутствии каких-либо априорных сведений об искомых классах. В этих условиях целесообразно применять так называемые сеточные (grid-based) алгоритмы кластеризации, использующие сетку с фиксированным шагом. Вычислительная сложность таких алгоритмов определяется числом элементов сеточной структуры и практически не зависит от количества классифицируемых объектов. Кроме того, они позволяют выделять кластеры сложной формы без каких-либо предположений о структуре данных. Однако результаты кластеризации при этом существенно зависят от выбора шага сетки, что значительно затрудняет их практическое применение. Для решения этой проблемы в последние годы активно развиваются сеточные методы, основанные на использовании не одной, а на нескольких сеток с фиксированным шагом. В данной работе предлагается алгоритм кластеризации, использующий промежуточные результаты, полученные алгоритмом CCA на последовательности сеток с фиксированными шагами. Алгоритм кластеризации CCA основывается на введении клеточной структуры в пространстве признаков и разбиении клеток на классы, используя оценку плотности распределения данных. Конечный результат определяется с помощью ансамблевого метода, основанного на построении согласованной матрицы различий. После вычисления согласованной матрицы различий для нахождения итогового решения применяется метод построения дендрограммы, основанный на агломеративной кластеризации. Алгоритм позволяет выделять многомодовые кластеры сложной формы и формировать решение, устойчивое к изменению шага сетки.