Αλγόριθμοι ανίχνευσης έκτοπων παρατηρήσεων (outliers) στην ανθεκτική (robust) εκτίμηση συνδιακύμανσης και παλινδρόμησης

Abstract

IntroductionThe location-covariance estimation and linear regression are the central parts in multivariate statistical analysis. They appear in many applications where we want to parametrize data that arrives from many different application domains such as in economics, finance, e-commerce, engineering, biology and other. For examples in finance, the covariance matrix between assets' returns is estimated to model their risk.When dealing with a large data set, we often want to find statistical and mathematical models to simplify its representation. One of the first questions that we often ask is whether we can fit the data with a normal distribution. This involves the estimation of the location and the covariance matrix of the normal distribution. The location and the covariance matrix are often estimated using the classical method of Maximum Likelihood Estimation (MLE) by assuming the data follows a multivariate normal distribution. It is well documented that even a single observation that deviates from the normal distribution could distort the MLE estimators. In fact, under the normality assumption, the loglikelihoud function contains the sum of the squared Mahalanobis distances from the dominated those from the good observations. Therefore, the location and the covariance matrix are pulled toward the outliers. Since outliers appear occasionally in practice, many different techniques for outlier detection and for robust estimation have been developed recently as we know from the robust literature.From the data, we also often want to study the relationship between different attributes and this is often done through regression analysis. In this case, linear regression with the method of least squares is the most common class practice because it is very simple to compute and to explain the results. However, it is well-known that the least squares fit can be grossly influenced by outliers. This issue again motivates the development of many different techniques for robust regression.Proposed Algorithms-EstimatorsClassical methods of maximum likelihood and least squares rely a great deal on the correctness of the model assumptions. Since these assumptions are only approximations of reality, many robust statistical methods have been developed to produce estimators that are robust against the deviation from the model assumptions. Unfortunately, these techniques have very high computational complexity that prevents their application to large scale problems. We present computationally efficient estimation and robust for location-covariance estimation and robust linear regression using special mathematical programming models.Robust Location Estimate (mean, median)Estimator Least Trimmed Absolute Deviations Using Linear Programming (LP-LTAD)Location estimate is one of the most important problem in statistical theory. It is well-known that classical methods using sample averages suffer from the presence of outliers. Using the median instead of the mean can partially resolve this issue but not completely. For the univariate case, a better approach is to use the Least Trimmed Absolute Deviation (LTAD) which is known to have desirable asymptotic properties such as robustness, consistently, high breakdown and normality. We extend the LTAD estimate to the multivariate case and study numerical methods for its computation. A major issue with LTAD estimation lies on the combinatorial nature of the problem which makes it very computationally challenging. We propose a new trimming procedure that reformulates the multivariate LTAD problem as a mixed integer linear program (MILP) which is then shown to be equivalent to a linear program (LP) under some transformations. We develop fast numerical methods for solving the resulting large-scale LPs. We also show attractive properties of the new estimate in terms of robustness and efficiency. Experimental results for demonstrating properties and computation of the multivariate LTAD are presented.Robust Covariance EstimateEstimator Least Trimmed Euclidean Deviations (LTED)Classical methods for multivariate location μ and scatter matrix Σ are based on the sample mean vector and sample covariance matrix, which are very sensitive to outlying observations. Detecting outliers in a multivariate point cloud is not trivial, especially when there are several masked outliers. To avoid the masking effect, we propose a new algorithm for robust location and scatter based on two stages: In the first stage a multivariate L1 median center μ is estimated after removing the outlying observations based on the least trimmed Euclidean deviations (LTED).In the second stage the concentration step is applied to the coverage data set of the first stage in order to detect observations which violate the correlational structure of the variables. The LTED subset changes to a subset separated from the set of all data by an ellipsoid.Besides, applying only the first stage of the LTED the new approach is also capable of detecting outliers in multivariate data where the number of dimensions is larger than the number of observations.Robust Regression EstimatePenalized Trimmed Square-LTED (\PTS-L)Usually, in the regression models, the data are contaminated with unusually observations (outliers). For that reason the last 30 years have developed robust regression models. One famous regression estimator is the Penalized Trimmed Square (PTS).In this work based on Least Trimmed Euclidean Deviations (LTED), we proposed a new robust efficient scale and leverage estimates. Extensive computational, Monte-Carlo simulations, with varying types of outliers and degrees of contamination, indicate that the proposed new estimator improves the PTS regression estimator and performs well in identifying groups of high-leverage outliers.Weighted Least Trimmed Absolute Deviation Using Linear Programming (LP-WLTAD)High breakdown estimation (HBE) addresses the problem of getting reliable parameter estimates in the face of outliers that may be numerous and bad placed. In multiple regression, the standard HBE's have been those defined by the least median of squares (LMS) and the least trimmed squares (LTS) criteria. One alternative is the least trimmed sum of absolute deviations (LTA), which is found by minimizing the sum of absolute residuals of the covered cases.We propose the Weighted Least Trimmed Absolute Deviation (LP-WLTAD), a new weighted trimming procedure that reformulates the LTA regression problem as a linear program (LP) under some new constraints and transformationsWe also show attractive properties of the new estimate in terms of robustness and efficiency. Experimental results for demonstrating properties and computation of LP-WLTAD are presented for all types of outliers.ConclusionsThe new estimators of the research we can called them new generation estimators. Because the have high breakdown point, they are efficient, very robust and they can address with every type of outliers wherever the outliers are located at the data set.

Η παρούσα διδακτορική διατριβή ασχολείται με την ανάπτυξη νέων ανθεκτικών εκτιμητών για τον εντοπισμό έκτοπων παρατηρήσεων και τον προσδιορισμό ανθεκτικού πίνακα συνδιακύμανσης καθώς και με μοντέλα παλινδρόμησης και γενικά σε σύνολα δεδομένων των οποίων οι μεταβλητές αποκλίνουν από τις ιδανικές συνθήκες κανονικότητας. Ο βασικός στόχος της διατριβής είναι η παρουσίαση των πλεονεκτημάτων της τεχνικής του μαθηματικού προγραμματισμού μέσω του οποίου είναι εφικτός ο προσδιορισμός νέων τύπων ανθεκτικών εκτιμητών θέσης, πίνακα συνδιακύμανσης και παλινδρόμησης. Η σύγκριση των διάφορων νέων ανθεκτικών εκτιμητών με τους γνωστούς κλασικούς εκτιμητές από την βιβλιογραφία της ανθεκτικής στατιστικής υποδεικνύει τη χρησιμότητα των νέων εκτιμητών αλλά και την αναγκαιότητα εισαγωγής του μαθηματικού προγραμματισμού ως μια πολύ χρήσιμη τεχνική στην ανθεκτική στατιστική.Το πιο σημαντικό τμήμα της εργασίας αποτελείται από τα διάφορα προτεινόμενα πρότυπα μαθηματικού προγραμματισμού τα οποία συντελούν στην ανάπτυξη νέων ανθεκτικών εκτιμητών θέσης και παλινδρόμησης. Monte Carlo μελέτη προσομοίωσης και γνωστά πρότυπα συγκριτικής αξιολόγησης (benchmark examples) της ανθεκτικής βιβλιογραφίας οδηγούν στο συμπέρασμα πως οι νέοι εκτιμητές βελτιώνουν τόσο την ανθεκτικότητα όσο και την αποτελεσματικότητα.Στο Κεφάλαιο 2 αρχικά περιγράφεται ο ανθεκτικός εκτιμητής του LTAD. Στην συνέχεια μία νέα ανθεκτική διαδικασία (με χρήση προτύπου μαθηματικού προγραμματισμού) προτείνεται για την εκτίμηση μέτρου θέσης. Η ανθεκτικότητα και η αποτελεσματικότητα της νέας διαδικασίας φαίνεται μέσω παραδειγμάτων και προσομοιώσεων Monte Carlo.Το Κεφάλαιο 3 περιλαμβάνει μια επισκόπηση των ανθεκτικών εκτιμητών για τον προσδιορισμό έκτοπων και πίνακα συνδιακύμανσης πολυμεταβλητών δεδομένων, καθώς και τους αλγόριθμους υπολογισμού των εκτιμητών αυτών. Στη συνέχεια του κεφαλαίου αυτού παρουσιάζεται ο νέος εκτιμητής LTED (ο οποίος είναι μια αλγοριθμική προσέγγιση του LTAD για πολυμεταβλητά δεδομένα). Μελέτη προσομοίωσης πραγματοποιείται για τη σύγκριση της αποτελεσματικότητας του νέου εκτιμητή με διάφορους γνωστούς εκτιμητές.Το Κεφάλαιο 4 είναι αφιερωμένο στους ανθεκτικούς εκτιμητές υψηλού σημείου κατάρρευσης. Περιγράφονται κάποιοι από τους πιο γνωστούς ανθεκτικούς εκτιμητές υψηλού σημείου κατάρρευσης. Στην κατηγορία αυτή ανήκει και ο εκτιμητής Penalized Trimmed Squares (PTS) για τον οποίο αναφέρονται οι καλές ιδιότητές του οι οποίες προέρχονται από την αναλυτική λύση η οποία επιτυγχάνεται από το μικτό ακέραιο τετραγωνικό προγραμματισμό. Για την καλυτέρευση του προτείνεται μια νέα διαδικασία η οποία χρησιμοποιεί την λύση του LTED για την αναγνώριση των leverage σημείων. Μελέτη προσομοίωσης πραγματοποιείται για τη σύγκριση της αποτελεσματικότητας του νέου PTS-L σε σύγκριση με το κλασικό PTS.Στο Κεφάλαιο 5 εισάγεται ένας νέος εκτιμητής ανθεκτικής παλινδρόμησης, ως απόρροια του εκτιμητή LTAD και προσαρμογή του στην ανθεκτική παλινδρόμηση, με την χρήση γραμμικού προγραμματισμού. Μελέτη προσομοίωσης πραγματοποιείται για τη σύγκριση της αποτελεσματικότητας και ανθεκτικότητας του νέου εκτιμητή με διάφορους γνωστούς εκτιμητές.Τέλος, στο Κεφάλαιο 6 διατυπώνονται τα συμπεράσματα της ερευνητικής μελέτης καθώς και μελλοντικές προτάσεις για επέκταση της υπάρχουσας μελέτης.