Содержание


Прогнозирование запросов web-контента с использованием R и InfoSphere Streams

Comments

Log-файлы web-серверов можно использовать для изучения поведения посетителей web-сайтов. Например, в статье Predicting Web Users' Next Access Based on Log Data Ритупарна Сен (Rituparna Sen) и Марк Хансен (Mark Hansen) использовали сочетание марковских моделей первого порядка для обнаружения кластеров страниц на web-сайте. Они применяли эти модели для прогнозирования того, какими, вероятнее всего, будут следующие страницы, запрашиваемые пользователями. Авторы статьи предложили использовать эту информацию для предварительной выборки ресурса, до того как пользователь его запросит. В данной статье рассказывается о том, как использовать IBM InfoSphere Streams и R для выполнения похожего анализа log-файлов web-серверов.

Предлагаемое решение использует расширяемые марковские модели (extensible Markov models, EMM), которые ввели Маргарет Данэм (Margaret Dunham), Ю Менг (Yu Meng) и Джи Хуанг (Jie Huang) в 2004 году, чтобы соединить алгоритм потоковой кластеризации с марковской цепью. Марковская цепь— это математическая система, которая выполняет переходы от одного состояния в другое, при этом следующее состояние зависит только от текущего состояния, а не от последовательности предшествовавших событий.

Состояния марковской цепи являются кластерами, определяемыми алгоритмом потоковой кластеризации. Модель EMM может меняться со временем, добавляя новые состояния по мере их появления и ослабляя или сокращая существующие состояния. Таким образом, модель может адаптироваться к изменениям с течением времени. Такая способность особенно важна в системах, имеющих динамичные модели использования, которые меняются за короткие промежутки времени. Например, для web-сайта, скорее всего, характерны динамичные модели использования, а также структурные изменения с течением времени.

В этой статье демонстрируется применение EMM для прогнозирования запросов контента пользователями web-сайта. Статья описывает, как использовать log-файлы сервера для обучения и тестирования модели, как применять модель для прогнозирования поведения посетителей и как использовать InfoSphere Streams и R для выполнения прогнозирования на основе этой модели. InfoSphere Streams предлагает среду исполнения, а R обеспечивает моделирование и прогнозирование. Модель EMM основывается на библиотеке rEMM, созданной Майклом Хаслером (Michael Hahsler) и Маргарет Данэм.

Преимущества интеграции InfoSphere Streams и R с использованием инструментария R-project Toolkit

Большинство моделей машинного обучения, используемых для прогнозирования, обучаются в автономном режиме на больших наборах обучающих данных. После завершения обучения прогнозирование обычно выполняется в режиме реального времени. Этот метод подходит для множества классов задач, но если прогнозируемые элементы часто меняются, то такой подход может генерировать модели, отстающие от систем, которые они пытаются прогнозировать. Поскольку модели EMM могут обучаться динамически, они полезны для моделирования таких систем, как сетевой трафик, движение автомобилей и многих других систем, где модели кластеризации могут меняться с течением времени. Трафик web-сервера — одна из таких областей. Log-файл сервера предлагает бесконечный источник потоковых данных для обучения модели, в то время как система делает прогнозы.

Прогнозирование запросов контента на основе log-файлов сервера

Web-серверы хранят информацию о запрашиваемых ресурсах в log-файлах. Каждая запись в log-файле содержит IP-адрес инициатора запроса, метку времени запроса и расположение запрашиваемого элемента. В таблице 1 показаны три примера записей из log-файла сервера. Эти записи содержат один и тот же IP-адрес и три разных запрошенных элемента (два изображения и HTML-документ). Записи представляют посещение (или часть посещения) web-сайта.

Таблица 1. Пример записей в log-файле сервера
IP-адресИмя пользователя и т.д.Метка времениЗапрос доступаКод статусаКоличество переданных байтов
123.123.123.123- -[26/Apr/2000:00:23:45 -0400]"GET /pics/wpaper.gif HTTP/1.0"2006248
123.123.123.123- -[26/Apr/2000:00:23:48 -0400]"GET /index.html HTTP/1.0"2008130
123.123.123.123- -[26/Apr/2000:00:23:50 -0400]"GET /pics/5star2000.gif HTTP/1.0"2004005

Подробное описание решения

