Кластеризация и визуализация экспериментальных данных в автоматизированной системе тематического анализа информации м.н.с. Титов А.С. НИИ механики МГУ

План доклада Что такое кластеризация и основные области её применения Что такое кластеризация и основные области её применения Этапы кластеризации, основные алгоритмы кластеризации Этапы кластеризации, основные алгоритмы кластеризации Алгоритм гравитационной кластеризации Алгоритм гравитационной кластеризации Алгоритм визуализации многомерных данных Алгоритм визуализации многомерных данных

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

Дистанционное зондирование Земли Задачей классификации является перенос нагрузки по анализу и обработки информации с человека на интеллектуальную технологию обработки. … Большинство методов классификации реализуются с помощью кластерного анализа. (ГЕОИНФОРМАЦИОННЫЙ АНАЛИЗ ДАННЫХ ДИСТАНЦИОННОГО ЗОНДИРОВАНИЯ, В.П. Савиных, В.Я. Цветков, Москва, 2001)

Анализ данных Скорой помощи

Традиционно кластеризация включает в себя следующие шаги: 1. Определить цель исследования. Это может быть или определение кластерной структуры данных (проверка наличия кластеров в данных) или разбиение объектов на группы по заранее определенному принципу, например, разбить множество книг по авторству или по их тематике. 2. Преобразование имеющихся данных в объекты для их кластеризации, например, определение набора слов, которые характеризуют тексты, определение переменных, характеризующих объекты, вычленение подпоследовательностей из генома. 3. Преобразование выбранных объектов в компьютерный вид, т.е. сопоставление значениям переменных числовые значения. 4. Задание метрики пространства. Для некоторых областей предпочтительны специфические метрики. 5. Выбор алгоритма кластеризации, что включает выбор параметров алгоритма, например, задание способа определения расстояния между группами точек, задание граничных параметров. 6. Интерпретация результатов кластеризации включает вычисление статистических характеристик каждого из кластеров и в результате сравнительного анализа проверяется соответствие заданному принципу разбиения. В случае несоответствия или отсутствия кластерной структуры проводится повторный процесс кластеризации с изменением настроек пунктов 1-4.

Краткий обзор методов кластеризации Классические алгоритмы Классические алгоритмы –Алгоритмы, основанные на минимизации функционала –Алгоритм К – средних –Форель(FOREL), ИСОМАД(ISODATA), ПУЛЬСАР –Иерархические алгоритмы Современные алгоритмы Современные алгоритмы –DBSCAN –BIRCH –CLARANS –CURE

Алгоритм К-средних Описание алгоритма: 1. Задание числа кластеров k, на которые надо разбить входные данные. 2. Выбор k точек в исходном пространстве, именуемые как центры кластеров. На практике в основном выбирают случайные точки исходных данных. 3. Для каждой точки входных данных находится ближайший центр кластера. Группа точек, ближайшая к некоторому центру кластера, называются кластером. 4. Вычисление для каждого кластера C его центра масс, которая объявляется новым центром кластера. 5. Повтор процедуры с 3 шага в том случае, если не выполняется критерий остановки, например,неизменность кластеров за несколько последних итераций.

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

Алгоритм К-средних Основные достоинства алгоритма: простота использовании метода - задание только одного параметра (числа кластеров). простота использовании метода - задание только одного параметра (числа кластеров). один шаг алгоритма – O(n*K*k). На практике число шагов не велико. один шаг алгоритма – O(n*K*k). На практике число шагов не велико. К недостаткам алгоритма стоит отнести следующие обстоятельства: число кластеров необходимо задавать, нет автоматического определения числа кластеров в исходных данных; число кластеров необходимо задавать, нет автоматического определения числа кластеров в исходных данных; результаты кластеризации алгоритма к-средних могут содержать ошибки, как это представлено на рисунке. результаты кластеризации алгоритма к-средних могут содержать ошибки, как это представлено на рисунке.

Алгоритм К-средних

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

