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 УрО РАН.


 

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

40997. ОСНОВНІ СВІТОГЛЯДНІ СИСТЕМИ УКРАЇНСЬКОГО ФОЛЬКЛОРУ 118 KB
  Складність її вирішення криється у значному часовому проміжкові що віддаляє нас від того періоду життя суспільства коли виникали перші уявлення та вірування пов'язані з ними ритуальні та магічні дії що становлять основу народної творчості. Вивчення історичних зв'язків давніх епох та народів виходить поза межі окреслені фольклористикою але в них можна знайти пояснення багатьох елементів та рис пов'язаних з виникненням усної народної творчості. Людина уявляючи себе дублікатом зовнішнього світу робить все те що відбувається у...
40999. Кар'єра як стратегія трудового життя. Планування і розвиток кар’єри 67 KB
  Ринок праці в сучасних економічних умовах характеризується високою конкуренцією і пред'являє до людини жорсткі вимоги: наявності не тільки відповідної кваліфікації, але і досвіду роботи, комунікабельності та новаторського мислення. Все це ускладнює процес працевлаштування навіть для висококласних професіоналів.
41000. Комплексоутворення в біологічних системах 55 KB
  Координаційне число це число яке показує скільки простих лігандів координується навколо центрально атома.До тридентантних лігандів можна віднести аспарагінову кислоту до полідентантних деякі аміно карбонові та поліамінокарбонові кислоти. Число приєднаних лігандів дорівнює координаційному числу поділеному на дентатність ліганду. Ось чому координаційне число не завжди збігається з числом приєднаних лігандів.
41001. Правове регулювання кредитних правовідносин 82 KB
  Характеристика форм та видів кредиту. Принципи за якими здійснюється банківське кредитування. Структура типової форми кредитного договору.
41002. Мистецькі здобутки української культури початку 20 століття 90.5 KB
  Міністерство освіти та науки України Донецький індустріальнопедагогічний технікум Лекція âКультура Київської Русіâ План.Особливості світогляду в епоху Київської Русі.Архітектура Київської Русі.Скульптура Київської Русі.
41003. Українське козацьке бароко 59.5 KB
  Архітектура українського бароко.Українська скульптура періоду бароко.Особливості барокової графіки.В архітектурних стилях XVII – XVIII ст. виявляються урізноманітнення економічного, політичного й культурного життя українського суспільства. Естетичні риси української архітектури яскраво виявлені у будівлях стилю бароко. Українське бароко поширюється у XVIIIст.
41004. Культурологія як наукова дисципліна: об’єкт і предмет 50.5 KB
  Сутність культури визначається у трьох основних її сферах: предмети матеріальної і духовної діяльності людини; субєкти творці і носії культури; національний характер народу менталітет мораль. Творчість від Бога і людини. Захід протиставляє Людину і Природу людина панує над природою може змінити її у відносності до своїх уявлень про досконалість і потреб єдність людини з природою можлива через підлаштування пристосування до людини. Східна культура орієнтується на нерозривність людини і природи на їх єдність на основі...
41005. СУТЬ, РОЛЬ І МЕТОДОЛОГІЧНІ ОСНОВИ МЕНЕДЖМЕНТУ 455 KB
  Суть зміст менеджменту та управління Менеджмент як система наукових знань та як мистецтво управління Рівні управління. Методи досліджень Менеджмент як специфічна сфера людської діяльності Будьяке управління це не тільки управління своїм часом а й управління процесами часу.