Постановка задачи Опишем эту задачу в обобщенном виде. Для этого обозначим объекты, составляющие исследуемые наборы (itemsets), следующим множеством: I={i 1, i 2,… i j,…, i n }, где i j объекты, входящие в анализируемые наборы; n общее количество объектов. В сфере торговли, например, такими объектами являются товары, представленные в прайс-листе (табл. 6.1).

Таблиuа 6.1 Они соответствуют следующему множеству объектов: I={шоколад,чипсы,кокосы,вода,пиво,орехи}. Описание транзакции: T={i j |i i I} идентификатор Наименование товара цена 0Шоколад Чипсы Кокосы Вода Пиво Орехи 15.00

Т 1 = {чипсы, вода, пиво}; Т 2 ={кокосы, вода, орехи} Набор транзакций, информация о которых доступна для анализа, обозначим следующим множеством: D={T 1, T 2,… T r,…, T m } Где m-количество доступных для анализа транзакций. Например, в магазине таким множеством будет: D={{чипсы,вода,пиво}, {кокосы,вода,орехи}, {орехи,кокосы,чипсы,кокосы,вода}, {кокосы,орехи,кокосы}} Для использования методов Data Mining множество D может быть представлено в виде табл. 6.2.

Таблица 6.2 Номер транзакции Номер товара Наименование товара цена 01Чипсы 12,00 03Вода 4,00 04Пиво 14,00 12Кокосы 10,00 13Вода 4,00 15Орехи 15,00 25Орехи 15,00 22Кокосы 10,00 21Чипсы 12,00 22Кокосы 10,00 23Вода 4,00 32Кокосы 10,00 35Орехи 15,00 32Кокосы 10,00

Множество транзакций, в которые входит объект i j, обозначим следующим образом: D i j ={T r |i j T r ; j=1..n; r=1..m} D В данном примере множеством транзакций, содержащих объект вода, является следующее множество: D вода = {{чипсы, вода, пиво}, {кокосы, вода, орехи}, {орехи, кокосы, чипсы, кокосы, вода}}. Некоторый произвольный набор объектов (itemset) обозначим следующим образом: F={i j |i j I;j=1..n}. Например, F={кокосы,вода}. D F ={T r |F T r ; r=1..n; r=1..m} D

Таким образом, при поиске ассоциативных правил требуется найти множество всех частых наборов: L={F|Supp(F)>Supp min } В данном примере частными наборами при Supp min =0,5 являются следующие: {чипсы} = Supp min 0,5; {чипсы, вода} Supp min = 0,5; {кокосы} Supp min = 0,75; {кокосы, вода} Supp min = 0,5; {кокосы, вода, орехи} Supp min = 0,5; {кокосы, орехи} Supp min = 0,75; {вода} Supp min = 0,75; {вода, орехи} Supp min = 0,5; {орехи} Supp min = 0,75

Секвенциальный анализ Последовательностью называется упорядоченное множество объектов. Для этого на множестве должно быть задано отношение порядка. Тогда последовательность объектов можно описать в следующем виде: S={…,i p,…,i q }, где p

Поддержкой последовательности S называется отношение количества транзакций, в которое входит последовательность S, к общему количеству транзакций. Последовательность является частой, если ее поддержка превышает минимальную поддержку, заданную пользователем: Supp(S)>Supp min Задачей секвенциального анализа является поиск всех частых последовательностей: L={S|Supp(S)>Supp min } Например, при анализе последовательности покупок в супермаркете наборами являются покупки, совершаемые в разное время одними и теми же покупателями, а отношением порядка в них является хронология покупок: D={{(вода),(пиво)), {(кокосы, вода), (пиво), (вода, шоколад, кокосы)}, {(пиво, чипсы, вода), (пиво)}}.

