Apprentissage des règles d'association

L'apprentissage des règles d'association est une méthode d'apprentissage automatique basée sur des règles permettant de découvrir des relations intéressantes entre des variables dans de grandes bases de données. Elle vise à identifier les règles fortes découvertes dans les bases de données à l'aide de certaines mesures d'intérêt. Dans toute transaction donnée avec une variété d'éléments, les règles d'association sont destinées à découvrir les règles qui déterminent comment ou pourquoi certains éléments sont connectés.

En se basant sur le concept de règles fortes, Rakesh Agrawal , Tomasz Imieliński et Arun Swami ont introduit des règles d'association permettant de découvrir des régularités entre produits dans les données de transactions à grande échelle enregistrées par les systèmes de point de vente (POS) des supermarchés. Par exemple, la règle trouvée dans les données de vente d'un supermarché indiquerait que si un client achète des oignons et des pommes de terre ensemble, il est susceptible d'acheter également de la viande hachée. Ces informations peuvent servir de base à des décisions concernant des activités marketing telles que, par exemple, des prix promotionnels ou des placements de produits . ${\displaystyle \{\mathrm {onions,potatoes} \}\Rightarrow \{\mathrm {burger} \ <semantics> <mrow> <mstyle> <mo>{</mo> <mrow> <mi>o</mi> <mi>n</mi> <mi>i</mi> <mi>o</mi> <mi>n</mi> <mi>s</mi> <mo>,</mo> <mi>p</mi> <mi>o</mi> <mi>t</mi> <mi>a</mi> <mi>t</mi> <mi>o</mi> <mi>e</mi> <mi>s</mi> </mrow> <mo>}</mo> <mo>⇒</mo> <mo>{</mo> <mrow> <mi>b</mi> <mi>u</mi> <mi>r</mi> <mi>g</mi> <mi>e</mi> <mi>r</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\mathrm {onions,potatoes} \}\Rightarrow \{\mathrm {burger} \}}</annotation> </semantics> </math><img src=$

Outre l'exemple ci-dessus issu de l'analyse du panier de consommation , les règles d'association sont aujourd'hui utilisées dans de nombreux domaines d'application, notamment l'exploration de l'utilisation du Web , la détection d'intrusion , la production continue et la bioinformatique . Contrairement à l'exploration de séquences , l'apprentissage des règles d'association ne prend généralement pas en compte l'ordre des éléments au sein d'une transaction ou entre les transactions.

L'algorithme de règle d'association lui-même se compose de divers paramètres qui peuvent rendre son exécution difficile pour ceux qui n'ont pas une certaine expertise en exploration de données, avec de nombreuses règles difficiles à comprendre.

Définition

Suivant la définition originale d'Agrawal, Imieliński, Swami le problème de l'exploration des règles d'association est défini comme suit :

