Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ
Посмотреть оригинал

Поиск ассоциаций в данных

Постановка задачи поиска ассоциаций в данных

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

(frequent pattern miningFPM)K Огромное число алгоритмов было предложено для решения задач FPM, однако до сих пор данная область остается в фокусе внимания исследователей. Прежде чем ответить на вопрос, почему FPM так привлекает внимание исследователей, попробуем дать формальную постановку задачи FPM. [1]

Основная задача FPM — поиск связей между элементами в базе данных. Задача FPM была впервые сформулирована в проблеме анализа пользовательских покупок в больших онлайн-магазинах. Мы будем придерживаться оригинальной терминологии в постановке задачи, однако, как вскоре станет ясно, данная задача может быть легко распространена на многие другие области.

Для данной базы данных D с набором транзакций (записей) Т{, Г2, ..., Гдг необходимо найти множество шаблонов Р такое, что каждый из них может представить как минимум 5 некоторых транзакций. Параметр s в задаче называется поддержкой (support) и определяет число транзакций, попадающих иод шаблон. Каждая транзакция может быть представлена сильно разряженным бинарным вектором, каждая г-я координата которого описывает наличие в транзакции заказа на товар i в магазине. Примем V и U как некоторые множества элементов из магазина. Правило U => V называется ассоциацией с минимальной поддержкой s и минимальной уверенностью с, если:

  • 1) U u V — это частотный шаблон;
  • 2) отношение мощностей U u V к U не меньше уверенности с.

Отметим, что во втором условии отношение мощностей будет

всегда меньше единицы, если множества U и V не равны.

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

Как нетрудно догадаться, шаблон — это тоже вектор того же пространства, что и транзакции, и представляет собой результат применения операции покоординатного логического «И» к некоторому подмножеству транзакций. Такой шаблон считается частотным, если его поддержка как минимум равна минимальной. Например, для транзакций Тх = {1, 0, 1, 1}, Т2 = {1, 0, 0, 1}, Г3 = {1, 1, 1, 1} общий шаблон будет Р = {1, 0, 0, 1} и его поддержка соответственно равна трем.

Причина, по которой задача FPM привлекает большое внимание исследователей, заключается в том, что FPM имеет огромное число полезных приложений, в частности:

  • • анализ покупательской активности. В данной задаче транзакции представляют собой набор совместно купленных товаров. FPM в данном случае может быть использована для генерации рекомендаций будущим покупателям — если текущий набор товаров пересекается с каким-либо частотным шаблоном, то можно предложить оставшиеся из шаблона товары;
  • • анализ логов пользователей онлайн-сервиса. В данной задаче элементами транзакции могут быть элементарные действия пользователя. Шаблоны, как и в первой задаче, можно использовать для автогенерации подсказок действий пользователям, а также для анализа дизайна сайта или поиска выбросов в пользовательской активности. К анализу дизайна FPM применима для поиска цепочек действий, которые можно сократить до одного. Если же па сервисе присутствуют часто встречающиеся цепочки действий, то цепочки действий с подозрительно малой поддержкой могут быть интерпретированы как выброс — странное действие пользователя;
  • • анализ ошибок в приложениях. Если приложение имеет достаточно подробные логи, то нормальное состояние приложения — генерировать примерно одинаковые последовательности логов, в то время как возможные ошибки будут порождать низкочастотные шаблоны, которые были бы интересны для анализа;
  • • алгоритмы FPM можно также использовать в других задачах машинного обучения, например для классификации, когда класс представляется частотным шаблоном, или же для кластеризации — похожие транзакции можно объединять кластером-шаблоном и г.п.

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

В качестве иллюстрации примера частотных шаблонов рассмотрим табл. 6.1.

Таблица 6.1

Пример множества транзакций в базе

Заказанные товары

Отсортированный список частотных элементов

1

a, by c, dy ву f

a, by с, d

2

a, b, c, d, h, g

a, by с, d

3

by dy hyj, Zy x

b,d

4

Cy dy e

с, d

5

a, b, c, d, h, g

Qy by c

1 См.: Agrawal R., Srikant R. Fast Algorithms for Mining Association Rules. URL: http://rakcsh.agrawal-family.com/papcrs/vldb94apriori.pdf

Множество товаров для данного примера равно {а, й, с, d, е, /, g, й, х, г}. Для данного примера мы выбрали значение минимальной поддержки, равное трем. Соответственно, зная это значение, легко найти в каждой транзакции все частотные шаблоны длины 1. На рис. 6.6 представлен граф, показывающий все возмножные шаблоны, которые можно сгенерировать на основе найденных частотных шаблонов длины 1, а также отмечены все возможные частотные шаблоны. Nil на рис. 6.6 обозначает пустой шаблон, от которого начинается построение всех частотных шаблонов.

Граф раскрытия частотных шаблонов

Рис. 6.6. Граф раскрытия частотных шаблонов:

— частотные шаблоны

Представим общий подход к генерации множества частотных шаблонов в виде алгоритма. [2] [3]

Алгоритм:

FP={).

  • 2. Найти все частотные шаблоны длины 1 и вставить их в FP.
  • 3. Пока вес частотные шаблоны из FP не были просмотрены:
  • 3.1. Сгенерировать шаблон Р на основе одного или нескольких шаблонов из FP.
  • 3.2. Если поддержка Р больше минимальной, то занести его в FP.
  • 3.3. Отметить просмотренные шаблоны.
  • 4. Вернуть множество FP.

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

  • [1] См.: Aggarwal С. С., Han J. Frequent Pattern Mining. N. Y.: Springer, 2014.
  • [2] Вход: • База данных D. • Минимальная поддержка 5. Выход:
  • [3] Множество частотных шаблонов FP.
 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы