---

Ottobre 2015

Volume 30 Numero 10

Il presente articolo è stato tradotto automaticamente.

Esecuzione di test - Analisi discriminante lineare con C#

Da James McCaffrey

L'obiettivo di un problema di classificazione binaria è per stimare il valore di una variabile che può assumere uno dei due valori possibili. È possibile, ad esempio stimare la modifica di un'azienda (aumentare o diminuire) il prezzo delle azioni in base alle variabili predittive come numero medio di condivisioni di vendita, numero di transazioni insider, rapporto prezzo-utile e così via. In alternativa, è possibile prevedere che l'inclinazione politica di una persona (il libero o conservativa) in base a età, reddito, il livello di istruzione e così via.

Esistono circa una dozzina principali algoritmi che possono essere utilizzati per la classificazione binaria. Analisi stabilire lineare (LDA) è uno degli approcci meno recenti, risalenti al 1930s. In questo articolo viene spiegato cosa LDA è, viene descritto come funziona e viene illustrato come implementare LDA con codice.

In realtà è probabilmente non che sarà mai necessario scrivere codice LDA. Tuttavia, esistono tre motivi in questo articolo possono risultare utili. In primo luogo, comprendere come programmare LDA offre una completa padronanza del funzionamento LDA nel caso in cui si accede mai su di esso. In secondo luogo, alcune delle tecniche di codifica utilizzate quando si implementa LDA può essere utile in altri scenari di programmazione più comuni. Infine, concetti LDA sono particolarmente utili e interessanti LDA esemplificativa di per.

Il modo migliore per acquisire familiarità con la classificazione binari quali LDA e per vedere quale ha inizio in questo articolo è a esaminare il programma demo in Figura 1.

Figura 1 analisi Descriminate lineare classificazione binario Demo

L'obiettivo del programma demo è per stimare l'inclinazione politico, il libero o conservativa, di una persona in base all'età e reddito annuale della persona. La demo utilizza un set di dati di training piccolo con otto solo elementi per creare il modello di stima LDA. Sia età e reddito sono stati normalizzati in qualche modo, in modo che i relativi ordini di grandezza sono entrambi approssimativamente lo stesso.

Inclinazione politici è stata codificata in modo che il libero è 0 e conservativo è 1. A differenza di molti algoritmi di classificazione binario LDA è possibile utilizzare qualsiasi tipo di codifica per la variabile per la stima. In modo inclinazione politici è codificato come -1 e + 1, o "A" e "b".

Classificazione LDA binaria è possibile utilizzare qualsiasi numero di variabili predittive. Ed è possibile estendere LDA base per stimare una variabile che può assumere uno dei tre o più valori. Ad esempio possibile stimare inclinazione politici dove i valori possibili sono libero, conservativa e moderata. In questo articolo viene descritto solo binaria classificazione.

La chiave per LDA è un elemento denominato lineare stabilire, in genere rappresentata da minuscolo "w". Utilizzando gli elementi di otto dati, calcola la demo w = (-0.868,-0.496). La matrice w avrà lo stesso numero di valori come variabili predittive. Durante il calcolo w, dietro le quinte la demo calcola i mezzi per ognuna delle due classi, quindi utilizza i mezzi per calcolare le matrici a dispersione per ogni classe e infine le matrici a dispersione viene utilizzata per calcolare una matrice a dispersione combinati all'interno di classe. La matrice all'interno della classe è necessaria per calcolare w.

Dopo aver calcolato w, demo utilizza per stimare la classe per una nuova persona che ha normalizzato age = 4.0 e normalizzati reddito = 5.0. La stima LDA è che la persona che ha un'inclinazione politici libero.

In questo articolo si presuppone che si dispone di almeno intermedi delle competenze di programmazione, ma non si supponga che si conoscono l'algoritmo di classificazione LDA. La demo è codificata tramite c#, ma si dovrebbe essere difficile se si desidera il refactoring del codice in un altro linguaggio, ad esempio Visual Basic .NET o JavaScript.