Целью этого проекта является моделирование переходов пользователей по web-сайтам. Для данной упрощенной модели каждый запрошенный элемент контента — это состояние в модели EMM. Более сложная модель может обеспечивать кластеризацию групп элементов контента. Вероятность перехода между состояниями определяется наблюдением количества пользователей, которые запрашивают страницу B после запроса страницы A. Помимо каждого из элементов контента модель включает состояние «вне сайта». Переход от состояния «вне сайта» означает, что пользователь начинает посещение (переходя к первому запрошенному ресурсу на этом web-сайте). Переход к состоянию «вне сайта» означает, что пользователь завершил посещение (перестал запрашивать ресурсы с этого web-сайта).

В листинге 1 представлен основной код для приложения на языке Streams Processing Language (SPL). Приложение включает пять операторов, перечисленных в порядке появления в конвейере:

  • Оператор FileSource— считывает построчно входной log-файл и возвращает каждую строку как кортеж с одним элементом. Каждая строка анализируется с использованием оператора RScript.
  • Первый оператор RScript— вызывает сценарий R. Сценарий R анализирует IP-адрес инициатора запроса и запрошенный элемент. Этот сценарий также анализирует запись log-файла для определения ее релевантности (соответствия оговоренным ранее условиям).
  • Оператор Filter— отфильтровывает все кортежи, помеченные для фильтрации процедурой анализа R. Оставшиеся кортежи передаются второму оператору RScript.
  • Второй оператор RScript— передает путь запрошенного элемента в сценарий R, который использует его для создания прогноза, содержащего список из 20 элементов контента, которые вероятнее всего будут запрошены на следующем шаге. Итоговый прогноз упаковывается в кортеж, вместе с IP-адресом инициатора запроса и запрошенным элементом контента.
  • Оператор FileSink— записывает входящие кортежи в выходной файл.
Листинг 1. SPL-код, определяющий граф приложения
composite Main {
  graph
    // считывание записей из log-файла
    stream<rstring line> 
    inStream = FileSource() {
      param  file : "../data/first-100-test-log.txt";
    } 
 
    // анализ строки с использованием сценария R
    stream<rstring origin, rstring path> 
    parsedStream = RScript(inStream) {
      param
        initializationScriptFileName : "../rsrc/parse-functions.R";
        rScriptFileName : "../rsrc/parse.R";
        streamAttributes : line;
        rObjects : "log.entry"; 

      output
        parsedStream: origin = fromR("origin"),
                      path = fromR("path");
    }

    // фильтрация некорректных кортежей:
    stream<rstring origin, rstring path>
    filteredStream = Filter(parsedStream) {
      param filter : origin != "filter me";
    }

    // вызов сценария r, который создаст прогноз
    stream<rstring origin, rstring path, list<rstring> prediction> 
    analyzedStream = RScript(filteredStream) {
      param
        initializationScriptFileName : "../rsrc/init_predict.R";
        rScriptFileName : "../rsrc/predict.R";
        streamAttributes : path;
        rObjects : "path";
          
      output
        analyzedStream:
          prediction = fromR("prediction");
    }

    // отправка результатов в файл
    () as dbg = FileSink(analyzedStream) {
      param
        format : csv;
        file   : "result.txt" ;   
    }
}

Листинг 2 содержит функции R, используемые в анализе записей log-файла. Кроме того, сценарий выявляет запросы элементов, отличных от документов HTML, PDF или PS, и помечает возвращаемый кортеж для фильтрации.

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

Листинг 2. Функции R, используемые в анализе записей log-файла
# Этот сценарий содержит функции, используемые для анализа строки из
# log-файла web-сервера.

if (file.exists("../data/bot-list.RData")) {
  load("../data/bot-list.RData")  
} else {
  bot.list <- c("")
}

origin.pattern <- "^\\S+(\\.\\S+)*\\.\\S+"
path.pattern <- "GET\\s+[/\\w]+.\\w+"

get.code <- function(log.entry) {
  # Возвращает код возврата записи из log-файла web-сервера.
  tokens = unlist(strsplit(x=log.entry, split="\\s+", perl=TRUE))
  code = tokens[length(tokens)-1]
  
  return(code)
}

get.path <- function(log.entry) {
  # Возвращает путь запрошенного ресурса из записи log-файла web-сервера.
  path <- regmatches(x=log.entry, m=regexpr(pattern=path.pattern, 
                                               text=log.entry, 
                                               perl=TRUE))
  path <- unlist(strsplit(x=path, split="\\s+", perl=TRUE))[2]
  
  return(path)
}

