Зайцев Применение методов Дата Мининг для поддержки процессов управления ИТ-услугами.Учебное пособие 2009

дилось к тому, присутствует в транзакции элемент или нет. Т.е. если рассматривать случай рыночной корзины, то мы рассматривали два состояния: куплен товар или нет, проигнорировав, например, информацию о том, сколько было куплено, кто купил, характеристики покупателя и т.д. Можно сказать, что рассматривали «булевские» ассоциативные правила. Если взять любую базу данных, каждая транзакция состоит из различных типов данных: числовых, категориальных и т.д. Для обработки таких записей и извлечения численных ассоциативных правил в работе [12] был предложен специальный алгоритм

Приведем пример численного ассоциативного правила.

[Возраст: 30-35] и [Семейное положение: женат] [Месячный доход: 1000-1500 ден. единиц].

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

3.2. Анализ возможностей и ограничений метода поиска ассоциативных правил

При помощи использования алгоритмов поиска ассоциативных правил аналитик может получить правила вида «Из A следует B» [29], с различными значениями поддержки и достоверности.

Однако в большинстве случаев количество правил необходимо ограничивать заранее установленными минимальными и максимальными значениями поддержки и достоверности.

Если значение поддержки правила слишком велико, то в результате работы алгоритма будут найдены правила очевидные и хорошо известные. Слишком низкое значение поддержки приведет к нахождению очень большого количества правил, которые, возможно, будут в большей части необоснованными, но не известными и не очевидными для аналитика. Таким образом, необходимо определить такой интервал, «золотую середину», который, с одной стороны, обеспечит нахождение неочевидных правил, а с другой их обоснованность.

51

Если уровень достоверности слишком мал, то ценность правила вызывает серьезные сомнения. Например, правило с достоверностью в 3% только условно можно назвать правилом.

Области эффективного применения метода поиска ассоциа-

тивных правил. Алгоритмы выявления ассоциативных правил нашли свое применение в основном в анализе объектов типа «покупательская корзина» [30]:

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

•розничная торговля: определение товаров, которые стоит продвигать совместно; выбор местоположения товара в магазине; анализ потребительской корзины; прогнозирование спроса;

•перекрестные продажи: если есть информация о том, что клиенты приобрели продукты A, Б и В, то какие из них вероятнее всего купят продукт Г;

•маркетинг: поиск рыночных сегментов, тенденций покупательского поведения;

•сегментация клиентов: выявление общих характеристик клиентов компании, выявление групп покупателей;

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

•анализ Web-логов.

3.3. Алгоритм Apriori

Современные базы данных могут иметь очень большие размеры, достигающие многих гига- и даже терабайтов, и главное – тенденцию к дальнейшему их увеличению. Поэтому, для нахождения ассоциативных правил требуются эффективные масштабируемые алгоритмы [21, 31], позволяющие решать задачу выделения правил за приемлемое время. Одним из таких алгоритмов является алгоритм Apriori. Для того чтобы было можно применить алгоритм, необходимо сначала провести предобработку исходных данных (табл. 3.1) в два этапа: во-первых, привести все данные к бинарному виду; и во-вторых, изменить структуру данных, так чтобы количество

52

столбцов в таблице было равно количеству элементов (табл. 3.2), присутствующих во множестве транзакций D. Каждая запись теперь соответствует транзакции, где в соответствующем столбце стоит 1, если элемент присутствует в транзакции, и 0, если не присутствует. Заметим, что исходный вид таблицы может быть отличным от приведенного в табл. 3.2. Главное, чтобы данные были преобразованы к нормализованному виду, иначе алгоритм будет неприменим.

Таблица 3.1

Обычный вид базы данных транзакций

Номер транзакции	Наименование элемента	Количество
1001	А	2
1001	D	3
1001	E	1
1002	А	2
1002	F	1
1003	B	2
1003	A	2
1003	C	2
…	…	…

									Таблица 3.2
			Нормализованный вид
	A
TID		B	C	D	E		F	G	H	…
1001	1	0	0	1	1		0	0	0	…
1002	1	0	0	0	0		1	0	0	…
1003	1	1	1	0	0		0	0	0	…

Как видно из таблицы, все элементы упорядочены в алфавитном порядке (если это числа, они должны быть упорядочены в числовом порядке). Это сделано неслучайно. Итак, данные преобразованы, теперь можно приступить к описанию самого алгоритма. В алгоритме Apriori на первом шаге необходимо найти часто встречающиеся наборы элементов, а затем, на втором, извлечь из них правила. Количество элементов в наборе будем называть размером набора, а набор, состоящий из k элементов, – k-элементным набором.

53

Свойство анти-монотонности. Выявление часто встречающихся наборов элементов – операция, требующая значительных вычислительных ресурсов и, соответственно, времени. Примитивный подход к решению данной задачи – простой перебор всех возможных наборов элементов. Это потребует O(|I|2) операций, где |I| – количество перебираемых элементов. Apriori использует одно из свойств поддержки – поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора будет всегда меньше или равна поддержке 2-элементных наборов. Дело в том, что любая транзакция, содержащая 3-элементный набор, также должна содержать все 2-элементные наборы, причем обратное не верно.

Это свойство носит название анти-монотонности и служит для снижения размерности пространства поиска. Не имей мы в наличии такого свойства, нахождение многоэлементных наборов было бы практически невыполнимой задачей в связи с экспоненциальным ростом объема вычислений.

Свойству анти-монотонности можно дать и другую формулировку: с ростом размера набора элементов поддержка уменьшается, либо остается такой же. Из всего вышесказанного следует, что любой k-элементный набор будет часто встречающимся тогда и только тогда, когда все его (k-1)-элементные подмножества будут часто встречающимися.

Все возможные наборы элементов из I можно представить в виде решетки, начинающейся с пустого множества, затем на 1-м уровне одноэлементные наборы, на 2-м – 2-элементные и т.д. На k- м уровне представлены k-элементные наборы, связанные со всеми своими (k-1)-элементными подмножествами.

Рассмотрим рис. 3.1, иллюстрирующий набор элементов I – {A, B, C, D}. Предположим, что набор из элементов {A, B} имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся. Тогда, согласно свойству анти-монотонности, все его супермножества также не являются часто встречающимися и отбрасываются. Вся эта ветвь, начиная с {A, B}, выделена тоном. Использование этой эвристики позволяет существенно сократить пространство поиска.

54

Описание алгоритма. Алгоритм является итерационным. Сначала действия выполняются для одноэлементных наборов, а затем для 2-х, 3-х и т.д. элементных.

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

Рис. 3.1. Набор элементов I – {A, B, C, D}

Описанный шаг 1 алгоритма можно записать в виде некоторого псевдокода:

F1 = {часто встречающиеся одноэлементные наборы}

для (k=2; Fk-1 <> k++ - «увеличивая k последовательно на 1») { Ck = Apriorigen(Fk-1) // генерация кандидатов для всех транзак-

ций t T {

55

Ct = subset(Ct , t) // удаление избыточных правил для всех кандидатов c Ct

c.count

}

Fk = { c Ck | c.count >= minsupport} // отбор кандидатов

}

Результат U Fk

Шаг 1. Генерация кандидатов. При поиске многоэлементных наборов нет необходимости обращаться к базе данных, как было в случае одноэлементных наборов. Для того чтобы получить k- элементные наборы, воспользуемся (k-1)-элементными наборами, которые были определены на предыдущей итерпации алгоритма и являются часто встречающимися. Помним, что наш исходный набор хранится в упорядоченном виде. Генерация кандидатов также состоит из двух фаз – формирование новых и удаление избыточных кандидатов.

Формирование. Каждый кандидат Ck будет формироваться путем расширения часто встречающегося набора размера (k-1) добавлением элемента из другого (k-1)- элементного набора.

Приведем алгоритм этой функции Apriorigen в виде небольшого SQL-подобного запроса.

insert into Ck

select p.item1, p.item2, …, p.itemk-1, q.itemk-1 From Fk-1 p, Fk-1 q

where p.item1= q.item1, p.item2 = q.item2, … , p.itemk-2 = q.itemk- 2, p.itemk-1 < q.itemk-1

Удаление. На основании		свойства анти-монотонности, следу-
ет удалить все наборы c		Ck если хотя бы одно из его (k-1) под-

множеств не является часто встречающимся.

Шаг 1. Подсчет поддержки. После генерации кандидатов следующим этапом шага алгоритма является подсчет поддержки для каждого кандидата. Очевидно, что количество кандидатов может быть очень большим и нужен эффективный способ подсчета. Самый тривиальный способ – сравнить каждую транзакцию с каждым кандидатом. Но это не лучшее решение. Гораздо быстрее и эффективнее использовать подход, основанный на хранении кандидатов в

56

хэш-дереве. Внутренние узлы дерева содержат хэш-таблицы с указателями на потомков, а листья – на кандидатов. Это дерево нам пригодится для быстрого подсчета поддержки кандидатов.

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

Хэш-дерево с кандидатами-наборами построено, теперь, используя хэш-дерево, легко подсчитать поддержку для каждого кандидата. Для этого нужно «пропустить» каждую транзакцию через дерево и увеличить счетчики для тех кандидатов, чьи элементы также содержатся и в транзакции, т.е. Ck Ti = Ck. На корневом уровне хэш-функция применяется к каждому элементу из транзакции. Далее, на втором уровне, хэш-функция применяется ко вторым элементам и т.д. На k-уровне хэшируется k-элемент. И так до тех пор, пока не достигнем уровня листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, тогда увеличиваем счетчик поддержки этого кандидата на единицу.

После того, как каждая транзакция из исходного набора данных «пропущена» через дерево, можно проверить удовлетворяют ли значения поддержки кандидатов минимальному порогу. Кандидаты, для которых это условие выполняется, переносятся в разряд часто встречающихся. Кроме того, следует запомнить и поддержку набора, она нам пригодится при извлечении правил. Эти же действия применяются для нахождения (k+1)-элементных наборов и т.д.

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

Шаг 2. Извлечение правил – менее трудоемкая задача. Во-первых, для подсчета достоверности правила достаточно знать поддержку

57

самого набора и множества, лежащего в условии правила. Например, имеется часто встречающийся набор {A, B, C} и требуется подсчитать достоверность для правила AB C. Поддержка самого набора нам известна, но и его множество {A, B}, лежащее в условии правила, также является часто встречающимся в силу свойства антимонотонности, и, значит, его поддержка нам известна. Тогда мы легко сможем подсчитать достоверность. Это избавляет нас от нежелательного просмотра базы транзакций, который потребовался бы в том случае, если бы эта поддержка была неизвестна.

Чтобы извлечь правило из часто встречающегося набора F, следует найти все его непустые подмножества. И для каждого подмножества s мы сможем сформулировать правило s (F – s), если достоверность правила conf(s (F – s)) = supp(F)/supp(s) не меньше порога minconf.

Заметим, что числитель остается постоянным. Тогда достоверность имеет минимальное значение, если знаменатель имеет максимальное значение, а это происходит в том случае, когда в условии правила имеется набор, состоящий из одного элемента. Все супермножества данного множества имеют меньшую или равную поддержку и, соответственно, большее значение достоверности. Это свойство может быть использовано при извлечении правил. Если мы начнем извлекать правила, рассматривая сначала только один элемент в условии правила, и это правило имеет необходимую поддержку, тогда все правила, где в условии стоят супермножества этого элемента, также имеют значение достоверности выше заданного порога. Например, если правило A BCDE удовлетворяет минимальному порогу достоверности minconf, тогда AB CDE также удовлетворяет. Для того, чтобы извлечь все правила, используется рекурсивная процедура. Важное замечание – любое правило, составленное из часто встречающегося набора, должно содержать все элементы набора. Например, если набор состоит из элементов {A, B, C}, то правило A B не должно рассматриваться.

3.4. Выявление обобщенных ассоциативных правил

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

58

Рассмотрим пример иерархии товаров и товарных групп приведенный на рис. 3.2 [26]. Имея подобную иерархию, можно получить, например, такие правила: «Если покупатель купил Сок, то он, скорее всего, захочет купить Кефир»; «Если покупатель купил Молочные продукты, то он, скорее всего, захочет купить Минеральную воду». Таким образом, в получаемых правилах, как в условии, так и в следствии могут присутствовать элементы, находящиеся на разных уровнях таксономии.

Рис. 3.2. Пример иерархии товаров и товарных групп

Введение информации о принадлежности элементов транзакций

ктой или иной группе может дать следующие преимущества:

•будут выявлены ассоциативные правила не только между отдельными элементами, но и между различными уровнями иерархии;

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

59

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

Введение информации о группировке элементов может использоваться для отсечения «неинтересных» правил.

Описание задачи. Пусть I={i1, i2, …, in} –множество элементов – лес направленных деревьев. Дуги в I – это зависимости между элементами. Пусть элементы, принадлежащие I, расположены в некой иерархии. Если имеется дуга от a к b, то говорят, что a – предок b, или b – потомок a (т.е. a – есть некоторое обобщение b).

Пусть имеется множество транзакций D, где каждая транзакция T – это множество элементов (событий), произошедших одновременно. Тогда имеет место следующее утверждение: T I.

Определение. Расширенной транзакцией называется транзакция, расширенная предками всех элементов, входящих в эту транзакцию.

Определение. Обобщенным ассоциативным правилом называ-

ется импликация X

Y, где X

I, Y

I и X

Y = , и где ни один

из элементов, входящих в набор Y, не является предком ни одного

элемента, входящего в X. Правило X

Y имеет поддержку

s

(support), если s%

расширенных транзакций содержит X

Y,

supp(X Y) = supp(X

Y). Достоверность правила показывает, ка-

кова вероятность того, что из X следует Y. Правило X Y справедливо с достоверностью c, если c% расширенных транзакций, содержащих X, также содержат Y, conf(X Y) = supp(X Y)/supp(X).

Будем называть правило X Y обобщенным, потому что элементы, входящие в него могут находиться на любом уровне таксономии. Также будем называть x предком x и x потомком x.

Задача. Пусть D – это множество транзакций, а I – множество элементов, находящихся в иерархической зависимости. Необходимо найти закономерности, которые являются обобщенными ассоциативными правилами вида X Y, причем supp(X Y) >= minsupp и conf(X Y) >= minconf.

Такая постановка задачи имеет одну неприятность. Дело в том, что при поиске обобщенных ассоциативных правил будут заведомо найдены «лишние», не представляющие интереса для предметной области, правила. Для их устранения вводится такой параметр, как «уровень интереса правила».

60