Создание ассоциативных правил в интеллектуальном анализе данных

Считайте себя на супермаркете !!

Вы когда-нибудь задумывались о соседних продуктах с печеньем? В основном это будут пакеты Нам-кин или какой-нибудь другой перекус.

Почему?

Обычно на веб-сайтах и ​​в мобильных приложениях рекомендовать персонализированные элементы для каждого пользователя практически невозможно. Но возможно ли это для физического магазина (скажем, Супермаркета)?

No !!

Так что же делать таким физическим магазинам?

Просто все расставить в случайном порядке? Нравится печенье рядом с отделом овощей / фруктов?

Или можно сделать какую-то стратегию для увеличения продаж? Это можно сделать следующими способами.

  • Либо разложите все популярные товары вместе на Главных воротах.
  • Найдите закономерности в продажах и разместите предметы, которые покупаются вместе, ближе.

Я буду обсуждать второй подход, который можно рассматривать как своего рода общую рекомендацию для всех, кто посещает магазин, где индивидуальные рекомендации невозможны.

Анализ ассоциаций в основном помогает определить «ассоциацию» между различными предметами, будь то бакалея, медицина и т. Д.

Давайте начнем с нескольких основных понятий:

Пусть I = {I1, I2, I3 и т.д.} будет набором всех возможных товаров в данной среде. Скажем, если наша среда - это Супермаркет, I - это набор всех возможных товаров в Супермаркете. Предположим

I = {Хлеб, Пеленки, Молоко, Пиво, Яйца, Кола} до конца сообщения.

  • Набор элементов: любое подмножество I называется набором элементов. Пример: {Хлеб, Подгузник}, {}, {Яйца} и т. Д. Являются наборами предметов, поскольку все они являются подмножеством I. Кроме того, подмножество элементов «k» будет называться K наборами предметов.

Например: {пиво, яйца} будет называться набором из 2 предметов.

  • Непересекающиеся наборы элементов. Любые два набора элементов без общих элементов. Пример: {Хлеб, Подгузник} и {Яйца, Пиво} не пересекаются друг с другом.
  • Транзакции. Транзакции - это наборы элементов в обучающих данных, с помощью которых нам нужно выяснить связь между элементами. Предположим, у нас есть супермаркет «M», где вчера произошли указанные ниже транзакции. TID - это идентификатор транзакции (пока не обращайте на него внимания)

  • Правило ассоциации

Пусть I1 и I2 - 2 непересекающихся набора элементов. Если I1 и I2 связаны, то I1 → I2.

Пример: Если I1 = {Beer} & I2 = {Diaper, Eggs} и если они связаны, то,

{Пиво} → {Пеленки, яйца}. Это означает, что если в транзакции есть «Пиво», в ней также могут быть «Подгузник» и «Яйца», но не наоборот. Чем может быть полезно знание таких отношений?

  1. Если мы сможем установить такие правила, мы сможем сказать, что если пиво покупается, то также покупаются подгузники и яйца, и, следовательно, все это можно держать под рукой.
  2. Может быть полезно при создании таких разделов, как «Клиенты, которые смотрели это, также смотрели это», как в Amazon.

Но как определить, связаны ли наборы элементов I1 и I2?

у нас есть несколько факторов для этого. Чтобы узнать, насколько сильным может быть правило I1 → I2, мы вычисляем 2 вещи:

Пусть I1 = {Хлеб} & I2 = {Молоко}. Нам нужно выяснить, держится ли Хлеб → Молоко или нет.

  • Поддержка: для правила I1 → I2 это =

Частота (I1 U I2) / N

Где:

N = Итоговые транзакции (в нашем случае 5, помните приведенную выше таблицу)

I1 U I2 = {Хлеб} U {Молоко} = {Хлеб, Молоко}.

As, частота для {Хлеб, Молоко} = 3, Поддержка = 3/5 = 0,6

Примечание. Поддержка набора элементов = Частота (набор элементов) / Общее количество транзакций.

  • Уверенность: для правила I1 → I2 это =

Частота (I1 U I2) / Частота (I1) или

Частота ({Хлеб, Молоко}) / Частота ({Хлеб}) = 3/4 = 0,75

Следовательно, для {Хлеб} → {Молоко} мы имеем Поддержка = 0,6, Уверенность = 0,75.

Открытие правил ассоциации

Учитывая набор транзакций T, найдите все правила ассоциации R такие, что

  • Поддержка любого правила R ’› Support_Threshold &
  • Уверенность в правиле R ’› Confidence_Threshold

Пока все в порядке. Теперь рассмотрим Супермаркет в реальном мире. В нем будет целых 1000 предметов. Если мы воспользуемся грубой силой, чтобы выяснить правила ассоциации, на это потребуются годы. Фактически, с любой средой, имеющей "d" элементов, общее количество проверяемых правил = 3ᵈ - 2ᵈ x 2 +1. При d = 1000 это равно 5,15 x 10⁴⁷ !!!

