Association rule

Многие предприятия накапливают большие объемы данных о своей повседневной деятельности. Например, на кассах продуктовых магазинов ежедневно собираются огромные объемы покупательских данных, называемых транзакциями в покупательской корзине, каждый банк сохраняет информацию об услугах, предоставляемых клиентам, деятельность страховых компаний неразрывно связана с анализом страховых рисков, а уж если говорить о такой сфере жизнедеятельности как медицина, то на каждого из нас существует множество результатов всяческих анализов и так далее.
Среди этих всех данных существуют скрытые связи, выявление которых позволяет сделать ​​методология, известная как анализ ассоциаций. Это полезно для обнаружения интересных отношений, скрытых в больших наборах данных. Некоторые из этих ассоциаций достаточно тривиальны - "пиво без водки - деньги на ветер", иные достаточно неожиданные и требуют дополнительного исследования. Одна из наиболее "забавных" и неожиданных ассоциаций приведена в статье D.J. Power «Ask Dan!».
В 1992 году группа по консалтингу компании Teradata под руководством Thomas Blischok, CEO of MindMeld, Inc. провела исследование 1.2 миллиона транзакций в 25 магазинах для ритейлера Osco Drug. После анализа всех этих транзакций самым сильным правилом получилось «Между 17:00 и 19:00 чаще всего пиво и подгузники покупают вместе». Такое правило показалось руководству Osco Drug настолько неконструктивным, что принять решение о том, чтобы пставить подгузники на полках рядом с пивом они не решились. После подробного исследования данного феномена, объяснение паре пиво-подгузники оказалось вполне логичным: после окончания рабочего дня и возвращения с работы домой (как раз где-то, к 17 часам), жены обычно отправляли мужей за подгузниками в ближайший магазин. Посланные волей жены, мужья, не долго думая, совмещали приятное с полезным — покупали подгузники по заданию жены и пиво для собственного вечернего времяпрепровождения.
Помимо информации о корзине, анализ ассоциаций также применим к данным из других областей, таких как биоинформатика, медицинская диагностика, веб-анализ и анализ научных исследований. Например, при анализе данных науки о Земле, закономерности ассоциаций могут выявить интересные связи между океаном, сушей и атмосферными процессами (вспомним феномен Эль-Ниньо, где среди всего прочего, Эль-Ниньо вызывает экстремальные погодные условия, связанные с циклами частоты возникновения эпидемических заболеваний). Такая информация может помочь лучше понять, как различные элементы системы Земли взаимодействуют друг с другом.
Приведем некоторые области применения ассоциативных правил: Существуют две ключевые проблемы, которые необходимо учитывать при применении анализа ассоциаций.
Во-первых, обнаружение шаблонов из большого набора данных транзакций может быть вычислительно дорогим.
Во-вторых, некоторые из обнаруженных паттернов могут быть ложными (случаются просто случайно), и даже для не фиктивных паттернов некоторые более интересны, чем другие.

Ассоциативные правила представляют собой механизм нахождения логических закономерностей между связанными элементами (событиями или объектами). Пусть имеется \(\mathbf{A} = \{a_1, a_2, a_3, \dots, a_n\}\)- конечное множество уникальных элементов (list of items). Из этих компонентов может быть составлено множество наборов \(\mathbf{T}\) (sets of items), т.е. \(\mathbf{T} \subseteq \mathbf{A}\).

Ассоциативные правила \(\mathcal{A} \rightarrow \mathcal{T}\) имеют следующий вид: если <условие> то <результат>, где в отличие от деревьев классификации, <условие> - не логическое выражение, а набор объектов из множества \(\mathbf{A}\), с которыми связаны (ассоциированы) объекты того же множества, включенные в <результат> данного правила. Например, ассоциативное правило если (лес, вода) то (лягушки) означает, что если в лесу встретилось болотце или ручей, то рядом будут лягушки.

Понятие “вид элемента \(a_k\)” легко может быть обобщено на ту или иную его категорию или вещественное значение, т.е. концепция ассоциативного анализа может быть применена для комбинаций любых переменных. Например, при прогнозировании погоды одно из ассоциативных правил может выглядеть так: 'утром обильная роса' -> 'днем солнечно' = TRUE

Выделяют три вида правил:

Поиск ассоциативных правил обычно выполняют в два этапа:

Для оценки полезности и продуктивности перебираемых правил используются различные частотные критерии, анализирующие встречаемость кандидата в массиве экспериментальных данных. Важнейшими из них являются поддержка (support) и достоверность (confidence). Правило \(\mathcal{A} \rightarrow \mathcal{T}\) имеет поддержку \(s\), если оно справедливо для \(s\%\) взятых в анализ случаев:

\[\text{support}(\mathcal{A} \rightarrow \mathcal{T}) = P(\mathcal{A} \cup \mathcal{T})\]

Достоверность правила показывает, какова вероятность того, что из наличия в рассматриваемом случае условной части правила следует наличие заключительной его части (т.е. из \(\mathcal{A}\) следует \(\mathcal{T}\)):

\[\text{confidence}(\mathcal{A} \rightarrow \mathcal{T}) = \frac{P(\mathcal{A} \cup \mathcal{T})}{P(\mathcal{A})} = \frac{\text{support}(\mathcal{A} \rightarrow \mathcal{T})}{\text{support}(\mathcal{A})}.\]

Алгоритмы поиска ассоциативных правил отбирают тех кандидатов, у которых поддержка и достоверность выше некоторых наперед заданных порогов: minsupport и minconfidence. Если поддержка имеет большое значение, то алгоритмы будут находить правила, хорошо известные аналитику или настолько очевидные, что нет никакого смысла проводить такой анализ. Большинство интересных правил находят именно при низком значении порога поддержки. С другой стороны, низкое значение minsupport ведет к генерации огромного количества вариантов, что требует существенных вычислительных ресурсов или ведет к генерации статистически необоснованных правил.

Используются и другие показатели - подъемная сила, или лифт (lift), которая показывает, насколько повышается вероятность нахождения \(\mathcal{T}\) в анализируемом случае, если в нем уже имеется \(\mathcal{A}\):

\[\text{lift}(\mathcal{A} \rightarrow \mathcal{T}) = \frac{\text{confidence}(\mathcal{A} \rightarrow \mathcal{T}) }{ \text{support}(\mathcal{T})}\]

и усиление (leverage), которое отражает, насколько интересной может быть более высокая частота \(\mathcal{A}\) и \(\mathcal{T}\) в сочетании с более низким подъемом:

\[\text{leverage}(\mathcal{A} \rightarrow \mathcal{T}) = \text{support}(\mathcal{A} \rightarrow \mathcal{T}) - \text{support}(\mathcal{A})\times\text{support}(\mathcal{T})\]

Пример.

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

Вначале выпишем матрицу частот парного сочетания товаров \(x_i\) и \(x_j\): \(\sigma(x_i\cup x_j)\)

Support (поддержка)

Это нормированное значение парного сочетания товаров \[ supp(x_i\cup x_j)=\frac{\sigma(x_i\cup x_j)}{|T|}, \] где \(|T|-\) общее число транзакций.

Confidence (достоверность)

Данный показатель характеризует насколько часто срабатывает наше правило: \[ conf(x_i\cup x_j)=\frac{supp(x_i\cup x_j)}{supp(x_i)}. \]

Lift (поддержка)

Показатель поддержки представляет собой отношение "зависимости" элементов транзакции к их "независимости" и, естественно, показывает насколько эти элементы зависят один от другого \[ lift(x_i\cup x_j)=\frac{supp(x_i\cup x_j)}{supp(x_i)\times supp(x_j)}. \] Если значение \(lift(x_i\cup x_j)=1\), то транзакции с \(x_i\) и \(x_j\) независимы и правил их совместной покупки нет. Если значение \(lift(x_i\cup x_j)>1\), то значение \(lift(x_i\cup x_j)-1\) характерирует ассоциативное правило, чем это значение больше, тем правило "правильнее", если же \(lift(x_i\cup x_j)\lt 1\), то покупка \(x_j\) негативно сказывается на покупке \(x_i\).

Conviction (убедительность)

Величина \[ conv(x_i\cup x_j)=\frac{1-supp(x_j)}{1-conf(x_i\cup x_j)} \] характеризует ошибки ассоциативного правила. Чем результат действия больше единицы, чем более надежно правило. Если значение равно Infinity, то правило тривиальное.

Leverage (усиление)

Показатель усиления характеризует насколько интересной может быть более высокая частота выпадения элементов в транзакции в сочетании с более низким подъемом \[ lever(x_i\cup x_j)=supp(x_i\cup x_j)-supp(x_i)\times supp(x_j). \]

