On the improvement of complexity time and detection rate of outlier detectors : an unsupervised ensemble perspective

Résumé

Cette thèse présente deux algorithmes non supervisés pour détecter des données aberrantes don't le comportement est dissimulé dans des sous-espaces ou ne peut être identifié par l’utilisation d’un seul détecteur. Plus spécifiquement, nous examinons trois aspects : premièrement, la difficulté d’un seul détecteur à identifier différents types de valeurs aberrantes; deuxièmement, la propension des valeurs aberrantes intéressantes à se cacher dans des sous-espaces à faible dimension; troisièmement, l’impact des mesures de distance sur le processus de détection des valeurs aberrantes. Le but de cette thèse est d’améliorer notre compréhension des données dont le comportement aberrant n’est pas apparent, en utilisant des algorithmes simples de detection des valeurs aberrantes. En conséquence, nous avons abordé trois problèmes spécifiques. D’abord, nous proposons une méthode basée sur un ensemble de différents types de détecteurs dont les poids sont attribués de manière non supervisée. Ensuite, nous proposons un ensemble de détecteurs permettant d’identifier les observations dont le comportement aberrant est identifiable uniquement dans des sous-espaces spécifiques. Finalement, nous avons développé un schéma permettant de comprendre comment un seul détecteur ou un ensemble de détecteurs est influencé par la sélection d’une métrique de distance et son interaction avec différentes dimensions, tailles de données, paramètres ou composants d’ensemble. Il existe de nombreux algorithmes permettant de détecter les valeurs aberrantes. Cependant, les approches fondées sur des ensembles non supervisés sont relativement limitées en nombre et sont principalement axées vers la détection d’un type spécifique de valeurs aberrantes. En conséquence, notre premier objectif est de détecter, de manière non supervisée, un type distinct d’observations périphériques. Nous proposons une approche capable d’utiliser la sortie de différents types de détecteurs, en attribuant des poids spécifiques à chaque détecteur en function d’une évaluation interne (non supervisée) de la capacité de chaque algorithme à traiter une série de données spécifiques. De plus, cette approche attribue un deuxième poids à chaque observation afin d’augmenter l’écart entre les valeurs aberrantes et les valeurs induites, ameliorant ainsi le taux de détection des valeurs aberrantes. La principale contribution de ce travail est un ensemble de détecteurs, dont les composants peuvent être basés sur des hypothèses adaptées, avec un taux de détection des valeurs aberrantes amélioré par rapport aux approches similaires pour la détection des valeurs aberrantes. Comme c’est le cas pour plusieurs méthodes dans la littérature, notre approche présente un temps de traitement linéairement dépendant du nombre de composantes dans l’ensemble. La deuxième partie de cette thèse se concentre sur la détection d’un type complexe de valeurs aberrantes, connu dans la littérature comme des valeurs aberrantes intéressantes; celles-ci ne sont détectables que dans des sous-espaces spécifiques, contrairement aux valeurs aberrantes simples qui sont détectables dans l’espace complet. Notre première approche précédente étant incapable de détecter en un temps acceptable ce type de valeurs aberrantes, notre deuxième objectif concerne donc la détection de valeurs aberrantes de dimensions inférieures dans un temps efficace en termes de calcul. Nous proposons ici un ensemble non supervisé basé sur différents sous-espaces et sous-échantillons de données qui fournit non seulement un taux de detection plus élevé, mais qui s’avère aussi plus efficace que les approches d’ensemble similaires et, dans certains cas, supérieur au taux de détection des algorithmes spécifiquement adaptés aux données. Les principales contributions de ce travail sont la possibilité de détecter des valeurs aberrantes de dimensions inférieures et un temps de traitement amélioré. La troisième partie de cette thèse étudie les interactions entre la métrique de distance choisie, les paramètres des algorithmes, la taille des données, la dimensionnalité et le nombre de composantes dans l’ensemble. Par conséquent, notre troisième objectif est d’améliorer notre comprehension des multiples facteurs influençant un algorithme de détection des valeurs aberrantes. Un ensemble d’expériences a été conçu pour évaluer à la fois le taux de détection et le temps de traitement. Les expériences couvrent un large éventail de scénarios de données synthétiques et réelles. Nos expériences de données synthétiques permettent des perturbations dans la taille et la dimensionnalité des données, alors que les données réelles permettent d’évaluer et de varier les paramètres d’un algorithme. À notre connaissance, il s’agit de la première évaluation, prenant en compte un ensemble complet de facteurs, principalement les mesures de distance, de l’influence de ces variantes sur l’efficacité d’un détecteur de valeurs aberrantes. Les résultats obtenus dans cette étude peuvent s’avérer une étape clé pour développer de nouvelles approches fondées sur des ensembles ou encore pour sélectionner les paramètres adéquats dans les approches existantes.

Date	24 oct. 2017
langue originale	Anglais américain
Établissement diplômant	École de technologie supérieure
Superviseur	Sylvie Ratté (Directeur(-trice))