Most widely accepted measures of performance for learning algorithms, such as accuracy and area under the ROC curve, provide information about behavior at the data set level. They say nothing about which instances are misclassified, whether two learning algorithms with the same classification accuracy on a data set misclassify the same instances, or whether there are instances misclassified by all learning algorithms. These questions about behavior at the instance level motivate our empirical analysis of instance hardness, a measure of expected classification accuracy for an instance. We analyze the classification of 57 data sets using 9 learning algorithms. Of the over 175000 instances investigated, 5% are misclassified by all 9 of the considered learning algorithms, and 15% are misclassified by at least half. We find that the major cause of misclassification for hard instances is class overlap, manifested as outliers and border points which can be exacerbated by class skew. We analyze these causes and show to what extent each leads to misclassifications, both in isolation and jointly. 19.8% of all misclassified instances are outliers; 71.3% are border points; 21% belong to a minority class. We also find that 91.6% of all outliers and 38.3% of all border points are misclassified whereas only 3.5% of instances without class overlap are misclassified. We propose a set of heuristics to predict when an instance will be hard to correctly classify. Additionally, we analyze how different learning algorithms perform on tasks with varying degrees of outliers, border points and class skew.

No description available.

No description available.

[pt] O desenvolvimento visto nos últimos anos em dispositivos móveis tem tornado dramático o aumento na quantidade de dados e informações disponíveis para publicitários ao redor do mundo. Custo computacional e tempo disponível para processar dados e ser capaz de distinguir verdadeiros usuários de anomalias ou ruído têm crescido. Assim, a criação de um método para detecção de outliers poderia apoiar melhor os pesquisadores de Marketing e aumentar sua precisão na compreensão do comportamento digital. Estudos atuais mostram que, até o momento, o uso de meta-algoritmos tem sido pouco usado para detecção de outliers. Meta-algoritmos tendem a trazer benefícios porque reduzem a dependência que um único algoritmo pode gerar. Esta dissertação propõe um design de meta-algoritmo que utiliza diferentes algoritmos para obter resultados de detecção de outliers melhores do que aqueles obtidos por apenas um único algoritmo: centrado em modelo e sequencial. A novidade da abordagem consiste em (i) explorar a técnica sequencial, utilizando algoritmos que são aplicados sequencialmente, no qual um algoritmo impacta o próximo e o resultado final é uma combinação dos resultados obtidos; (ii) centralizar a performance no modelo e não nos dados, o que significa que o ensemble é aplicado a todo o conjunto de dados ao mesmo tempo e; (iii) apoiar pesquisadores de marketing que precisem operar ciência de dados de forma mais robusta e coerente. / [en] Latest years evolution in mobile devices has increased dramatically the amount of data and available information for advertisers around the world. Computational cost and available time to process data and be able to distinguish true users from anomalies or noise has only increased. Thus, the creation of a method to detect outliers could support Marketing researchers and increase their precision in understanding online behavior. Recent studies showthat, so far, meta-algorithms have not been used to detect outliers. Metaalgorithms tend to bring benefits because they reduce dependency that a single algorithm can generate. This work proposes a sequential model-centric ensemble design that uses different algorithms in outlier detection to obtain better results than those obtained by a single algorithm. The novelty in this approach consists in: (i) exploring the sequential technique, using algorithms that impact the next one and whose results are a combination of previously obtained results; (ii) centralizing performance around the model and not the data, which means the ensemble is applied in the whole dataset and not on different subsamples; (iii) support Marketing researchers that need to operate data Science in a more robust and coherent way.

This research approaches the prediction models application along with the usage of residual control charts to evaluate productive processes with characteristics of autocorrelation in its samples. The overall objective was to determine the Individual Measurement Control Charts (IMCC) and the Exponentially Weighted Moving Average (EWMA) efficiency when applied to residuals of ARIMA class, to the outliers detection in autocorrelated processes, as well as identifying the autocorrelation influence and the amplitude of the outlier concerning the charts detection capacity. To each AR(1) and MA(1), 640.000 series were simulated, with varying strength and autocorrelation signal. After each series simulated residual stability verification, in the original series, outliers were inserted with varying amplitudes in a pre-determined observation. The series contaminated by the anomalous observation were again modeled and the residual were inscribed in IMCC and EWMA control charts, correctly registering the detected points. In the detection proportions to the outlier s variant pair, autocorrelation parameter and amplitude, non parametric tests were applied. The result obtained through the tests presented the superiority of the IMCC chart for both models. To what concerns the study of the autocorrelation parameter influence, regarding its signal and magnitude to both charts and AR(1) and MA(1) models, no significant difference could be verified. Therefore, the efficacy of IMCC control charts in the outliers detection through residuals in non independent processes could be confirmed. / A presente pesquisa aborda a aplicação de modelos de previsão juntamente com a utilização de gráficos de controle de resíduos para a avaliação de processos produtivos com características de autocorrelação em suas amostras. O objetivo geral foi determinar a eficiência dos gráficos de controle de observações individuais (IMCC) e de média móvel exponencialmente ponderada (EWMA) quando aplicados aos resíduos de modelos da classe AR(1) ou MA(1), para detecção de outliers em processos autocorrelacionados, além de evidenciar a influência da autocorrelação e da amplitude do outlier no poder de detecção dos gráficos. Foram simuladas 640.000 séries para cada modelo, variando a força e o sinal da autocorrelação. Após a verificação da estabilidade dos resíduos em cada série simulada, na série original, foram inseridos outliers com amplitudes variáveis em uma observação prédeterminada. As séries contaminadas pela observação anômala foram novamente modeladas e os resíduos foram grafados em gráficos de controle IMCC e EWMA, registrando-se os pontos detectados corretamente. Em cada gráfico, para o par de variáveis: parâmetro de autocorrelação e amplitude de outlier, gerou-se uma proporção de detecção, na qual foram aplicados testes de comparação não-paramétricos. O resultado obtido por meio dos testes evidenciou a superioridade do gráfico IMCC para ambos os modelos. Quanto ao estudo da influência do parâmetro de autocorrelação, referente ao sinal e a magnitude da mesma, para ambos os gráfico e modelos AR(1) e MA(1), não se verificou diferença significativa. Dessa forma, comprovou-se a eficácia dos gráficos de controle IMCC em detectar outliers por meio de resíduos em processos industriais autocorrelacionados.

A área de detecção de outliers (ou detecção de anomalias) possui um papel fundamental na descoberta de padrões em dados que podem ser considerados excepcionais sob alguma perspectiva. Detectar tais padrões é relevante de maneira geral porque, em muitas aplicações de mineração de dados, tais padrões representam comportamentos extraordinários que merecem uma atenção especial. Uma importante distinção se dá entre as técnicas supervisionadas e não supervisionadas de detecção. O presente projeto enfoca as técnicas de detecção não supervisionadas. Existem dezenas de algoritmos desta categoria na literatura e novos algoritmos são propostos de tempos em tempos, porém cada um deles utiliza uma abordagem própria do que deve ser considerado um outlier ou não, que é um conceito subjetivo no contexto não supervisionado. Isso dificulta sensivelmente a escolha de um algoritmo em particular em uma dada aplicação prática. Embora seja de conhecimento comum que nenhum algoritmo de aprendizado de máquina pode ser superior a todos os demais em todos os cenários de aplicação, é uma questão relevante se o desempenho de certos algoritmos em geral tende a dominar o de determinados outros, ao menos em classes particulares de problemas. Neste projeto, propõe-se contribuir com o estudo, seleção e pré-processamento de bases de dados que sejam apropriadas para se juntarem a uma coleção de benchmarks para avaliação de algoritmos de detecção não supervisionada de outliers. Propõe-se ainda avaliar comparativamente o desempenho de métodos de detecção de outliers. Durante parte do meu trabalho de mestrado, tive a colaboração intelectual de Erich Schubert, Ira Assent, Barbora Micenková, Michael Houle e, principalmente, Joerg Sander e Arthur Zimek. A contribuição deles foi essencial para as análises dos resultados e a forma compacta de apresentá-los. / The outlier detection area has an essential role in discovering patterns in data that can be considered as exceptional in some perspective. Detect such patterns is important in general because, in many data mining applications, such patterns represent extraordinary behaviors that deserve special attention. An important distinction occurs between supervised and unsupervised detection techniques. This project focuses on the unsupervised detection techniques. There are dozens of algorithms in this category in literature and new algorithms are proposed from time to time, but each of them uses its own approach of what should be considered an outlier or not, which is a subjective concept in the unsupervised context. This considerably complicates the choice of a particular algorithm in a given practical application. While it is common knowledge that no machine learning algorithm can be superior to all others in all application scenarios, it is a relevant question if the performance of certain algorithms in general tends to dominate certain other, at least in particular classes of problems. In this project, proposes to contribute to the databases study, selection and pre-processing that are appropriate to join a benchmark collection for evaluating unsupervised outlier detection algorithms. It is also proposed to evaluate comparatively the performance of outlier detection methods. During part of my master thesis, I had the intellectual collaboration of Erich Schubert, Ira Assent, Barbora Micenková, Michael Houle and especially Joerg Sander and Arthur Zimek. Their contribution was essential for the analysis of the results and the compact way to present them.

[pt] O objetivo da dissertação é analisar o comportamento das diferentes metodologias utilizadas para detecção e tratamento de outliers na determinação de fatores de prova de medidores do tipo turbina. A motivação desse trabalho é evitar tomadas de decisão equivocadas decorrentes de tratamento inadequado de outliers, comprometendo a confiabilidade na medição e consequentemente seu faturamento. A prova do fator de medidor pode ser considerada como um parâmetro de calibração, expressando a razão entre o volume de referência e o volume total de líquido que passa através do medidor. A Norma internacional recomenda o teste de Dixon para o tratamento de outliers para um conjunto de prova do fator de medidor. No entanto, a literatura é explícita quanto à avaliação do comportamento dos dados, a priori. A metodologia avalia se o comportamento dos dados do conjunto de prova do fator de medidor é Gaussiano, em seguida se comparam diferentes abordagens paramétricas e não paramétricas para a detecção e tratamento de outliers aplicados às provas dos fatores de medidores do tipo turbina para a transferência de custódia de gás liquefeito de petróleo. Posteriormente, este efeito é avaliado em relação ao número de outliers e como este manuseio afeta os critérios da amplitude variável para a incerteza expandida na prova do fator de medidor médio. Os resultados mostram que diferentes fatores de medidores médios podem ser alcançados para cada teste paramétrico e não paramétrico; de qualquer forma, conclui-se que estatisticamente não é observada diferença significativa entre eles. / [en] The objective of the dissertation is to analyze the behavior of the different methodologies used for the detection and treatment of outliers in the determination of meter proving factors of turbine type meters. The motivation of this work is to avoid mistaken decision-making as a result of inadequate treatment of outliers, compromising reliability in measurement and consequently its billing. A meter proving factor can be considered as a calibration parameter, by expressing the ratio the reference volume and the gross volume of liquid passed through a meter. The international guideline recommends Dixon s test for outliers to a meter proving factor set. However, the literature is explicit regarding the evaluation of data behavior, a priori. The methodology evaluates if the behavior of the meter proving factor set is Gaussian, then different parametric and nonparametric approaches for detection and treating outliers applied to turbine meter proving factors for custody transfer of liquefied petroleum gas are compared. Afterwards, this effect is evaluated in relation to the number of outliers and how this handling affects the variable range criteria for expanded uncertainty in average meter proving factor. The results show that different average meter factors can be reached for each nonparametric and parametric test; anyway, it is concluded that no statistically significant difference between them is noticed.

Submitted by Anderson Ricardo Ubinha de Sá (anderson.ubinha@yahoo.com.br) on 2016-09-05T21:29:18Z No. of bitstreams: 1 Dissertação Final - Anderson Ricardo Ubinha de Sá vf.pdf: 6749863 bytes, checksum: bd865f83f290dfc8a997497024fa3e32 (MD5) / Approved for entry into archive by Renata de Souza Nascimento (renata.souza@fgv.br) on 2016-09-06T17:20:49Z (GMT) No. of bitstreams: 1 Dissertação Final - Anderson Ricardo Ubinha de Sá vf.pdf: 6749863 bytes, checksum: bd865f83f290dfc8a997497024fa3e32 (MD5) / Made available in DSpace on 2016-09-06T17:23:02Z (GMT). No. of bitstreams: 1 Dissertação Final - Anderson Ricardo Ubinha de Sá vf.pdf: 6749863 bytes, checksum: bd865f83f290dfc8a997497024fa3e32 (MD5) Previous issue date: 2016-08-12 / O objetivo deste trabalho é comparar as metodologias anterior e atual da taxa DI-Cetip e indicar as suscetibilidades de cada procedimento. Por meio da geração de operações com taxas e volumes coerentes com o histórico, foi possível comparar ambas as metodologias e outras possíveis seis propostas apresentadas, além de identificar as magnitudes das diferenças dos resultados das apurações. São sugeridas melhorias a serem implementadas, como o delay na divulgação das informações, a exclusão total de outliers, a redução dos pesos das taxas extremas de forma simétrica, além de uma alternativa semelhante à taxa LIBOR, que mitigaria algumas das questões apontadas e seria mais adequada devido à redução drástica de negócios válidos para o cálculo. / The objective of this study is to compare the previous and current methodologies of DI-Cetip rate and indicate the susceptibilities of each procedure. By generating trades with rates and volumes according history, it was possible to compare both methodologies and other possible six proposals and identify the magnitudes of the differences in calculations. Improvements are suggested to be implemented, such as the delay in the disclosure of information, the total exclusion of outliers, reducing the weights of the extreme rates symmetrically, and an alternative like LIBOR, which would mitigate some of the issues raised and would be appropriate due to the drastic reduction of valid trades for the calculation.

