Визуализация кластерной структуры. Bubble Sets - Визуализация графа цитирования

Для визуализации кластерной структуры был выбран алгоритм Bubble Sets [18]. Это гибкий алгоритм, относящийся к оверлеям, основанным на областях пространства (см. Главу 1). Этот алгоритм в большей степени удовлетворяет требованиям к кластерной визуализации. Он способен, как учитывать графовую структуру множеств, на которых он работает, так и не учитывать.

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

Контур, иначе называемый "пузырь", описывается, как функция от двух переменных.

.

Здесь функция E понимается, как энергия пикселя с координатами X, y. А С как потенциальная энергия. Если функция E непрерывна, то и контур будет непрерывным.

Абстрактно шаги алгоритма для каждого кластера можно описать следующим образом:

    1. Для каждого объекта из кластера ищем оптимально соседа (также объекта из кластера), и строим между ними ломанное виртуальное ребро, по возможности, избегающее элементов не из кластера. 2. Считаем потенциальную энергию каждого пикселя. Под "пикселем" понимается группа реальных пикселей, размер которой дает баланс между производительностью и точностью: чем больше группа - тем меньше точность, но выше скорость выполнения. 3. С помощью алгоритма Marching squares выделяем контур, уменьшая пороговое значение (параметр алгоритма) пока все элементы кластера не будут внутри, или пороговое значение не достигнет 0. 4. Рисуем полученный пузырь с помощью сплайнов.

Теперь подробно рассмотрим эти шаги. Значения и являются параметрами алгоритма, их значение будет объяснено нижу..

Для начала нужно создать виртуальные ребра (virtual edges), которые будут учитываться при подсчете энергии. Ребра должны проложить путь, избегая препятствий. Препятствием считается объект, не входящий в кластер.

Предварительно устанавливаем прямоугольную рабочую область в которую входят все элементы кластера + дополнительное место во все стороны равное. Далее мы работаем только с объектами, находящимися внутри найденной области или пересекающих ее. Также необходимо найти центроиду кластера.

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

.

Где distance - минимальное расстояние между границами объектов, а obstacles - количество объектов-препятствий, не входящих в кластер, на пути ребра.

Далее мы проверяем полученное ребро на пересечение с объектами, не входящими в кластер. Если оно найдено мы ломаем ребро в контрольной точке так, чтобы избежать пересечения, если это возможно. Эта точка выбирается на расстоянии длинной от до 0 от угла препятствия. Углы и расстояния перебираются, пока контрольная точка находится в каком-либо препятствии. Если какая-либо часть сломанного ребра имеет пересечения с препятствиями, алгоритм применяется к ней рекурсивно. Этот процесс проиллюстрирован на рис. 7.

процесс создание виртуального ребра [19]

Рисунок 7. Процесс создание виртуального ребра [19]

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

Следующим шагом алгоритма является вычисление энергии. Для вычисления энергии вначале пространство разбивается на группы пикселей (обычно 9х 9 или 3х 3).

Потенциальная энергия группы пикселей (далее просто "пиксель) считается следующим образом:

.

,

Где - расстояние, где энергия равна 1, - расстояние, где энергия достигает 0 (эти параметры эвристические, их надо подбирать). - все элементы, влияющие на энергию пикселя. - веса, присвоенные элементам. - расстояние между границами объекта.

Веса элементам присваиваются следующим образом:

    - Ребрам (как виртуальным, так и структурным) и объектам из кластера присваивается вес 1 - Объектам, не входящим в кластер -0.8 - Ребрам не из кластера присваивается вес 0.

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

После вычисления энергии необходимо получить контур. Для этого используется алгоритм Marching squares. Вначале алгоритм бинаризует все значения пикселей. Если значение энергии меньше порогового значения, то значение пикселя приравнивается 0, иначе 1. Далее строится сетка в узлах которой находятся бинаризованные пиксели. Каждой ячейке сетки выдается номер, получаемый из значений в ее узлах. Далее полученный номер сравнивается со значением в специальной таблице, в которой каждому номеру сопоставляется, что надо отрисовать в ячейке сетки. Таким образом выстраивается пузырь. Если контур содержит все не объекты из кластера, то алгоритм повторяется с другим пороговым значением.

Последним этапом алгоритма является отрисовка самих пузырей. Для этого выбирается каждая 10-ая (возможны другие значения) точка из контура и между ними строится кубический сплайн.

Глава 3

В данной главе будут рассмотрены основные аспекты имплементации программы и алгоритмов, которые она использует. Сама программа состоит из двух частей - клиентской (основной) и серверной. О каждой из них будет написано отдельно.

Похожие статьи




Визуализация кластерной структуры. Bubble Sets - Визуализация графа цитирования

Предыдущая | Следующая