Методы искусственного интеллекта. Алгоритмы поиска ассоциативных правил (лекция)

1. Методы искусственного интеллекта

Алгоритмы поиска
ассоциативных правил

2.

Ассоциативные
правила – установление
закономерностей
между
связанными
событиями. Нахождение зависимости, что из
события X следует событие Y.

3. Поиск ассоциативных правил алгоритм Apriori (1994г.)

Методика поиска:
1. Преобразовать базу транзакций в
нормализованную таблицу
2. Найти частые наборы (применяя свойство
антимонотонности).
Частый предметный набор — предметный набор с
поддержкой больше заданного порога либо равной ему.
Этот порог называется минимальной поддержкой.
3. На их основе необходимо сгенерировать
ассоциативные правила

4. Поиск ассоциативных правил алгоритм Apriori (1994г.)

Методика поиска:
4. Вычислить показатели значимости
(S, С, L, T, I)
5. Отобрать правила, удовлетворяющие
критериям значимости.
6. Отобрать нетривиальные полезные
правила.

5. Недостатки алгоритма A priori

Большие
затраты,
вычислительные
и
временные
на
и
обработку
кандидатов
генерацию
в
популярные
предметные
наборы.
Многократное
транзакций.
сканирование
базы
данных

6. Алгоритм FPG Frequent Pattern-Growth

Преимущества:
Сжатие БД транзакций в компактную структуру –
дерево – очень эффективное и полное извлечение
частых предметных наборов;
2.
При построении
FP-дерева используется
технология разделения и захвата, которая позволяет
выполнить декомпозицию одной сложной задачи на
множество более простых;
3.
Позволяет избежать затратной процедуры
генерации кандидатов, характерной для алгоритма
Аpriori.
1.

7. База транзакций для алгоритма FPG

№
1
2
3
4
5
6
7
Транзакция

8. Алгоритм FPG

1. Производится первое сканирование БД
транзакций, и отбирается множество
часто встречающихся предметов, т.е.
предметов, которые встречаются три или
более раза. Упорядочивание предметов в
транзакциях по убыванию значений их
поддержек.
2. Построение FP-дерева.

9.

N
Исходный
Упорядоченный
предметный набор предметный набор
1
abcde
cbdea
2
abc
cba
3
acde
cdea
4
bcde
cbde
5
bc
cb
6
bde
bde
7
cde
cde

10. Построение FP-дерева

Правило.
Если для очередного предмета в дереве
встречается
узел,
имя
которого
совпадает с именем предмета, то
предмет не создает нового узла, а индекс
соответствующего
узла
в
дереве
увеличивается на 1. В противном случае
для этого предмета создается новый узел
и ему присваивается индекс 1.

11. Построение FP-дерева на транзакции №1

12. Построение FP-дерева на транзакции №2

2
2

13. Построение FP-дерева на транзакции №3

14. Построение FP-дерева на транзакции №3

15. Построение FP-дерева на транзакции №4

16. Построение FP-дерева на транзакции №5

17. Построение FP-дерева на транзакции №6

18. Построение FP-дерева на транзакции №7

19. Извлечение частых предметных наборов из FP-дерева

в FP-дереве для предмета a можно указать
3 пути: {cbdea, cba, cdea}.
Такой набор путей называется условным
базисом предмета (англ.: conditional base).
Каждый путь в базисе состоит из двух
частей – префикса и суффикса.
В пути cbdea префиксом будет cbde, а
суффиксом – a.

20. Извлечение частых предметных наборов из FP-дерева

Префикс – это последовательность узлов,
которые проходит путь для того, чтобы
достичь узла, связанного с предметом.
Суффикс – это сам узел, к которому
«прокладывается» путь.

21. Алгоритм извлечения из FP-дерева частых предметных наборов

1.
2.
3.
Выбираем предмет (например, a) и
находим в дереве все пути, которые
ведут к узлам этого предмета (для a это
будет набор {(cbdea,1), (cba,1),
(cdea,1)}).
2. Удалим сам предмет (суффикс набора)
из ведущих к нему путей, т.е. {cbdea, cba,
cdea}. После это останутся только
префиксы: {cbde, cb, cde}.

22. Алгоритм

3. Подсчитаем, сколько раз каждый предмет
появляется в префиксах путей {(cbde,1),
(cb,1), (cde,1)}), полученных на предыдущем
шаге, и упорядочим в порядке убывания
этих значений, получив новый набор
транзакций.
(с;3) (b;2) (d;2) (e;2)

23. Алгоритм

4. На его основе (с;3) (b;2)(d;2) (e;2)
построим новое FP-дерево, которое назовем
условным FP-деревом (conditional FP-tree),
поскольку оно связано только с одним
объектом.
Условное FP-дерево
Для предмета а:

24. Алгоритм

5. В этом FP-дереве найдем все предметы
(узлы), для которых поддержка (количество
появлений в дереве) равна 3 и больше, что
соответствует заданному уровню
минимальной поддержки. Если предмет
встречается два или более раза, то его
индексы, т.е. частоты появлений в условном
базисе, суммируются.

25. Пример

Поскольку предметы d и e встречаются два
раза, то их индексы суммируются, и в итоге
мы получим следующий порядок предметов:
(c, 3), (b, 2), (d, 2), (e, 2).

26. Алгоритм

6. Начиная с верхушки дерева,
записываем пути, которые ведут к
каждому
узлу,
для
которого
поддержка/индекс больше или равны 3,
возвращаем назад предмет (суффикс
шаблона), удаленный на шаге 2, и
подсчитываем
индекс/поддержку,
полученную в результате.

27. Пример

Только узел c удовлетворяет уровню
минимальной поддержки 3. Следовательно,
для предмета a может быть сгенерирован
только один популярный набор (c, a) с
поддержкой S=3).

28. Задание

Построить условное FP-дерево для
предметов {b, d, e} и найти популярные
предметные наборы с поддержкой >=3.

29. Пример

Ответ:
получили
следующие
популярные предметные наборы:
(c,a,3), (c,b,4), (c,d, 4), (b,d,3), (d,e,5),
(с,e,5),(b,e,3), (d, c, e,4), (d, b,e,3)
Контроль правильности: оба алгоритма
Apriori и FPG дают одинаковые частые
наборы.
Этап генерации правил и показатели
значимости такие же, как у алгоритма
Apriori

30. Сравнение алгоритмов FPG и a priori

31. Интерпретация правил

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

32. Интерпретация правил

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

33. Задание (применить алгоритм FPG, порог 30%)

10
Яблоки, картофель