Agosto 2015

Volume 30 numero 8

Test Run - K-mezzi + + Clustering di dati

Da James McCaffrey

James McCaffreyClustering di dati sono il processo di raggruppamento di elementi di dati affinché articoli simili sono messi insieme. Una volta raggruppati, i cluster di dati possono essere esaminati per vedere se ci sono relazioni che potrebbero essere utili. Ad esempio, se è stato cluster una serie enorme di dati di vendita, informazioni sui dati in ogni cluster potrebbero rivelare modelli che potrebbero essere utilizzati per il marketing mirato.

Esistono diversi algoritmi di clustering. Uno dei più comuni è chiamato l'algoritmo k-means. Ci sono diverse varianti di questo algoritmo. Questo articolo viene descritto una variante relativamente recente chiamata k-mezzi + + algoritmo.

Guardate il programma demo in Figura 1. Il programma inizia con gli elementi di 20 dati, ognuna consistente di altezza di una persona in pollici e peso in libbre. Successivamente, il numero di cluster è impostato su 3. In dati la maggior parte degli scenari di cluster, il numero di cluster deve essere specificato dall'utente.

K-mezzi + + Clustering in azione
Figura 1 K-mezzi + + Clustering in azione

Il programma demo quindi cluster i dati utilizzando il k-mezzi + + algoritmo. Ognuno degli elementi di 20 dati viene assegnato a un cluster con ID 0, 1 o 2. Le assegnazioni del cluster sono archiviate in una matrice, dove l'indice della matrice corrisponde a un indice dei dati e il valore della matrice è l'ID del cluster associata. Ad esempio, il clustering finale dei dati demo è:

0 2 1 1 2 . . . 1

Indica dati elemento 0 (altezza = 65,0, peso = 220.0) viene assegnato al cluster 0, dati elemento 1 viene assegnato al cluster 2, dati elemento 2 viene assegnato al cluster 1 e così via. La demo si conclude visualizzando i dati, raggruppati per cluster. Ecco svelato uno schema molto chiaro. Ci sono otto persone caratterizzate da media altezza e peso pesante, sette persone con bassa statura e peso leggero e cinque persone con alto altezza e peso medio.

Questo articolo presuppone che hai competenze di programmazione almeno intermedie ma non assumere che si sa nulla circa la k-mezzi + + algoritmo. Il programma demo è codificato utilizzando c#, ma non dovreste avere troppe difficoltà refactoring del codice in un'altra lingua, ad esempio Python o JavaScript. Il codice demo è troppo lungo per presentare nella sua interezza, ma il sorgente completo è disponibile nel download del codice che accompagna questo articolo.

Comprendere il K-mezzi + + algoritmo

Il k-algoritmo di mezzi + + è una variante dell'algoritmo k-means standard, così per capire k-mezzi + + è necessario prima capire il regolare k-means. L'algoritmo k-means ha una storia interessante e a volte è chiamato algoritmo di Lloyd. Il "k" in k-means si intende il numero di cluster. In pseudo-codice molto ad alto livello, la forma più comune di standard k-means è ingannevolmente semplice:

pick k initial means
loop until no change
  assign each data item to closest mean
  compute new means based on new clusters
end loop

Nonostante il suo aspetto semplice, l'algoritmo k-means standard è, infatti, molto sottile, e implementazione è sorprendentemente difficile. Si supponga che i dati da inserire nel cluster è costituito da elementi di 20 dati illustrati nella Figura 1, con k impostata su 3. Il primo passaggio consiste nel selezionare tre degli elementi di dati di agire come mezzo iniziale. Un approccio comune è quello di selezionare gli elementi di dati in modo casuale. Supponiamo che i tre selezionati in modo casuale gli elementi di dati sono voce 2 (59,0, 110.0) come la media di cluster 0, elemento 4 (75.0, 150.0) come la media di cluster 1 e 6 (68,0, 230,0) come la media di cluster 2.

All'interno del ciclo di elaborazione principale, ogni elemento di dati è esaminato e assegnato al cluster con la media più vicino. Così, dati elemento 0 (65.0, 220.0) sarebbe essere assegnato al cluster 2 perché elemento 0 è più vicino (68,0, 230,0) rispetto agli altri due significa. Ognuno degli elementi rimanenti 19 dati verrebbe assegnato a un cluster. Si noti che gli elementi di dati che sono stati inizialmente selezionati come mezzo verrebbe assegnati al cluster corretto perché la distanza sarebbe 0.

Dopo ogni elemento di dati viene assegnato a uno dei cluster, viene calcolato un nuovo mezzo per ogni cluster. Si supponga che tale cluster 0 attualmente contiene solo tre elementi di dati: (59.0, 110.0), (70.0, 210.0), (61.0, 130.0). Il nuovo mezzo per questo cluster sarebbe:

( (59 + 70 + 61)/3, (110 + 210 + 130)/3 ) =
(190/3, 450/3) =
(63.3, 150.0)

Nuovi mezzi per i cluster 1 e 2 dovrebbe essere calcolati allo stesso modo. I nuovi mezzi di comunicazione non sono necessariamente uno degli elementi di dati effettivi piu '. Tecnicamente, ognuno dei nuovi mezzi è un "baricentro", ma la "media" di termine è comunemente usata.

Dopo nuovi mezzi di calcolo, ogni elemento di dati è nuovamente esaminato e assegnato al cluster con la più nuova media. Il cluster di aggiornamento iterativo, aggiornamento-significa processo continua finché non ci sarà nessun cambiamento nelle assegnazioni di cluster.

Tutto questo suona relativamente semplice, ma molto può andare storto con un'implementazione naïve dell'algoritmo k-means standard. In particolare, una cattiva scelta per i mezzi iniziale può portare a un raggruppamento molto povera di dati o a un runtime molto lungo a stabilizzazione, o entrambi. Come si scopre, buoni mezzi iniziali sono quelli che non sono vicino a vicenda. Il k-mezzi + + algoritmo seleziona iniziale significa che non è vicino a vicenda, quindi utilizza l'algoritmo k-means standard per il clustering.

Il K-mezzi + + meccanismo di inizializzazione

In pseudocodice ad alto livello il k-mezzi + + meccanismo di inizializzazione per selezionare significa è:

select one data item at random as first mean
loop k-1 times
  compute distance from each item to closest mean
  select an item that has large distance-squared
    as next initial mean
end loop

Ancora una volta, nello pseudo-codice è ingannevolmente semplice. Il k-mezzi + + meccanismo di inizializzazione è illustrata Figura 2. Ci sono nove punti dati, ognuno dei quali ha due componenti. Il numero di cluster è impostato su 3, quindi gli elementi di 3 dati devono essere selezionati come mezzo iniziale.

K-mezzi + + meccanismo di inizializzazione
Figura 2 K-mezzi + + meccanismo di inizializzazione

Il diagramma in Figura 2 Mostra il k-mezzi + + processo di inizializzazione dopo due dei tre mezzi iniziali sono stati selezionati. L'iniziale dire a (3, 6) è stato selezionato casualmente. Poi la distanza al quadrato da ciascuno degli altri elementi di 8 dati alla prima media è stato calcolato, e utilizzando queste informazioni, la seconda iniziale dire alle (4, 3) è stato selezionato (nel senso che spiegherò tra breve).

Per selezionare un elemento di dati come la terza media iniziale, viene calcolata la distanza al quadrato da ogni punto di dati alla media più vicino. Le distanze sono indicate come linee tratteggiate. Utilizzando questi valori di distanza al quadrato, la terza media sarà selezionata in modo che gli elementi di dati con valori di distanza al quadrato piccolo hanno una bassa probabilità di essere selezionati ed elementi di dati con valori di grande distanza al quadrato hanno un'alta probabilità di essere selezionati. Questa tecnica è talvolta chiamata selezione fitness proporzionale.

