|
отличную от основных объектов. Например, для нахождения документов, имеющих наибольшую релевантность в зависимости от месторасположения сервера, в транзакции можно добавить объект, характеризующий адрес и/или тематику информационного сервера. 3.2. Представление результатов Решение задачи поиска ассоциативных правил, как и любой задачи, сводится к обработке исходных данных и получению результатов. Обработка над исходными данными выполняется по некоторому алгоритму Data Mining. Результаты, получаемые при решении этой задачи, принято представлять в виде ассоциативных правил. В связи с этим при их поиске выделяют два основных этапа: нахождение всех частых наборов объектов; генерация ассоциативных правил из найденных частых наборов объектов. Ассоциативные правила имеют следующий вид: если (условие) то (результат), где условие — обычно не логическое выражение (как в классификационных правилах), а набор объектов из множества /, с которыми связаны (ассоциированы) объекты, включенные в результат данного правила. Например, ассоциативное правило: если (term3, term.4) то (term6) означает, что если JJLl’lP запрашивает term3 и term4, то он запросит и term6. Как уже отмечалось, в ассоциативных правилах условие и результат являются объектами множества Г. если X то Y, где X е I,Y <= I,XvjY = (р. Ассоциативное правило можно представить как импликацию над множеством X =>Y, где X е I,Y <= I,X |
Последовательностью называется упорядоченное множество объектов. Для этого на множестве должно быть задано отношение порядка. Тогда последовательность объектов можно описать в следующем виде: ...},...,,{..., 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 ∉ . Часто объекты имеют дополнительные атрибуты, как правило, численные. Например, товары в транзакции имеют атрибуты: цена и количество. При этом наличие объекта в наборе может определяться не просто фактом его присутствия, а выполнением условия по отношению к определенному атрибуту. Например, при анализе транзакций, совершаемых покупателем, может интересовать не просто наличие покупаемого товара, а товара, покупаемого по некоторой цене. Для расширения возможностей анализа с помощью поиска ассоциативных правил в исследуемые наборы можно добавлять дополнительные объекты. В общем случае они могут иметь природу, отличную от основных объектов. Например, для определения товаров, имеющих больший спрос в зависимости от месторасположения магазина, в транзакции можно добавить объект, характеризующий район. Представление результатов. Решение задачи поиска ассоциативных правил, как и любой задачи, сводится к обработке исходных данных и получению результатов. Обработка исходных данных выполняется по некоторому алгоритму ИА. Результаты, получаемые при решении этой задачи, принято представлять в виде ассоциативных правил. В связи с этим при их поиске выделяют два основных этапа: − Нахождение частых наборов объектов. − Генерация ассоциативных правил, найденных частых наборов объектов. Ассоциативные правила имеют следующий вид: Если (условие) то (результат), где условие – обычно не логическое выражение (как в классификационных правилах), а набор объектов из множества I , с которыми связаны (ассоциированы) объекты, включенные в результат данного правила. Как уже отмечалось, в ассоциативных правилах условие и результат являются объектами множества I : Если X то Y , где ϕ=∪∈∈ YXIYIX ,, . Ассоциативное правило можно представить как импликацию над множеством: YX ⇒ , где ϕ=∪∈∈ YXIYIX ,, . Основным достоинством ассоциативных правил является их легкое восприятие человеком и простая интерпретация языками программирования. Однако они не всегда полезны. Выделяют три вида правил. − Полезные правила содержат действительную информацию, которая ранее была неизвестна, но имеет логичное объяснение. Такие правила могут быть использованы для принятия решений, приносящих выгоду. − Тривиальные правила содержат действительную и легко объяснимую информацию, которая уже известна. Такие правила, хотя и объяснимы, но не могут принести какой-либо пользы, так как отражают или известные законы в исследуемой области, или результаты прошлой деятельности. Иногда такие правила могут использоваться для проверки выполнения решений, принятых на основании предыдущего анализа. − Непонятные правила содержат информацию, которая не может быть объяснена. Такие правила могут быть получены или на основе аномальных значений, или глубоко скрытых знаний. Напрямую такие правила нельзя использовать для принятия решений, так как их необъяснимость может привести к непредсказуемым результатам. Для лучшего понимания требуется дополнительный анализ. Ассоциативные правила строятся на основе частых наборов. Так, правила, построенные на основании набора F (т.е. FYX =∪ ), являются всеми возможными комбинациями объектов, входящих в него. Таким образом, количество ассоциативных правил может быть очень большим и тяжело воспринимаемым для человека. К тому же, не все из построенных правил несут в себе полезную информацию. Для оценки их полезности вводятся следующие величины. Поддержка 0 показывает, какой процент транзакций поддерживает данное правило. Так как правило строится на основании набора, то, значит, правило YX ⇒ имеет поддержку, равную поддержке набора F , который составляют X и Y : D D SuppSupp YXF FYX ∪= ⇒ == . Очевидно, что правила, построенные на основании одного и того же набора, имеют одинаковую поддержку. Достоверность показывает вероятность того, что из наличия в транзакции набора X следует наличие в ней набора Y . Достоверностью правила YX ⇒ является отношение числа транзакций, содержащих наборы X и Y , к числу транзакций, содержащих набор X : X YX X YXF YX Supp Supp D D Conf ∪∪= ⇒ == . Очевидно, что чем больше достоверность, тем правило лучше, причем у правил, построенных на основании одного и того же набора, достоверность будет разная. К сожалению, достоверность не позволяет оценить полезность правила. Если процент наличия в транзакциях набора Y при условии наличия в них набора X меньше, чем процент безусловного наличия набора Y : y X YX YX Supp Supp Supp Conf <= ∪ ⇒ , это значит, что вероятность случайно угадать наличие в транзакции набора Y больше, чем предсказать это с помощью правила YX ⇒ . Для исправления такой ситуации вводится мера – улучшение. Улучшение показывает, полезнее ли правило случайного угадывания. Улучшение правила – это отношение числа транзакций, содержащих наборы X и Y , к произведению количества транзакций, содержащих набор X , и количества транзакций, содержащих набор Y : YX YX YX YXF YX SuppSupp Supp DD D impr * ∪∪= ⇒ == . Если улучшение больше единицы, то это значит, что с помощью правила предсказать наличие набора Y вероятнее, чем случайное угадывание, если меньше единицы, то наоборот. В последнем случае можно использовать отрицающее правило, т.е. правило, которое предсказывает отсутствие набора Y : YX ¬⇒ . У такого правила улучшение будет больше единицы, так как YY SuppSupp −=¬ 1 . Таким образом, можно получить правило, которое предсказывает результат лучше, чем случайным образом. Правда, на практике такие правила мало применимы. Данные оценки используются при генерации правил. Аналитик при поиске ассоциативных правил задает минимальные значения перечисленных величин. В результате те правила, которые не удовлетворяют этим условиям, отбрасываются и не |