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


 

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

13836. CМИ подсчитали, сколько стоят предвыборные обещания: Миронов, Зюганов и Жириновский превзошли даже Путина 18.05 KB
  CМИ подсчитали сколько стоят предвыборные обещания: Миронов Зюганов и Жириновский превзошли даже Путина В нынешней президентской кампании обещания стоят дорого. Чтобы выяснить насколько дорого Московский комсомолец обратился за помощью к одной из экспертных орг
13837. В Москве решили строить ЕврАзЭС по образу Евросоюза 18.75 KB
  В Москве решили строить ЕврАзЭС по образу Евросоюза За экономической интеграцией последует политическая. Такова логика процесса объясняют в Белом доме Президент РФ Дмитрий Медведев в центре и члены Высшего Евразийского экономического совета проходят на очередно...
13838. Валютная война или Замкнутый круг? США и Китай в одной упряжке 17.41 KB
  3 Валютная война или Замкнутый круг США и Китай в одной упряжке Несмотря на валютный конфликт между США и Китаем серьезной угрозы возникновения курсовой войны директорраспорядитель МВФ Доминик СтроссКан не видит. Таким образом глава МВФ опроверг мнение
13839. Власти РФ хвалятся небывалым демографическим успехом, а эксперты пугают: от ямы не спасут даже мигранты 18.85 KB
  Власти РФ хвалятся небывалым демографическим успехом а эксперты пугают: от ямы не спасут даже мигранты Российские власти объявили: впервые за весь постсоветский период удалось стабилизировать численность населения страны. Естественная убыль населения сократилась по
13840. Всемирный банк оценил выгоды России от вступления в ВТО 13.01 KB
  Всемирный банк оценил выгоды России от вступления в ВТО Выгоды ВВП от вступления России в ВТО в среднесрочной перспективе составят 33 процента от ВВП. В денежном выражении показатель составит 49 миллиардов долларов. Об этом сообщается в докладе Всемирного банка опублико...
13841. Всю жизнь с протянутой рукой 33.5 KB
  Всю жизнь с протянутой рукой Лучший способ найти деньги – попросить их у государства считают в РЖД. Но аппетиты железнодорожной монополии велики а в бюджете есть и другие более важные расходы. Впрочем Якунин проблемы в этом не видит – если денег пока нет то их можно зан...
13842. ВТО по правилам Россия может ограничить доступ иностранных компаний к ста секторам экономики 18.68 KB
  ВТО по правилам Россия может ограничить доступ иностранных компаний к ста секторам экономики С вступлением России во Всемирную торговую организацию ВТО ее возможности по защитным мерам отраслей экономики не уменьшаться а вырастут. Массовое разорение производителе...
13843. Тесты для старшей школы по обществознанию 1.5 MB
  Общество как динамичная система. Духовная культура современного общества. Человек. Познание. Экономическая жизнь современного общества. Социальные отношения и взаимодействия в современном мире. Политические отношения в современном обществе. Право – регулятор общественных отношений
13844. Алгоритм и критерии выбора проектов девелопмента. Использование приемов оценки недвижимости при реализации проектов девелопмента 35 KB
  Алгоритм и критерии выбора проектов девелопмента. Использование приемов оценки недвижимости при реализации проектов девелопмента. Инициатором и организатором проектов развития недвижимости является как правило девелопер. При реализации какоголибо проекта девел...