WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 

«ТРУДЫ МФТИ. — 2014. — Том 6, № 3 43 Ю. С. Кашницкий УДК 004.51 Ю. С. Кашницкий Национальный исследовательский университет Высшая школа экономики Московский ...»

ТРУДЫ МФТИ. — 2014. — Том 6, № 3 43

Ю. С. Кашницкий

УДК 004.51

Ю. С. Кашницкий

Национальный исследовательский университет Высшая школа экономики

Московский физико-технический институт (государственный университет)

Визуальная аналитика в задаче трикластеризации

многомерных данных

Трикластеризация – это способ обнаружения объектов со схожими свойствами в

контексте из трех множеств сущностей. Например, в задаче анализа данных социальных сетей такими множествами могут быть пользователи, их интересы и события, в которых пользователи принимают участие. Трикластеризация здесь может помочь найти группы пользователей с похожими интересами и, например, делать им рекомендации событий на основе этих интересов. В статье описывается конкретный алгоритм трикластеризации и прототип программной платформы для визуального анализа полученных трикластеров.

Ключевые слова: визуальная аналитика, анализ данных, кластеризация, анализ формальных понятий, рекомендательные системы.

Введение Классический Анализ формальных понятий (АФП) имеет дело с данными, описывающими отношение на множествах объектов и их признаков (какой объект имеет какой признак), и предоставляет средства для определения в них иерархии.

На основе входных данных АФП выдает два вида выхода [1]. Первый – это решетка формальных понятий, то есть множество формальных понятий, иерархически упорядоченных по отношению «подпонятие–суперпонятие». Формальные понятия – это комбинации объектов и их признаков, представляющие жизненные понятия, которыми оперирует человек, такие как, например, «организм, обитающий в воде», «автомобиль с полным приводом», «числа, делящиеся на 3 и на 4» и так далее.


Второй результат АФП – это множество признаковых импликаций. Признаковая импликация описывает определенное правило, действующее на множестве формальных понятий, например, «любое число, делящееся на 3 и 4, также делится и на 6» или «каждый абонент старше 60 лет безработный». АФП – это мощное средство для обнаружения зависимостей в данных, которое широко применяется в таких сферах, как извлечение информации из данных (data mining), обработка текста, машинное обучение, управление знаниями, семантические сети и разработка ПО.

Как естественное развитие АФП, Триадический анализ формальных понятий (ТАФП) обрабатывает триадические данные (контексты) в виде объектов, их признаков и условий, при которых определенные объекты имеют определенные признаки. Один из типичных примеров применения – анализ данных социальной сети с контекстом в виде пользователей (объекты), событий, в которых пользователи принимают участие (признаки), и интересов пользователей (которые могут рассматриваться как условия, при которых данный пользователь участвует в данном событии).

По мере того как нахождение всех понятий или трипонятий заданного контекста начало становиться ресурсоемкой задачей, были предложены некоторые ослабления этих определений: бикластеры и трикластеры [3]. Здесь мы будем иметь дело с трикластерами - наборами множеств объектов, признаков и условий, таких что не обязательно каждый объект имеет каждый признак из этих множеств. Строгое определение трикластера мы дадим позднее, а здесь отметим, что трикластеризация позволяет намного проще оперировать большими объемами триадических данных и дает на выходе кластеры объектов со схожими признаками при схожих условиях. Таким образом, трикластеризация находит применение в таких Математика и информатика 44 ТРУДЫ МФТИ. — 2014. — Том 6, № 3 задачах, как, например, нахождение пользователей соцсетей со схожими интересами, претендентов на работу со сходными компетенциями или ресурсов Интернета, помеченных похожими тегами. Также на базе алгоритмов трикластеризации основаны некоторые рекомендательные системы [4].

Визуальная аналитика – одно из бурно развивающихся направлений информационных технологий, в котором человеческие и машинные ресурсы объединяются для решения спектра задач, непосильных для человека или компьютера по отдельности. Это подобласть анализа данных, акцентированная на принятии решений на основе предварительной обработки данных, извлечения информации из данных (data mining) и визуальных интерактивных пользовательских интерфейсах. Например, Siemens PLM Software позволяет пользователям собирать, обрабатывать и представлять отчетные данные прямо в среде проектирования новых видов транспорта, таким образом делая возможным принятие решение в процессе разработки. Этот же метод используется в ситуационных центрах принятия решений в атомной энергетике и при исследовании криминальных правонарушений.

