Главная цель этой статьи показать наиболее значимые использования НМ в DM, особенно в отношении разработки ассоциативных правил (AR).

Поиск ап(Ассоциативные правила)

Начинается все со статьи Agrawal, первая работа темы была посвящена извлечению паттернов транзакций базы данных для бизнесса розничных продаж. Иногда поиск АП именуют как анализ потребительской корзины в указании поиска ассоциативных правил среди элементов, которые покупатель выбрал с свою покупку. С точки зрения компании любая покупка клиента состоит из транзакции, которая состоит из набора элементов.

Классический пример анализ связей среди различных типов товаров на складе, который подтверждает, что тот клиент, который покупает некоторый продукт (например, хлеб) обычно также покупает другой – молоко.

Предположим, что таблица 1 отображает информацию собранную ретейлерами. Таблица описывает композицию шести покупок, т.е. шести транзакций в терминах из 4 элементов: хлеб, масло, бисквиты и молоко. Значение равное единице означает, что соответствующий ему элемент включен (не включен) в транзакцию. Очень легко определить ассоциативное правило Bread&Butter => Milk, которое иллюстрирует тот факт: что когда клиент покупает хлеб и батон, то он так же покупает молоко. Однако, это правило имеет одно исключение в 5 транзакции и значит ретейлер не может полностью доверять данному заявлению.

Для измерения надежности\точности правила существуют два параметра Поддержка и Доверие, которые интенсивно используются в данной области. Поддержка измеряет надежность относительную частоту вхождения элемента в правиле. Доверие измеряет точность правила, как коэффициент между поддержкой этого правила и относительной частотой вхождения элементов в левую часть правила. В нашем примере поддержка равна 3\6, а доверие – 3\4.

Разработчик ищет ассоциативные правила в наборах элементов с поддержкой больше чем порог minsupp, который фиксирует пользователь. С точки зрения Доверия ассоциативного правила, отбирают те АП, для которых оно больше чем порог minconf.

Формальная модель.

Пусть множеств элементов (объектов) и множество транзакций в причем оба не пустые.

Определение 1. Ассоциативное правил (АП) это выражение , где , и .

Правило означает «каждая транзакция из , которая содержит , так же содержит ».

Как был сказано выше, обычно чтобы оценить ассоциативное правило измеряют Support(поддержка) и Confidence(доверие), оба базируются на концепции поддержки множества элементов(itemset).

Определение 2. Поддержка множества элементов в отношении множества транзакций

,

то есть, вероятность того, что транзакция из содержит .

Определение 3. Support(Поддержка) ассоциативного правила в это

и

Confidence(доверие)

Обычно принимают, что фиксировано для каждой задачи и таким образом обычно избегают ссылки на это. Выше введенные значения обычно записывают , и соответственно. Заметим, что перечисленные показатели начинаются с маленькой буквы для элементов , тогда как для правила с заглавной буквы , .

Поддержка – это процент транзакций, которые содержат правило. Доверие – это условная вероятность для в отношении или другими словами относительное кардинальное число для в отношении .

Методы, используемые для добычи ассоциативных правил (АП) пытаются открыть те, чья поддержка и доверие больше чем два определенных пользователем порога, называемых , соответственно. Такие правила называют «строгими правилами».