Ассоциативные правила (лекция 2)

1.

АССОЦИАТИВНЫЕ
ПРАВИЛА
Лекция 2

2.

Понятие машинного обучения
Цель моделирования в анализе данных — является выявление свойств и
закономерностей в анализируемых данных.
Информационная модель должна самостоятельно выявлять в данных
присущие им закономерности.
Комплекс методов, используемых для создания таких моделей,
называется машинным обучением, а такие модели называются
обучаемыми.
Обучение по прецедентам,
или индуктивное обучение
Дедуктивное обучение
Важнейшим свойством модели является способность к обобщению.

3.

Понятие ассоциативных правил
Аффинитивный анализ (affinity analysis) — один из распространенных
методов Data Mining.
Его название происходит от английского слова affinity, которое в
переводе означает "близость", "сходство".
Цель данного метода — исследование взаимной связи между событиями,
которые происходят совместно.
Разновидностью аффинитивного анализа является анализ рыночной корзины
(market basket analysis).
Цель анализа — обнаружить ассоциации между различными событиями, то
есть найти правила для количественного описания взаимной связи между двумя
или более событиями. Такие правила называются ассоциативными правилами
(association rules).

4.

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

5.

Базовые понятия
транзакция — некоторое множество событий, происходящих совместно.
рыночная корзина — набор товаров.
Анализ рыночной корзины —
это анализ наборов данных для
определения комбинаций товаров, связанных между собой. Иными
словами, производится поиск товаров, присутствие которых в транзакции
влияет на вероятность наличия других товаров или комбинаций товаров.

6.

Пример.
В каждой строке указывается комбинация продуктов, приобретенных за
одну покупку.
№ Транзакция
1
Сливы, салат, помидоры
2
Сельдерей, конфеты
3
Конфеты
4
Яблоки, морковь, помидоры, картофель, конфеты
5
Яблоки, апельсины, салат, конфеты, помидоры
6
Персики, апельсины, сельдерей, помидоры
7
Фасоль, салат, помидоры
8
Апельсины, салат, морковь, помидоры, конфеты
9
Яблоки, бананы, сливы, морковь, помидоры, лук,
конфеты
10 Яблоки, картофель

7.

Ассоциативное правило
Ассоциативное правило состоит из двух наборов предметов, называемых
условием (antecedent) и следствием (consequent), записываемых в виде:
X Y
ассоциативное правило формулируется в виде:
«Если условие, то следствие».

8.

Показатели
Поддержка ассоциативного правила — это доля транзакций, которые
содержат как условие, так и следствие.
где —
количество транзакций, содержащих A и B, N — общее количество
транзакций.

9.

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

10.

Пример
Возьмем ассоциацию салат — > помидоры. Поскольку количество транзакций,
содержащих как салат, так и помидоры, равно 4, а общее число транзакций равно 10, то
поддержка данной ассоциации будет
Поскольку количество транзакций, содержащих только салат (условие), равно 4, то
достоверность данной ассоциации будет
Иными словами, все наблюдения, содержащие салат, также содержат и помидоры, из чего
делаем вывод о том, что данная ассоциация может рассматриваться как правило. С точки
зрения интуитивного поведения такое правило вполне объяснимо, поскольку оба продукта
широко используются для приготовления растительных блюд и часто покупаются вместе.
Теперь рассмотрим ассоциацию
. Поддержка данной ассоциации
равна S=4/10=0,4, а достоверность равна C=4/6=0,67. Таким образом, данная ассоциация
имеет сравнительно невысокую достоверность и вряд является правилом.

11.

Показатели
Лифт — это отношение частоты появления условия в транзакциях, которые также содержат и
следствие, к частоте появления следствия в целом. Значения лифта большие, чем 1,
показывают, что условие чаще появляется в транзакциях, содержащих следствие, чем в
остальных. Можно сказать, что лифт является обобщенной мерой связи двух предметных
наборов: при значениях лифта больше 1 связь положительная, при 1 она отсутствует, а при
значениях меньше 1 — отрицательная.

12.

Пример

13.

