Секвенциальный анализ

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

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

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

, где p<q.

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

S= {(вода, 02.03.2003), (чипсы, 05.03.2003), (пиво, 10.03.2003)}

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

Различают два вида последовательностей: с циклами и без циклов. В первом случае допускается вхождение в последовательность одного и того же объекта на разных позициях:

, где p<q, а

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

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

Задачей секвенциального анализа является поиск всех частых последовательностей:

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

Например, при анализе последовательности покупок в супермаркете наборами являются покупки, совершаемые в разное время одними и теми же покупателями, а отношением порядка в них является хронология покупок:

D = {(вода), (пиво)},

{(кокосы, вода), (пиво), (вода, шоколад, кокосы)},

{(пиво, чипсы, вода), (пиво)}}.

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

Таблица 3

ID покупателя	Последовательность покупок
0	(Пиво), (вода)
1	(Кокосы, вода), (пиво), (вода, шоколад, кокосы)
2	(Пиво, чипсы, вода), (пиво)

Интерпретировать такую последовательность можно следующим образом: покупатель с идентификатором 1 вначале купил кокосы и воду, затем купил пиво, в последний раз он купил воду, шоколад и кокосы.

Поддержка, например, последовательности {(пиво), (вода)} составит 2/3, т. к. она встречается у покупателей с идентификаторами 0 и 1. У последнего покупателя также встречается набор {(пиво), (вода)}, но не сохраняется последовательность (он купил вначале воду, а затем пиво).

Секвенциальный анализ актуален и для телекоммуникационных компаний. Основная проблема, для решения которой он используется, – это анализ данных об авариях на различных узлах телекоммуникационной сети. Информация о последовательности совершения аварий может помочь в обнаружении неполадок и предупреждении новых аварий. Данные для такого анализа могут быть представлены, например, в виде таблице 4.

Таблица 4

Дата	Время	Источник ошибки	Код источника	Код ошибки	...
01.01.03	15:04:23	Станция 1	1001	a
01.01.03	16:45:46	Станция 1	1001	f
01.01.03	18:32:26	Станция 4	1004	q
01.01.03	20:07:11	Станция 5	1005	h
01.01.03	20:54:43	Станция 1	1001	q

В данной задаче объектами множества I являются коды ошибок, возникающих в процессе работы телекоммуникационной сети. Последовательность S_sid содержит сбои, происходящие на станции с идентификатором s_id. Их можно представить в виде пар (e_id, t), где e_id – код ошибки, а t – время, когда она произошла. Таким образом, последовательность сбоев на станции с идентификатором s_id будет иметь следующий вид:

Для данных, приведенных в табл. 6.4, транзакции будут следующие:

T₁₀₀₁ = {(а, 15:04:23 01.01.03), (f, 16:45:46 01.01.03), (q, 20:54:43 01.01.03),…};

T₁₀₀₄={(z, 18:32:26 01.01.03),...};

T₁₀₀₅ = {(h, 20:07:11 01.01.03),...}.

Отношение порядка в данном случае задается относительно времени появления ошибки (значения t).

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

Рис.1. Последовательность сбоев на телекоммуникационной станции