WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 ||

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

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

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

Понятие ассоциативных правил определено на пространстве транзакций. Транзакция на пространстве I – произвольный конечный набор элементов пространства I. Таким образом, пользовательская сессия является частным случаем транзакции на пространстве страниц веб-сайта. Ассоциативное правило на пространстве I = {i1,…,iN} - это предикат вида A => B, где A, B I и AB = 0. Тогда поддержка ассоциативного правила A=>B - это отношение общего числа транзакций, в которые входит набор A, к общему числу транзакций.

Достоверность правила A=>B определяется как отношение поддержки AB к поддержке A, то есть вероятность выполнения правила на множестве транзакций, содержащих основание импликации.

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

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

n M (P) = / Ki, где Ki количество элементов в i-ом кластере, Mi M i i=– количество уникальных правил в i-ом кластере. Для удобства использования, в дальнейшем для предлагаемой функции используется наименование «индекс различимости». Индекс различимости показывает насколько выражена уникальность каждого из кластеров. В ходе работы показана применимость этого метода и - 13 - хорошая наглядность при выборе оптимального разбиения пространства.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предлагаемая метрика Расстояние Редактирования Расстояние Манхэттена Расстояние редактирования с нормализацией на 0,Метрика применяется к каталогам второго уровня.

Все сессии нормализуются до наибольшей длины.

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Рисунок 2. Количество уникальных ассоциативных правил по кластерам.

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

Индекс M(P) для предлагаемой метрики 0,0,0,0,0,0,0,2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Количество кластеров Рисунок 3. Значения индекса различимости M(P) для кластеризации при помощи предлагаемой метрики.

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

Расстояние\Индекс Данна Разделения Беждека Энтропии Предлагаемая метрика 12 10 6 Расстояние редактирования 14 15 7 Расстояние Манхэттена 12 12 8 Расстояние редактирования с 9 9 4 нормализацией на 0,Расстояние редактирования на 16 8 8 пространстве каталогов Расстояние редактирования для нормализованных сессий Таблица 1. Оптимальное разбиение с точки зрения различных индексов.

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

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

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

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

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

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

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

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 proс. 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.

- 19 - 5. Andrei Scherbina, Sergey Kuznetsov. Clustering of Web Sessions Using Levenshtein Metric//Lecture Notes in Computer Science. – Springler 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.

Pages:     | 1 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»