Показатели
Левередж — это разность между наблюдаемой частотой, с которой условие и следствие
появляются совместно (то есть поддержкой ассоциации), и произведением частот
появления (поддержек) условия и следствия по отдельности.

14.

Пример

15.

Алгоритм Apriori
В основе алгоритма Apriori (a priori — лат. априорный, не зависящий от опыта)
лежит понятие популярных наборов (frequent itemset — частый предметный набор),
которые также можно назвать частыми предметными наборами, часто
встречающимися множествами (соответственно, они связаны с понятием частоты).
Под частотой понимается количество транзакций, в которых содержится данный
предметный набор.
Тогда популярными наборами будут те из них, которые встречаются чаще, чем в
заданном числе транзакций.
Популярный предметный набор — предметный набор с поддержкой больше
заданного порога, либо равной ему. Этот порог называется минимальной
поддержкой.

16.

Методика поиска ассоциативных правил с
использованием популярных наборов
Следует найти популярные наборы.
На их основе необходимо сгенерировать ассоциативные правила,
удовлетворяющие условиям минимальной поддержки и достоверности.
Алгоритм Apriori использует свойство антимонотонности. Свойство утверждает,
что если предметный набор Z не является частым, то добавление некоторого
нового предмета A к набору Z не делает его более частым. Другими словами,
если Z не является популярным набором, то и набор Z A также не будет являться
таковым. Данное полезное свойство позволяет значительно уменьшить
пространство поиска ассоциативных правил.

17.

Алгоритм выявления популярных
наборов
Шаг 1. Присвоить k =1 и выполнить отбор популярных одноэлементных
наборов F1 , то есть наборов, у которых поддержка больше минимально
заданной пользователем Smin .
Шаг 2. k =k +1.
Шаг 3. Если не удается создавать k -элементные наборы, то завершить
алгоритм, иначе выполнить следующий шаг.
Шаг 4. Создать множество Fk k -элементных наборов кандидатов из
популярных наборов. Для этого необходимо объединить в k –элементные
кандидаты (k -1) -элементные популярные наборы. Предметы в популярных
наборах должны быть упорядочены, например, по алфавиту. Предметные
наборы являются связываемыми, если у них первые k -2 предметов
одинаковые. Если объединяются наборы p и q , то к набору p добавляется
последний элемент набора q, который по порядку выше, чем последний
элемент набора p .

18.

Шаг 5. Удаление избыточных правил. На основании свойства
антимонотонности, следует удалить те наборы, у которых хотя бы одно
из (k -1) -подмножеств не является популярным.
Шаг 6. Подсчет поддержки для каждого кандидата. Очевидно, что
количество кандидатов может быть очень большим и нужен
эффективный способ подсчета. Самый тривиальный способ —
сравнить каждую транзакцию с каждым кандидатом. Но это далеко не
лучшее решение. Практически используют хранение кандидатов в
специальном хэш-дереве.
Шаг 7. Переход на шаг 3.
Генерация ассоциативных правил
1. Генерируются все возможные поднаборы набора s .
2. Если поднабор ss является непустым поднабором s , то рассматривается
ассоциация R: ss->(s – ss) , где s - ss представляет собой набор s без поднабора
ss . Ассоциация R считается ассоциативным правилом, если удовлетворяет
условию заданного минимума поддержки и достоверности.
Данный шаг повторяется для каждого подмножества ss из s .

19.

Иерархические ассоциативные
правила
Ассоциативные правила для предметов, расположенных на различных
иерархических уровнях, называются иерархическими ассоциативными
правилами.
Используются также термины многоуровневые правила (multilevel rules) или
обобщенные правила (generalized rules).
Иерархия предметов может использоваться для сокращения числа
рассматриваемых предметных наборов:
1. Сначала ищутся ассоциации с высокой поддержкой для верхних уровней
иерархии.
2. Анализируются потомки только тех предметов верхних уровней, которые
удовлетворяют заданному минимуму поддержки. Анализировать потомки редких
предметов нет смысла, так как они будут встречаться еще реже, чем их предки.