Come funziona l’algoritmo RQFP per scoprire pattern nascosti nei dati?

Immagina di voler capire quali prodotti si comprano insieme in un supermercato o quali corsi universitari sono spesso seguiti dallo stesso studente. In ambito data mining, questo si chiama "frequent pattern mining". Tradizionalmente si usano algoritmi come Apriori o FP‑Growth, ma hanno due problemi: generano tantissime combinazioni candidate e consumano molta memoria, soprattutto con tabelle molto grandi.

Il nuovo algoritmo Recursive Queried Frequent Patterns (RQFP) propone una soluzione diversa, basata su query ricorsive SQL. In pratica, RQFP crea una tabella di mining relazionale e, usando le Common Table Expressions (CTE) ricorsive, costruisce gli insiemi di item più frequenti senza dover elencare preventivamente tutte le combinazioni possibili.

Il team ha implementato RQFP su Microsoft SQL Server e ha costruito una piccola interfaccia web in C#. I test su un dataset accademico mostrano che RQFP trova gli stessi pattern di Apriori e FP‑Growth, ma con un consumo di RAM notevolmente inferiore e con risultati più facili da interpretare. Inoltre, grazie al fatto che l’algoritmo gira direttamente sul database, è più semplice integrarlo in sistemi esistenti.

Le sperimentazioni future puntano a valutare RQFP su dati sanitari e di retail, dove la quantità di informazioni è enorme. Anche se per ora è una versione educativa, il metodo dimostra che il mining dei pattern può diventare più scalabile e “database‑native”.

Il cuore dell’algoritmo RQFP è l’utilizzo delle Common Table Expressions (CTE) ricorsive, una funzionalità SQL introdotta con SQL:1999 e supportata da tutti i principali DBMS moderni. Una CTE ricorsiva permette di definire una query di base (seed) e una regola di ricorsione che, iterativamente, aggiunge nuovi record finché non si raggiunge una condizione di arresto.

Nel contesto del frequent pattern mining, la query di seed seleziona tutti gli item singoli con supporto superiore alla soglia minima. La regola di ricorsione combina gli item già trovati con quelli successivi, calcolando il supporto dell’unione e mantenendo solo le combinazioni che superano la soglia. Questo approccio elimina la fase di generazione esplicita dei candidati tipica di Apriori, riducendo drasticamente il numero di tuple temporanee da memorizzare.

Dal punto di vista della complessità computazionale, RQFP mantiene una crescita esponenziale legata al numero di item frequenti, ma la costante è molto più bassa rispetto a Apriori perché la memoria è gestita dal motore di query del DBMS, che ottimizza l’uso di indici e di buffer. FP‑Growth, invece, costruisce un albero di prefissi (FP‑tree) che richiede una scansione completa del dataset e una struttura in‑memory complessa; RQFP evita questa struttura, sfruttando la capacità di esecuzione parallela del server SQL.

Un altro vantaggio è la trasparenza dei risultati: ogni livello della ricorsione corrisponde a un livello di lunghezza dell’itemset, rendendo più semplice tracciare il percorso di generazione dei pattern. Inoltre, poiché le operazioni avvengono interamente in SQL, è possibile sfruttare le funzionalità di sicurezza, logging e gestione delle transazioni già presenti nel database, facilitando l’integrazione in ambienti enterprise.

Le limitazioni attuali includono la dipendenza dalle capacità di ottimizzazione del DBMS e la necessità di una buona definizione di indici su colonne di item e supporto. In scenari con milioni di transazioni e migliaia di item, la profondità della ricorsione può diventare un collo di bottiglia; in questi casi è consigliabile combinare RQFP con tecniche di partizionamento dei dati o con approcci ibridi che pre‑filtrano gli item più promettenti.

In sintesi, RQFP dimostra che il mining dei pattern frequenti può essere realizzato in modo nativo all’interno del database, riducendo la dipendenza da strutture dati esterne e migliorando l’efficienza di memoria, pur mantenendo una precisione comparabile ai metodi tradizionali.