Règle d'association

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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'associations 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 ventes des chaines 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 de la ménagère, les règles d'associations 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[modifier | modifier le code]

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[modifier | modifier le code]

Définition[modifier | modifier le code]

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

  • Définition : Soit \Iota= \left\{i_1,i_2,...,i_m \right\} un ensemble d'items. Soit \Tau= \left\{t_1,t_2,...,t_n \right\} un ensemble de transactions, telles que t_i soit un sous-ensemble de \Iota (ie t_i  \subseteq \Iota). Une règle d'association s'exprime sous la forme :
 \Chi  \rightarrow Y , où \Chi \in \Tau ,~ Y \in \Tau, et \Chi \cap Y = \empty

Notions utiles[modifier | modifier le code]

  •  \Chi est un sous-ensemble de  \Iota appelé itemset.
  • Le recouvrement ou la couverture de  \Chi \text{ dans } \Tau noté  \Kappa_{\Tau} \bigl( \Chi \bigr) est définie par \left\{k ={1,2,..n} | \Chi \subseteq t_k \right\} . Remarque :  \Kappa_{\Tau} \bigl( \Chi \cup Y \bigr) = \Kappa_{\Tau} \bigl( \Chi \bigr) \cap \Kappa_{\Tau} \bigl( Y \bigr) .
  • Le compteur de support (« support count ») de \Chi dans \Tau est le nombre de transactions de \Tau qui contiennent \Chi. On le note \Chi .count = | \Kappa_{\Tau} \bigl( \Chi \bigr)| .
  • Le support (« support ») est alors la proportion des transactions de \Tau contenant \Chi, soit Supp(\Chi) =  \frac{ \Chi.count }{Card(\Tau)} . Celui-ci peut être vu comme une estimation de la probabilité \Pr( \Chi ).
  • 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  \Chi  \rightarrow Y est défini par la proportion de transactions de \Tau qui contiennent  \Chi \cup Y (à la fois X et Y, et non X ou Y), soit Supp( \Chi \cup Y ). Il s'agit donc d'une estimation de la probabilité \Pr( \Chi \cup Y).
    • L'indice de confiance (« confidence ») d'une règle  \Chi  \rightarrow Y est défini par la proportion de transactions de \Tau contenant \Chi qui contiennent aussi Y, soit \frac{( \Chi \cup Y ).count }{\Chi.count} . Il peut être vu comme une estimation de la probabilité conditionnelle \Pr(Y|\Chi). Remarque : Conf( \Chi  \rightarrow Y ) = \frac{Supp(\Chi \cup Y)}{Supp(\Chi)} .
  • Le « lift » d'une règle  \Chi  \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(\Chi \cup Y)}{Supp(\Chi).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[modifier | modifier le code]

Apriori[modifier | modifier le code]

Article principal : Algorithme APriori

Apriori[6] est le plus connu des algorithmes de Règles d'association.

Eclat[modifier | modifier le code]

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

FP-growth[modifier | modifier le code]

FP-growth (frequent pattern growth)[8] 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 taches 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[modifier | modifier le code]

GUHA[9] (« 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[10] 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 structure de données en tableau (« Bit array »).

One-attribute-rule[modifier | modifier le code]

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[11] à découvert que les règles simples avec un seul attribut dans la condition fonctionnent réellement bien.

OPUS[modifier | modifier le code]

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[12]. Initialement utilisé pour trouver des règles pour une conclusion donnée[12],[13], il a par la suite été étendu pour trouver des règles avec n'importe quel item comme conclusion[14]. Le moteur de recherche OPUS est la technologie centrale dans le populaire système de recherche d'association Magnum Opus.

Zero-attribute-rule[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Notes[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Références[modifier | modifier le code]

  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.
  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
  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
  6. Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.
  7. Mohammed J. Zaki. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering 12(3):372-390, May/June 2000.
  8. Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. Mining frequent patterns without candidate generation. Data Mining and Knowledge Discovery 8:53-87, 2004.
  9. GUHA GUHA - basic information Site officiel
  10. P. Hájek, P. Havránek Mechanising Hypothesis Formation – Mathematical Foundations for a General Theory, Springer-Verlag, Édition 1978, ISBN 0387087389
  11. Peter Ross, OneR: the simplest method
  12. 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.
  13. R.J. Bayardo, R. Agrawal et D. Gunopulos, « Constraint-based rule mining in large, dense databases », Data Mining and Knowledge Discovery, vol. 4, no 2,‎ 2000, p. 217–240 (DOI 10.1023/A:1009895914772)
  14. 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