Per il Support Vector Clustering esiste un solo metodo per generare valori pertinenti della larghezza del kernel gaussiano, ed è mostrato in

• bibtex | link
  S. Lee and K. M. Daniels, "Gaussian Kernel Width Generator for Support Vector Clustering," in Advances in Bioinformatics and Its Applications, 2005, pp. 151-162.
  @inproceedings{gauskergenerator2004,
  author = {Sei-Hyung Lee and Karen M. Daniels},
  Booktitle = {Advances in Bioinformatics and Its Applications},
  Date-Added = {2007-10-23 17:21:17 +0200},
  Date-Modified = {2007-10-23 17:21:17 +0200},
  Editor = {Matthew He and Giri Narasimhan and Sergei Petoukhov},
  Keywords = {SVM, clustering, gaussian kernel},
  Pages = {151--162},
  Title = {Gaussian Kernel Width Generator for Support Vector Clustering},
  Url = {http://www.cs.uml.edu/~kdaniels/papers/ICBA.pdf},
  Volume = {8},
  Year = {2005},
  Bdsk-Url-1 = {http://www.cs.uml.edu/~kdaniels/papers/ICBA.pdf}
}

che di seguito indicheremo con GKWG.

Il metodo si basa sullo stesso problema di programmazione quadratica su cui si basa l’SVC stesso, unito a un algoritmo secante.

Gli autori usano questo metodo per generare una lista di valori per la larghezza del kernel prima di eseguire il Support Vector Clustering. Una volta ottenuta la lista, si esegue SVC per ogni valore di quella lista, finché non si raggiunge il criterio di stop.

Gli svantaggi di questo approccio sono due:

• Si rischia di generare una lista di valori più lunga del necessario
• Si aggiunge una complessità non indifferente all’intero processo di clustering, poiché il processo di risoluzione del problema di programmazione quadratica ha una notevole complessità (teoricamente O(N^3), praticamente, tramite SMO Algorithm, O(m*N^2)) e questo viene eseguito una volta per ogni valore di larghezza del kernel generato.

Nel nostro caso, si è riuscito a fondere il processo GKWG con il processo di clustering, sfruttando i calcoli che vengono eseguiti necessariamente per la fase di cluster description dell’SVC. Abbiamo dunque eliminato i due svantaggi precedenti.

Risultati

La nostra implementazione del GKWG porta, oltre a un vantaggio in termini di complessità computazionale totale, anche a risultati migliori di quelli presenti in letteratura, per ora in riferimento soltanto all’IRIS Data Set (vedere esperimenti preliminari SVC).

Si è infatti raggiunta, sull’IRIS completo di tutte le feature, un’accuratezza del 92.6667% (precedentemente ci si era fermati al 90%), grazie al valore di larghezza del kernel ottenuto dal GKWG. Risultati migliori sono stati raggiunti in letteratura soltanto riducendo lo spazio delle feature da 4D a 3D o 2D, tramite PCA o Sammon non linear mapping. Restando invece in 4D, tutti i testi in letteratura ottengono un’accuratezza inferiore alla nostra.

Dettagli del test su IRIS

Total time taken: 0.01 s

Kernel Width: 0.0917017
Number of clusters: 3
Number of non-singleton clusters: 3
Number of singleton clusters: 0
Points per cluster:
Cluster 0: 50
Cluster 1: 55
Cluster 2: 45

Class 0
TP: 50 FP: 0
FN: 0 TN: 100

Precision: 100 – Recall: 100 – F1: 100

Class 1
TP: 47 FP: 8
FN: 3 TN: 92

Precision: 85.4545 – Recall: 94 – F1: 89.5238

Class 2
TP: 42 FP: 3
FN: 8 TN: 97

Precision: 93.3333 – Recall: 84 – F1: 88.4211

Macroaveraging: 92.6483
Accuracy: 92.6667