DEA PTI Perception et Traitement de l’Information

  • Published on
    20-Jan-2016

  • View
    31

  • Download
    2

DESCRIPTION

DEA PTI Perception et Traitement de lInformation. Reconnaissance des formes Les mthodes base de noyaux S. Canu http://psichaud.insa-rouen.fr/~scanu/RdF. Buts de la RdF. D : Algorithme de Reconnaissance des Formes. Cest la forme y=D(x) . Une forme x (vecteur forme - PowerPoint PPT Presentation

Transcript

DEA PTI Perception et Traitement de lInformationReconnaissance des formesLes mthodes base de noyauxS. Canuhttp://psichaud.insa-rouen.fr/~scanu/RdFButs de la RdFD : Algorithme de Reconnaissancedes FormesUne forme x(vecteur formedes caractristiques)Cest la formey=D(x) Nous voulons un algorithme de RdF performantRdF et apprentissageD : Algorithme de Reconnaissancedes FormesUne forme x(vecteur formedes caractristiques)Cest la formey=D(x) A : Algorithme dapprentissageEnsemble dapprentissage (chantillon)A priorisur lanature de la solution23Les problmesLes mthodes base de NoyauCe qui se ressemble sassemble=zone dinfluence dun exempleEnsemble dapprentissage (chantillon)si x ressemble un xi, il aura ltiquette yi Zone dinfluenceDfinition : Si d(x,xi) < b x appartient la zone dinfluence du point xibRgle de dcisionDfinition : 1-Si x appartient la zone dinfluence dun seul point xi, alors il a ltiquette yi2-Si x appartient la zone dinfluence de plusieurs points de mme tiquette, alors il a cette tiquette3-Si x appartient la zone dinfluence de plusieurs point dtiquette diffrentes, alors il y a rejet dambiguit4-Si x appartient la zone dinfluence daucun point, alors il y a rejet de distance12344bMise en uvrefor i = 1:n d(i) = norm((x-xi(i,:))/b);endind = find(d>seuil); b caractrise la zone dinfluence dun pointPour b grandLa zone dambigut est trop importantePour b plus petitLa zone de rejet de distance est trop importanteil faut cumuler les influencesxxNoyauDistance de la forme x toutes les forme de lensemble dapprentissageOn peut aussi modifier la zone dinfluence dun pointau lieu davoir uniquement une influence de type tout ou rienon peut imaginer de nombreuses autres manires dont un point influence les autres : par exemple : NoyauFrontire de dcisiond(x)=0d(x)=0Classe 1Classe 2Noyau matlabd = 0for i = 1:n d = d + yi(i)*exp(-(norm(xi(i,:)-x).^2)/b);endD=sign(d); Avec rejet d(x) est petit si x est loin des xi ou si les rouges et les bleus se compensentrejet de distance et rejet dambigut ?????Frontire de dcisiond(x)=rClasse 1Classe 2d(x)=-rrejetNoyaux avec rejetsEst-ce une bonne ide ?Comment interprter d ?Comment choisir G ?Comment choisir b ?Comment choisir les seuils ?Classe 1Classe 2Rejet de distanceRejet dambigutEst-ce une bonne ide ? Oui si cest universellement consistantComment choisir G : Autres noyauxExemples de noyauxNoyaux positifs et les autresUniversellement consistantDfinition : un noyau G est dit rgulier si il est non ngatif il existe une boule contre B de rayon r et une constante k telle que : Thorme :Erreur de notre rgleErreur de BayesComment interprter le rgle de dcision ? Estimation de densit par des noyauxFentres de ParzenConsistance universelleStratgie de RdF : Cest la rgle du MAPDiscrimination avec les noyau de Parzen : rgle du MAP (3 classes)d1 = 0; d2 = 0; d3 = 0;for i = 1:n if(yi(i)=1); d1 = d1 + exp(-(norm(xi(i,:)-x).^2)/b); end; % Vraisemblance if(yi(i)=2); d2 = d2 + exp(-(norm(xi(i,:)-x).^2)/b); end; if(yi(i)=3); d3 = d3 + exp(-(norm(xi(i,:)-x).^2)/b); end;endpc1=length(x1); pc2=length(x2); pc3=length(x3);nt = pc1+pc2+pc3;pc1=pc1/nt; pc2=pc2/nt; pc3=pc3/nt; % probabilit a priorip = pc1*d1+pc2*d2+pc3*d3; % p(x) (thorme des probabilit totales)map1 = pc1*d1./p; map2 = pc2*d2./p; map3 = pc3*d3./p;seuil = .15; rejetD = 0.025;if (map1>(map2+seuil)) & (map1>(map3+seuil))); classe = 1elseif ((map2>(map1+seuil)) & (map2>(map3+seuil))); classe = 2elseif (map3>(map1+seuil)) & (map3>(map2+seuil))); classe = 3elseif (pMAP sur 3 classesExemple sur 3 classesComment choisir b ?Minimiser lerreur en gnralisation : avec un ensemble de test avec une technique de rchantillonnage avec une borne sur lerreurMthode linairemthode des potentielsLes ci sont recherchs de manire minimiser la probabilit derreurLes ci traduisent linfluence du point dans le calcul de la solutionMthodes non linaires : les RBFCasser la linarit : adapter le noyau au problme au lieu de choisir xi, optimiser la position du centre adapter la largeur de bande du noyau si on a de bon noyaux, on peu en rduire le nombre Les ci mi et bi sont recherchs de manire minimiser lerreur :ATTENTION : on a maintenant un problme de minimisation non linaireInconvnient des noyauxla maldiction de la dimensionnalitn points pour d dimensions Formulation gomtrique,Densit de lchantillonnage,Distance entre 2 points,Tous les points sont la frontire,Borne de Stone,En grande dimension la notion de distance ne veut pas dire grand choseDensit de lchantillonnagen points pour d dimensionsX ~ N(0,1) d x = randn(10000,100)proj = x * x(1,:);hist(proj./proj(1))X ~ U(0,1) ddist(n,d) = Ej(mini |xi-xj|)nConclusionNoyau =distancemaldiction = reprsentationflexibilit = largeur de bandedes noyaux pour battre la maldiction ?vers la non linarit pour battre la maldiction !TP matlabAller rechercher les donnes sur le WEB : psichaud.insa-rouen.fr\~scau\RdF\DataAcor.txtouvrir Matlab : et charger les donnesload 'DataAcor.txt'Xi = DataAcor;visualiser les donnes grce au programme visu.mcrire une programme matlab1. Netoyer les donnes (liminer les codes -9999)2. Normaliser3. diviser les donnes en apprentissage / test4. raliser lanalyse discriminante5. estimer les densits par la mthode de Parzen6. calculer et visualiser la matrice de confusionparzen3crejet

Recommended

View more >