Skip to content
Retour aux résultats

Règles d'association semi-supervisées

Introduite par
Liu, B.; Hsu, W.; Ma, Y. (and subsequent researchers)
Année
2003–2010s
Type
Pattern mining with partial supervision
Famille
Machine learning

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

L'extraction de règles d'association semi-supervisées étend l'apprentissage classique des règles d'association en intégrant une petite quantité de données étiquetées à un ensemble de données non étiquetées plus vaste.

Elle utilise des informations de classe connues ou des contraintes fournies par l'utilisateur pour guider la découverte de règles à la fois statistiquement fréquentes et sémantiquement significatives, faisant le pont entre l'exploration de motifs non supervisée et une supervision légère.

L’intuition derrière la méthode

L'extraction standard de règles d'association trouve tous les motifs de cooccurrence fréquents sans aucune notion de pertinence. Les règles d'association semi-supervisées modifient cela en permettant à un petit ensemble d'exemples étiquetés ou de contraintes de domaine d'orienter la recherche : les règles qui s'alignent sur une structure de classe connue sont préférées aux règles statistiquement fréquentes mais dénuées de sens. Il s'agit de donner à l'algorithme quelques indices sur ce qui intéresse l'analyste, afin qu'il cesse de faire remonter des motifs triviaux ou déjà connus et mette plutôt en évidence des relations véritablement nouvelles et exploitables. Le résultat combine l'étendue de la découverte de motifs non supervisée avec juste assez de guidage pour maintenir la pertinence des résultats.

Histoire

L'extraction de règles d'association a été formalisée par Agrawal, Imielinski et Swami en 1993 avec l'introduction de l'algorithme Apriori, ciblant la découverte non supervisée d'itemsets fréquents dans les données de paniers d'achat. L'intégration des étiquettes de classe et des contraintes dans l'extraction de règles d'association a pris de l'ampleur au début des années 2000, notamment à travers les cadres CMAR et CBA de Liu et ses collègues, qui traitaient les étiquettes de classe comme des conséquents de règles. Les extensions semi-supervisées sont apparues lorsque les chercheurs ont reconnu qu'une supervision partielle pouvait réduire l'explosion combinatoire des règles candidates tout en maintenant la contribution statistique des données non étiquetées. L'approche est maintenant utilisée en bioinformatique, en exploration de données éducatives et dans les systèmes de recommandation.

Quand l’utiliser

Utilisez l'extraction de règles d'association semi-supervisées lorsque vous disposez d'un grand ensemble de données transactionnelles ou tabulaires, dont seule une fraction contient des étiquettes de classe ou des annotations de domaine, et que vous devez découvrir des motifs de cooccurrence qui sont véritablement pertinents pour un concept cible plutôt que simplement fréquents. Elle est bien adaptée à l'analyse de paniers d'achat avec certains résultats d'achat connus, à l'exploration de dossiers médicaux où seul un sous-ensemble de cas a des diagnostics confirmés, et à la catégorisation de texte où les documents étiquetés sont rares. Évitez-la lorsque la partie étiquetée est négligeable (moins de quelques dizaines d'instances étiquetées), lorsque la supervision complète est réalisable, ou lorsque les exigences d'interprétabilité nécessitent un modèle plus simple tel que la régression logistique ou un arbre de décision.

Limites et points d’attention

  • La qualité des règles dépend fortement de la qualité et de la représentativité de l'ensemble de germes étiquetés ; un sous-ensemble étiqueté biaisé propage le biais dans les règles découvertes.
  • La combinaison des seuils de support, de confiance et de contrainte crée un vaste espace d'hyperparamètres difficile à ajuster sans données de validation étiquetées.
  • Le coût de calcul évolue avec le nombre d'itemsets candidats ; les ensembles de données avec des espaces d'éléments de très haute dimension nécessitent des stratégies d'élagage agressives.
  • Les boucles d'auto-apprentissage peuvent amplifier les erreurs initiales si les pseudo-étiquettes initiales sont bruitées, entraînant une dérive des règles au fil des itérations.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Exploite l'abondance de données non étiquetées pour trouver des motifs qui seraient statistiquement invisibles avec les seules données étiquetées.
  • Les contraintes dérivées des étiquettes élaguent les règles non pertinentes, produisant un ensemble de règles plus petit et plus exploitable que l'extraction purement non supervisée.
  • Les règles restent des énoncés SI-ALORS lisibles par l'homme, préservant l'avantage d'interprétabilité de l'apprentissage classique des règles d'association.
  • Le raffinement par auto-apprentissage peut améliorer itérativement la qualité des règles et la couverture des pseudo-étiquettes sans coût d'étiquetage supplémentaire.
  • Flexible : les contraintes peuvent encoder des connaissances du domaine au-delà des simples étiquettes de classe (par exemple, ordre temporel, hiérarchies d'éléments).

Applications

  • Exploration de dossiers médicaux où seul un sous-ensemble de dossiers patients contient des diagnostics confirmés.
  • Analyse de paniers d'achat guidée par un sous-ensemble connu de résultats d'achat de grande valeur.
  • Exploration de données éducatives pour découvrir des motifs de comportement d'apprentissage associés à un petit ensemble de résultats de performance étudiante étiquetés.
  • Exploration de texte et catégorisation de documents avec des corpus étiquetés rares.
  • Détection d'intrusion où seule une fraction des événements réseau sont des attaques confirmées.
  • Systèmes de recommandation qui utilisent des évaluations d'utilisateurs éparses pour contraindre les règles de cooccurrence d'éléments.

Comment ça marche

Comment ça marche

1

L'ensemble de données est divisé en une petite partie étiquetée (avec des étiquettes de classe connues ou des contraintes spécifiées par l'utilisateur) et une partie non étiquetée plus grande. Les exemples étiquetés servent de germes ou d'ancres qui définissent l'espace conceptuel cible, tandis que les transactions non étiquetées fournissent la masse statistique nécessaire pour calculer des comptes de support fiables.

