Автор: Максим Гончаров
Источник: Сайт www.BusinessDataAnalytics.ru предлагаетктуальные материалы об алгоритмах и технологиях добычи знаний и интеллектуального анализа данных.
Необходимость автоматического анализа информации из интернета вызвана высокой доступностью огромного количества постоянно пополняющейся информации, а также растущей популярностью веб-услуг среди всех категорий пользователей. Развитие Веба в глобальную информационную инфраструктуру позволило обычным пользователям быть не только потребителями информации, но ее создателями и распространителями. В этой связи для эффективного решения задач поиска, структурирования и анализа в основном хаотично организованной информации в сети предназначено новое направление в методологии анализа данных - Web Mining.
Web Mining развивается на пересечении таких дисциплин как обнаружение знаний в базах данных, эффективный поиск информации, искусственный интеллект, машинное обучение и обработка естественных языков.
В статье предпринята попытка дать классификацию методов Web Mining с точки зрения решаемых задач и реализуемых подходов.
Для нахождения необходимой информации пользователи обычно пользуются поисковыми ресурсами. При этом часто используются простые запросы по ключевым словам. Результатом выполнения запроса является список страниц, отсортированный по некому индексу релевантности, описывающему степень совпадения результата с запросом. Однако существующие поисковые механизмы обладают недостатками. Основным из них является низкая точность результата, вызванная недостаточным учетом семантических связей и контекста найденных в тексте выражений. Индексация интересующих сегментов сети с использованием интеллектуального анализа данных, применяющего алгоритмы математической лингвистики и обработки естественных языков, является перспективным направлением Web Mining в области поиска информации. Интересный подход описан в статье Anupam Joshi, "Improving Web Search Engine Results Using Clustering".
Этот метод заключается в анализе структуры ссылок между различными веб-страницами, внутренними и внешними сайтами в выделенном сетевом сегменте. Появление этого метода было вызвано необходимостью решения задач, возникающих при анализе социальных сетей или специфических областей человеческой деятельности или знаний, например, в анализе цитирования авторов. Результатом такого анализа может служить выявленный набор специфичных страниц следующих типов:
• хабы - из такой страницы ссылки идут на наиболее значимые ресурсы в данной области знаний или на "знакомства" с наиболее значимыми пользователями социальной сети;
• авторитеты - страницы, на которые ссылаются большое количеством авторов по данной тематике или пользователи социальной сети, к "дружбе" с которыми стремится большое количество пользователей.
Топология структуры ссылок представляется в виде направленного графа с помеченными узлами в соответствии с их функциональной классификацией и дугами с весами, описывающими, например, частоты переходов по ссылке. Для моделирования топологии веб-ссылок используется несколько алгоритмов, например HITS (Jon M. Kleinberg, "Authoritative sources in hyperlink environment").
Эта задача пересекается с уже описанной проблемой поиска информации. Только здесь у исследователя уже имеется набор веб-страниц, полученных в результате запроса. Далее требуется произвести их обработку с точки зрения автоматической классификации, составления оглавлений, выявления ключевых слов и общих тем. Выявленные знания могут представляться в виде деревьев, описывающих структуры документов или в виде логических и семантических выражений. Решение части этих проблем предлагает Text Mining - технология автоматического извлечения знаний в больших объемах текстового материала, основанная на сочетании лингвистических, семантических, статистических и машинных обучающихся методик (http://www.megaputer.ru/text_mining.php, Soumen Chakrabarti "Data mining for hypertext", Helena Ahonen-Myka, "Finding co-occuring text phrases by combining sequence and frequent set discovery")
Персонализации веб-пространства - задача по созданию веб-систем, адаптирующих свои возможности (навигация, контент, баннеры и другие рекламные предложения) под пользователя на основании собранной и проанализированной информации о пользовательских предпочтениях.
Классическим примером может являться ресурс http://www.amazon.com/, на котором один раз заказав дорогую книгу в твердом переплете, пользователь начинает регулярно получать предложения о покупке подарочных изданий по схожей тематике. Другой пример - на основании анализа корзин заказов пользователя ему предлагаются товары, которые он никогда не заказывал, но которые входят в корзины других покупателей, схожих с ним по транзакционному поведению.
Для анализа информации о пользователе следует в наименьшей степени использовать декларируемую о себе информацию, а скорее основываться на стойких шаблонах его "поведения" в сети - последовательности кликов внутри ресурса, переходах на другие под-ресурсы, периодах сетевой активности, осуществляемых покупках и т.д. См. B. Masand, Redwood, "Web Usage Analysis and User Profiling", Miha Gr?ar, "User profiling: Web usage mining".
Эта задача связана с предыдущей, но ее целью является не адаптация ресурса к предпочтениям индивидуальных пользователей, а поиск закономерностей в шаблонах взаимодействия пользователя с веб-ресурсом с целью прогнозирования его последующих действий. Анализируемые действия пользователей могут включать не только переходы по ссылкам, но и отправку форм, прокрутку страниц, добавление в избранные страницы и т.д. Найденные шаблоны используются в дальнейшем для оптимизации структуры сайта, изучения целевой аудитории и для прямого маркетинга.
Разработано множество подходов к решению задачи по выявлению знаний из шаблонов навигации пользователей (Jose Borges и Mark Levene "Data Mining of User Navigation Patterns", A. G. Buechner "Navigation Pattern Discovery from Internet Data").
С точки зрения применения алгоритмов интеллектуального анализа данных при поиске шаблонов пользовательского поведения чаще всего используются следующие методики:
• Кластеризация - поиск групп похожих посетителей, сайтов, страниц и т.д.
• Ассоциации - поиск совместно запрашиваемых страниц, заказываемых товаров.
• Анализ последовательностей - поиск последовательностей действий. Наиболее часто применяется вариант алгоритма apriori, разработанного для анализа частых наборов, но модифицированного для выявления частых фрагментов последовательностей и переходов.
Особенно интересен подход кластеризации последовательностей - поиск групп пользователей со схожими последовательностями действий. На первом этапе в этом подходе выделяются последовательности классифицированных действий пользователя, например, в рамках одной сессии. Затем подсчитываются частоты переходов между различными действиями для составления Марковской цепи заданного порядка. На заключительном этапе полученные Марковские цепи кластеризуются для выявления групп с похожими частотами переходов. Для прогнозирования следующего действия пользователя сначала на основании истории его действий в рамках сессии определяется группа, к которой он принадлежит с наибольшей вероятностью. Затем определяется действие, которое выполняется с наибольшей вероятностью в этой группе с учетом последних действий данного пользователя. Для реализации такого анализа можно, например, использовать алгоритм Microsoft Sequential Clustering, входящий в Microsoft Analysis Services 2005/2008. Недостатком алгоритма Microsoft является то, что до настоящего времени реализован алгоритм, использующий Марковские цепи только первого порядка.
В качестве примера применения метода анализа последовательности действий можно привести задачу по оптимизации рубрикации одного книжного интернет-магазина, проведенную компанией spellabs. Была выявлена группа, состоящая из пользователей, переходящих долгими путями по ссылкам на книги из разных рубрик и заказывающих в конечном итоге "изотерическую" литературу , до этого отдельно не выделенную в рубрику. Так была выявлена неучтенная целевая аудитория и оптимизирована структура сайта.
Web Mining является новым перспективным направлением анализа интернет-ресурсов для оптимизации структуры веб-сайтов, получения знаний о посетителях сайта, описания социальных сетей и сообществ, а также для автоматического поиска и структуризации информации из интернета.
Походящей инструментальной платформой для практической реализации описанных методов является Microsoft SQL Server 2008 Analytical Services.