Таблица 6.3 ID покупателя Последовательность покупок 0(пиво),(вода) 1(кокосы,вода),(пиво),(вода,шоколад,кокосы) 2(пиво,чипсы,вода)(пиво) Интерпретировать такую последовательность можно следующим образом: покупатель с идентификатором 1 вначале купил кокосы и воду, затем купил пиво, в последний раз он купил воду, шоколад и кокосы. Поддержка, например, последовательности {(пиво), (вода)} составит 2/3, т. к. она встречается у покупателей с идентификаторами 0 и 1.

У последнего покупателя также встречается набор {(пиво), (вода)}, но не сохраняется последовательность (он купил вначале воду, а затем пиво). Таблица 6.4 Дата ВремяИсточник ошибки Код источника Код ошибки… :04:23Станция 11001a… :45:46Станция 11001f… :32:26Станция 41004z… :07:11Станция 51005h… :54:43Станция 11001q… ………………

В данной задаче объектами множества I являются коды ошибок, возникающих в процессе работы телекоммуникационной сети. Последовательность S sid содержит сбои, происходящие на станции с идентификатором sid. Их можно представить в виде пар (eid, t), где eid код ошибки, а t время, когда она произошла. Таким образом, последовательность сбоев на станции с идентификатором sid будет иметь следующий вид: S sid ={{eid 1, t 1 ),(eid 2, t 2 ),…,(eid n, t n )}. Для данных, приведенных в табл. 6.4, транзакции будут следующие: T 1001 ={(a,15:04: ),(f,16:45: ),(q,20:54: ),…}; T 1004 ={(z,18:32: ),…}; T 1005 ={(h,20:07: ),…}.

При анализе такой последовательности важным является определение интервала времени между сбоями. Оно позволяет предсказать момент и характер новых сбоев, а следовательно,предпринять профилактические меры. По этой причине при анализе данных интерес вызывает не просто последовательность событий, а сбои, которые происходят друг за другом. Например, на рис. 6.1 изображена временная шкала последовательности сбоев, происходящих на одной станции. При определении поддержки, например, для последовательности {А, С} учитываются только следующие наборы: {(А, 0: 12), (С, 0:25)}, {(А, 0:38), (С, 1 :42)}, {(А, 1 :25), (С, 1 :42)}. При этом не учитываются следующие последовательности: {(А, 0:12), (С, 1:42)}, {(А, 0:12), (С, 1:51)}, {(А, 0:38), (С, ]:51)} и {(А, 1:25), (С, 1:51)}, т. к. они не следуют непосредственно друг за другом. Отношение порядка в данном случае задается относительно времени появления ошибки (значения t).

Разновидности задачи поиска ассоциативных правил Рис.6.2. Иерархическое представление объектов множества I Для примера, приведенного в табл. 6.1, такой иерархии может быть следующая категоризация товаров: напитки; еда; алкогольные; шоколад; пиво; чипсы безалкогольные; кокосы; вода; орехи.

Представление результатов Результаты, получаемые при решении этой задачи, принято представлять в виде ассоциативных правил. В связи с этим при их поиске выделяют два основных этапа: нахождение всех частых наборов объектов; генерация ассоциативных правил из найденных частых наборов объектов. Ассоциативные правила имеют следующий вид: если (условие) то (результат) где условие обычно не логическое выражение (как в классификационных правилах), а набор объектов из множества I, с которыми связаны (ассоциированы) объекты, включенные в результат данного правила.

Например, ассоциативное правило: если (кокосы, вода) то (орехи) означает, что если потребитель покупает кокосы и воду, то он покупает и орехи. Как уже отмечалось, в ассоциативных правилах условие и результат являются объектами множества I : если X то Y где X I,Y I, X Y = φ. Ассоциативное правило можно представить как импликацию над множеством X Y, где X I,Y I, X Y = φ. Основным достоинством ассоциативных правил является их легкое восприятие человеком и простая интерпретация языками программирования. Однако они не всегда полезны. Выделяют три вида правил:

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

