Ассоциативные правила. То произойдет и событие
 Скачать 111 Kb.
|
|
Развитие методов записи и хранения данных привело к бурному росту объемов собираемой и анализируемой информации. Объемы данных настолько внушительны, что человеку просто не по силам проанализировать их самостоятельно, хотя необходимость проведения такого анализа вполне очевидна, ведь в этих "сырых" данных заключены знания, которые могут быть использованы при принятии решений. Для того чтобы провести автоматический анализ данных, используется Data Mining. Data Mining – это процесс обнаружения в "сырых" данных ранее неизвестных нетривиальных практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Data Mining является одним из шагов Knowledge Discovery in Databases. Алгоритмы, используемые в Data Mining, требуют большого количества вычислений. Раньше это являлось сдерживающим фактором широкого практического применения Data Mining, однако сегодняшний рост производительности современных процессоров снял остроту этой проблемы. Теперь за приемлемое время можно провести качественный анализ сотен тысяч и миллионов записей. Одним из стремительно развивающихся направлений в Data Mining является поиск ассоциативных правил. Ассоциативные правила позволяют найти закономерности между связанными событиями. Примером такого правила, служит утверждение, что в том случае, если произошло событие А, то произойдет и событие В. Данное утверждение можно записать в виде  . Причем условная часть ассоциативного правила может представлять из себя группу событий.Первая работа (Agrawal 1993 год) на эту тему была посвящена извлечению паттернов транзакций базы данных для бизнеса розничных продаж. Иногда поиск АП именуют как анализ потребительской корзины в указании поиска ассоциативных правил среди элементов, которые покупатель выбрал в свою покупку. С точки зрения компании любая покупка клиента состоит из транзакции, которая состоит из набора элементов. Классический пример анализ связей среди различных типов товаров на складе, который подтверждает, что тот клиент, который покупает некоторый продукт (например, хлеб) обычно также покупает так же и молоко. Предположим, что таблица 1 отображает информацию собранную ритейлерами. Таблица 1 описывает композицию шести покупок, т.е. шести транзакций в терминах из 4 элементов: хлеб, масло, бисквиты и молоко. Значение равное единице означает, что соответствующий ему элемент включен (не включен) в транзакцию. Очень легко определить ассоциативное правило «Хлеб и Масло => Молоко», которое иллюстрирует тот факт: что когда клиент покупает хлеб и масло, то он так же покупает молоко. Однако, это правило имеет одно исключение в 5 транзакции и значит, что ритейлер не может полностью доверять данному заявлению. Для измерения надежности\точности правила существуют два параметра Поддержка (от англ. support) и Достоверность (от англ. confidence), которые интенсивно используются в данной области. Поддержка измеряет надежность, используя относительную частоту вхождения элемента в правиле. Достоверность измеряет точность правила, как коэффициент между поддержкой этого правила и относительной частотой вхождения элементов в левую часть правила. В нашем примере поддержка равна 3\6, а достоверность – 3\4 Математическая модель. Построим математическую модель ассоциативных правил, дадим формальные определения понятий, составляющих тезаурус данной предметной области. Пусть  - множество сущностей,  - множество транзакций, каждая из которых состоит из элементов множества  и уникального идентификатора – TID. Транзакция - это множество событий, произошедших одновременно (групповая операция).  обозначает, что транзакция  содержит множество  в том случае, если  . Покрытие множества в  состоит из множестве транзакций, которые содержат cover  .Определение 1. Ассоциативное правил (АП) - это выражение , где  ,  и  .Правило означает «каждая транзакция из , которая содержит  , так же содержит  ».Как был сказано выше, обычно чтобы оценить ассоциативное правило измеряют Support(поддержка) и Confidence(достоверность), оба базируются на концепции поддержки множества элементов(itemset). Где itemset – атомарная сущность состоящая из элементов множества  , причем  . Определение 2. Поддержка множества элементов  в отношении множества транзакций  ,то есть, вероятность того, что транзакция из содержит  .Определение 3. Support(Поддержка) ассоциативного правила в это иConfidence(достоверность)  Обычно принимают, что фиксировано для каждой задачи и таким образом обычно избегают ссылки на него. Выше введенные значения обычно записывают  , и  соответственно. Заметим, что перечисленные показатели начинаются с маленькой буквы для элементов  , тогда как для правила с заглавной буквы  ,  .Поддержка – это процент транзакций, которые содержат правило. Достоверность – это условная вероятность для  в отношении или другими словами относительная мощность множества в отношении . Рассмотрим классификацию транзакций. Определение 3. Пусть ассоциативное правило и  транзакция, тогда - позитивная транзакция,   ; - не позитивная транзакция,  ; - негативная транзакция,  ; - не негативная транзакция,  . |