Skip to content
Torna ai risultati

Regole di associazione semi-supervisionate

Introdotto da
Liu, B.; Hsu, W.; Ma, Y. (and subsequent researchers)
Anno
2003–2010s
Tipo
Pattern mining with partial supervision
Famiglia
Machine learning

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

L'estrazione di regole di associazione semi-supervisionate estende l'apprendimento classico delle regole di associazione incorporando una piccola quantità di dati etichettati accanto a un dataset più ampio non etichettato.

Utilizza informazioni di classe note o vincoli forniti dall'utente per guidare la scoperta di regole che siano sia statisticamente frequenti che semanticamente significative, colmando il divario tra l'estrazione di pattern non supervisionata e la supervisione leggera.

L’intuizione alla base del metodo

L'estrazione standard di regole di associazione trova tutti i pattern di co-occorrenza frequenti senza alcun senso di ciò che è importante. Le regole di associazione semi-supervisionate cambiano questo permettendo a un piccolo insieme di esempi etichettati o vincoli di dominio di guidare la ricerca: le regole che si allineano con la struttura di classe nota sono preferite rispetto a quelle statisticamente frequenti ma prive di significato. Pensala come dare all'algoritmo una manciata di suggerimenti su ciò che interessa all'analista, in modo che smetta di far emergere pattern banali o già noti e metta invece in evidenza relazioni realmente nuove e attuabili. Il risultato combina l'ampiezza dell'estrazione di pattern non supervisionata con la giusta guida per mantenere i risultati pertinenti.

Storia

L'estrazione di regole di associazione è stata formalizzata da Agrawal, Imielinski e Swami nel 1993 con l'introduzione dell'algoritmo Apriori, mirato alla scoperta non supervisionata di itemset frequenti nei dati del carrello della spesa. L'integrazione di etichette di classe e vincoli nell'estrazione di regole di associazione ha guadagnato slancio nei primi anni 2000, in particolare attraverso i framework CMAR e CBA di Liu e colleghi, che trattavano le etichette di classe come conseguenti delle regole. Le estensioni semi-supervisionate sono emerse quando i ricercatori hanno riconosciuto che una supervisione parziale poteva ridurre l'esplosione combinatoria degli itemset candidati mantenendo il contributo statistico dei dati non etichettati. L'approccio appare ora in bioinformatica, data mining educativo e sistemi di raccomandazione.

Quando usarlo

Utilizzare l'estrazione di regole di associazione semi-supervisionate quando si dispone di un ampio dataset transazionale o tabellare, di cui solo una frazione contiene etichette di classe o annotazioni di dominio, e si necessita di scoprire pattern di co-occorrenza che siano realmente pertinenti a un concetto target piuttosto che semplicemente frequenti. È ben adatta all'analisi del carrello della spesa con alcuni risultati di acquisto noti, all'estrazione di dati medici in cui solo un sottoinsieme di casi ha diagnosi confermate e alla categorizzazione di testi in cui i documenti etichettati sono scarsi. Evitarla quando la porzione etichettata è trascurabilmente piccola (meno di qualche decina di istanze etichettate), quando la supervisione completa è fattibile, o quando i requisiti di interpretabilità richiedono un modello più semplice come la regressione logistica o un albero decisionale.

Limiti e considerazioni

  • La qualità delle regole dipende fortemente dalla qualità e dalla rappresentatività del set di semi etichettati; un sottoinsieme etichettato distorto propaga la distorsione nelle regole scoperte.
  • La combinazione di soglie di supporto, confidenza e vincoli crea un ampio spazio di iperparametri difficile da ottimizzare senza dati di validazione etichettati.
  • Il costo computazionale scala con il numero di itemset candidati; dataset con spazi di item ad altissima dimensionalità richiedono strategie di potatura aggressive.
  • I cicli di auto-addestramento possono amplificare errori precoci se le pseudo-etichette iniziali sono rumorose, portando a una deriva delle regole nel corso delle iterazioni.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Sfrutta abbondanti dati non etichettati per trovare pattern che sarebbero statisticamente invisibili con soli dati etichettati.
  • I vincoli derivati dalle etichette eliminano le regole irrilevanti, producendo un set di regole più piccolo e più attuabile rispetto all'estrazione puramente non supervisionata.
  • Le regole rimangono istruzioni IF-THEN leggibili dall'uomo, preservando il vantaggio di interpretabilità dell'apprendimento classico delle regole di associazione.
  • Il perfezionamento tramite auto-addestramento può migliorare iterativamente sia la qualità delle regole che la copertura delle pseudo-etichette senza costi aggiuntivi di etichettatura.
  • Flessibile: i vincoli possono codificare la conoscenza del dominio oltre le semplici etichette di classe (ad es. ordine temporale, gerarchie di articoli).

Applicazioni

  • Estrazione di dati medici in cui solo un sottoinsieme di cartelle cliniche contiene diagnosi confermate.
  • Analisi del carrello della spesa guidata da un sottoinsieme noto di risultati di acquisto di alto valore.
  • Data mining educativo per scoprire pattern di comportamento di apprendimento associati a un piccolo insieme di risultati di performance degli studenti etichettati.
  • Text mining e categorizzazione di documenti con corpora etichettati scarsi.
  • Rilevamento di intrusioni in cui solo una frazione di eventi di rete sono attacchi confermati.
  • Sistemi di raccomandazione che utilizzano valutazioni sparse degli utenti per vincolare le regole di co-occorrenza degli articoli.

