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

Определение «интересных» правил. Порядка 50 – 70 % обоб-

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

Пусть Z – это предок Z, где Z и Z – множества элементов, входящих в иерархию (Z ,Z I). Z является предком Z, только в том случае, если Z можно получить из Z путем подмены одного или нескольких элементов их предками. Если рассматривать иерархию на рис. 3.2, то примером могут быть эти два множества: Z = {Сок, Кефир, Бумага}, Z = {Напитки, Молочные продукты, Бумага}. Будем называть правила X Y, X Y и X Y предками правила

X Y.

Определение. Правило X Y является ближайшим предком правила X Y, если не существует такого правила X" Y", что X" Y" – это предок X Y и X Y – это предок X" Y".

Рассмотрим правило X Y. Пусть Z = X Y. Заметим, что supp(X Y) = supp(Z). Назовем EZ[Pr(Z)] ожидаемым значением поддержки Pr(Z) относительно Z. И пусть Z ={z1, …, zj, zj+1, …, zn}, Z ={ z1, …, zj}, 1 <= j <= n. Тогда можно определить:

.

Аналогично EX Y [Pr(Y|X)] определим как ожидаемое значение достоверности правила X Y относительно X Y. Пусть

Y={y1, …, yj, yj+1…, yn}, Y ={ y1, …, yj}, 1<= j <= n. Тогда можно оп-

ределить

.

Определение. Правило X Y называется R-интересным относительно правила-предка X Y, если поддержка самого правила X Y в R раз больше ожидаемой поддержки правила X Y относительно правила-предка X Y или если достоверность самого правила X Y в R раз больше ожидаемой достоверности правила X Y относительно правила-предка.

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

61

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

Пример. Пусть в результате работы алгоритма мы получили правила, перечисленные в табл. 3.3. Поддержка отдельных элементов входящих в правила приведена в табл. 3.4. Иерархия элементов изображена на рис. 3.2. Уровень интереса R = 1.3.

Рассмотрим правило 3 и определим, является ли это правило интересным / частично интересным. Для этого нам необходимо проверить выполнимость неравенства

Pr(Сок Кефир) > EСок Кефир[Pr(Сок Кефир)]*R.

Согласно определениям, ищем ближайших предков к правилу 3. Их два – правило 2 и правило 1. Подсчитаем ожидаемую поддержку для правила 2.

Неравенство

Pr(СокКефир) = 9 > EБезалкогольные напиткиКефир(СокКефир)*R = 11.7

не выполняется, следовательно, правило 3 не является интересным.

62

Подсчитаем ожидаемую поддержку для правила 1.

Неравенство

Pr(СокКефир) = 9 > EСокМолочные продукты(СокКефир)*R = 8.7

выполняется, следовательно, правило 3 является частично интересным.

Теперь с учетом полученных результатов можно сформулировать задачу иначе. Пусть D – это множество транзакций, а I – множество элементов, находящихся в иерархической зависимости. Необходимо найти закономерности, которые являются обобщенными ассоциативными правилами вида X Y. При этом поддержка каждого правила должна быть больше некоторого заданного порогового значения минимальной поддержки и достоверность должна быть больше некоторого заданного порогового значения минимальной достоверности; и кроме этого каждое правило должно быть интересным или частично интересным.

3.5. Алгоритм вычисления обобщенных ассоциативных правил

На первый взгляд может показаться, что для вычисления обобщенных ассоциативных правил можно использовать любой алгоритм выявления ассоциативных правил, дополнив лишь каждую транзакцию предками каждого элемента, входящего в транзакцию [31]. Однако такой метод «в лоб» очень неэффективен и его использование приводит к следующим проблемам:

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

2)появляются избыточные правила, и в условии, и в следствии которых находятся сам элемент и его предок. Примером такого правила, может быть: «Если покупатель купил Кефир, то он, скорее всего, захочет купить Молочные продукты». Очевидно, что практическая ценность такого правила равна нулю при достоверности равной 100 %.

63

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

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

2.Вычисление правил на основе часто встречающихся множеств элементов. Основная идея вычисления правил заключается в следующем. Если ABCD – это часто встречающееся множество элементов, то на основе его можно построить правила X Y, выполняющие условие X Y = ABCD (например, AB CD или A BCD). Поддержка правила при этом равна поддержке часто встречающегося множества. Достоверность правила вычисляется по формуле conf(X Y) = supp(X Y) / supp(X). Правило добавляется к результирующему списку правил, если достоверность его больше порога minconf.

3.Удаление из результирующего списка «неинтересных» пра-

вил.

Базовый алгоритм поиска часто встречающихся множеств.

1.На первом шаге алгоритма подсчитываются одноэлементные часто встречающиеся наборы. Эти элементы могут находиться на любом уровне таксономии. Для подсчета необходимо «пройтись» по всему набору данных и подсчитать для них поддержку, т.е. сколько раз элемент встречается в базе данных.

2.Следующие шаги состоят из двух этапов (по аналогии с алго-

ритмом Apriori):

•генерация потенциально часто встречающихся наборов элементов (их называют кандидатами),

•подсчет поддержки для кандидатов.

Этот базовый алгоритм можно схематично записать в виде псевдокода:

L1 = { Часто встречающиеся множества элементов и групп элементов };

Для ( k=2; Lk-1 <> ; k++ )

{

Ck = { Генерация кандидатов мощностью k на основе Lk-1 }; для всех транзакций t D

{

Расширитьтранзакциюt предкамивсехэлементов, входящихвтранзакцию;

64

Удалить дубликаты из транзакции t; для всех кандидатов с Ck

если с t то c.count++;

}

Lk = { с Ck | c.count >= minsupp }; // Отбор кандидатов

}

Результат = Uk Lk;

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

Алгоритм генерации кандидатов состоит из двух шагов.

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

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

са:

INSERT INTO Ck

SELECT

a.item1, a.item2, …, a.itemk-1, b.itemk-1 FROM

Fk-1 a, Fk-1 b WHERE

a.item1 = b.item1, a.item2 = b.item2, … , a.itemk-2 = b.itemk-2, a.itemk-1 < b.itemk-1

2. Удаление избыточных правил. На основании свойства анти-

монотонности, необходимо удалить все наборы Ck, если хотя бы одно из его (k-1) подмножеств не является часто встречающимся.

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

65

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

3.6. Улучшенный алгоритм поиска часто встречающихся множеств

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

Лемма 1. Поддержка множества X, содержащего и элемент x и его предка x , вычисляется по формуле supp(X)=supp(X-x).

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

Лемма 2. Если Lk – список часто встречающихся множеств, не содержащий множеств, включающих и сам элемент и его предков в одном множестве, то Ck+1 (список кандидатов, получаемых из Lk) также не будет содержать множеств, включающих и сам элемент и его предков.

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

Далее для рационализации действий алгоритма необходимо иметь ввиду, что:

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

66

производится замена этих элементов на их предков. К транзакции добавляются только не удаленные предки;

•нет необходимости также «пропускать» транзакцию через хэш-дерево, если ее мощность меньше чем мощность элементов, расположенных в хэш-дереве;

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

Учитывая приведенные доводы, схема полученного алгоритма будет такой:

// Оптимизация 1-й этап

Вычислить I* - множества предков элементов для каждого элемента; L1 = {Часто встречающиеся множества элементов и групп элементов};

для ( k = 2; Lk-1 <> ; k++ )

{

Ck = {Генерация кандидатов мощностью k на основе Lk-1};

//Оптимизация 2-ой этап если k = 2,то

удалить тех кандидатов из Ck, которые содержат элемент и его предок;

//Оптимизация 3-ий этап

Пометить как удаленные множества предков элемента, который не содержится в списке кандидатов;

для всех транзакций t D

{

// Оптимизация 3 этап для каждого элемента х t

добавить всех предков х из I* к t; Удалить дубликаты из транзакции t; // Оптимизация 4,5 этапы

если (t не помечена как удаленная) и ( |t| >= k), то

{

для всех кандидатов с Ck если с t, то

c.count++;

// Оптимизация 5-ый этап

если в транзакцию t не вошел ни один кандидат то пометить эту транзакцию как удаленную;

}

}

// Отбор кандидатов

Lk = { с >= Ck | c.count >= minsupp };

}

Результат = UkLk;

67

3.7. Прогноз развития

Как было показано в разд. 1, среди всех проанализированных подходов существует только два метода поиска логических закономерностей в виде правил «если-то». Приведем перспективные направления поиска таких логических правил [16 – 18, 29].

Эволюционные алгоритмы. Некоторые исследователи видят путь развития аналитических методов в разработке эволюционных алгоритмов. Среди них наиболее популярными являются генетические алгоритмы [28], пытающиеся моделировать механизмы наследственности, изменчивости и отбора живой природы.

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

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

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

68

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

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

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

У этого метода есть некоторые особенности. Первая из них состоит в том, что для поиска логических закономерностей в данных на основе геометрических представлений необходимо сначала перейти от первичных признаков xi (i = 1, 2, ..., p) к бинарным переменным gk (gk равно либо 0, либо 1), кодирующим элементарные события Т. Результатом перехода к бинарным переменным является пространство событий G, в котором любой объект gk изображается точкой, расположенной в какой-либо вершине q-мерного единичного гиперкуба.

С другой стороны, этот же объект представляет собой конъюнкцию элементарных событий. Он заключает в себе логическое выражение А, являющееся ядром логического правила IF (A) THEN (B). За счет такой двойственности представления объекта дальнейшая комбинаторная процедура поиска логических закономерностей получает геометрическое толкование. Исходные комбинаторные ситуации выглядят как точки в бинарном пространстве, и задача поиска логических закономерностей может быть сведена к проецированию точек исходного пространства событий в подпространства событий меньшей размерности, где логические закономерности выглядят как точки этих подпространств, в которые попадает определенное количество объектов одинакового класса.

69