Riferimento tecnico per l'algoritmo Microsoft Clustering

  • Articolo

Si applica a: SQL Server 2019 e versioni precedenti di Analysis Services Azure Analysis Services Fabric/Power BI Premium

Importante

Il data mining è stato deprecato in SQL Server 2017 Analysis Services e ora è stato interrotto in SQL Server 2022 Analysis Services. La documentazione non viene aggiornata per le funzionalità deprecate e non più disponibili. Per altre informazioni, vedere Compatibilità con le versioni precedenti di Analysis Services.

In questa sezione viene illustrata l'implementazione dell'algoritmo Microsoft Clustering, inclusi i parametri che è possibile usare per controllare il comportamento dei modelli di clustering. Vengono inoltre fornite istruzioni su come migliorare le prestazioni durante la creazione e l'elaborazione di modelli di clustering.

Per ulteriori informazioni sull'utilizzo dei modelli di clustering, vedere gli argomenti seguenti:

Implementazione dell'algoritmo Microsoft Clustering

L'algoritmo Microsoft Clustering fornisce due metodi per la creazione di cluster e l'assegnazione di punti dati ai cluster. Il primo, l'algoritmo K-means , è un metodo di tipo hard clustering, ovvero un punto dati può appartenere a un unico cluster e viene calcolata una singola probabilità per l'appartenenza di ogni punto dati a tale cluster. Il secondo, Expectation Maximization (EM), è un metodo di tipo soft clustering , ovvero un punto dati appartiene sempre a più cluster e viene calcolata una probabilità per ogni combinazione di punto dati e cluster.

È possibile scegliere l'algoritmo da usare impostando il parametro CLUSTERING_METHOD . Il metodo predefinito per il clustering è EM scalabile.

Clustering EM

Nel clustering EM l'algoritmo perfeziona in modo iterativo un modello di cluster iniziale per il fit dei dati e determina la probabilità che un punto dati esista in un cluster. L'algoritmo termina il processo quando si ottiene il fit del modello probabilistico ai dati. La funzione utilizzata per determinare il fit è la probabilità in forma logaritmica dei dati, dato il modello.

Se durante il processo vengono generati cluster vuoti o se l'appartenenza di uno o più cluster è minore di una data soglia, i cluster con popolazioni basse vengono reinizializzati su nuovi punti e l'algoritmo EM viene rieseguito.

I risultati del metodo di clustering EM sono probabilistici, ovvero ogni punto dati appartiene a tutti i cluster, ma ogni assegnazione di un punto dati a un cluster presenta una probabilità diversa. Poiché il metodo consente la sovrapposizione dei cluster, la somma degli elementi di tutti i cluster può essere maggiore del totale degli elementi del set di training. Nei risultati del modello di data mining i punteggi che indicano il supporto vengono adattati per tenere conto di questa situazione.

L'algoritmo EM è l'algoritmo predefinito utilizzato nei modelli di clustering Microsoft. Viene utilizzato come predefinito perché offre più vantaggi rispetto al clustering K-means:

  • Richiede al massimo un'analisi del database.

  • Funziona anche se la quantità di memoria RAM è limitata.

  • Ha la possibilità di utilizzare un cursore forward-only.

  • Offre prestazioni più elevate rispetto agli approcci di campionamento.

L'implementazione Microsoft prevede due opzioni: EM scalabile e non scalabile. Per impostazione predefinita, nell'algoritmo EM scalabile vengono utilizzati i primi 50.000 record per inizializzare l'analisi iniziale. Se l'operazione riesce, il modello utilizza solo questi dati. Se non è possibile ottenere il fit del modello utilizzando 50.000 record, vengono letti altri 50.000 record. Nell'algoritmo EM non scalabile viene letto l'intero set di dati, indipendentemente dalla dimensione. Con questo metodo è possibile creare cluster più accurati, ma i requisiti di memoria possono essere significativi. Poiché EM scalabile opera su un buffer locale, le iterazioni nei dati sono molto più veloci e l'algoritmo utilizza la memoria cache della CPU in modo molto più efficace rispetto a EM non scalabile. Inoltre, EM scalabile è tre volte più veloce di EM non scalabile, anche se tutti i dati possono rientrare nella memoria principale. Nella maggior parte dei casi, il miglioramento delle prestazioni non implica una riduzione della qualità del modello completo.

Per un report tecnico che descrive l'implementazione di EM nell'algoritmo Microsoft Clustering, vedere Scaling EM (Expectation Maximization) Clustering to Large Databases .For a technical report that describes the implementation of EM in the Microsoft Clustering algorithm, see Scaling EM (Expectation Maximization) Clustering to Large Databases.

Clustering K-means

Il clustering K-means è un metodo noto che consiste nell'assegnare l'appartenenza a un cluster riducendo le differenze tra gli elementi di un cluster e massimizzando allo stesso tempo la distanza tra i cluster. Il termine "means" in K-means fa riferimento al centroide del cluster, ovvero un punto dati scelto arbitrariamente e quindi perfezionato in modo iterativo finché non rappresenta la media reale di tutti i punti dati del cluster. La lettera "K" fa riferimento a un numero arbitrario di punti utilizzati per inizializzare il processo di clustering. L'algoritmo K-means calcola le distanze euclidee al quadrato tra i record di dati in un cluster e il vettore che rappresenta la media del cluster, quindi converge su un set finale di K cluster quando la somma raggiunge il valore minimo.

L'algoritmo K-means assegna ogni punto dati esattamente a un unico cluster e non consente incertezze nell'appartenenza. L'appartenenza a un cluster è espressa come distanza dal centro.

In genere, l'algoritmo K-means viene utilizzato per la creazione di cluster di attributi continui, in cui il calcolo della distanza da una media è un processo diretto. Tuttavia, l'implementazione Di Microsoft adatta il metodo k-means agli attributi discreti del cluster, usando le probabilità. Per gli attributi discreti, la distanza di un punto dati da un determinato cluster viene calcolata come segue:

1 - P (punto dati, cluster)

Nota

L'algoritmo Microsoft Clustering non espone la funzione distance usata nel calcolo k-means e le misure di distanza non sono disponibili nel modello completato. Tuttavia, è possibile utilizzare una funzione di stima per restituire un valore che corrisponde alla distanza, in cui la distanza viene calcolata come la probabilità che un punto dati appartenga al cluster. Per altre informazioni, vedere ClusterProbability (DMX).

L'algoritmo K-means prevede due metodi di campionamento del set di dati: K-means non scalabile, che carica l'intero set di dati ed esegue un unico passaggio di clustering, oppure K-means scalabile, in cui l'algoritmo usa i primi 50.000 case e legge altri case solo se sono necessari più dati per ottenere un modello appropriato ai dati.

Aggiornamenti all'algoritmo Microsoft Clustering in SQL Server 2008

In SQL Server 2008, la configurazione predefinita dell'algoritmo microsoft clustering è stata modificata per usare il parametro interno, NORMALIZATION = 1. La normalizzazione viene eseguita usando le statistiche z-score e presuppone una distribuzione normale. Lo scopo di questa modifica apportata al comportamento predefinito è ridurre l'effetto di attributi che potrebbero avere grandezze eccessive e molti outlier. Tuttavia, è possibile che la normalizzazione z-score alteri i risultati di clustering su distribuzioni che non sono normali (ad esempio, le distribuzioni uniformi). Per impedire la normalizzazione e ottenere lo stesso comportamento dell'algoritmo di clustering K-means di SQL Server 2005, è possibile usare la finestra di dialogo di impostazione dei parametri per aggiungere il parametro personalizzato, NORMALIZATION, e impostare il valore corrispondente su 0.

Nota

Il parametro NORMALIZATION è una proprietà interna dell'algoritmo Microsoft Clustering e non è supportato. In generale l'uso della normalizzazione è consigliato nei modelli di clustering per migliorare i risultati del modello.

Personalizzazione dell'algoritmo Microsoft Clustering

L'algoritmo Microsoft Clustering supporta diversi parametri che influiscono sul comportamento, sulle prestazioni e sull'accuratezza del modello di data mining risultante.

Impostazione dei parametri dell'algoritmo

La tabella seguente descrive i parametri che possono essere usati con l'algoritmo Microsoft Clustering. Tali parametri influiscono sia sulle prestazioni che sull'accuratezza del modello di data mining risultante.

CLUSTERING_METHOD
Specifica il metodo di clustering utilizzato dall'algoritmo. Sono disponibili i metodi di clustering seguenti:

ID Metodo
1 EM scalabile
2 EM non scalabile
3 K-means scalabile
4 K-means non scalabile

Il valore predefinito è 1 (EM scalabile).

CLUSTER_COUNT
Specifica il numero approssimativo di cluster che devono essere generati dall'algoritmo. Se i dati non consentono di generare il numero approssimativo di cluster, l'algoritmo compila il maggior numero di cluster possibile. Se si imposta CLUSTER_COUNT su 0, l'algoritmo utilizzerà l'euristica per determinare con maggiore accuratezza il numero di cluster da compilare.

Il valore predefinito è 10.

CLUSTER_SEED
Specifica il numero di inizializzazione utilizzato per la generazione casuale dei cluster per la fase iniziale di compilazione del modello.

