«Доклады по компьютерным наукам 01 и информационным технологиям Издается с 2012 года. Редакционный совет Александр Авдеев, Intel, Россия, Москва Сергей Белов, IBM, Россия, Москва Александр Гаврилов, ...»

Доклады по компьютерным наук

ам 01

и информационным технологиям

Издается с 2012 года. www.LectureNotes.ru

Редакционный совет

Александр Авдеев,

Intel, Россия, Москва

Сергей Белов,

IBM, Россия, Москва

Александр Гаврилов,

Microsoft, Россия, Москва

Виктор Гергель

НИУ Нижегородский Государственный Университет им. Н.И.

Лобачевского, Россия Нижний Новгород

Александр Гиглавый

Лицей информационных технологий, Россия, Москва Дмитрий Игнатов НИУ Высшая Школа Экономики, Россия, Москва Михаил Лаврентьев Новосибирский Государственный Университет, Россия, Новосибирск Александр Олейник Высшая школа бизнес-информатики, НИУ Высшая Школа Экономики, Россия, Москва Александр Петренко Институт системного программирования РАН, Россия, Москва Андрей Терехов Санкт-Петербургский государственный университет, Россия, Санкт-Петербург Олег Спиридонов Московский государственный технический университет им.

Н. Э. Баумана, Россия, Москва Павел Христов Издательство «Открытые системы», Россия, Москва Анатолий Шкред Национальный Открытый Университет, Россия, Москва Ростислав Яворский Witology, Россия, Москва Дмитрий Игнатов Ростислав Яворский (редакторы) Доклады всероссийской научной конференции «Анализ Изображений Сетей и Текстов» (АИСТ'12) Модели, алгоритмы и инструменты анализа данных;

результаты и возможности для анализа изображений, сетей и текстов Екатеринбург, 16 – 18 марта 2012 года УДК [004.738.5+004.9](063) ББК 32.973.202я431(2Рос)+32.973.26-018я431(2Рос) Д Учредитель: Национальный Открытый Университет «ИНТУИТ»

Редакторы тома Дмитрий Игнатов Ростислав Яворский Д63 Доклады по компьютерным наукам и информационным технологиям. № 1, 2012 г. Доклады всероссийской научнопрактической конференции «Анализ Изображений, Сетей и Текстов» (АИСТ 2012). Екатеринбург, 16 – 18 марта 2012 года.

М.: Национальный Открытый Университет «ИНТУИТ» 2012. – 419 с.

ISBN 978-5-9556-0132- Доклады Всероссийской научно-практической конференции «Анализ Изображений, Сетей и Текстов» (АИСТ, Екатеринбург, 2012).

Рассматриваются проблемы в области компьютерного зрения, анализа изображений и видео, анализа форумов, блогов и социальных сетей, анализ сетевых (графовых) и потоковых данных, компьютерной обработки текстов, гео-информационных систем, математических моделей и методов анализа данных, машинного обучения и разработки данных (Data Mining), рекомендательных систем и алгоритмов, Semantic Web, онтологии и их приложений.

Для студентов, аспирантов и специалистов в области компьютерной графики, машинного зрения и обработки изображений.

© Национальный Открытый Университет «ИНТУИТ», Предисловие В сборнике представлены работы участников Всероссийской научно-практической конференции «Анализ Изображений, Сетей и Текстов» (АИСТ 2012). Это мероприятие стало площадкой, которая позволила студентам, аспирантам, специалистам и ученым математических, технических, лингвистических, географических, социологических и иных специальностей представить результаты своих работ и расширить познания в области анализа данных, обменяться опытом.

Конференция проводилась с 16 по 18 марта 2012 года в столице Урала – Екатеринбурге. Все статьи можно условно разбить на несколько групп по темам:

Компьютерное зрение, анализ изображений и видео Анализ форумов, блогов и социальных сетей Анализ сетевых (графовых) и потоковых данных Компьютерная обработка текста Гео-информационные системы Математические модели и методы анализа данных Машинное обучение и разработка данных (Data Mining) Рекомендательные системы и алгоритмы Semantic Web, онтологии и их приложения Всего было получено 45 заявок, каждая из которых была оценена минимум двумя рецензентами. По итогам рецензирования 23 работы были отобраны для секционных докладов и 17 для постерных сессий. В программу конференции включены три мини-курса и две лекции, прочитанные приглашёнными докладчиками, а также презентации компаний организаторов и спонсоров конференции.

Пользуясь этой возможностью, мы выражаем благодарность всем организаторам, членам программного комитета, рецензентам, докладчикам, спонсорам и партнёрам конференции, благодаря которым эта конференция состоялась. Мы благодарны Национальному Открытому Университету «ИНТУИТ» за помощь в издании тома трудов конференции.

Программный комитет конференции Координаторы Дмитрий Игнатов, НИУ ВШЭ, Россия Ростислав Яворский, Witology, Россия Члены Ольга Баринова, МГУ, Россия Виктор Бочаров, СПбГУ, Россия Павел Браславский, СКБ Контур, Россия Александр Вохминцев, ИИТ ЧелГУ, Россия Борис Галицкий, Университет Жироны, Испания Дарья Гончарова, Witology, Россия Дмитрий Грановский, Яндекс, Россия Леонид Дворянский, НИУ ВШЭ, Россия Максим Дубинин, NextGIS, Россия Виктор Ерухимов, ЦКЗ Аргус, Россия Леонид Жуков, НИУ ВШЭ, Россия Вадим Канторов, cole Normale Suprieure de Cachan, Франция Юрий Катков, СПб НИУ ИТМО, Россия Никита Козин, Университет Райса, США Андрей Константинов, НИУ ВШЭ, Россия Дмитрий Корнев, УрФУ, Россия Сергей Кузнецов, НИУ ВШЭ, Россия Алексей Лахно, НИУ ВШЭ, Россия Виктор Лемпицкий, Яндекс, Россия Алексей Незнанов, НИУ ВШЭ, Россия Сергей Объедков, НИУ ВШЭ, Россия Йонас Пульманс, Католический Университет Левена, Бельгия Сергей Рогожкин, Microsoft, Россия Александра Савельева, НИУ ВШЭ, Россия Александр Семенов, НИУ ВШЭ, Россия Павел Сердюков, Яндекс, Россия Никита Спирин, Университет Иллинойса, США Алексей Станкевичус, НИЯУ МИФИ, Россия Рустам Тагиев, Технический университет Фрайберга, Германия Олег Ушмаев, Институт проблем информатики РАН, Россия Михаил Хачай, ИММ УрО РАН и УрФУ, Россия Приглашенные рецензенты Лидия Пивоварова, СПбГУ, Россия Константин Блинкин, НИУ ВШЭ, Россия Наталия Жукова, СПбГТУ «ЛЭТИ», Россия Александра Каминская, НИУ ВШЭ и Witology, Россия Елена Павлова, Microsoft Research, Россия Никита Ромашкин, НИУ ВШЭ, Россия Федор Строк, НИУ ВШЭ, Россия Екатерина Черняк, НИУ ВШЭ, Россия Ольга Чугунова, НИУ ВШЭ, Россия Организационный комитет конференции Секретарь Александра Каминская, НИУ ВШЭ и Witology, Россия Члены Дарья Гончарова, Witology, Россия Ирина Войчитская, Яндекс, Россия Мария Рудниченко, СКБ Контур, Россия Никита Спирин, Университет штата Иллинойс, США VIII Спонсоры и партнеры конференции Национальный исследовательский университет Высшая школа экономики Национальный Открытый Университет «ИНТУИТ»

Witology Яндекс СКБ Контур Уральский федеральный университет имени первого Президента России Б.Н. Ельцина Исследовательский центр моделирования, анализа и тестирования «Моданте»

3DiVi Company (ООО «ТРИДИВИ») Издательство «Открытые системы»

Приглашенные доклады Компьютерное зрение

Ольга Баринова Геоинформационные системы

Максим Дубинин Анализ формальных понятий: от теории к практике.............. Дмитрий Игнатов Система анализа данных коллаборативных платформ CrowDM

Дмитрий Игнатов, Александра Каминская, Анастасия Беззубцева, Константин Блинкин Прагматическое введение в Semantic Web и Linked Data....... Ю.В. Катков Сходимость эмпирических случайных процессов и обобщающая способность алгоритмов обучения

Михаил Хачай Секционные доклады Влияние метрики на эффективность сжатия видеоизображения

Евгений Альтман, Елена Захаренко Идентификация пользователей социальных сетей в Интернет на основе социальных связей

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

Екатерина Черняк, Ольга Чугунова, Юлия Аскарова, Сусанна Насименто, Борис Миркин Влияние разрешения изображений на качество детектирования лиц

Николай Дегтярёв, Олеся Кушнир, Олег Середин Визуализация данных социосемантической сети

Алексей Друца, Константин Яворский Лиана Ермакова Применение марковской модели для анализа влиятельности участников интернет-сообществ

Денис Федянин Методика совместной обработки разносезонных изображений Landsat-TM и создания на их основе карты наземных экосистем Московской области

Егор Гаврилюк, Дмитрий Ершов Выделение гармонической информации из музыкальных аудиозаписей

Николай Глазырин, Александр Клепинин Кластеризация текстовых данных с помощью модифицированного генетического алгоритма

Дарья Глушкова Рекомендательные системы: тематический обзор

Андрей Константинов Автоматизация подготовки исходных текстовых данных из сети интернет для дальнейшего анализа

Никита Найденов Извлечение семантических отношений из статей Александр Панченко, Сергей Адейкин, Алексей Романов, Павел Романов Алгоритм ГИС-анализа данных для оценки вероятности Александра Подольская, Дмитрий Ершов, Павел Шуляк Автоматическое снятие морфологической неоднозначности при разметке корпуса текстов

Екатерина Протопопова Распознавание образов при помощи динамических NKсетей, состоящих из бинарных динамических элементов...... Дарья Пучкова Метод спектральной трикластеризации для систем совместного пользования ресурсами

Зарина Секинаева, Дмитрий Игнатов Автоматизированная система распознания рукописных исторических документов

Артем Скабин, Иван Штеркель Консенсус в социальных сетях: динамический подход.......... Федор Строк Особенности создания поискового индекса к фотографиям в цифровом историческом альбоме

Андрей Талбонен Применение онтологии при синтезе изображения по тексту. Дмитрий Усталов, Александр Кудрявцев Определение компетенций участников конкурса

Александр Воробьев Постерные доклады Формирование критериев эффективного трудоустройства выпускников ВУЗа на основе методов Data Mining................ Юлия Ахмайзянова Автоматизированный анализ мнений о товарах

Сергей Ермаков Географическая информационная система «Поездка на один бензобак»

Нияз Габдрахманов, Екатерина Михеева, Михаил Рожко Прототипы системы стереонаблюдения

XII Владимир Горшенин Оценивание параметров билинейных динамических систем с помехой в выходном сигнале

Дмитрий Иванов, Олег Усков Geospatial Semantic Web – расширение семантической паутины для описания и обработки пространственных данных

Степан Кузьмин Сравнение методов извлечения ключевых слов из текстов на естественных языках

Даниил Недумов Об одной задаче семантической классификации цифровых изображений

Максим Паначёв, Борис Парфененков Модель системы коллаборативного рейтингования событий Екатерина Щербакова Методики улучшения качества данных в онлайн исследованиях с помощью нематериальных стимулов мотивации участников access-панелей.

Елена Соловьёва, Иван Куприянов, Юлия Ермоленко Горная ГИС на основе OpenCASCADE

Антон Уймин, Владимир Суханов Бинокулярное зрение в режиме реального времени................ Михаил Хрущев Анализ ассоциативных тезаурусов и возможность их применения в задачах машинного перевода

Екатерина Выломова Распознавание дорожных знаков на основе машины опорных векторов и показателя сопряжённости

Роман Захаров, Владимир Фурсов 119992 ГСП-2, Москва, Воробьевы горы, МГУ им. М.В.Ломоносова Аннотация. Современные системы компьютерного зрения позволяют распознавать жесты, восстанавливать трехмерную структуру сцены по двумерному изображению, выделять объекты переднего плана от фона, надежно обнаруживать объекты определенного класса. Эти достижения во многом обязаны появлению графических моделей, которые позволяют с одной стороны объединять информацию из различных частей и элементов изображения в единую модель, а с другой стороны использовать глобальные ограничения реального мира. В мини-курсе мы коснёмся следующих вопросов: Что такое компьютерное зрение, какие задачи оно позволяет решать? Что такое графические модели? Какие графические модели используются в современных системах компьютерного зрения? Для иллюстрации мы рассмотрим последние совместные проекты МГУ и Microsoft Research по компьютерному зрению.

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

Игнатов Д.И., Яворский Р.Э. (ред.): Анализ Изображений, Сетей и Текстов, Екатеринбург, 16-18 марта, 2012.

© Национальный Открытый Университет «ИНТУИТ», Аннотация. В докладе будут рассмотрены следующие вопросы, касающиеся геоинформационных систем. 1) Геоданные: особенности, основные источники, ПО для работы с ними. 2) Непараметрические классификаторы для анализа данных дистанционного зондирования. 3) Методы максимальной энтропии для пространственного нишевого анализа.

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