Selezione di fitness proporzionale è il cuore del k-mezzi + + meccanismo di inizializzazione. Ci sono diversi modi per implementare la selezione fitness proporzionale. Il programma demo utilizza una tecnica chiamata selezione di ruota di roulette. In pseudocodice ad alto livello, una forma di selezione di ruota di roulette è:

p = random value between 0.0 and 1.0
create an array of cumulative probabilities
loop each cell of cum prob array
  if cum[i] >= p
    return i
  end if
end loop

Un esempio concreto aiuterà a chiarire la selezione di ruota di roulette. Si supponga che esistono quattro elementi di candidato (0, 1, 2, 3) con valori associati (20.0, 10.0, 40.0, 30.0). La somma dei valori è 20.0 + 40.0 + 10,0 + 30.0 = 100.0. Selezione di fitness proporzionale sceglierà elemento 0 con probabilità 20.0/100.0 = 0.20; scegliere elemento 1 con probabilità 10.0/100.0 = 0,10; scegliere la voce 2 con probabilità 40.0/100.0 = 0.40; e scegliere la voce 3 con probabilità 30.0/100.0 = 0.30.

Se le probabilità di selezione vengono memorizzate in una matrice come (0.10, 0.20, 0.30, 0.40), le probabilità cumulative sono memorizzabili in una matrice con valori (0.20, 0.30, 0,70 1,00). Ora, supponiamo che un p casuale viene generato con valore 0,83. Se i è un indice di matrice nella matrice, le probabilità cumulative quando i = 0, massimo [i] = 0,20, che non è maggiore di p = 0,83, in modo che i viene incrementato di 1. A questo punto massimo [i] = 0,30, che ancora non maggiore di p, pertanto i incrementa a 2. A questo punto massimo [i] 0.70 che ancora non maggiore di p, pertanto i incrementa a 3. A questo punto massimo [i] = 1,00, che è maggiore di p, pertanto i = 3 viene restituito come l'elemento selezionato.

Si noti che le distanze tra le probabilità cumulative differiscono, con grandi differenze corrispondenti a tali elementi con maggiore probabilità di selezione.

Per riassumere, il k-mezzi + + algoritmo seleziona iniziale significa quindi i mezzi sono dissimili, quindi utilizza l'algoritmo k-means standard ai dati del cluster. Il processo di inizializzazione utilizza selezione fitness proporzionale, che può essere implementato in diversi modi. La selezione di ruota roulette demo programma usi.

Struttura generale del programma

La struttura complessiva del programma demo, con alcune modifiche minori per risparmiare spazio, è presentata Figura 3. Per creare il programma demo, ho lanciato Visual Studio e creato un nuovo progetto applicazione console di c# denominato KMeansPlus. Il programma demo non ha significative Microsoft .NET Framework dipendenze quindi funzionerà con qualsiasi versione relativamente recente di Visual Studio .

Figura 3 struttura generale del programma

using System;
using System.Collections.Generic;
namespace KMeansPlus
{
  class KMeansPlusProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin k-means++ demo");
      // All program code here
      Console.WriteLine("End k-means++ demo");
      Console.ReadLine();
    }
    public static int[] Cluster(double[][] rawData,
      int numClusters, int seed) { . . }
    public static double[][] InitMeans(int numClusters,
      double[][] data, int seed) { . . }
    private static double[][] Normalized(double[][] rawData) { . . }
    private static double[][] MakeMatrix(int rows, int cols) { . . }
    private static bool UpdateMeans(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static bool UpdateClustering(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static double Distance(double[] tuple,
      double[] mean) { . . }
    private static int MinIndex(double[] distances) { . . }
    static void ShowData(double[][] data, int decimals,
      bool indices, bool newLine) { . . }
    static void ShowVector(int[] vector, bool newLine) { . . }
    static void ShowClustered(double[][] data, int[] clustering,
      int numClusters, int decimals)
  }
} // ns

