Règle d'association

Diagramme montrant une représentation visuelle de la manière dont les relations entre les transactions peuvent être découvertes grâce à l'extraction de règles d'association.

Dans le domaine du data mining la recherche des règles d'association est une méthode populaire étudiée d'une manière approfondie dont le but est de découvrir des relations ayant un intérêt pour le statisticien entre deux ou plusieurs variables stockées dans de très importantes bases de données. Piatetsky-Shapiro^[1] présentent des règles d'association extrêmement fortes découvertes dans des bases de données en utilisant différentes mesures d’intérêt. En se basant sur le concept de relations fortes, Rakesh Agrawal et son équipe^[2] présente des règles d'association dont le but est de découvrir des similitudes entre des produits dans des données saisies sur une grande échelle dans les systèmes informatiques des points de vente des chaînes de supermarchés. Par exemple, une règle découverte dans les données de ventes dans un supermarché pourrait indiquer qu'un client achetant des oignons et des pommes de terre simultanément, serait susceptible d'acheter un hamburger. Une telle information peut être utilisée comme base pour prendre des décisions marketing telles que par exemple des promotions ou des emplacements bien choisis pour les produits associés. En plus des exemples ci-dessus concernant le panier des ménages, les règles d'association sont employées aujourd'hui dans plusieurs domaines incluant celui de la fouille du web, de la détection d'intrusion et de la bio-informatique.

Histoire

Le concept de règle d'association a été popularisé, en particulier, par un article de Rakesh Agrawal^[2] de 1993. Mais il est possible que cette notion ait été découverte sous le nom de GUHA en 1966 par Petr Hájek et ses collègues^[3].

Principes

Définition

Une règle d'association peut être définie formellement comme ceci^[4]^,^[5] :

Définition : Soit $\mathrm {I} =\left\{i_{1},i_{2},...,i_{m}\right\}$ un ensemble d'indices (items) et $\mathrm {T} =\left\{t_{1},t_{2},...,t_{n}\right\}$ un ensemble de transactions, telles que $t_{i}$ contient un sous-ensemble de $\mathrm {I}$ (ie $t_{i}\subseteq \mathrm {I}$ ). Une règle d'association, qui peut-être vraie ou fausse, s'exprime sous la forme :

\mathrm {X} \rightarrow Y

, où

\mathrm {X} \in \mathrm {T} ,~Y\in \mathrm {T} ,

et

\mathrm {X} \cap Y=\emptyset

Notions utiles

Pour un sous-ensemble $X$ d'indices $X\subseteq \mathrm {I}$ (appelé itemset) :

Le recouvrement ou la couverture de $X$ (dans $T$ ) est l'ensemble des transactions observées contenant $X$ : $\mathrm {K} _{T}{\bigl (}X{\bigr )}=\left\{k={1,2,..n}|X\subseteq t_{k}\right\}$ .

On remarquera que $\mathrm {K} _{T}{\bigl (}X\cup Y{\bigr )}=\mathrm {K} _{T}{\bigl (}X{\bigr )}\cap \mathrm {K} _{T}{\bigl (}Y{\bigr )}$ , traduisant le fait que $X\cup Y\subseteq t$ si et seulement si $X\subseteq t$ et $Y\subseteq t$ .