Игнатов Д.И., Яворский Р.Э. (ред.): Анализ Изображений, Сетей и Текстов, Екатеринбург, 16-18 марта, 2012.

© Национальный Открытый Университет «ИНТУИТ», НИУ ВШЭ, Россия, 101000, г. Москва, ул. Мясницкая, д. Аннотация. В работе даются основные определения анализа формальных понятий (АФП), рассказывается о его роли в математике и компьютерных науках, а также приводится краткий обзор его основных приложений.

Ключевые слова: анализ формальных понятий, разработка данных (Data Mining), приложения.

Введение Анализ формальных понятий (АФП) является прикладной ветвью алгебраической теории решеток, в рамках которой предложен математический формализм, описывающий на языке алгебры понятие и иерархии понятий. Основные идеи АФП был сформулированы Рудольфом Вилле в его работе [50], а наиболее полной монографией по АФП является книга Гантера и Вилле [23].

Фактически анализ формальных понятий имеет дело с данными в объектно-признаковой форме, а формальные понятия, определенные с помощью соответствия Галуа, представляют собой пары множеств вида (объем, содержание), им в точности до перестановки строк и столбцов соответствуют максимальные прямоугольники в таблице объектпризнак. Основными достоинствами такого определения понятия являются соответствие традиционным представлениям о понятиях испольИгнатов Д.И., Яворский Р.Э. (ред.): Анализ Изображений, Сетей и Текстов, Екатеринбург, 16-18 марта, 2012.

© Национальный Открытый Университет «ИНТУИТ», зуемым в философии: 1) понятие — это пара вида (объем, содержание), 2) при уменьшении объема понятия увеличивается его содержание и наоборот, 3) понятия иерархически упорядочены по отношению «быть более общим понятием».

За последние 30 лет АФП прошел значительный путь от первоначальных теоретических изысканий к разнообразным многочисленным приложениям (только на английском языке издано около 900 научных работ по тематике АФП, более половины из которых посвящены приложениям), что позволяет полноправно назвать его прикладной математической дисциплиной. Основными приложениями АФП, которым мы уделим внимание в этой работе, являются анализ данных (машинное обучение и разработка данных), представление знаний (онтологии и таксономии), информационный поиск, анализ неструктурированных данных (в частности, текстов), программная инженерия, социология и образование. В настоящее время существуют три наиболее репрезентативных международных конференции по тематике АФП: International Conference on Formal Concept Analysis, International Conference on Concept Lattices and Their Applications и International Conference on Conceptual Structures. Первая в списке конференция является наиболее представительной и служит для обсуждения значительных теоретических и практических результатов в области, вторая посвящена преимущественно приложениям АФП, а третья, помимо АФП-сообщества, призвана собрать исследователей в области представления знаний и онтологического моделирования (например, сооснователем этой серии конференций является создатель понятийных графов Джон Сова).

Основные определения анализа формальных понятий Контекстом в АФП называют тройку K = (G, M, I), где G — множество объектов, M — множество признаков, а отношение I G M говорит о том, какие объекты какими признаками обладают. Для произвольных A G и B M определены операторы Галуа:

Оператор '' (двукратное применение оператора ') является оператором замыкания: он идемпотентен (A'''' = A''), монотонен (A B влечет A'' B'') и экстенсивен (A A''). Множество объектов A G, такое, что A'' = A, называется замкнутым. Аналогично для замкнутых множеств признаков — подмножеств множества M. Пара множеств (A, B), таких, что A G, B M, A' = B и B' = A, называется формальным понятием контекста K. Множества A и B замкнуты и называются объемом и соАнализ формальных понятий: от теории к практике держанием формального понятия (A, B) соответственно. Для множества объектов A множество их общих признаков A' служит описанием сходства объектов из множества A, а замкнутое множество A'' является кластером сходных объектов (с множеством общих признаков A'). Отношение «быть более общим понятием» задается следующим образом:

(A, B) (C, D) тогда и только тогда, когда AC. Понятия формального контекста K = (G, M, I), упорядоченные по вложению объемов образуют решетку B (G, M, I), называемую решеткой понятий. Для визуализации решеток понятий используют т.н. диаграммы Хассе, т.е. граф покрытия отношения «быть более общим понятием».

АФП в машинном обучении и разработке данных В этом разделе мы кратко опишем основные приложения и методы на основе АФП в области современного анализа данных, в частности в разработке данных (Data Mining).

Рис. 1. Диаграмма решетки понятий для 702 статей по АФП, Классификация Соответствия Галуа также использовались некоторыми исследователи в СССР, например, ДСМ-метод автоматического порождения гипотез, применяемый для решения задач классификации довольно естественно формулируется в терминах решеток понятий как метод машинного обучения по положительным и отрицательным примерам [11]. Переход в данном случае с языка математической логики к алгебраическим формулировкам позволил разработать эффективные программные реализации ДСМ-метода. На языке формальных понятий и соответствий Галуа переформулированы такие методы машинного обучения как пространства версий и деревья решений (см. [22]). Более поздняя работа [14] по применению решеток понятий для порождения деревьев решений на основе решеток формальных понятий показала улучшение результатов по сравнению с известными методами, такими как C4.5 и IB1.

Отбор признаков Отбор признаков (feature selection), сокращение или редуцирование признаков на этапе предварительного анализа данных существенно помогают сократить не только вычислительные затраты, но и улучшить точность классификации. Сплав идей анализа формальных понятий и неточных множеств (Rough Sets) убедительно демонстрирует такое сокращение [25].

Частые (замкнутые) множества признаков Поиск частых множеств признаков возник как направление в разработке данных в начале 90-х годов для решения задач анализа корзины покупок в крупных продуктовых супермаркетах. Анализ формальных понятий и поиск (замкнутых) множеств признаков (Frequent Itemset Mining) объединяет идея замыкания. Фактически решетка понятий некоторого формального контекста в АФП изоморфна решетке замкнутых множеств, если требование быть частым множеством не учитывать. В АФП было введено понятие решетки-айсберга [47], которое позволило максимально сблизить терминологию двух сообществ FIM и FCA.

Поиск закономерностей: импликации, ассоциативные правила и функциональные зависимости Импликацией формального контекста K = (G, M, I) в анализе формальных понятий называется признаковая зависимость вида AB, где A, B M, при условии, что все объекты, обладающие A, также обладаАнализ формальных понятий: от теории к практике ют всеми признаками из B, т.е. A' B'. Импликация в АФП является частным случаем такой признаковой зависимости как ассоциативное правило в разработке данных, это в точности ассоциативное правило с достоверностью (confidence) равной 1. В свою очередь, ассоциативные правила изучались в АФП задолго до их появления в сообществе разработки данных под названием частичные импликации [37]. Связь импликаций и функциональных зависимостей позволила использовать т. н.

базис импликаций Дюкена-Гига для компактного представления функциональных зависимостей (см. теорию баз данных) виде их ограниченного множества, из которого все оставшиеся функциональные зависимости данного многозначного контекста (таблицы данных) выводимы по правилам Армстронга [23]. Достаточно полный обзор по поиску ассоциативных правил на основе АФП можно найти в работе [36].

Модели мультимодальной кластеризации Недостатки традиционных методов кластеризации, связанные с потерей признакового описания сходства объектов, при установлении факта их числового сходства требуют новых методов кластерного анализа во многих приложениях, таких как анализ данных генной экспрессии и Интернет-данных. Формальные понятия могут быть рассмотрены как своего рода бикластеры, в которых описание сходства объектов сохраняется в признаковой компоненте бикластера — содержании [6, 8].

Стоит отменить многочисленные попытки ослабления определения формального понятия и его обобщения на многомерный случай. Одними из успешных таких попыток являются разработка метода поиска мультимодальных кластеров DataPeeler [38] и плотных би- [6, 8] и трикластеров [4, 5, 30].

Рекомендательные системы Рекомендательные системы также потенциальные кандидаты для применения АФП, первые шаги в этом направлении были сделаны в работах [1, 7, 28].

Приложения в анализе текстов Анализ формальных понятий помогает также в анализе неструктурированных данных. Например, для выявления (почти) дубликатов по большим коллекциям веб-документов [9, 10, 29] и анализа текстов полицейских отчетов [41]. Основное преимущество перед методами кластеризации на основе попарного сравнения документов в хорошей эмпирической временной сложности при кластеризации текстовых коллекций благодаря разреженности данных. Во втором приложении важным для экспертов являются таксономические возможности решеток понятий, позволяющих удобно изучать коллекции полицейских отчетов по диаграмме решетки понятий, построенной по таблице отчеты – ключевые слова [41].

Приложения в программной инженерии Пожалуй, впервые систематическое обсуждение приложений АФП в программной инженерии было дано в книге [25]. В основном АФП применяется для поддержки разработки ПО и объектноориентированного моделирования иерархий классов на ранних стадиях проекта, а также для улучшения и рефакторинга кода на более поздних этапах (см. статьи [26, 27, 46, 49]). Позднее появился обзор 47 статей по программной инженерии на основе АФП [48]. Авторы разбили эти статьи по 10 категориям на основании стандарта программной инженерии ISO 12207 и визуализировали результаты анализа с помощью диаграммы решетки понятий.

АФП в онтологическом моделировании и представлении знаний Таксономические свойства решеток понятий, представление множества понятий в виде иерархии с отношением «быть более общим понятием» ставят естественный вопрос насколько тесно АФП связан с онтологиями. Ответ на него был дан достаточно давно в работах Ф. Симиано и А. Хотхо (исследователь из университета Касселя, Германия) [17].

Было установлено как можно получить частичный порядок менее строгий, чем решеточный, из решеток понятий, и, наоборот, как по имеющейся онтологии, представленной в виде частичного порядка на понятиях, построить решетку понятий. АФП тесно связан с описательными логиками (Descriptive Logic), например, так называемое исследование признаков (Attribute Exploration), как метод пополнения баз знаний был позаимствован сообществом DL из АФП [13].

Важной темой в работах по АФП является вопрос построения онтологий эффективным образом. Этой теме посвящено около 30% всех статей по АФП (всего 93 статьи за период с 2003 по 2009 год). Авторы используют АФП преимущественно как средство извлечения онтологических понятий и их иерархий. Большинство из них имеют дело с неструктурированными текстами, такими как медицинские отчеты, RSS потоки, научные статьи и т.п. Анализируя неструктурированные тексты авторы как правило используют средства обработки естественного языка (NLP). С помощью NLP они извлекают из текстовых коллекций клюАнализ формальных понятий: от теории к практике чевые слова, фразы, лексико-синтаксический контекст и т.п. По таким данных можно построить решетки понятий и извлекать онтологические классы ключевых слов, иерархически упорядочивать эти понятия, выявлять зависимости между классами и т.п. В итоге новое онтологическое знание может быть сохранено, например, в формате OWL, а новые тексты могут быть классифицированы с использованием уже этой онтологии. Именно с появлением работ Симиано, Хотхо и др. (см. [17] и [18]) АФП стал популярным инструментом для построения онтологий.

Работа [17] обсуждает как АФП может быть использован для поддержки построения онтологий и как онтологии могут быть использованы в приложениях АФП. Ричардс [43] предлагает использовать АФП для построения небольших персональных и ad hoc, которые могут помочь пониманию области исследований.

Таксономические свойства АФП оказались удобными для представления знаний, например, при анализе посещаемости сайтов в сети Интернет для построения таксономий аудиторий веб-сайтов [33].

Информационный поиск Среди приложений АФП по информационному поиску можно отметить мета-поисковые системы для Интернета [16, 19, 32]. Для более детального знакомства с предметом рекомендуется обратиться к книге Карпинето и Романо [15] или еще вполне актуальному обзору Уты Присс [42].

Социологические приложения и анализ образовательных данных Ключевыми фигурами по приложениям АФП в социологии являются Линтон Фриман и Винсент Дюкен. Линтоном Фриманом изучались возможности решеток понятий для определения сообществ в анализе социальных групп и сетей [21], а Винсентом Дюкеном сделано немало для социологических и антропологических исследований на основе опросных данных [20, 39 и 40]. Исследованием эпистемических сообществ интенсивно занимались Сергей Объедков и Камий Рот [45]. Анализу результатов социологических опросов и данных в области образования посвящены работы автора этой статьи [2, 3, 31 и 44]. Работа [4] посвящена изучению три-сообществ в социальных Интернет-сервисах.

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

Благодарности Работа выполнена в рамках проектно-учебной группы НИУ ВШЭ «Алгоритмы интеллектуального анализа данных (Data Mining) для Интернет-форумов обсуждения инновационных проектов».

Список источников 1. Игнатов Д.И., Кузнецов С.О. Методы разработки данных (Data Mining) для рекомендательной системы Интернет-рекламы // Одиннадцатая национальная конференция по искусственному интеллекту с международным участием (КИИ-2008, 28 сентября – 3 октября 2008 г., г.

Дубна, Россия): Труды конференции. Т.2. – М.: Ленанд, 2008. – 392 с.

2. Игнатов Д.И., Кононыхина О.Н. Решетки формальных понятий для анализа данных социологических опросов// Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сборник научных трудов V-й Международной научно-технической конференции (Коломна, 20-30 мая 2009 г.). В 2-х томах. Т1. – М.: Физматлит, 2009. – 546 с.

3. Игнатов Д.И., Хавенсон Т.Е. Изучение ресурсной обеспеченности российских школ с помощью методов, основанных на решетках понятий// Социологические методы в современной исследовательской практике: Сборник статей, посвященный памяти первого декана факультета социологии НИУ ВШЭ А.О. Крыштановского / Отв. ред. и вступит. ст.

О.А. Оберемко; НИУ ВШЭ, ИС РАН, РОС. М.: НИУ ВШЭ, 2011.

4. Игнатов Д.И., Магизов Р.А. Анализ тримодальных данных на примере Интернет-сервисов социальных закладок// Социологические методы в современной исследовательской практике: Сборник статей, посвященный памяти первого декана факультета социологии НИУ ВШЭ А.О.

Крыштановского / Отв. ред. и вступит. ст. О.А. Оберемко; НИУ ВШЭ, ИС РАН, РОС. М.: НИУ ВШЭ, 2011.

5. Игнатов Д. И., Кузнецов С. O., Пульманс Й. Разработка данных систем совместного пользования ресурсами: от трипонятий к трикластерам //Математические методы распознавания образов: 15-я Всероссийская конференция. г. Петрозаводск, 11–17 сентября 2011 г.: Сборник докладов. — М.: МАКС Пресс, 2011. — 618 с. (ISBN 978-5-317-03787-1) 6. Игнатов Д.И., Кузнецов С.О. Бикластеризация объектнопризнаковых данных на основе решеток замкнутых множеств// Труды 12-й национальной конференции по искусственному интеллекту, М., Физматлит, Т. 1., С.175-182, 2010.

7. Игнатов Д.И., Каминская С.Ю., Магизов Р.А. Метод скользящего контроля для оценки качества рекомендательных Интернет-сервисов// Труды 12-й национальной конференции по искусственному интеллекту, М., Физматлит, Т. 1., С.183-191, 2010.

8. Игнатов Д.И., Каминская А.Ю, Кузнецов С.О., Магизов Р. А. Метод бикластеризации на основе объектных и признаковых замыканий// Интеллектуализация обработки информации: 8-я международная конференция. Республика Кипр, г. Пафос, 17-24 октября 2010 г.: Сборник докладов. – М.: МАКС Пресс, 2010. – С. 140 – 143.

9. Игнатов Д.И., Кузнецов С.О. О поиске сходства Интернетдокументов с помощью частых замкнутых множеств признаков // Труды 10-й национальной конференции по искусственному интеллекту с международным участием (КИИ’06). – М.:Физматлит, 2006, Т.2, стр.249- 10. Кузнецов С.О., Игнатов Д.И., Объедков С.А., Самохин М.В. Порождение кластеров документов дубликатов: подход, основанный на поиске частых замкнутых множеств признаков. Интернетматематика 2005. Автоматическая обработка веб-данных. Москва:

«Яndex», 2005, стр. 302 – 11. С.О. Кузнецов, ДСМ-метод как система автоматического обучения, Итоги науки и техники. Сер. Информатика. 1991, Т. 15, С.17-54.

12. С.О. Кузнецов, Формальный анализ понятий с помощью ДСМметода, 6-я Национальная Конференция по Искусственному Интеллекту (КИИ-98), т.2, Пущино, АИИ, 1998,С. 591-592.

13. F. Baader and B. Sertkaya. Applying formal concept analysis to description logics. In P. Eklund, editor, Proceedings of the 2nd International Conference on Formal Concept Analysis (ICFCA 2004), volume 2961 of Lecture Notes in Computer Science, pages 261-286. Springer-Verlag, 2004.

14. Belohlavek, Radim and De Baets, Bernard and Outrata, Jan and Vychodil, Vilem. Inducing decision trees via concept lattices. J. International Journal of General Systems, 2009, Volume 38, 4, Pages 455–467(2011) 15. Carpineto, C., Romano, G. (2004a) Concept data analysis: Theory and applications. John Wiley & Sons.

16. Carpineto, C., Romano, G. (2004b) Exploiting the Potential of Concept Lattices for Information Retrieval with CREDO. J. of Universal Computing, 10, 8, 985-1013.

17. Philipp Cimiano, Andreas Hotho, Gerd Stumme, and Julien Tane. Conceptual Knowledge Processing with Formal Concept Analysis and Ontologies. Proceedings of the The Second International Conference on Formal Concept Analysis ICFCA 04, (2961) Springer, 2004.

18. Cimiano, P.; Hotho, A. & Staab, S. Learning Concept Hierarchies from Text Corpora using Formal Concept Analysis. Journal of Artificial Intelligence Research, 2005, 24, 305- 19. Dau, F., Ducrou, J., Eklund, P. (2008) Concept Similarity and Related Categories in SearchSleuth. P. Eklund et al. (Eds.): ICCS. LNAI 5113, 255Springer.

20. Vincent Duquenne: Latticial Structures in Data Analysis. Theor.

Comput. Sci. 217(2): 407-436 (1999) 21. L. Freeman Cliques, Galois Lattices, and the Structure of Human Social Groups. Social Networks, 18, 1996, 173- 22. B. Ganter and S.O. Kuznetsov, Hypotheses and Version Spaces, Proc.

10th Int. Conf. on Conceptual Structures, ICCS'03, A. de Moor, W. Lex, and B.Ganter, Eds., Lecture Notes in Artificial Intelligence, vol. 2746 (2003), pp.

83-95.

23. B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer, 1999.

24. Bernhard Ganter, Sergei O. Kuznetsov, Scale Coarsening as Feature Selection, In: R.Medina, S.Obiedkov, Eds., Proc. International Conference on Formal Concept Analysis, Lecture Notes in Artificial Intelligence, vol. 4933, pp. 217-228.

25. Bernhard Ganter, Gerd Stumme, Rudolf Wille: Formal Concept Analysis, Foundations and Applications Springer 26. R. Godin, P. Valtchev. Formal Concept Analysis-Based Class Hierarchy Design in Object-Oriented Software Development. In.: B. Ganter, G. Stumme, and R. Wille. (Eds.) Formal Concept Analysis, Foundations and Applications, LNAIvolume 3626, pages 209–231. Springer Berlin / Heidelberg, 2005.

27. W. Hesse, T. Tilley. Formal Concept Analysis Used for Software Analysis and Modelling. In.: B. Ganter, G. Stumme, and R. Wille. (Eds.) Formal Concept Analysis, Foundations and Applications, LNAI volume 3626, pages 259–282. Springer Berlin / Heidelberg, 2005.

28. D.I. Ignatov, S.O. Kuznetsov. Concept-based Recommendations for Internet Advertisement// In proceedings of The Sixth International Conference Concept Lattices and Their Applications (CLA'08), Radim Belohlavek, Sergei O. Kuznetsov (Eds.): CLA 2008, pp. 157–166 ISBN 978–80–244– 2111–7, Palacky University, Olomouc, 2008.

29. D.I. Ignatov, S.O. Kuznetsov. Frequent Itemset Mining for Clustering Near Duplicate Web Documents// In proceedings of The 17th International Conference on Conceptual Structures, S. Rudolph, F. Dau, and S.O.Kuznetsov (Eds.): ICCS 2009, LNCS (LNAI) 5662, pp. 185–200, Springer-Verlag Berlin Heidelberg, 30. Dmitry I. Ignatov, Sergei O. Kuznetsov, Ruslan A. Magizov and Leonid E. Zhukov. From Triconcepts to Triclusters// In proceedings of 13th International Conference on ROUGH SETS, FUZZY SETS, DATA MINING AND GRANULAR COMPUTING, Kuznetsov et al. (Eds.): RSFDGrC 2011, LNCS/LNAI Volume 6743/2011, Springer-Verlag Berlin Heidelberg, 257Dmitry Ignatov and Serafima Mamedova and Nikita Romashkin and Ivan Shamshurin. What can closed sets of students and their marks say?// In proceedings of 4th International Conference on Educational Data Mining, Mykola Pechenizkiy et al. (Eds.), EDM-2011, TU/e Eindhoven, 223-228, 32. Koester, B. (2006) Conceptual Knowledge Retrieval with FooCA: Improving Web Search Engine Results with Contexts and Concept Hierarchies.

P. Perner (Ed.): ICDM, LNAI 4065, 176-190. Springer.

33. Sergei O. Kuznetsov, Dmitrii I. Ignatov, Concept Stability for Constructing Taxonomies of Web-site Users// Proc. Satellite Workshop «Social Network Analysis and Conceptual Structures: Exploring Opportunities» at ICFCA'07, Clermont-Ferrand, France, P. 19-24.

34. S.O. Kuznetsov and S.A. Obiedkov, Comparing Performance of Algorithms for Generating Concept Lattices, Journal of Experimental and Theoretical Artificial Intelligence, vol. 14 (2002), pp. 189-216.

35. S.O. Kuznetsov, Galois Connections in Data Analysis: Contributions from the Soviet Era and Modern Russian Research, in Formal Concept Analysis: Foundations and Applications, B. Ganter, G. Stumme, R. Wille, Eds., Lecture Notes in Artificial Intelligence, State-of-the Art Ser. (2005), vol.

3626, pp. 196-225.

36. Lakhal, L., Stumme, G. (2005) Efficient Mining of Association Rules Based on Formal Concept Analysis. B. Ganter et al. (Eds.): Formal Concept Analysis, LNAI 3626, 180-195. Springer 37. Michael Luxemburger. Partielle Implikationen und partielle Abhngigkeiten zwischen Merkmalen. Diplomarbeit, TH Darmstadt, 1988.

38. Loc Cerf, Jrmy Besson, Cline Robardet, Jean-Franois Boulicaut:

Data Peeler: Contraint-Based Closed Pattern Mining in n-ary Relations. SDM 2008: 37- 39. Mohr, J., Duquenne, V.: The duality of culture and practice: Poverty relief in New-York City, 1888-1917. Theory and Society 26, 305–356 (1997) 40. Mohr, J., Bourgeois, M., Duquenne, V.: The Logic of Opportunity: A Formal Analysis of the University of California’s Outreach and Diversity Discourse. Center for Studies in Higher Education, UC Berkeley, Research and Occasional Papers Series (2004) 41. Jonas Poelmans, Paul Elzinga, Stijn Viaene, Guido Dedene: A Case of Using Formal Concept Analysis in Combination with Emergent Self Organizing Maps for Detecting Domestic Violence.ICDM 2009: 247- 42. Priss, U. (2000) Lattice-based Information Retrieval. Knowledge Organization, 27, 3, 132-142.

43. Richards, D. (2006) Ad-Hoc and Personal Ontologies: A Prototyping Approach to Ontology Engineering. A. Hoffmann et al. (Eds.): PKAW, LNAI 4303, 13-24. Springer.

44. Nikita Romashkin, Dmitry Ignatov and Elena Kolotova. How university entrants are choosing their department? Mining of university admission process with FCA taxonomies// In proceedings of 4th International Conference on Educational Data Mining, Mykola Pechenizkiy et al. (Eds.), EDM-2011, TU/e Eindhoven, 229-234, 45. Roth, C., Obiedkov, S., Kourie, D. (2008a) Towards Concise Representation for Taxonomies of Epistemic Communities. S.B. Yahia et al. (Eds.):

CLA 2006, LNAI 4923, 240-255. Springer.

46. G. Snelting. Concept Lattices in Software Analysis. In.: B. Ganter, G. Stumme, and R. Wille. (Eds.) Formal Concept Analysis, Foundations and Applications, LNAIvolume 3626, pages 151–167. Springer, 2005.

47. Stumme, G., Taouil, R., Bastide, Y., Pasqier, N.and Lakhal, L. Computing Iceberg Concept Lattices with Titanic. J. on Knowledge and Data Engineering, (42)2:189–222, 48. Tilley, T., Eklund, P. (2007) Citation analysis using Formal Concept Analysis: A case study in software engineering. 18th int. conf. on database and expert systems applications (DEXA).

49. T. Tilley, R. Cole, P. Becker, P. Eklund A Survey of Formal Concept Analysis Support for Software Engineering Activities. In.: B. Ganter, G. Stumme, and R. Wille. (Eds.) Formal Concept Analysis, Foundations and Applications, LNAI volume 3626, pages 250–271. Springer, 2005.

50. Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts // Ordered Sets / Ed. by I. Rival. — Dordrecht; Boston:

Reidel, 1982.— P. 445–470.

Система анализа данных коллаборативных Д. И. Игнатов1, А. Ю. Каминская2, А. А. Беззубцева3, К. Н. Блинкин [email protected], [email protected], [email protected] НИУ ВШЭ, Россия, 101000, г. Москва, ул. Мясницкая, д. Аннотация. В работе описывается система анализа данных коллаборативной платформы компании Witology. Проект находится в состоянии разработки, поэтому в статье отражены в основном методологические аспекты и результаты первых экспериментов.

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

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

Введение Успехи современной индустрии коллаборативных технологий ознаменовались появлением ряда новых платформ для проведения распределенных мозговых штурмов или осуществления так называемой общественной экспертизы, например, на Российском рынке такие продукты выпускают компании Witology [1] и Wikivote [2]. И, хотя до технологического прорыва еще далеко, несколько крупных проектов уже успешно завершены. Среди них «Сбербанк-21», анализ форумов АгентИгнатов Д.И., Яворский Р.Э. (ред.): Анализ Изображений, Сетей и Текстов, Екатеринбург, 16-18 марта, 2012.

© Национальный Открытый Университет «ИНТУИТ», Система анализа данных коллаборативных платформ CrowDM ства Стратегических Инициатив и др. Массивы данных нового типа систем, ядро которых составляют так называемые социосемантические сети, требуют новых подходов к анализу данных. В рамках данной статьи мы предлагаем новую методологическую базу для анализа данных коллаборативных систем, опирающуюся на современные модели и методы разработки данных (Data Mining) и искусственного интеллекта.

Как правило, в рамках одного проекта пользователи таких краудсорсинговых платформ [3] решают некую общую задачу, выдвигают идеи, оценивают идеи друг друга как эксперты, а в итоге по результатам обсуждений и рейтингования определяются лучшие идеи и люди – генераторы идей. Для более глубокого понимания поведения пользователей, выработки адекватных критериев оценки, анализа динамики и статистики в ходе развития проекта необходимы особые средства. Традиционные методы кластеризации, поиска сообществ и анализа текстов нуждаются в адаптации, а иногда и в полной переработке, требуют изобретательности для их результативного применения, т.е. получения действительно полезных и нетривиальных результатов. Мы кратко описываем модели данных, используемых в проекте, в терминах Анализа Формальных Понятий (АФП) [4]. Также мы приводим описание системы анализа данных CrowDM (Crowd Data Mining), ее архитектуру и методы, лежащие в основе ключевых этапов анализа данных.

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

Для анализа данных без ключевых слов предлагается применять методы анализа социальных сетей (Social Network Analysis), кластеризации (а также би- и трикластеризации [5, 6, 7, 8], спектральной кластеризации), анализ формальных понятий (решетки понятий, импликации, ассоциативные правила) и его расширения для случая мультимодальных данных, например, триадических [9]; рекомендательные системы [10, 11, 12] и статистические методы анализа (анализ распределений и средних значений).

Для методов анализа текстовых данных с использованием ключевых слов, основным является этап выделения ключевых слов и словосочетаний. Это направление компьютерной лингвистики заслуживает отдельного рассмотрения, поэтому в данной статье мы остановимся на Система анализа данных коллаборативных платформ CrowDM некоторых методах анализа данных без использования ключевых слов.

На схеме анализа (см. рис. 2) синим цветом выделены методы, описанные в данной статье.

Главными действующими лицами в краудсорсинговых проектах, а значит и в коллаборативных платформах, созданных для этих проектов, являются пользователи платформы, они же участники проекта. Будем рассматривать их в качестве объектов для анализа. Вместе с тем, каждый объект может обладать (или не обладать) определенным набором признаков. В качестве признаков пользователей коллаборативной платформы могут выступать темы, в обсуждении которых пользователь принимал участие, идеи, которые он выдвигал или за которые голосовал, и даже другие пользователи. Основным инструментом для анализа данных объектно-признаковой природы является анализ формальных понятий (АФП). Дадим формальные определения.

Контекстом в АФП называют тройку = (G, M, I), где G — множество объектов, M — множество признаков, а отношение I G M говорит о том, какие объекты какими признаками обладают. Для произвольных A G и B M определены операторы Галуа:

Оператор '' (двукратное применение оператора ') является оператором замыкания: он идемпотентен (A'''' = A''), монотонен (A B влечет A'' B'') и экстенсивен (A A''). Множество объектов A G, такое, что A'' = A, называется замкнутым. Аналогично для замкнутых множеств признаков — подмножеств множества M. Пара множеств (A, B), таких, что A G, B M, A' = B и B' = A, называется формальным понятием контекста. Множества A и B замкнуты и называются объемом и содержанием формального понятия (A, B) соответственно. Для множества объектов A множество их общих признаков A' служит описанием сходства объектов из множества A, а замкнутое множество A'' является кластером сходных объектов (с множеством общих признаков A'). Отношение «быть более общим понятием» задается следующим образом: (A, B) (C, D) тогда и только тогда, когда AC. Понятия формального контекста = (G, M, I), упорядоченные по вложению объемов образуют решетку B (G, M, I ), называемую решеткой понятий. Для визуализации решеток понятий используют т.н. диаграммы Хассе, т.е. граф покрытия отношения «быть более общим понятием».

Так как в худшем случае (булева решетка понятий) количество понятий равно 2min{|G|,|M|}, то для больших формальных контекстов разумно применять АФП, если данные разрежены. Так же можно использовать различные способы сокращения количества формальных понятий, такие Система анализа данных коллаборативных платформ CrowDM как отбор понятий по индексу устойчивости или размеру объема. Альтернативным подходом является ослабление определения формального понятия, как максимального прямоугольника в объектно-признаковой матрице все элементы которого принадлежат отношению инцидентности. Одним из таких ослаблений является определение объектнопризнакового бикластера [2,3].

Если (g, m)I, то (m', g') называется объектно-признаковым бикластером с плотностью (m',g')=|I(m'g')|/(|m'||g'|).

Приведем основные свойства оп-бикластеров:

1. для любого бикластера (A,B)2G2M выполняется 0(A,B)1.

2. оп-бикластер (m',g') является формальным понятием тогда и только тогда, когда =1.

3. Если (m', g') – бикластер, то (g'', g')(m', m'').

Пусть (A,B)2G2M будет бикластером и min неотрицательное действительное число такое, что 0min1, тогда (A, B) называется плотным, если он удовлетворяет ограничению (A,B)min.

Из вышеописанного следует, что оп-бикластеры отличаются от формальных понятий тем, что в них не обязательно наблюдается единичная плотность. Графически это означает, что не обязательно все «ячейки» на пересечении объектов и признаков бикластера должны быть заполнены (см. рис. 1).

Система анализа данных коллаборативных платформ CrowDM Помимо построения решеток понятий и их визуализации с помощью диаграмм Хассе используются импликации и ассоциативные правила для выявления признаковых зависимостей в данных. Далее на основе полученных результатов, можно формировать рекомендации, например, предлагать пользователям наиболее интересные для них обсуждения. Кроме того, можно произвести структурный анализ сети и применить методы кластеризации для поиска сообществ, а также статистические методы для частотного анализа различной активности пользователей.

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

Схема анализа Схема анализа данных системы CrowDM, создаваемой в данный момент проектно-учебной группой НИУ ВШЭ, представлена на рисунке 2. Ранее упоминалось, что после выгрузки данных из базы, мы получаем формальные контексты и коллекции текстов. Последние в свою очередь тоже преобразуются в формальные контексты после выделения ключевых слов. Далее анализируются полученные контексты.

Результаты экспериментов Для проведения первых двух экспериментов были отобраны формальные контексты, в которых в качестве объектов выступают пользователи платформы, а в качестве признаков – идеи, которые они предлагали в рамках одной из пяти тем проекта («Сбербанк и частный клиент»). Из всех идей были также отобраны лишь те, которые дошли почти до самого конца проекта. Считается, что объект «пользователь» обладает признаком «идея», если данный пользователь внес любой вклад в обсуждение идеи: является автором идеи, комментировал идею, оставил комментарий в ветке этой идеи, выставил оценку этой идее или комментариям к ней. Таким образом, найденные формальные понятия вида (U,I), где U – множество пользователей, I – множество идей, соответствуют так называемым эпистемическим сообществам (проще говоря, сообществам по интересам) из множества людей U, которые интересуются множествами идей I.

На рисунке 3 представлена диаграмма полученной решетки понятий.

Каждому узлу диаграммы решетки соответствует одно формальное понятие (в данной решетке всего 198 понятий). Также каждый узел поСистема анализа данных коллаборативных платформ CrowDM мечен множеством объектов и признаков, если этот узел является первым, где встречается данный объект (при движении снизу вверх по диаграмме) или признак (при движении сверху вниз) соответственно. Очевидно, что полученная диаграмма решетки является достаточно громоздкой для анализа по ее статическому изображению. Обычно в таких случаях для визуализации используют порядковые фильтры (верхняя часть решетки) или диаграммы множества устойчивых понятий. Мы в свою очередь демонстрируем отдельный фрагмент решетки (см. рис. 4), таким образом, объясняя способ ее «чтения».

Рис. 2. Схема анализа данных коллаборативных платформ в Система анализа данных коллаборативных платформ CrowDM Рис. 3. Диаграмма решетки формальных понятий для контекста Эксперименты были проведены в программе Concept Explorer, разработанной специально для применения алгоритмов АФП к объектнопризнаковым данным. Выделив любой узел решетки, можно увидеть объекты и признаки, соответствующие понятию в этом узле. Объекты «накапливаются» снизу (в данном примере множество объектов состоит из User45 и User22), признаки – сверху (у нас один признак – «Микрокредиты от 1000 до 5000»). Это означает, что пользователи User45 и User22 вместе участвовали в обсуждении идеи с указанным именем и больше ни один из пользователей участия в обсуждении не принимал.

Рис. 4. Фрагмент диаграммы решетки понятий Ниже представлены результаты применения алгоритмов бикластеризации на тех же самых данных.

Система анализа данных коллаборативных платформ CrowDM Рис. 5. Результат работы алгоритма бикластеризации BiMax Поясним рисунок 5. Эксперименты проведены в системе анализа данных генной экспрессии BicAT. Строки соответствуют пользователям, столбцы – идеям в рамках указанной темы, в обсуждении которых пользователи принимали участие. Цвет ячейки на пересечении соответствующей строки и столбца соответствует интенсивности вклада конкретного пользователя в данную проблему. Под вкладом пользователя понимается взвешенная сумма числа его комментариев к этой идее, количества оценок, при этом учитывается, является ли данный человек автором этой идеи, или нет. Самые светлые ячейки соответствуют нулевому вкладу, самые яркие (см. левую верхнюю ячейку на рис.6) – максимальному вкладу. После дискретизации данных (0 соответствовал нулевому вкладу, 1 – ненулевому) к ним был применен алгоритм бикластеризации BiMax, который нашел несколько бикластеров (см. пример на рисунке 6). Поскольку одной из задач проведения краудсорсинговых проектов является поиск людей со схожими идеями, представленный бикластер из 11 пользователей наиболее интересен, в то время как остальные найденные бискластеры содержали в среднем по 4-5 пользователей (с ограничением на количество идей в бикластере строго больше двух).

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

Система анализа данных коллаборативных платформ CrowDM Рис. 6. Бикластер с большим числом пользователей По оси абсцисс отложено количество оценок, оставленных пользователем. По оси ординат – число пользователей, которые выставили больше соответствующего числа оценок. Например, больше 5000 оценок поставил один пользователь (крайняя правая точка на оси абсцисс), а больше 4000 – уже упомянутый пользователь и еще один участник.

Всего участников, поставивших хотя бы одну оценку, 167. Множество Система анализа данных коллаборативных платформ CrowDM точек явно разделяется на две части: пологая длинная линия (от x=0 до 544 включительно) и более крутой хвост. Тот факт, что в логарифмических шкалах обе части выглядят похожими на прямые, указывает на то, что обе части, возможно, распределены по Парето.

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

Заключение Результаты первых экспериментов позволяют утверждать, что разрабатываемая методология окажется полезной для анализа данных коллаборативных систем и систем совместного пользования ресурсами.

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

Благодарности Работа выполнена в рамках проектно-учебной группы НИУ ВШЭ «Алгоритмы интеллектуального анализа данных (Data Mining) для Интернет-форумов обсуждения инновационных проектов».

Список источников 1. http://witology.com/ 2. http://www.wikivote.ru/ 3. Jeff Howe. The Rise of Crowdsourcing. Wired, 2006.

4. Ganter, B., Wille, R. Formal Concept Analysis. Springer, Heidelberg, 1999.

5. Игнатов Д.И., Кузнецов С.О. Бикластеризация объектно-признаковых данных на основе решеток замкнутых множеств// Труды 12-й национальной конференции по искусственному интеллекту, М., Физматлит, Т.

1., С.175-182, 2010.

6. Игнатов Д.И., Каминская А.Ю., Кузнецов С.О., Магизов Р. А. Метод бикластеризации на основе объектных и признаковых замыканий// Интеллектуализация обработки информации: 8-я международная конференция. Республика Кипр, г. Пафос, 17-24 октября 2010 г.: Сборник докладов.– М.: МАКС Пресс, 2010. – С. 140 – 143.

Система анализа данных коллаборативных платформ CrowDM 7. Игнатов Д.И., Магизов Р.А. Анализ тримодальных данных на примере Интернет-сервисов социальных закладок// Социологические методы в современной исследовательской практике: Сборник статей, посвященный памяти первого декана факультета социологии НИУ ВШЭ А.О.

Крыштановского / Отв. ред. и вступит. ст. О.А. Оберемко; НИУ ВШЭ, ИС РАН, РОС. М.: НИУ ВШЭ, 2011.

8. Игнатов Д. И., Кузнецов С. O., Пульманс Й. Разработка данных систем совместного пользования ресурсами: от трипонятий к трикластерам //Математические методы распознавания образов: 15-я Всероссийская конференция. г. Петрозаводск, 11–17 сентября 2011 г.: Сборник докладов. — М.: МАКС Пресс, 2011. — 618 с. (ISBN 978-5-317-03787-1) 9. Robert Jschke, Andreas Hotho, Christoph Schmitz, Bernhard Ganter, Gerd Stumme: TRIAS - An Algorithm for Mining Iceberg TriLattices. ICDM 2006: 907- 10. Игнатов Д.И., Кузнецов С.О. Методы разработки данных (Data Mining) для рекомендательной системы Интернет-рекламы // Одиннадцатая национальная конференция по искусственному интеллекту с международным участием (КИИ-2008, 28 сентября – 3 октября 2008 г., г.

Дубна, Россия): Труды конференции. Т.2. – М.: Ленанд, 2008. – 392 с.

11. D.I. Ignatov, S.O. Kuznetsov. Concept-based Recommendations for Internet Advertisement// In proceedings of The Sixth International Conference Concept Lattices and Their Applications (CLA'08), Radim Belohlavek, Sergei O. Kuznetsov (Eds.): CLA 2008, pp. 157–166 ISBN 978–80–244– 2111–7, Palacky University, Olomouc, 2008.

12. Dmitry I. Ignatov, Sergei O. Kuznetsov, Ruslan A. Magizov and Leonid E. Zhukov. From Triconcepts to Triclusters// In proceedings of 13th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing, Kuznetsov et al. (Eds.): RSFDGrC 2011, LNCS/LNAI Volume 6743/2011, Springer-Verlag Berlin Heidelberg, 257-264, 2011.

Аннотация. Статья представляет собой обзор технологий Semantic Web и Linked Data. Дано краткое введение в технологии и протоколы, рассмотрены некоторые приёмы работы с данными. В помощь разработчику приведены ссылки на литературу и ресурсы сообщества Semantic Web.

Ключевые слова: semantic web, linked data, обзор Введение За одиннадцать лет своего существования семантический веб (Semantic Web, SW) прошел путь от одной амбициозной идеи в голове Тима Бернерса-Ли до целого направления в науке, и, кроме того, разработанные технологии и полученные научными группами результаты давно успели найти свое применение на практике.

Сейчас все больше крупных компаний как проявляют интерес к уже существующим проектам в области семантического веба, так и создают свои собственные. Например, проект семантического поиска Powerset был выкуплен компанией Microsoft и использован при создании Bing поисковой системы, сравнимой по качеству результатов с Yahoo! и Google. В свою очередь Google купил компанию Metaweb, разрабатывающую базу знаний Freebase и средство очистки данных Gridworks (новое название Google Refine). Компании IBM и Oracle занялись разраИгнатов Д.И., Яворский Р.Э. (ред.): Анализ Изображений, Сетей и Текстов, Екатеринбург, 16-18 марта, 2012.

© Национальный Открытый Университет «ИНТУИТ», Прагматическое введение в Semantic Web и Linked Data боткой RDF-хранилищ и библиотек доступа. Наконец, огромным успехом семантического веба можно считать появление ресурса schema.org, на котором размещается общая схема метаданных, которые учитываются поисковыми машинами Google, Yahoo, Bing и Яндекс.

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

Довольно сложно спорить с тем, что Semantic Web - это актуально.

Целью этой статьи будет изложение основ семантических технологий1 с прагматических позиций. После краткого введения будет рассмотрено несколько примеров задач, ради решения которых стоит браться за изучение стандартов Semantic Web. Затем будет произведен краткий обзор стандартов, используемых сегодня для представления данных и доступа к ним, а также будут показаны некоторые приёмы, использующиеся при изучении источников RDF-данных. Наконец, будут названы основные инструменты исследователя и программиста и вкратце затронут вопрос публикаций собственных данных в общепринятых форматах. Статья завершается кратким обзором литературы, электронных ресурсов и событий, посвященных Linked Data.

Общие сведения «Семантический веб - это веб данных» - объясняет комитет по стандартизации W3C на официальной странице проекта Semantic Web. Термин был введен Тимом Бернерсом-Ли, создателем World Wide Web [1] и основателем консорциума W3C. Свое видение Тим и его коллеги изложили в публицистической статье The Semantic Web [2]. Центральным элементом проекта являются действующие во всемирной паутине автоматические агенты, оперирующие со структурированными данными. Эти агенты могут выполнять интеллектуальные поисковые запросы, добывать новые знания из уже имеющихся, и таким образом помогать людям принимать важные решения.

В консорциуме W3C начали разрабатываться стандарты для обеспечения жизненного цикла данных во всемирной паутине. Тимом БерЗдесь и далее под семантическими технологиями и форматами понимаются те из них, которые имеют отношение к Semantic Web.

http://www.w3.org/2001/sw/ Система анализа данных коллаборативных платформ CrowDM нерсом-Ли была предложена высокоуровневая архитектура, получившая название слоеного пирога семантического веба: Все сущности в вебе должны соответствовать т.н. ресурсам, а те, в свою очередь, должны уникальным образом идентифицироваться с помощью URI (Uniform Resource Identifier, [3]), частным случаем которыя являются URL.

Для обмена данными должен использоваться язык XML [4].

«Точно так же, как HTML был создан, чтобы любой пользователь мог читать Internet-документы, XML дает нам то эсперанто, на котором любой может читать и писать, невзирая на вавилон несовместимых платформ» [5].

Для представления данных используется графовый язык Resourse Description Framework [6], [7], где данные описываются тройками идентификаторов и XML-литералов в последовательности «субъект»-»предикат»-»объект». Мощь подобного представления данных в том, что такие графы легко объединять между собой - для объединения данных из двух RDF-файлов достаточно дописать один файл в конец другого. RDF имеет несколько способов записи (сериализации) в виде троек «субъект - предикат - объект» (Notation3 [8], Turtle [9], N-triples) и в виде Простые схемы данных описываются в терминах RDF Schema [11] – аналога XML Schema для RDF. С течением времени схеиз презентации http://www.w3.org/2007/Talks/0130-sb-W3CTechSemWeb мы могут эволюционировать, при этом не нужно обновлять RDF-данные, связанные с этими схемами. RDF Schema позволяет оперировать таксономическими связами, а также задавать области определения и значения предикатов.

5. К данным должны осуществляться запросы - для этого существует язык запросов и протокол, специфицируемые стандартом SPARQL[12][13].

6. Сложные схемы данных описываются языком OWL, по ним доступен логический вывод новых фактов. OWL прочно стоит на логическом фундаменте (его подмножество OWL-DL основывается на формализме дескрипционных логик [14], [15], [16]) и предоставляет гораздо большую выразительность для описания словарей. Для того, чтобы подчеркнуть тот факт, что RDFSи OWL-документы являются полноценными схемами данных и на их основе можно производить логический вывод, их называют онтологиями [17].

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

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

Желающим изучить стек семантического веба подробнее следует обратиться к книгам и обзорам, рекомендуемым в последней главе данной статьи. Из русскоязычных работ рекомендуется [18] и вики Semantic Future1 Для понимания роли семантического веба в контексте развития всемирной паутины следует обратиться к документам по развитию WWW2 и книге [19].

Область применения Linked Data Использование технологий семантического веба позволяет улучшить многие приложения, но наиболее успешно применяются для следующих задач:

получение актуальных структурированных данных из внешних публикация собственных массивов данных во всемирной паутине для использования сторонними организациями, повышение релеватности поисковой выдачи, http://semanticfuture.net/ http://www.w3.org/DesignIssues/ Система анализа данных коллаборативных платформ CrowDM улучшение структуры публикуемых данных, поддержка задач компьютерной лингвистики, автоматический сбор статистики и анализ данных, удовлетворяющих определенным критериям.

Приведем несколько примеров разработанных приложений, которые могут прояснить то, как используются данные в семантическом вебе:

Проекты, похожие на Where does my Money Go 1 помогают британскому налогоплательщику понять, как государство тратит его деньги: приложение использует красочную инфографику для того, чтобы показать связь доходов пользователя с теми государственными проектами, которые сейчас активны: работы в области здравоохранения, охраны окружающей среды, науки и т.д. Приложение использует официальные регулярно обновляемые данные о налогах из data.gov.uk в формате RDF. Благодаря тому, что эти данные связаны с тематической онтологией, многочисленные статьи расходов иерархически структурированы и позволяют легко создавать аналитические приложения.

компания BBC постепенно внедряет достижения семантического веба на своих вебсайтах. И неудивительно - у корпорации есть не только огромные массивы данных о многих музыкальных и научно-популярных теле- и радиопрограммах, но и собственные исследовательские проекты, посвященные биологическому разнообразию. Веб-приложение BBC Wildlife finder2 увязывает эти данные воедино и соединяет их с внешними источниками: на странице, посвященной львам можно увидеть не только ссылки на все передачи BBC, посвященные этим величественным кошкам. Они включают в себя также динамически обновляемую информацию из Википедии (проекта Dbpedia [20], [21], [22]) и из международных биологических баз данных, предоставляющих их в виде RDF.

Кембриджский проект True Knowledge 3 позволяет мгновенно получать ответы на вопросы заданные на естественном языке.

А компания IBM недавно потрясла мир еще более впечатляющим проектом: их компьютер IBM Watson победил чемпиона мира по игре Jeopardy (российский аналог - передача «Своя игра» ). Оба этих проекта заявляют о том, что используют RDFданные Dbpedia [23].

http://wheredoesmymoneygo.org http://www.bbc.co.uk/nature/wildlife http://www.trueknowledge.com Работа с открытыми связанными данными Основным стимулом для изучения стандартов является существование большого количества опубликованных в общем доступе данных, для работы с которыми эти стандарты могут быть использованы.

Для того, чтобы быстро обозреть основные источники данных достаточно посмотреть на известное облако связанных данных (Linked Data Cloud)1. Видно, что наибольшее количество данных посвящено научным публикациям, затем следуют источники данных по биологии, открытые государственные данные и медиаинформация. Сравнительно небольшое количество датасетов (англ. dataset, источник данных) с географическим данными компенсируется большим количеством входящих и исходящих ссылок на них и довольно высоким качеством.

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

Самым правильным и удобным способ знакомства с данными является изучение их CKAN-описаний. CKAN Project2 - это хаб, на котором хранятся описания RDF-хранилищ, относящихся к Linked Data. Именно базы, попавшие в CKAN отображаются в облаке Linked Data. CKANстраницы датасетов содержат RDFS и OWL схемы, лежащие в основе RDF-баз, их машиночитабельные описания в формате VoID [24], ссылки на их SPARQL-точки (SPARQL endpoint), примеры описанных объектов и некоторую статистику.

Приведем несколько приёмов, использующихся для того, чтобы найти нужные данные в облаке Linked Data. В первую очередь, стоит проверить, есть ли база по интересующей вас теме в CKAN.

Затем можно воспользоваться RDF-поисковиком, например Sig.ma 3, Sindice4 или Swoogle5. После этого данные удобно просматривать с помощью RDF-браузера, наглядно показывающего объекты и их RDFсвойства. Иногда держатель данных предоставляет RDF-браузер на сайте (например, Dbpedia), но это не так, то можно воспользоваться браузерами Marbles6 или Operator7.

http://richard.cyganiak.de/2007/10/lod http://thedatahub.org http://sig.ma http://sindice.com http://swoogle.umbc.edu http://marbles.sourceforge.net https://addons.mozilla.org/en-US/firefox/addon/operator Система анализа данных коллаборативных платформ CrowDM Другим эффективным способом исследовать данные являются проверочные SPARQL-запросы. В таблице (Таблица 1) приведены примеры таких запросов.

SELECT * WHERE {?s ?p ?o} LIMIT SELECT DISTINCT ?p WHERE {?s показать не более тысячи свойств ?p ?o} LIMIT ?s ?p ?o.

?p a rdf:Property.

} LIMIT ?countPredicate) WHERE { GROUP BY ?p

ORDER BY DESC

(?countPredicate) LIMIT ?s ?p ?o.

} LIMIT При практическом использовании данных Semantic Web разработчику потребуется ряд инструментов. Перечислим наиболее часто применяющиеся:

средства конвертации данных в RDF (RDFizers), например RDF-редакторы, например OntoWiki3, Altova SemanticWorks® редакторы онтологий, например Protege5, NeOn Toolkit6, http://code.google.com/p/google-refine http://lab.linkeddata.deri.ie/2010/grefine-rdf-extension http://ontowiki.net/Projects/OntoWiki http://www.altova.com/solutions/semantic-web-tools.html http://protege.stanford.edu http://neon-toolkit.org http://www.topquadrant.com/products/TB_Suite.html Прагматическое введение в Semantic Web и Linked Data программные библиотеки для доступа к RDF-данным (RDF libraries and frameworks), например Jena (Java)1, Sesame (Java)2, dotNetRdf (.Net)3, ARC2 (PHP)4, Graphite (PHP)5, rdflib (Python)6, (Python)6, Redland (мультиязычная) движки логического вывода (reasoners, inference engines), например Pellet8, Fact++9, Hermit RDF-хранилища (RDF storages, triple storages), например OpenLink Virtuoso11, 4Store12, Sesame13.

Помимо этих инструментов программиста, существуют также готовые к использованию семантические платформы, например многочисленные семантические вики14 и CMS (англ. Content Management Systems, системы управления содержимым) с поддержкой RDF (модули для Joomla15 и Drupal16).