Informazioni sulla classificazione binaria LDA

Sono illustrati i concetti principali della classificazione binario LDA nei due grafici illustrati nella Figura 2. Il grafico in alto mostra i dati dal programma di dimostrazione. Tre punti blu rappresentano le tre persone che hanno il libero. I cinque punti rossi sono il conservatives. Punto giallo al (4.0, 5.0) rappresenta una persona con inclinazione politici sconosciuto. Anche per questo problema semplice, non è ovvio se utenti sconosciuti devono essere classificata come un libero o un prudente.

Figura 2 LDA stima utilizzando il vettore di stabilire

Si noti che l'unico motivo la demo potrebbero essere inclusa nel grafico dati come illustrato nella Figura 2 è che esistono solo due variabili predittive. Se si sono verificati più di due variabili predittive, non sarebbe possibile visualizzare i dati si adatta così bene in un grafico 2D, ma gli stessi principi LDA applicherebbe. Indipendentemente da quanti predittive variabili sono disponibili in LDA binario, ci saranno due classi. È facile confondere il numero di variabili predittive (due o più) con il numero di valori che la variabile per la stima può richiedere (sempre esattamente due elementi per la classificazione binaria).

La maggior parte degli algoritmi di classificazione binario potrebbero tentare di trovare una riga (tecnicamente vettoriale) che separa in modo esplicito le due classi. Ad esempio, nel grafico superiore Figura 2, è possibile immaginare un ipotetico riga che viene eseguito sulla separazione (3, 9) verso il basso (5, 0). Qualsiasi punto dati sconosciuti sul lato sinistro della linea viene classificata come libero, e qualsiasi punto sul lato destro sarebbe un prudente. LDA funziona in modo completamente diverso.

Il primo passaggio nella LDA è trovare una linea denominata di stabilire. In Figura 2, la riga di stabilire è colorata verde e di stabilire è identificato come (0.868, 0.496). In LDA, la riga stabilire viene sempre identificata da un singolo punto di fine e il punto di partenza è sempre in modo implicito (0, 0,.., 0).

Ma attendere un minuto; l'output del programma demo in Figura 1 indica lo stabilire (-0.868,-0.496) anziché (+0.868, +0.496). Ebbene, è possibile moltiplicare i componenti di stabilire il per qualsiasi costante e non vi sarà alcun effetto sul risultato. Pertanto, per rendere il grafico inferiore in Figura 2 aspetto più accattivante e per illustrare questo concetto importante, ho utilizzato (+0.868, +0.496) per w anziché i valori calcolati effettivi, che sono risultati negativi. In altre parole, entrambi i componenti è moltiplicato per -1.

In altre parole, stabilire il può essere identificato da qualsiasi punto della linea verde in Figura 2, ad esempio -2 * (-0.868,-0.496) = (1.736, 0.992). In LDA, l'approccio standard, ma non da universale, è per la scalabilità di stabilire in modo che abbia lunghezza 1 dall'origine. Si noti che la lunghezza da (0, 0) a (0.868, 0.496) = sqrt ((0 - 0.868) ^ 2 + (0 - 0.496) ^ 2) = sqrt (0.754 + 0.246) = sqrt(1.000) = 1.

Ma qual è l'importanza del vettore di stabilire? In Figura 2, sono disponibili linee tratteggiate nere da ogni punto dati proiettati riga di stabilire, in cui sono perpendicolare per stabilire le linee tratteggiate. Ebbene, stabilire il è una riga, iniziando da (0, 0) che contemporaneamente riduce al minimo la distanza tra i punti previsti per ogni classe e consente di ottimizzare la distanza tra i due gruppi di punti proiettati. Questa idea non è ovvia.

OK, ma anche se è possibile calcolare il vettore di stabilire per un set di dati, è comunque non chiaro lo stabilire come utilizzare per eseguire una stima. In Figura 2, il rombo viola con etichettato "significa" è il punto dati Media indica la due classe. È possibile visualizzare che la media si trova a metà tra i due gruppi di punti dati. Supponiamo ora una linea tratteggiata perpendicolare dalla media viola fino alla riga stabilire verde. Sarebbe accedono a riga di proiezione su (5.2, 3.0).