2

L'énumération des itemsets fréquents s'effectue sur les données étiquetées et non étiquetées à l'aide d'algorithmes classiques tels qu'Apriori ou FP-Growth, en calculant le support comme la fraction des transactions contenant un itemset donné. Seuls les itemsets dépassant le seuil de support minimum sont conservés comme candidats pour la génération de règles.

Formule
\text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \text{min\_sup}
3

Des contraintes dérivées des étiquettes ou spécifiées par l'utilisateur sont appliquées pour élaguer l'espace des candidats. Les contraintes peuvent prendre la forme de must-link (deux éléments doivent co-apparaître dans le conséquent avec une classe cible), cannot-link (certaines combinaisons sont exclues), ou de filtres d'étiquettes de classe qui restreignent les règles impliquant un résultat cible. Cela réduit considérablement le nombre de règles fallacieuses ou redondantes.

4

Des règles valides X implique Y sont générées à partir des itemsets fréquents survivants, filtrées par un seuil de confiance minimum. La confiance mesure la probabilité conditionnelle que Y apparaisse étant donné X. Dans un contexte semi-supervisé, les règles dont le conséquent s'aligne sur une classe étiquetée ou une contrainte sont priorisées ou pondérées plus fortement.

Formule
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}
5

Les règles découvertes peuvent être utilisées de manière itérative pour attribuer des pseudo-étiquettes à des transactions précédemment non étiquetées, qui sont ensuite réinjectées dans les cycles d'extraction ultérieurs. Cette boucle d'auto-apprentissage enrichit progressivement le pool étiqueté et affine l'ensemble de règles, convergeant lorsqu'aucune nouvelle règle de haute confiance n'est trouvée ou qu'une limite d'itération prédéfinie est atteinte.

Pièges courants

  • Définir un support minimum trop bas sans contraintes, inondant le résultat de règles trivialement fréquentes mais non informatives.
  • Ignorer le déséquilibre des classes dans l'ensemble de germes étiquetés, ce qui entraîne une surreprésentation de la classe majoritaire par le filtre de contraintes dans les règles découvertes.
  • Traiter la confiance comme la seule mesure d'intérêt et manquer des règles avec un lift ou une conviction élevés qui sont plus utiles en pratique.
  • Omettre une évaluation sur un ensemble de test de la qualité prédictive des règles et accepter les règles extraites au pied de la lettre sans validation sur des données non vues.
  • Confondre l'association (cooccurrence) avec la causalité lors de la présentation des résultats.

Questions fréquentes

En quoi cela diffère-t-il de l'extraction de règles d'association standard ?

L'extraction de règles d'association standard est entièrement non supervisée : elle trouve tous les motifs de cooccurrence au-dessus d'un seuil de support et de confiance sans concept de classe cible. Les règles d'association semi-supervisées intègrent des informations d'étiquettes partielles ou des contraintes de domaine pour filtrer et prioriser les règles pertinentes pour un résultat spécifique, produisant un ensemble de résultats plus petit et plus exploitable.

Quelle quantité de données étiquetées est nécessaire ?

Même un petit ensemble étiqueté peut fournir des contraintes utiles, mais la qualité des germes compte plus que la quantité. En pratique, il est conseillé d'avoir au moins quelques dizaines d'exemples étiquetés par classe pour éviter des contraintes fortement biaisées. Si les étiquettes sont extrêmement rares, les résultats doivent être validés soigneusement sur un sous-ensemble étiqueté mis de côté.

Quels seuils dois-je définir pour le support et la confiance ?

Il n'y a pas de réponse universelle : les seuils dépendent de la taille de l'ensemble de données, du domaine et du nombre de règles que vous pouvez évaluer de manière réaliste. Commencez par des seuils modérés (par exemple, support 0,05-0,10, confiance 0,60-0,80), examinez le nombre de règles résultantes et ajustez. Lorsque les contraintes sont actives, vous pouvez souvent vous permettre des seuils de support légèrement inférieurs car les règles non pertinentes sont filtrées par les conditions d'étiquette.

Cette méthode peut-elle gérer des caractéristiques continues ou numériques ?

L'extraction de règles d'association opère nativement sur des éléments discrets. Les caractéristiques continues doivent être discrétisées en intervalles avant l'extraction. Le choix de la stratégie de discrétisation affecte les itemsets qui deviennent fréquents, il est donc utile d'expérimenter avec des discrétisations de largeur égale, de fréquence égale et basées sur le domaine, et de vérifier la sensibilité des résultats à ce choix.

Comment évaluer la qualité des règles découvertes ?

Au-delà du support et de la confiance, évaluez les règles en utilisant le lift (les valeurs supérieures à 1 indiquent une cooccurrence réelle au-delà du hasard), la conviction et le levier. Si les règles sont utilisées pour la prédiction, mesurez la précision de la classification, le F1 ou l'AUC sur un ensemble étiqueté mis de côté. Les mesures d'intérêt seules ne suffisent pas pour évaluer l'utilité pratique.

Méthodes associées

Sources

  1. Liu, B., Hsu, W., & Ma, Y. (2003). Integrating Classification and Association Rule Mining. In Proceedings of the 4th IEEE International Conference on Data Mining (ICDM), pp. 339–346.

    Ouvrir la référence de la publication
    Copié.
  2. Association rule learning. Wikipedia.

    Ouvrir la référence de la publication
    Copié.