Подводя итог, можно без преувеличения можно сказать, что сегодня существуют программные средства (зачастую с открытым программным кодом) и интернет-сервисы, использование которых упростит разработку на всех стадиях построения семантического проекта. В [25] и [26] приведён подробный обзор инструментов в контексте жизненного цикла связанных данных и архитектуры приложений соответственно.

Существует также несколько списков и постоянно пополняемых каталогов подобного программного обеспечения. Обзор литературы и сообществ Исследователи и работники организаций, использующие в своей работе семантические технологии, формируют сообщество, и количестhttp://incubator.apache.org/jena http://www.openrdf.org http://www.dotnetrdf.org https://github.com/semsol/arc http://graphite.ecs.soton.ac.uk http://code.google.com/p/rdflib http://librdf.org http://clarkparsia.com/pellet http://owl.man.ac.uk/factplusplus http://hermit-reasoner.com http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main http://4store.org http://www.openrdf.org автором статьи поддерживается страница Семантические вики в Википедии http://swm.deri.org/jsyndication http://semantic-drupal.com http://www.w3.org/2001/sw/wiki/Tools Система анализа данных коллаборативных платформ CrowDM во участников этого сообщества постоянно растёт. Для того, чтобы помочь начинающему исследователю или разработчику сориентироваться, ниже приведен обзор событий, публикаций и ресурсов, связанных с семантическим вебом.

Книги и статьи С момента выхода статьи «The Semantic Web» в 2001 году тема семантического веба породила огромное количество исследований, и, как следствие, научных статей и книг. Заметим, однако, что чтение литературы, выпущенной до 2006-го года, вряд ли приблизит разработчика к пониманию современных подходов и инструментов семантического веба. Литература этого периода - это пионерские работы, записи проб и ошибок - её стоит читать только тем, кто глубоко погрузился в проблематику Semantic Web, но она не годится для тех, кто собирается использовать семантические технологии как подспорье для своей прикладной деятельности.

Книга «Semantic Web Programming» [25] служит отличным стартом для практической работы. Хебелер и соавторы отталкиваются от практических задач и дают прекрасный обзор с примерами на Jena. Работа «Programming the Semantic Web» [27] также прекрасно подходит для разработчиков ПО и содержит большое количество простых примеров на языке Python. Она перекликается с другой книгой Тоби Серагана «Программируем коллективный разум» [28] - замечательным введением в машинное обучение, data mining и социальные алгоритмы. Из бесплатных книг, касающихся темы практического использования Linked Data (англ. consuming Linked Data) стоит отметить книгу [29]. Кроме этого рекомендуются материалы лекций школ по Linked Data и Semantic Web (обзор таких школ приведён ниже).

