Развитие методов и средств построения статистических облаков тегов на основе онтологической информации Фомин Илья Научные руководители: к. ф.-м. н., м.н.с. Браиловский И.В., м.н.с. Дмитриев Л.В.

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

Цели и задачи ЦелиЗадачи Исследовать область классификации информации в Веб 2.0 и разработать метод классификации информации, совмещающую онтологические и статистические данные Спроектировать и разработать макет системы, реализующий разработанный метод, и исследовать его практическую применимость для задач классификации и информационного поиска Исследование технологий, используемых для классификации информации в проектах Веб 2.0 Разработка метода и архитектуры реализующей его системы, а так же ее базовых алгоритмов, учитывающих недостатки существующих решений Программная реализации системы Апробация программной реализации Исследование применимости полученной программной реализации для практических задач классификации и информационного поиска

Анализ КаталогиТегиСтатистикаСовмещ. модель Delicious.com -++- Amazon.com +++- Flickr.com -+-- WordPress.com +++- Habrahabr.ru +++- Ozon.ru +++- Wikipedia.org + (категории) + (ссылки) -+ Построенная система ++++

Функциональная архитектура системы

Описание функциональных модулей МодульНазначение БЗОССБаза Знаний об Онтологических и Статистических Связях – хранит информацию Интерфейс к базе знанийОбеспечивает взаимодействие компонентов системы с БЗОСС Загрузчик онтологических данных Загружает информацию о связях между терминами из Википедии, заносит из в Базу Знаний Модуль построения множеств тегов Строит множества семантически близких тегов к данному термину или произвольному тексту Модуль вычисления семантической близости текстов Анализирует множества тегов, на их основе делает вывод о семантической близости произвольных текстов Программный интерфейсОбеспечивает взаимодействие сторонних приложений с системой Пользовательский интерфейс Обеспечивает взаимодействие пользователей с системой в интуитивно-понятной и наглядной форме

Эвристический алгоритм вычисления веса связи между элементами (тегами) Вес прямой типизованной связи между элементами: Вес итоговой прямой связи между элементами: Суммарный вес связи между элементами:

Эвристический алгоритм: константы, переменные ОбозначениеСемантикаЗначения СtСt Величина влияния онтологической связи типа t на ее итоговый вес [0..1] S Коэффициент влияния статистической компоненты 50 N t 1,2 Величина счетчика прямой связи типа t между элементами 1 и 2 > 0> 0 N1N1 Суммарное количество прямых связей у элемента 1 >= 0

Вычисление величины семантической близости текстов Мера Джаккарда: A, B – взвешенные множества тегов, семантически близких к соответствующим текстам

Реализация системы Функциональный модуль Способ реализации БЗОСС Приложение баз данных «Менеджер категорий», основанное на СУБД PostgreSQL 8.3. Совмещение данных и процедур работы с ними в одном компоненте позволило избавиться от многократных обменов информации между системами при построении множеств семантически связанных с данным тегов. В ходе данной операции происходит обход графа семантических связей, что требует до нескольких тысяч обращений к данным при построении одного множества. Интерфейс к базе знаний Модуль построения множеств тегов Модуль вычисления семантической близости текстов Программный интерфейс Загрузчик онтологических данных из Википедии Приложение загрузки данных Википедии. Пользовательский интерфейс Клиентское приложение с пользовательским интерфейсом для демонстрации возможностей системы

Реализация системы: Менеджер категорий: PostgreSQL 8.3 Реализация процедур работы с данными – pgplsql Доступ к данным возможен через API или произвольные SQL запросы 1 БД, 4 таблицы, 25 хранимых процедур Загрузчик онтологической информации Википедии: Платформа Java SE 1.6 URLConnection, XMLDocument, JDBC Использует API Менеджера Категорий Пользовательский интерфейс Предназначен для демонстрации возможностей системы Использует API Менеджера Категорий DHTML, VBS, WSH, ODBC

Модель базы знаний, хранящейся в БД Хранит граф разнотипных связей между терминами и их статистические характеристики Вес связей динамически изменяется при изменении статистических данных Эвристическая функция вычисления веса связей легко заменяется и настраивается при помощи констант Построение облака тегов (рекурсивный обход графа) происходит максимально быстро благодаря предварительно построенной таблице весов связей

Модель реляционной БД, реализующей БЗОСС

Программный интерфейс Доступ ко всей функциональности системы Использование SQL-интерфейса для максимальной универсальности Не требует знания синтаксиса и особенностей SQL Позволяет учитывать как все имеющиеся в системе связи, так и только связи, полученные из Википедии Изменение данныхВыборка данных long _addTag ( varchar, integer )boolean _isTagParsed ( varchar ) long _addTagDef ( varchar )set of ( varchar, integer, real ) _getCloud ( varchar, real, integer ) void _linkTags ( varchar, varchar, integer, integer ) varchar _getDirectLinks ( varchar, boolean ) boolean _setTagParsed ( varchar, boolean ) real _countSimilarity (text, text, real, integer, integer) void _fillLinks_counted ( boolean )set of ( varchar, integer, real ) _getCloud ( text, real, integer )

Режимы работы Пополнение базы знаний –Из Википедии посредством автоматического загрузчика данных –Из стороннего приложения – статистические данные от пользователей Построение взвешенного множества/облака семантически близких тегов для заданного термина Построение взвешенного множества/облака семантически близких тегов для произвольного текста (в т.ч. для поискового запроса) Вычисление величины семантической близости произвольных текстов на основе построенных взвешенных множеств тегов

Пример построенного облака тегов

Пример множеств тегов для сравнения

Практическое использование Система будет использована в качестве классификатора и вспомогательного средства информационного поиска в интернет-портале it-edu.ru

Результаты * Исследована область классификации информации в существующих проектах Веб 2.0 * Разработан метод классификации информации, совмещающий онтологические и статистические данные * Разработана архитектура и базовые алгоритмы системы, учитывающей полученную модель * Смоделированная система программно реализована * Программная реализация проверена и опробована на тестовых задачах * Исследована применимость программной реализации к задачам классификации информации и информационного поиска * Программная реализация подготовлена к внедрению в интернет- проект it-edu.ru Направление дальнейших исследований: * Реализация поддержки русского языка * Использование кросс-языковых ссылок Википедии для поиска семантически близких текстов на разных языках