Règle d'association

Règle 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 de 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

Sommaire

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 \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 ti soit un sous-ensemble de Ι (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

  • Χ est un sous-ensemble de Ι appelé itemset.
  • Le recouvrement ou la couverture de Χ dans Τ noté \Kappa_{\Tau} \bigl( \Chi \bigr) est définie par \left\{k ={1,2,..n} | \Chi \subseteq t_k \right\}
  • Le compteur de support (« support count ») de Χ dans Τ est le nombre de transactions de Τ qui contiennent Χ. On le note \Chi .count = | \Kappa_{\Tau} \bigl( \Chi \bigr)| .
  • 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éfinie par le pourcentage de transactions de Τ qui contiennent \Chi \cup Y, soit \frac{ (\Chi \cup Y).count }{Card(\Tau)}. Elle peut être vue comme une estimation de la probabilité \Pr( \Chi \cup Y).
    • L'indice de confiance (« confidence ») d'une règle \Chi \rightarrow Y est définie par le pourcentage de transactions de Τ contenant Χ qui contiennent aussi Y, soit \frac{ (\Chi \cup Y).count }{\Chi.count}. Elle peut être vue comme une estimation de la probabilité conditionnelle Pr(Y | Χ). Si X et Y sont indépendants on a (\Chi \cup Y).count = \Chi.count . Y.count.
    • Remarque : on a 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 au hasard. Il est défini par \frac{Supp(\Chi \cup Y)}{Supp(\Chi).Supp(Y)}. La règle d'association apporte quelque chose à l'analyse si le lift est supérieur à 1.

Algorithmes

Apriori

Article principal : Algorithme APriori

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

Eclat

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

FP-growth

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

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

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

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

Voir aussi

Notes

Liens internes

Références

  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, Edition 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, Edition 1978,isbn=0-7869-1850-8
  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, « Constraint-based rule mining in large, dense databases », dans Data Mining and Knowledge Discovery, vol. 4, no 2, 2000, p. 217–240 [lien DOI] 
  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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Règle d'association de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Association de Compagnons Passants Tailleurs De Pierre — Association des compagnons passants tailleurs de pierre L Association de compagnons passants tailleurs de pierre est une fraternité ouvrière d aspirants et compagnons tailleurs de pierre du devoir régie par les articles 21 et 79 du code civil… …   Wikipédia en Français

  • Association des compagnons passants tailleurs de pierre — L Association de compagnons passants tailleurs de pierre est une fraternité ouvrière d aspirants et compagnons tailleurs de pierre du devoir régie par les articles 21 et 79 du code civil local, maintenu en vigueur dans les départements du Bas… …   Wikipédia en Français

  • règle — [ rɛgl ] n. f. • XIIIe, adapt. du lat.; ruile 1119; reille 1105; lat. regula I ♦ (1317) Planchette allongée ou tige à arêtes rectilignes qui sert à guider le crayon, la plume, quand on trace un trait, à mesurer une longueur, etc. ⇒ réglet,… …   Encyclopédie Universelle

  • réglé — règle [ rɛgl ] n. f. • XIIIe, adapt. du lat.; ruile 1119; reille 1105; lat. regula I ♦ (1317) Planchette allongée ou tige à arêtes rectilignes qui sert à guider le crayon, la plume, quand on trace un trait, à mesurer une longueur, etc. ⇒ réglet,… …   Encyclopédie Universelle

  • ASSOCIATION — Le terme «association» comporte deux acceptions d’ampleur différente. En un sens générique, il sert à désigner tout groupement volontaire et permanent formé entre plusieurs personnes, quels qu’en soient la forme, l’objet ou le but. En un sens… …   Encyclopédie Universelle

  • ASSOCIATION LIBRE (psychanalyse) — ASSOCIATION LIBRE, psychanalyse Expression utilisée en psychanalyse pour désigner l’objet de la règle fondamentale, laquelle consiste pour le patient à exprimer toutes les pensées (idées; images; Einfall , dit Freud, «ce qui tombe» dans l’esprit) …   Encyclopédie Universelle

  • Association Internationale Du Transport Aérien — International Air Transport Association Création Avril 1945 à La Havane Siège …   Wikipédia en Français

  • Association Internationale du Transport Aérien — International Air Transport Association Création Avril 1945 à La Havane Siège …   Wikipédia en Français

  • Association internationale du transport aerien — Association internationale du transport aérien Association internationale du transport aérien International Air Transport Association Création Avril 1945 à La Havane Siège …   Wikipédia en Français

  • Regle de droit — Règle de droit La règle de droit ou droit objectif est « la norme juridiquement obligatoire, quelle que soit sa source (règle légale, coutumière), son degré de généralité (règle générale, règle spéciale), sa portée (règle absolue, rigide,… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”