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

Pasillas Díaz, José Ramón (2017). On the improvement of complexity time and detection rate of outlier detectors : an unsupervised ensemble perspective. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (1MB) | Prévisualisation
Prévisualisation	PDF Télécharger (848kB) | Prévisualisation

Résumé

This thesis presents two unsupervised algorithms to detect outlier observations whose aberrant behavior is hidden in lower dimensional subspaces or cannot be identified with the use of a single detector. In particular, we contemplated three facets: first, the difficulty of a single detector to identify different types of outliers; second, the propensity of interesting outliers to hide in low dimensional subspaces; third, the impact that distinct distance measures have on the outlier detection process. The ambition of the proposed algorithms is to improve our understanding about data observations whose outlier behavior is not evident using simple outlier detection algorithms. Accordingly, we addressed three specific problems. First, we propose to design an ensemble based on different types of outlier detectors with a set of weights assigned without supervision. Second, we propose an ensemble to identify observations whose outlier behavior is visible only on specific subspaces. Third, we develop a scheme to understand how a single detector or an ensemble of outlier detectors is influenced by the selection of a distance metric and its interaction with different dimensionalities, data sizes, parameter settings or ensemble components.

There is a wide availability of algorithms aimed at detecting outliers. However, the number of unsupervised ensemble approaches is limited and are mainly oriented towards the detection of a specific type of outlier. Accordingly, our first goal is to detect, in a unsupervised manner, distinct type of outlying observations. We propose an approach capable of using the output of different types of detectors, assigning specific weights to each detector depending on an internal evaluation (unsupervised) of the ability that each algorithm has on the specific dataset at hand; furthermore, this approach assigns a second weight to each data observation in order to increase the gap between outlier and inliers, further improving the outlier detection rate. The main contribution of this work is an ensemble of outlier detectors, whose components can be based on different assumptions, with an enhanced outlier detection rate when compared with similar single and ensemble approaches for outlier detection. Nonetheless, our approach exhibits a processing time linearly dependent on the number of ensemble components; this behavior is not exclusive of our approach, being instead prevalent in the ensemble outlier detection literature.

The second part of this thesis focuses on the detection of a complex type of outliers, known in the literature as interesting outliers, which are detectable only on specific subspaces of the data, on the contrary simple outliers are detectable on full dimensionality. Since our first approach was unable to efficiently detect this type of outlier, our second goal is the detection of lower dimensional outliers in a computationally efficient time. We propose an unsupervised ensemble based on different subspaces and subsamples of data which provides a higher detection rate and is computationally more efficient than similar ensemble approaches; in some cases, our approach is even better to that of a single execution of a simple outlier detection algorithm. The main contributions of this work are the possibility of detecting lower dimensional outliers within an improved processing time.

The last section of this thesis is oriented towards the study of the interaction between distance metric, parameter settings, data size, dimensionality and number of ensemble components in determining the detection rate and processing time of an outlier detector. Hence, our third goal is to improve our comprehension about the multiple factors influencing an outlier detection algorithm. A set of experiments has been devised to evaluate both detection rate and processing time. The experiments cover a wide set of synthetic and real-world data scenarios. Our synthetic data experiments allow us to introduce perturbations in the size and dimensionality of the data, while real world data permits an evaluation of the effect of varying the parameter settings of an algorithm. To the best of our knowledge this is the first evaluation considering a complete set of factors, mainly distance metrics, influencing the effectiveness and efficiency of an outlier detector. The understanding achieved in this study can be a key step towards the development of new ensemble approaches or the selection and parameterization of existing ones.

Titre traduit

Sur l'amélioration de la complexité temporelle et du taux de détection des données aberrantes : une perspective d'utilisation des methodes non supervisées fondées sur les ensembles

Résumé traduit

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.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Manuscript-based thesis presented to École de technologie supérieure in partial fulfillment of the requirements for the degree of doctor of philosophy". Bibliographie : pages 139-148.
Mots-clés libres:	Observations aberrantes (Statistique) Exploration de données (Informatique) Algorithmes. valeurs aberrantes, ensemble, apprentissage non supervisé, données non balancées
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Ratté, Sylvie
Programme:	Doctorat en génie > Génie
Date de dépôt:	21 mars 2018 16:01
Dernière modification:	21 mars 2018 16:01
URI:	https://espace.etsmtl.ca/id/eprint/2016

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt