|
Tiooi = {(a, 15:04:23 01.01.03), (f, 16:45:46 01.01.03),(q, 20:54:43 01.01.03),...}; Ti004 = {(z, 18:32:26 01.01.03),...}; Tioos = {(h, 20:07:11 01.01.03),...}. Отношение порядка в данном случае задается относительно времени появления ошибки (значения t). (А, 0:12) (С, 0:25) (А, 0:38) (D, 0:53) (А, 1:25) (С, 1:42) (С. 1:51) I-----AJ------А_-----Ж_—А___________ J___ А I А I А I 0:00 0:15 0:30 0:45 1:00 1:15 1:30 1:45 2:00 Рисунок 5 Последовательность сбоев на телекоммуникационной станции. При анализе такой последовательности важным является определение интервала времени между сбоями. Оно позволяет предсказать момент и характер новых сбоев, а следовательно, предпринять профилактические меры. По этой причине при анализе данных интерес вызывает не просто последовательность событий, а сбои, которые происходят друг за другом. Например, на рис. 5 изображена временная шкала последовательности сбоев, происходящих на одной станции. При определении поддержки, например, для последовательности (А, С} учитываются только следующие наборы: {(А, 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)}, т. к. они не следуют непосредственно друг за другом. 3.1.3. Разновидности задачи поиска ассоциативных правил Во многих прикладных областях многоверсионные объекты множества I естественным образом объединяются в группы, которые в свою очередь также могут объединяться в более общие группы, и т. д. Таким образом, получается иерархическая структура объектов, которая представленная в одноверсионном исполнении на рис. 6. 81 |
Последовательностью называется упорядоченное множество объектов. Для этого на множестве должно быть задано отношение порядка. Тогда последовательность объектов можно описать в следующем виде: ...},...,,{..., qp iiS = , где pq < . Различают два вида последовательностей: с циклами и без циклов. В первом случае допускается вхождение в последовательность одного и того же объекта на разных позициях: ...},...,,{..., qp iiS = , где pq < , а pq ii = . Говорят, что транзакция T содержит последовательность S , если TS ⊆ и объекты, входящие в S входят и в множество T с сохранением отношения порядка. При этом допускается, что в множестве T между объектами из последовательности S могут находиться другие объекты. Поддержкой последовательности S называется отношение количества транзакций, в которое входит последовательность ,S к общему количеству транзакций. Последовательность является частой, если ее поддержка превышает минимальную поддержку, заданную пользователем: min)( SuppSSupp > . Задачей сиквенциального анализа является поиск всех частых последовательностей: })({ minSuppSSuppSL >= . Основным отличием задачи сиквенциального анализа от поиска ассоциативных правил является установление отношения порядка между объектами множества .I Данное отношение может быть определено разными способами. При анализе последовательности событий, происходящих во времени, объектами множества I являются события, а отношение порядка соответствует хронологии их появления. Сиквенциальный анализ актуален и для телекоммуникационных компаний. Основная проблема, для решения которой он используется, – это анализ данных об авариях на различных узлах телекоммуникационной сети. Информация о последовательности совершения аварий может помочь в обнаружении неполадок и предупреждении новых аварий. Разновидности задачи поиска ассоциативных правил. Во многих прикладных областях объекты множества I естественным образом объединяются в группы, которые в свою очередь также могут объединяться в более общие группы, и т.д. Наличие иерархии изменяет представление о том, когда объект i присутствует в транзакции .T Очевидно, что поддержка не отдельного объекта, а группы, в которую он входит, больше: )()( j g q iSuppISupp ≥ , где g qj Ii ∈ . Это связано с тем, что при анализе групп подсчитываются не только транзакции, в которые входит отдельный объект, но и транзакции, содержащие все объекты анализируемой группы. Использование иерархии позволяет определить связи, входящие в более высокие уровни иерархии, поскольку поддержка набора может увеличиваться, если подсчитывается вхождение группы, а не ее объекта. Кроме поиска наборов, часто встречающихся в транзакциях, состоящих из объектов }{ IiiF ∈= или групп одного уровня иерархии }{ 1+ ∈= ggg IIIF , можно рассматривать также смешанные наборы объектов и групп },,{ 1+ ∈= ggg IIiIiF . Это позволяет расширить анализ и получить дополнительные знания. При иерархическом построении объектов можно варьировать характер поиска, изменяя анализируемый уровень. Очевидно, что чем больше объектов в множестве I , тем больше объектов в транзакциях T и частых наборах. Это в свою очередь увеличивает время поиска и усложняет анализ результатов. Уменьшить или увеличить количество данных можно с помощью иерархического представления анализируемых объектов. Перемещаясь вверх по иерархии, обобщаем данные и уменьшаем из количество, и наоборот. Недостатком обобщения объектов является меньшая полезность полученных знаний, т.е. в этом случае они относятся к группам товаров, что не всегда приемлемо. Для достижения компромисса между анализом групп и анализом отдельных объектов часто поступают следующим образом: сначала анализируют группы, а затем в зависимости от полученных результатов исследуют объекты заинтересовавших аналитика групп. В любом случае можно утверждать, что наличие иерархии в объектах и ее использование в задаче поиска ассоциативных правил позволяют выполнять более гибкий анализ и получать дополнительные знания. В рассмотренной задаче поиска ассоциативных правил наличие объекта в транзакции определялось только его присутствием в ней ( Tij ∈ ) или отсутствием Tij ∉ . Часто объекты имеют дополнительные атрибуты, как правило, численные. Например, товары в транзакции имеют атрибуты: цена и количество. При этом наличие объекта в наборе может определяться не просто фактом его присутствия, а выполнением условия по отношению к определенному атрибуту. Например, при анализе транзакций, совершаемых покупателем, может интересовать не просто наличие покупаемого товара, а товара, покупаемого по некоторой цене. Для расширения возможностей анализа с помощью поиска ассоциативных правил в исследуемые наборы можно добавлять дополнительные объекты. В общем случае они могут иметь природу, отличную от основных объектов. Например, для определения товаров, имеющих больший спрос в зависимости от месторасположения магазина, в транзакции можно добавить объект, характеризующий район. Представление результатов. Решение задачи поиска ассоциативных правил, как и любой задачи, сводится к обработке исходных данных и получению результатов. Обработка исходных данных выполняется по некоторому алгоритму ИА. Результаты, получаемые при решении этой задачи, принято представлять в виде ассоциативных правил. В связи с этим при их поиске выделяют два основных этапа: |