Применение анализа ассоциаций

Как было сказано, задача поиска ассоциативных правил впервые была представлена для анализа рыночной корзины. Ассоциативные правила эффективно используются в сегментации покупателей по поведению при покупках, анализе предпочтений клиентов, планировании расположения товаров в супермаркетах, кросс-маркетинге, адресной рассылке. Однако, сфера применения этих алгоритмов не ограничивается лишь одной торговлей. Другими областями анализа данных, где используются методы поиска ассоциативных правил, являются: выявление мошеннических операций по кредитным картам, страховым случаям; определение причин сбоев в телекоммуникационных системах; анализ ДНК живых организмов; обработка данных социологических исследований. и т.д.

Web Mining можно перевести как "добыча данных в Web" [1]. Web Intelligence или Web Интеллект готов "открыть новую главу" в стремительном развитии электронного бизнеса. Способность определять интересы и предпочтения каждого посетителя, наблюдая за его поведением, является серьезным и критичным преимуществом конкурентной борьбы на рынке электронной коммерции. В системах Web Mining ассоциативные правила используются для анализа поисковых запросов и предпочтений пользователя, а также для для анализа посещений веб-страниц.

Поиск ассоциативных правил также успешно применяют для анализа текста (Text Mining). Задача выделения терминов (term extraction) из текстов, решаемая перед задачей рубрикации, может быть сведена к поиску ассоциаций. Терминами считаются отдельные слова или устойчивые словосочетания, которые часто встречаются в небольшом подмножестве документов, и редко во всех остальных. Множество часто совместно встречающихся терминов образует тему, скорее всего, соответствующую некоторой рубрике.

 Поиск ассоциативных правил в XML-документах [10] отличается от поиска правил в простых документах, потому что в XML-формате информация может быть структурирована по-разному. Как правило, поиск ассоциативных правил XML означает поиск отношения между составными частями одного или нескольких XML-документов, для чего обычно применяются обобщенные ассоциативные правила.

Модель данных

Пусть I = {i₁, i₂, i₃, ...i_m} – множество изучаемых объектов, называемых элементами (item), общим числом m.

Набором элементов (itemset) X называетсялюбое подмножество множества объектов, , в том числе само множество I и пустое множество .

Если для набора элементов X задан некоторый уникальный идентификатор TID, то пару t=(TID, X) называют транзакцией. Мы говорим, что транзакция t содержит Y ( ), где Y – некоторый набор элементов из I, если .

Пусть D = {t¹, t², t³, ...t^N} – множество транзакций общим числом N. Каждая транзакция t=(TID, t₁, t₂, t₃, ...t_m) может быть представлена как бинарный вектор, где t_k =1, если i_k элемент присутствует в транзакции, иначе t_k=0. Тогда данные о транзакциях могут быть представлены в виде бинарной матрицы, где различным столбцам соответствуют различные объекты, а различным строкам – различные транзакции, или наоборот.

Пример транзакционных данных, содержащих список покупок в магазине приведен в таблице 2.1.

Таблица 2.1 – Транзакционные данные в матричной форме

Транзакционные данные представляют собой особый тип данных, где каждая запись, являющаяся транзакцией, включает набор значений. Для хранения иногда транзакционные данные записывают в виде массива пар (TID, ). Пример такого представления приведен в таблице 2.2.

Таблица 2.2 – Транзакционные данные в форме массива

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

Таблица 2.3 – Транзакционные данные в списочной форме (горизонтальный формат)

Также существует другой вид списочной формы, удобный для поиска ассоциаций. Для каждого продукта будем хранить список номеров транзакций, в которых он участвовал (см. табл. 2.4).

Таблица 2.4 – Пример списочной формы другого вида (вертикальный формат)

Тогда по количеству элементов в таком списке можно определить поддержку элемента в базе транзакционных данных. Под поддержкой (support) множества X на базе транзакций D понимается величина S(X), равная числу транзакций, содержащих все элементы из этого множества:

,

где |Z| означает мощность множества Z.

       Для матричной формы, например, поддержка элемента равна сумме элементов соответствующего столбца бинарной матрицы.

       Если элементы разбиты на категории и для каждой категории допустимо только одно значение, то транзакционные данные могут быть представлены в виде таблицы, где каждой транзакции соответствует одна запись (строка таблицы), а столбцы соответствуют категориям, например, табл. 2.5.

Таблица 2.5 – Транзакционные данные в табличной форме