На правах рукописи

УДК 681.3.06 Щербина Андрей Андреевич ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДА АВТОМАТИЧЕСКОЙ КЛАССИФИКАЦИИ ПОВЕДЕНИЯ ПОЛЬЗОВАТЕЛЕЙ ИНТЕРНЕТ Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2007

Работа выполнена в Институте Системного Программирования Российской Академии Наук.

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

Ведущая организация: Вычислительный центр имени А.А.

Дородницына Российской Академии Наук.

Защита состоится л16 февраля 2007 г. в 15-00 часов на заседании Диссертационного Совета Д.002.087.01 в Институте Системного Программирования РАН по адресу: 109004, Москва, ул. Б.

Коммунистическая, д.25, конференц-зал.

С диссертацией можно ознакомиться в библиотеке Института Системного Программирования РАН.

Автореферат разослан л_ января 2007 г.

Ученый секретарь диссертационного совета Д.002.087.0 института системного программирования РАН кандидат физико-математических наук С. П. Прохоров - 3 -

Общая характеристика работы

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

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

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

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

Для достижения этой цели были поставлены следующие задачи:

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

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

создание прототипа системы классификации, выполняющего все этапы анализа: от очистки данных до оценки результатов кластеризации;

достижение высокой эффективности кластеризации. Целевое значение: не более двух часов на обработку данных за одни сутки (100 000 посещений).

Научная новизна Научной новизной обладают следующие результаты работы:

предложена метрика на пространстве веб-сессий, основанная на расстоянии редактирования. В рамках работы проведено сравнительное тестирование метрики Евклида, расстояния редактирования, а также четырёх вариантов модификации расстояния редактирования. Среди протестированных расстояний разработанная метрика обеспечивает на пространстве веб-сессий наиболее адекватные результаты кластеризации;

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

- 5 - Практическая значимость Разработанная методика позволяет осуществлять полностью автономную классификацию пользователей Интернет. Отсутствие необходимости в работе эксперта и линейная зависимость сложности используемых алгоритмов от количества веб-сессий позволяет обрабатывать данные практически любых объёмов. С учётом того, что используются данные серверных журналов, которые собираются для каждого веб-ресурса, разработанная методика применима для анализа большинства веб-сайтов.

Реализованный прототип системы был использован для анализа журналов веб-ресурсов www.citforum.ru и www.sigla.ru. С помощью прототипа были получены классы пользователей этих сайтов, соответствующие наиболее популярным моделям поведения.

Апробация работы и публикации По материалам диссертации опубликовано 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.

- 6 - Структура работы Работа состоит из введения, трёх глав, заключения, списка литературы и приложения. Объём диссертации составляет 87 страниц, в том числе 13 рисунков, 3 таблицы. Библиография включает наименований.

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

2. Предметная область.

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

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

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

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

3. Предлагаемая методика.

В главе Предлагаемая методика представлены разработанные и опробованные в данной работе методы сравнения сессий и верификации результатов кластеризации. Для кластеризации пользовательских сессий в работе рассматривается возможность применения ранее известных методов двух видов: dbscan и метода Кцентроидов.

Метод dbscan (Ester et al, 1996) имеет сложность O(N2), где N - количество сессий. Для работы метода требуется выбор одного параметра, где - это расстояние между соседними элементами, при котором они считаются соседями. Алгоритм работы метода - - 8 - последовательный перебор всех точек пространства и присоединение к каждой точке всех соседних для неё. Соседней считается точка входящая в -окрестность данной. Кластеры, образуемые в результате работы метода, представляют собой множество пересекающихся окрестностей.

Принцип работы нечёткого метода К-центроидов (Nasraoui et al, 2002) - это последовательная оптимизация разбиения. На каждой итерации метода происходит выбор новых центров кластеров. Выбор центров основан на минимизации функции, показывающей чёткость границ между кластерами. Далее каждый элемент пространства распределяется в кластер, центр которого является ближайшим.

Кластеры, образуемые в результате работы метода, могут иметь границы сложной формы, при этом каждый из элементов входит в каждый из кластеров с определённой вероятностью. Сложность метода составляет O(N), где N - общее количество сессий. Невысокая сложность достигается за счёт того, что при выборе новых центров кластеров используются не все точки пространства, а только ограниченное константой количество представителей каждого из кластеров.

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

Для применения метрики Евклида необходимо приведении пользовательских сессий к следующему виду:

vj = {v1j,..vnj}, vj P, j {1,..N}, где N - количество пользовательских сессий, n - количество страниц на сайте.

- 9 - 1, если i-ая страница входит в j-ую сессию.

vij ={ 0, если i-ая страница не входит в j-ую сессию.

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

Рассмотрим группу расстояний, основанных на принципе попарного сравнения символов в двух строках. При этом, расстоянием между двумя строками является минимальная сумма весов операций, требующихся для перевода одной строки во вторую. Эта методика была предложена В.И. Левенштейном и расстояния этой группы известны как метрики Левенштейна. Простейший набор операций состоит из замены символа, добавления символа и удаления символа.

Расстояние задаётся следующим рекуррентным соотношением. r (v1,v2) = D (m,n), где v1 - сессия длины m, v2 - сессия длины n. Для i {1,m}, j {1,n}. Далее задаются граничные условия:

D(i,0) = D(i-1,0)+del, стоимость удаления всех символов из vD(0,j)= D(0,j-1)+ins, стоимость вставки всех символов из v2 в vD(i-1,j) +del D(i,j) =min D(i,j-1) +ins { D(i-1,j-1) + subst (v1(i), v2(j)) ins - вес операции вставки символа.

del - вес операции удаления символа.

Subst(a,b) - вес операции замены символа a на b.

Для расчета расстояния редактирования используются следующие веса операций: a,b: ab ins(a)=1, del(a)=1, subst(a,b)=2, subst(a,a)=0.

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

- 10 - 1. Расстояние рассчитывается как стандартное расстояние редактирования. Полученное расстояние уменьшается на 10% за каждую выполненную операцию subst(a,a). Таким образом, дополнительно уменьшается расстояние между двумя строками, в которых большое количество совпадающих символов.

2. Все сессии дополняются уникальными для каждой сессии значениями вплоть до длины максимальной строки и приводятся к единой длине. То есть, v(v1,Е,vn) преобразуется в v(v1,..vn,vn+1,..vM), где M - максимальная длина сессии, vn+1 =.. = vM =, где - число уникальное для каждой сессии v. К этим сессиям применяется расстояние редактирования.

3. Все страницы в сессиях заменяются на каталоги, в которых они находятся. К исправленным сессиям применяется расстояние редактирования. Происходит сравнение не посещенных страниц, а посещенных каталогов сайта.

4. Расстояние редактирования, модифицируемое в зависимости от принадлежности страниц к одному и тому же каталогу. Каждая страница веб-сайта может быть представлена в виде diri1/Е/diri2/pi. Где diri1 - каталог сайта высшего уровня, diri2 - каталог в котором непосредственно находится страница pi. Тогда операция замены двух страниц p1 и p2 имеет следующий вес. Для p1,p2 : p1p2, p1,p2 {1,p} 16, если dir12 = dir22, dir11 = dirSubst (p1,p2) = 21, если dir11 = dir21, dir12 dir{ 30, если dir11 dir21, dir12 dirНаименьшей вес имеет замена двух страниц, лежащих в одном каталоге. Данная метрика работает на тех сайтах, где сохраняется иерархическая структура каталогов, и они используются для упорядочивания информации.

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

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