E supponiamo una linea perpendicolare dal punto di colore giallo per classificare fino alla riga stabilire verde. Poiché la proiezione del punto da classificare scende a sinistra della proiezione dalla media, più si avvicina alle proiezioni dei punti dati libero e pertanto viene classificato come libero. Se la riga di stabilire la proiezione dal punto di sconosciuto era fortemente su altro lato della proiezione dal valore medio, il punto sarebbe sono stato classificato come. Un'idea estremamente intelligente.

Implementazione di classificazione binaria LDA

La struttura generale del programma demo, con pochi WriteLine istruzioni rimosse e minori modifiche per risparmiare spazio, viene presentata in Figura 3. Per creare il programma demo, ho avviato Visual Studio e creato una nuova applicazione console c# denominata LinearDiscriminate. La demo non presenta significativi .NET versione dipendenze in modo che qualsiasi versione di Visual Studio dovrebbe funzionare. Dopo che il codice del modello caricato nell'editor, eliminato tutti utilizzando istruzioni ad eccezione di riferimento singolo per il livello principale dello spazio dei nomi System. Nella finestra Esplora soluzioni è rinominato il file Program.cs in LinearDiscriminateProgram.cs e Visual Studio rinominare automaticamente class Program per me è consentito.

Figura 3 struttura generale del programma Demo

using System;
namespace LinearDiscriminate
{
  class LinearDiscriminateProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin LDA demo");
      // All program control statements here
      Console.WriteLine("End LDA demo");
      Console.ReadLine();
    }
    static int Prediction(double[][] data,
      double[] x, double[][] w) { . . }
    static int Prediction(double[][] data,
      double[][] x, double[][] w) { . . }
    static double[][] Mean(double[][] data,
      int c) { . . }
    static double[][] Discriminate(double[][] data,
      bool unitize) { . . }
    static double[][] ScatterWithin(double[][] data) { . . }
    static double[][] Scatter(double[][] data, int c) { . . }
    static double[][] Unitize(double[][] vector) { . . }
    // Matrix helper methods here
  }
} // ns

Il programma demo è troppo lungo per la presentazione nella sua interezza qui, ma è possibile trovare il codice sorgente completo nel download che accompagna questo articolo. Ho utilizzato un approccio di metodo statico piuttosto che un approccio di programmazione orientata agli oggetti.

Il metodo Main inizia impostando il set di dati di training otto elementi hardcoded in una matrice di matrice di matrici di stile:

double[][] data = new double[8][];
data[0] = new double[] { 1.0, 4.0, 0 };
data[1] = new double[] { 2.0, 2.0, 0 };
// Etc. for [2] through [6]
data[7] = new double[] { 9.0, 8.0, 1 };
ShowMatrix(data, 2, true);

In uno scenario non demo, è necessario leggere dati da un file di testo in memoria utilizzando un metodo denominato qualcosa come LoadData. Il calcolo viene eseguito lo stabilire come segue:

double[][] w = Discriminate(data, true);
Console.WriteLine("Discriminate is: ");
ShowMatrix(w, 6, true);

Si noti che il valore restituito del metodo stabilire è una matrice di matrici di matrici, anziché una matrice. La maggior parte delle operazioni utilizzate LDA sono operazioni di matrice, ad esempio la moltiplicazione e l'inversione di matrice. In questo caso, invece di una matrice con due celle, w è una matrice con due righe e colonne. Tali matrici di una colonna sono talvolta denominate vettori di colonna. A meno che non si utilizzano matrici spesso, può richiedere alcuni minuti per ottenere abituati a lavorare con loro anziché come matrici.

In Figura 1, si noterà che i diversi oggetti intermedi vengono calcolati e visualizzati. Le istruzioni di visualizzazione all'interno di metodo Discriminate e i relativi metodi helper e consentono di comprendere LDA. È probabile che rimuove le istruzioni di visualizzazione nel codice di produzione.