Книги [30] и [31] не ориентированы на разработчика, а скорее представляют собой обзоры того, как устроен современный семантический веб, какие инициативы в нем реализуются, в то время как [32] рассказывает о математических основаниях проекта. «Handbook...» также содержит множество идей семантических приложений на основе существующих данных.

Тем, кто занимается публикацией массивов данных в вебе, нужно ознакомиться с бесплатными онлайн-книгами [33] и [34], статьёй [26], а также заметкой Тима Бернерса-Ли [35], позволяющую оценить предоставляемые данные по шкале от одного до пяти.

Списки рассылки и форумы Новичок в вопросах связанных данных всегда может найти достаточное количество ресурсов, дающих краткое введение в тему, а также имеет возможность задать интересующий его вопрос на одном из форумов или списках рассылки. Главные списки рассылки, Semantic Web 1 и public-lod2, служат как для общения участников, так и для информирования сообщества о предстоящих мероприятиях. Каждый из стандартов разрабатывает своя рабочая группа, имеющая свои списки рассылки;

аналогично поступают университетские лаборатории и команды, занимающимися разработкой ПО. Помимо этого, набирает популярность ресурс Semantic Overflow3 - форум экспертов, построенный на технологии StackExchange. Из русскоязычных можно выделить рассылки Веб Данных4 и Open Government5, рассылку школы KESW6 а также форум Semantic Future7.

Конференции и семинары Научные и технические новинки обсуждаются на тематических конференциях и семинарах. Наиболее престижной считается World Wide Web Conference8, затем следуют International Semantic Web Conference9 и Extended Semantic Web Conference 10. Примечательно то, что на этих событиях часто проводятся так называемые Doctoral Symposium, цель которых - помочь аспирантам определиться с темами их диссертаций. Русскоязычные конференции, в которых поднимается тема связанных данных и семантического веба это KESW 11, RCDL12, WebConf13, OSTIS14, КИИ15.

Журналы Зачастую в научных журналах предъявляются более высокие требования к качеству статей, нежели на конференциях. Поэтому публикация в уважаемом журнале высоко ценится, а статьи содержат полную и хорошо описанную информацию о проведённых исследованиях. Среди http://lists.w3.org/Archives/Public/semantic-web http://lists.w3.org/Archives/Public/public-lod http://answers.semanticweb.com http://groups.google.com/group/webofdata-russian http://groups.google.com/group/opengovdataru https://groups.google.com/group/kesw-school http://forum.semanticfuture.net http://www2012.wwwconference.org http://iswc2012.semanticweb.org http://2012.eswc-conferences.org http://kesw.ifmo.ru http://rcdl.ru/ http://www.webconf.bsu.by http://conf.ostis.net http://www.isa.ru/cai журналов по семантическим технологиям стоит выделить SWJ 1, IJSWIS2, ETAI3, IJSWIS4, JWS5.

Школы Школы являются прекрасным способом систематизации знаний и изучения нового на практике за короткий промежуток времени. На момент написания статьи на тему семантических технологий регулярно проводится несколько летних школ: Reasoning Web 6, ESWC Summer School7, SSSW8, ASWS9, SSSC10. Лекторами на европейских и американских школах зачастую становятся признанные учёные с большим опытом и разработчики известных приложений. Из русскоязычных школ можно выделить KESW11 и Russir12. Помимо самого процесса обучения, на школе есть возможность проконсультироваться по теме дипломной или диссертационной работы с признанными экспертами. Чтение материалов таких школ тоже крайне полезно, так как обычно это качественные обзоры.

Новостные ресурсы Для того, чтобы быть в курсе последних событий, стоит посещать не только подписаться на рассылки, но и посещать новостные ресурсы (либо подписаться на обновления с них с помощью RSS-агрегаторов). В первую очередь это сайты w3.org, semanticweb.com и semanticweb.org (последний вебсайт является вики-системой и туда стоит добавлять информацию о своих разработках). Раздел, посвященный семантическим технологиям есть на сайте ReadWriteWeb13. Сайт AI314 также занимается отслеживанием последних новостей. Ресурс Cloud of Data 15 предоставляет новости и интервью в виде аудиоподкастов.

http://www.semantic-web-journal.net http://www.igi-global.com/journal/international-journal-semantic-web-information/ http://www.etaij.org/seweb http://www.ijswis.org http://www.websemanticsjournal.org http://reasoningweb.org http://summerschool2012.eswc-conferences.org http://sssw.org http://asws2011.semsphere.com http://sssc2011.sti2.org http://kesw.ifmo.ru http://romip.ru/edbt-russir http://www.readwriteweb.com/archives/semantic-web http://www.mkbergman.com http://cloudofdata.com Прагматическое введение в Semantic Web и Linked Data Сообщество Наконец, стоит сказать о некоторых группах в сообществе Semantic Web. Одни исследователи ориентированы на данные и исповедуют подход снизу вверх (bottom-up): сюда входят создатели крупнейших общедоступных баз данных и исследователи, работающие в области ubiquitous computing. Они признают важность использования онтологий для схем данных, но эти онтологии используют довольно мало возможностей OWL (в основном owl:sameAs), могут содержать противоречия (быть несогласованными, англ. inconsistent), а для их обработки помимо алгоритмов логического вывода могут применяться и структурные подходы вроде вывода по графам. Другая группа вышла из сообщества логиков и меньше заботится о публикации и связывании данных, ориентируясь на мощный логический вывод: таковы проекты из области биоинформатики. Наконец, существует прослойка, занимающаяся системным анализом и моделированием - с помощью OWL и языков представления правил они создают модели предметных областей и бизнес-процессов.

Их онтологии должны быть понятны людям, а потому большое значение придаётся визуализациям (в том числе на UML). И, хотя формально граница между этими фракциями не проводится, крайне важно правильно расставить свои приоритеты при выборе данных и онтологий для повторного использования.

Заключение Использование семантических технологий перестало быть уделом исследовательских лабораторий - стандарты, форматы, библиотеки и программы для работы со связанными данными успешно используются для создания коммерческих приложений. Постоянно растущее количество RDF-данных, доступных через SPARQL-интерфейсы, открывает перспективы для создания функциональных и мощных приложений в гораздо более короткие сроки, чем это было возможно раньше. В этой статье было дано введение в технологии Linked Data и Semantic Web с точки зрения прикладного программиста. Автор надеется, что предоставленный обзор и ссылки окажут помощь разработчику в написании приложений нового поколения.

Благодарности Автор хочет поблагодарить Починок Ирину за ценные советы и замечания относительно текста статьи.

Система анализа данных коллаборативных платформ CrowDM Список источников 1. Berners-Lee T. et al. World-Wide Web: The Information Universe // Internet Research. 1992. Vol. 2, № 1. P. 52–58.

2. Berners-Lee T., Hendler J., Lassila O. The Semantic Web // Scientific American / ed. Gmez-Prez A., Yu Y., Ding Y. Citeseer, 2001. Vol. 284, № 5. P. 34–43.

3. Berners-Lee T., Fielding R., Masinter L. RFC 3986 - Uniform Resource httptoolsietforghtmlrfc3986. Network Working Group, 2005. P. 1–62.

4. Bray T., Paoli J., Sperberg-McQueen C. Extensible Markup Language (XML) // W3C recommendation. World Wide Web Consortium, 2000. Vol.

2004, № 31-05. P. 1–7.

5. Bosak J., Bray T. XML and the Second-Generation Web // Scientific American. Scientific American, 1999. Vol. 280, № 5. P. 89–93.

6. Lassila O., Swick R.R. Resource Description Framework (RDF) Model and Syntax Specification // World Wide Web Internet And Web Information Systems / ed. Lassila O., Swick R.R. 1999. Vol. 2004, № October. P. 1–54.

7. Manola F., Miller E. RDF Primer // W3C Recommendation / ed. Manola F., Miller E. W3C, 2004. Vol. 10, № February. P. 1–107.

8. Berners-Lee T. Notation3 (N3) A readable RDF syntax // Design Issues.

W3C, 1998.

9. Beckett D., Berners-Lee T. Turtle - Terse RDF Triple Language // W3C Team Submission. Chapman and Hall, 2008. Vol. 28, № January. P. 3–11.

10. Beckett D. RDF/XML Syntax Specification (Revised) // W3C recommendation / ed. Beckett D. World Wide Web Consortium, 2004. Vol. 10. P.

1–37.

11. Brickley D., Guha R.V. RDF Vocabulary Description Language 1.0:

RDF Schema // W3C Recommendation / ed. McBride B. W3C, 2004. Vol.

2009, № 10 February 2004.

12. Prud’hommeaux E., Seaborne A. SPARQL Query Language for RDF // W3C Recommendation / ed. Prud’hommeaux E., Seaborne A. W3C, 2008.

Vol. 2009, № January. P. 1–106.

13. Harris S., Seaborne A. SPARQL 1.1 Query Language // W3C Working Draft / ed. Harris S., Seaborne A. W3C, 2010. № May.

14. Nardi D., Brachman R.J. An Introduction to Description Logics.