A área de detecção de outliers (ou detecção de anomalias) possui um papel fundamental na descoberta de padrões em dados que podem ser considerados excepcionais sob alguma perspectiva. Detectar tais padrões é relevante de maneira geral porque, em muitas aplicações de mineração de dados, tais padrões representam comportamentos extraordinários que merecem uma atenção especial. Uma importante distinção se dá entre as técnicas supervisionadas e não supervisionadas de detecção. O presente projeto enfoca as técnicas de detecção não supervisionadas. Existem dezenas de algoritmos desta categoria na literatura e novos algoritmos são propostos de tempos em tempos, porém cada um deles utiliza uma abordagem própria do que deve ser considerado um outlier ou não, que é um conceito subjetivo no contexto não supervisionado. Isso dificulta sensivelmente a escolha de um algoritmo em particular em uma dada aplicação prática. Embora seja de conhecimento comum que nenhum algoritmo de aprendizado de máquina pode ser superior a todos os demais em todos os cenários de aplicação, é uma questão relevante se o desempenho de certos algoritmos em geral tende a dominar o de determinados outros, ao menos em classes particulares de problemas. Neste projeto, propõe-se contribuir com o estudo, seleção e pré-processamento de bases de dados que sejam apropriadas para se juntarem a uma coleção de benchmarks para avaliação de algoritmos de detecção não supervisionada de outliers. Propõe-se ainda avaliar comparativamente o desempenho de métodos de detecção de outliers. Durante parte do meu trabalho de mestrado, tive a colaboração intelectual de Erich Schubert, Ira Assent, Barbora Micenková, Michael Houle e, principalmente, Joerg Sander e Arthur Zimek. A contribuição deles foi essencial para as análises dos resultados e a forma compacta de apresentá-los. / The outlier detection area has an essential role in discovering patterns in data that can be considered as exceptional in some perspective. Detect such patterns is important in general because, in many data mining applications, such patterns represent extraordinary behaviors that deserve special attention. An important distinction occurs between supervised and unsupervised detection techniques. This project focuses on the unsupervised detection techniques. There are dozens of algorithms in this category in literature and new algorithms are proposed from time to time, but each of them uses its own approach of what should be considered an outlier or not, which is a subjective concept in the unsupervised context. This considerably complicates the choice of a particular algorithm in a given practical application. While it is common knowledge that no machine learning algorithm can be superior to all others in all application scenarios, it is a relevant question if the performance of certain algorithms in general tends to dominate certain other, at least in particular classes of problems. In this project, proposes to contribute to the databases study, selection and pre-processing that are appropriate to join a benchmark collection for evaluating unsupervised outlier detection algorithms. It is also proposed to evaluate comparatively the performance of outlier detection methods. During part of my master thesis, I had the intellectual collaboration of Erich Schubert, Ira Assent, Barbora Micenková, Michael Houle and especially Joerg Sander and Arthur Zimek. Their contribution was essential for the analysis of the results and the compact way to present them.

In this work we develop algorithms for the k-Supplier with Outliers problem. In a network, we are given a set of suppliers and a set of clients. The goal is to choose k suppliers so that the distance between every served client and its nearest supplier is minimized. Clients that are not served are called outliers and the number of allowed outliers is given on input. As k-Supplier with Outliers has numerous applications in logistics, we focus on parameters which are suitable for transportation networks. We study graphs with low highway dimension, which was proposed by Abraham et al. [SODA 2010], and low doubling dimension. It is known that unless P = NP, k-Supplier with Outliers does not admit a (3 − ε)-approximation algorithm for any constant ε > 0. The k-Supplier with Outliers problem is W[1]-hard on graphs of constant doubling dimension for parame- ters k and highway dimension. We overcome both of these barriers through the paradigm of parameterized approximation algorithms. In the case of highway dimension, we develop a (1 + ε)-approximation algorithm for any ε > 0 with running time f(k, p, h, ε) · nO(1) where p is the number of allowed outliers, h is the highway dimension of the input graph, and f is some computable function. In the case of doubling dimension, we develop a (1 + ε)-approximation...