Такие правила могут быть получены или на основе аномальных значений, или глубоко скрытых знаний. Напрямую такие правила нельзя использовать для принятия решений, т. к. их необъяснимость может привести к непредсказуемым результатам. Для лучшего понимания требуется дополнительный анализ. Ассоциативные правила строятся на основе частых наборов. Так, правила,построенные на основании набора F (т. е. X Y = F ), являются всеми возможными комбинациями объектов, входящих в него.

Например, для набора {кокосы, вода, орехи} могут быть построены следующие правила: если (кокосы) то (вода); если (кокосы) то (орехи); если (кокосы) то (вода, орехи); если (вода, орехи) то (кокосы); если (вода) то (кокосы); если (вода) то (орехи); если (вода) то (кокосы, орехи); если (кокосы, орехи) то (вода); если (орехи) то (вода); если (орехи) то (кокосы); если (орехи) то (вода, кокосы); если (вода, кокосы) то (орехи).

Очевидно, что чем больше достоверность, тем правило лучше, причем у правил, построенных на основании одного и того же набора, достоверность будет разная, например: Conf если(вода) то (орехи)= 2/3; Conf если(орехи) то (вода)= 2/3; Conf если(вода,кокосы) то (орехи )=1; Conf если(вода) то (орехи,кокосы )=2/3; К сожалению, достоверность не позволяет оценить полезность правила,поэтому ввели следующую величину: Улучшение (improvement) показывает, полезнее ли правило случайного угадывания. Улучшение правила является отношением числа транзакций, содержащих наборы X и Y, к произведению количества транзакций, содержащих набор X, и количества транзакций, содержащих набор Y :.

Алгортим Apriori Он использует одно из свойств поддержки, гласящее: поддержка любого набора объектов не может превышать минимальной поддержки любого из его подмножеств: Supp F Supp E при E F Например, поддержка 3-объектного набора {пиво, вода, чипсы} будет всегда меньше или равна поддержке 2-объектных наборов {пиво, вода}, {вода,чипсы}, {пиво, чипсы}. Это объясняется тем, что любая транзакция, содержащая {пиво, вода, чипсы}, содержит также и наборы {пиво, вода}, {вода, чипсы},{пиво, чипсы}, причем обратное неверно. L 1 = {часто встречающиеся 1-элементные наборы} для (k=2; L k-1 φ; k++)

C k = Apriorigen(Fk-1) // генерация кандидатов для всех транзакций t D выполнить C t = subset(C k, t) // удаление избыточных правил для всех кандидатов c Ct выполнить c.count ++ конец для всех L k = { c C k | c.count >= Supp min } // отбор кандидатов конец для Результат = L k k L k -множество k-элементных частых наборов, чья поддержка не меньше заданной пользователем. Каждый член множества имеет набор упорядоченных ( Ij < Ip,если j < p ) элементов F и значение поддержки набора Supp F >Supp min :

C k -множество кандидатов k -элементных наборов потенциально частых. Каждый член множества имеет набор упорядоченных ( ij< ip, если j < p ) элементов F и значение поддержки набора Supp. Опишем данный алгоритм по шагам. Шаг 1. Присвоить k = 1 и выполнить отбор всех 1-элементных наборов,у которых поддержка больше минимально заданной пользователем Supp min. Шаг 2. k = k +1. Шаг 3. Если не удается создавать k-элементные наборы, то завершить алгоритм, иначе выполнить следующий шаг. Шаг 4. Создать множество k-элементных наборов кандидатов в частые наборы. Для этого необходимо объединить в k- элементные кандидаты (k – 1)-элементные частые наборы. Каждый кандидат c Ck будет формироваться путем добавления к (k – 1)-элементному частому набору p элемента из другого (k – 1)-элементного частого набора q.

Причем добавляется последний элемент набора q, который по порядку выше, чем последний элемент набора p (p.item k–1 < q.item k–1 ). При этом первые все (k – 2) элемента обоих наборов одинаковы (p.item 1 = q.item 1, p.item 2 = q.item 2,..., p.item k–2 = q.item k–2 ). Это может быть записано в виде следующего SQL-подобного запроса. insert into C k select p.item 1, p.item 2,..., p.item k-1, q.item k-1 from L k-1 p, L k-1 q where p.item 1 = q.item 1, p.item 2 = q.item 2,..., p.item k-2 = q.item k-2, p.item k-1 < q.item k-1