Dopo il codice del modello caricati nell'editor, nella finestra Esplora soluzioni che selezionata sul file Program.cs, rinominato il KMeansPlusProgram.cs più descrittivo e permesso Visual Studio rinominare automaticamente classe Program. Nella finestra dell'editor, nella parte superiore del codice generato da modelli, ho eliminato tutti i riferimenti agli spazi dei nomi ad eccezione di quelli per il primo livello dello spazio dei nomi System e lo spazio dei nomi Collections.Generic.

Il metodo Main inizia impostando gli elementi 20 dati grezzi:

double[][] rawData = new double[20][];
rawData[0] = new double[] { 65.0, 220.0 };
...
rawData[19] = new double[] { 61.0, 130.0 };

In uno scenario di demo non si sarebbero probabilmente leggere dati da un database SQL o un file di testo. Dopo aver visualizzato i dati non elaborati utilizzando un metodo di supporto definito dal programma denominato ShowData, i dati sono di tipo cluster:

int numClusters = 3;
int[] clustering = Cluster(rawData,   numClusters, 0);

Anche se ci sono alcune tecniche che è possibile utilizzare per indovinare il miglior numero di cluster, in generale è necessario utilizzare tentativi ed errori. Il metodo di Cluster accetta dati numerici crudi al cluster in un array di array stile matrix; il numero di cluster da utilizzare (ho potuto utilizzare "k" ma "numClusters" è più leggibile); e un valore di inizializzazione da utilizzare per la randomizzazione.

Il metodo Main conclude visualizzando l'array clustering e mostrando i dati grezzi raggruppati per cluster:

ShowVector(clustering, true);
ShowClustered(rawData, clustering, numClusters, 1);

Ho usato un approccio di metodo statico, piuttosto che un approccio OOP. Cluster di metodo chiama quattro metodi di supporto. Metodo di supporto Normalized accetta una matrice di dati grezzi e restituisce una matrice dove i dati sono stati normalizzati in modo che tutti i valori sono più o meno la stessa grandezza (in genere tra-6.0 e + 6,0). Metodo InitMeans implementa il k-mezzi + + meccanismo di inizializzazione. Metodi UpdateClustering e UpdateMeans implementare i componenti principali dell'algoritmo k-medie standard.

Metodi InitMeans e UpdateClustering entrambi chiamare metodo helper distanza, che restituisce la distanza euclidea tra elementi di due dati. Ad esempio, se è una tupla di dati (3.0, 9.0, 5.0) e una seconda tupla è (2.0, 6.0, 1.0), la distanza euclidea tra i due elementi è:

Sqrt( (3-2)^2 + (9-6)^2 + (5-1)^2) ) =
Sqrt( 1 + 9 + 16 ) =
Sqrt(26) = 5.1

Altre definizioni di distanza possono essere utilizzati. In generale, k-means e k-mezzi + + sono utilizzati in cluster dati rigorosamente numerici piuttosto che dati categorici.

Implementazione di K-mezzi + +

Il codice per il metodo Cluster è presentato Figura 4. Metodo Cluster inizia normalizzando i dati grezzi in modo che grandi componenti in elementi di dati (ad esempio valori di peso nella demo) non dominano i componenti più piccoli (i valori di altezza). La demo utilizza normalizzazione gaussiana. Due alternative comuni sono min-max normalizzazione e la normalizzazione di ordine di grandezza. Un'alternativa di progettazione è quello di normalizzare i dati grezzi in una fase di pre-elaborazione, quindi passare i dati normalizzati direttamente al metodo Cluster.

Figura 4 Metodo Cluster

public static int[] Cluster(double[][] rawData,
 int numClusters, int seed)
{
  double[][] data = Normalized(rawData);
  bool changed = true;
  bool success = true;
  double[][] means = InitMeans(numClusters, data, seed);
  int[] clustering = new int[data.Length];
  int maxCount = data.Length * 10;
  int ct = 0;
  while (changed == true && success == true &&
    ct < maxCount)
  {
    changed = UpdateClustering(data, clustering, means);
    success = UpdateMeans(data, clustering, means);
    ++ct;
  }
  return clustering;
}