Come funziona

Come funziona

1

Il dataset è diviso in una piccola porzione etichettata (con etichette di classe note o vincoli specificati dall'utente) e una porzione più ampia non etichettata. Gli esempi etichettati servono come semi o ancore che definiscono lo spazio del concetto target, mentre le transazioni non etichettate forniscono la massa statistica necessaria per calcolare conteggi di supporto affidabili.

2

L'enumerazione degli itemset frequenti viene eseguita sia sui dati etichettati che non etichettati utilizzando algoritmi classici come Apriori o FP-Growth, calcolando il supporto come la frazione di transazioni contenenti un dato itemset. Solo gli itemset che superano la soglia minima di supporto vengono conservati come candidati per la generazione di regole.

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

Vincoli derivati dalle etichette o specificati dall'utente vengono applicati per potare lo spazio dei candidati. I vincoli possono assumere la forma di must-link (due elementi dovrebbero co-occorrere nel conseguente con una classe target), cannot-link (certe combinazioni sono escluse) o filtri di etichette di classe che limitano quali regole coinvolgono un risultato target. Questo riduce drasticamente il numero di regole spurie o ridondanti.

4

Regole valide X implica Y vengono generate dagli itemset frequenti sopravvissuti, filtrate da una soglia minima di confidenza. La confidenza misura la probabilità condizionale che Y appaia dato X. In un contesto semi-supervisionato, le regole il cui conseguente si allinea con una classe etichettata o un vincolo sono prioritizzate o pesate maggiormente.

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

Le regole scoperte possono essere utilizzate iterativamente per assegnare pseudo-etichette a transazioni precedentemente non etichettate, che vengono poi reintrodotte nei successivi cicli di estrazione. Questo ciclo di auto-addestramento arricchisce gradualmente il pool etichettato e affina il set di regole, convergendo quando non vengono trovate nuove regole ad alta confidenza o viene raggiunto un limite di iterazione predefinito.

Errori comuni

  • Impostare il supporto minimo troppo basso senza vincoli, inondando il risultato con regole banalmente frequenti ma poco informative.
  • Ignorare lo squilibrio delle classi nel set di semi etichettati, che fa sì che il filtro dei vincoli sovra-rappresenti la classe maggioritaria nelle regole scoperte.
  • Considerare la confidenza come unica misura di interesse e trascurare regole con alto lift o convinzione che sono più utili dal punto di vista pratico.
  • Saltare una valutazione separata della qualità predittiva delle regole e accettare le regole estratte così come sono, senza validazione su dati non visti.
  • Confondere associazione (co-occorrenza) con causalità nella presentazione dei risultati.

Domande frequenti

In che modo questo si differenzia dall'estrazione standard di regole di associazione?

L'estrazione standard di regole di associazione è completamente non supervisionata: trova tutti i pattern di co-occorrenza al di sopra di una soglia di supporto e confidenza senza alcun concetto di classe target. Le regole di associazione semi-supervisionate incorporano informazioni parziali sulle etichette o vincoli di dominio per filtrare e prioritizzare le regole pertinenti a uno specifico risultato, producendo un set di risultati più piccolo e più attuabile.

Quanti dati etichettati sono necessari?

Anche un piccolo set etichettato può fornire vincoli utili, ma la qualità dei semi è più importante della quantità. In pratica, avere almeno qualche decina di esempi etichettati per classe è consigliabile per evitare vincoli gravemente distorti. Se le etichette sono estremamente sparse, i risultati dovrebbero essere validati attentamente su un sottoinsieme etichettato separato.

Quali soglie dovrei impostare per supporto e confidenza?

Non esiste una risposta universale: le soglie dipendono dalla dimensione del dataset, dal dominio e da quante regole è possibile valutare realisticamente. Iniziare con soglie moderate (ad es. supporto 0.05–0.10, confidenza 0.60–0.80), esaminare il numero di regole risultanti e aggiustare. Quando i vincoli sono attivi, si possono spesso permettere soglie di supporto leggermente inferiori perché le regole irrilevanti vengono filtrate dalle condizioni delle etichette.

Questo metodo può gestire caratteristiche continue o numeriche?

L'estrazione di regole di associazione opera nativamente su elementi discreti. Le caratteristiche continue devono essere discretizzate in intervalli prima dell'estrazione. La scelta della strategia di discretizzazione influisce su quali itemset diventano frequenti, quindi vale la pena sperimentare con la discretizzazione a larghezza uguale, frequenza uguale e guidata dal dominio e verificare quanto sono sensibili i risultati alla scelta.

Come valuto la qualità delle regole scoperte?

Oltre a supporto e confidenza, valutare le regole utilizzando lift (valori superiori a 1 indicano co-occorrenza genuina oltre il caso), convinzione (conviction) e leverage. Se le regole vengono utilizzate per la predizione, misurare accuratezza di classificazione, F1 o AUC su un set etichettato separato. Le misure di interesse da sole non sono sufficienti per valutare l'utilità pratica.

Metodi correlati

Fonti

  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.

    Apri il riferimento della pubblicazione
    Copiato.
  2. Association rule learning. Wikipedia.

    Apri il riferimento della pubblicazione
    Copiato.