SVM Classifier – a comprehensive java interface for support vector machine classification of microarray data (Italiano)

Abbiamo sviluppato una semplice interfaccia grafica per la nostra implementazione dell’algoritmo SVM, chiamata SVM Classifier. Questa interfaccia permette agli utenti inesperti di scaricare il software per l’installazione locale e applicare facilmente un sofisticato algoritmo di apprendimento automatico ai loro dati. Abbiamo implementato un’applicazione accessibile al pubblico che permette agli utenti SVM di eseguire l’addestramento SVM, la classificazione e la predizione. Per i dettagli sull’uso del software, il dataset di esempio e le spiegazioni degli algoritmi sottostanti, rimandiamo i lettori al sito web e ai riferimenti ivi elencati. Gli utenti di SVM potrebbero anche essere interessati a una serie di altre implementazioni SVM su licenza che sono state descritte in precedenza, tra cui LIBSVM .

Abbiamo usato gli algoritmi SVM implementati dal team Libsvm , come nucleo. Al fine di massimizzare la compatibilità multipiattaforma SVM Classifier è implementato in java utilizzando le librerie standard swing (Figura 1).

L’open source, multipiattaforma Apache Ant, e l’edizione gratuita di Borland JBuilder 2005 Foundation sono usati come strumenti di costruzione. Anche se sviluppato su WinXP, SVM Classifier è stato testato con successo su Linux e altre piattaforme Windows, e funzionerà su Mac OS9 con l’estensione Swing. Gli utenti sono in grado di eseguire SVM Classifier su qualsiasi computer con java 1.4 runtime o versione superiore.

L’applicazione ha due frame, quello di classificazione e quello di predizione. In entrambi i frame il formato dei file di dati può essere importato come “Labeled” o come “Delimited” (Figura 2 e Figura 3).

Nel frame di classificazione l’utente creerà un modello dal dataset di allenamento per la classificazione (C-SVC, nu-SVC), regressione (epsilon-SVR, nu-SVR), e stima della distribuzione.

In questo frame l’utente è in grado di importare il dataset di allenamento nell’applicazione, selezionare il percorso per salvare il file del modello, selezionare il tipo appropriato di SVM e kernel e creare un modello per il dataset. Il file del modello può essere utilizzato in seguito per la predizione. C’è anche una scelta per la convalida incrociata. La tecnica di convalida incrociata (CV) è usata per stimare l’accuratezza di ogni combinazione di parametri nell’intervallo specificato e ci aiuta a decidere i migliori parametri per il problema della classificazione.

Nel quadro di predizione il modello sarà applicato ai dati di test per prevedere la classificazione dei dati sconosciuti. Abbiamo anche fornito uno strumento per la visualizzazione dei dati bidimensionali a cui si può accedere dalla barra del menu di visualizzazione (Figura 4).

Tipi di kernel

K(x i , x j ) = Φ(x i )TΦ(x j ) è chiamata funzione kernel. Qui i vettori di addestramento x i sono mappati in uno spazio dimensionale superiore (probabilmente infinito) dalla funzione Φ. Ci sono i seguenti quattro kernel di base: lineare, polinomiale, funzione di base radiale (RBF), e sigmoide:

1. Lineare: K(x i , x j ) = x i Tx j

2. Polinomiale: Il kernel polinomiale di grado d è della forma

K(x i , x j ) = (x i , x j )d

1. RBF: Il kernel gaussiano, noto anche come funzione a base radiale, ha la forma

Dove σ indica la larghezza della finestra

1. Sigmoide: Il kernel sigmoide è della forma

K(x i , x j ) = tanh(k(x i x j ) + ϑ)

Quando il kernel sigmoide è usato con la SVM si può considerare come una rete neurale a due strati.

Tipi di SVM

1. C-SVC: C-Support Vector Classification (caso binario)

Dato un set di allenamento di coppie istanza-etichetta (x i , y i ), i = 1,…,l dove x i ∈ Rn e y ∈ {1, -1}l, ←le macchine vettoriali di supporto (SVM) richiedono la soluzione del seguente problema di ottimizzazione:

SVM trova un iperpiano di separazione lineare con il margine massimo in questo spazio dimensionale superiore. C > 0 è il parametro di penalità del termine di errore. La funzione di decisione è:

2. nu-SVC: Classificazione a vettori di supporto ν (caso binario)

Il parametro ν ∈ (0, 1) è un limite superiore della frazione di errori di addestramento e un limite inferiore della frazione di vettori di supporto. Dati i vettori di addestramento x i ∈ Rn, i = 1,…,l, in due classi, e un vettore y ∈ Rls tale che y i ∈ {1, -1}, la forma primaria considerata è:

E la funzione di decisione è:

3. epsilon-SVR: ε-Support Vector Regression (ε-SVR)

Una estensione dell’SVM è quella per il compito di regressione. Un problema di regressione è dato ogni volta che Y = ℝ per l’insieme di dati di allenamento Z = {(x i , y i ) ∈ X × Y | i = 1,…,M} e il nostro interesse è trovare una funzione della forma f: X → RD. La formulazione primaria per l’SVR è quindi data da:

Dobbiamo introdurre due tipi di variabili slack ξ i e , una per controllare l’errore indotto dalle osservazioni che sono più grandi del limite superiore del tubo ε, e l’altra per le osservazioni più piccole del limite inferiore. La funzione approssimata è:

4. nu-SVR: ν-Support Vector Regression (ν-SVR)

Simile a ν-SVC, per la regressione, usa un parametro ν per controllare il numero di vettori di supporto. Tuttavia, a differenza di ν-SVC dove C è sostituito da ν qui ν sostituisce il parametro ε di ε-SVR. Quindi la funzione di decisione è la stessa di quella di ε-SVR.

5. SVM a una classe: stima della distribuzione

La differenza della classificazione a una classe dal problema di classificazione standard è che i dati di formazione non sono distribuiti in modo identico ai dati di test. Il set di dati contiene due classi: una di esse, la classe target, è ben campionata, mentre l’altra classe è assente o campionata molto scarsamente. Schölkopf et al. hanno proposto un approccio in cui la classe target è separata dall’origine da un iperpiano. La forma primaria considerata è:

E la funzione di decisione è:

Convalida incrociata

L’obiettivo di utilizzare la convalida incrociata è quello di identificare buoni parametri in modo che il classificatore possa prevedere accuratamente i dati sconosciuti.

Un modo comune è quello di separare i dati di allenamento in due parti, una delle quali è considerata sconosciuta nell’addestramento del classificatore. Quindi l’accuratezza della predizione su questo set può riflettere più precisamente la performance sulla classificazione dei dati sconosciuti. Una versione migliorata di questa procedura è la convalida incrociata.

Nella convalida incrociata v-fold, l’insieme di allenamento è diviso in v sottoinsiemi di uguale dimensione. Sequenzialmente un sottoinsieme viene testato usando il classificatore addestrato sui restanti v – 1 sottoinsiemi. Così, ogni istanza dell’intero set di addestramento viene predetta una volta, quindi l’accuratezza della convalida incrociata è la percentuale di dati che sono classificati correttamente. La procedura di convalida incrociata può prevenire il problema dell’overfitting.

Riduzione

Chang e Lin hanno menzionato che poiché per molti problemi il numero di vettori di supporto liberi (cioè 0 <α i < C) è piccolo, la tecnica di shrinking riduce la dimensione del problema di lavoro senza considerare alcune variabili vincolate .

Caching

Caching è un’altra tecnica per ridurre il tempo di calcolo. Poiché Q (Q è una matrice semi definita positiva l per l, Q ij = y i y j K(x i , x j )) è completamente denso e può non essere memorizzato nella memoria del computer, gli elementi Qij sono calcolati come necessario. Di solito una memoria speciale che utilizza l’idea di una cache viene utilizzata per memorizzare i Qij usati di recente.