Utilisation des méthodes Support Vector Machine (SVM) dans

Utilisation des methodes Support VectorMachine (SVM) dans l’analyse des bases de

donnees

Abdelhamid DJEFFAL

Encadre par: M.C. BABAHENINICo-Encadre par: A. TALEB-AHMED

Departement d’informatique, Laboratoire LESIAUniversite de Biskra

Mai 2012

Problematique Data mining SVM SVM & analyse des BDD Contributions Conclusion

1 Problematique

2 Data mining

4 SVM & analyse des BDD

5 ContributionsAcceleration des SVMs par reduction d’exemplesSVM multiclasse acceleree a base de OC-SVMApplications

6 Conclusion

Outline

1 Problematique

2 Data mining

6 Conclusion

Motivations de la these

MotivationsLe developpement du data mining et utilisation dans lesgrand SGBDLe developpement des SVMs et leurs applications dansplusieurs domainesLe developpement continu des volumes des BDDsInsuffisances et lacunes des techniques de data mining

PropositionUtilisation des SVMs pour l’analyse des BDD

ContraintesDans quel niveau d’analyse ?Pour quelles taches ?Que faire face aux specificites des BDD ?Quelles adaptations pour les SVMs ?Comment assurer la scalabilite ?

Outline

1 Problematique

2 Data mining

6 Conclusion

Definition

Data mining

DefinitionData mining, Fouilles de donnees , ECDUtilisation des techniques de: statistiques, IA,Optimisation, ...Pour decouvrir les modeles, les relations, les regles, lesmotifs, les patterns, ... qui se cachent dans les grandesquantites de donnees,Pour comprendre, aider a la decision, optimiser, ameliorer,...Dans les banques, les laboratoires, les supermarches, leshopitaux, ...

Definition

Data mining

Definition

Data mining

Definition

Data mining

Definition

Data mining

Definition

Data mining

Processus

Processus de data mining

Analyse du problème

Collecte des données

BDD originales BDD initiales

BDD préparées

Préparation des données

Fouille de données

Modèles/patterns Motifs

Evaluation

Connaissances

Déploiement

Taches

Data mining

Taches de data miningClassification,Regression,Clustering,Renforcement,Recherche des motifs frequents et des reglesd’association,Visualisation,...

Taches

Data mining

Taches

Data mining

Taches

Data mining

Taches

Data mining

Taches

Data mining

Taches

Data mining

Taches

Data mining

Outline

1 Problematique

2 Data mining

6 Conclusion

Principe

Introduction

Support vector machinesUne methode d’apprentissage statistique due a Vladimir Vapnik

Principe

Classification binaire:yi = ±1Rechercher un hyperplande separation: w • x + b = 0Qui maximise la marge:

2‖w‖2

Principe

Introduction

Principe

2‖w‖2

Principe

Introduction

Principe

2‖w‖2

Principe

Introduction

Principe

2‖w‖2

Principe

Introduction

Principe

Resoudre l’equation:Minimiser 1

2 ‖w‖2 + C

n∑i=1

Avec yi(wT xi + b) ≥ 1− ξi ; i = 1..nξi ≥ 0

Principe

Introduction

SolutionIntroduire les multiplicateurs de Lagrange αi

Minimiser 12

n∑i=1

n∑j=1

αiαjyiyj⟨xi , xj

⟩−

n∑i=1

Avecn∑

i=1αiyi = 0

0 ≤ αi ≤ C

La fonction de decision est: H(x) =n∑

i=1αiyi 〈xi , x〉+ b

Principe

Introduction

SolutionIntroduire les multiplicateurs de Lagrange αi

Minimiser 12

n∑i=1

n∑j=1

αiαjyiyj⟨xi , xj

⟩−

n∑i=1

Avecn∑

i=1αiyi = 0

0 ≤ αi ≤ C

i=1αiyi 〈xi , x〉+ b

Principe

Utilisation des noyaux

Espace original Espace de caractéristiques

Espace original

Principe

Noyau (Kernel)La transformation et son inverse sont calculees par unefonction reelle appelee Noyau K (xi , xj)

Lineaire: K (xi , xj) = xTi xj

Polynomial: K (xi , xj) = (xTi xj)

Gaussien: K (xi , xj) = e

