Основной причиной роста электронной коммерции послужили простота и скорость, с которыми можно осуществлять покупки и другие операции через Internet. Особенно серьезные изменения претерпело общение с конечным пользователем — появилась и возможность персонифицировать предложения продавца для каждого клиента.
Извлечение знаний можно определить как нахождение и анализ полезной информации. Данную область деятельности принято подразделять на две части: автоматический поиск информации в документах Сети — Web content mining и обнаружение и обработка информации, касающейся работы пользователей с сервером, — Web usage mining.
Рост объема доступных через Internet данных, хранимых в слабо структурированном виде, способствовал появлению автоматических программных средств поиска информации и получения данных об использовании определенных ресурсов. Возник целый ряд интеллектуальных систем, основная задача которых состоит в эффективном извлечении знаний из Internet.
В статье осуществлен краткий обзор технологий, применяемых для сбора информации и извлечения знаний из использования Internet.
Основные этапы анализа
Процесс автоматического изучения характеристик доступа пользователей к серверам может включать изучение наиболее популярных путей посещения, нахождение ассоциативных правил, кластеризацию и т.д. Для решения этих задач можно использовать накопленные Internet технические документы. Организации собирают огромные объемы информации, автоматически создаваемой серверами и оседающей в журналах. Источниками информации являются также ссылочные журналы, в которых содержится информация для каждой страницы, на которую есть ссылка, журналы браузеров и регистрационные или анкетные данные пользователей, собранные CGI-сценариями.Основные потребители систем категории usage mining — организации, торгующие или предоставляющие услуги в Сети. Главными задачами для них являются персонификация наполнения страниц и оптимизация сайта с точки зрения упрощения навигации [1]. Также подобные системы представляют интерес для провайдеров Internet и сетевых администраторов. Основными областями применения в этом случае являются оптимизации работы сети, минимизация трафика и оптимизация предоставляемых услуг (например, интеллектуальное кэширование данных [2]).
Большинство традиционных систем мониторинга Сети предоставляют возможность фильтрации и получения статистической информации о пользователях. Подобный инструментарий помогает определять количество обращений к разным файлам и серверам, адреса отдельных пользователей, при этом такие системы рассчитаны на малый или ограниченный поток данных и редко предоставляют возможности анализа связи между обращениями к файлам и логикой их расположения. Рассмотрим инструменты, дающие аналитику более полную информацию.
Сбор информации
На каком участке взаимодействия пользователей и серверов собирать статистические данные? На сервере, на клиенте, на промежуточных участках сети?Сбор информации на уровне сервера представляет собой отбор информации непосредственно из журналов Web-сервера. Этот способ используется наиболее часто, поскольку без излишних накладных расходов можно получить достаточно полную картину работы пользователей с сервером. Кроме того, это один из немногих методов, для которого уже существуют заранее накопленные данные. Действительно, все или почти все серверы автоматически ведут журнализацию; при этом журналы, как правило, хранятся годами. Рассмотрим детально, какую именно информацию предоставляет журнал сервера, отвечающий требованиям стандарта Common Log Format (CLF).
Большинство современных Web-серверов (в том числе, Apache или IIS) предоставляют возможность администратору выбирать, какие поля должны включаться в журнал, а какие — нет. Самые распространенные из дополнительных полей, которые при добавлении к Common Log Format образуют так называемый Combined Log Format, таковы: обратившееся приложение; URL документа, с которого осуществлено обращение; значения cookies.
У журналов сервера есть и недостатки. Основным из них является неполнота информации. Обращения к сохраненным на каком-либо уровне страницам, например, у пользователя в локальном кэше, не заносятся в журнал сервера, так же в журналы сервера не попадают данные, пересылаемые с помощью метода POST. Альтернативный метод сбора данных на самом сервере — анализ на уровне пакетов. Таким образом можно анализировать на уровне отдельных запросов TCP/IP, но для накопления таких данных, как правило, требуется написание дополнительных программ. На уровне сервера можно собирать данные запросов, полученных через формы на страницах или после выполнения различных сценариев. Достаточно интересным может быть анализ выданных различным пользователям cookie; информация об этом также хранится на сервере.
Заманчиво собирать информацию о посещениях на уровне клиента. Один из способов — использование Java-программ, подгружаемых через страницы интересующего нас сервера; однако функциональность подобных приложений ограничена, кроме того, сам пользователь с помощью настроек своего браузера способен исключить или ограничить возможность подобного сбора информации. Вторым способом могло бы стать внесение изменений в программы для просмотра Сети. Но следует понимать, что вносить в журнал придется все сразу, поскольку если в будущем понадобится собирать данные по какому-либо новому параметру, то внести соответствующие изменения в браузеры всех клиентов будет почти невозможно. Также при таком подходе возникают две неразрешимые проблемы: во-первых, как правило, никто не хочет, чтобы его шаги протоколировались, а затем собранные данные куда-либо отсылались, а во-вторых, мало кто станет обновлять свое программное обеспечение из-за нужд третьей стороны, осуществляющей сбор данных. Таким образом, сбор информации на стороне клиента более любых других методов затрагивает проблему сохранения неприкосновенности личной жизни, и пока такие методики мало применимы. Тем не менее, на данный момент существует несколько систем, использующих подобный подход [3].
Анализ данных прокси-сервера [4] может предоставить информацию о характере просмотра Сети анонимной группы пользователей использующих один прокси-сервер. В случае создания специализированного программного обеспечения для прокси-серверов можно добиться некоторых преимуществ по сравнению со сбором на стороне сервера или клиента. Решается проблема со снижением быстродействия сервера; кроме того, достаточно просто можно осуществить подключение нового сайта к сбору статистики или обновление системы для взаимодействия с новыми версиями браузеров (не требуется обновление приложений клиента).
Как альтернативу сбору информации на стороне сервера или шлюза можно рассмотреть сбор данных на узлах сети. Во-первых, не всегда возможен доступ к журналам сервера, во-вторых, не всегда данные, собираемые на сервере, релевантны к решаемой задаче. Кроме того, добавление на сервер каких-либо программных средств сбора интересующей информации может быть невозможно, или может просто замедлить сервер, что крайне нежелательно. Выходом может служить размещение датчиков в узлах сети на подходе к серверу. В таком случае сервер разгружается от излишнего программного обеспечения. Очевидно, что работа ведется на уровне протоколов и, как правило, сбор идет на уровне пакетов TCP/IP.
Хорошим примером подобной системы служит Web Traffic Warehouse [5]. Создатели системы обнаружили, что расположение сборщика данных влияет на качество получаемых результатов. Вследствие асинхронного характера передачи данных по Сети входящий и исходящий трафики могут проходить по разным физическим каналам. Просматривая его в некоторой точке сети, можно увидеть только одну из сторон диалога. Чтобы этого избежать, система собирает данные непосредственно на уровне приложений. В будущем планируется использовать большее количество датчиков в сети. Тогда, получая, скажем, данные как от приложения, так и от клиента, можно получать дополнительные параметры (такие, как потеря и задержка пакетов). Кроме того, много коррелированных источников могут использовать для выявления точек потерь или задержек информации.
Коллекционирование всех пакетов позволяет получить подробные данные о сети — дополнительная информация извлекается из журналов приложений (межсетевые экраны, серверы и др.). Информация о состоянии сети может быть получена периодичным просмотром счетчиков непосредственно находящихся на сетевых элементах, имеющих SNMP-доступ к базе Management Information Base. Более детальные данные можно найти в полях данных, которые поддерживаются датчиками RMON, что расширяет возможности хранения данных большинства сетевых элементов. Совмещая множество источников данных, можно получать очень подробную картину.
Следует заметить, что независимо от места сбора информации, в полном потоке данных содержатся пароли, частная корреспонденция, тексты документов. Даже IP-адреса источника или получателя в некоторых случаях могут быть сочтены частной информацией, особенно с учетом того, что по адресу можно определить компьютер, с которого была произведена операция. Можно исключать из обработки подобные данные, но это приводит к потерям ценной информации. Разработчики должны выбирать подходящий компромисс. Например, желательно скрывать IP-адреса; при этом есть потребность определять вхождения на один сайт с разных компьютеров, для чего необходимо осуществлять проекции от истинных к зашифрованным адресам.
Подготовка данных
На этом этапе могут выполняться некоторые простые интеграционные задачи, например, совмещение нескольких журналов и отсев ненужных для решаемой задачи данных. Найденные ассоциации полезны только в том случае, если данные в журнале показывают точную картину доступа пользователей к сайту, иногда удаление записей о файлах с «неважными» суффиксами (jpg, gif, map и др.) может существенно очистить записи. Во многих случаях требуется также очистить записи от неудачных запросов (например, оставить только строки, в которых ответ сервера имеет код 200). Обычно также требуется отсекать запросы со стороны различных автоматических агентов (в частности, это агенты поисковых систем, служащие для создания индексов страниц и слов во внутренних базах данных, автоматические верификаторы ссылок и инструментарий для управления сайтом).Сходная, но гораздо более сложная проблема состоит в определении обращений, которые не заносятся в журнал, механизмы локального кэша или прокси-сервера искажают картину перемещений пользователей в Internet. Сейчас для преодоления этой проблемы используется метод cache bursting, однако он полностью нивелирует преимущества в скорости от использования локального кэша. Методы борьбы с этой проблемой используют топологию сайта и ссылочные журналы, вкупе с временной информацией для обнаружения пропущенных ссылок. Более-менее точную картину перемещений пользователя можно составить, только если пропуски страниц были единичными (например, если клиент использовал в своем браузере переход по журналу назад), в таком случае можно дополнять путь пользователя; эта проблема получила название «заполнение пути» (path completion).
После того как данные очищены, возникает задача разбиения журнала на различные сеансы различных пользователей. Для того чтобы однозначным образом различать обращения различных пользователей из рассмотренных выше полей журнала можно использовать IP-адрес, агент пользователя и адрес вызвавшего документа. Рассмотрим три основных типа спорных ситуаций для идентификации различных пользователей.
A. Один IP-адрес/много пользователей. Очень распространенная ситуация, возникает при использовании провайдером прокси-сервера, кроме этого, когда любому пользователю при установке связи с провайдером выделяется случайный адрес (очень характерно при связи по телефонной линии), два разных пользователя могут получить одинаковый адрес.
B. Много IP-адресов/один пользователь. Также весьма распространенный случай, возникает при динамическом выделении адресов провайдером. В некоторых случаях (широко известный пример — America Online) новый адрес выделяется пользователю при каждом новом обращении к странице. Для случаев A или B можно выделять различных пользователей, основываясь на типе браузера, и отслеживать путь пользователя за один сеанс, находя для каждого документа вызвавший его, и таким образом выделять отдельные сеансы, от входа на сайт до страницы, с которой не было перехода внутри сайта.
C. Один пользователь использует различные браузеры. В таком случае, если IP-адрес не дает достоверных данных, можно воспользоваться только двумя методами, описанными ниже, при этом надо учесть, что файлы cookie будут далеко не всегда корректно работать.
В любом из упомянутых случаев, если для идентификации не хватает данных журнала, можно использовать файлы cookie и уникальную регистрацию пользователей. У каждого из этих методов есть недостатки: пользователь может удалить файлы, находящиеся на его компьютере, а обязательная регистрация, помимо очевидных недостатков, не обязательно получает точные данные.
Другая важная задача — идентификация сеанса доступа. Перед тем как будет выполнен какой-либо анализ использования, необходимо разделить данные на логические части, представляющие разные сеансы или транзакции. Сеанс пользователя — весь набор использованных страничных ссылок, сделанных им за одно посещение сайта. Проблема определения сеансов сходна с определением отдельных пользователей.
Самым популярным методом решения этой проблемы является выделение сеансов использования по временному принципу, когда два последовательных обращения с одного адреса считаются принадлежащими одному сеансу, если перерыв между этими обращениями не превысил заданный порог [3,6]. Вторым широко используемым способом является поддержание «per session cookies» (на стороне пользователя хранятся данные, только от первого визита на страницу до выключения браузера; анализ этих данных позволяет отличить одно посещение пользователя от другого).
Транзакции отличаются от пользовательского сеанса тем, что в них могут входить от одной до всех страниц маршрута пользователя за одну или несколько сеансов, в зависимости от заданного условия. Основная задача разбиения работы пользователя на транзакции состоит в выделении групп семантически близких обращений одного пользователя, поэтому для разбиения могут использоваться и операция разбиения, и слияния. Таким образом, транзакция может быть меньше или больше, чем один сеанс. Опишем три различных подхода [7] к разбиению на транзакции.
A. Идентификация транзакций с учетом продолжительности посещений. Данный метод основывается на том, что время, проведенное пользователем на странице, зависит от важности этой страницы для пользователя. (Статистические данные показывают, что количество страниц, где пользователь провел определенное время, обратно экспоненциально зависит от этого времени.) Таким образом, если выбрать некоторую границу времени, то можно отделить страницы, которые интересны пользователю от остальных. Этот метод предлагает формулу для вычисления такого интервала, в зависимости от распределения посещений страниц с различными временными интервалами. Концом транзакции служит первая из страниц, время посещения которой превысило выбранный порог, а началом — первая страница после конца предыдущей.
B. Идентификация транзакций методом максимальной ссылочной глубины. В этом случае новая транзакция начинается с первой ссылки вперед (переход на страницу, которую данный пользователь еще не посещал). Конец транзакции — достижение наибольшей глубины, т.е. если пользователь вернулся на уже посещенную страницу.
C. Разбиение транзакций по временному принципу — перекликается с методом выделения сеансов, все посещения делятся на части продолжительностью не превышающие заданный порог. Независимое применение такого разбиения малооправданно, этот метод можно применять после одного из семантически ориентированных методов, для отсечения вырожденных транзакций, с помощью слияния транзакций, меньших порогового значения.
Статистический анализ
Как правило, по данным журнала сервера подсчитываются самая популярная страница, наибольшее количество посетителей за день, неделю, месяц, также могут быть выделены страницы, обращения к которым вызвали наибольшее количество ошибок. Можно применять статистический анализ к уже очищенному и разбитому на транзакции журналу. В этом случае функциональная полезность резко возрастает, появляется возможность подсчитывать статистические данные для продолжительности пребывания на различных страницах или длины транзакции. Конечно, сбор статистики не дает требуемой для методов извлечения знаний глубины, но любая система принятия решений предоставляет пользователю такого рода информацию, как потенциально интересную и полезную. В качестве удобного интерфейса анализа получаемых данных, часто используется OLAP [5, 8].Методы поиска схем
После идентификации отдельной транзакции аналитик может применить один из методов извлечения знаний из схемы доступа: анализ пути, нахождение ассоциативных правил и последовательностей образцов, кластеризация или классификация.Для анализа пути используются различные виды графов, так как граф представляет некоторое отношение, определенное на странице (или другом объекте). Самым распространенным является построение графа, соответствующее физической структуре сервера, при этом страницы являются узлами, а ссылки между ними — направленными ветвями. Также могут быть использованы графы, основанные на типах страниц, когда ребра представляют совпадения между страницами, или где ребрам соответствуют количества пользователей, переходящих с одной страницы на другую. Большая часть исследований, посвященных нахождению частых путей или последовательностей ссылок, проведена для графов отражающих физическую структуру. С помощью этой методики можно определять наиболее посещаемые пути в сети.
В связи с тем, что подобные базы транзакций содержат множество информации, обычно технологии поиска ориентируются только на записи, доступ к которым осуществлялся не менее определенного числа раз. Обнаружение этих правил для организаций, занятых в электронной коммерции, может помочь в разработке эффективного маркетинга. Также эта информации помогает при улучшении организации сетевого пространства.
Нахождение последовательностей образцов — обнаружение связи между различными операциями, происходящими на протяжении одного временного интервала. В серверных журналах транзакций каждое посещение клиента записывается с некоторым интервалом времени. Исследование временных отношений между различными данными, может иметь например следующие результаты: 30% клиентов после посещения исследуемого сервера, в течение 10 дней прошли на нем регистрацию.
Другой важный тип связанности данных, также обнаруживаемый при помощи этой методики — сходные временные последовательности. Например, нам может быть интересно найти общие характеристики у клиентов, обращавшихся к одному файлу в определенный период времени, или временной интервал, на протяжении которого интересующий нас файл чаще всего используется.
Обнаружение классификационных правил позволяет создать описание записей, принадлежащих к определенной группе в связи с общностью атрибутов. Это описание затем используется для классификации вновь добавляемых записей. При изучении использования сети можно разрабатывать описание для клиентов, обращавшихся к определенным файлам, используя имеющиеся для этих клиентов демографическую информацию или схемы доступа.
Кластерный анализ позволяет сгруппировать клиентов или данные, которые имеют сходные характеристики. Кластеризация информации о клиенте с данными в журналах может позволить разработать и осуществить ряд маркетинговых стратегий.
Кластеризация транзакций
Основной областью применения для кластер-анализа в Web usage mining, является персонификация наполнения страниц. Пользователь распределяется в одну из категорий, после чего соответствующим образом изменяется выводимая для данного пользователя информация [9]. Еще одной традиционной для кластеризации областью применения является поддержка принятия решений [5].В [10] кластеризация используется для автоматической модификации страниц. В данной работе особый интерес представляет выбор объекта кластеризации. Ее авторы предлагают не проводить разбиение по транзакциям. Отказ от традиционного подхода объясняется трудностями с выбором метрики, а также слишком большим количеством транзакций, относительно общего числа страниц. В этой работе используется метод ARHP. На первом этапе с помощью алгоритма нахождения ассоциативных правил выделяются группы страниц, к которым часто обращаются на протяжении одной транзакции. На втором полученные группы проецируются на ребра графа, и к графу применяется алгоритм кластеризации. При запросе пользователя, система размещает текущую транзакцию в один из заранее созданных кластеров. В зависимости от свойств данного кластера формируется результирующий список ссылок, интересных пользователю, который выводится на просматриваемой странице.
При применении кластеризации всегда требуется решить две различные проблемы: выбор метрики и выбор алгоритма. Основной проблемой при кластеризации транзакций является выбор метрики. По ряду причин классические евклидовы метрики оказываются неэффективными.
Можно попробовать сравнивать сеансы пользователей следующим образом. Поскольку количество страниц ограничено, представим все сессии как вектора одинаковой длины, где длина — общее количество анализируемых страниц, а значениями элементов будет Истина, если такая страница входит в сеансы — Ложь, если не входит. Используя подходящие методы кластеризации, при таком подходе можно добиться достаточно точных результатов (например, алгоритмы ROCK или CACTUS). Но при таком подходе теряется количество обращений к одной странице за время одной транзакции, также не учитывается последовательность посещения страниц.
Второй проблемой, сопряженной с выбором метрики, является нормализация транзакций. Достаточно часто приходится сравнивать между собой транзакции из двух-трех страниц, и транзакции длинной свыше 25 переходов. На данный момент работ, посвященных этой проблеме, нет. Следует отметить, что проблема нормализации данных отпадает при применении некоторых специальных метрик. Очень перспективно выглядит возможность изучения применимости для кластеризации транзакций метрики n-грамов, но на данный момент таких работ также нет.
Анализ полученных схем
OLAP является мощным инструментом для стратегического анализа баз данных. Показано, что анализ, требуемый при извлечении знаний из сети, сходен с проводимым в хранилищах данных. Хорошим примером применения OLAP в данной области является система WebLogMiner [10]. Работа данной системы напоминает многоуровневую базу данных.На первом уровне записи журналов очищаются и помещаются в реляционные таблицы. На втором уровне строится куб данных на основании выбранных атрибутов. В качестве атрибутов могут быть выбраны: пользователь, расположение пользователя, тип ресурса, время, затраченное на просмотр ресурса, дата, ответ сервера и т.д. На третьем — используется механизм OLAP, для изучения полученных данных экспертами. Для изучения можно запрашивать различные срезы куба данных. Например, можно получить статистику по всем запросам, по запросам от одного домена или от одного типа браузера. Можно получать информацию по различным пользовательским сессиям или временным отрезкам. На четвертом уровне используются методы data mining для предсказания, классификации и нахождения интересных закономерностей. Этот этап может предоставлять информацию, которую в силу различных причин не удалось обнаружить на предыдущем.
Визуализация является мощным инструментом для облегчения понимания различного рода задач. Еще в 1996 году была разработана система WebViz для визуализации образцов сетевого доступа. Система использует парадигму Web-пути, при которой наборы записей в журнале используются для извлечения последовательных наборов прохождения сети. WebViz позволяет аналитику обработать часть сети, отфильтровав неподходящую информацию по различным критериям, как-то, по именам серверов или по локальным адресам страниц. При этом сеть представлена как направленный, цикличный граф, в котором узлам соответствуют страницы и ребрам — переходы пользователей по ссылкам со страницы на страницу.
Заключение
Методы извлечения знаний из использования Internet, на данный момент, становятся все более популярными. Хорошим показателем может служить возросшее число научных публикаций за год; при этом, например, методы content mining, наоборот получают меньше внимания, чем раньше. На данный момент хорошо работающих систем позволяющих проводить точный анализ Сети, практически нет, а существующие плохо масштабируемы и мало эффективны. При этом в связи с резким ростом числа пользователей Сети, потребность рынка в подобных информационных системах крайне велика, но реализации мешает отсутствие готовых теоретических решений. Нет окончательного решения для целого ряда задач: идентификации пользователей, сохранения конфиденциальности, выбора метрики для пространства транзакций и т.д.Литература
- Alexandrin Popescul, Lyle Ungar, David Pennock, Steve Lawrence. "Probabilistic Models for Unified Collaborative and Content-Based Recommendation in Sparse-Data Environments", 17th Conference on Uncertainty in Artificial Intelligence, 2001, August 2-5.
- Francesco Bonchi, Fosca Giannotti, Giuseppe Manco, Mirco Nanni, Dino Pedreschi, Chiara Renso, Salvatore Ruggieri. "Data Mining for Intelligent Web Caching", 2001 December.
- Cyrus Shahabi, Farnoush Banaei-Kashani. "A Framework for Efficient and Anonymous Web Usage Mining Based on Client-Side Tracking", Department of Computer Science, Integrated Media Systems Center, University of Southern California, USA, 2001.
- Jason I. Hong, James A. Landay. "WebQuilt: A Framework for Capturing and Visualizing the Web Experience", Berkley, USA, 2001
- Chung-Min Chen, Munir Cochinwala, Claudio Petrone, Marc Pucci, Sunil Samtani, Patrizia Santa, Marco Mesiti. "Internet traffic Warehouse", Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, May 16-18, 2000, Dallas, Texas, USA.
- Birgit Hay, Geert Wets, Koen Vanhoof. "Clustering navigational patterns on a website using a Sequence alignment method", Limburg University center, Belgium. 2001.
- Robert Cooley, Bamshad Mobasher, Jaideep Srivastava. "Data Preparation for Mining World Wide Web Browsing Patterns", Knowledge and Information Systems. 1, 1999.
- Osmar R. Zaiane, Man Xin, Jiawei Han. "Discovering Web Access Patterns and Trends by Applying OLAP and Data Mining Technology on Web Logs", Advances in Digital Libraries, 1998.
- B. Mobasher, H. Dai, T. Luo, Y. Sun, J. Zhu. "Combining web usage and content mining for more effective personalization", In Proc. of the Intl. Conf. on ECommerce and Web Technologies (ECWeb), 2000.
- B. Mobasher, R. Cooley, J. Srivastava. "Creating adaptive web sites through usage-based clustering of urls", In IEEE Knowledge and Data Engineering Workshop (KDEX'99), 1999.
Андрей Щербина (Andrei.A.Scherbina@techsell.ru) — аспирант ИСП РАН (Москва).
CLF: минимальный набор полей, хранимых в журнале
- IP-адрес клиента.
- Идентификационный номер пользователя.
- Время обращения.
- Метод запроса HTTP (GET, POST и т.д.)
- Путь к запрашиваемому ресурсу.
- Использованный протокол.
- Ответ сервера (200 - "все хорошо", 404 - "ресурс не найден" и т.д.)
- Объем переданной информации.
Идея очистки состоит в удалении из рассмотрения всех тех объектов, к которым пользователь прямо не обращался при своем путешествии по сайту, сюда также попадают файлы сценариев или таблицы стилей. Иногда, пользователь явно запрашивает графические файлы, для таких случаев в программе очищающей журнал должна быть предусмотрена модификация фильтра.
***Техника обнаружения ассоциаций обычно применяется к базам данных транзакций, где каждой транзакции соответствуют несколько полей. В таком случае задача состоит в обнаружении всех взаимосвязей между наличием одних или отсутствием других полей в транзакции. В терминах использования сети это означает обнаружение связей между обращениями к различным файлам от одного клиента, например, 80% клиентов, запросивших файл sql.rar, также запросили sql.r00; 30% клиентов, обращавшихся за этим файлом, прошли регистрацию.