Riferimento tecnico per l'algoritmo Microsoft Clustering

Questa sezione illustra l'implementazione dell'algoritmo Microsoft Clustering, inclusi i parametri che è possibile usare per controllare il comportamento dei modelli di clustering. Fornisce inoltre indicazioni su come migliorare le prestazioni quando si creano ed elaborano modelli di clustering.

Per altre informazioni sull'uso dei modelli di clustering, vedere gli argomenti seguenti:

• Contenuto del modello di mining per i modelli di clustering (Analysis Services - Data Mining)

• Esempi di query del modello di clustering

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 clustering rigido. Ciò significa che un punto dati può appartenere a un solo cluster e che viene calcolata una singola probabilità per l'appartenenza di ogni punto dati in tale cluster. Il secondo metodo, il metodo Expectation Maximization (EM), è un metodo soft clustering . Ciò significa che un punto dati appartiene sempre a più cluster e che 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.

Clusterizzazione EM

Nel clustering EM l'algoritmo affina in modo iterativo un modello cluster iniziale per adattare i dati e determina la probabilità che un punto dati esista in un cluster. L'algoritmo termina il processo quando il modello probabilistico si adatta ai dati. La funzione usata per determinare l'adattamento è la probabilità di log dei dati specificati dal modello.

Se durante il processo vengono generati cluster vuoti o se l'appartenenza di uno o più cluster scende al di sotto di una determinata soglia, i cluster con popolamenti bassi vengono reinviati in nuovi punti e l'algoritmo EM viene rieseguito.

I risultati del metodo di clustering EM sono probabilistici. Ciò significa che ogni punto dati appartiene a tutti i cluster, ma ogni assegnazione di un punto dati a un cluster ha una probabilità diversa. Poiché il metodo consente la sovrapposizione dei cluster, la somma degli elementi in tutti i cluster può superare gli elementi totali del set di training. Nei risultati del modello di data mining i punteggi che indicano il supporto vengono modificati in base a questo.

L'algoritmo EM è l'algoritmo predefinito usato nei modelli di clustering Microsoft. Questo algoritmo viene usato come predefinito perché offre più vantaggi rispetto al clustering k-means:

• Richiede al massimo un'analisi del database.

• Funzionerà nonostante memoria limitata (RAM).

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

• Supera gli approcci di campionamento.

L'implementazione di Microsoft offre due opzioni: EM scalabile e non scalabile. Per impostazione predefinita, in EM scalabile, i primi 50.000 record vengono usati per eseguire il seeding dell'analisi iniziale. In caso di esito positivo, il modello usa solo questi dati. Se il modello non può essere adatto utilizzando 50.000 record, vengono letti altri 50.000 record. In EM non scalabile, l'intero set di dati viene letto indipendentemente dalle dimensioni. Questo metodo potrebbe creare cluster più accurati, ma i requisiti di memoria possono essere significativi. Poiché EM scalabile opera su un buffer locale, l'iterazione dei dati è molto più veloce e l'algoritmo usa molto meglio la cache della memoria della CPU rispetto a EM non scalabile. Inoltre, EM scalabile è tre volte più veloce di EM non scalabile, anche se tutti i dati possono essere inseriti nella memoria principale. Nella maggior parte dei casi, il miglioramento delle prestazioni non comporta una qualità inferiore del modello completo.

Per un report tecnico che descrive l'implementazione di EM nell'algoritmo Microsoft Clustering, vedere Scala EM (Expectation Maximization) Clustering su Database di grandi dimensioni.

Clustering K-Means

Il clustering K-means è un metodo noto per assegnare l'appartenenza al cluster riducendo al minimo le differenze tra gli elementi in un cluster, ottimizzando al contempo la distanza tra i cluster. Il termine "means" in k-means si riferisce al centro del cluster, ovvero un punto dati scelto in modo arbitrario e quindi perfezionato in modo iterativo fino a quando non rappresenta la vera media di tutti i punti dati nel cluster. Il termine "k" si riferisce a un numero arbitrario di punti usati per eseguire il seeding del processo di clustering. L'algoritmo k-means calcola le distanze euclidee quadrate tra i record di dati in un cluster e il vettore che rappresenta la media del cluster e converge su un set finale di k cluster quando tale somma raggiunge il valore minimo.

L'algoritmo k-means assegna ogni punto dati a un solo cluster e non consente l'incertezza nell'appartenenza. L'appartenenza a un cluster viene espressa come distanza dal centroide.

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

1 - P(punto dati, cluster)

Annotazioni

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

L'algoritmo k-means fornisce due metodi di campionamento del set di dati: il k-means non scalabile, che carica l'intero set di dati ed esegue una sola passata di clustering, e il k-means scalabile, in cui l'algoritmo utilizza i primi 50.000 casi e legge più casi solo se richiede più dati per ottenere una buona adattabilità del modello ai dati.

Aggiornamenti dell'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 nel comportamento predefinito è ridurre al minimo l'effetto degli attributi che potrebbero avere grandi dimensioni e molti outlier. Tuttavia, la normalizzazione del punteggio z può modificare i risultati del clustering nelle distribuzioni che non sono normali (ad esempio distribuzioni uniformi). Per evitare la normalizzazione e ottenere lo stesso comportamento dell'algoritmo di clustering K-means in SQL Server 2005, è possibile usare la finestra di dialogo Impostazioni parametro per aggiungere il parametro personalizzato, NORMALIZATION e impostarne il valore su 0.