Modificando questo numero, è possibile cambiare il modo in cui vengono compilati i cluster iniziali, quindi confrontare i modelli compilati utilizzando valori di inizializzazione diversi. Se il valore di inizializzazione viene modificato ma i cluster trovati non cambiano di molto, il modello può essere considerato relativamente stabile.

Il valore predefinito è 0.

MINIMUM_SUPPORT
Specifica il numero minimo di case necessari per compilare un cluster. Se il numero di case nel cluster è minore di questo numero, il cluster viene considerato vuoto e viene ignorato.

Se si imposta un numero eccessivamente alto, è possibile che non vengano riscontrati cluster validi.

Nota

Se si utilizza EM, ovvero il metodo di clustering predefinito, alcuni cluster possono avere un valore di supporto minore di quello specificato. Ogni case viene infatti valutato per rilevarne l'appartenenza a tutti i cluster possibili e per alcuni cluster può essere disponibile solo un supporto minimo.

Il valore predefinito è 1.

MODELLING_CARDINALITY
Specifica il numero di modelli di esempio costruiti durante il processo di clustering.

Riducendo il numero di modelli candidati, è possibile migliorare le prestazioni rischiando però di non riscontrare alcuni modelli candidati validi.

Il valore predefinito è 10.

STOPPING_TOLERANCE
Specifica il valore utilizzato per determinare quando viene raggiunta la convergenza e l'algoritmo ha completato la compilazione del modello. La convergenza viene raggiunta quando la variazione complessiva nelle probabilità del cluster è inferiore al rapporto tra il parametro STOPPING_TOLERANCE e la dimensione del modello.

Il valore predefinito è 10.

SAMPLE_SIZE
Specifica il numero di case utilizzati dall'algoritmo a ogni passaggio se il parametro CLUSTERING_METHOD è impostato su uno dei metodi di clustering scalabili. Se si imposta il parametro SAMPLE_SIZE su 0, l'intero set di dati verrà inserito nel cluster in un unico passaggio. Il caricamento dell'intero set di dati in un unico passaggio può generare problemi di memoria e prestazioni.

Il valore predefinito è 50000.

MAXIMUM_INPUT_ATTRIBUTES
Specifica il numero massimo di attributi di input che l'algoritmo è in grado di gestire prima di richiamare la caratteristica di selezione degli attributi. Se si imposta il valore 0, indica che non esiste un numero massimo di attributi.

Se si aumenta il numero di attributi, si può verificare una riduzione significativa delle prestazioni.

Il valore predefinito è 255.

MAXIMUM_STATES
Specifica il numero massimo di stati degli attributi supportati dall'algoritmo. Se il numero di stati di un attributo è maggiore del numero massimo, l'algoritmo utilizza gli stati più frequenti dell'attributo e ignora gli stati rimanenti.

Se si aumenta il numero di stati, si può verificare una riduzione significativa delle prestazioni.

Il valore predefinito è 100.

Flag di modellazione

L'algoritmo supporta i flag di modellazione seguenti. I flag di modellazione, definiti durante la creazione della struttura o del modello di data mining, specificano la modalità di gestione dei valori in ogni colonna durante l'analisi.

Flag di modellazione Descrizione
MODEL_EXISTENCE_ONLY La colonna verrà considerata come se disponesse di due stati possibili: Missing ed Existing. Un valore Null è un valore mancante.

Si applica alla colonna del modello di data mining.
NOT NULL La colonna non può contenere un valore Null. Se Analysis Services rileva un valore Null durante il training del modello, viene generato un errore.

Si applica alla colonna della struttura di data mining.

Requisiti

Un modello di clustering deve contenere una colonna chiave e le colonne di input. È inoltre possibile definire le colonne di input come stimabili. Le colonne impostate su Solo stima non vengono usate per la compilazione di cluster. La distribuzione di questi valori nel cluster viene calcolata dopo la compilazione dei cluster.

Colonne di input e stimabili

L'algoritmo Microsoft Clustering supporta le colonne di input specifiche e le colonne stimabili elencate nella tabella seguente. Per altre informazioni sui tipi di contenuto usati in un modello di data mining, vedere Tipi di contenuto (data mining).

Colonna Tipi di contenuto
Attributo di input Continuous, Cyclical, Discrete, Discretized, Key, Table, Ordered
Attributo stimabile Continuous, Cyclical, Discrete, Discretized, Table, Ordered

Nota

Sono supportati i tipi di contenuto Cyclical e Ordered ma l'algoritmo li considera come valori discreti e non esegue un'elaborazione speciale.

Vedere anche

Algoritmo Microsoft Clustering
Esempi di query sul modello di clustering
Contenuto dei modelli di data mining per i modelli di clustering (Analysis Services - Data mining)