Учебное пособие по курсу интеллектуальные системы (Часть 1) Москва 2003

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

Менеджеры по маркетингу любят правила подобные следующему: 90 % женщин с красным спортивным автомобилем и маленькими собачками используют духи Chanel No.5. Эти виды описаний дают им ясные профили заказчиков, на которые они ориентируют свои действия. Теперь можно задаться вопросом, можно ли найти эти типы правил с помощью инструментальных средств обнаружения знаний. Ответ - положительный и в технологии обнаружения знаний этот тип связей называется ассоциативными правилами [2] .

Существует много методов для нахождения таких правил. Предположим, что существует база данных, содержащая информацию относительно пола заказчиков, цвета и типа их автомобиля, вида домашнего животного, которого они имеют, и характера продуктов, которые они, вероятно, купят. Тогда упомянутое выше правило следовало бы сформулировать в такой базе данных так: для 90 % записей, где пол женский, автомобиль - спортивный, цвет автомобиля - красный, а домашнее животное - небольшая собачка, духи были бы Chanel No. 5.
Ассоциативные правила всегда определяются на бинарных атрибутах, таких как были использованы в базе данных выборки, чтобы представить подписки на журналы. Не очень трудно разработать алгоритмы, которые найдут эту ассоциацию в большой базе данных. Однако проблема состоит в том, что такой алгоритм будет открывать также много других ассоциаций, которые имеют очень небольшое значение.
Не существует многих женщин, обладающих красными спортивными автомобилями и небольшими домашними животными, так что это очень небольшое подмножество наших заказчиков, и соответствующий алгоритм найдет только это небольшое подмножество из обширного множества клиентов. К тому же число возможных ассоциативных правил, которые может быть найдено в такой базе данных, достаточно велико. Проблема с ассоциативными правилами состоит в том, что алгоритм может найти так много ассоциаций, что будет очень трудно отделить ценную информацию от простого шума, и следовательно необходимо ввести некоторую меру различия значимых ассоциаций от неинтересных.
Будем представлять ассоциативное правило следующим способом:
MUSIC_MAG, HOUSE_MAG = > CAR_MAG
Это означает, что кто-то, кто читает и музыкальный журнал, и журнал о доме также с большой вероятностью будет читать автомобильный журнал. Какие же ассоциации значимы? Первоначально ищем ассоциации, которые имеют множество примеров в базе данных, и заканчиваем этот процесс поддержкой ассоциативного правила. В нашем случае поддержка правила - это процент записей, в которых содержатся все выражения MUSIC_MAG, HOUSE_MAG и CAR_MAG, т.е., все люди, которые читают все три журнала.
Однако, поддержка сам по себе - недостаточна. Возможен случай, когда мы имеем значительную группу людей, которая читают все три журнала, но существует гораздо большая группа, которая читает, и MUSIC_MAG и HOUSE_MAG, хотя не читает CAR_MAG. В этом случае ассоциация очень слаба, хотя поддержка могла бы быть относительно высокой. Таким образом, нам необходима дополнительная мера - доверие - и в представленном случае такое доверие есть процент записей, в которых содержится CAR_MAG в пределах группы записей, в которых содержатся MUSIC_MAG и HOUSE_MAG.
В целом ассоциативные правила полезны в технологии обнаружения знаний только, если уже существует приближенное представление о том, что должно быть обнаружено. Это иллюстрирует тот факт, что не существует алгоритма, который автоматически даст нам всё, что есть интересного в базе данных. Алгоритм, который находит множество правил, будет вероятно находить также множество бесполезных правил, в то время как алгоритм, который находит только ограниченное число ассоциаций, без хорошей настройки, будет вероятно также пропускать множество значимой информации. В приведенном выше примере, были проиллюстрированы ассоциативные правила, использующие многократные атрибуты. В нашем маркетинговом примере относительно журналов, сначала исследуем одноместные ассоциативные правила. На рис. 3.4. представлены ассоциации между различными группами читателей журнала.



Рис. 3.4.. Бинарные ассоциации между журналами.

