43090

ОБЛАКО ТЕГОВ ДЛЯ ИНФОРМАЦИОННОЙ ФИЛЬТРАЦИИ ДАННЫХ

Курсовая

Информатика, кибернетика и программирование

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

Русский

2015-01-19

33.5 KB

9 чел.

ОБЛАКО ТЕГОВ ДЛЯ ИНФОРМАЦИОННОЙ ФИЛЬТРАЦИИ ДАННЫХ

Д.В. Манаков, Р.О. Судариков

ИММ УрО РАН, УрФУ, Екатеринбург

Параллельная фильтрация данных наряду с параллельным рендерингом активно применяется для сокращения объема визуализируемых данных.

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

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

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

Правильное решение проблемы эффективности возможно только на основе формальной модели. “В огромном числе случаев при попытке построить модель какого-либо объекта либо не возможно прямо указать фундаментальные законы, или вариационные принципы, которым он подчиняется. Одним из плодотворных подходов к такого рода объектам является использование аналогий с уже изученными явлениями.”  [1]

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

Одна из возможных аналогий – это оптимальное управление, то есть постановка каких-то минимаксных задач для визуализации. Так фильтрацию можно рассмотреть, как интерактивный процесс, целью которого является получение максимума информации с минимальными затратами. Или в общем случае, как нахождение минимума когнитивного расстояния, которое измеряет усилия пользователя, необходимые для преобразования действий по вводу данных и представлений выводимой информации в операции и объекты прикладной области. Для поиска применяется алгоритм MapReduce, если вид отображения выбрать аналогичный этому алгоритму, то возможно когнитивное расстояние уменьшится.

Возможность применения топологического анализа в визуализации продемонстрировано в работе [2], где облако точек отображает трассу программы.

Нами рассматривается возможность применения теории грубых множеств для задач визуализации и обработки информации. Теорию грубых множеств можно рассматривать как одно из развитий идеи Фреге о неопределенности, в частности, в данном подходе нечеткость определяется через границу множества, а не через частичную принадлежность, как в теории нечетких множеств. Если знаний о множестве не достаточно для его строгого определения, то граница не равна нулю, иначе стандартное (четкое) множество. Граница, как топологическое понятие – разность между замыканием и внутренностью множества. Важное понятие данной теории – гранулярность. Множество представляется в виде совокупности элементарных знаний, например, для визуализации - это графические примитивы.

Задание функций принадлежности для множества можно рассматривать, как способ упорядочения этого множества. Так же очевидно параллель c ассоциативными массивами. Наибольший интерес представляет рассмотрение функций принадлежности грубых множеств, как относительную метрику оценки эффективности. В общем случае, можно рассмотреть нечеткое множество X, где для каждого элемента множества (объекта) задана функция принадлежности X(x)[0,1], которая задает степень принадлежности элемента множеству, в отличие от классической теории, когда элемент точно принадлежит множеству. В частности облако тегов можно рассматривать, как множество слов, которое упорядочивает функция принадлежности, и отражает частотные характеристики.

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

Метафора контекстного облака тегов является расширением  стандартного облака тегов с заданием нескольких функций принадлежности для множества, включающего результаты поиска. Результаты поиска (нечеткое множество X) представим в виде массива ассоциативных массивов, где центральный элемент массива – строка поиска. Формально задаются две функции принадлежности: ширина контекста (количество слов поиска слева и справа от строки поиска) и  частота встречаемости слова, зависящая от типа документа с расширением pdf, doc, html соответственно отображается градацией цвета R,G,B. Результаты поиска также включают название документа и гиперссылку, которые выделяются через взаимодействие с конкретным словом (ключом).

Программа реализована на языке Ruby  и по архитектуре соответствует облачным вычислениям.  Модуль посредник перехватывает результаты поиска через Google API и реструктуризирует данные в виде ассоциативных массивов. В результате взаимодействие в клиентской части строится на основе хеширования, то есть практически без пересчета.  Предполагается интеграция разработанной системы с сервером распределенных вычислений Hadoop.

Литература

1. Самарский А.А., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. - М.: Физматлит, 1993, - 320 с.

2. Choudhury, A.N.M.I.; Bei Wang; Rosen, P.; Pascucci, V. Topological analysis and visualization of cyclical behavior in memory reference traces // Pacific Visualization Symposium (PacificVis), 2012 IEEE,vol., no., pp.9-16, Feb. 28 2012-March 2 2012.

Работа выполнена при поддержке программы Президиума РАН № 18 "Алгоритмы и математическое обеспечение для вычислительных систем  сверхвысокой производительности", а также проекта 12-П-1-1034 УрО РАН.


 

А также другие работы, которые могут Вас заинтересовать