Статья организована следующим образом: в главе 1 рассказывается о визуальной аналитике, смежных ей областях – научной визуализации и визуализации информации – и приводятся некоторые примеры применения. В главе 3 даются основные определения Анализа формальных понятий. Глава 4 описывает триадический АФП и трикластеризацию. В главе 5 описывается алгоритм OAC-трикластеризации, основанной на штрих-операторах, его реализация и результаты, а в главе 6 – рекомендательный алгоритм, основывающийся на трикластеризации. Затем в главе 7 показывается, как методы визуальной аналитики можно применить для анализа трикластеров, порожденных OAC-алгоритмом. В конце статьи делаются выводы о результатах проделанной работы.

1. Визуальная аналитика 1.1. Определение Поскольку эта область информатики довольно молодая, определений у понятия «визуальная аналитика» немало. Многие авторы, внесшие значительный вклад в формирование нового направления анализа данных, определяли его по-своему. Рассмотрим некоторые из этих определений.

Визуальная аналитика — это комбинация средств визуализации информации и других методов анализа данных [5].

Визуальная аналитика – это циклический процесс сбора информации, предварительной обработки данных, представления знаний, установления взаимосвязей данных и принятия решений [6].

Визуальная аналитика -– это наука о вынесении обоснованного аналитического решения с помощью визуальных интерактивных пользовательских интерфейсов [7], продукт слияния визуализации информации и научной визуализации [8].

Обобщая и вычленяя главное из каждого из них, дадим следующее определение.

Визуальная аналитика — это направление в анализе данных, фокусирующееся на вынесении аналитического решения с помощью визуальных интерактивных пользовательских интерфейсов в процессе сбора информации, предварительной обработки данных, представления знаний и установления их взаимосвязей.

1.2. Специфика задач визуальной аналитики

–  –  –

1) Задачи, решаемые средствами визуальной аналитики, обычно сложные, требуют обработки больших объемов данных и обоюдного человеческого и машинного анализа, что делает их порой не разрешимыми другими методами [5].

2) Конечная цель визуальной аналитики — глубоко вникнуть в какую-либо задачу, описываемую большими объемами данных различного рода и из различных источников.

Для этого визуальная аналитика использует как машинные, так и человеческие ресурсы. С одной стороны, методы обнаружения знаний в данных (data mining), статистика и информатика — движущая сила любого автоматического анализа данных. С другой

– способности мозга к восприятию информации, соотнесению данных и дальнейшим умозаключениям дополняют машинные ресурсы, что делает визуальную аналитику многообещающей техникой и перспективной сферой для дальнейших разработок.

3) По мере развития визуальная аналитика требует также совершенствования методов аналитического мышления, установления взаимосвязей в данных, их преобразования и представления для дальнейших вычислений и отображения, а также аналитической отчетности [9].

4) Визуальная аналитика также касается вопросов сознания, восприятия информации человеком, информатики, интерактивного и графического дизайна.

5) Визуальная аналитика сочетает методы визуализации информации с методами вычислительного анализа данных, при этом отображение усиливает познавательные способности человека шестью основными способами [10]:

увеличение объема источников данных — пользователю приходится держать меньше информации в голове;

–  –  –

поддерживание связей данных, например, когда они размещены в пространстве по принципу их временных отношений;

возможность пользователя вывести отношения или закономерности данных, которые иначе сделать было бы трудно;





–  –  –

1.3. Визуальная аналитика и смежные направления Как уже говорилось, визуальная аналитика – результат слияния таких направлений, как визуализация информации и научная визуализация с добавлением интерактивных интерфейсов. Хотя четкая граница между этими тремя дисциплинами и не определена, считается, что:

научная визуализация применяется для задач, в которых данные имеют естественную геометрическую структуру, например, моделирование самолетов (поездов, автомобилей) методом конечного элемента для исследования аэродинамических свойств, магнитно-резонансная томография (МРТ), исследования молекулярного строения веществ и т.д.;