Из рис. 3.4. видно, что для пяти атрибутов уже существует 25 возможных ассоциативных правил. Это число растёт экспоненциально, если допускать многократные ассоциации атрибутов. Можно видеть также высокую корреляцию между журналами музыки и комиксов, между автомобильным и музыкальным журналами. Снова, как в случае с деревьями решений, лучше использовать среду, которая дает нам возможность интерактивно увеличить масштаб на значимых наборах ассоциативных правил, и на рис. 3.5 представлена такая среда.

Спортивный журнал Музыкальный журнал Комиксы
(36 %, 45 %) (96 %, 15 %) (57 %, 8 %)

Рис. 3.5. Бинарные ассоциации для автомобильного журнала.

Мы выбрали CAR_MAG в качестве целевого атрибута, то есть интересуемся читателями автомобильного журнала. Уровни доверия и поддержки установлены в 33% и 3%, что означает, что мы не заинтересованы в подгруппах, меньших, чем 3 % базы данных, и что внутри этих подгрупп мы хотим найти ассоциации, которые содержат, по крайней мере, 33 % записей. На первой стадии нашего исследования анализируются все релевантные атрибуты и очевидно, что с этими уровнями доверия и поддержки алгоритм не найдёт никакой ассоциации для журнала о доме. Однако анализ связей с другими тремя журналами приводит к следующим предварительным ассоциативным правилам:

SPORTS_MAG = > CAR_MAG
MUSIC_MAG = > CAR_MAG
COMIC_MAG = > CAR_MAG
Второе правило наиболее интересно, так как оно имеет высокий уровень доверия (96 %) с довольно высокой поддержкой (15%). Следующий логический шаг состоит в том, чтобы проанализировать дальше потенциальные ассоциации, включающие журнал музыки. Результат представлен на рис. 3.6.

Спортивный журнал Музыкальный журнал Комиксы

(36 %, 45 %) (96 %, 15 %) (57 %, 8 %)

Музыкальный журнал Музыкальный журнал Музыкальный журнал

“Дом” Спортивный журнал Комиксы
(97 %, 9 %) (95 %, 6 %) (100 %, 4 %)
Музыкальный журнал
“Дом”
Спортивный журнал
(95 %, 4 %)

Рис. 3.7. Все значимые ассоциативные правила для

автомобильного журнала

Спортивный журнал Музыкальный журнал Комиксы

(36 %, 45 %) (96 %, 15 %) (57 %, 8 %)

Музыкальный журнал Музыкальный журнал Музыкальный журнал

“Дом” Спортивный журнал Комиксы
(97 %, 9 %) (95 %, 6 %) (100 %, 4 %)
Рис. 3.6 Расширение ассоциативных правил
для автомобильного журнала.

Находим три новых ассоциативных правила:

MUSIC_MAG, HOUSE_MAG = > CAR_MAG
MUSIC_MAG, SPORTS_MAG = > CAR_MAG
MUSIC_MAG, COMIC_MAG = > CAR_MAG
Из этих трех правил только первое относительно интересно: оно имеет высокий уровень доверия (97 %) со сравнительно высокой поддержкой (9 %). На рис.3.7. показано, что произойдет, когда мы решаем расширить это правило.

Спортивный журнал Музыкальный журнал Комиксы

(36 %, 45 %) (96 %, 15 %) (57 %, 8 %)

Музыкальный журнал Музыкальный журнал Музыкальный журнал

“Дом” Спортивный журнал Комиксы
(97 %, 9 %) (95 %, 6 %) (100 %, 4 %)

Музыкальный журнал

“Дом”
Спортивный журнал
(95 %, 4 %)

Рис. 3.7. Все значимые ассоциативные правила для

автомобильного журнала.

Получаем только одно новое правило:

MUSIC_MAG, HOUSE_MAG, SPORTS_MAG = > CAR_MAG,
но доверие и поддержка не увеличивается. Получается, что мы не можем предсказать намного лучше чем, ассоциативное правило, сообщающее нам, что все читатели и музыкального журнала и журнала о доме будут также читать автомобильный журнал с доверием 97 % и поддержкой 9 %. Тем не менее, такое правило могло быть значимым для маркетинга.