Metodo InitMeans implementa il k-mezzi + + meccanismo di inizializzazione e restituisce un set di significa che sono molto distanti tra loro in termini di distanza euclidea. All'interno del ciclo principale di clustering, metodo UpdateClustering scorre attraverso ogni elemento di dati e assegna ogni elemento del cluster associato con i più attuali mezzi/centroidi. Il metodo restituisce false se non non c'è nessun cambiamento per le assegnazioni di cluster (che indica che il clustering è completo) o se il nuovo raggruppamento si tradurrebbe in un cluster che non ha elementi di dati (che indica che qualcosa non va). Alternativa è possibile generare un'eccezione in una situazione di zero-conteggio cluster.

Metodo UpdateMeans scorre i dati assegnati a ogni cluster e calcola un nuovo media/centroide per ogni cluster. Il metodo restituisce false se uno o più mezzi non possono essere calcolati perché un cluster non ha elementi di dati.

Il ciclo principale di clustering utilizza un controllo di conteggio di sanità mentale per evitare un ciclo infinito. L'algoritmo k-means in genere si stabilizza molto rapidamente, ma non non c'è alcuna garanzia che l'algoritmo si stabilizzerà a tutti. Il valore di maxCount è impostato a 10 volte il numero di elementi di dati, che è arbitraria, ma ha funzionato bene per me in pratica.

La definizione del metodo InitMeans inizia con:

public static double[][] InitMeans(int numClusters,
  double[][] data, int seed)
{
  double[][] means = MakeMatrix(numClusters, data[0].Length);
  List<int> used = new List<int>();
...

La matrice locale matrici di matrici stile denominata mezzi detiene il metodo viene restituito, dove l'indice di riga è un ID del cluster e ogni riga è una matrice che contiene i componenti della media associata. L'elenco < int > denominato utilizzato contiene indici degli elementi di dati che sono stati assegnati come mezzo iniziale, in modo duplicati significa iniziale può essere evitato. Questo approccio presuppone che non sono presenti elementi di dati con valori identici. Quando il clustering, come avete a che fare con gli elementi di dati duplicati dipende dallo scenario particolare problema. Un'alternativa a rimuovere gli elementi duplicati nei dati di origine è il peso degli elementi duplicati dalla loro frequenza.

Successivamente, il primo mezzo iniziale è selezionato e memorizzato:

Random rnd = new Random(seed);
int idx = rnd.Next(0, data.Length);
Array.Copy(data[idx], means[0], data[idx].Length);
used.Add(idx);

Il primo mezzo iniziale viene selezionato a caso da tutti gli elementi di dati. Il mezzo iniziale è presenti elementi di dati e sono a volte chiamati medoid.

Prossimo, una per ciclo viene costruita per selezionare le restanti k-1 significa:

for (int k = 1; k < numClusters; ++k)
{
  double[] dSquared = new double[data.Length];
  int newMean = -1;
...

DSquared matrice tiene le distanze al quadrato tra ogni elemento di dati e la media iniziale esistente più vicina. NewMean variabile contiene l'indice di un elemento di dati che sarà la prossima media iniziale. Successivamente, viene esaminato ogni elemento di dati (normalizzata) e il valore di dSquared è calcolato e memorizzato:

for (int i = 0; i < data.Length; ++i)
{
  if (used.Contains(i) == true) continue;
  double[] distances = new double[k];
  for (int j = 0; j < k; ++j)
    distances[j] = Distance(data[i], means[k]);
  int m = MinIndex(distances);
  dSquared[i] = distances[m] * distances[m];
}

La verifica per determinare se un elemento di dati è già stato utilizzato come una media iniziale non è necessaria perché se l'elemento è stato utilizzato, la distanza al quadrato alla media armadio sarà la distanza a se stesso, che è 0. La matrice denominata distanze conterrà le distanze Euclidee dall'elemento di dati corrente a ciascuno dei mezzi iniziale k esistenti che sono stati selezionati finora.

Ricordare che la distanza euclidea nel metodo distanza prende la radice quadrata della somma delle differenze al quadrato tra componenti di elemento di dati. Perché k-mezzi + + utilizza distanze al quadrato, l'operazione di squadratura in InitMeans Annulla l'operazione di radice quadrata in distanza. Di conseguenza, si potrebbe semplificare il codice mediante la definizione di un metodo che restituisce la distanza al quadrato direttamente.

Successivamente, viene preparato il ciclo per scorrere le probabilità cumulative per selezione di ruota di roulette:

double p = rnd.NextDouble();
double sum = 0.0;
for (int i = 0; i < dSquared.Length; ++i)
  sum += dSquared[i];
double cumulative = 0.0;
int ii = 0;
int sanity = 0;

Viene generato un valore casuale compreso tra 0.0 e 1.0 e viene calcolata la somma delle distanze al quadrato, come spiegato nella sezione che descrive selezione fitness proporzionale. Invece di creare in modo esplicito una matrice di probabilità cumulativa, risulta più efficiente per generare la probabilità cumulativa corrente al volo.

Ogni probabilità cumulativa è calcolata ed esaminato in un po' di tempo ciclo che implementa selezione di ruota di roulette:

while (sanity < data.Length * 2)
{
  cumulative += dSquared[ii] / sum;
  if (cumulative >= p && used.Contains(ii) == false)
  {
    newMean = ii; // the chosen index
    used.Add(newMean); // don't pick again
    break;
  }
  ++ii; // next candidate
  if (ii >= dSquared.Length) ii = 0; // past the end
  ++sanity;
}

Il ciclo while progressi fino a quando il valore di probabilità cumulativa è maggiore o uguale al valore casuale p. Tuttavia, non è possibile consentire duplicati significa iniziale in modo che se la media selezionata nell'elenco "usata" < int >, viene selezionato l'elemento successivo di dati disponibili. Se l'indice ii viene eseguito oltre la fine dei dati, viene reimpostato su 0. Si noti che se è già stato selezionato un elemento di dati come una media iniziale, il successivo elemento di dati disponibile probabilmente non sarà l'elemento successivo più probabile.

Metodo InitMeans conclude salvando la media iniziale selezionata e restituisce la matrice di mezzi selezionati:

...
    Array.Copy(data[newMean], means[k], data[newMean].Length);
  } // k, each remaining mean
  return means;
} // InitMean

Lo scopo del metodo InitMeans è quello di trovare gli elementi di dati dissimili k per essere utilizzato come mezzo iniziale. Selezione di ruota di roulette non garantisce che i mezzi selezionati sono al massimo diversi gli uni dagli altri, e c'è una possibilità molto piccola che i mezzi selezionati potrebbero essere abbastanza vicino a vicenda. Pertanto, se si desidera effettuare il refactoring del metodo InitMeans modo che la selezione di ruota di roulette viene utilizzato più volte per generare set di candidati di mezzi e quindi restituire il set contenente significa che sono più differenti gli uni dagli altri.

Avvolgendo

Questo articolo è basato sul libro della ricerca 2007, "K-mezzi + +: I vantaggi di Seeding attenzione,"d. Arthur e S. Vassilvitskii. Come avviene in genere con ricerche, praticamente non assegnato nessun dettaglio di implementazione. Tuttavia, il libro spiega attentamente come k-mezzi + + inizializzazione funziona e stabilisce i limiti teorici per il suo comportamento.


Ripristino di emergenza. James McCaffrey lavora per Microsoft Research a Redmond, Washington. Ha lavorato su numerosi prodotti Microsoft, inclusi Internet Explorer e Bing. Dr. È possibile contattarlo McCaffrey jammc@microsoft.com.


Grazie all'esperto tecnico Microsoft Research seguente per la revisione di questo articolo: Kirk Olynyk