Поиск ассоциативных правил в интеллектуальном анализе данных.

Siu Nin Lam

Department of Computer Science

University of Illinois at Urbana-Champaign

snlam@uiuc.edu

перевод В.В. Деревянко, dvpublic@gmail.com

Аннотация

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

Введение

Поиск ассоциативных правил - это сердце интеллектуального анализа данных (data mining). Поиск обнаруживает скрытые связи в, на первый взгляд, никак несвязанных данных. Эти связи - правила. Те, которые превышают определенный порог, считаются интересными. Интересные правила дают возможность выполнять действия основываясь на определенных шаблонах. Они так же помогают в принятии и объяснении решений.

Одним из наиболее часто цитируемых примеров поиска ассоциативных правил служит проблема поиска устойчивых связей в корзине покупателя (Market-Basket Problem). Как следует из [3], проблема поиска устойчивых связей в корзине покупателя состоит в том, чтобы определить какие товары приобретаются покупателями вместе, так, чтобы специалисты по маркетингу могли соответствующим образом разместить эти товары в магазине для повышения объема продаж, а так же принять другие решения, способствующие продажам. Некоторые обнаруживаемые правила могут быть тривиальными, например, "покупатели, которые покупают хлеб, так же покупают и масло". Другие - интересные и экстраординарные, например "покупатели, которые покупают пеленки, так же покупают и пиво". Именно способность обнаруживать интересные правила делает поиск ассоциативных правил ценным и способствующим поиску знаний.

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

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

Теории

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

Ассоциативные правила определяются как утверждения вида {X1,X2,…,Xn} -> Y [3], где подразумевается, что Y может присутствовать в транзакции при условии, что X1,X2,…,Xn присутствуют в этой же транзакции. Следует обратить внимание, что слово "может" подразумевает, что правило не является тождеством, а выполняется только с некоторой вероятностью. Кроме того, в качестве Y может выступать набор элементов, а не только один элемент. Вероятность нахождения Y в транзакции, в которой имеются элементы X1,X2,…,Xn, называется достоверностью (confidence). Процент транзакций, содержащих правило, от общего числа транзакций называется поддержкой (support). Уровень достоверности, который должна превышать достоверность правила, называется интересностью (interestingness) [2].

Существуют различные типы ассоциативных правил. В простейшей форме ассоциативные правила сообщают только о наличии или отсутствии ассоциации. Логическая природа таких правил озвучена в их названии - булевые ассоциативные правила (Boolean Association Rule). На примере корзины потребителя, "покупатели, которые приобретают снятое молоко так же приобретают масло с низким уровнем жира" - типичное булевое ассоциативное правило.

Правила, которые собирают несколько ассоциативных правил вместе, называются мультиуровневые или обобщенные ассоциативные правила (Multilevel or Generalized Association Rules) [2]. При построении таких правил элементы обычно группируются согласно иерархии и поиск ведется на самом высоком концептуальном уровне. Например, "покупатели, которые приобретают молоко, так же приобретают хлеб". В этом примере, молоко и хлеб содержат иерархию различных типов и брендов, однако поиск на нижнем уровне не позволит найти интересные правила.

Более сложным типом правил являются количественные ассоциативные правила (Quantitative Association Rules). Этот тип правил ищется с применением количественных (например, цена) или категориальных (например, пол) атрибутов, и определен в [1] как {<attribute:value>, <attribute:value>,…,<attribute:value>} -> <attribute:value>. Например, "покупатели, чей возраст находится между 30 и 35 годами с доходом более 75000 в год покупают машины стоимостью более 20000".

Вышеперечисленные типы правил не затрагивают тот факт, что транзакции, по своей природе, зависят от времени. Например, поиск до того, как продукт был выставлен на продажу или после того, как он исчез с рынка, неблагоприятно повлияет на пороговое значение поддержки (support). С учетом этого, в [5] введена концепция атрибутного времени жизни в алгоритмах поиска временных ассоциативных правил (Temporal Association Rules).

Несмотря на различные типы правил, алгоритм для поиска ассоциативных правил может быть в общем виде разделен на два этапа:

1. поиск наиболее часто встречающихся наборов элементов (large (frequent) itemsets); часто встречающийся набор - это набор, у которого поддержка превышает минимальное значение;

2. генерация правил на основе часто встречающихся наборов.

С момента появления алгоритма Apriori [4], этот алгоритм является наиболее часто применяемым на первом шаге. Многие улучшения [7, 13] шага 1, например, по скорости и по масштабируемости, направлены на совершенствование алгоритма Apriori, на исправление его ошибочного свойства генерировать слишком много кандидатов на наиболее часто встречающиеся наборы элементов. Другие алгоритмы базируются не на Apriori [9, 11, 12], но нацелены на решение проблем скорости этого алгоритма.

Второй шаг в основном характеризуется достоверностью и интересностью. Имеются исследования, посвященные поиску других путей генерации правил [8] и альтернативным измерениям интересности [6, 10]. Кроме того, существует ряд исследований посвященных генерированию других типов правил [1, 5].