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


 

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

19605. Види та способи вибору конструкційних матеріалів. Породи дерев та їх будова 102.03 KB
  Урок 7. Види та способи вибору конструкційних матеріалів. Породи дерев та їх будова 1год. Мета уроку. Засвоєння знань про породи деревини та її будову сортамент виготовлення шпону фанери ДВП ДСП та їх призначення; формування умінь здійснювати вибір матеріалу для виг...
19606. Техніка. Короткі відомості з історії розвитку техніки 31.2 KB
  Техніка і технологічні процеси виготовлення виробів з конструкційних матеріалів Урок 8. Техніка. Короткі відомості з історії розвитку техніки 1 год. Мета. Засвоєння знань про історію розвитку техніки та роль машин у сучасному виробництві і побуті як знарядь праці; п
19607. Типові та спеціальні деталі. Види з’єднань 28.39 KB
  Урок 9. Типові та спеціальні деталі. Види зєднань 1 год. Мета уроку. Засвоєння знань про типові та спеціальні деталі види зєднань формування практичних вмінь у зєднанні деталей. Розвиток в учнів памяті. Виховання основ культури праці. Обєкт навчальної праці: мех...
19608. Ознайомлення з механізмами у шкільній майстерні 77.59 KB
  Урок 10. Ознайомлення з механізмами у шкільній майстерні 1 год. Мета. Засвоєння знань про графічне зображення механізмів кінематичні схеми. Формування вмінь виконувати графічне зображення деталей і механізмів. Розвивати просторову уяву. Виховувати інтерес до технік...
19609. Виробничий процес. Етапи виготовлення виробу. Прийоми вимірювання лінійкою і кутником 31.79 KB
  Урок 11. Виробничий процес. Етапи виготовлення виробу. Прийоми вимірювання лінійкою і кутником 1 год. Мета уроку. Засвоєння знань про виробничий процес етапи виготовлення виробу вимірювання і розмічання; формування вмінь вимірювати і розмічати заготовки. Розвивати т
19610. Прийоми пиляння фанери ножівкою 58.93 KB
  Урок 12. Прийоми пиляння фанери ножівкою 1 год. Мета уроку. Засвоєння знань про способи пиляння деревини. Засвоєння вмінь виконувати пиляння фанери ножівкою. Розвивати окомір. Виховувати акуратність дисциплінованість. Обєкт навчальної праці: кухонна дошка Облад...
19611. Прийоми пиляння фанери лобзиком 26.59 KB
  Урок 13 14. Прийоми пиляння фанери лобзиком 2 год. Мета уроку. Формування вмінь виконувати пиляння фанери лобзиком; закріплення знань про пиляння деревини. Розвивати точність окомір. Виховувати акуратність виконавчу дисципліну творче ставлення до праці. Обєкт нав...
19612. Свердління отворів коловоротом і ручним дрилем 55.43 KB
  Урок 15. Свердління отворів коловоротом і ручним дрилем 1 год. Мета уроку. Засвоєння знань про будову і принцип дії коловорота та ручного дриля; формування вмінь користуватись ручним дрилем та коловоротом. Розвивати окомір точність. Виховувати економне ставлення до ма...
19613. Обпилювання фанери рашпілем, напилком. Шліфування фанери наждачною шкуркою 28.34 KB
  Урок 16. Обпилювання фанери рашпілем напилком. Шліфування фанери наждачною шкуркою 1 год. Мета уроку. Засвоєння знань про прийоми обпилювання фанери рашпілем напилком; формування вмінь виконувати операції обпилювання та шліфування. Виховувати елементи культури пра