Итак, мы обычно не используем грубую силу.

Чтобы ускорить процесс, определение строгих правил можно разделить на 2 части.

  • Создание набора часто встречающихся элементов с установленным параметром Support ›Support_Threshold
  • Расчет уверенности только для частых наборов предметов. Если их уверенность выше установленного значения Confidence_Threshold, примите их как строгое правило.
  • Следовательно, вместо одновременного расчета поддержки и уверенности, выполняйте их по одному шагу за раз.

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

Принцип априори

Здесь набор элементов называется часто, если для него установлено значение Support ›Support_Threshold.

Он состоит из двух основных моментов.

  1. Если набор элементов является частым (поддержка выше Support_Threshold), все его подмножества также встречаются часто. Следовательно, нам не нужно рассчитывать поддержку для каждого правила. Бывший:

Если Поддержка {Хлеб, Пиво, Яйца} выше Support_Threshold, то {Хлеб, Пиво}, {Пиво, Яйца}, {Хлеб, Яйца} и т. Д. Также имеют поддержку выше порогового значения. Таким образом, сэкономлено много сравнений.

На изображении выше, если часто встречается «cde» (последняя выделенная серым ячейка), все серые наборы элементов также часто используются автоматически.

2. Если набор элементов A является нечастым, то все его супер-наборы (наборы, для которых A является подмножеством) также нечасты. Следовательно, если {Bread} нечасто встречается, {Bread, Eggs }, {Хлеб, Подгузники, Пиво} и т. Д. - все это нечасто, поэтому их поддержку не следует рассчитывать. Опять же экономия на сравнениях.

Если «ab» встречается нечасто, каждый суперсет нечасто встречается и может быть проигнорирован тогда и там.

Но почему верны два вышеупомянутых пункта?

Благодаря антимонотонному свойству меры поддержки.

Монотонность

  • Если X⊆Y, то f (X) ≤f (Y). Если какая-либо мера «f ()» обладает этим свойством, говорят, что мера обладает монотонным свойством.

Например: пусть f () будет Count. Тогда, если X (скажем, {1,2}) ⊆Y (скажем, {1,2,3,4,5}), X никогда не может иметь больше элементов, чем Y. Следовательно, Count (X) ≤Count (Y) всегда выполняется.

  • Если X⊆Y, то f (Y) ≤f (X). Если какая-либо мера «f ()» обладает этим свойством, говорят, что эта мера обладает антимонотонным свойством.

Например: пусть f () будет Count⁻¹, то есть 1 / Count. Следовательно, если X⊆Y, то всегда Count⁻¹ (X) ›Count⁻¹ (Y).

Служба поддержки также имеет это свойство, как если бы учитывала {Beer} ⊆ {Beer, Milk}, чем, {Beer} всегда будет больше, чем {Beer, Milk} в общих транзакциях.

Теперь, когда мы видим, что все готово, пришло время для алгоритма

Алгоритм априори

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

1. Find Frequent 1-item-set F_1. 
2. For i=2->k: #k is number of unique items
      'CANDIDATE-SET GENERATION'
      A. Generate Candidate 'i'-item-set by F_(i-1) X F_(i-1)
         #Exception case for i=2 mentioned below
 
      'CANDIDATE SET PRUNING'
      B. Find Frequent 'i'-item-set(F_i) from Candidate 'i'-item-set 
      C. If Frequent 'i'-item-set is {}: 
         Finish & return F_(i-1)

Отвергать его - не ракетостроение.

  • F_ (i-1) X F_ (i-1) - это что-то интересное. Если i = 2, будет рассматриваться каждый элемент из F_1. Теперь, когда i = 3, мы будем объединять частый набор из 2 элементов, у которого 1-й элемент i-2 является общим. скажи, если у меня есть

{Пиво, Подгузники}, {Пиво, яйца}, {Яйца, Кола} как частый набор из 2 предметов. Теперь, чтобы сгенерировать набор из 3 элементов-кандидатов, это будет просто {Пиво, Подгузники, Яйца}, и мы будем игнорировать {Яйца, Колу}, поскольку его 1-й элемент не совпадает с двумя другими частыми наборами.

Пример все прояснит !!

Вспомним множество транзакций T:

Пусть Support_Threshold = 0,6 & Confidence_Threshold = 0,6. Поскольку total_transactions = 5, набор элементов должен иметь частоту не менее 3 (3/5 = 0,6), чтобы называться частым набором элементов.

  • Найдите все часто встречающиеся наборы из 1 элемента (подмножества с одним элементом, у которых есть Support ›Support_Threshold). Для этого нам сначала нужно рассчитать частоту набора из 1 элемента.

  • Выберите часто встречающиеся наборы из 1 элемента: серые значения в приведенной выше таблице будут отклонены из дальнейшего рассмотрения из-за низкой поддержки (‹3).
  • Затем, чтобы создать набор кандидатов из 2 элементов, мы будем вычислять F_ (1) xF_ (1). Поскольку это исключение, мы будем перекрестно объединять все частые наборы из 1 элемента, следовательно,