get.origin <- function(log.entry) {
  # Возвращает инициирующий ip-адрес или домен из записи в log-файле web-сервера.
  return(regmatches(x=log.entry, m=regexpr(pattern=origin.pattern, 
                                           text=log.entry, 
                                           perl=TRUE)))
}

get.tuple <- function(log.entry) {
  # Возвращает список из двух элементов, содержащий модифицированный источник 
  # запроса и путь к запрошенному элементу.
  # Источнику будет присвоена отметка "отфильтровать", если:
  #   -- код возврата отличен от 200
  #   -- запрошенный файл не относится к HTML, PDF или PS
  #   -- источник идентифицирован как бот
  origin <- get.origin(log.entry)
  path <- get.path(log.entry)
  code <- get.code(log.entry)
  
  if (code != "200") {
    origin <- "filter me"
  } else if(is.null(path)) {
    origin <- "filter me"
  } else if(path == FALSE) {
    origin <- "filter me"
  } else if (! grepl(pattern="\\S+\\.(htm|html|pdf|ps)$", x=path, perl=TRUE)) {
    origin <- "filter me"
  } else if (origin %in% bot.list) {
    origin <- "filter me"
  }

  return(list(origin, path))
}

Листинг 3 содержит сценарий R, вызываемый для анализа записей в log-файле. Этот сценарий использует функции в листинге 2.

Листинг 3. Сценарий R, вызываемый для анализа кортежа записи log-файла
# Этот сценарий анализирует записи log-файла, преобразуя их в кортежи
# Он анализирует источник запроса и запрошенный путь.
# 
# на входе:  log.entry -- одна строка из log-файла web-сервера.
# на выходе: origin -- источник запроса, полученного web- 
#                    сервером.
#          path -- путь к запрошенному элементу.
#
# Источнику будет присвоена отметка "отфильтровать", если:
#   -- код возврата отличен от 200
#   -- запрошенный файл не относится к HTML, PDF или PS
#   -- источник идентифицирован как бот

tuple <- unlist(get.tuple(log.entry))
origin <- tuple[1]
path <- tuple[2]

Как показано в листинге 4, tсценарий R использует обученную модель EMM для прогнозирования следующего наиболее вероятного запроса страницы или элемента. В данном случае каждое состояние EMM представляет элемент на сайте (например, документ HTML, PDF или PS). Для прогнозирования следующего наиболее вероятного запроса элемента сценарий ищет состояние, связанное с прежде запрошенным элементом. Затем он использует модель EMM для возврата списка возможных переходов от текущего состояния ко всем другим наблюдавшимся состояниям. Для получения 20 наиболее вероятных элементов приложение просто сортирует список в убывающем порядке и извлекает состояния с самыми высокими уровнями вероятности. На последнем шаге оно преобразует спрогнозированные состояния в соответствующие элементы.

Листинг 4. Сценарий R для прогнозирования с использованием модели EMM
# на входе:  path — путь к последнему запрошенному элементу.
# на выходе: prediction — список из двадцати следующих путей с наибольшей 
#                        вероятностью запроса.

prediction <- vector()
last.request <- page.hash[[path]]
if (! is.null(last.request)) {
  likelihoods <- predict(emm, current_state=last.request, 
                           probabilities=TRUE)
  top.twenty <- names(sort(x=likelihoods, decreasing=TRUE)[1:20])
  for (i in 1:20) {
    prediction[[i]] <- toString(page.list[as.numeric(top.twenty[i])])
  } 
}

Результаты

Приложение создает выходные кортежи, состоящие из IP-адреса источника, запрошенного пути и списка из 20 наиболее вероятных запросов для следующего шага. Листинг 5— это пример выходного кортежа для записи в log-файле web-сервера.

Листинг 5. Пример выходного кортежа
"123.123.123.123", "/pub/atomicbk/catalog/sleazbk.html",
                            ["/atomicbk/new/new.html", "/atomicbk/images/gallery.html",
                            "/atomicbk/shocked.html", ...]

Заключение

В статье демонстрируется применение InfoSphere Stream и R для прогнозирования контента, который будет запрашиваться с web-сервера, с использованием log-файлов этого сервера. Моделирование и прогнозирование выполняется с использованием реализации модели EMM в R.

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


Ресурсы для скачивания


Похожие темы


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Information Management
ArticleID=987248
ArticleTitle=Прогнозирование запросов web-контента с использованием R и InfoSphere Streams
publish-date=10272014