Association rule

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

Ассоциативные правила представляют собой механизм нахождения логических закономерностей между связанными элементами (событиями или объектами). Пусть имеется \(\mathbf{A} = \{a_1, a_2, a_3, \dots, a_n\}\)- конечное множество уникальных элементов (list of items). Из этих компонентов может быть составлено множество наборов \(\mathbf{T}\) (sets of items), т.е. \(\mathbf{T} \subseteq \mathbf{A}\).

Ассоциативные правила \(\mathcal{A} \rightarrow \mathcal{T}\) имеют следующий вид: если <условие> то <результат>, где в отличие от деревьев классификации, <условие> - не логическое выражение, а набор объектов из множества \(\mathbf{A}\), с которыми связаны (ассоциированы) объекты того же множества, включенные в <результат> данного правила. Например, ассоциативное правило если (лес, вода) то (лягушки) означает, что если в лесу встретилось болотце или ручей, то рядом будут лягушки.

Понятие “вид элемента \(a_k\)” легко может быть обобщено на ту или иную его категорию или вещественное значение, т.е. концепция ассоциативного анализа может быть применена для комбинаций любых переменных. Например, при прогнозировании погоды одно из ассоциативных правил может выглядеть так: 'утром обильная роса' -> 'днем солнечно' = TRUE

Выделяют три вида правил:

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

Поиск ассоциативных правил обычно выполняют в два этапа:

• в пуле имеющихся признаков \(\mathbf{A}\) находят наиболее часто встречающиеся комбинации элементов \(\mathbf{T}\);
• из этих найденных наиболее часто встречающихся наборов формируют ассоциативные правила.

Для оценки полезности и продуктивности перебираемых правил используются различные частотные критерии, анализирующие встречаемость кандидата в массиве экспериментальных данных. Важнейшими из них являются поддержка (support) и достоверность (confidence). Правило \(\mathcal{A} \rightarrow \mathcal{T}\) имеет поддержку \(s\), если оно справедливо для \(s\%\) взятых в анализ случаев:

\[\text{support}(\mathcal{A} \rightarrow \mathcal{T}) = P(\mathcal{A} \cup \mathcal{T})\]

Достоверность правила показывает, какова вероятность того, что из наличия в рассматриваемом случае условной части правила следует наличие заключительной его части (т.е. из \(\mathcal{A}\) следует \(\mathcal{T}\)):

\[\text{confidence}(\mathcal{A} \rightarrow \mathcal{T}) = \frac{P(\mathcal{A} \cup \mathcal{T})}{P(\mathcal{A})} = \frac{\text{support}(\mathcal{A} \rightarrow \mathcal{T})}{\text{support}(\mathcal{A})}.\]

Алгоритмы поиска ассоциативных правил отбирают тех кандидатов, у которых поддержка и достоверность выше некоторых наперед заданных порогов: minsupport и minconfidence. Если поддержка имеет большое значение, то алгоритмы будут находить правила, хорошо известные аналитику или настолько очевидные, что нет никакого смысла проводить такой анализ. Большинство интересных правил находят именно при низком значении порога поддержки. С другой стороны, низкое значение minsupport ведет к генерации огромного количества вариантов, что требует существенных вычислительных ресурсов или ведет к генерации статистически необоснованных правил.

Используются и другие показатели - подъемная сила, или лифт (lift), которая показывает, насколько повышается вероятность нахождения \(\mathcal{T}\) в анализируемом случае, если в нем уже имеется \(\mathcal{A}\):

\[\text{lift}(\mathcal{A} \rightarrow \mathcal{T}) = \frac{\text{confidence}(\mathcal{A} \rightarrow \mathcal{T}) }{ \text{support}(\mathcal{T})}\]

и усиление (leverage), которое отражает, насколько интересной может быть более высокая частота \(\mathcal{A}\) и \(\mathcal{T}\) в сочетании с более низким подъемом:

\[\text{leverage}(\mathcal{A} \rightarrow \mathcal{T}) = \text{support}(\mathcal{A} \rightarrow \mathcal{T}) - \text{support}(\mathcal{A})\times\text{support}(\mathcal{T})\]

Пример.

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