Soit un ensemble de n attributs binaires appelés éléments . ${\displaystyle I=\{i_{1},i_{2},\ldots ,i_{n}\ <semantics> <mrow> <mstyle> <mi>I</mi> <mo>=</mo> <mo>{</mo> <msub> <mi>i</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>i</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>i</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle I=\{i_{1},i_{2},\ldots ,i_{n}\}}</annotation> </semantics> </math><img src=$

Soit un ensemble de transactions appelé base de données . ${\displaystyle D=\{t_{1},t_{2},\ldots ,t_{m}\ <semantics> <mrow> <mstyle> <mi>D</mi> <mo>=</mo> <mo>{</mo> <msub> <mi>t</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>t</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>t</mi> <mrow> <mi>m</mi> </mrow> </msub> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle D=\{t_{1},t_{2},\ldots ,t_{m}\}}</annotation> </semantics> </math><img src=$

Chaque transaction dans D possède un identifiant de transaction unique et contient un sous-ensemble des éléments dans I.

Une règle est définie comme une implication de la forme :

{\displaystyle X\Rightarrow Y <semantics> <mrow> <mstyle> <mi>X</mi> <mo>⇒</mo> <mi>Y</mi> </mstyle> </mrow> <annotation>{\displaystyle X\Rightarrow Y}</annotation> </semantics> </math></span><img src=

{\displaystyle X,Y\subseteq I <semantics> <mrow> <mstyle> <mi>X</mi> <mo>,</mo> <mi>Y</mi> <mo>⊆</mo> <mi>I</mi> </mstyle> </mrow> <annotation>{\displaystyle X,Y\subseteq I}</annotation> </semantics> </math></span><img src=

Dans Agrawal, Imieliński, Swami une règle est définie uniquement entre un ensemble et un seul élément, pour . ${\displaystyle X\Rightarrow i_{j <semantics> <mrow> <mstyle> <mi>X</mi> <mo>⇒</mo> <msub> <mi>i</mi> <mrow> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle X\Rightarrow i_{j}}</annotation> </semantics> </math><img src=$ ${\displaystyle i_{j}\in I <semantics> <mrow> <mstyle> <msub> <mi>i</mi> <mrow> <mi>j</mi> </mrow> </msub> <mo>∈</mo> <mi>I</mi> </mstyle> </mrow> <annotation>{\displaystyle i_{j}\in I}</annotation> </semantics> </math><img src=$

Chaque règle est composée de deux ensembles d'éléments différents, également appelés ensembles d'éléments , X et Y , où X est appelé antécédent ou côté gauche (LHS) et Y conséquent ou côté droit (RHS). L'antécédent est l'élément qui peut être trouvé dans les données tandis que le conséquent est l'élément trouvé lorsqu'il est combiné avec l'antécédent. L'énoncé est souvent lu comme si X alors Y , où l'antécédent ( X ) est le si et le conséquent ( Y ) est le alors . Cela implique simplement qu'en théorie, chaque fois que X apparaît dans un ensemble de données, Y apparaît également. ${\displaystyle X\Rightarrow Y <semantics> <mrow> <mstyle> <mi>X</mi> <mo>⇒</mo> <mi>Y</mi> </mstyle> </mrow> <annotation>{\displaystyle X\Rightarrow Y}</annotation> </semantics> </math><img src=$

Processus

Les règles d'association sont créées en recherchant dans les données des modèles fréquents de type "si-alors" et en utilisant un certain critère sous Support et Confiance pour définir quelles sont les relations les plus importantes. Le support est la preuve de la fréquence à laquelle un élément apparaît dans les données fournies, car la confiance est définie par le nombre de fois que les énoncés "si-alors" sont jugés vrais. Cependant, il existe un troisième critère qui peut être utilisé, il s'appelle Lift et il peut être utilisé pour comparer la confiance attendue et la confiance réelle. Lift montrera combien de fois l'énoncé "si-alors" devrait être jugé vrai.

Les règles d'association sont conçues pour calculer à partir d'ensembles d'éléments, qui sont créés par deux éléments ou plus. Si les règles étaient élaborées à partir de l'analyse de tous les ensembles d'éléments possibles à partir des données, il y aurait tellement de règles qu'elles n'auraient aucune signification. C'est pourquoi les règles d'association sont généralement élaborées à partir de règles bien représentées par les données.

Il existe de nombreuses techniques d'exploration de données différentes que vous pouvez utiliser pour trouver certaines analyses et résultats, par exemple, il existe l'analyse de classification, l'analyse de clustering et l'analyse de régression. La technique que vous devez utiliser dépend de ce que vous recherchez avec vos données. Les règles d'association sont principalement utilisées pour trouver des analyses et une prédiction du comportement des clients. Pour l'analyse de classification, elle serait très probablement utilisée pour remettre en question, prendre des décisions et prédire le comportement. L'analyse de clustering est principalement utilisée lorsqu'aucune hypothèse n'est faite sur les relations probables au sein des données. L'analyse de régression est utilisée lorsque vous souhaitez prédire la valeur d'une variable dépendante continue à partir d'un certain nombre de variables indépendantes.

Avantages

L'utilisation des règles d'association présente de nombreux avantages, notamment la recherche du modèle qui permet de comprendre les corrélations et les cooccurrences entre les ensembles de données. La médecine est un très bon exemple concret d'utilisation des règles d'association. La médecine utilise les règles d'association pour aider à diagnostiquer les patients. Lors du diagnostic des patients, de nombreuses variables doivent être prises en compte, car de nombreuses maladies partagent des symptômes similaires. Grâce à l'utilisation des règles d'association, les médecins peuvent déterminer la probabilité conditionnelle d'une maladie en comparant les relations entre les symptômes des cas passés.

Inconvénients

Cependant, les règles d'association entraînent également de nombreux inconvénients, comme la recherche des paramètres et des seuils appropriés pour l'algorithme d'exploration. Mais il y a aussi l'inconvénient d'avoir un grand nombre de règles découvertes. La raison en est que cela ne garantit pas que les règles seront jugées pertinentes, mais cela peut également entraîner une faible performance de l'algorithme. Parfois, les algorithmes implémentés contiennent trop de variables et de paramètres. Pour quelqu'un qui n'a pas une bonne notion de l'exploration de données, cela peut lui causer des difficultés à le comprendre.

Seuils

Treillis d'ensembles d'éléments fréquents, où la couleur de la boîte indique le nombre de transactions contenant la combinaison d'éléments. Notez que les niveaux inférieurs du treillis peuvent contenir au plus le nombre minimum d'éléments de leurs parents ; par exemple, {ac} ne peut contenir qu'au plus d'éléments. C'est ce qu'on appelle la *propriété de fermeture vers le bas* . ${\displaystyle \min(a,c) <semantics> <mrow> <mstyle> <mo>min</mo> <mo>(</mo> <mi>a</mi> <mo>,</mo> <mi>c</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle \min(a,c)}</annotation> </semantics> </math></span><img src=$

Lorsque vous utilisez des règles d'association, vous n'utiliserez probablement que le support et la confiance. Cependant, cela signifie que vous devez satisfaire simultanément à un support minimum spécifié par l'utilisateur et à une confiance minimum spécifiée par l'utilisateur. En général, la génération de règles d'association est divisée en deux étapes différentes qui doivent être appliquées :

Un seuil de support minimum pour trouver tous les ensembles d'éléments fréquents présents dans la base de données.
Un seuil de confiance minimum pour les ensembles d'éléments fréquents trouvés pour créer des règles.

Le seuil de soutien est de 30%, le seuil de confiance est de 50%

Le tableau de gauche contient les données originales non organisées et le tableau de droite est organisé en fonction des seuils. Dans ce cas, l'élément C est meilleur que les seuils de soutien et de confiance, c'est pourquoi il est premier. L'élément A est deuxième car ses valeurs de seuil sont exactes. L'élément D a atteint le seuil de soutien mais pas de confiance. L'élément B n'a atteint ni le seuil de soutien ni le seuil de confiance et c'est pourquoi il est dernier.

Trouver tous les itemsets fréquents dans une base de données n'est pas une tâche facile car cela implique de parcourir toutes les données pour trouver toutes les combinaisons d'éléments possibles à partir de tous les itemsets possibles. L'ensemble des itemsets possibles est l' ensemble de puissance sur I et a une taille , bien sûr cela signifie exclure l'ensemble vide qui n'est pas considéré comme un itemset valide. Cependant, la taille de l'ensemble de puissance augmentera exponentiellement avec le nombre d'éléments n qui se trouve dans l'ensemble de puissance I . Une recherche efficace est possible en utilisant la propriété de fermeture vers le bas du support (également appelée anti-monotonie ). Cela garantirait qu'un itemset fréquent et tous ses sous-ensembles sont également fréquents et n'auront donc aucun itemsets peu fréquents comme sous-ensemble d'un itemset fréquent. En exploitant cette propriété, des algorithmes efficaces (par exemple, Apriori et Eclat ) peuvent trouver tous les itemsets fréquents. ${\displaystyle 2^{n}-1 <semantics> <mrow> <mstyle> <msup> <mn>2</mn> <mrow> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle 2^{n}-1}</annotation> </semantics> </math><img src=$

Concepts utiles

Pour illustrer les concepts, nous utilisons un petit exemple du domaine des supermarchés. Le tableau 2 montre une petite base de données contenant les éléments où, dans chaque entrée, la valeur 1 signifie la présence de l'élément dans la transaction correspondante et la valeur 0 représente l'absence d'un élément dans cette transaction. L'ensemble des éléments est . ${\displaystyle I=\{\mathrm {milk,bread,butter,beer,diapers,eggs,fruit} \ <semantics> <mrow> <mstyle> <mi>I</mi> <mo>=</mo> <mo>{</mo> <mrow> <mi>m</mi> <mi>i</mi> <mi>l</mi> <mi>k</mi> <mo>,</mo> <mi>b</mi> <mi>r</mi> <mi>e</mi> <mi>a</mi> <mi>d</mi> <mo>,</mo> <mi>b</mi> <mi>u</mi> <mi>t</mi> <mi>t</mi> <mi>e</mi> <mi>r</mi> <mo>,</mo> <mi>b</mi> <mi>e</mi> <mi>e</mi> <mi>r</mi> <mo>,</mo> <mi>d</mi> <mi>i</mi> <mi>a</mi> <mi>p</mi> <mi>e</mi> <mi>r</mi> <mi>s</mi> <mo>,</mo> <mi>e</mi> <mi>g</mi> <mi>g</mi> <mi>s</mi> <mo>,</mo> <mi>f</mi> <mi>r</mi> <mi>u</mi> <mi>i</mi> <mi>t</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle I=\{\mathrm {milk,bread,butter,beer,diapers,eggs,fruit} \}}</annotation> </semantics> </math><img src=$

Un exemple de règle pour un supermarché pourrait être que si du beurre et du pain sont achetés, les clients achètent également du lait. ${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \ <semantics> <mrow> <mstyle> <mo>{</mo> <mrow> <mi>b</mi> <mi>u</mi> <mi>t</mi> <mi>t</mi> <mi>e</mi> <mi>r</mi> <mo>,</mo> <mi>b</mi> <mi>r</mi> <mi>e</mi> <mi>a</mi> <mi>d</mi> </mrow> <mo>}</mo> <mo>⇒</mo> <mo>{</mo> <mrow> <mi>m</mi> <mi>i</mi> <mi>l</mi> <mi>k</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}</annotation> </semantics> </math><img src=$

Afin de sélectionner des règles intéressantes parmi l'ensemble des règles possibles, des contraintes sur diverses mesures de signification et d'intérêt sont utilisées. Les contraintes les plus connues sont les seuils minimaux de support et de confiance.

Soient des ensembles d'éléments, une règle d'association et T un ensemble de transactions d'une base de données donnée. ${\displaystyle X,Y <semantics> <mrow> <mstyle> <mi>X</mi> <mo>,</mo> <mi>Y</mi> </mstyle> </mrow> <annotation>{\displaystyle X,Y}</annotation> </semantics> </math><img src=$ ${\displaystyle X\Rightarrow Y <semantics> <mrow> <mstyle> <mi>X</mi> <mo>⇒</mo> <mi>Y</mi> </mstyle> </mrow> <annotation>{\displaystyle X\Rightarrow Y}</annotation> </semantics> </math><img src=$

Remarque : cet exemple est extrêmement petit. Dans les applications pratiques, une règle doit être prise en charge par plusieurs centaines de transactions avant de pouvoir être considérée comme statistiquement significative, et les ensembles de données contiennent souvent des milliers ou des millions de transactions.

Soutien

Le support est une indication de la fréquence à laquelle l'ensemble d'éléments apparaît dans l'ensemble de données.

Dans notre exemple, il peut être plus facile d’expliquer le support en écrivant où A et B sont des ensembles d’éléments distincts qui apparaissent en même temps dans une transaction. ${\displaystyle { ext{support}}=P(A\cap B)={\frac {({ ext{number of transactions containing }}A{ ext{ and }}B)}{ ext{ (total number of transactions) <semantics> <mrow> <mstyle> <mrow> <mtext>support</mtext> </mrow> <mo>=</mo> <mi>P</mi> <mo>(</mo> <mi>A</mi> <mo>∩</mo> <mi>B</mi> <mo>)</mo> <mo>=</mo> <mrow> <mfrac> <mrow> <mo>(</mo> <mrow> <mtext>number of transactions containing </mtext> </mrow> <mi>A</mi> <mrow> <mtext> and </mtext> </mrow> <mi>B</mi> <mo>)</mo> </mrow> <mtext> (total number of transactions)</mtext> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle { ext{support}}=P(A\cap B)={\frac {({ ext{number of transactions containing }}A{ ext{ and }}B)}{ ext{ (total number of transactions)}}}}</annotation> </semantics> </math><img src=$

En prenant le tableau 2 comme exemple, l'ensemble d'éléments a un support de 1/5=0,2 puisqu'il apparaît dans 20 % de toutes les transactions (1 transaction sur 5). L'argument de support de X est un ensemble de conditions préalables, et devient donc plus restrictif à mesure qu'il grandit (au lieu d'être plus inclusif). ${\displaystyle X=\{\mathrm {beer,diapers} \ <semantics> <mrow> <mstyle> <mi>X</mi> <mo>=</mo> <mo>{</mo> <mrow> <mi>b</mi> <mi>e</mi> <mi>e</mi> <mi>r</mi> <mo>,</mo> <mi>d</mi> <mi>i</mi> <mi>a</mi> <mi>p</mi> <mi>e</mi> <mi>r</mi> <mi>s</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle X=\{\mathrm {beer,diapers} \}}</annotation> </semantics> </math><img src=$

De plus, l'ensemble d'éléments bénéficie d'un support de 1/5=0,2 car il apparaît également dans 20 % de toutes les transactions. ${\displaystyle Y=\{\mathrm {milk,bread,butter} \ <semantics> <mrow> <mstyle> <mi>Y</mi> <mo>=</mo> <mo>{</mo> <mrow> <mi>m</mi> <mi>i</mi> <mi>l</mi> <mi>k</mi> <mo>,</mo> <mi>b</mi> <mi>r</mi> <mi>e</mi> <mi>a</mi> <mi>d</mi> <mo>,</mo> <mi>b</mi> <mi>u</mi> <mi>t</mi> <mi>t</mi> <mi>e</mi> <mi>r</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle Y=\{\mathrm {milk,bread,butter} \}}</annotation> </semantics> </math><img src=$

En utilisant des antécédents et des conséquents, cela permet à un data miner de déterminer le support de l'achat de plusieurs articles ensemble par rapport à l'ensemble des données. Par exemple, le tableau 2 montre que si l'on achète du lait, l'achat de pain a un support de 0,4 ou 40 %. Cela parce que dans 2 transactions sur 5, on achète du lait et du pain. Dans des ensembles de données plus petits comme cet exemple, il est plus difficile de voir une forte corrélation lorsqu'il y a peu d'échantillons, mais lorsque l'ensemble de données s'agrandit, le support peut être utilisé pour trouver une corrélation entre deux ou plusieurs produits dans l'exemple du supermarché.

Les seuils de support minimum sont utiles pour déterminer quels ensembles d'éléments sont préférés ou intéressants.

Si nous fixons le seuil de support à ≥ 0,4 dans le tableau 3, alors le serait supprimé car il ne respecte pas le seuil minimum de 0,4. Le seuil minimum est utilisé pour supprimer les échantillons où il n'y a pas de support ou de confiance suffisamment fort pour considérer l'échantillon comme important ou intéressant dans l'ensemble de données. ${\displaystyle \{\mathrm {milk} \}\Rightarrow \{\mathrm {eggs} \ <semantics> <mrow> <mstyle> <mo>{</mo> <mrow> <mi>m</mi> <mi>i</mi> <mi>l</mi> <mi>k</mi> </mrow> <mo>}</mo> <mo>⇒</mo> <mo>{</mo> <mrow> <mi>e</mi> <mi>g</mi> <mi>g</mi> <mi>s</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\mathrm {milk} \}\Rightarrow \{\mathrm {eggs} \}}</annotation> </semantics> </math><img src=$

Une autre façon de trouver des échantillons intéressants est de trouver la valeur de (support) × (confiance) ; cela permet à un data miner de voir les échantillons où le support et la confiance sont suffisamment élevés pour être mis en évidence dans l'ensemble de données et inciter à examiner de plus près l'échantillon pour trouver plus d'informations sur le lien entre les éléments.

Le support peut être utile pour trouver le lien entre les produits par rapport à l'ensemble des données, tandis que la confiance examine le lien entre un ou plusieurs éléments et un autre élément. Vous trouverez ci-dessous un tableau qui montre la comparaison et le contraste entre le support et le support × confiance, en utilisant les informations du tableau 4 pour dériver les valeurs de confiance.

Le support de X par rapport à T est défini comme la proportion de transactions dans l'ensemble de données qui contient l'ensemble d'éléments X. En désignant une transaction par où i est l'identifiant unique de la transaction et t est son ensemble d'éléments, le support peut être écrit comme suit : ${\displaystyle (i,t) <semantics> <mrow> <mstyle> <mo>(</mo> <mi>i</mi> <mo>,</mo> <mi>t</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle (i,t)}</annotation> </semantics> </math><img src=$

{\displaystyle \mathrm {support\,of\,X} ={\frac {|\{(i,t)\in T:X\subseteq t\}|}{|T| <semantics> <mrow> <mstyle> <mrow> <mi>s</mi> <mi>u</mi> <mi>p</mi> <mi>p</mi> <mi>o</mi> <mi>r</mi> <mi>t</mi> <mspace></mspace> <mi>o</mi> <mi>f</mi> <mspace></mspace> <mi>X</mi> </mrow> <mo>=</mo> <mrow> <mfrac> <mrow> <mrow> <mo>|</mo> </mrow> <mo>{</mo> <mo>(</mo> <mi>i</mi> <mo>,</mo> <mi>t</mi> <mo>)</mo> <mo>∈</mo> <mi>T</mi> <mo>:</mo> <mi>X</mi> <mo>⊆</mo> <mi>t</mi> <mo>}</mo> <mrow> <mo>|</mo> </mrow> </mrow> <mrow> <mrow> <mo>|</mo> </mrow> <mi>T</mi> <mrow> <mo>|</mo> </mrow> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \mathrm {support\,of\,X} ={\frac {|\{(i,t)\in T:X\subseteq t\}|}{|T|}}}</annotation> </semantics> </math></span><img src=

Cette notation peut être utilisée pour définir des ensembles de données plus complexes où les articles et les ensembles d'articles peuvent ne pas être aussi simples que notre exemple de supermarché ci-dessus. D'autres exemples où le support peut être utilisé sont la recherche de groupes de mutations génétiques qui fonctionnent collectivement pour provoquer une maladie, l'étude du nombre d'abonnés qui répondent aux offres de mise à niveau et la découverte des produits dans une pharmacie qui ne sont jamais achetés ensemble.

Confiance

La confiance est le pourcentage de toutes les transactions satisfaisant X qui satisfont également Y. ]

Par rapport à T , la valeur de confiance d'une règle d'association, souvent désignée par , est le rapport des transactions contenant à la fois X et Y au montant total des valeurs X présentes, où X est l'antécédent et Y est le conséquent. ${\displaystyle X\Rightarrow Y <semantics> <mrow> <mstyle> <mi>X</mi> <mo>⇒</mo> <mi>Y</mi> </mstyle> </mrow> <annotation>{\displaystyle X\Rightarrow Y}</annotation> </semantics> </math><img src=$

La confiance peut également être interprétée comme une estimation de la probabilité conditionnelle , la probabilité de trouver le RHS de la règle dans les transactions sous la condition que ces transactions contiennent également le LHS. ${\displaystyle P(E_{Y}|E_{X}) <semantics> <mrow> <mstyle> <mi>P</mi> <mo>(</mo> <msub> <mi>E</mi> <mrow> <mi>Y</mi> </mrow> </msub> <mrow> <mo>|</mo> </mrow> <msub> <mi>E</mi> <mrow> <mi>X</mi> </mrow> </msub> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle P(E_{Y}|E_{X})}</annotation> </semantics> </math><img src=$

On le décrit généralement comme suit :

{\displaystyle \mathrm {conf} (X\Rightarrow Y)=P(Y|X)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)}}={\frac {{ ext{number of transactions containing }}X{ ext{ and }}Y}{{ ext{number of transactions containing }}X <semantics> <mrow> <mstyle> <mrow> <mi>c</mi> <mi>o</mi> <mi>n</mi> <mi>f</mi> </mrow> <mo>(</mo> <mi>X</mi> <mo>⇒</mo> <mi>Y</mi> <mo>)</mo> <mo>=</mo> <mi>P</mi> <mo>(</mo> <mi>Y</mi> <mrow> <mo>|</mo> </mrow> <mi>X</mi> <mo>)</mo> <mo>=</mo> <mrow> <mfrac> <mrow> <mrow> <mi>s</mi> <mi>u</mi> <mi>p</mi> <mi>p</mi> </mrow> <mo>(</mo> <mi>X</mi> <mo>∪</mo> <mi>Y</mi> <mo>)</mo> </mrow> <mrow> <mrow> <mi>s</mi> <mi>u</mi> <mi>p</mi> <mi>p</mi> </mrow> <mo>(</mo> <mi>X</mi> <mo>)</mo> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <mrow> <mrow> <mtext>number of transactions containing </mtext> </mrow> <mi>X</mi> <mrow> <mtext> and </mtext> </mrow> <mi>Y</mi> </mrow> <mrow> <mrow> <mtext>number of transactions containing </mtext> </mrow> <mi>X</mi> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \mathrm {conf} (X\Rightarrow Y)=P(Y|X)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)}}={\frac {{ ext{number of transactions containing }}X{ ext{ and }}Y}{{ ext{number of transactions containing }}X}}}</annotation> </semantics> </math></span><img src=

L'équation montre que la confiance peut être calculée en calculant la cooccurrence des transactions X et Y dans l'ensemble de données par rapport aux transactions contenant uniquement X. Cela signifie que le nombre de transactions dans X et Y est divisé par celui de X uniquement .

Par exemple, le tableau 2 montre la règle qui a un niveau de confiance de dans l'ensemble de données, ce qui signifie que chaque fois qu'un client achète du beurre et du pain, il achète également du lait. Cet exemple particulier démontre que la règle est correcte à 100 % du temps pour les transactions contenant à la fois du beurre et du pain. La règle , cependant, a un niveau de confiance de . Cela suggère que des œufs sont achetés 67 % des fois où des fruits sont achetés. Dans cet ensemble de données particulier, des fruits sont achetés au total 3 fois, dont deux de ces fois consistant en des achats d'œufs. ${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \ <semantics> <mrow> <mstyle> <mo>{</mo> <mrow> <mi>b</mi> <mi>u</mi> <mi>t</mi> <mi>t</mi> <mi>e</mi> <mi>r</mi> <mo>,</mo> <mi>b</mi> <mi>r</mi> <mi>e</mi> <mi>a</mi> <mi>d</mi> </mrow> <mo>}</mo> <mo>⇒</mo> <mo>{</mo> <mrow> <mi>m</mi> <mi>i</mi> <mi>l</mi> <mi>k</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\frac {1/5}{1/5}}={\frac {0.2}{0.2}}=1.0 <semantics> <mrow> <mstyle> <mrow> <mfrac> <mrow> <mn>1</mn> <mrow> <mo>/</mo> </mrow> <mn>5</mn> </mrow> <mrow> <mn>1</mn> <mrow> <mo>/</mo> </mrow> <mn>5</mn> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <mn>0.2</mn> <mn>0.2</mn> </mfrac> </mrow> <mo>=</mo> <mn>1.0</mn> </mstyle> </mrow> <annotation>{\displaystyle {\frac {1/5}{1/5}}={\frac {0.2}{0.2}}=1.0}</annotation> </semantics> </math><img src=$ ${\displaystyle \{\mathrm {fruit} \}\Rightarrow \{\mathrm {eggs} \ <semantics> <mrow> <mstyle> <mo>{</mo> <mrow> <mi>f</mi> <mi>r</mi> <mi>u</mi> <mi>i</mi> <mi>t</mi> </mrow> <mo>}</mo> <mo>⇒</mo> <mo>{</mo> <mrow> <mi>e</mi> <mi>g</mi> <mi>g</mi> <mi>s</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\mathrm {fruit} \}\Rightarrow \{\mathrm {eggs} \}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\frac {2/5}{3/5}}={\frac {0.4}{0.6}}=0.67 <semantics> <mrow> <mstyle> <mrow> <mfrac> <mrow> <mn>2</mn> <mrow> <mo>/</mo> </mrow> <mn>5</mn> </mrow> <mrow> <mn>3</mn> <mrow> <mo>/</mo> </mrow> <mn>5</mn> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <mn>0.4</mn> <mn>0.6</mn> </mfrac> </mrow> <mo>=</mo> <mn>0.67</mn> </mstyle> </mrow> <annotation>{\displaystyle {\frac {2/5}{3/5}}={\frac {0.4}{0.6}}=0.67}</annotation> </semantics> </math><img src=$

Pour les ensembles de données plus volumineux, un seuil minimum ou un pourcentage de coupure pour la confiance peut être utile pour déterminer les relations entre les éléments. Lorsque cette méthode est appliquée à certaines des données du tableau 2, les informations qui ne répondent pas aux exigences sont supprimées. Le tableau 4 montre des exemples de règles d'association où le seuil minimum de confiance est de 0,5 (50 %). Toutes les données qui n'ont pas un niveau de confiance d'au moins 0,5 sont omises. La génération de seuils permet de renforcer l'association entre les éléments à mesure que les données sont étudiées plus en détail en mettant l'accent sur ceux qui coexistent le plus. Le tableau utilise les informations de confiance du tableau 3 pour implémenter la colonne Support × Confiance, où la relation entre les éléments via leur confiance et leur support, au lieu d'un seul concept, est mise en évidence. Le classement des règles par Support × Confiance multiplie la confiance d'une règle particulière par son support et est souvent mis en œuvre pour une compréhension plus approfondie de la relation entre les éléments.

Dans l’ensemble, l’utilisation de la confiance dans l’exploration de règles d’association est un excellent moyen de faire prendre conscience des relations entre les données. Son principal avantage est de mettre en évidence la relation entre des éléments particuliers les uns par rapport aux autres au sein de l’ensemble, car elle compare les cooccurrences d’éléments à l’occurrence totale de l’antécédent dans la règle spécifique. Cependant, la confiance n’est pas la méthode optimale pour chaque concept dans l’exploration de règles d’association. L’inconvénient de son utilisation est qu’elle n’offre pas de perspectives de différences multiples sur les associations. Contrairement au support, par exemple, la confiance ne fournit pas la perspective des relations entre certains éléments par rapport à l’ensemble de données complet, donc alors que le lait et le pain, par exemple, peuvent apparaître 100 % du temps pour la confiance, elle n’a qu’un support de 0,4 (40 %). C’est pourquoi il est important d’examiner d’autres points de vue, tels que Support × Confiance, au lieu de s’appuyer uniquement sur un seul concept sans cesse pour définir les relations.

Ascenseur

La levée d'une règle est définie comme :

${\displaystyle \mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X) imes \mathrm {supp} (Y) <semantics> <mrow> <mstyle> <mrow> <mi>l</mi> <mi>i</mi> <mi>f</mi> <mi>t</mi> </mrow> <mo>(</mo> <mi>X</mi> <mo>⇒</mo> <mi>Y</mi> <mo>)</mo> <mo>=</mo> <mrow> <mfrac> <mrow> <mrow> <mi>s</mi> <mi>u</mi> <mi>p</mi> <mi>p</mi> </mrow> <mo>(</mo> <mi>X</mi> <mo>∪</mo> <mi>Y</mi> <mo>)</mo> </mrow> <mrow> <mrow> <mi>s</mi> <mi>u</mi> <mi>p</mi> <mi>p</mi> </mrow> <mo>(</mo> <mi>X</mi> <mo>)</mo> <mo>×</mo> <mrow> <mi>s</mi> <mi>u</mi> <mi>p</mi> <mi>p</mi> </mrow> <mo>(</mo> <mi>Y</mi> <mo>)</mo> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X) imes \mathrm {supp} (Y)}}}</annotation> </semantics> </math><img src=$

ou le rapport entre le support observé et celui attendu si X et Y étaient indépendants .

Par exemple, la règle a une portée de . ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \ <semantics> <mrow> <mstyle> <mo>{</mo> <mrow> <mi>m</mi> <mi>i</mi> <mi>l</mi> <mi>k</mi> <mo>,</mo> <mi>b</mi> <mi>r</mi> <mi>e</mi> <mi>a</mi> <mi>d</mi> </mrow> <mo>}</mo> <mo>⇒</mo> <mo>{</mo> <mrow> <mi>b</mi> <mi>u</mi> <mi>t</mi> <mi>t</mi> <mi>e</mi> <mi>r</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\frac {0.2}{0.4 imes 0.4}}=1.25 <semantics> <mrow> <mstyle> <mrow> <mfrac> <mn>0.2</mn> <mrow> <mn>0.4</mn> <mo>×</mo> <mn>0.4</mn> </mrow> </mfrac> </mrow> <mo>=</mo> <mn>1.25</mn> </mstyle> </mrow> <annotation>{\displaystyle {\frac {0.2}{0.4 imes 0.4}}=1.25}</annotation> </semantics> </math><img src=$

Si la règle avait une valeur de 1, cela impliquerait que la probabilité d'occurrence de l'antécédent et celle du conséquent sont indépendantes l'une de l'autre. Lorsque deux événements sont indépendants l'un de l'autre, aucune règle ne peut être établie concernant ces deux événements.

Si l'ascenseur est > 1, cela nous permet de connaître le degré auquel ces deux occurrences dépendent l'une de l'autre et rend ces règles potentiellement utiles pour prédire les conséquences dans les futurs ensembles de données.

Si l'ascenseur est < 1, cela nous permet de savoir que les éléments sont substituables les uns aux autres. Cela signifie que la présence d'un élément a un effet négatif sur la présence d'un autre élément et vice versa.

L'intérêt de la méthode lift est qu'elle prend en compte à la fois le support de la règle et l'ensemble des données globales.

[refaire]

Conviction

La conviction d’une règle est définie comme . ${\displaystyle \mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {supp} (Y)}{1-\mathrm {conf} (X\Rightarrow Y) <semantics> <mrow> <mstyle> <mrow> <mi>c</mi> <mi>o</mi> <mi>n</mi> <mi>v</mi> </mrow> <mo>(</mo> <mi>X</mi> <mo>⇒</mo> <mi>Y</mi> <mo>)</mo> <mo>=</mo> <mrow> <mfrac> <mrow> <mn>1</mn> <mo>−</mo> <mrow> <mi>s</mi> <mi>u</mi> <mi>p</mi> <mi>p</mi> </mrow> <mo>(</mo> <mi>Y</mi> <mo>)</mo> </mrow> <mrow> <mn>1</mn> <mo>−</mo> <mrow> <mi>c</mi> <mi>o</mi> <mi>n</mi> <mi>f</mi> </mrow> <mo>(</mo> <mi>X</mi> <mo>⇒</mo> <mi>Y</mi> <mo>)</mo> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {supp} (Y)}{1-\mathrm {conf} (X\Rightarrow Y)}}}</annotation> </semantics> </math><img src=$

Par exemple, la règle a une valeur de conviction de , et peut être interprétée comme le rapport de la fréquence attendue que X se produise sans Y (c'est-à-dire la fréquence à laquelle la règle fait une prédiction incorrecte) si X et Y étaient indépendants divisée par la fréquence observée de prédictions incorrectes. Dans cet exemple, la valeur de conviction de 1,2 montre que la règle serait incorrecte 20 % plus souvent (1,2 fois plus souvent) si l'association entre X et Y était purement aléatoire. ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \ <semantics> <mrow> <mstyle> <mo>{</mo> <mrow> <mi>m</mi> <mi>i</mi> <mi>l</mi> <mi>k</mi> <mo>,</mo> <mi>b</mi> <mi>r</mi> <mi>e</mi> <mi>a</mi> <mi>d</mi> </mrow> <mo>}</mo> <mo>⇒</mo> <mo>{</mo> <mrow> <mi>b</mi> <mi>u</mi> <mi>t</mi> <mi>t</mi> <mi>e</mi> <mi>r</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\frac {1-0.4}{1-0.5}}=1.2 <semantics> <mrow> <mstyle> <mrow> <mfrac> <mrow> <mn>1</mn> <mo>−</mo> <mn>0.4</mn> </mrow> <mrow> <mn>1</mn> <mo>−</mo> <mn>0.5</mn> </mrow> </mfrac> </mrow> <mo>=</mo> <mn>1.2</mn> </mstyle> </mrow> <annotation>{\displaystyle {\frac {1-0.4}{1-0.5}}=1.2}</annotation> </semantics> </math><img src=$ ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \ <semantics> <mrow> <mstyle> <mo>{</mo> <mrow> <mi>m</mi> <mi>i</mi> <mi>l</mi> <mi>k</mi> <mo>,</mo> <mi>b</mi> <mi>r</mi> <mi>e</mi> <mi>a</mi> <mi>d</mi> </mrow> <mo>}</mo> <mo>⇒</mo> <mo>{</mo> <mrow> <mi>b</mi> <mi>u</mi> <mi>t</mi> <mi>t</mi> <mi>e</mi> <mi>r</mi> </mrow> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}</annotation> </semantics> </math><img src=$

Mesures alternatives de l'intérêt

Outre la confiance, d'autres mesures de l'intérêt des règles ont été proposées. Certaines mesures populaires sont les suivantes :

Confiance totale
La force collective
Effet de levier

Plusieurs autres mesures sont présentées et comparées par Tan et al. et par Hahsler. La recherche de techniques capables de modéliser ce que l'utilisateur a connu (et d'utiliser ces modèles comme mesures d'intérêt) est actuellement une tendance de recherche active sous le nom de « intérêt subjectif ».

Histoire

Le concept de règles d'association a été popularisé notamment grâce à l'article de 1993 d'Agrawal et al., qui a acquis plus de 23 790 citations selon Google Scholar, en avril 2021, et est donc l'un des articles les plus cités dans le domaine de l'exploration de données. Cependant, ce que l'on appelle désormais « règles d'association » est déjà introduit dans l'article de 1966 sur GUHA, une méthode générale d'exploration de données développée par Petr Hájek et al.

Une utilisation précoce (vers 1989) du support et de la confiance minimum pour trouver toutes les règles d'association est le cadre de modélisation basé sur les fonctionnalités, qui a trouvé toutes les règles avec et supérieures aux contraintes définies par l'utilisateur. ${\displaystyle \mathrm {supp} (X) <semantics> <mrow> <mstyle> <mrow> <mi>s</mi> <mi>u</mi> <mi>p</mi> <mi>p</mi> </mrow> <mo>(</mo> <mi>X</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle \mathrm {supp} (X)}</annotation> </semantics> </math><img src=$ ${\displaystyle \mathrm {conf} (X\Rightarrow Y) <semantics> <mrow> <mstyle> <mrow> <mi>c</mi> <mi>o</mi> <mi>n</mi> <mi>f</mi> </mrow> <mo>(</mo> <mi>X</mi> <mo>⇒</mo> <mi>Y</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle \mathrm {conf} (X\Rightarrow Y)}</annotation> </semantics> </math><img src=$

Des associations statistiquement fiables

L'une des limites de l'approche standard de découverte d'associations est qu'en recherchant un grand nombre d'associations possibles pour trouver des collections d'éléments qui semblent être associées, il existe un risque élevé de trouver de nombreuses associations fausses. Il s'agit de collections d'éléments qui coexistent avec une fréquence inattendue dans les données, mais qui ne le font que par hasard. Par exemple, supposons que nous examinions une collection de 10 000 éléments et que nous recherchions des règles contenant deux éléments dans le côté gauche et un élément dans le côté droit. Il existe environ 1 000 000 000 000 de ces règles. Si nous appliquons un test statistique d'indépendance avec un niveau de signification de 0,05, cela signifie qu'il n'y a que 5 % de chances d'accepter une règle s'il n'y a pas d'association. Si nous supposons qu'il n'y a pas d'association, nous devrions néanmoins nous attendre à trouver 50 000 000 000 de règles. La découverte d’associations statistiquement fiable contrôle ce risque, réduisant dans la plupart des cas le risque de trouver des associations parasites à un niveau de signification spécifié par l’utilisateur.

Algorithmes

De nombreux algorithmes permettant de générer des règles d’association ont été proposés.

Certains algorithmes bien connus sont Apriori , Eclat et FP-Growth, mais ils ne font que la moitié du travail, car ce sont des algorithmes d'extraction d'ensembles d'éléments fréquents. Une autre étape doit être effectuée ensuite pour générer des règles à partir d'ensembles d'éléments fréquents trouvés dans une base de données.

Algorithme a priori

Apriori est une méthode proposée par R. Agrawal et R. Srikant en 1994 pour l'exploration d'ensembles d'éléments fréquents et l'apprentissage de règles d'association. Elle procède en identifiant les éléments individuels fréquents dans la base de données et en les étendant à des ensembles d'éléments de plus en plus grands tant que ces ensembles d'éléments apparaissent suffisamment souvent. Le nom de l'algorithme est Apriori car il utilise la connaissance préalable des propriétés des ensembles d'éléments fréquents.

Présentation : Apriori utilise une approche « ascendante », où les sous-ensembles fréquents sont étendus un élément à la fois (une étape connue sous le nom de génération de candidats ), et des groupes de candidats sont testés par rapport aux données. L'algorithme se termine lorsqu'aucune autre extension réussie n'est trouvée. Apriori utilise une recherche en largeur et une structure d'arbre de hachage pour compter efficacement les ensembles d'éléments candidats. Il génère des ensembles d'éléments candidats de longueur à partir d'ensembles d'éléments de longueur . Ensuite, il élague les candidats qui ont un modèle de sous-ensemble peu fréquent. Selon le lemme de fermeture descendante, l'ensemble candidat contient tous les ensembles d'éléments fréquents de longueur. Après cela, il analyse la base de données de transactions pour déterminer les ensembles d'éléments fréquents parmi les candidats.

Exemple : supposons que chaque ligne corresponde à un échantillon de cancer avec une certaine combinaison de mutations étiquetées par un caractère de l'alphabet. Par exemple, une ligne pourrait contenir {a, c}, ce qui signifie qu'elle est affectée par la mutation « a » et la mutation « c ».

Nous allons maintenant générer l'ensemble d'éléments fréquents en comptant le nombre d'occurrences de chaque caractère. Cette opération est également connue sous le nom de recherche des valeurs de support. Ensuite, nous allons élaguer l'ensemble d'éléments en choisissant un seuil de support minimum. Pour cette étape de l'algorithme, nous choisirons 3.

Étant donné que toutes les valeurs de support sont égales ou supérieures à trois, il n'y a pas d'élagage. L'ensemble des éléments fréquents est {a}, {b}, {c} et {d}. Après cela, nous répéterons le processus en comptant les paires de mutations dans l'ensemble d'entrée.

Nous allons maintenant définir notre valeur de support minimale à 4 afin que seuls {a, d} restent après l'élagage. Nous allons maintenant utiliser l'ensemble d'éléments fréquents pour créer des combinaisons de triplets. Nous répéterons ensuite le processus en comptant les occurrences de triplets de mutations dans l'ensemble d'entrée.

Comme nous n'avons qu'un seul élément, le prochain ensemble de combinaisons de quadruplets est vide, donc l'algorithme s'arrêtera.

Avantages et limites :

Apriori a quelques limitations. La génération de candidats peut aboutir à de grands ensembles de candidats. Par exemple, un ensemble de 1 élément fréquent de 10^4 générera un ensemble de 2 éléments candidats de 10^7. L'algorithme doit également analyser fréquemment la base de données, pour être précis n+1 analyses où n est la longueur du motif le plus long. Apriori est plus lent que l'algorithme Eclat. Cependant, Apriori fonctionne bien par rapport à Eclat lorsque l'ensemble de données est volumineux. En effet, dans l'algorithme Eclat, si l'ensemble de données est trop volumineux, les listes de tid deviennent trop grandes pour la mémoire. FP-growth surpasse Apriori et Eclat. Cela est dû au fait que l'algorithme FP-growth n'a pas de génération de candidats ou de test, utilise une structure de données compacte et n'a qu'une seule analyse de base de données.

Algorithme Eclat

Eclat (alt. ECLAT, signifie Equivalence Class Transformation) est un algorithme de rétro-suivi , qui parcourt le graphe en treillis d'éléments fréquents selon une recherche en profondeur (DFS). Alors que la recherche en largeur (BFS) utilisée dans l'algorithme Apriori finira par vérifier chaque sous-ensemble d'un ensemble d'éléments avant de le vérifier, la recherche DFS vérifie des ensembles d'éléments plus grands et peut économiser sur la vérification de la prise en charge de certains de ses sous-ensembles en vertu de la propriété de rapprochement vers le bas. De plus, il utilisera presque certainement moins de mémoire car DFS a une complexité spatiale inférieure à BFS.

Pour illustrer cela, supposons un ensemble d'éléments fréquents {a, b, c}. Un DFS peut vérifier les nœuds du treillis d'éléments fréquents dans l'ordre suivant : {a} → {a, b} → {a, b, c}, auquel cas on sait que {b}, {c}, {a, c}, {b, c} satisfont tous la contrainte de support par la propriété de fermeture vers le bas. Le BFS explorerait chaque sous-ensemble de {a, b, c} avant de le vérifier définitivement. Lorsque la taille d'un ensemble d'éléments augmente, le nombre de ses sous-ensembles subit une explosion combinatoire .

Il convient à la fois à l'exécution séquentielle et parallèle avec des propriétés d'amélioration de la localité.

Algorithme de croissance FP

FP signifie « modèle fréquent ».

Dans la première étape, l'algorithme compte les occurrences d'éléments (paires attribut-valeur) dans l'ensemble de données des transactions et stocke ces comptages dans une « table d'en-tête ». Dans la deuxième étape, il construit la structure de l'arbre FP en insérant les transactions dans un trie .

Les éléments de chaque transaction doivent être triés par ordre décroissant de leur fréquence dans l'ensemble de données avant d'être insérés afin que l'arbre puisse être traité rapidement. Les éléments de chaque transaction qui ne répondent pas aux exigences de support minimum sont rejetés. Si de nombreuses transactions partagent les éléments les plus fréquents, l'arbre FP fournit une compression élevée à proximité de la racine de l'arbre.

Le traitement récursif de cette version compressée de l'ensemble de données principal génère directement des ensembles d'éléments fréquents, au lieu de générer des éléments candidats et de les tester par rapport à l'ensemble de la base de données (comme dans l'algorithme a priori).

La croissance commence à partir du bas du tableau d'en-tête, c'est-à-dire l'élément avec le plus petit support en trouvant toutes les transactions triées qui se terminent par cet élément. Appelez cet élément . ${\displaystyle I <semantics> <mrow> <mstyle> <mi>I</mi> </mstyle> </mrow> <annotation>{\displaystyle I}</annotation> </semantics> </math><img src=$

Un nouvel arbre conditionnel est créé, qui est l'arbre FP d'origine projeté sur . Les supports de tous les nœuds de l'arbre projeté sont recomptés, chaque nœud obtenant la somme de ses nombres d'enfants. Les nœuds (et donc les sous-arbres) qui ne répondent pas au support minimum sont élagués. La croissance récursive se termine lorsqu'aucun élément individuel conditionnel à ne répond au seuil de support minimum. Les chemins résultants de la racine à seront des ensembles d'éléments fréquents. Après cette étape, le traitement continue avec l'élément d'en-tête le moins pris en charge de l'arbre FP d'origine. ${\displaystyle I <semantics> <mrow> <mstyle> <mi>I</mi> </mstyle> </mrow> <annotation>{\displaystyle I}</annotation> </semantics> </math><img src=$ ${\displaystyle I <semantics> <mrow> <mstyle> <mi>I</mi> </mstyle> </mrow> <annotation>{\displaystyle I}</annotation> </semantics> </math><img src=$ ${\displaystyle I <semantics> <mrow> <mstyle> <mi>I</mi> </mstyle> </mrow> <annotation>{\displaystyle I}</annotation> </semantics> </math><img src=$

Une fois le processus récursif terminé, tous les ensembles d’éléments fréquents auront été trouvés et la création de la règle d’association commencera.

Autres

ASSOCIATION

La procédure ASSOC est une méthode GUHA qui extrait des règles d'association généralisées à l'aide d'opérations de chaînes de bits rapides . Les règles d'association extraites par cette méthode sont plus générales que celles générées par apriori, par exemple les « éléments » peuvent être connectés à la fois par des conjonctions et des disjonctions et la relation entre l'antécédent et le conséquent de la règle ne se limite pas à la définition d'un support et d'une confiance minimum comme dans apriori : une combinaison arbitraire de mesures d'intérêt supportées peut être utilisée.

Recherche OPUS

OPUS est un algorithme efficace pour la découverte de règles qui, contrairement à la plupart des alternatives, ne nécessite pas de contraintes monotones ou anti-monotones telles qu'un support minimum. Initialement utilisé pour trouver des règles pour un conséquent fixe il a ensuite été étendu pour trouver des règles avec n'importe quel élément comme conséquent. La recherche OPUS est la technologie de base du système de découverte d'association populaire Magnum Opus.

Traditions

L'histoire de la bière et des couches est une histoire célèbre sur l'exploitation des règles d'association. Une enquête sur le comportement des clients des supermarchés a révélé que les clients (probablement des jeunes hommes) qui achètent des couches ont tendance à acheter également de la bière. Cette anecdote est devenue populaire comme exemple de la façon dont des règles d'association inattendues peuvent être trouvées à partir de données quotidiennes. Les opinions divergent quant à la part de vérité de cette histoire. Daniel Powers dit :

En 1992, Thomas Blischok, directeur d'un groupe de conseil en vente au détail chez Teradata , et son équipe ont préparé une analyse de 1,2 million de paniers de 25 pharmacies Osco. Des requêtes de base de données ont été développées pour identifier les affinités. L'analyse « a révélé qu'entre 17h00 et 19h00, les consommateurs achetaient de la bière et des couches ». Les dirigeants d'Osco n'ont PAS exploité la relation entre la bière et les couches en rapprochant les produits sur les étagères.

Autres types d'exploration de règles d'association

Règles d'association multi-relation (MRAR) : Il s'agit de règles d'association dans lesquelles chaque élément peut avoir plusieurs relations. Ces relations indiquent des relations indirectes entre les entités. Considérons le MRAR suivant où le premier élément se compose de trois relations vivre dans , à proximité et humide : « Ceux qui vivent dans un endroit qui est proche d' une ville avec un type de climat humide et qui ont également moins de 20 ans, leur état de santé est bon ». De telles règles d'association peuvent être extraites de données RDBMS ou de données du Web sémantique. ${\displaystyle \implies <semantics> <mrow> <mstyle> <mspace></mspace> <mo>⟹</mo> <mspace></mspace> </mstyle> </mrow> <annotation>{\displaystyle \implies }</annotation> </semantics> </math><img src=$

L'apprentissage par ensemble contrasté est une forme d'apprentissage associatif. Les apprenants utilisant des ensembles contrastés utilisent des règles qui diffèrent de manière significative dans leur distribution entre les sous-ensembles.

L'apprentissage pondéré des classes est une autre forme d'apprentissage associatif dans laquelle des pondérations peuvent être attribuées aux classes pour mettre l'accent sur un problème particulier qui préoccupe le consommateur des résultats de l'exploration de données.

La découverte de modèles d'ordre élevé facilite la capture de modèles d'ordre élevé (polythétiques) ou d'associations d'événements intrinsèques à des données complexes du monde réel.

La découverte de modèles K-optimaux offre une alternative à l’approche standard de l’apprentissage des règles d’association qui exige que chaque modèle apparaisse fréquemment dans les données.

L'exploration d'ensembles d'éléments fréquents approximatifs est une version assouplie de l'exploration d'ensembles d'éléments fréquents qui permet à certains éléments de certaines lignes d'être égaux à 0.

Taxonomie hiérarchique des règles d'association généralisées (hiérarchie des concepts)

Règles d'association quantitatives données catégorielles et quantitatives

Règles d'association de données d'intervalle , par exemple partitionner l'âge en tranches de 5 ans

L'exploration de modèles séquentiels découvre des sous-séquences communes à plus de séquences minsup (seuil de support minimum) dans une base de données de séquences, où minsup est défini par l'utilisateur. Une séquence est une liste ordonnée de transactions.

Le clustering de sous-espaces , un type spécifique de clustering de données de grande dimension , est également basé dans de nombreuses variantes sur la propriété de fermeture vers le bas pour des modèles de clustering spécifiques.

Warmr , fourni dans le cadre de la suite d'exploration de données ACE, permet l'apprentissage de règles d'association pour les règles relationnelles de premier ordre.