(−‖xi−xj‖2

Principe

(−‖xi−xj‖2

Principe

(−‖xi−xj‖2

Principe

(−‖xi−xj‖2

Principe

(−‖xi−xj‖2

Principe

Le probleme dual a resoudre devient:Minimiser 1

n∑i=1

n∑j=1

αiαjyiyjK (xi , xj)−n∑

i=1αi

Avecn∑

i=1αiyi = 0

0 ≤ αi ≤ C

i=1αiyiK (xi , x) + b

Implementation

OptimisationHeuristiquesSMO (Platt et al. 97)Optimiser a chaque iteration deux αi

Plusieurs packages: SVMlight, SVMTORCH, LibSVM ...Complexite O(MN2)

Probleme avec les grands ensembles de donnees

Implementation

Architecture

Vecteur x à tester

Vecteurs supports x1..xs

Fonction noyau K

Multiplicateurs

Fonction de décision

1 si f >0

autre sinon

K(x2,x) K(x1,x

K(xi,xj) K(xs,x) … K(xs-1,x)

𝑓𝑓 = �αiyiK(xi, x) + 𝑏𝑏

α1 α2 αs-1 αs

K(x1,x)

Décision Décision

Variantes

SVM Multiclasse

H14 H23

{1,2,3,4}

{2,3,4} {1, 3,4}

Ecarter 2 Ecarter 1

Ecarter 3 Ecarter 4

H24 H34 H13

Ecarter 3 Ecarter 2

{2,4} {3,4}

Ecarter 2

Ecarter 4 Ecarter 1

Ecarter 1

{1, 3}

Ecarter 3

Ecarter 4

X2 Classe 1

Classe 2

Classe 3

H23(x)

H12(x)

H 13(x)

X2 Classe 1

Classe 2

Classe 3

1 Vs Reste 1 Vs 1

Variantes

SVM Monoclasse (Novelty detection)

Classe cible

Origine

Variantes

SVM pour la regression (SVR)

y = wx + b y

φ φ-1

Espace original Espace de caractéristiques Espace original

Variantes

SVM pour le clustering (SVC)

Variantes

SVM pour le renforcement (Transductive)

Hyperplan sans renforcement

Hyperplan avec renforcement 15

Evaluation

Evaluation des SVMs

Technique d’evaluationHold Out (partie training + partie test)N Cross Validation (Leave One Out),Bootstrap (choix aleatoire des exemples d’entrainement).

Evaluation

Evaluation des SVMs

Evaluation

Evaluation des SVMs

Evaluation

Evaluation des SVMs

Outline

1 Problematique

2 Data mining

6 Conclusion

Ou sont utilisees les BDDs

Bases de données

Images Son Web Textes …

Extraction des caractéristiques

Entrepôt de données (bases de données)

Analyse

Connaissances (bases de données)

Acquisition

Extraction des connaissances

Visualisation et intégration

Acquisition

Utilisation des SVMs pour l’acquisition

Preparation des BDDsLissage (SVR): elimination du bruit au niveau des attributs,Nettoyage (SVM, OCSVM, SVC): detection des exempleserrones, elimination des doublons, elimination des outliers,Reduction verticale (SVM): eliminations successives desattributs,Reduction Horizontale (OC-SVM, Multiclasse):eliminations des exemples redondants et de faibleimportance.

Acquisition

Utilisation des SVMs pour l’Extraction desconnaissances

Extraction des connaissancesClassification (mono, bi et multiclasse),Regression (SVR),Clustering (SVC)Renforcement (Transductive SVM)

Problemes d’utilisation des SVMs

Problemes

Attributs symboliquesUtilisation des noyaux symboliques (text mining)

Sac de motsp-spectrum,All Sub Sequences,...

Nombre eleve d’enregistrementUtilisation des techniques d’acceleration

SVM online,Parallelisation,Reduction d’exemples (contribution 1),Techniques d’acceleration (contribution 2).

Problemes

Integration des SVMs dans les SGBDUtiliser les outils SGBDs dans l’entrainement des SVMs,Utiliser le jargon SGBD (SQL, PL) pour l’utilisation desSVMs,Exemple d’Oracle.

Outline

1 Problematique

2 Data mining

6 Conclusion

Acceleration des SVMs par reduction d’exemples

Contribution 1: CB-SR

Observations1 Les vecteurs non support

n’ont aucune influence surl’hyperplan,

2 Selon V.Vapnik, les vecteurssupports representent 10%des exemples.

IdeeDecouvrir ces vecteurs et lesutiliser seuls pour l’apprentissage

Travaux anterieurs sur la reduction d’exemplesLiu & Feng, 2008Kernel Bisecting k-means clusteringA. Arslan, 2008Clustering k-NNLin &. Yeh, 2009Reduction basee sur les algorithmes genetiques

Covering Based Samples Reduction

FiltrageDetecter les vecteurssupports potentiels par deshyperplans locaux

RevisionRajouter les exempleseventuellement ecartes parerreur.

Filtrage

Zone de couvertureLa zone de couverture de xi par rapporta xk = Zone delimitee par H+

ik et H−ik :xj / −1 ≤ Hik (xj) ≤ 1

Couverturexi ∈ yi(±1) est couvert par xj ∈ yi parrapport a xk ∈ yk = −yi si xj se situedans la zone de couverture de xi parrapport a xk . mais ...

Zone de couverture de xi

par rapport à xk

Hik=-1

Hik=+1

Classe + Classe -

Filtrage

Zone de couvertureLa zone de couverture de xi par rapporta xk = Zone delimitee par H+

ik et H−ik :xj / −1 ≤ Hik (xj) ≤ 1

Couverturexi ∈ yi(±1) est couvert par xj ∈ yi parrapport a xk ∈ yk = −yi si xj se situedans la zone de couverture de xi parrapport a xk . mais ...

par rapport à xk

Hik=-1

Hik=+1

Classe + Classe -

Filtrage

Couverture mutuelleOn dit que xi et xj ∈ yi(±1) sontmutuellement couvert par rapport axk ∈ yk = −yi si chacun se situe dans lazone de couverture de l’autre.

Couverturexi ∈ yi(±1) est couvert par xj ∈ yi parrapport a xk ∈ yk = −yi si xj se situedans la zone de couverture de xi parrapport a xk et xi ne se situe pas dans lazone de couverture de xj par rapport a xk

Couverture de xi

par rapport à xk

Couverture de xj

par rapport à xk

Hik=-1

Hjk=-1

Hjk=+1

Hik=+1

Classe - Classe + X2

Filtrage

Couverture mutuelleOn dit que xi et xj ∈ yi(±1) sontmutuellement couvert par rapport axk ∈ yk = −yi si chacun se situe dans lazone de couverture de l’autre.

Couverturexi ∈ yi(±1) est couvert par xj ∈ yi parrapport a xk ∈ yk = −yi si xj se situedans la zone de couverture de xi parrapport a xk et xi ne se situe pas dans lazone de couverture de xj par rapport a xk

Couverture de xi

par rapport à xk

Couverture de xj

par rapport à xk

Hik=-1

Hjk=-1

Hjk=+1

Hik=+1

Classe - Classe + X2

Filtrage

Couverture totaleOn dit qu’un exemple xi d’une classe yi(±1) est totalementcouvert par rapport a la classe −yi , si pour tout exemple xk dela classe −yi , il existe un exemple xj de la classe yi qui couvrexi par rapport a xk :∃ xj non ecarte ∈ N+/(−1 ≤ Hik (xj) ≤ 1) et (−1 > Hjk (xi) ouHjk (xi) > 1)

FiltrageEcarter tous les exemples totalement couverts.

Filtrage

Couverture totaleOn dit qu’un exemple xi d’une classe yi(±1) est totalementcouvert par rapport a la classe −yi , si pour tout exemple xk dela classe −yi , il existe un exemple xj de la classe yi qui couvrexi par rapport a xk :∃ xj non ecarte ∈ N+/(−1 ≤ Hik (xj) ≤ 1) et (−1 > Hjk (xi) ouHjk (xi) > 1)

FiltrageEcarter tous les exemples totalement couverts.

Filtrage

Exemple recapitulatif

Filtrage

Tuning

Utilisation du parametre ρ

par rapport à xk

Hik=-1

Hik=+1

Classe + Classe -

Tuning

Effet: controle du taux de filtrage

Revision

Rajouter les exemples ecartes par erreurs

Pas toujoursUniquement si le taux de reconnaissance de l’hyperplan obtenun’est pas satisfaisant

Sources d’erreurs1 Le filtrage (ρ, noyau et ses parametres)2 L’apprentissage (noyau et ses parametres, C,

Optimisation: heuristiques et critere d’arret)

ResultatEcarter des vecteurs supports potentiels

Revision

Utiliser les conditions KKT: (Karush-Kuhn-Tucker)αi = 0⇒ yi f (xi) > 1 : exemples bien classesαi = C ⇒ yi f (xi) ≤ 1 : exemples mal classes0 < αi < C ⇒ yi f (xi) = 1 : vecteurs supports

Revision

Etapes de la revision1 Utiliser l’hyperplan obtenu dans la phase de filtrage,2 Mettre les αi des exemples ecartes a 0,3 Verifier les conditions KKT pour ces exemples,4 Ajouter les exemples qui ne verifient pas les conditions

KKT a l’ensembles des exemples filtres,5 Recommencer un nouvel apprentissage en demarrant de

l’hyperplan precedent (valeurs precedentes des αi )

ResultatObtenir un hyperplan final

Revision

Donnees utilisees pour les tests

Tests sur:1 Des donnees artificielles: type Toy2 Des donnees reelles du cite UCI

Tables

Table NAtt N NEntr NTestGermen 24 1000 500 500Diabetes 8 768 384 384Tow Spiras 2 3000 300 2700Tow Ellipses 2 3000 300 2700Cancer Analysis 32 596 596 596Segmentation 19 2309 2309 2309

Tables

Evaluation

Parametres d’evaluation1 Nombre d’exemples maintenus apres filtrage2 Temps d’apprentissage a bases des exemples maintenus3 Taux de reconnaissances

Comparer avec1 KBK-SR (Kernel Bisecting k-means Clustering) [Liu &

Feng, 2008]2 Methode de Lin [Lin &. Yeh, 2009]

Evaluation

Resultats

Resultats sur des toys

SVM seule apres Filtrage

N T(s) R(%) N T(s) R(%)1169 432.656 100 471 60.516 99,65

Resultats

SVM seule apres Filtrage et Revision

N T(s) R(%) N T(s) R(%)1169 432.656 100 679 93.268 100

Resultats

Resultats sur des BDDs du cite UCI

Base de test Methode N ρ T(s) R(%)German SVM 500 / 501.375 72.8

KBK-SR 156 / 60.42 70.83CB-SR 3 0.95 0.578 72.8

Tow Spirals SVM 300 / 10.687 100Lin 92 / / 99.95

CB-SR 37 0.86 0.875 100Tow Ellipses SVM 300 / 12.395 100

Lin 39 / / 100CB-SR 12 0.79 0.126 100

Segmentation SVM 2309 / 84.61 100CB-SR 32 / 0.937 100

SVM multiclasse acceleree a base de OC-SVM

Contribution 2: OCBM

Large utilisation de la variante multiclasseLa plupart des applications reelles utilisent la SVM multiclasse

OCR,Reconnaissance des caracteres manuscrits,Reconnaissance visages humains, ...

Lenteur des SVM multiclasse utilisees1vsR1vs1, DAGArbres de decisions, ...

Travaux anterieurs (HvsH: Han-sheng & al, 2005)

ABC vs DEF

A vs BC DE vs F

B vs C D vs E

C DB E

Travaux anterieurs (OC-SVM:Yang & al, 2007)

Travaux anterieurs (R-1vsR: Arun & al, 2010)

Reduced-1vsRPour chaque hyperplan: utiliser les exemples restants et lesvecteurs supports precedents

Travaux anterieurs (ODT-SVM: Agrawal & al, 2011)

Classe 1

Classe 2

Classe 3

Classe 4 1vs(2,3,4)

2vs(3,4) classe1

Classe2

Classe3 Classe4

Principe

Utiliser le OC-SVM avec renforcement de la precisionPrendre un hyperplan mono classe pour chaque classeCalculer des decalages pour renforcer la precisionUtiliser le principe de maximum de profondeur

Principe

𝒙𝒙𝒌𝒌−

𝒙𝒙≠𝒌𝒌−

Hyperplan OC-SVM Hyperplan décalé

Classe K (cible)

Les autres classes ≠ K

𝑯𝑯𝒌𝒌

𝑯𝑯𝒅𝒅𝒌𝒌

𝑯𝑯(𝒙𝒙≠𝒌𝒌− ) 𝑯𝑯(𝒙𝒙𝒌𝒌−)

Principe

Classe 1 Classe 2

Classe 3

Classe 4

Classe 1 Classe 2

Classe 3

Classe 4

Classe 1 Classe 2

Classe 3

Classe 4

OC-SVM Décalages

Maximum de profondeur

Evaluation

Parametres d’evaluation1 Temps d’apprentissage,2 Temps de classification,3 Taille du modele obtenu,4 Taux de reconnaissance

Comparer avec1 1vsR, 1vs1, DAG2 HvsH (Han-sheng & all, 2005)3 OC-SVM (Yang & all, 2007)4 R-1vsR (Arun & all, 2010)5 ODT-SVM (Agrawal & all, 2011)

Evaluation

Analyse de complexite

SoitK : nombre de classesNc : Nombre d’exemple par classeβ: constante relative aux conditions d’executionδ:nombre d’octets necessaires au stockage d’une valeurd’un attribut

Exemple d’applicationK = 10, Nc = 20, β = 1, δ = 1

Temps d’entrainement

Methode # hyperplans Temps estime Exemple1vsR K K 3βN2

c 4000001vs1 K (K − 1)/2 2βK 2N2

c 80000ODT K − 1 K 3

3 βN2c 27000

HvsH 2log2K − 1 2βK 2N2c 80000

R-SVM K K 3

3 βN2c 27000

OC K KβN2c 4000

OCBM K KβN2c 4000

Temps de classification

Methode # hyperplans Temps estime Exemple1vsR K K 2βNc 20001vs1 K (K − 1)/2 K (K − 1)βNc 1800DAG (K − 1) 2(K − 1)βNc 360ODT K − 1 (K (K+1)

2 − 1)βNc 1080HvsH log2K 2KβNc 400

R-1vsR K ODT 1080OC-SVM K KβNc 200OCBM K KβNc 200

Taille du modele

Methode # hyperplans Taille estime Exemple1vsR K 2K 2δNc + K δ 40101vs1 K (K − 1)/2 K (K − 1)(2Nc + δ

2) 3600ODT K − 1 2(K (K+1)

2 − 1)δNc 1769HAH 2log2K − 1 2Klog2(K )δNc 1409R-1vsR K ODT-SVM 1769OC K K δ(Nc + 2) 220OCBM K K δ(Nc + 2) 220

1vs1 DAG

Te(s) Tt (s) R(%) T(KB) Te(s) Tt (s) R(%) T(KB)343.5 644.2 100 302.5 343.5 152.3 100 302.5

1vsR OCBM-SVM

Te(s) Tt (s) R(%) T(KB) Te(s) Tt (s) R(%) T(KB)546 454.3 100 209.5 0.656 132.5 100 60.2

Resultats sur des BDDS UCI

Base ODT HvsH R-1vsR OC OCBMIris 98 100 / 90.67 100Scc / 99.44 / / 93.88Glass 77.57 / / 71.03 99.53Wine 98.98 / / 54.49 100Yeast 68.65 / / / 99.93PenDigits / 98.37 98.82 / 98.01SatImage 93.98 / 91.9 / 94.2

Avantages de la methode OCBM par rapport aux autresAccelere l’entrainement,Accelere la classification,Reduit la taille du modele,Tout en preservant la precision.

Applications

Calculatrice vocale

Speech audio

Traitement de signal et extraction des

coefficients

Classification des nouvelles entrées

Calculatrice

Création du profile du locuteur

Base de données des profiles

Vecteurs

Mot (chiffre ou opération)

Apprentissage

Prononciation du résultat

Validation du résultat par l’utilisateur

Applications

Trieuse des dattes

Construction d’une base d’apprentissage

Apprentissage par SVM

Prétraitements

Extraction des caractéristiques

Vecteur de caractéristiques

Classes

Modèle de décision

Classification par SVM

Classe

Apprentissage Classification

Applications

Reconnaissance des caracteres manuscrits arabes

Prétraitement, segmentation et extraction de caractéristiques

Post-traitement

Image brute

Résultat final كتـاب

Interfaces Acquisition

Base de modèles

Classification Apprentissage SVM Vecteurs

té i ti

Outline

1 Problematique

2 Data mining

6 Conclusion

Conclusion & perspectives

Bilan1 Etude de l’utilisabilite des SVMs pour l’analyse des BDD2 Contributions

CB-SR: technique d’acceleration des SVMs binaires parreduction d’exemplesOCBM: technique d’acceleration des SVMs multiclassespar OC-SVM

3 ApplicationsCalculatrice vocale a base des SVMsTrieuse des dattes a base des SVMsReconnaissance des caracteres manuscrits arabes parSVMs

Resultats4 publications internationales,10 communications nationales et internationales

Nos travaux futursUtiliser le principe CB-SR pour le multi et le mono classe etla regression,Etudier le calcul de ρ a partir des donnees,Etudier le parametre v pour la methode OCBM,Etudier le decalage,SVC

Nos projetsPNR (fraude bancaire, CRM, credit scoring, ...)CNEPRU (Segmentation d’images par SVC, ...)CMEP (Optimisation du positionnement des cameras)

Fin de l’expose

Merci pour votre attention ...

Utilisation des méthodes Support Vector Machine (SVM) dans

Documents

Presentation My Vector

SVM Mac N245 - Janvier-Fevrier 2012

Vector 2 et Vector 2S - Garminstatic.garmin.com/pumac/Vector_2_OM_FR.pdf · 2015-07-13 · Vector. ou le . Vector S. Ce manuel couvre les deux systèmes Vector . Le . Vector a été

Plan de l’exposé - Machine Learning Thoughtsml.typepad.com/Talks/Machine_Learning_CAP.pdf · SVM, noyaux, régularisation quelques idées récentes en Machine Learning 30 mai 2005

Multicategory Support Vector Machines: Theory and ...pages.stat.wisc.edu/~wahba/ftp1/lee.lin.wahba.04.pdf · Multicategory Support Vector Machines: Theory and Application to the Classi”

10 97 RAY-VECTOR - rosemex.com · ray-vector cabinet mural continu produits rosemex chauffage hydronique chauffage 10 97

MICROMASTER Vector MIDIMASTER Vector · Le MICROMASTER Vector (MMV) et le MIDIMASTER Vector (MDV) constituent une gamme standard de ... • Capacité de surcharge de 200% pour 3s

Lyme Borreliosis Spirochete and its Tick Vector · 2013-02-08 · Lyme Borreliosis Spirochete and its Tick Vector Relationship of protein expression, antigenicity and pathogenicity

Vector 2 et Vector 2S - static.garmincdn.comstatic.garmincdn.com/pumac/Vector_2_OM_FR.pdf · Edge Instructions concernant les appareils 810 et 510 ... l'axe de pédale et la manivelle

Svm 156-m2606-dream-

Support Vector Machines Présenté par : BEKHELIFI Okba

Credit Card Fraud Identification Using Machine Learningbudi.rahardjo.id/files/...Makalah_Andre_Juliantama.pdf · and fraud catching rate as compared to SVM and Naïve Bayes Classifier

Vector Biology and Malaria Transmission in Southeast Asia

Multi-Dimension Support Vector Machine Based Crowd Detection … · Machine Based Crowd Detection and Localisation Framework for Varying Video Sequences Manoharan Mahalakshmi , Radhakrishnan

Atlas of Mexican Triatominae (Reduviidae: Hemiptera) and vector transmission … · 2015-07-08 · Atlas of Mexican Triatominae (Reduviidae: Hemiptera) and vector transmission of

MENGGUNAKAN SUPPORT VECTOR MACHINE DENGAN PARTICLE …

CHALLENGE 2018 - chemom2018.sciencesconf.org · Méthode SVM –Support Vector Machine Régression non linéaire Alexander Statnikov, Douglas Hardin, Isabelle Guyon, Constantin F

Le Chariot SVM systèmes de caméras et

Vector et Vector S · 2014-10-01 · Ce manuel couvre les deux systèmes Vector . Le Vector a été conçu pour les cyclistes, par des cyclistes, afin qu'ils bénéficient d'un système

générateur pwm svm triphasé pour moteur bldc schémas et