Le compteur de support (« support count ») de $\mathrm {X}$ dans $\mathrm {T}$ est le nombre de transactions de $\mathrm {T}$ qui contiennent $\mathrm {X}$ . On le note $\mathrm {X} .count=|\mathrm {K} _{\mathrm {T} }{\bigl (}\mathrm {X} {\bigr )}|$ .
Le support (« support ») est alors la proportion des transactions de $\mathrm {T}$ contenant $\mathrm {X}$ , soit $Supp(\mathrm {X} )={\frac {\mathrm {X} .count}{Card(\mathrm {T} )}}$ . Celui-ci peut être vu comme une estimation de la probabilité $\Pr(\mathrm {X} )$ .
La force d'une règle d'association est mesurée par son indice de support et son indice de confiance.
- L'indice de support (« support ») d'une règle $\mathrm {X} \rightarrow Y$ est défini par la proportion de transactions de $\mathrm {T}$ qui contiennent $\mathrm {X} \cap Y$ (à la fois X et Y, et non X ou Y), soit $Supp(\mathrm {X} \cap Y)$ . Il s'agit donc d'une estimation de la probabilité $\Pr(\mathrm {X} \cap Y)$ .
- L'indice de confiance (« confidence ») d'une règle $\mathrm {X} \rightarrow Y$ est défini par la proportion de transactions de $\mathrm {T}$ contenant $\mathrm {X}$ qui contiennent aussi $Y$ , soit ${\frac {(\mathrm {X} \cap Y).count}{\mathrm {X} .count}}$ . Il peut être vu comme une estimation de la probabilité conditionnelle $\Pr(Y|\mathrm {X} )$ . Remarque : $Conf(\mathrm {X} \rightarrow Y)={\frac {Supp(\mathrm {X} \cap Y)}{Supp(\mathrm {X} )}}$ .
Le « lift » d'une règle $\mathrm {X} \rightarrow Y$ mesure l'amélioration apportée par la règle d'association par rapport à un jeu de transactions aléatoire (où X et Y seraient indépendants). Il est défini par ${\frac {Supp(\mathrm {X} \cap Y)}{Supp(\mathrm {X} ).Supp(Y)}}$ . Un « lift » supérieur à 1 traduit une corrélation positive de X et Y, et donc le caractère significatif de l'association.

Algorithmes

Apriori

REQUIRE : Un support seuil S

ENSURE : La liste des itemsets fréquents

L1 ‹— Liste des items dont le support est supérieur à S; i ‹— i+1;

REPEAT

  i ‹— 1;
  À partir des Li-1, construire l'ensemble Ci des itemsets fréquents, candidats comprenant i items ;
  Li ‹— {};
  POUR tout élément e € Ci FAIRE
     SI support(e) > S ALORS
       ajouter e à Li;
     FINSI
  FINPOUR

UNTIL L1 == {}

Eclat

Eclat^[6] est un algorithme de recherche d'associations utilisant les intersections d'ensembles.

FP-growth

FP-growth (frequent pattern growth)^[7] utilise une structure d'arbre (FP-tree) pour stocker une forme compressée d'une base de données. FP-growth adopte une stratégie de découpage pour décomposer les tâches d'exploration de données et les bases de données. Il utilise une méthode « pattern fragment growth » pour éviter le coûteux processus de génération et de test des candidats, utilisé par Apriori.

GUHA procedure ASSOC

GUHA^[8] (« General Unary Hypotheses Automaton ») est une méthode de génération automatique d'hypothèses à partir de données empiriques, c'est donc une méthode d'exploration de données. La procédure ASSOC^[9] est une méthode GUHA qui explore les données en vue de trouver rapidement des règles d'association généralisées en utilisant des structures de données en tableau (« Bit array »).

One-attribute-rule

L'idée qui préside à la conception de l'algorithme OneR (one-attribute-rule) consiste à trouver un attribut à utiliser qui fait le moins d'erreurs de prédiction possibles. Peter Ross^[10] à découvert que les règles simples avec un seul attribut dans la condition fonctionnent réellement bien.

OPUS

OPUS est un algorithme efficace pour la recherche de règles d'association, qui, par opposition à d'autres, ne nécessite pas de contraintes anti-monotones et monotones tels que le support minimum^[11]. Initialement utilisé pour trouver des règles pour une conclusion donnée^[11]^,^[12], il a par la suite été étendu pour trouver des règles avec n'importe quel item comme conclusion^[13]. Le moteur de recherche OPUS est la technologie centrale dans le populaire système de recherche d'association Magnum Opus.

Zero-attribute-rule

Voir aussi

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Association rule learning » (voir la liste des auteurs).

Liens internes

Références

↑ Piatetsky-Shapiro, G. (1991), Discovery, analysis, and presentation of strong rules, in G.Piatetsky-Shapiro & W. J. Frawley, eds, ‘Knowledge Discovery in Databases’, AAAI/MIT Press, Cambridge, MA.
↑ ^{a et b} R. Agrawal; T. Imielinski; A. Swami: Mining Association Rules Between Sets of Items in Large Databases", SIGMOD Conference 1993: 207-216
↑ Petr Hajek, Tomas Feglar, Jan Rauch, David Coufal. The GUHA method, data preprocessing and mining. Database Support for Data Mining Applications, (ISBN 978-3-540-22479-2), Springer, 2004
↑ Gurmeet Singh Manku, Rajeev Motwani, Approximate Frequency Counts over Data Streams
↑ Bing Liu, Web Data Mining, Springer, Édition 2010, Page 14
↑ Mohammed J. Zaki. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering 12(3):372-390, May/June 2000.
↑ Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. Mining frequent patterns without candidate generation. Data Mining and Knowledge Discovery 8:53-87, 2004.
↑ GUHA GUHA - basic information Site officiel
↑ P. Hájek, P. Havránek Mechanising Hypothesis Formation – Mathematical Foundations for a General Theory, Springer-Verlag, Édition 1978, (ISBN 0387087389)
↑ Peter Ross, OneR: the simplest method
↑ ^{a et b} Webb, G. I. (1995). OPUS: An Efficient Admissible Algorithm For Unordered Search. Journal of Artificial Intelligence Research 3. Menlo Park, CA: AAAI Press, pages 431-465 online access.
↑ R.J. Bayardo, R. Agrawal et D. Gunopulos, « Constraint-based rule mining in large, dense databases », Data Mining and Knowledge Discovery, vol. 4, n^o 2,‎ 2000, p. 217–240 (DOI 10.1023/A:1009895914772)
↑ Webb, G. I. (2000). Efficient Search for Association Rules. In R. Ramakrishnan and S. Stolfo (Eds.), Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2000) Boston, MA. New York: The Association for Computing Machinery, pages 99-107. online access

Portail de l’informatique

[piatetsky-1] Piatetsky-Shapiro, G. (1991), Discovery, analysis, and presentation of strong rules, in G.Piatetsky-Shapiro & W. J. Frawley, eds, ‘Knowledge Discovery in Databases’, AAAI/MIT Press, Cambridge, MA.

[Agrawal-2] {a et b} R. Agrawal; T. Imielinski; A. Swami: Mining Association Rules Between Sets of Items in Large Databases", SIGMOD Conference 1993: 207-216

[pospaper-3] Petr Hajek, Tomas Feglar, Jan Rauch, David Coufal. The GUHA method, data preprocessing and mining. Database Support for Data Mining Applications, (ISBN 978-3-540-22479-2), Springer, 2004

[4] Gurmeet Singh Manku, Rajeev Motwani, Approximate Frequency Counts over Data Streams

[5] Bing Liu, Web Data Mining, Springer, Édition 2010, Page 14

[eclat-6] Mohammed J. Zaki. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering 12(3):372-390, May/June 2000.

[fp-growth-7] Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. Mining frequent patterns without candidate generation. Data Mining and Knowledge Discovery 8:53-87, 2004.

[8] GUHA GUHA - basic information Site officiel

[9] P. Hájek, P. Havránek Mechanising Hypothesis Formation – Mathematical Foundations for a General Theory, Springer-Verlag, Édition 1978, (ISBN 0387087389)

[10] Peter Ross, OneR: the simplest method

[OPUS-11] {a et b} Webb, G. I. (1995). OPUS: An Efficient Admissible Algorithm For Unordered Search. Journal of Artificial Intelligence Research 3. Menlo Park, CA: AAAI Press, pages 431-465 online access.

[Bayardo-12] R.J. Bayardo, R. Agrawal et D. Gunopulos, « Constraint-based rule mining in large, dense databases », Data Mining and Knowledge Discovery, vol. 4, n^o 2,‎ 2000, p. 217–240 (DOI 10.1023/A:1009895914772)

[webb-13] Webb, G. I. (2000). Efficient Search for Association Rules. In R. Ramakrishnan and S. Stolfo (Eds.), Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2000) Boston, MA. New York: The Association for Computing Machinery, pages 99-107. online access

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]