Le istruzioni di impostazione di un elemento per stimare sono:

double[] x = new double[] { 4.0, 5.0 };
Console.WriteLine("Predicting class for Age Income =");
ShowVector(x, 1);

In questo caso, per facilitare il chiamante, per stimare l'elemento si trova in una matrice numerica normale, anche se questa dovrà essere convertito in una matrice di una colonna in un secondo momento. Le istruzioni di stima sono:

int c = Prediction(data, x, w);
Console.Write("Predicted class: " + c);
if (c == 0)
  Console.WriteLine(" (liberal)");
else
  Console.WriteLine(" (conservative)");

Il metodo di stima accetta la matrice di dati per calcolare il Media di mezzi, come illustrato nella Figura 2. Il metodo richiede inoltre l'elemento per la stima, x e il vettore di stabilire, w.

Il calcolo di stabilire

Metodo discriminare calcola il vettore di stabilire LDA. Il codice con istruzioni WriteLine e visualizzazione rimosse, è sorprendentemente breve perché la maggior parte del lavoro viene eseguita dai metodi di supporto:

static double[][] Discriminate(double[][] data, bool unitize)
{
  double[][] mean0 = Mean(data, 0);
  double[][] mean1 = Mean(data, 1);
  double[][] Sw = ScatterWithin(data);
  double[][] SwInv = MatrixInverse(Sw);
  double[][] diff = MatrixSubtract(mean0, mean1);
  double[][] w = MatrixProduct(SwInv, diff);
  if (unitize == true) return Unitize(w);
  else return w;
}

I calcoli matematici dietro il LDA stabilire sono abbastanza complesso, ma i risultati sono piuttosto semplici. Il metodo di supporto media calcola la media di una determinata classe (0 o 1). Ad esempio, i dati di tre elementi che rappresentano il libero (classe 0) sono (1, 4), (2, 2) e (3, 3). È loro Media ((1 + 2 + 3) / 3, (4 + 2 + 3) / 3) = (2.0, 3.0).

La matrice all'interno di separazione è una misura della variabile il set di dati. Con i mezzi di due classi, mean0 e mean1 e all'interno di dispersione matrice Sw a disposizione di stabilire è il prodotto dell'inverso di Sw e la differenza di matrice di mean0 e mean1.

Sono disponibili diverse risorse su Internet che illustrano la matematica piuttosto complessa che deriva l'equazione per stabilire il. Tenere presente che esistono molte versioni diverse di derivazione per w. In particolare, è possibile trovare riferimenti per la covarianza e a dispersione tra (Sb). La covarianza è un'entità matematica è equivalente all'interno di separazione. Tra cui dispersione è un'entità matematica che viene utilizzata per la derivazione dell'equazione per il LDA discriminare ma separazione tra non viene esplicitamente utilizzato per calcolare lo stabilire o eseguire una stima.

Metodo discriminare ha un parametro booleano denominato unitize che indica se scalare la lunghezza di unità, vale a dire una lunghezza uguale a 1.0 stabilire o meno. Nella maggior parte dei casi si desidera passare true come argomento corrispondente.

Eseguire una stima

Il programma demo dispone di due metodi di overload di stima. Il primo accetta l'elemento per la stima, x, come una matrice numerica normale:

static int Prediction(double[][] data, double[] x, double[][] w)
{
  double[][] xm = MatrixFromVector(x);
  return Prediction(data, xm, w);
}

Questa versione di stima è per la chiamata di comodità ed è solo un wrapper per la versione di stima che svolge il lavoro:

static int Prediction(double[][] data, double[][] x, double[][] w)
{
  int dim = data[0].Length - 1; // at least 2
  double[][] wT = MatrixTranspose(w); // 1 x d
  double[][] m0 = Mean(data, 0); // d x 1
  double[][] m1 = Mean(data, 1); // d x 1
  double[][] m = MatrixAdd(m0, m1); // d x 1
  m = MatrixProduct(m, 0.5); // d x 1 
  double[][] tc = MatrixProduct(wT, m); // ((1xd)(dx1) = 1 x 1
  double[][] wTx = MatrixProduct(wT, x); // (1xd)(dx1) = 1 x 1
  if (wTx[0][0] > tc[0][0]) return 0; else return 1;
}

Metodo stima calcola la trasposizione di w affinché possano essere utilizzato nella moltiplicazione di matrici. Vengono calcolati i mezzi per le due classi, quindi la media di questi due metodi è calcolata moltiplicando il valore di ogni componente per 0,5 e quindi archiviata nella matrice m.

Matrice tc è la costante di soglia ed è il prodotto di trasposto del vettore stabilire, wT e la media dei mezzi classe m. Tc matrice sarà sempre una matrice 1 x 1, che contiene un singolo valore. Il valore di matrice tc rappresenta la proiezione della media nel vettore stabilire.

La proiezione di elemento per la stima, x, nello stabilire vettore viene calcolata in modo analogo, come il prodotto di trasposto del vettore di stabilire e x. Purtroppo, poiché la proiezione di stabilire il può essere positivo o negativo, l'operatore di confronto booleano da utilizzare, minore di- o superiore-che variano da un problema a un problema. L'approccio più semplice consiste nel provare maggiore-rispetto e vedere se fornisce risultati significativi. È possibile determinare a livello di programmazione l'operatore da utilizzare, ma tale approccio consente di aggiungere codice molto più di quanto si potrebbe supporre.

Per regolare la proiezione della media dei mezzi classe prendendo in considerazione le probabilità di ogni classe è un'opzione quando si effettua una stima. Questo fattore di rettifica è log(p0 / p1), dove p0 è la probabilità della classe 0 e p1 è la probabilità di classe 1. Per i dati demo, p0 = 3/8 = 0.375 e p1 = 5/8 = 0.625, in modo che il fattore di rettifica log(0.375 / 0.625) = log(0.6) =-0.22. Si noti che se due probabilità si presuppone che siano uguali, quindi p0 = p1 e la regolazione fattore sarebbe log(1) = 0.

Commenti e limitazioni

Esistono effettivamente diverse varianti di LDA. Quello presentato in questo articolo viene in genere chiamato di Fisher LDA. LDA utilizzabili per la funzionalità di selezione (identificazione quali variabili predittive risultano particolarmente utili in modo che possono essere ignorati meno utile eseguire stime), e classificazione. E si noterà che esistono LDA una statistica completamente diverso (latente Dirichlet allocazione) utilizzato nell'elaborazione di linguaggio naturale.

Classificazione binaria LDA è matematicamente elegante, ma presenta diverse limitazioni critiche. Dietro le quinte, versioni diverse di LDA fare ipotesi diverse, ad esempio che le variabili predittive sono in genere distribuito e avere covariances simile. In molti casi questi presupposti non sono true. Anche in questo caso, in pratica, LDA spesso funziona abbastanza bene anche quando non vengono soddisfatti i presupposti di matematica. Un'altra limitazione di matematica è che LDA deve calcolare l'inverso della matrice all'interno di separazione. Inversione di matrice è un processo molto complesso e facilmente può avere esito negativo.

Probabilmente la limitazione principale della classificazione binaria LDA è che presuppone che le due classi sono disponibili in modo lineare. Regime generale, questo significa che quando rappresentare graficamente come in Figura 2, è possibile trovare una linea retta che separa le due classi. I dati per molti problemi non appena separabili in modo lineare.

A mio parere, classificazione binaria LDA è bellissima, ma sono disponibili algoritmi di classificazione alternativo, la regressione logistica particolare classificazione e classificazione di rete neurale, che sono più pratico. Ma è certamente interessante LDA.

---

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

Ringraziano i seguenti esperti tecnici presso Microsoft Research per la revisione dell'articolo: Madison Minsk e Amy Shan