Для поиска устойчивого ассоциативного правила напомним терминологию -
  1. Кортежи - это транзакции, пары атрибут-значение - элементы.
  2. Правило ассоциации : {A, B, C, D, ...} => {E, F, G, ...}, где A, B, C, D, E, F, G, ... являются элементами ,
  3. Достоверность(точность) A => B: P (B | A) = (количество транзакций, содержащих как A, так и B) / (количество транзакций, содержащих A).
  4. Поддержка (покрытие) A => B: P (A, B) = (количество транзакций, содержащих как A, так и B) / (общее количество транзакций)
  5. Мы ищем правила, которые превышают заранее определенную поддержку (минимальную поддержку ) и имеют высокую степень достоверности.
Частые наборы элементов представляют собой наборы с желаемой минимальной поддержкой. Заметим, что если {A, B} является частым набором элементов, то и A, и B также являются частыми наборами элементов. Обратное, однако, неверно.

Первый алгоритм поиска ассоциативных правил был разработан в 1993 г. сотрудниками исследовательского центра IBM, что сразу возбудило интерес к этому направлению. Каждый год появлялось несколько новых алгоритмов (DHP, Partition, DIC и др.), из которых наиболее известным остался алгоритм “Apriori” (Agrawal, Srikant, 1994).

Полный перебор (метод «грубой силы» -brute force).

Ясно, что полным перебором можно решить любую задачу, решение которой лежит в ограниченном множестве (сила есть - ума не надо). Другое дело - цена вопроса.

Для небольшого числа транзакций вполне можно воспользоваться следующим алгоритмом.

Можно этот алгоритм слегка улучшить.
Лучший способ: итеративная генерация правил с минимальной точностью.
Наблюдение: если выполняется n-последовательное правило, то также выполняются все соответствующие (n-1) -концептивные правила.
Алгоритм: генерировать n-последовательных правил-кандидатов из (n-1) -концептивных правил (аналогично алгоритму для наборов элементов).

Apriory

Частые наборы предметов: наборы предметов с желаемой минимальной поддержкой.
Замечание: если {A, B} является частым набором элементов, то и A, и B также являются частыми наборами элементов. Обратное неверно.

Основная идея (алгоритм Apriori):

Схематически алгоритм выглядит следующим образом (значение поддержки-support можно не нормировать).
Демо взято отсюда
Рассмотрим пошаговое применение Apriory к рассматриваемому примеру.
Наиболее часто встречаемые одноэлементные наборы по порогу 2.
Далее из этих элементов сформируем наиболее часто встречающиеся по порогу 2 двухэлементные наборы .
Значение confidence (достоверность) характеризует насколько часто срабатывает правило. Если confidence=1, то правило срабатывает всегда. Тривиальный случай.
Если Lift>1, то приобретение одного товара, способствует приобретению другого.
Значение Conviction>1 характеризует надежность правила.
Исходя из этих характеристик, выберем наиболее надежные правила.
Далее из элементов, входящих в данные пары, сформируем тройки. Заметим, что в этом случае \( conf(x_i\cup x_j\cup x_k)=\frac{supp(x_i\cup x_j\cup x_k)}{supp(x_i\cup x_j)}. \)
Отберем лучшие тройки
Остается выбрать четверки
Вот, пожалуй, и все.

Полезная литература. Книги.

  1. Berry L. Data Mining Techniques For Marketing, Sales, and Customer Relationship Management / L.Berry, G.Linoff; Second Edition .— Indianapolis, Indiana: Wiley Publishing, Inc., 2004 .— 672 p.
  2. Bramer M. Principles of Data Mining / M.Bramer; Third Edition .— London: Springer, 2007 .— 530 с.
  3. Brown S. Data Mining For Dummies / S.Brown .— Hoboken, New Jersey: John Wiley & Sons, Inc, 2014 .— 410 p.
  4. Charu C. Aggarwal Data Mining. The Textbook. / C.A.Charu; — Springer, 2015 .— 746 p.
  5. Clarke B. Principles and Theory for Data Mining and Machine Learning / B.Clarke, E.Fokoue, H.Zhang .— Dordrecht Heidelberg London New York: Springer, 2009 .— 793 с.
  6. Data Analysis, Machine Learning and Applications / C.Preisach, H.Burkhardt, L.Schmidt-Thieme, R.Decker and etc.; Proceedings of the 31st Annual Conference of the Gesellschaft für Klassifikation, Albert-Ludwigs-Universität Freiburg, March 7–9, 2007 .— Berlin Heidelberg: Springer-Verlag, 2008 .— 703 p.
  7. Dynamic Warehousing: Data Mining Made Easy / C.Ballard, J.Rollins, J.Ramos та ін. .— IBM: International Technical Support Organization, 2007 .— 554 p.
  8. Giudici P. Applied data mining: statistical methods for business and industry / P.Giudici .— West Sussex, England: John Wiley & Sons Ltd, 2003 .— 378 с.
  9. Han J. Data Mining Concepts and Techniques / J.Han, M.Kamber, J.Pei; Third Edition .— 225 Wyman Street, Waltham, MA 02451, USA: Morgan Kaufmann Publishers is an imprint of Elsevier, 2012 .— 740 p.
  10. Hand D. Principles of Data Mining / D.Hand, H.Mannila, P.Smyth .— MIT: The MIT Press, 2001 .— 546 p.
  11. Harrington P. Machine Learning in Action / P.Harrington .— Shelter Island: Manning Publications Co., 2012 .— 354 p.
  12. Liu B. Web Data Mining. Exploring Hyperlinks, Contents, and Usage Data / B.Li .— London New York Heidelberg Dordrecht: Springer, 2011 .— 643 p.
  13. Poncelet P. Data Mining Patterns: New Methods and Applications / P.Poncelet, M.Teisseire, F.Masseglia .— NY: Information Science Reference, 2008 .— 324 p.
  14. Sammut C. Encyclopedia of Machine Learning / C.Sammut, G.Webb .— NY: Springer Science+Business Media, 2010 .— 1059 p.
  15. Tan Pang-Ning. Introduction to Data Mining. Instructor’s Solution Manual. / Pang-Ning Tan, M.Steinbach, V.Kumar.— Pearson Addison-Wesley, 2006 .— 165 p.
  16. The Top Ten Algorithms in DataMining; Vipin Kumar (Editor) .— Taylor & Francis Group, LLC, 2009 .— 2006 p.
  17. Witten I.H. Data Mining. Practical Machine Learning Tools and Techniques / Ian H. Witten, Eibe Frank; Second Edition .— San Francisco: Elsevier Inc., 2005 .— 558 p.
  18. Zaki M.J. Data Mining and Analysis: Fundamental Concepts and Algorithms / M.J.Zaki, W.Meira .— New York: Cambridge University Press, 2014 .— 660 p.
  19. Флах П. Машинное обучение. Наука и искусство построения алгоритмов, которые извлекают знания из данных / П.Флах .— М: ДМК, 2015 .— 399 с.

Полезная литература. Статьи.

  1. Agrawal R. Fast Algorithms for Mining Association Rules / R.Agrawal, R.Srikant // 20th VLDB conference .— Santiago, Chile, 1994 .— P.487-499.
  2. Agrawal R. Mining Association Rules between Sets of Items in Large Databases / R.Agrawal, T.Imielinski, A.Swami // ACM SIGMOD .— Washington DC, USA, 1993 .— P.1-10.
  3. D.J. Power «Ask Dan!»
  4. Introduction to arules - A computational environment for mining association rules and frequent item sets / M.Hahsler, B.Grun, K.Hornik, C.Buchta // Journal of Statistical software .— 2005 .— №14 .— P.1-39.
  5. Liu B. Integrating Classification and Association Rule Mining / B.Liu, W.Hsu, Y.Ma // Appeared in KDD-98 .— New York, 1998 .— P.1-7.
  6. Rajan R.H. A Method for Classification based on Associati using Ontology in Web Data / R.H.Rajan, J.P.Dhas // International Journal of Computer Applications .— 2012 .— №8 (49) .— P.13-17.
  7. Белим С.В. Автоматический метод анализа множества ассоциативных правил в исследовании деятельности общественных организаций / С.В.Белим, Т.Б.Смирнова, А.Н.Мироненко // Proceedings of the Workshop on Data, Modeling and Security .— Омск, 2017 .— C.1-7.
  8. Городецкий В.И. Ассоциативный и причинный анализ и ассоциативные байесовские сети / В.И.Городецкий, В.В.Самойлов // Труды СПИИРАН .— 2009 .— №9 .— C.13-65.
  9. Зайко Т.А. Ассоциативные правила в интеллектуальном анализе данных / Т.А.Зайко, А.А.Олейник, С.А.Субботин // Вестник НТУ "ХПИ" .— 2013 .— №39 (1012) .— C.82-95.
  10. Паклин Н.Б. Ассоциативные правила в программах банковской лояльности / Н.Б.Паклин, С.В.Уланов // Банковская система .— 2009 .— №24(360) .— C.25-29.
  11. Черенков И.А. Прогнозирование на основе новостного потока посредством ассоциативных правил / И.А.Черенков // Энергетика .— 2012 .— №11(105) .— C.38-42.

Вопрос-ответ.

Задать вопрос: