Содержание к диссертации
Введение
1.1 Актуальность темы 3
1.2 Цель и задачи работы 3
1.3 Научная новизна 4
1.4 Практическая значимость 4
1.5 Апробация работы и публикации 5
1.6 Структура работы 5
1.7 Краткое содержание работы б
17.1 Предметная область 6
17.2 Предлагаемые решения 7
1.7.3 Обсуждение результатов 13
1.8 Основные выводы и результаты исследования 14
1.9 Список работ опубликованных по теме диссертации 15
2 Предметная область 16
2.1 Практическая значимость 16
2.2 Основные принципы анализа 19
2.3 Сбор информации 21
2.3.1 Сбор данных на уровне клиента 21
2.3.2 Сбор данных на уровне прокси-сервера 22
2.3.3 Сбор данных на узлах сети 22
2.3.4 Сбор данных на уровне сервера 23
2.3.5 Ограничения в сборе данных 24
2.4 Подготовка данных 25
2.5 Статистический анализ 25
2.6 Визуализация данных 27
2.7 Поиск ассоциативных правил и частых последовательностей 29
2.8 Алгоритмы кластеризации 31
2.9 Кластеризация пользовательских сессий 32
2.10 Верификация результатов анализа 35
2.11 Заключение 38
3 Предлагаемая методика 40
3.1 Выбор оптимальной метрики 41
3.1.1 Метрика Манхэттена 42
3.1.2 Метрика Левенштейна, Модификации метрики 42
3.1.3 Предлагаемая метрика 43
3.2 Выделение выбросов 45
3.3 Определение оптимального распределения 46
3.4 Структура прототипа 49
3.5 Модуль очистки данных 51
3.6 Модуль выделения сессий доступа 52
3.7 Модуль кластеризации 54
3.8 Модуль поиска ассоциативных правил 57
3.9 Выводы 59
4 Результаты и обсуждение 60
4.1 Тестовый набор , 60
4.2 Результаты кластеризации 61
4.2.1 Распределение пользователей по кластерам 62
4.2.2 Распределение страниц по кластерам 63
4.2.3 Распределение каталогов го кластерам 63
4.2.4 Распределение сессий различной длины по кластерам 65
4.2.5 Внутри кластерное и межкластерное расстояния бб
4.2.6 Количество выбросов 67
4.2.7 Ассоциативные правила 67
4.3 Сравнительный анализ предлагаемых методов 67
4.4 Статистические индексы разбиения 68
4.5 Индексы, основанные на характеристической функции 69
4.6 Индекс на основании количества уникальных правил 70
4.7 Обсуждение результатов 74
4.7.1 Алгоритмы кластеризации 74
4.7.2 Метрики 75
4.7.3 Определение лучшего разбиения 76
5 Выводы 78
6 Библиография (69 наименований)
- Практическая значимость
- Сбор данных на уровне клиента
- Метрика Левенштейна, Модификации метрики
- Распределение пользователей по кластерам
Введение к работе
1.1 Актуальность темы
На данный момент практически в любой области знания накоплены
огромные объёмы данных. Каждый день новые данные поступают в наше распоряжение, и их больше, чем можно просто просмотреть, не говоря уже об эффективном использовании для принятия решений. Очевидно, что такие объемы данных не поддаются эффективной обработке традиционными методами ручного анализа.
Интерес со стороны научно-технических и коммерческих организаций породил в начале 1990-х годов острую необходимость в разработке новых технологий и средств, которые могли бы автоматически переводить обрабатываемые данные в полезную информацию и знания. Технология Data mining (извлечение знаний) - один из результатов этих научных разработок.
На данный момент, отсутствуют полностью автоматизированные методики классификации пользователей Интернет. Существующие решения требует достаточно больших затрат времени со стороны эксперта на обучение системы, её настройку или контроль. Рост числа пользователей, объёма накопленных данных и экономического значения Интернет требует появления, независимых от экспертов, программных средств для поиска информации и получения данных об использовании определенных ресурсов.
В данной работе предлагается метод автоматической классификации пользователей Интернет, основанный на расстоянии редактирования. Создан прототип системы, обеспечивающий полную автоматизацию процесса классификации от очистки данных до контроля качества полученной классификации.
1.2 Цель и задачи работы
Целью работы является создание автономного программного средства, выполняющего классификацию пользователей произвольного Интернет-сайта. Для достижения этой цели были поставлены следующие задачи:
— разработка метода кластеризации, обеспечивающего разбиение пользователей по классам в зависимости от демонстрируемых ими линий поведения и предпочтений;
— разработка автоматизированного метода определения оптимального для данного набора данных разбиения по кластерам. Разбиение признаётся оптимальным, в случае если все полученные кластеры соответствуют существующим типам поведения пользователей;
— создание прототипа системы классификации, включающего все этапы анализа: от очистки данных до оценки результатов кластеризации;
— достижение высокой эффективности кластеризации. Целевое значение: не более двух часов на обработку данных за одни сутки (100 000 посещений).
1.3 Научная новизна
Научной новизной обладают следующие результаты работы:
— создана метрика на пространстве веб-сессий, основанная на расстоянии редактирования, В рамках работы проведено сравнительное тестирование на пространстве веб-сессий представленной метрики, метрики Манхэттена, расстояния редактирования, а также трёх дополнительных вариантов модификации расстояния редактирования. Представленная метрика обеспечивает на пространстве веб-сессий наилучшие результаты из протестированных методик;
— разработан метод оценки качества кластеризации, основанный на применении поиска ассоциативных правил.
1.4 Практическая значимость
Число пользователей Интернет растёт темпами, опережающими любые возможности ручного анализа. Оказывается невозможным применение классических методов анализа, требующих от эксперта формулирования гипотез или создания обучающих данных. При этом создание корректной классификации пользователей и основных моделей их поведения на сайте необходимо для улучшения наполнения сайта, размещения более эффективной рекламы, устранения ошибок в структуре сайта и обеспечения каждого пользователя тем наполнением, которое необходимо именно ему.
Разработанная методика позволяет осуществлять полностью автономную классификацию пользователей Интернет. Отсутствие необходимости в работе эксперта и линейная зависимость сложности метода от количества веб-сессий позволяет обрабатывать данные праю"ически любых объёмов. С учётом того, что используются данные серверных журналов, которые собираются практически для любого веб-ресурса, разработанная методика применима для анализа большинства веб-сайтов.
Реализованный прототип системы был использован для анализа журналов веб-ресурсов wvw.citforum.ru и www.slgla.ru. Получены классы пользователей этих сайтов, соответствующие наиболее популярным моделям поведения. Классы были определены автономно, все пользовательские сессии были распределены по соответствующим кластерам.
1.5 Апробация работы и публикации
По материалам диссертации опубликовано 7 работ. Основные положения работы докладывались на следующих семинарах и конференциях:
- Восемьдесят шестой семинар Московской Секции ACM SIGMOD, Москва, 2003.
- Конференция Spring Young Researcher s Colloquium on Database and Information Systems (SYRCoDIS 2004), Санкт-Петербург, 2004;
- Конференция Business Information Systems-2004, Познань, Польша, 2004.
- Конференция International Conference on Data Mining-2004, Лейпциг, Германия, 2004,
- Семинар "Современные сетевые технологии" под руководством д.ф.-м.н. профессора Васенина ВА, 2005.
1.6 Структура работы
Работа состоит из введения, трёх глав, заключения и списка литературы.
Объём диссертации составляет 87 страниц. Библиография включает 69 наименований.
Практическая значимость
Во второй главе представлены существующие методы анализа поведения пользователей Интернет. Отмечаются основные недостатки существующих систем и выделяются теоретические задачи, требующие разрешения.
Любое действие в Интернет достаточно точно протоколируется на всех уровнях: на сервере/ на промежуточных узлах, на компьютере пользователя. Анализ этих данных потенциально позволяет понять закономерности в поведении пользователей и оборудования. Методы автоматического изучения характеристик доступа пользователей к серверам включают изучение наиболее популярных путей посещения, нахождение ассоциативных правил, кластеризацию, классификацию.
Как сказано выше, организации собирают огромные объемы информации, автоматически создаваемой и оседающей в журналах на серверах- Сбор информации на уровне сервера представляет собой отбор информации непосредственно из журналов Web-сайта, которые хранятся на физическом сервере. Этот способ используется наиболее часто, поскольку предоставляет возможность без излишних накладных расходов получить достаточно полную картину работы пользователей со всеми сайтам находящимися на анализируемом сервере. Кроме того, это один из немногих методов, для которого уже существуют заранее накопленные данные. Действительно, все или почти все серверы автоматически ведут журнализацию для каждого из сайтов; при этом журналы, как правило, хранятся годами.
У журналов сервера есть недостатки, основным из которых является неполнота информации. На уровне сервера не отмечаются те запросы, которые не попали на сервер. Например, в журналах нет информации об обращениях к сохраненных у пользователя в локальном кэше страницах. Также в журналы сервера не попадают данные, пересылаемые с помощью метода POST, Несмотря на отмеченные недостатки, анализ серверных жураналов является наиболее распространенным методом анализа поведения пользователей. С учётом того, что анализ данных на уровне сервера позволяет вести работу с любым ресурсом в
Интернет и использовать уже накопленные данные, в представленной работе используется сбор данных именно на уровне сервера.
Кластерный анализ позволяет сгруппировать клиентов или данные, которые имеют сходные характеристики. Кластеризация информации о клиенте с данными в журналах может позволить разработать и осуществить различные маркетинговые стратегии. Основной областью применения для кластер-анализа в Интернет является персонификация наполнения страниц. Пользователь распределяется в одну из категорий, после чего соответствующим образом изменяется выводимая для данного пользователя информация.
Основной проблемой при кластеризации сессий является выбор метрики на этом пространстве. На данный момент существует ряд исследований, посвященных выбору оптимальной метрики, в частности применяются метрика Евклида, метрика Манхэттена, метрика Левенштейна или алгоритмы, основанные на использовании пространства страниц вместо пространства сессий.
Основной неразрешенной задачей является создание полностью автоматизированной методики. Так, для большинства методов кластеризации требуется подбор стартовых параметров и результирующего количества кластеров. При этом, если эксперт ошибается при выборе параметров, качество кластеризации сущеавенно ухудшается. Как правило, подбор параметров может быть частично автоматизирован, но всё равно требует длительного участия эксперта. Для оценки качества кластеризации с точки зрения семантики разбиения используются методы, требующие создания экспертом эталонного разбиения. Поэтому применение существующих методик не может быть автоматизировано.
В главе «Предлагаемая методика» представлены разработанные и опробованные в данной работе методы сравнения сессий и верификации результатов кластеризации. Для кластеризации пользовательских сессий в работе рассматривается возможность применения ранее известных методов двух видов: dbscan и метода К-центроидов.
Метод dbscan (Ester et al, 1996) имеет сложность 0(N2), где N - количество сессий. Для работы метода требуется выбор одного параметра Е, где Е - это расстояние между соседними элементами, при котором они считаются соседями. Алгоритм работы метода - последовательный перебор всех точек пространства и присоединение к каждой точке всех соседних для неё. Соседней считается точка входящая в Е-окресгность данной. Кластеры, образуемые в результате работы метода, представляют собой множество пересекающихся е-окрестносгей.
Принцип работы нечёткого метода К-цектроидов (Nasraoui et al, 2002) - это последовательная оптимизация разбиения. На каждой итерации метода происходит выбор новых центров кластеров. Выбор центров основан на минимизации функции, показывающей чёткость границ между кластерами. Далее каждый элемент пространства распределяется в кластер, центр которого является ближайшим. Кластеры, образуемые в результате работы метода, могут иметь границы сложной формы, при этом каждый из элементов входит в каждый из кластеров с определённой вероятностью. Сложность метода составляет O(N), где N - общее количество сессий. Невысокая сложность достигается за счёт того, что при выборе новых центров кластеров используются не все точки пространства, а только ограниченное константой количество представителей каждого из кластеров.
Выбор метрики на пространстве сессий представляет большую сложность. В данной работе изучается применимость метрики Манхэттена, метрики Левенштейна (расстояние редактирования), а также нескольких модификаций метрики Левенштейна. Все предложенные метрики были опробованы на тестовых данных с каждым из методов кластеризации.
Сбор данных на уровне клиента
Как альтернативу сбору информации на стороне сервера или шлюза можно рассмотреть сбор данных на узлах сети. Во-первых, не всегда возможен доступ к журналам сервера, во-вторых, не всегда данные, собираемые на сервере, релевантны к решаемой задаче. Кроме того, добавление на сервер каких-либо программных средств сбора интересующей информации может быть невозможно, или может просто замедлить сервер, что крайне нежелательно- Выходом может служить размещение датчиков в узлах сети на подходе к серверу, В таком случае сервер разгружается от излишнего программного обеспечения.
Хорошим примером системы, использующей сбор данных на узлах сети, служит Web Traffic Warehouse (Chen et al, 2000). Рассмотрим на её примере сложности и перспективы подобного подхода. Создатели системы обнаружили, что расположение сборщика данных влияет на качество получаемых результатов, В связи с асинхронной передачей данных по сети, входящий и исходящий трафик могут проходить по разным физическим каналам. Просматривая поток данных в некоторой точке сети, мы можем увидеть только одну из сторон диалога. Получая, например, данные и от приложения, и от клиента, можно отслеживать дополнительные параметры, такие, как потеря и задержка пакетов. Кроме этого, много коррелированных источников могут быть использованы для выявления точек потерь или задержек информации. Коллекционирование всех пакетов позволяет получить подробные данные о сети, дополнительная информация извлекается из журналов приложений (брандмауэры, серверы и др.).
Из вышеизложенного следует, что сбор данных на узлах сети позволяет получать максимально подробные данные по физическому функционированию сети. Для решения задач нахождения узких мест в сетевой конфигурации или предотвращения сбоев такая методика оптимальна. Данные методы плохо подходят для анализа именно пользовательского поведения, так как акцент в сборе данных делается на аспектах физического уровня работы сети. Реконструкция поведения конкретного пользователя, наоборот очень сложна, так как данные о его обращениях к веб-сайтам могут оседать на различных узлах сети.
Сбор информации на уровне сервера использует данные непосредственно из журналов Web-сервера. Этот способ используется наиболее часто, поскольку без излишних накладных расходов есть возможность получить достаточно полную картину работы пользователей с сайтов. Кроме того, это один из немногих методов, для которого уже существуют заранее накопленные данные. На данный момент, все или почти все серверы автоматически ведут журнализацию; при этом журналы, как правило, хранятся годами. На одном физическом сервере, как правило, размещается несколько веб-сайтов, поэтому одно программное средство может обеспечить анализ сразу нескольких сайтов.
У журналов сервера есть ряд недостатков, основным из которых является неполнота информации. Обращения к сохраненным на каком-либо уровне страницам, например, у пользователя в локальном кэше, не заносятся в журнал сервера, также в журналы сервера не попадают данные, пересылаемые с помощью метода POST. Также в серверных журналах часто содержатся записи обращений веб-пауков и прочий шум, не имеющий отношения к действиям пользователей Интернет.
Несмотря на существующие недостатки, сбор данных на стороне сервера является наиболее распространенным и эффективным методом анализа использования Интернет. С учётом того, что анализ данных на уровне сервера позволяет вести работу с любым ресурсом в Интернет и использовать уже накопленные данные, в представленной работе применяется сбор данных именно на уровне сервера.
Следует заметить, что вне зависимости от места сбора, в полном потоке данных содержатся пароли, частная корреспонденция, тексты документов. Даже IP адреса источника или получателя в некоторых случаях могут быть сочтены частной информацией, особенно с учетом того, что по адресу можно определить компьютер, с которого была произведена операция. Можно исключать из обработки подобные данные, но это приводит к потерям ценной информации. Разработчики должны выбирать подходящий компромисс. Например, желательно скрывать IP адреса. Если же при этом сіь потребность определять вхождения на один сайт с разных компьютеров, для этого необходимо осуществлять проекции от истинных к зашифрованным адресам.
Законодательством Евросоюза (Directive 95/46/ЕС) запрещена передача информации о пользователях для нужд третьей стороны без письменного согласия самих пользователей. Согласно директиве для анализа поведения пользователей требуется, чтобы данный анализ являлся необходимым для работы самого веб-ресурса. Также запрещается передача подобных данных за пределы Евросоюза, Таким образом, большую часть анализа требуется выполнять силами организации, которой принадлежит сервер, что вызывает потребность в переносимых, полностью автоматизированных и простых в использовании средствах анализа.
Метрика Левенштейна, Модификации метрики
Метрикой Левенштейна называется метрика, задаваемая как сумма весов операций по преобразованию одной строки во вторую. В данной работе применяется метрика, основанная на операциях вставки, удаления и замены символа. Для этого набора операций используются два расстояния: расстояние Левенштейна (добавление, замена или удаление символа имеют вес единицу) и расстояние редактирования (добавление или удаление символа имеют вес единицу, а замена символа - двойку), То есть varb: a b w{a, )=1, w(e,b)=l, w(a,b)=2, w(a,a)=0, где w - вес операции замены символа, Е - пустой символ.
Тестирование расстояния редактирования на пространстве пользовательских сессий показало преимущество данной метрики над традиционными метриками Минковского- Тем не менее результаты кластеризации были неоптимальны. В основном это объясняется отмеченными ранее недостатками метрики Левенштейна; некорректное сравнении строк разной длины и отсутствие перестановок. Для проверки эффективности подхода в целом и для получения наиболее точных результатов было предложено несколько несложных модификаций расстояния редактирования, призванных частично устранить отмеченные недостатки:
1. расстояние рассчитывается как стандартное расстояние редактирования, но для каждой лары совпавших символов расстояние уменьшается на 10%;
2. все страницы заменяются на те каталоги, в которых они находятся. Далее к изменённым сессиям применяется расстояние редактирования. Данная метрика позволяет достаточно эффективно анализировать сайты, в которых для каждого раздела представлено избыточное количество араниц. На таком сайте пользователи могут запрашивать различные страницы, но при этом посещать один и тот же раздел сайта;
3. стандартное расстояние редактирования с нормализацией данных. Все строки дополняются уникальными для каждой строки значениями вплоть до длины максимальной строки. С использованием такой нормализации значимость коротких сессий сокращается, так как расстояние между ними и длинными сессиями существенно возрастает.
На основании тестирования применимости различных вариантов метрики Левенштеина было сформулировано две гипотезы:
1- качество результатов может быть существенно улучшено за счёт самообучающихся методов;
2, качество результатов может быть значительно улучшено за счёт анализа содержания посещённых страниц и классификации страниц в зависимости от их семантики.
Для проверки гипотезы была разработана метрика, основанная на метрике Левенштеина. Основная идея метода состоит в изменении веса операции замены в зависимости от близости араниц. Так две страницы, находящиеся в одном каталоге, являются достаточно близкими (в случае если структура сайта выдержанна корректно). Страницы, находящиеся в двух различных каталогах, но относящиеся к одному каталогу первого уровня, не обязательно являются семантически близкими, но, тем не менее, достаточно близки по назначению и точно ближе, нежели две страницы из разных участков сайта.
Попарное сравнение страниц с применением методов семантического сравнения текстов могло дать более точные результаты, чем сравнение на основании только расположения страниц. Тем не менее, необходимо отметить, что подобные методы обладают очень невысокой производительностью, выделение всех ключевых слов и индексация содержимого сайта может занять ощутимое время. Кроме этого, различные главы в одной книге могут не иметь совпадающих ключевых слов и как следствие подобные методы сравнения не всегда точны. В данной работе использовался упрощенный метод сравнения страниц на основании их положения на сервере, так как, обладая высокой скоростью, метод демонстрирует очень хорошие результаты.
Лемма 1. Для предложенной модификации метрики Левенштейна выполняется правило треугольника.
Доказательство- Предположим, существуют точки пространства а,Ь,с, такие что для них не выполняется правило треугольника. То есть pa,b)+ р{Ь,с) р(а,с), где р - предлагаемое расстояние. Следовательно, наименьшая сумма веса операций переводящих а в с больше, чем сумма операций переводящих а в Ь, и затем b в с. Но это невозможно, так как а может быть переведено в с, последовательным преобразованием в b и затем в с. Таким образом, минимальная сумма операций для преобразования а в с должна быть больше, чем одна из сумм весов таких операций. Приходим к противоречию, следовательно первоначальное утверждение неверно. Что и требовалось доказать.
Распределение пользователей по кластерам
Следует учитывать, что уникальные идентификаторы не присваиваются отдельным пользователям, так как на изучаемых ресурсах не было регистрации. IP адрес не позволяет однозначно разделять пользователей, так как один адрес может принадлежать нескольким пользователям и наоборот. Тем не менее, с учётом указанных ограничений, точность разделения пользователей составляет не менее 80%.
По результатам кластеризации несложно подсчитать статистику распределения IP адресов по результирующим кластерам, В результате можно определить насколько часто пользователи встречаются только в одном кластере. Данный метод не позволяет оценить качество кластеризации, так как одни и те же пользователи редко возвращаются на сайт за анализируемый период. При этом, в целом, нельзя утверждать, что пользователь будет демонстрировать одну и ту же модель поведения при каждом посещении веб-сервера- Таким образом, принадлежность всех посещений одним пользователем веб-сайта строго одному кластеру не может служить характеристикой для оценки качества кластеризации.
Единственным автоматизированным методом проверки качества кластеризации на основании распределения пользователей по кластерам является проверка распределения автоматизированных агентов. Идея этого метода состоит в том, что пользовательское поведение отличается от поведения программных средств, следовательно все сессии созданные автоматизированным агентом, должны быть распределены в один кластер.
Распределение страниц по кластерам, показывает наиболее и наименее популярные страницы для каждого из кластеров. Для данных сайта citforum это распределение не поддаётся ручному анализу, так как количество отдельных страниц превышает 10 000.
В качестве альтернативы рассматриваются распределения не страниц, а каталогов, к которым принадлежат страницы. Также возможен анализ распределения наиболее посещаемых страниц, но на практике все эти страницы являются корневыми для различных каталогов сайта. На этом основании можно сделать вывод, что анализ наиболее посещаемых страниц не несёт существенно новых данных по сравнению с анализом непосредственно каталогов.
Распределение посещений страниц из разных каталогов более понятно для эксперта, так как содержит существенно меньше параметров. Ниже представлено распределение, полученное на данных сервера citforum с применением метода dbscan. Как видно на рисунке 5, каталоги (горизонтальная ось графика) распределены сравнительно равномерно по полученным крупным кластерам. На оси абсцисс отображены кластеры, для каждого кластера указано общее число элементов.
Распределение сессий различной длины для метрики на пространстве каталогов. На рисунках 7 и 8 можно увидеть, что при применении предлагаемой метрики все сессии длинной более 16 попалм в выбросы. При этом для метрика на пространстве каталогов распределение длин сессий более равномерное, Длинные сессии попали в несколько кластеров, На основании такого рода данных практически невозможно различить качественные и некачественные разбиения пространства. Ниже представлены более точные, статистические и семантические методы сравнения разбиений пространства,
Внутри кластерное и межкластерное расстояния применяются практически во всех известных методах статистической верификации данных. Основным недостатком этих методов является то, что они не учитывают специфики пространства веб-сессий. Индексы этой группы показывают, насколько компактны полученные кластеры, а также, насколько далеко кластеры отстоят друг от друга. Ножно отметить, что эти качества кластеров не связаны напрямую с теи, насколько хорошо кластеры отражают предпочтения пользователей,
В рамках работы использовались методы статистической верификации, так как они являются наиболее распространенным способом проверки качества кластеризации. Результаты проверки с помощью этих методов приводятся для
сравнения. Тем не менее, основные выводы по предпочтению той или иной метрики будут сделаны на основании других методов верификации.
В зависимости от применяемого метода кластеризации или функции расстояния может существенно меняться количество сессий, которые были отнесены к выбросам. В случаях, когда количество выбросов априори неизвестно, его достаточно сложно автоматически подсчитать. Поэтому, заранее неизвестно какое из разбиений: с большим или меньшим количеством выбросов является более удачным. Таким образом, количество выбросов в результирующем разбиении не рассматривается как способ оценки качества самого разбиения.
Как показано выше, основной идеей методики является подсчёт ассоциативных правил. По сравнению с другими существующими данными по результатам кластер-анализа ассоциативные правила обладают наибольшей семантической значимостью. Действительно, количество выбросов, диаметр отдельных кластеров или расстояние между ними, в принципе, не связаны с семантикой разбиения. Наличие тех или иных страниц или каталогов в разбиении является неплохой характеристикой для каждого из полученных кластеров, Тем не менее, нет методики определения различий между двумя различными разбиениями пространства, на основании размещения тех или иных страниц по этим кластерам.
При подсчёте уникальных ассоциативных правил есть возможность выделить однозначно лучшую кластеризацию. Так, наибольшее количество уникальных ассоциативных правил показывает наилучшее разбиение,
