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

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

УДК 681.3.06

№—-

Щербина Андрей Андреевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДА АВТОМАТИЧЕСКОЙ КЛАССИФИКАЦИИ ПОВЕДЕНИЯ ПОЛЬЗОВАТЕЛЕЙ ИНТЕРНЕТ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2007

003053156

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

доктор технических наук, профессор

Кузнецов Сергей Дмитриевич

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

Васенин Валерий Александрович

кандидат физико-математических наук, старший научный сотрудник Кулямин Виктор Вячеславович

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

Защита состоится «Vé» февраля 2007 г. в YS часов на заседании Диссертационного Совета Д.002.087.01 в Институте Системного Программирования РАН по адресу: 109004, Москва, ул. Б. Коммунистическая, д.25, конференц-зал.

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

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

Научный руководитель

Официальные оппоненты

Ученый секретарь

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

С. П. Прохоров

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

Актуальность темы

Число пользователей Интернет растёт темпами,

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

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

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

Цель и задачи работы

Целью работы является создание автономного

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

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

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

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

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

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

Научная новизна

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

работы:

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

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

Практическая значимость

Разработанная методика позволяет осуществлять

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

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

Апробация работы и публикации

По материалам диссертации опубликовано 7 работ.

Основные положения работы докладывались на следующих семинарах и конференциях:

Восемьдесят шестой семинар Московской Секции АСМ 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.

Структура работы

Работа состоит из введения, трёх глав, заключения, списка

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

Краткое содержание работы

Первая глава представляет собой введение в

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

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

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

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

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

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

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

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

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

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

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

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

Для применения метрики Евклида необходимо приведении пользовательских сессий к следующему виду: V, = Ь>1„.уП}}, V, £ Р, ] б {1,..М}, где N - количество пользовательских сессий, п - количество страниц на сайте.

{1, если ¡-ая страница входит в ]'-ую сессию.

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

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

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

метрики Левенштейна. Простейший набор операций состоит из замены символа, добавления символа и удаления символа.

Расстояние задаётся следующим рекуррентным соотношением, г (чич2) = О (т,п), где V1 - сессия длины т, ч2 - сессия длины п. Для 'I е{1,т>, ]е{1,п>. Далее задаются граничные условия:

0(1,0) = О0-1,О)+с1е1, стоимость удаления всех символов из VI О(0,з)= 0(0,>1)+т5, стоимость вставки всех символов из у2 в VI

ins - вес операции вставки символа.

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

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

Для расчета расстояния редактирования используются

следующие веса операций: Va,b: a*b ins(a)=l, del(a)=l,

subst(a,b)=2, subst(a,a)=0.

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

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

2. Все сессии дополняются уникальными для каждой сессии значениями вплоть до длины максимальной строки и

D(i-l,j) +del

D(i,j) =min

DC'-1/j"l) + subst (Vi(i), v2(j))

и

приводятся к единой длине. То есть, у(у1(...,уп) преобразуется в у(у1;..уп,уп+1,..ум), где М - максимальная длина сессии, у„+1 = .. = ум = а, где а - число уникальное для каждой сессии V. К этим сессиям применяется расстояние редактирования.

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

4. Расстояние редактирования, модифицируемое в зависимости от принадлежности страниц к одному и тому же каталогу. Каждая страница веб-сайта может быть представлена в виде сКгц/.../сИГ|2/р|. Где сНгц - каталог сайта высшего уровня, сИГ|2 - каталог в котором непосредственно находится страница р,. Тогда операция замены двух страниц Р1 и р2 имеет следующий вес. Для Урьр2: р!*р2, р1,р2 е{1,р>

{16, если сйг12 = сйг22, сйгп = сНга 21, если сйгц = сИг21,сйг12 * сИг22 30, если сПгц * ¿¡г21, сИг12 * сЛг22 Наименьшей вес имеет замена двух страниц, лежащих в одном каталоге. Данная метрика работает на тех сайтах, где сохраняется иерархическая структура каталогов, и они используются для упорядочивания информации.

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

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

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

Для оценки качества кластеризации традиционно используются различные методы статистической оценки качества полученных кластеров. В работе применен ряд известных методов статистической верификации данных: Индекс разделения, метрика Данна, Энтропия разделения, индекс Беждека (На1М е1 а1,2001).

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

Понятие ассоциативных правил определено на пространстве транзакций. Транзакция на пространстве I -произвольный конечный набор элементов пространства I. Таким образом, пользовательская сессия является частным случаем транзакции на пространстве страниц веб-сайта. Ассоциативное правило на пространстве I = - это

предикат вида А => В, где А, В с I и АпВ = 0. Тогда поддержка ассоциативного правила А=>В - это отношение общего числа транзакций, в которые входит набор А, к общему числу транзакций. Достоверность правила А=>В определяется как отношение поддержки АиВ к поддержке А, то есть вероятность выполнения правила на множестве транзакций, содержащих основание импликации.

Определение 1. Уникальное ассоциативное правило -правило, обладающее поддержкой более 20% и достоверностью более 65% только в одном из кластеров разбиения. При этом в остальных кластерах данное правило должно обладать меньшей поддержкой.

Определение 2. Определим индекс для проверки качества кластеризации. Пусть разбиение Р = {с,ис2..ис„}, где С: - набор кластеров, полностью покрывающих пространство пользовательских сессий. Определим функицю М(Р) для любого разбиения Р следующим образом:

М (Р) = ±м,1к„ где К, количество элементов в ¡-ом

■и

кластере, М, - количество уникальных правил в ¡-ом кластере. Для удобства использования, в дальнейшем для предлагаемой функции используется наименование «индекс различимости». Индекс различимости показывает насколько выражена

уникальность каждого из кластеров. В ходе работы показана применимость этого метода и хорошая наглядность при выборе оптимального разбиения пространства.

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

На рисунке 1 представлена принципиальная схема прототипа программного комплекса. Прототип разрабатывался с целью обеспечения тестирования всех этапов методики.

Рисунок 1. Схема прототипа системы.

В прототип системы входят следующие основные

компоненты:

1. Модуль очистки данных обеспечивает удаление нерелевантной информации и определение уникальных идентификаторов страниц.

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

3. В модуле кластеризации применяется один из методов кластер-анализа для разбиения сессий по классам.

4. Модуль статистической верификации обеспечивает дополнительный контроль выбора оптимальных параметров кластеризации. Статистическая верификация выполняется на каждом тестовом запуске. Таким образом есть возможность выделить параметры кластеризации, которые обеспечивают самые высокие показатели для статистических методов. Статистические методы верификации используются только в качестве контрольных значений, решение об оптимальном наборе параметров принимается на основании количества уникальных ассоциативных правил.

5. Модуль поиска ассоциативных правил служит для выделения ассоциативных правил в найденных кластерах. Из найденных ассоциативных правил выделяются уникальные для каждого из кластеров. На основании количества уникальных ассоциативных правил выбирается оптимальное разбиение для входного набора данных.

4. Результаты и обсуждение.

В главе «Результаты и обсуждение» представлены все использованные данные и результаты применения методики. Для проверки методики применялись данные из двух сайтов: информационного репозитория и поисковой системы. Были получены классы пользователей, характеризующие модели пользовательского поведения. Присутствие данных из нескольких источников позволило оценить применимость метода для анализа групп пользователей, решающих различные прикладные задачи. Для выбора оптимальных результатов и определения оптимальной методики кластеризации применялись методы статической и семантической верификации разбиения. Ниже представлены результаты полученные при анализе журналов информационного репозитория www.citforum.ru.

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

В Предлагаемая метрика Т Расстояние Редактирования . РасстпяниЕ Манхаттана

'.1 Расстояние редактирования с нормализацией на С.9 щУетрикэ применяется к каталогам второго у со у к? О Все сессии нормализуются до наибольшей длины.

та —— - ------_----—

» в

3 А 5 6 7 0 9 10 И 12 1Э » 15 1А 17 1Я

Рисунок 2. Количество уникальных ассоциативных правил по кластерам.

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

Индекс М(Р) для предлагаемой метрики

Количество кластеров

Рисунок 3. Значения индекса различимости М(Р) для кластеризации при помощи предлагаемой метрики.

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

Рассгояние\Индекс Данна Разделения Беждека Энтропии

Предлагаемая метрика 12 10 6 12

Расстояние редактирования 14 15 7 7

Расстояние Манхэттена 12 12 8 8

Расстояние редактирования с нормализацией на 0,9 9 9 4 13

Расстояние редактирования на пространстве каталогов 16 8 8 8

Расстояние редактирования для нормализованных сессий 2

Таблица 1. Оптимальное разбиение с точки зрения различных индексов.

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

Прототип выполнялся на системе с процессором AMD Athlon 2500+ с 768 Мб оперативной памяти. Выполнение всего процесса от очистки данных до верификации результатов кластеризации для данных сайта www.citforum.ru за один день (92 ООО посещений или 9 ООО сессий) требует 15 минут. В связи с тем, что предлагаемое решение обладает сравнительно невысокой вычислительной сложностью O(N), где N - количество отдельных сессий в исходных данных, разработка распределённого решения не выполнялась. Можно

отметить, что для анализа серверных журналов использование распределённых методов представляет скорее теоретический интерес, так как для анализа дневного журнала допустимо время выполнения до 2-х часов. Таким образом, объём данных может быть увеличен до 700 ООО посещений или 72 ООО сессий в день. Для сравнения, самые крупные ресурсы в российской части Интернет имеют до 200 ООО посещений в день.

Основные выводы и результаты исследования

В рамках работы получены следующие результаты:

1. Разработан и апробирован метод сравнения сессий пользовательского доступа к веб-сайту. Основные достоинства предложенного метода состоят в следующем:

— предложенное расстояние обеспечивает корректное сравнение сессий пользовательского доступа за счёт использования данных о последовательности посещения страниц и их размещения на сайте;

— применение метода не требует предварительной индексации или обработки самих страниц сайта.

2. Разработан и апробирован метод автоматической верификации результатов кластеризации пользовательских сессий. Основные особенности предложенного метода верификации результатов кластеризации:

— метод определяет качество разбиения сессий по кластерам в зависимости от наличия уникальных ассоциативных правил;

— метод выявляет семантические отношения, характерные для каждого из кластеров.

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

Список работ опубликованных по теме диссертации

1. Щербина А.А. Основы извлечения знаний из Internet// Открытые системы. - 2003. - № 04. - стр. 49-53.

2. Scherbina A. The User Access to Web-Server Behavior Patterns Classification Method: In proc. of 6th Open German-Russian Workshop "Pattern Recognition and Image Understanding". - Novosibirsk. - 2003. - pages 238-241.

3. Scherbina A. Application of Levenstein Metric to Web Usage Mining: In proc. of 7th International Conference on Business Information Systems. - Poznan. - 2004. - pages 363-369.

4. A. A. Shcherbina. Classification Method For User Access to a Web Server//Pattern recognition and Image Analysis. -MAIK. - 2004. - Vol. 14. - No. 2. - pages 317-323.

5. Andrei Scherbina, Sergey Kuznetsov. Clustering of Web Sessions Using Levenshtein Metric//Lecture Notes in Computer Science. - Springier Verlag. - Volume 3275. - Nov 2004.-pages 127-133.

6. Andrei Scherbina. Clustering of Web Access Sessions: Proceeding of the Spring Young Researcher's Colloquium on Database and Information Systems (SYRCoDIS'2004). -Saint-Petersburg. - 2004. - pages 53-56.

7. Andrei Scherbina. The Cluster Validation Based on the Sequential Patterns: Proceeding of the Spring Young

Researcher's Colloquium on Database and Information Systems (SYRCoDIS'2005). - Volume B. - Saint-Petersburg. -2005. - pages 5-8.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от-01.12.99 г. Подписано к печати 10.01.2007 г. Формат 60x90 1/16. Усл.печ.л. 1,25. Тираж 80 экз. Заказ 006. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение.

1.1 Аюуальность темы.

1.2 Цель и задачи работы.

1.3 Научная новизна.

1.4 Практическая значимость.

1.5 Апробация работы и публикации.

1.6 Структура работы.

1.7 Краткое содержание работы.

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

1.7.2 Предлагаемые решения.

1.7.3 Обсуждение результатов.

1.1 Актуальность темы

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

Интерес со стороны научно-технических и коммерческих организаций породил в начале 1990-х годов острую необходимость в разработке новых технологий и средств, которые могли бы автоматически переводить обрабатываемые данные в полезную информацию и знания. Технология Data mining (извлечение знаний) - один из результатов этих научных разработок.

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

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

5 Выводы

В ходе работы получены более чем 200 разбиений данных. В ходе тестирования были выявлены следующие закономерности: результаты кластеризации (количество и состав кластеров) существенно зависят от метрики и алгоритма; для определения оптимального разбиения эффективно применение предлагаемого метода подсчёта ассоциативных правил; предложенный индекс, основанный на подсчете ассоциативных правил, позволяет однозначно определить оптимальное количество кластеров или значения входных параметров метода.

Оптимальные результаты демонстрирует применение предлагаемой метрики, основанной на структуре каталогов веб-сайта.

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

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

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

Все предлагаемые методы были реализованы в программном комплексе, обеспечивающем кластеризацию пользовательских сессий. Можно отметить следующие возможные пути развития данной работы: интеграция прототипа в систему динамического изменения наполнения страниц; организация параллельного вычисления и обработки данных о поведение пользователей; улучшение методики поиска ассоциативных правил. Поиск ассоциативных правил может вестись для более длинных последовательностей в три-четыре и более страниц. В рамках данной работы, подсчитывались последовательности из двух страниц, которые могут встречаться в любой точке сессии; на основании найденных наиболее популярных последовательностей возможна генерация портретов кластеров (какие последовательности характеризуют данный кластер); внедрение самообучающейся методики определения весов операций замены для оптимизации результатов кластеризации для каждого набора данных.

2 Agrawal et al, 1993

3 Agrawal et al, 1994

4 Agrawal et al, 1995

5 Barford et al 1998

1. Agrawal, J.C. Shafer: "Parallel Mining of

2. Association Rules", IEEE Transactions on Knowledge and Data Engineering, Vul. 8, No. 6, December 1996.

3. Dieberger and Lonnqvist, 200017 Directive 95/46/EC18 Ester et al, 1996

4. Ed Huai-hsin Chi, Adam Rosien, Jeffrey Heer: Lumberjack: Intelligent Discovery and Analysis of Web User Traffic Composition. WEBKDD 2002: 1-16http://www.w3.org/Daemon/User/Config/Loggin g.html

5. U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, Advances in Knowledge Discovery and Data Mining, AMI Press/MIT Press, 1996.

6. Ginsburg, Fenstermacher, K. D. and Ginsburg, M. 2003.

7. Koschke and Eisenbarth, 200038 Krane and Langdon, 200539 Levene and Loizou, 1999

8. Heer, J. and Chi, E.H. Mining the Structure of User Activity using Cluster Stability, in Proceedings of the Workshop on Web Analytics, SIAM Conference on Data Mining (Arlington VA, April 2002).

9. Hong, J.I., J. Heer, S. Waterson, and J.A. Landay, WebQuilt: A Proxy-based Approach to Remote Web Usability Testing, ACM Transactions on Information Systems, 2001, 19(3): pp. 263285.

10. Joshi, A., Joshi, K., Krishnapuram, R., On mining Web Access Logs, in Proceedings of the ACM-SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2000, pp. 6369

11. Kerkhofs J., Vanhoof K., Pannemans D.- Web usage mining on proxy servers: a case study.-In: Proceedings of Data Mining for Marketing Applications Workshop at ECML/PKDD 2001, September 3-7 2001, Freiburg (Germany), s.l., 2001

12. Y. S. Maarek, Z. Ben Shaul. «Automatically Organizing Bookmarks per Contents.» In proc. of Fifth International World Wide Web Conference 1996, Paris, France

13. Pazzani, M., Muramatsu, J. & Billsus, D., Syskill & webert: Identifying interesting web sites, in 'AAI Spring Symposium on Machine Learning in Information Access'. Lecture Notes in Computer Science 11,1996

14. Pirolli, P. L. and Pitkow, J. E. Distributions of surfers' paths through the World Wide Web: Empirical characterizations. World Wide Web 2, 1-2 (Jan. 1999), 29-45.

15. James E. Pitkow, Krishna A. Bharat. «Webviz: A Tool For World-Wide Web Access Log Analysis.» Graphics. 1994.

16. Alexandrin Popescul, Lyle Ungar, David Pennock, Steve Lawrence. «Probabilistic Models for Unified Collaborative and Content-Based

17. Shahabi, Banaei-Kashani, 200161 Spiliopoulou et al, 199962 Wang and Zaiane, 200263 Wang et al, 199764 Wang et al, 200565 Weiss et al, 199666 Xie and Beni, 199167 Zaiane et al 1998).

18. Santosh K. Rangarajan, Vir V. Phoha, Kiran S. Balagani, Rastko R.Selmic, S.S. Iyengar. "Adaptive Neural Network Clustering of Web Users," Computer, vol. 37, no. 4, pp. 34-40, April, 2004

19. T.A. Runkler and J.C. Bezdek, "Web mining with relational clustering.", International Journal of Approximate Reasoning, Vol. 32 (2-3), 2003, pp. 217-236

20. Myra Spiliopoulou, Carsten Pohle, Lukas Faulstich. «Improving the Effectiveness of a Web Site with Web Usage Mining.» WEBKDD, crp. 142-162, 1999.

21. Wang, W. and Zaiane, 0. R. 2002. Clustering Web Sessions by Sequence Alignment. In Proceedings of the 13th international Workshop on Database and Expert Systems Applications (September 02 06, 2002). DEXA. IEEE Computer Society, Washington, DC, 394-398.

22. X. L. Xie and G. A. Beni, "A validity measure for fuzzy clustering," IEEE Trans, on Pattern Analysis and Machine Intelligence, vol. 3, no. 8, pp. 841 846, 1991.