Ассоциативные правила

Введение в анализ ассоциативных правил

Объемы современных баз данных, которые весьма внушительны, вызвали устойчивый спрос на новые масштабируемые алгоритмы анализа данных. Одним из популярных методов обнаружения знаний стали алгоритмы поиска ассоциативных правил. Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила, служит утверждение, что покупатель, приобретающий "Хлеб", приобретет и "Молоко" с вероятностью 75%. 

Apriori - масштабируемый алгоритм поиска ассоциативных правил

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

Выявление обобщенных ассоциативных правил

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

FPG - альтернативный алгоритм поиска ассоциативных правил

Кроме алгоритма a priori, для поиска ассоциативных правил является алгоритм, получивший название Frequent Pattern-Growth (FPG), что можно перевести как «выращивание популярных (часто встречающихся) предметных наборов». Он позволяет не только избежать затратной процедуры генерации кандидатов, но уменьшить необходимое число проходов по набору данных до двух. 

Поиск последовательных шаблонов. Часть 1.

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

Поиск последовательных шаблонов. Часть 2.

Во второй части статьи подробно рассматриваются алгоритмы нахождения последовательных шаблонов - AprioriAll, AprioriSome, DynamicSome.