–  –  –

2.1. Научная визуализация Одно из самых развитых проявлений научной визуализации – это вычислительная гидродинамика (Computational Fluid Dynamics, CFD). Классическая задача вычисления параметров потока воздуха при обтекании крыла самолета (таких как плотность, давление, число Рейнольдса и др.) требует построения сетки на обтекаемых поверхностях для дальнейшего применения численных методов конечного объема (или элемента, или конечных разностей) решения систем дифференциальных уравнений.

Рис. 1. Температура поверхности самолета и окружающего пространства при обтекании сверхзвуковым потоком – CFD моделирование Такие программные продукты, как Ansys и Catia, позволяют пользователю собственноручно построить сетку на поверхности 3D-модели исследуемого летательного аппарата или его части. Конечно, в этой «вечной» для прикладной аэродинамики задаче суперкомпьютеры используются не для получения наглядных изображений, а, собственно, для вычислений, но представление результатов полученных вычислений – не что иное, как научная визуализация.

Здесь же можно упомянуть один из первых реализованных проектов, посвященных научной визуализации в виртуальном окружении, – создание виртуальной аэродинамической трубы в исследовательском центре NASA Aims [11]. Целью данного проекта было визуализировать трёхмерные нестационарные потоки обтекания тел, моделирующие эксперименты в аэродинамической трубе.

ТРУДЫ МФТИ. — 2014. — Том 6, № 3 47 Ю. С. Кашницкий Рис. 2. Отображение результатов численного моделирования распределения давления при обтекании тонкого профиля

2.2. Научная визуализация В основе проекта We Feel Fine Джонатана Харриса и Сепа Камвара [12] лежит механизм сбора данных о чувствах и настроении пользователей Интернета. Каждые 10 минут множество постов в блогах, включая Live Journal, MSN Spaces, My Space, Blogger, Flickr и Google, проверяются на наличие фраз, содержащих «i feel» или «i’m feeling». Как только такое сочетание появляется, все предложение сохраняется в базе и далее идет проверка смысла, который несет пост: а именно, какое чувство он передает, находится ли оно в базе «предопределенных чувств» или для него нужно создать новое.

Полный список «чувств» насчитывает около 2 миллионов записей, а его начало выглядит так:

<

–  –  –

В этом списке «чувству» соответствует число его вхождений в записи в блогах и цвет, которым оно будет обозначаться на карте. Предсказуемо среди самых популярных выражений человеческих чувств встречаются слова «хорошо», «лучше», «плохо». Пятое место заняло чувство вины. Поскольку большинство исследуемых записей приходят из нескольких наиболее популярных блогов, URL-формат ссылок на них позволяет определить автора Математика и информатика 48 ТРУДЫ МФТИ. — 2014. — Том 6, № 3 Рис. 3. Карта WeFeelFine, отображающая данные по эмоциям людей за последние 10 минут поста, страницу его профиля, пол, возраст, страну проживания, погоду в его городе и так далее. Таким образом, данные можно сортировать по нескольким параметрам.

2.3. Визуальная аналитика Визуальная аналитика применяется компанией Siemens в их продукте PLM Software, который позволяет разработчикам мгновенно получать данные и визуализировать их прямо в контексте среды 3D-проектирования новых средств транспорта [13]. Продукт включает и визуальные отчеты – простой способ сбора, обмена и представления информации в графическом, интуитивно понятном виде, где данные представляются в среде 3D-проектирования изделий и их можно тут же применить для принятия решений.

И главное, система обеспечивает непосредственное визуальное взаимодействие. Это ускоряет процесс контроля проектных решений на соответствие заданным требованиям и позволяет выявлять и устранять проблемы качества продукции. Разработчики отслеживают соответствие изделия критически важным функциональным требованиям благодаря визуальной обратной связи, предоставляющей также большой объем информации.

3. Основные определения Анализа Формальных Понятий

–  –  –

трикластером (или объектно-признаково-условным трикластером, или здесь просто трикластером), основанном на штрих-операторах. Здесь (, ) = { | (,, ) }, (, ) = { | (,, ) }, (1) (, ) = { | (,, ) }.

–  –  –

Получается, Кирилл, Леня и Макс разделяют одни и те же интересы и добавили в закладки почти одни и те же сайты (разница лишь в том, что Леня не отметил сайт hockeycanada.ca). Главную идею кластеризации здесь иллюстрирует трикластер = ({1, 2, 3 }, {1, 2 }, {1, 2, 3, 4 }) с плотностью = 11/24 0.46.

= Это всего лишь один объект для анализа в отличие от 11 в случае трипонятий.

5. Алгоритм OAC-трикластеризации на штрих-операторах

–  –  –

Описанный выше алгоритм был реализован автором на языке Python версии 2.7.3 на 2-процессорной машине (Core i3-370M, 2.4 ГГц) с 3.87 Гб ОЗУ. Далее следует описание контекстов, на которых проверялся алгоритм, и некоторые результаты – таблицы 6.5, 6.6, 6.7.

–  –  –

Все трикластеры, содержащие данную пару user-tag, могут быть отображены с помощью вкладки «Triclusters» контекстного меню, связанного с клеткой, или просто нажатием на нее. Аналитик также может отобразить наибольший трикластер для данной клетки (рис. 7).

Кроме этого, аналитик с помощью вкладки «Recommend attributes» может отобразить результаты рекомендательного алгоритма для конкретного пользователя (в данном случае, рекомендуемые теги).

–  –  –

Рис. 6. Подсвечивание наибольшего трикластера для пары (6, 4) Рис. 7. Подсвечивание рекомендуемых тегов для нескольких пользователей Вывод

–  –  –

в контексте данных социальных сетей. Был предложен алгоритм для объединения таких объектов, признаков и условий в трикластеры. Описана вкратце программа, находящаяся на стадии разработки, предназначенная для графического отображения результатов этого алгоритма и наделения пользователя возможностью обнаруживать группы схожих объектов в контексте.

Благодарность Автор выражает благодарность своим научным руководителям в МФТИ и НИУ ВШЭ Клименко Станиславу Владимировичу и Кузнецову Сергею Олеговичу, а также коллеге Игнатову Дмитрию за своевременные советы и помощь в работе.

Литература

1. Ganter B., Wille R. Formal concept analysis: Mathematical foundations. Springer, Berlin. — 1999.

2. Lehmann F., Wille R. A triadic approach to formal concept analysis. — London. SpringerVerlag, 1995.

3. Ignatov D. I., Kuznetsov S. O., Poelmans J., Zhukov L. E. Can triconcepts become triclusters? // International Journal of General Systems. — 2013. — V. 42. — P. 572–593.

4. Venjega A. B., Gnatyshak D. V., Ignatov D. I., Konstantinov A. V. Recommender system for perfumes and their tags based on triclustering // Proceedings of the «Intellectual data processing» conference. — 2012 — P. 601–605. — (in Russian).

5. Kosara R. Parallel sets: Interactive exploration and visual analysis of categorical data // IEEE Transactions on Visualization and Computer Graphics. — 2006. — V. 12, N. 4. — P. 558–568.

6. Keim D., Andrienko G. Visual analytics: Definition, process, and challenges // Information Visualization. — 1999. — V. 4950. — P. 154–175.

7. Thomas J., Cook K. Illuminating the Path: Research and Development Agenda for Visual Analytics. — New York. IEEE-Press, 2005.

8. Wong P. C., Thomas J. Visual Analytics // IEEE Computer Graphics and Applications. — 2004. — V. 24, N. 5. — P. 20-21.

9. Kielman J., Thomas J. Special Issue: Foundations and Frontiers of Visual Analytics.

Information Visualization. — 2009. — V. 8, N. 4. — P. 239–314.

10. Card S., Mackinlay J. D., Shneiderman B. Readings in Information Visualization: Using Vision to Think. Morgan Kaufmann Publishers, San-Francisco. — 1999.

11. Описание проекта по созданию виртуальной аэродинамической трубы http://veonpc.com/index.php/3d-vizualization/science-vizualization

12. Сайт проекта WeFeelFine http://www.wefeelfine.org

13. Визуальная аналитика компании Siemens http://www.plm.automation.siemens.com

14. Kuznetsov S. O. On stability of a formal concept // Annals of Mathematics and Artificial Intelligence. — 2007. — V. 49. — P. 101–115.

15. Gnatyshak D. V., Ignatov D. I., Semenov A., Poelmans J. Analysing online social network data with biclustering and triclustering // Proceedings of the «Concept Discovery in Unstructured Data» conference. — 2012. — V. 871. — P. 30–39.

Похожие работы:

«Номер договора 2106 от " 01 " июля 2011 г. ДОГОВОР НА ОБСЛУЖИВАНИЕ ОБОРУДОВАНИЯ ЗАКАЗЧИК: ТСЖ "АТЛАНТ-51" АДРЕС: 350089 Г. КРАСНОДАР УЛ. РОЖДЕСТВЕНСКАЯ НАБЕРЕЖНАЯ 51 РАСЧЕТНЫЙ СЧЕТ: 40703810757110007626 В ЛЕНИНСКОМ ФИЛИАЛЕ ОАО АКБ "УРАЛСИБ-ЮГ БАНК" Г. КРАСНОДАР 344002,...»

«АДОТЕЛ – ГЕКС ТОО с местом нахождения: П. О. Хвиездоцлава 68, 010 01 Жилина регистрационный №: 30 229 162 внесенный в Торговый реестр Районного суда г. Жилина, отдел: ТОО вставка №. 236/Л Уважаемые торговые партнеры и друзья, Вам попадают в руки информации о компании АДОТЕЛ –ГЕКС ТОО, которых основной целью является короткая оценка и пре...»

«МИНИСТЕРСТВО СТРОИТЕЛЬСТВА И ЖИЛИЩНОКОММУНАЛЬНОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ ПИСЬМО от 24 апреля 2015 г. N 12258-АЧ/04 ОБ ОТДЕЛЬНЫХ ВОПРОСАХ, ВОЗНИКАЮЩИХ В СВЯЗИ С ВВЕДЕНИЕМ ЛИЦЕНЗИРОВАНИЯ ПРЕДПРИНИМАТЕЛЬСКОЙ ДЕЯТЕЛЬНОСТИ ПО...»

«SCIENCE TIME ЦЕННОСТНЫЕ ХАРАКТЕРИСТИКИ ЛИНГВОКУЛЬТУРНОГО ТИПАЖА "НАЦИОНАЛЬНЫЙ ГЕРОЙ" В ОТЕЧЕСТВЕННОМ И ЗАРУБЕЖНОМ АВТОРСКОМ КИНО Мельников Пётр Николаевич, Комсомольский-на-Амуре государственный технический универ...»

«Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Сибирская государственная автомобильно-дорожная академия (СибАДИ)" Кафедра экономики и проектного управления в транспортном строительстве ЭКОНОМИКА И...»

«Коваленко П.А. Пагубное влияние "прямой" индикации в авиагоризонтах на катастрофу самолета Boeing-737, 14.09.08 г. под Пермью и другие авиапроисшествия. Психологическое "дорасследование" Москва – 2011 УДК 159.9:629.7 ББК 68.53 К-56 Рецензент: доктор технических наук, профессор, летчик-испытатель 1 класса В.Е.Овчаров <...»

«Институт Государственного управления, Главный редактор д.э.н., профессор К.А. Кирсанов тел. для справок: +7 (925) 853-04-57 (с 1100 – до 1800) права и инновационных технологий (ИГУПИТ) Опубликовать статью в журнале http://publ.naukovedenie.ru Интернет-журнал "...»

«АНАЛИЗ УРОВНЕЙ ОБЩЕНИЯ Байбаторов И. В. Институт Авиационных Технологий и Управления Ульяновского Государственного Технического Университета Ульяновск, Россия ANALYSIS OF THE COMM...»

«Хмельник С. И.Гравитомагнетизм: природные явления, эксперименты, математические модели Первая редакция 05.01.2017 Вторая редакция, дополненная 20.02.2017 Израиль 2016 Solomon I. Khmelnik Gravitomagnetism: Nature's Phenomenas, E...»








 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.