Шаг 5 Для каждой транзакции Т из множества D выбрать кандидатов Ct из множества C k, присутствующих в транзакции Т. Для каждого набора из построенного множества C k удалить набор, если хотя бы одно из его (k – 1)подмножеств не является часто встречающимся, т. е. отсутствует во множестве L k-1. Это можно записать в виде следующего псевдокода: для всех наборов c C k выполнить для всех (k-1) – поднаборов s из c выполнить если (s L k-1 ) то удалить c из C k Шаг 6 Для каждого кандидата из множества C k увеличить значение поддержки на единицу.

Шаг 7 Выбрать только кандидатов L k из множества C k, у которых значение поддержки больше заданной пользователем Supp min. Вернуться к шагу 2. Результатом работы алгоритма является объединение всех множеств L k всех k. Рассмотрим работу алгоритма на примере, приведенном в табл. 6.1, при Supp min = 0,5. На первом шаге имеем следующее множество кандидатов C 1 (указываются идентификаторы товаров) (табл. 6.5). Таблица 6.5 НаборSupp 1{0}0 2{1}0,5 3{2}0,75 4{4}0,25 5{3}0,75 6{5}0,75

Заданной минимальной поддержке удовлетворяют только кандидаты 2, 3, 5 и 6, следовательно: L1={{1},{2},{3},{5}}. На втором шаге увеличиваем значение k до двух. Так как можно построить 2-элементные наборы, то получаем множество C 2 (табл. 6.6). Таблица 6.6 НаборSupp 1{1,2}0,25 2{1,3}0,5 3{1,5}0,25 4{2,3}0,5 5{2,5}0,75 6{3,5}0,5

Из построенных кандидатов заданной минимальной поддержке удовлетворяют только кандидаты 2, 4, 5 и 6, следовательно: L 2 ={{1,3},{2,3},{2,5},{2,5}}. На третьем шаге перейдем к созданию 3-элементных кандидатов и подсчету их поддержки. В результате получим следующее множество C 3 (табл. 6.7). Данный набор удовлетворяет минимальной поддержке, следовательно: L 3 = {{2,3,5}} Так как 4-элементные наборы создать не удастся, то результатом работы алгоритма является множество: L=L 1 L 2 L 3 = {{1}, {2}, {3}, {5}, {1, 3}, {2, 3}, {2, 5}, {3, 5}, {2, 3, 5}}. НаборSupp 1{2,3,5}0,5

После построения хэш-дерево с кандидатами-наборами,легко подсчитать поддержку для каждого кандидата. Для этого нужно "пропустить" каждую транзакцию через дерево и увеличить счетчики для тех кандидатов, чьи элементы также содержатся и в транзакции, C k T i =C k

Выводы Задачей поиска ассоциативных правил является определение часто встречающихся наборов объектов в большом множестве наборов. Секвенциальный анализ заключается в поиске частых последовательностей. Основным отличием задачи секвенциального анализа от поиска аcсоциативных правил является установление отношения порядка между объектами. Наличие иерархии в объектах и ее использование в задаче поиска ассоциативных правил позволяет выполнять более гибкий анализ и получать дополнительные знания.

Результаты решения задачи представляются в виде ассоциативных правил, условная и заключительная часть которых содержит наборы объектов. Основными характеристиками ассоциативных правил являются поддержка, достоверность и улучшение. Поддержка (support) показывает, какой процент транзакций поддерживает данное правило. Достоверность (confidence) показывает, какова вероятность того, что из наличия в транзакции набора условной части правила следует наличие в ней набора заключительной части. Улучшение (improvement) показывает, полезнее ли правило случайного угадывания.

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