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


 

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

11005. Жизнь и философствования Сократа 62 KB
  Жизнь и философствования Сократа Поворотным пунктом в развитии античной философии явились воззрения Сократа 469 – 399 до н.э.. Его имя стало нарицательным и служит для выражения иди мудрости. Сам Сократ ничего не писал был близким к народу мудрецом; философствовал на улиц...
11006. Основные черты средневекового христианского мировоззрения.(Бог, человек и мир в средневековой христианской философии) 38 KB
  Основные черты средневекового христианского мировоззрения.Бог человек и мир в средневековой христианской философии. Особенности философии СредневековьяВыделяют следующие особенности философии Средневековья: философское учение теоцентрично философия Средневеко
11007. Рационалистическая метафизика 17 века (Декарт, Спиноза, Лейбниц) 38 KB
  Рационалистическая метафизика 17 века Декарт Спиноза Лейбниц Рационализм направление признающее разум основой познания и поведения людей. Начал складывать в результате развития математики и естествознания. Исходит из идеи естественного порядка. Утверждает опр
11008. Полемика славянофилоф и западников в русской философии 74 KB
  Полемика славянофилоф и западников в русской философии Своеобразным направлением в русской философии явилось славянофильство ярким представиетелм которого были А.С.Хомяков 18041860 и И.В.Киреевский 18061856 оказавшие значительное воздействие на развитие русской мыс
11009. Истоки философии. Хронология и краткая характеристика основных этапов 46 KB
  Тема. Истоки философии Хронология и краткая характеристика основных этапов. Причины возникновения философии являются и причиной её развития. Данный вопрос является дискуссионным. Основные этапы развития мировой философии преимущественно связываются только с развит...
11010. Гносеология или теория познания 55 KB
  Гносеология. Гносеология или теория познания – это раздел философии в котором изучаются природа познания и его возможности отношение знания к реальности выявляются условия достоверности и истинности познания. Термин Гносеология происходит от греческих слов g...
11011. Закономерности исторического развития техники 46 KB
  Закономерности исторического развития техники. Проблема периодизации. Предметная сторона Т. Техника и наука. Т как деятельность. ФТ выделяет общие закономерности и стадии исторической эволюции Т потом это будет конкретизировано в истории Т. В отличие...
11012. Социальная роль техники 47 KB
  Социальная роль техники. Техника как основа социального прогресса. Информационное общество. Понятие техногенной цивилизации. Антитехницизм и его основания. Рассмотрены различные периодизации истории техники. Каждая новая стадия в развитии техники в
11013. Техника и наука в контексте культуры 58 KB
  Техника и наука в контексте культуры Специфика техники как феномена культуры. Технические науки как тип наук. В имеющихся определениях техники обнаруживается существенно общий смысловой срез: по отношению к человеку техника является вопервых воплощ