27902. Пластины АКБ 34 KB
  Сильно сульфатированные пластины бракуют слабо сульфотированные восстанавливают без разборки без разборки батарей продолжительным зарядом током малой силы не более 005 от емкости при низкой плотности электролита не более 111 2 Варианты ремонта ЦПГ двигателя поминальный размер ремонтный размер сухая и мокрая гильза Различают мокрые и сухие гильзы. Внешняя поверхность мокрых гильз омывается охлаждающей жидкостью а сухие гильзы непосредственно с охлаждающей жидкостью не соприкасаются и избыточное тепло отводится через...
27903. ОПРЕДЕЛЕНИЕ ЧИСЛО ПОСТОВ 47.5 KB
  Xео и то: такт ритм Хто2 Д = такт ритм ню ню коэф исп времени рабочего поста 2 Основные конструкционные стали применяемые в автомобилестроении и авторемонтном производстве и их характеристики. Конструкционные стали предназначены для изготовления деталей машин машиностроительные стали. К этой группе относятся углеродистые и легированные стали с содержанием не более 0708 углерода. Низкоуглеродистые стали до 03 углерода пластичны хорошо свариваются и деформируются.
27904. Организация заправки а/м сжиженным газом (стационарные, полустационарные, передвижные АГНС) 70.5 KB
  Оборудование для восстановления протектора Для горячей накатки протектора Для холодной накатки протектора 4 Характеристика основных разделов текущего плана АТП План перевозок грузов пассажиров Разработка плана установление объемов и структуры транспортных услуг которые намечается предоставить потребителю. Основой составления плана является анализ показателей использования подвижного состава за предшествующий период. Разработка плана ведется по двум направлениям: Расчет показателей на основе известных объемов и структуры перевозок...
27905. Особенности пуска двигателя на газе и переключения с одного топлива на другое 59.5 KB
  Уровень механизации. Одним из основных показателей использования средств механизации является уровень механизации. Уровень механизации определяется долей трудовых затрат на ТО и Р а м выполняемых с использованием средств механизации в общих трудозатрат выраженных в . При определении уровня механизации все работы делятся на: механизированные; механизированоручные; работы выполняемые в ручную.
27906. Особенности хранения газобаллонных а/м на стоянках закрытого типа 40.5 KB
  В места хранения автомобилей в помещении и на посты линии ТО и ТР автомобили должны поступать после проверки герметичности газовой системы питания с выработанным газом при закрытых расходных вентилях. Допускается проектировать помещения для хранения газобаллонных автомобилей без естественного освещения. В одноэтажном здании помещения для газобаллонных автомобилей должны быть отделены от помещений для карбюраторных и дизельных автомобилей несгораемыми стенками и перекрытиями с пределом огнестойкости не менее 15 ч. В помещениях для...
27907. Диагностирование рулевого управления. Параметры. Оборудование 38.5 KB
  При диагностике РУ определяют люфт рул колеса и усилие необходимое для его поворота при вывешенных колёсах потерь на трение проверяют также крепления и состояние шарнирных сочленений тяг рулевого привода. На а м с гидравлическим усилителем рулевого управления люфт измеряют при работающем двигателе. Кроме люфта рулевого колеса необходимо проверить зазоры в шарнирных соединениях рулевых тяг по относительному перемещению шаровых пальцев и наконечников или головок тяг при резком повёртывании рулевого колеса в обе стороны зазор в...
27908. Причины, затрудняющие пуск холодных двигателей. Средства, облегчающие пуск холодных двигателей (без подогрева, разогрева) 188.5 KB
  Припуском на обработку называется слой металла подлежащий удалению с поверхности заготовки в процессе обработки для получения готовой детали. Размер припуска определяют разностью между размером заготовки и размером детали по рабочему чертежу; припуск задается на сторону. Обозначая общий припуск на обработку z0 размер заготовки аз и размер готовой детали ад получаем: для наружных поверхностей z0 = аз ад; для внутренних поверхностей z0 = ад аз. Тогда общий припуск на обработку равен сумме межоперационных припусков по всем...
27909. Процессы, происходящие в природе и технике 102.5 KB
  Процессы, происходящие в природе и технике, могут быть подразделены на две большие группы: процессы, описываемые функциональными зависимостями, и случайные или вероятностные (стохастические) процессы
27910. Исследование работы неуправляемых однофазных выпрямителей с помощью по «Electronics Workbench» 311.5 KB
  Выпрямители служат для преобразования переменного напряжения питающей сети в постоянное. Основными компонентами выпрямителей служат вентили – элементы с явно выраженной нелинейной вольт-амперной характеристикой. В качестве таких элементов используют кремниевые диоды.