Прагматическое введение в Semantic Web и Linked Data 15. Baader F. Basic Description Logics // The Description Logic Handbook / ed. Baader F. et al. Cambridge University Press, 2003. Vol. 25, № 1. P. 43– 95.

16. Schulz S., Hahn U. Description Logics // Studies In Health Technology And Informatics / ed. Van Harmelen F., Lifschitz V., Porter B. Springer-Verlag, 2004. Vol. 101, № 07. P. 137–141.

17. Gruber T.R. A translation approach to portable ontology specifications // Knowledge Acquisition. Citeseer, 1993. Vol. 5, № 2. P. 199–220.

18. Андон Ф.И., Гришанова И.Ю., Резниченко В.А. Semantic Web как новая модель информационного пространства Интернет | Щербак Сергей [Online]. 2009. URL: http://shcherbak.net/semantic-web-kak-novayamodel-informacionnogo-prostranstva-internet/ (accessed: 21.02.2012).

19. Berners-Lee T. Weaving the Web // The original design and ultimate destiny of the world wide web by its inventor. Harper Collins, 1999. P. chapter 12.

20. Kobilarov G. et al. DBpedia - A Linked Data Hub and Data Source for Web and Enterprise Applications // Knowledge Creation Diffusion Utilization. 2009. P. 1–3.

21. Bizer C. et al. DBpedia - A crystallization point for the Web of Data // Web Semantics Science Services and Agents on the World Wide Web. Elsevier, 2009. Vol. 7, № 3. P. 154–165.

22. Auer S. et al. Dbpedia: A nucleus for a web of open data // The Semantic Web / ed. Aberer K. et al. Springer, 2007. Vol. 4825, № Springer. P. 722– 735.

23. Ferrucci D. et al. Building Watson: An Overview of the DeepQA Project // AI Magazine. Association for the Advancement of Artificial Intelligence, 2010. Vol. 31, № 3. P. 59–79.

24. Alexander K. et al. Describing Linked Datasets with the VoID Vocabulary // Knowledge Creation Diffusion Utilization. 2010. № March.

25. Hebeler J., Fisher M., Blace R. Semantic web programming. 2011.

26. Auer S., Lehmann J., Ngonga Ngomo A.C. Introduction to linked data and its lifecycle on the web // Reasoning Web Semantic Technologies for the Web of Data / ed. Polleres A. et al. Springer, 2011. Vol. 6848. P. 1–75.

27. Segaran T., Evans C., Taylor J. Programming the Semantic Web // Semantic Web Services Processes and Applications / ed. Treseler M. O’Reilly Media, 2009. Vol. 54, № 2. P. 300.

Система анализа данных коллаборативных платформ CrowDM 28. Segaran T. Programming Collective Intelligence // Computational intelligence the experts speak. O’Reilly, 2007. P. 368.

29. Heath T., Bizer C. Linked Data: Evolving the Web into a Global Data Space // Synthesis Lectures on the Semantic Web Theory and Technology / ed. Van Harmelen F., Hendler J. Morgan & Claypool, 2011. Vol. 1, № 1. P.

1–136.

30. Pollock J. Semantic Web for dummies // Production. 2009.

31. Year C. et al. Handbook of Semantic Web Technologies // World Wide Web Internet And Web Information Systems / ed. Domingue J., Fensel D., Hendler J.A. Springer Berlin Heidelberg, 2011. P. 157–190.

32. Hitzler P., Krtzsch M., Rudolph S. Foundations of Semantic Web Technologies // Chapman Hall CRC Press. Chapman & Hall/CRC, 2009. P.

427.

33. Bizer C., Cyganiak R., Heath T. How to Publish Linked Data on the Web // Publish. 2007. Vol. 20, № October. P. 43.

34. Dodds L., Davis I. Linked Data Patterns [Online]. 2011. URL:

http://patterns.dataincubator.org/book/ (accessed: 21.02.2012).

35. Berners-Lee T. Linked Data // TED. 2009.

Сходимость эмпирических случайных процессов и обобщающая способность Институт математики и механики УрО РАН, 620219, Россия, г.Екатеринбург, Уральский государственный университет, 620000, Россия, г. Екатеринбург, ул.

Аннотация. Классический подход к обоснованию алгоритмов обучения распознаванию и восстановления эмпирических закономерностей более общей природы связан с выводом гарантированных оценок математического ожидания подходящей функции потерь. Построение подобных оценок на основе материала обучения традиционно связано с рассмотрением сходимости подходящих эмпирических случайных процессов. При этом получаемые результаты опираются либо на условия равномерной сходимости (родственные теореме Гливенко-Кантелли), либо слабой сходимости (близкие к ЦПТ и теореме Донскера) исследуемых процессов. В докладе наряду с известными будут приведены новые результаты, касающиеся достаточных условий как первого, так и второго рода для специального класса эмпирических процессов, порождаемых процедурами обучения.

Ключевые слова: машинное обучение, обобщающая способность, оценки сходимости.

Игнатов Д.И., Яворский Р.Э. (ред.): Анализ Изображений, Сетей и Текстов, Екатеринбург, 16-18 марта, 2012.

© Национальный Открытый Университет «ИНТУИТ», Влияние метрики на эффективность Аннотация. Сжатие видео и повышение качества изображения являются актуальными задачами видео кодирования и средством повышения эффективности анализа видеоизображений. Основным этапом кодирования, влияющим на степень сжатия, является оценка движения. В статье представлен анализ существующих метрик оценки движения и предложен новый метод, обеспечивающий лучшие показатели сжатия при том же качестве изображения.

Ключевые слова: метрика, оценка движения, сжатие видео, алгоритм сопоставления блоков, метод полного перебора, метод бриллиантового поиска, стандарт MPEG-4, квантование, дискретное косинусное преобразование, зигзаг-преобразование.

Введение Одна из наиболее актуальных задач анализа видеоизображений – это распознавание объектов. Повысить эффективность реализации этой задачи можно посредством улучшения качества видео при неизменном размере видеофайла. Этого можно добиться путем применения алгоритмов эффективного сжатия.

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

Игнатов Д.И., Яворский Р.Э. (ред.): Анализ Изображений, Сетей и Текстов, Екатеринбург, 16-18 марта, 2012.

© Национальный Открытый Университет «ИНТУИТ», Влияние метрики на эффективность сжатия видеоизображения Основная сложность при работе с видео – недостаточная пропускная способности канала связи, до 100 Мбит/с. Тогда как для передачи видео 720480 пикселей в формате RGB c частотой 25 кадров в секунду необходим канал с пропускной способностью 198 Мбит/с, а для видео HDTV 1280720 пикселей – 633 Мбит/с. При этом, принимая во внимание значительную избыточность, присущую видеоизображениям, используют алгоритмы сжатия.

Оценка и компенсация движения являются основными этапами сжатия видео во многих телекоммуникационных системах, например, телевидение высокой и стандартной четкости (HDTV и SDTV), видео конференции и мультимедиа сервисы для Web приложений. Международные стандарты, такие как MPEG, ATSC, и ITU в качестве метода оценки движения регламентируют применять алгоритм сопоставления блоков (Block Matching Algorithm – BMA) [1]. Основной частью алгоритма BMA является метод поиска остаточных блоков и векторов смещения или как его принято называть – метрика. По причине того, что в стандарте не регламентируется выбор этого метода, существует несколько метрик, многие из которых не обеспечивают наилучшее сжатие видео в условиях неизменного качества изображения.

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

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

Популярные метрики Алгоритм BMA состоит в разбиении текущего кадр на непересекающиеся блоки одного размера и поиске наиболее схожего блока текущего кадра с блоком из заданной области на предыдущем кадре. Наиболее популярными метриками этого алгоритма являются энергия остатка (SSD) и суммарная абсолютная разность (SAD) [1].

Суммарная квадратичная ошибка (Sum of Square Difference – SSD) вычисляется по формуле (1).

Суммарная абсолютная разница (Sum of Absolute Difference – SAD) – по формуле (2).

Влияние метрики на эффективность сжатия видеоизображения где: Obj – прямоугольный блок размером NN пикселей YСur и YRf – яркость текущего и предыдущего кадров, соответственно, в точке p=(x,y).

Схема кодирования с использованием метрики SAD представлена на рис. 1.

Рис. 1. Схема алгоритма кодирования одного блока кадра с Влияние метрики на эффективность сжатия видеоизображения При применении подобных метрик блок текущего кадра C сравнивается с каждым блоком-кандидатом Si из области поиска S на предыдущем кадре по формуле (1) или (2). Получается n (количество блоков зависит от размера области поиска) значений метрики для блока SAD(C,Si). Наименьшее значение определяет координаты вектора движения блока vec(min SAD(C,Sk)). После оценки движения осуществляется его компенсация на основе полученных координат вектора, вычисляется скомпенсированный блок. Далее этот блок переводится в частотную область путем применения дискретного косинусного преобразования (ДКП). Полученные ДКП-коэффициенты квантуются. К квантованному блоку применяются коды переменной длины. Результатом такого кодера является битовая последовательность.

Реализация каждого блок схемы рис. 1 описана в стандарте ISO/IEC 14496 Part 2 («MPEG4 Visual») [2].

SAD и SSD являются упрощенными, и их применение снижает вычислительную сложность алгоритма. При этом точность оценки движения такими метриками также снижается, что не позволяет максимально сжать видео при неизменном качестве видеоизображения.

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

1. Для фиксированного блока C текущего кадра вычисляются все возможные в области поиска S разностные блоки-кандидаты C-Si и определяются координаты всех векторов движения.

2. Каждый разностные блок переводится в частотную область путем применения дискретного косинусного преобразования (ДКП). Таким образом, для одного фиксированного блока получается множество ДКП блоков-кандидатов DCT(C-Si), i=1,2..n.

3. Все ДКП-блоки квантуются. Вычисляется QUANTi, i=1,2..n.

4. Применяется зигзаг-преобразование внутри каждого блока.

Зигзаг-преобразование – это перестановка пикселей блока с целью более эффективного кодирования.

5. Квантованные коэффициенты кодируются с использованием заранее фиксированной системы кодов переменной длины. ПроВлияние метрики на эффективность сжатия видеоизображения изводится подсчет количества бит для каждого блока-кандидата 6. Из всех полученных значений количества бит выбирается минимальное. Наименьшее значение определяет вектор движения и остаточный блок.

В рассмотренной литературе [3] подобная метрика не встречалась, поэтому назовем предложенный метод New Method (NM).

Рис. 2. Схема алгоритма кодирования одного блока кадра с Влияние метрики на эффективность сжатия видеоизображения Модель кодера Для исследования эффективности применения NM разработана модель кодера в соответствии со стандартом ISO/IEC 14496 Part («MPEG4 Visual») [2]. Стандарт предполагает выбор следующих параметров кодирования: коэффициент квантования от 1 до 31 и степень билинейной интерполяции для увеличения (масштабирования) изображения в 2 и в 4 раза по каждому из измерений. В модели выбран коэффициент квантования, равный 1, т.к. при таком значении наименьшие потери качества изображения. С целью увеличения скорости моделирования не используется интерполяция. Также стандарт определяет систему кодов переменной длины (VLC).