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


 

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

29165. Ответственность за неисполнение денежного обязательства 26 KB
  Размер процентов определяется существующей в месте жительства кредитора а если кредитором является юридическое лицо в месте его нахождения учетной ставкой банковского процента на день исполнения денежного обязательства или его соответствующей части. При взыскании долга в судебном порядке суд может удовлетворить требование кредитора исходя из учетной ставки банковского процента на день предъявления иска или на день вынесения решения. Проценты за пользование чужими средствами взимаются по день уплаты суммы этих средств кредитору если...
29166. Общая характеристика оснований прекращения обязательств 24 KB
  Обязательство прекращается полностью или частично по основаниям: Надлежащее исполнение кредитор принимая исполнение обязан по требованию должника выдать ему расписку в получении исполнения полностью или в соответствующей части акт выполненных работ. Отступное – по соглашению сторон обязательство может быть прекращено предоставлением взамен исполнения отступного уплатой денег передачей имущества. Зачет – Обязательство прекращается полностью или частично зачетом встречного однородного требования срок которого наступил либо срок...
29168. Судебная баллистика 52.5 KB
  Судебная баллистика – это отрасль криминалистической техники, изучающая огнестрельное оружие и боеприпасы, следы их применения, а также разрабатывающая приёмы и методы обнаружения, собирания и исследования этих объектов с целью решения вопросов установления истины по делу, решения вопросов и задач расследования
29169. Криминалистическое значение следов крови 54 KB
  Прочие следы включают в себя: следы отображения (следы зубов, ногтей, кожного покрова тела человека) следы вещества (это биологические следы: кровь, слюна, сперма, а также следы других выделений человеческого организма)
29170. Почерковедческая экспертиза 62 KB
  Следовательно объектами почерковедческой экспертизы являются рукописные документы фрагменты рукописных текстов краткие записи буквенные и цифровые подписи. Одним или разными лицами выполнены тексты подписи в различных документах либо отдельной части текста в одном документе например подписи от имени гна Иванова в накладной и расходном ордере или рукописный текст и подпись от имени гна Иванова Диагностические задачи связаны с решением вопросов: 1. Свободные образцы – рукописи и подписи выполненные до начала производства по...
29172. Установление дистанции выстрела 56 KB
  Принято выделять 3 основных дистанции выстрела: 1 выстрел в упор Выстрел в упор происходит тогда когда дульный срез оружия касается преграды при производстве выстрела. В этом случае: может наблюдаться отпечаток дульного среза оружия штанцмарка на преграде теле человека дополнительные следы выстрела находятся внутри раневого канала. 2 выстрел с близкого расстояния В этом случае дополнительные факторы следы выстрела находятся вокруг входного отверстия.
29173. Криминалистическая регистрация 58.5 KB
  Виды учетов соответствующие им формы информационных карт а также порядок систематизации информации об объектах учета в рамках одного вида учета определяется МВД России. Криминалистическая регистрация насчитывает множество различных видов учетов. Оперативносправочные учеты чаще всего характерно наличие причинноследственной связи между объектом учета и событием преступлением. К оперативносправочным учетам относят учет: лиц подвергшихся аресту; лиц осужденных за совершение преступлений; лиц находящихся в розыске; лиц совершивших...