Annotazioni

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. Questi parametri influiscono sia sulle prestazioni che sull'accuratezza del modello di data mining risultante.

METODO_DI_RAGGRUPPAMENTO
Specifica il metodo di clustering da usare per l'algoritmo. Sono disponibili i metodi di clustering seguenti:

Documento d'identità	Metodo
1	EM scalabile
2	EM non scalabile
3	K-Means scalabile
4	K-Means non scalabile.

Il valore predefinito è 1 (EM scalabile).

Conteggio del Cluster
Specifica il numero approssimativo di cluster da compilare dall'algoritmo. Se il numero approssimativo di cluster non può essere compilato dai dati, l'algoritmo compila il maggior numero possibile di cluster. Se si imposta il CLUSTER_COUNT su 0, l'algoritmo usa l'euristica per determinare al meglio il numero di cluster da compilare.

L'impostazione predefinita è 10.

CLUSTER_SEED
Specifica il numero seed usato per generare in modo casuale i cluster per la fase iniziale della costruzione del modello.

Modificando questo numero, è possibile modificare la modalità di compilazione dei cluster iniziali e quindi confrontare i modelli compilati usando semi diversi. Se il seed viene modificato, ma i cluster trovati non cambiano notevolmente, il modello può essere considerato relativamente stabile.

Il valore predefinito è 0.

SUPPORTO_MINIMO
Specifica il numero minimo di case necessari per compilare un cluster. Se il numero di case nel cluster è inferiore a questo numero, il cluster viene considerato vuoto e rimosso.

Se si imposta questo numero troppo alto, è possibile che si perdano cluster validi.

Annotazioni

Se si usa EM, ovvero il metodo di clustering predefinito, alcuni cluster possono avere un valore di supporto inferiore al valore specificato. Questo perché ogni caso viene valutato per l'appartenenza a tutti i cluster possibili e per alcuni cluster potrebbe essere disponibile solo un supporto minimo.

Il valore predefinito è 1.

MODELLAZIONE_CARDINALITÀ
Specifica il numero di modelli di esempio costruiti durante il processo di clustering.

La riduzione del numero di modelli candidati può migliorare le prestazioni a rischio di mancanza di alcuni modelli candidati validi.

L'impostazione predefinita è 10.

TOLLERANZA_DI_ARRESTO
Specifica il valore utilizzato per determinare quando viene raggiunta la convergenza e l'algoritmo completa la costruzione del modello. La convergenza viene raggiunta quando la variazione complessiva delle probabilità del cluster è inferiore al rapporto tra il parametro STOPPING_TOLERANCE diviso per le dimensioni del modello.

L'impostazione predefinita è 10.

SAMPLE_SIZE
Specifica il numero di case utilizzati dall'algoritmo in 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à raggruppato in un singolo passaggio. Il caricamento dell'intero set di dati in un singolo passaggio può causare problemi di memoria e prestazioni.

Il valore predefinito è 50000.

Attributi Di Input Massimi
Specifica il numero massimo di attributi di input che l'algoritmo può gestire prima di richiamare la selezione delle funzionalità. L'impostazione di questo valore su 0 specifica che non esiste alcun numero massimo di attributi.

L'aumento del numero di attributi può ridurre significativamente le prestazioni.

Il valore predefinito è 255.

STATI_MASSIMI
Specifica il numero massimo di stati dell'attributo supportati dall'algoritmo. Se un attributo ha più stati del valore massimo, l'algoritmo usa gli stati più diffusi e ignora gli stati rimanenti.

L'aumento del numero di stati può ridurre significativamente le prestazioni.

L'impostazione predefinita è 100.

Bandiere di modellazione

L'algoritmo supporta i flag di modellazione seguenti. I flag di modellazione vengono definiti quando si crea la struttura di data mining o il modello di data mining. I flag di modellazione specificano la modalità di gestione dei valori in ogni colonna durante l'analisi.

Indicatore di modellazione	Descrizione
SOLO_ESISTENZA_MODELLO	La colonna verrà considerata come con due possibili stati: Mancante e Esistente. Un valore Null è un valore mancante. Si applica alla colonna del modello di mining.
NON NULLO	La colonna non può contenere un valore Null. Se Analysis Services rileva un valore Null durante il training del modello, verrà generato un errore. Si applica alla colonna della struttura di mining.

Requisiti

Un modello di clustering deve contenere una colonna chiave e colonne di input. È anche possibile definire colonne di input come prevedibili. Le colonne impostate su Predict Only non vengono usate per compilare cluster. La distribuzione di questi valori nei cluster viene calcolata dopo la compilazione dei cluster.

Colonne di input e prevedibili

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	Continuo, Ciclico, Discreto, Discretizzato, Chiave, Tabella, Ordinato
Attributo prevedibile	Continuo, Ciclico, Discreto, Discretizzato, Tabella, Ordinato

Annotazioni

I tipi di contenuto ciclici e ordinati sono supportati, ma l'algoritmo li considera come valori discreti e non esegue un'elaborazione speciale.

Vedere anche

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