Алгоритм гравитационной кластеризации Общее описание Общее описание Шаг 1: построение дерева объединений Шаг 1: построение дерева объединений Шаг 2: построение естественных кластеров Шаг 2: построение естественных кластеров Шаг 3: построение кластеризации Шаг 3: построение кластеризации

Алгоритм гравитационной кластеризации: общее описание

Алгоритм гравитационной кластеризации: построение дерева объединений numpoints=n;t=0;while(numpoints!=1){ объединение близких точек объединение близких точек движение точек движение точек} Объединение близких Две точки и объединяются, если где минимальное расстояние между точками в начальный момент времени (t=0), а первая константа алгоритма. Результатом объединения является точка с пересчитанными координатами: Объединение близких Две точки и объединяются, если где минимальное расстояние между точками в начальный момент времени (t=0), а первая константа алгоритма. Результатом объединения является точка с пересчитанными координатами: Движение точек шаг по времени определяется как, движение точек - Движение точек шаг по времени определяется как, движение точек -

Алгоритм гравитационной кластеризации: построение дерева объединений

Алгоритм гравитационной кластеризации: построениеестественных кластеров Упрощение дерева объединений Пусть - дети вершины рассмотрим величины - время жизни соотвествующих вершин Если или (где - время жизни вершины ), то вершины становятся детьми родительской вершины вершины Упрощение дерева объединений Пусть - дети вершины рассмотрим величины - время жизни соотвествующих вершин Если или (где - время жизни вершины ), то вершины становятся детьми родительской вершины вершины

Алгоритм гравитационной кластеризации: построениеестественных кластеров Определение естественных кластеров Вершину будем называть естественным кластером, если выполняется условие и вершине приписывается значение - коэффициент качества вершины Определение естественных кластеров Вершину будем называть естественным кластером, если выполняется условие и вершине приписывается значение - коэффициент качества вершины

Алгоритм гравитационной кластеризации: построение кластеризации Если выполнено то говорим, что естественный кластер допускает разбиение на более «качественное» множество кластеров и выполняется процедура для его детей. Иначе, множество точек, соответствующих вершине объявляется новым множеством. В результате выполнения этой процедуры сверху вниз получается набор непересекающихся кластеров Если выполнено то говорим, что естественный кластер допускает разбиение на более «качественное» множество кластеров и выполняется процедура для его детей. Иначе, множество точек, соответствующих вершине объявляется новым множеством. В результате выполнения этой процедуры сверху вниз получается набор непересекающихся кластеров

Достоинства –Автоматическое определение числа кластеров –Независимость настроек алгоритма от входных данных –Дерево объединения даёт представление о ходе работы алгоритма, что позволяет проанализировать структуру данных –Устойчивость алгоритма к изменениям входных данных

Устойчивость алгоритма гравитационной кластеризации Определение Алгоритм кластеризации устойчив на наборе данных если существуют такие что результаты кластеризации на наборах данных и совпадают, где. Определение Дерево объединений для набора данных будем называть устойчивым, если существуют такие, что дерево объединений для набора данных подобно дереву объединений для набора данных где Теорема (Устойчивость дерева объединений) Теорема (Устойчивость алгоритма гравитационной кластеризации.) Замечание Теорема верна для полной гравитационной кластеризации и для алгоритма по m ближайшим точкам.

Гравитационная кластеризация по m ближайшим точкам Основная идея - учитывать влияние только mближайших точек Пусть точкиобъединяютсяи первая стратегия если то пересчет m ближайших для точки вторая стратегия еслито или - m ближайших для точки

Гравитационная кластеризация с использованием CF-дерева CF-дерево, построенное по последователь- ности из n точек с параметрами B и T имеет максимальную глубину минимальная глубина при T=0 Основная идея – разбиваем множество на m групп, учитываем влияние на точку только точек из этой группы и остальных групп.

