Основы информационных технологий

Транзакционная база данных 
TID 
Приобретенные покупки 
100 
Хлеб, молоко, печенье 
200 
Молоко, сметана 
300 
Молоко, хлеб, сметана, печенье 
400 
Колбаса, сметана 
500 
Хлеб, молоко, печенье, сметана 
Ассоциативные правила
определяются как утверждения вида 
{
X
1
,X
2
,…,X
n
} 

Y
, где подразумевается, что 
Y 
может присутствовать в тран-
закции при условии, что 
X
1
,X
2
,…,X
n
присутствуют в этой же транзакции.
В качестве 
Y
может выступать набор элементов, а не только один 
элемент. Вероятность нахождения 
Y
в транзакции, в которой имеются 
элементы 
X
1
,X
2
,…,X
n
,
называется 
достоверностью
(confidence). Процент 
транзакций, содержащих правило, от общего числа транзакций 
называется 
поддержкой
(support). Уровень достоверности, который 
должна превышать достоверность правила, называется 
интересностью
(interestingness). 
Существуют различные типы ассоциативных правил. В простейшей 
форме ассоциативные правила сообщают только о наличии или отсут-
ствии ассоциации. Логическая природа таких правил озвучена в их 
названии –булевые ассоциативные правила (Boolean Association Rule). На 
примере корзины потребителя, "покупатели, которые приобретают сня-
тое молоко также приобретают масло с низким уровнем жира" – типич-
ное булевое ассоциативное правило. 
Правила, которые собирают несколько ассоциативных правил вместе, 
называются мультиуровневыми, или обобщенными, ассоциативными 
правилами (Multilevel or Generalized Association Rules). При построении 

---

– 60 – 
таких правил элементы обычно группируются согласно иерархии и поиск 
ведется на самом высоком концептуальном уровне. Например, "покупа-
тели, которые приобретают молоко, приобретают также хлеб". В этом 
примере молоко и хлеб содержат иерархию различных типов и брендов, 
однако поиск на нижнем уровне не позволит найти интересные правила. 
Более сложным типом правил являются количественные ассоциатив-
ные правила (Quantitative Association Rules). Этот тип правил ищется с 
применением количественных (например, цена) или категориальных 
(например, пол) атрибутов, и определен как 
{,,…,n
:value>}

. 
Например, "покупатели, чей возраст находится между 30 и 35 годами 
с доходом более 75000 в год покупают машины стоимостью более 
20000".
Вышеперечисленные типы правил не затрагивают тот факт, что тран-
закции по своей природе зависят от времени. Например, поиск до того, 
как продукт был выставлен на продажу, или после того, как он исчез с 
рынка, неблагоприятно повлияет на пороговое значение поддержки 
(support). 
Несмотря на различные типы правил, алгоритм для поиска ассоциа-
тивных правил может быть в общем виде разделен на два этапа:
1) поиск наиболее часто встречающихся наборов элементов (large 
(frequent) itemsets); часто встречающийся набор – это набор, у которого 
поддержка превышает минимальное значение;
2) генерация правил на основе часто встречающихся наборов.
Присвоим значениям товаров переменные (табл.8): 
хлеб = 
a
; молоко = 
b
; печенье = 
c
; сметана = 
d
; колбаса = 
e
; конфе-
ты = 
f
. 
Таблица 8