Вы можете заметить одну вещь: в наборе кандидатов из 2 предметов мы не учли {Подгузник, Пиво}, {Молоко, Подгузники} и т. Д.? Это связано с тем, что {Подгузники, Пиво} - это то же самое, что {Пиво, Подгузники}, и, следовательно, чтобы избежать таких повторяющихся случаев, мы будем располагать элементы наборов предметов в некотором лексическом порядке (скажем, в алфавитном порядке, как в таблице выше).

  • Теперь, чтобы сгенерировать набор кандидатов из 3 элементов, мы будем использовать F_ (2) xF_ (2). Следовательно, мы будем объединять частый набор из 2 элементов с 1-м элементом. Поскольку только {Bread, Diapers} и {Beer, Milk} имеют общий 1-й элемент, они будут объединены в:

  • Теперь, когда у нас есть только одно правило в частом наборе из 3 элементов, набор кандидатов из 4 элементов невозможен. Значит, мы закончили !!
  • Если бы у нас было больше наборов элементов в Frequent 3-item-set, мы бы сгенерировали Candidate 4-item-set путем объединения наборов элементов с первыми двумя такими же элементами. Например: если бы у нас были {A, B, C}, {A, B, D}, {A, C, E}, в наборе кандидатов из 4 пунктов {A, B, C, D} игнорировалось бы {A, C, E}

Итак, Априори предоставил нам {Хлеб, Подгузники, Молоко} в качестве продукции.

Но это всего лишь частый набор предметов. Нам все еще нужны правила ассоциации.

Как сгенерировать правила из набора часто задаваемых элементов?

Теперь, если Apriori дает нам набор из 100 пунктов в качестве вывода, даже вычисление уверенности может быть медленным. Как можно ускорить этот этап? Используя следующую теорему

Теорема

Если Confidence for X → Y-X ‹Confidence_Threshold, то даже Xx → Y-Xx может быть отклонено, где Xx ⊆X.

Что это значит?

Скажите {Хлеб, Пиво} → {Подгузники} - {Хлеб, Пиво} не выдерживает. Чем {Хлеб} → {Подгузники} - {Хлеба} не удержать.

Пара вопросов?

Какие доказательства?

Уверенность для любого правила X → Y = Частота (X U Y) / Частота (X)

Теперь, если у нас есть

X → Y-X = Частота (X U Y -X) / Частота (X) = F (Y) / F (X)

Xx → Y-Xx = Частота (Xx U Y -Xx) / Частота (Xx) = F (Y) / F (Xx)

Но поскольку Частота (Xx) ›Частота (X) как Xx⊆X, следовательно,

F (Y) / F (Xx) ≤F (Y) / F (X), и если X → Y-X отклоняется, другой также отклоняется.

Почему я должен вычислять X → Y-X, а не просто X → Y, т.е. как эта теорема полезна в нашем случае?

Если смотреть на 1-ю ячейку, выделенную серым цветом, поскольку bcd → a отклоняется, остальные ячейки, выделенные серым цветом (6 правил), отклоняются. При выборе одного из них cd → ab отклоняется как cd⊆bcd & Confidence cd → ab = Frequency ({c, d, a, b} - {c, d}) / Frequency ({c, d}). Следовательно, нам нужно рассчитать уверенность только для одного правила, а не для семи !!

= Частота ({a, b}) / Частота ({c, d}), которая всегда будет меньше, чем Частота ({a, b}) / Частота ({b, c, d})

Таким же образом, как указано выше, мы можем начать с {Хлеб, Подгузники, Молоко} → {} и найти правила ассоциации с Уверенностью ›Порог уверенности.

Если вы чувствуете себя немного сбитым с толку, используя вышеупомянутый метод поиска правил ассоциации из набора часто встречающихся элементов, вы можете использовать метод грубой силы, который будет вычислять доверие для каждого и каждого возможного правила, которое может быть сформировано из полученного набора часто встречающихся элементов. Как и в случае с {Хлеб, подгузники, молоко}, при использовании грубой силы необходимо проверить следующие правила:

{Хлеб} → {Подгузники}, {Подгузники} → {Хлеб},

{Хлеб} → {Молоко}, {Молоко} → {Хлеб},

{Молоко} → {Подгузники}, {Подгузники} → {Молоко},

{Хлеб, Подгузники} → {Молоко}, {Молоко} → {Хлеб, Подгузники},

{Хлеб} → {Подгузники, Молоко}, {Подгузники, Молоко} → {Хлеб},

{Хлеб, Молоко} → {Подгузники}, {Подгузники} → {Хлеб, Молоко}

И с этим, его упаковка !!

Для получения дополнительных материалов по науке о данных!