Модификации алгоритма гравитационной кластеризации Предложены следующие модификации алгоритма Алгоритм гравитационной кластеризации по m ближайшим точкам Алгоритм гравитационной кластеризации по m ближайшим точкам Алгоритм гравитационной кластеризации с использованием CF- и R- деревьев Алгоритм гравитационной кластеризации с использованием CF- и R- деревьев Алгоритм гравитационной кластеризации с разбиением каждой группы точек на кластеры Алгоритм гравитационной кластеризации с разбиением каждой группы точек на кластеры Оценка алгоритмической сложности Алгоритм гравитационной кластеризации Алгоритм гравитационной кластеризации Алгоритм гравитационной кластеризации по m-ближайшим Алгоритм гравитационной кластеризации по m-ближайшим Алгоритм гравитационной кластеризации с использованием CF- и R- деревьев Алгоритм гравитационной кластеризации с использованием CF- и R- деревьев Алгоритм гравитационной кластеризации с разбиением каждой группы точек на кластеры ( - полный алгоритм, по 1-й ближайшей точке – ) Алгоритм гравитационной кластеризации с разбиением каждой группы точек на кластеры ( - полный алгоритм, по 1-й ближайшей точке – )

Результаты работы гравитационного алгоритма

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

Области применения: обработка потоковой информации Проведенные испытания показывают, что использование дерева повышает точность определения рубрики при большом количестве рубрик с 60-65% до 87-92%

Области применения: Минимизация вычислений в задаче обтекания

Минимизация вычислений в задаче обтекания Пример разбиения множества вихрей на группы Цель: разбиение множества вихрей на кластеры, которые изолированы друг от друга, где число кластеров равняется числу процессоров. При этом в каждой кластере разбиение вихрей на компактные группы.

Сопоставление набору точек из многомерного пространства точек на плоскости с качественным отображением: Задача визуализации 1) кластерной структуры; 2) расположения данных в исходном пространстве; 3) взаимосвязи между точками.

Требования к алгоритму визуализации 1) интуитивно понятное изображение 2) простота в навигации по данным 3) эффективное использование области для изображения 4) отображение взаимосвязи между данными 5) отображение пространственной структуры данных

Существующие подходы 1)Многомерное шкалирование 2) TreeMaps 3) Botanical Tree 4) Star Tree 5) Hyperbolic Display 6) Визуализация графов

Treemaps Botanical Tree Star Tree

Соответствие предъявленным требованиям существующих методов Интуит. понятная визуализация Простота в навигации Эфф. испол. прост-ва Отобр-е взаимосвяз и Отобр-е кластерной структуры данных Многом.шкалир TreeMaps-++-- Botanical Tree Star Tree Hyper Tree Граф++++-

Визуализация многомерных данных Определение Визуализация множество где Определение Визуализатор множество визуализаций, т.е. Число s называется размером визуализатора. Утверждение Размер каждого визуализатора, состоящего из различных визуализаций, не превосходит Множество визуализаций, соответствующих каждой вершине дерева объединений, образует визуализатор, называемый деревом визуализации. Утверждение Размер дерева визуализации не превосходит

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

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

Построение дерева визуализации (визуализатора) При построении визуализатора на основе дерева объединений выполняются следующие шаги: Сопоставление визуализации точек на плоскости с помощью минимизации функции Сопоставление визуализации точек на плоскости с помощью минимизации функции Сопоставление визуализаций. Основные шаги: Сопоставление визуализаций. Основные шаги: –Выполнение смещения где –Выполнение поворота

Обеспечение плавности перехода от одной конфигурации к другой Смещение Смещение –В любой конфигурации всегда должна быть «точка в центре» с некоторыми фиксированными координатами Поворот Поворот –Осуществление поворота таким образом, чтобы сохранялась направленность данных

Структура хранения визуализатора Структура хранения визуализации данных – дерево (дерево визуализации), вершины которого содержат следующую информацию: –указатель на родителя; –указатели на детей; –указатели на вершины, отображаемые вместо с данной; –координаты вершин, отображаемых вместе с данной (визуализация).

Схема взаимодействия элементов системы визуализации Запрос конфигурации точек Клиентское приложение Передача конфигурации точек Обработчик запросов визуализации Запрос конфигурации точек Передача конфигурации точек Сервер обсчета функций интерфейса

Пример Раскрытие точки 6

Спасибо за внимание