offres d'emploi formations actualités contact accès annuaire intranet
Séminaires >

Matrice chapeau à noyau discriminante : nouvel outil pour la détection de points aberrants dans les jeux de données

Franck Dufrenois - LISIC

jeudi 14 mars 2013 à 15h00

salle B014


Les données que nous manipulons et étudions sont généralement imparfaites, « polluées » par la présence d’observations aberrantes et constitue un handicap pour expliquer le phénomène dominant sous-jacent aux données. Ces « outliers » signalent soit la présence d’un phénomène résiduel étranger et/ou la nature imparfaite des « capteurs » que nous utilisons. Les outils statistiques classiques doivent donc introduire dans leur principe des propriétés de robustesse afin d’isoler la structure d’intérêt.

En régression, le terme employé est la « régression robuste » et en classification, plusieurs termes sont utilisés : problème de classification à une classe, détection de nouveautés. Le terme « une classe » signifie qu’un sous ensemble des observations forme statistiquement un échantillon représentatif et que l’autre regroupe des événements « rares », souvent impossible à caractériser statistiquement et donc ne pouvant être définis par une classe additionnelle.

Bien qu’a priori conceptuellement différent, je propose dans cet exposé de montrer qu’il existe une passerelle entre la régression robuste et la classification à une classe. En particulier, je montre que la régression linéaire robuste peut être formulée à partir d’un critère de Fisher linéaire à une classe, critère traditionnellement employé pour séparer linéairement deux classes. Cette nouvelle mesure de contraste est basée sur les propriétés de décomposition en sous espace de la matrice chapeau. La matrice chapeau est une quantité auxiliaire utilisée en régression, permettant en particulier, via ses éléments diagonaux, de détecter la présence de données atypiques.

La maximisation de cette mesure de contraste fournit à la fois le sous espace projectif optimale (au sens du critère) ainsi que le vecteur indicateur séparant la population en deux classes : la classe « dominante » et la classe « outliers ». Elle est conduite sous la forme d’un processus d’optimisation itératif, alternant entre l’estimation du sous espace projectif optimal et la mise à jour de l’état du vecteur indicateur. Si l’estimation du sous espace projectif est équivalent à résoudre un problème de valeurs propres généralisées, la mise à jour de l’état du vecteur indicateur est basé sur l’hypothèse de gaussianité perturbant le sous ensemble linéaire dominant. Il en résulte que les coefficients diagonaux de la matrice chapeau « projetés » sur le sous espace optimal suivent une loi du chi 2 permettant une description formelle des points aberrants et leur identification par test d’hypothèse.

L’itération de cette procédure en deux étapes fournit à la fois le vecteur des paramètres de la régression et les labels des données. La fonctionnalité de cet algorithme est bivalente : il agit à la fois comme un régresseur et un classifieur. Cette caractéristique confère « naturellement » à notre outil un très bon niveau de robustesse.

Dans une seconde partie, nous verrons comment étendre cette mesure de contraste pour isoler une population dominante non linéaire du reste des données. L’utilisation de l’astuce du noyau « the kernel trick » maintenant couramment employé pour « sortir du linéaire » nos outils statistiques standards, sera là encore mis à contribution. L’idée majeure de cette astuce repose sur l’action de « plonger » les données d’entrée dans un espace de redescription de dimension plus importante voir infinie et surtout, afin d’éviter le problème récurrent de la course à la dimension, de remplacer le produit scalaire par une fonction noyau. La fonction noyau qui sera utilisée durant ce travail sera la fonction gaussienne.

En particulier, nous montrerons dans cette partie qu’il existe un encadrant supérieure de notre mesure de contraste, dépendant uniquement du vecteur indicateur, permettant ainsi de séparer l’estimation du vecteur indicateur de l’estimation du sous espace projectif.

Nous montrerons également que cet encadrant moyennant une légère modification constitue une fonction objective concave, dont la maximisation est équivalent à résoudre un problème linéaire à variables binaires sans contraintes. Si à première vue ce problème peut être considéré comme NP difficile, sa nature concave nous permettra de le résoudre facilement par une approche de type perturbation avec initialisation. L’état du vecteur indicateur sera ainsi déterminé. Une frontière de décision séparant les outliers des données dominantes sera ensuite estimée comme solution d’un problème de valeurs propres généralisé.

Bien évidemment, le problème de la sélection du modèle sera également abordé. Le choix de l’échelle de la gaussienne ainsi que le paramètre de régularisation sera discuté.

La performance de cette approche sera étudiée sur des données synthétiques ainsi que sur des données réelles. La phase d’initialisation de notre approche nous permet de travailler soit en mode « non supervisé » soit en mode « semi-supervisé ». Nous pourrons comparer cette approche avec des méthodes récentes non et semi supervisées.