|
{term4} Suppmin = 0,75; {term4, term6} Suppmin = 0,5; {term6} Suppmi)l = 0,75. 3.1.2. Секвенциальный анализ При анализе информации и транзакций в корпоративных системах часто вызывает интерес последовательность происходящих событий. При обнаружении закономерностей в таких последовательностях можно с некоторой долей вероятности предсказывать появление событий в будущем, что позволяет принимать более правильные решения [48]. Так же покажем модификацию модели до многоверсионного случая. За многоверсионность отвечает коэффициент I. Последовательностью называется упорядоченное множество объектов. Для этого на множестве должно быть задано отношение порядка. Тогда последовательность объектов можно описать в следующем виде: S = \...,ip,...,iq,...},T)\Qp Тогда последовательность S {(term.4, 02.03.2003), (term2, 05.03.2003), (term5,10.03.2003)} можно интерпретировать как запросы, совершаемые одним человеком в разное время (вначале была запрошена информация, содержащая термин term4, затем term2, а потом term5). Различают два вида последовательностей: с циклами и без циклов. В первом случае допускается вхождение в последовательность одного и того же объекта на разных позициях: S = {...,ip>.гдер При этом допускается, что 78 |
− для каждого класса в задаче классификации или каждого интервала области значений в задаче регрессии выборка должна содержать достаточное количество объектов. На втором этапе построенную модель применяют к анализируемым объектам (к объектам с неопределенным значением зависимой переменной). Основные проблемы, с которыми сталкиваются при решении задач классификации и регрессии, – это неудовлетворительное качество исходных данных, в которых встречаются как ошибочные данные, так и пропущенные значения, различные типы атрибутов – числовые и категоричные, разная значимость атрибутов, а также так называемые overfitting и underfitting. Суть первой из них заключается в том, что классификационная функция при построении «слишком хорошо» адаптируется к данным, и встречающиеся в них ошибки и аномальные значения пытается интерпретировать как часть внутренней структуры данных. Очевидно, что такая модель будет некорректно работать в дальнейшем с другими данными, где характер ошибок будет несколько иной. Термином underfitting обозначают ситуацию, когда слишком велико количество ошибок при проверке классификатора на обучающем множестве. Это означает, что особых закономерностей в данных не было обнаружено и либо их нет вообще, либо необходимо выбрать иной метод обнаружения. Задача поиска ассоциативных правил. Поиск ассоциативных правил является одним из самых популярных приложений ИА. Суть задачи заключается в определении часто встречающихся наборов объектов в большом множестве таких наборов. Данная задача является частным случаем задачи классификации [5]. Первоначально она решалась при анализе тенденций в поведении покупателей в супермаркетах. Анализу подвергались данные о совершаемых ими покупках, которые покупатели складывают в корзину. Это послужило причиной второго часто встречающегося названия – анализ рыночных корзин. При анализе этих данных интерес прежде всего представляет информация о том, какие товары предпочитают, в какие периоды времени и т.п. Такая информация позволяет более эффективно планировать закупку товаров, проведение рекламной кампании и т.д. Задача поиска ассоциативных правил актуальна не только в сфере торговли. Например, в сфере обслуживания интерес представляет, какими услугами клиенты предпочитают пользоваться в совокупности. Для получения этой информации задача решается применительно к данным об услугах, которыми пользуется один клиент в течение определенного времени (месяца, года). В медицине анализу могут подвергаться симптомы и болезни, наблюдаемые у пациентов. В этом случае знания о том, какие сочетания болезней и симптомов встречаются наиболее часто, помогают в будущем правильно ставить диагноз. При анализе часто вызывает интерес последовательность производящих событий. При обнаружении закономерностей в таких последовательностях можно с некоторой долей вероятности предсказывать появление событий в будущем, что позволяет принимать более правильные решения. Такая задача является разновидностью задачи поиска ассоциативных правил и называется сиквенциальным анализом. Основным отличием задачи сиквенциального анализа от поиска ассоциативных правил является установление отношения порядка между исследуемыми наборами. Данное отношение может быть определено разными способами. При анализе последовательности событий, происходящих во времени, объектами таких наборов являются события, а отношение порядка соответствует хронологии их появления. Сиквенциальный анализ широко используется, например в телекоммуникационных компаниях, для анализа данных об авариях на различных узлах сети. Информация о последовательности совершения аварий может помочь в обнаружении неполадок и предупреждении новых аварий. Например, если известна последовательность сбоев: { },...,,,,,, 1613725 eeeeee где ie – сбой с кодом i , то на основании факта появления сбоя 2e можно сделать вывод о скором появлении сбоя 7e . Зная это, можно предпринять профилактические меры, устраняющие причины возникновения сбоя. Если дополнительно обладать и знаниями о времени между сбоями, то можно предсказать не только факт его появления, но и время, что часто не менее важно. Задача кластеризации. Задача кластеризации состоит в разделении исследуемого множества объектов на группы «похожих» объектов, называемых кластерами. Слово кластер английского происхождения (cluster), переводится как сгусток, пучок, группа. Родственные понятия, используемые в литературе, – класс, таксон, сгущение. Часто решение задачи разбиения множества элементов на кластеры называют кластерным анализом [5]. Кластеризация может применятся практически в любой области, где необходимо исследование экспериментальных или статистических данных. Для научных исследований изучение результатов кластеризации, а именно вычисление причин, по которым объекты объединяются в группы, способно открыть новые перспективные направления. Кластеризация отличается от классификации тем, что для проведения анализа не требуется иметь выделенную зависимую переменную. С этой точки зрения она относится к классу обучения без учителя. Задача решается на начальных этапах исследования, когда о данных мало что известно. Ее решение помогает лучше понять данные, и с этой точки зрения задача кластеризации является описательной задачей. Для задачи кластеризации характерно отсутствие каких-либо различий как между переменными, так и между объектами. Напротив, ищутся группы наиболее близких, похожих объектов. Методы автоматического разбиения на кластеры редко используются сами по себе, просто для получения групп схожих объектов. После определения кластеров применяются другие методы ИА, для того чтобы попытаться установить, что означает такое разбиение, чем оно вызвано. Кластерный анализ позволяет рассматривать достаточно большой объем информации и резко сокращать, сжимать большие массивы информации, делать их компактными и наглядными. Отметим ряд особенностей, присущих задаче кластеризации. Во-первых, решение сильно зависит от природы объектов данных (и их атрибутов). Так, с одной стороны, это могут быть однозначно определенные, четко количественно очерченные объекты, а с другой – объекты, имеющие вероятностное или нечеткое описание. Во-вторых, решение значительно зависит также и от представления кластеров и предполагаемых отношений объектов данных и кластеров. Так, необходимо учитывать такие свойства, как возможность/невозможность принадлежности объектов − Проверка построенных моделей. − Интерпретация моделей человеком. На первом этапе выполняется осмысление поставленной задачи и уточнение целей, которые должны быть достигнуты методами ИА. Важно правильно сформулировать цели и выбрать необходимые для их достижения методы, так как от этого зависит дальнейшая эффективность всего процесса. Второй этап состоит в приведении данных к форме, пригодной для применения конкретных методов ИА. Данный процесс ниже будет описан более подробно, здесь заметим только, что вид преобразований, совершаемых над данными, во многом зависит от используемых методов, выбранных на предыдущем этапе. Третий этап – это собственно применение методов ИА. Сценарии этого применения могут быть самыми различными и включать сложную комбинацию разных методов, особенно если используемые методы позволяют проанализировать данные с разных точек зрения. Следующий этап – проверка построенных моделей. Очень простой и часто используемый способ заключается в том, что все имеющиеся данные, которые необходимо анализировать, разбиваются на две группы. Как правило, одна из них большего размера, другая – меньшего. На большей группе, применяя те или иные методы ИА, получают модели, а на меньшей – проверяют их. По разнице в точности между тестовой и обучающей группами можно судить об адекватности построенной модели. Последний этап – интерпретация полученных моделей человеком в целях их использования для принятия решений, добавление получившихся правил и зависимостей в базы знаний и т.д. Этот этап часто подразумевает использование методов, находящихся на стыке технологий ИА и технологии экспертных систем. Оттого, насколько эффективным он будет, в значительной степени зависит успех решения поставленной задачи. 1.6. ЗАДАЧА ПОИСКА АССОЦИАТИВНЫХ ПРАВИЛ Формальная постановка задачи. Одной из наиболее распространенных задач анализа данных является определение часто встречающихся наборов объектов в большом множестве наборов. Опишем эту задачу в обобщенном виде [10]. Для этого обозначим объекты, составляющие исследуемые наборы, следующим множеством: }...,,...,,,{ 21 nj iiiiI = , где ji – объекты, входящие в анализируемые наборы; n – общее количество объектов. Наборы объектов из множества I , хранящиеся в БД и подвергаемые анализу, называются транзакциями. Опишем транзакцию как подмножество множества I : }{ IiiT jj ∈= . Такие транзакции в магазине соответствуют наборам товаров, покупаемых потребителем и сохраняемых в БД в виде товарного чека или накладной. В них перечисляются приобретаемые покупателем товары, их цена, количество и др. Набор транзакций, информация о которых доступна для анализа, обозначим следующим множеством: }...,,...,,,{ 21 mr TTTTD = , где m – количество доступных для анализа транзакций. Множество транзакций, в которые входит объект ji , обозначим следующим образом: DmrnjTiTD rjri j ⊆==∈= }..1;..1;{ . Некоторый произвольный набор объектов обозначим следующим образом: }..1;{ njIiiF jj =∈= . Набор, состоящий из k объектов, называется k -элементным набором (в данном примере это 2-элементный набор). Множество транзакций, в которые входит набор F , обозначим следующим образом: DmrTFTD rrF ⊆=⊆= }..1;{ . Отношение количества транзакций, в которое входит набор F , к общему количеству транзакций называется поддержкой набора F и обозначается )(FSupp : )( D D FSupp F = . При поиске аналитик может указать минимальное значение поддержки интересующих его наборов minSupp . Набор называется частым, если значение его поддержки больше минимального значения поддержки, заданного пользователем: min)( SuppFSupp > . Таким образом, при поиске ассоциативных правил требуется найти множество всех частых наборов: })({ minSuppFSuppFL >= . Сиквенциальный анализ. При анализе часто вызывает интерес последовательность происходящих событий. При обнаружении закономерностей в таких последовательностях можно с некоторой долей вероятности предсказывать появление событий в будущем, что позволяет принимать более правильные решения. Последовательностью называется упорядоченное множество объектов. Для этого на множестве должно быть задано отношение порядка. Тогда последовательность объектов можно описать в следующем виде: ...},...,,{..., 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 ∉ . Часто объекты имеют дополнительные атрибуты, как правило, численные. Например, товары в транзакции имеют атрибуты: цена и количество. При этом наличие объекта в наборе может определяться не просто фактом его присутствия, а выполнением условия по отношению к определенному атрибуту. Например, при анализе транзакций, совершаемых покупателем, может интересовать не просто наличие покупаемого товара, а товара, покупаемого по некоторой цене. Для расширения возможностей анализа с помощью поиска ассоциативных правил в исследуемые наборы можно добавлять дополнительные объекты. В общем случае они могут иметь природу, отличную от основных объектов. Например, для определения товаров, имеющих больший спрос в зависимости от месторасположения магазина, в транзакции можно добавить объект, характеризующий район. Представление результатов. Решение задачи поиска ассоциативных правил, как и любой задачи, сводится к обработке исходных данных и получению результатов. Обработка исходных данных выполняется по некоторому алгоритму ИА. Результаты, получаемые при решении этой задачи, принято представлять в виде ассоциативных правил. В связи с этим при их поиске выделяют два основных этапа: |