Визуализация кластерной структуры. 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.
Рисунок 7. Процесс создание виртуального ребра [19]
В конце этого шага мы получаем множество ломанных виртуальных ребер для всех вершин, кроме самой дальней от центроиды.
Следующим шагом алгоритма является вычисление энергии. Для вычисления энергии вначале пространство разбивается на группы пикселей (обычно 9х 9 или 3х 3).
Потенциальная энергия группы пикселей (далее просто "пиксель) считается следующим образом:
.
,
Где - расстояние, где энергия равна 1, - расстояние, где энергия достигает 0 (эти параметры эвристические, их надо подбирать). - все элементы, влияющие на энергию пикселя. - веса, присвоенные элементам. - расстояние между границами объекта.
Веса элементам присваиваются следующим образом:
- - Ребрам (как виртуальным, так и структурным) и объектам из кластера присваивается вес 1 - Объектам, не входящим в кластер -0.8 - Ребрам не из кластера присваивается вес 0.
Для вычисления энергии для каждого из объектов обходятся все пиксели, находящиеся на расстоянии не дальше чем от его границ. Для каждого пикселя высчитывается энергия и прибавляется к текущей. Вначале считается энергия от объектов с положительными весами, потом с отрицательными, если у пикселя энергия на этот момент больше 0.
После вычисления энергии необходимо получить контур. Для этого используется алгоритм Marching squares. Вначале алгоритм бинаризует все значения пикселей. Если значение энергии меньше порогового значения, то значение пикселя приравнивается 0, иначе 1. Далее строится сетка в узлах которой находятся бинаризованные пиксели. Каждой ячейке сетки выдается номер, получаемый из значений в ее узлах. Далее полученный номер сравнивается со значением в специальной таблице, в которой каждому номеру сопоставляется, что надо отрисовать в ячейке сетки. Таким образом выстраивается пузырь. Если контур содержит все не объекты из кластера, то алгоритм повторяется с другим пороговым значением.
Последним этапом алгоритма является отрисовка самих пузырей. Для этого выбирается каждая 10-ая (возможны другие значения) точка из контура и между ними строится кубический сплайн.
Глава 3
В данной главе будут рассмотрены основные аспекты имплементации программы и алгоритмов, которые она использует. Сама программа состоит из двух частей - клиентской (основной) и серверной. О каждой из них будет написано отдельно.
Похожие статьи
-
Силовые алгоритмы для иерархически-кластеризованных графов - Визуализация графа цитирования
На данный момент мы рассмотрели алгоритм для отрисовки некластеризованных графов и их улучшения. Теперь необходимо изучить подходы, которые используются...
-
Силовые алгоритмы расположения вершин на плоскости - Визуализация графа цитирования
Классический подход к решению таких задач это использовать алгоритм из семейства силовых. Основная идея таких алгоритмов - это рассматривать графы как...
-
Автоматическое расположение вершин на плоскости - Визуализация графа цитирования
Первая проблема, о которой стоит поговорить - это проблема автоматического расположения вершин на плоскости. Для начала поставим базовую задачу, как она...
-
Автоматическая расстановка вершин на плоскости Для автоматической расстановки вершин использовался алгоритм основанный на работах Eades [9],...
-
Улучшения классических силовых алгоритмов - Визуализация графа цитирования
Первым улучшением является добавление псевдо-гравитационной силы [11]. Эта сила притягивает все вершины к центру рабочей области. Обычно она линейна...
-
Визуализация кластерной структуры - Визуализация графа цитирования
Следующей задачей, после расстановки вершин на плоскости, должна быть решена задача визуализации кластерной структуры. В данном разделе мы рассмотрим...
-
Существующие решения - Визуализация графа цитирования
На данный момент не было найдено решений, которые полностью бы удовлетворяли всем требованиям, однако существуют те, которые реализуют их не все и/или не...
-
Постановка задачи - Визуализация графа цитирования
В качестве результата выпускной квалификационной работы требуется создать программу, позволяющую визуализировать граф цитирования публикаций, которые...
-
Обзор предметной области, Графы цитирования - Визуализация графа цитирования
Графы цитирования Во время работы над научными статьями и проектами возникает необходимость хранить используемые публикации. Стандартный поход к этой...
-
Введение - Визуализация графа цитирования
В данной работе рассматриваются методы автоматической и полуавтоматической визуализации графов цитирования на плоскости. Визуализация графов на плоскости...
-
Итерационные алгоритмы разрезания графа на куски
Лекция Итерационные алгоритмы разрезания графа на куски Суть Итерационных Алгоритмов Разрезания Графов заключается в выборе первого случайного разрезания...
-
Самым традиционным и широко известным из структурированных типов данных является массив (иначе называемый регулярным типом) - однородная упорядоченная...
-
При создании проекта нужно указать его свойства: Application Name (название приложения), Project location (расположение проекта на диске), Min SDK...
-
Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается...
-
Предлагаемый метод моделирования, Структура системы. - Искусственный интеллект
В каждый момент времени анимат находится в некоторой области, которой соответствует некоторая когнитивная карта. Такая карта называется активной...
-
Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов
Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное...
-
ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных
Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берем средний элемент отсортированного массива и сравниваем с ключом X. Возможны...
-
Разработка структуры сайта Разработка структуры web-сайта является одним из ключевых моментов его создания, который в большой степени определяет...
-
Структура кластера и его параметры Вычислительный кластер -- это совокупность компьютеров, объединенных в рамках некоторой сети для решения одной задачи,...
-
Примеры визуального представления данных - Визуализация количественных данных
Визуализация программный обеспечение данные В научно-технической документации применяются различные виды визуализации (ниже приведены примеры...
-
Программы (ресурсы) для создания презентаций - Структура презентации
1.Microsoft PowerPoint Говоря "программа для презентаций" большинство подразумевают PowerPoint, аналогично и с другими программами пакета Microsoft...
-
Виды презентаций - Структура презентации
Существует несколько видов и типов презентаций. Различные виды презентации, как правило, отличаются своей функциональностью и стоимостью. Чем красивее и...
-
Введение - Структура презентации
Во время лекции, доклада или на иных выступлениях, как правило, используют средства наглядной демонстрации: плакаты, пособия, лабораторные опыты. Для...
-
2.1 Описание структуры базы данных Реляционная схема базы данных для ЦЗН представлена следующими таблицами: "ПО" - содержит список единиц программного...
-
Социальные сети: структура коммуникации online vs. offline - Распространение новостной информации
Одна из простейших форм передачи информации - это коммуникация. В то же время это многогранное понятие, включающее в себя различные особенности и...
-
Для того, чтобы понять структуру и сценарий Web-документа, мы должны рассмотреть несколько Web-страниц и выявить общие элементы. Любой Web-документ...
-
Программа задания случайных графов Эрдеша - Реньи - Алгоритмы нескольких махов
Программа реализует алгоритм задания случайных графов Эрдеша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер...
-
Структура проекта Программа была реализована на языке Java в среде разработки AndroidStudio с помощью инструментов для разработки Android SDK. Разработка...
-
Структура web-документа - Создание сайта
Каждый HTML-документ, отвечающий спецификации HTML какой-либо версии, должен начинаться со строки объявления версии HTML <!DOCTYPE...>, которая обычно...
-
Allocation Table, Структура системы FAT - Операционная система Windows
FAT (от англ. File Allocation Table - "таблица размещения файлов") - архитектура файловой системы, сейчас широко используемая в картах памяти...
-
Розроблений програмний модуль ІС "ГППР " призначений для використання на тепловій електростанції з метою забезпечення комплексної автоматизації обліку...
-
Некоторые хитрости - Компьютерная графика и ее аппаратная реализация (обзор видеокарт)
Для повышения реалистичности изображения разработчики игр. Сперва эта технология применялась для уменьшения нагрузки на акселератор или процессор (когда...
-
Rendering Synthetic Objects into Legacy Photographs - Моделирование эффектов
Более подробно остановимся на методе, описанном в работе "Rendering Synthetic Objects into Legacy Photographs" Karsch K. et al. Rendering synthetic...
-
Растеризация - Компьютерная графика и ее аппаратная реализация (обзор видеокарт)
Последний этап конвейера называется растеризацией и обозначается буквой "R". Это единственный этап конвейера, который даже в старых акселераторах...
-
Информационное обеспечение - совокупность единой системы классификации и кодирования информации, унифицированных систем документации, схем информационных...
-
ОСОБЕННОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ - Структуры и алгоритмы обработки данных
В ходе выполнения курсовой работы, помимо основных алгоритмов, потребовалось реализовать также несколько вспомогательных, необходимых для корректной...
-
Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы...
-
МЕТОДОВ МЕТОД СОРТИРОВКИ Пирамидальная сортировка Пирамидальная сортировка основана на алгоритме построения пирамиды. Последовательность aI, aI+1,...,aK...
-
Все рассмотренные ранее диаграммы отражали концептуальные аспекты построения модели системы и относились к логическому уровню представления. Особенность...
-
Некоторые сведения из теории графов - Алгоритмы нескольких махов
Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6]. Граф, или обыкновенный граф G -- это упорядоченная пара G := (V, E), где V -- это...
Визуализация кластерной структуры. Bubble Sets - Визуализация графа цитирования