Вначале выпишем матрицу частот парного сочетания товаров \(x_i\) и \(x_j\): \(\sigma(x_i\cup x_j)\)

Support (поддержка)

Это нормированное значение парного сочетания товаров \[ supp(x_i\cup x_j)=\frac{\sigma(x_i\cup x_j)}{|T|}, \] где \(|T|-\) общее число транзакций.

Confidence (достоверность)

Данный показатель характеризует насколько часто срабатывает наше правило: \[ conf(x_i\cup x_j)=\frac{supp(x_i\cup x_j)}{supp(x_i)}. \]

Lift (поддержка)

Показатель поддержки представляет собой отношение "зависимости" элементов транзакции к их "независимости" и, естественно, показывает насколько эти элементы зависят один от другого \[ lift(x_i\cup x_j)=\frac{supp(x_i\cup x_j)}{supp(x_i)\times supp(x_j)}. \] Если значение \(lift(x_i\cup x_j)=1\), то транзакции с \(x_i\) и \(x_j\) независимы и правил их совместной покупки нет. Если значение \(lift(x_i\cup x_j)>1\), то значение \(lift(x_i\cup x_j)-1\) характерирует ассоциативное правило, чем это значение больше, тем правило "правильнее", если же \(lift(x_i\cup x_j)\lt 1\), то покупка \(x_j\) негативно сказывается на покупке \(x_i\).

Conviction (убедительность)

Величина \[ conv(x_i\cup x_j)=\frac{1-supp(x_j)}{1-conf(x_i\cup x_j)} \] характеризует ошибки ассоциативного правила. Чем результат действия больше единицы, чем более надежно правило. Если значение равно Infinity, то правило тривиальное.

Leverage (усиление)

Показатель усиления характеризует насколько интересной может быть более высокая частота выпадения элементов в транзакции в сочетании с более низким подъемом \[ lever(x_i\cup x_j)=supp(x_i\cup x_j)-supp(x_i)\times supp(x_j). \]

1. Кортежи - это транзакции, пары атрибут-значение - элементы.
2. Правило ассоциации : {A, B, C, D, ...} => {E, F, G, ...}, где A, B, C, D, E, F, G, ... являются элементами ,
3. Достоверность(точность) A => B: P (B | A) = (количество транзакций, содержащих как A, так и B) / (количество транзакций, содержащих A).
4. Поддержка (покрытие) A => B: P (A, B) = (количество транзакций, содержащих как A, так и B) / (общее количество транзакций)
5. Мы ищем правила, которые превышают заранее определенную поддержку (минимальную поддержку ) и имеют высокую степень достоверности.

Первый алгоритм поиска ассоциативных правил был разработан в 1993 г. сотрудниками исследовательского центра IBM, что сразу возбудило интерес к этому направлению. Каждый год появлялось несколько новых алгоритмов (DHP, Partition, DIC и др.), из которых наиболее известным остался алгоритм “Apriori” (Agrawal, Srikant, 1994).

Полный перебор (метод «грубой силы» -brute force).

Для небольшого числа транзакций вполне можно воспользоваться следующим алгоритмом.

• Сгенерировать все возможные подмножества наборов элементов, за исключением пустого набора (\(2^n - 1\)), и используйте их как следствия правила (остальные элементы использовать в качестве априорных данных).
• Вычислите доверие: разделите поддержку элемента, установленную на поддержку предшествующего элемента.
• Выберите правила с высокой достоверностью (используя порог).

Apriory

Основная идея (алгоритм Apriori):

Найти все наборы из n предметов. Пример (n = 2): L2 = {{A, B}, {A, D}, {C, D}, {B, D}}
• Генерация (n + 1) наборов элементов путем объединения наборов из n элементов. L3 = {{A, B, C}, {A, C, D}, {A, B, D}, {B, C, D}}.
• Проверьте вновь сгенерированные наборы (n + 1) -элементов на минимальную поддержку.
• Из L3 исключите наборы, которые содержат нечастые наборы из 2 предметов.
• Протестируйте оставшиеся наборы элементов на минимальную поддержку, посчитав их вхождения в данные.
• Увеличивайте n и продолжайте, пока не будут сгенерированы более частые наборы элементов.

Вопрос-ответ.