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...

C'est sous l'impulsion des travaux fondateurs de Schumpeter que l'innovation se positionne au coeur de l'analyse économique. Depuis ces travaux fondateurs, trop peu d'innovation studies se sont toutefois consacrées aux usages du brevet dans la longue durée. Partant de là, cette thèse a pour ambition première de fournir, outre des renseignements empiriques de bonne qualité et de nouvelles séries statistiques, une lecture renouvelée, d'inspiration cliométrique, des brevets dans leurs dimensions structurelles et spatiales. Notre premier apport est de présenter l'organisation d'une nouvelle base de données sur l'évolution de longue période des brevets dans 40 pays du XVIIe siècle à 1945 et dans plus de 150 pays de 1945 à nos jours. Nous montrons, par la suite, que des événements certes rares, mais particulièrement significatifs, ont conditionné les pulsations de l'histoire économique des brevets. Les guerres, la promulgation de lois, l'ouverture ou la fermeture d'offices, mais aussi des effets purement statistiques ont, sur le très long terme, normé, à travers le dépôt et la délivrance des séries étudiées, l'existence des systèmes de brevets. En prolongement, nous déterminons, à travers une analyse spectrale et co-spectrale, la périodicité de nos séries de brevets. Enfin, nous livrons un éclairage plus contemporain, en termes de convergence, sur les dynamiques structurelles et surtout spatiales en oeuvre dans les systèmes de brevets des pays européens. / At the behest of Schumpeter's seminal works, innovation is now positioned at the heart of economic analysis. However, since these pioneering works, not enough innovation studies have been devoted to the uses of patent over time. Starting from this assertion, the present thesis aims first and foremost at providing - in addition to good quality empirical information and new statistical series - a new interpretation of patents in their structural and spatial dimensions, based on a cliometric approach. Our first contribution is to present the organisation of a new database on the evolution over a long period of time of patents in 40 countries from the XVIIth century up to 1945 and in over 150 countries from 1945 to the present time. We show in a second step that rare but nevertheless significant events conditioned the heartbeat of the economic history of patents. Wars, the promulgation of laws, the opening or closing of offices, but also purely statistical effects standardized over the long term the existence of patent systems through the application and granting of the series under study. Furthermore we determine the periodicity of our patent series using a spectral and co-spectral analysis. Finally we propose a more contemporary insight - in terms of convergence - into structural and more specifically spatial dynamics at work in the European countries patent systems.

This paper concerns itself with the methods of identifying outliers in an otherwise normally distributed data set. Several significant tests and criteria designed for this purpose are described here, Peirce's criterion, Chauvenet's criterion, Grubbs' test, Dixon's test and Cochran's test. Deriving of the tests and criteria is indicated and finally the results of the use of the test and criteria on simulated data with normal distribution and inserted outlier are looked into. Codes in programming language R with the implementation of these test and criteria using existing functions are included. Powered by TCPDF (www.tcpdf.org)

Master of Science / Department of Statistics / Weixin Yao / In this report, we propose a robust mixture of regression based on t-distribution by extending the mixture of t-distributions proposed by Peel and McLachlan (2000) to the regression setting. This new mixture of regression model is robust to outliers in y direction but not robust to the outliers with high leverage points. In order to combat this, we also propose a modified version of the proposed method, which fits the mixture of regression based on t-distribution to the data after adaptively trimming the high leverage points. We further propose to adaptively choose the degree of freedom for the t-distribution using profile likelihood. The proposed robust mixture regression estimate has high efficiency due to the adaptive choice of degree of freedom. We demonstrate the effectiveness of the proposed new method and compare it with some of the existing methods through simulation study.

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. Uma importante distinção se dá entre as técnicas supervisionadas e não supervisionadas. O presente trabalho enfoca as técnicas de detecção não supervisionadas. Existem dezenas de algoritmos desta categoria na literatura, porém cada um deles utiliza uma intuição própria do que deve ser considerado um outlier ou não, que é naturalmente um conceito subjetivo. Isso dificulta sensivelmente a escolha de um algoritmo em particular e também a escolha de uma configuração adequada para o algoritmo escolhido em uma dada aplicação prática. Isso também torna altamente complexo avaliar a qualidade da solução obtida por um algoritmo/configuração em particular adotados pelo analista, especialmente em função da problemática de se definir uma medida de qualidade que não seja vinculada ao próprio critério utilizado pelo algoritmo. Tais questões estão inter-relacionadas e se referem respectivamente aos problemas de seleção de modelos e avaliação (ou validação) de resultados em aprendizado de máquina não supervisionado. Neste trabalho foi desenvolvido um índice pioneiro para avaliação não supervisionada de detecção de outliers. O índice, chamado IREOS (Internal, Relative Evaluation of Outlier Solutions), avalia e compara diferentes soluções (top-n, i.e., rotulações binárias) candidatas baseando-se apenas nas informações dos dados e nas próprias soluções a serem avaliadas. O índice também é ajustado estatisticamente para aleatoriedade e extensivamente avaliado em vários experimentos envolvendo diferentes coleções de bases de dados sintéticas e reais. / Outlier detection (or anomaly detection) plays an important role in the pattern discovery from data that can be considered exceptional in some sense. An important distinction is that between the supervised and unsupervised techniques. In this work we focus on unsupervised outlier detection techniques. There are dozens of algorithms of this category in literature, however, each of these algorithms uses its own intuition to judge what should be considered an outlier or not, which naturally is a subjective concept. This substantially complicates the selection of a particular algorithm and also the choice of an appropriate configuration of parameters for a given algorithm in a practical application. This also makes it highly complex to evaluate the quality of the solution obtained by an algorithm or configuration adopted by the analyst, especially in light of the problem of defining a measure of quality that is not hooked on the criterion used by the algorithm itself. These issues are interrelated and refer respectively to the problems of model selection and evaluation (or validation) of results in unsupervised learning. Here we developed a pioneer index for unsupervised evaluation of outlier detection results. The index, called IREOS (Internal, Relative Evaluation of Outlier Solutions), can evaluate and compare different candidate (top-n, i.e., binary labelings) solutions based only upon the data information and the solution to be evaluated. The index is also statistically adjusted for chance and extensively evaluated in several experiments involving different collections of synthetic and real data sets.

As redes complexas surgiram como uma nova e importante maneira de representação e abstração de dados capaz de capturar as relações espaciais, topológicas, funcionais, entre outras características presentes em muitas bases de dados. Dentre as várias abordagens para a análise de dados, destacam-se a classificação e a detecção de outliers. A classificação de dados permite atribuir uma classe aos dados, baseada nas características de seus atributos e a detecção de outliers busca por dados cujas características se diferem dos demais. Métodos de classificação de dados e de detecção de outliers baseados em redes complexas ainda são pouco estudados. Tendo em vista os benefícios proporcionados pelo uso de redes complexas na representação de dados, o presente trabalho apresenta o desenvolvimento de um método baseado em redes complexas para detecção de outliers que utiliza a caminhada aleatória e um índice de dissimilaridade. Este método possibilita a identificação de diferentes tipos de outliers usando a mesma medida. Dependendo da estrutura da rede, os vértices outliers podem ser tanto aqueles distantes do centro como os centrais, podem ser hubs ou vértices com poucas ligações. De um modo geral, a medida proposta é uma boa estimadora de vértices outliers em uma rede, identificando, de maneira adequada, vértices com uma estrutura diferenciada ou com uma função especial na rede. Foi proposta também uma técnica de construção de redes capaz de representar relações de similaridade entre classes de dados, baseada em uma função de energia que considera medidas de pureza e extensão da rede. Esta rede construída foi utilizada para caracterizar mistura entre classes de dados. A caracterização de classes é uma questão importante na classificação de dados, porém ainda é pouco explorada. Considera-se que o trabalho desenvolvido é uma das primeiras tentativas nesta direção / Complex networks have emerged as a new and important way of representation and data abstraction capable of capturing the spatial relationships, topological, functional, and other features present in many databases. Among the various approaches to data analysis, we highlight classification and outlier detection. Data classification allows to assign a class to the data based on characteristics of their attributes and outlier detection search for data whose characteristics differ from the others. Methods of data classification and outlier detection based on complex networks are still little studied. Given the benefits provided by the use of complex networks in data representation, this study developed a method based on complex networks to detect outliers based on random walk and on a dissimilarity index. The method allows the identification of different types of outliers using the same measure. Depending on the structure of the network, the vertices outliers can be either those distant from the center as the central, can be hubs or vertices with few connections. In general, the proposed measure is a good estimator of outlier vertices in a network, properly identifying vertices with a different structure or a special function in the network. We also propose a technique for building networks capable of representing similarity relationships between classes of data based on an energy function that considers measures of purity and extension of the network. This network was used to characterize mixing among data classes. Characterization of classes is an important issue in data classification, but it is little explored. We consider that this work is one of the first attempts in this direction

O desenvolvimento tecnológico permite que diferentes dispositivos eletrônicos sejam capazes de executar cada vez mais um número maior de tarefas. Dentre estes dispositivos estão os dispositivos móveis, que pela utilização de uma bateria, agregam mobilidade e comodidade na execução de diferentes serviços, otimizando o tempo do usuário. Desta forma, o funcionamento do dispositivo está ligado diretamente ao tempo de vida da bateria, nesse contexto é importante o estudo acerca do desempenho e do comportamento da bateria frente a diferentes cenários de descarga. A predição do tempo de vida de baterias pode ser realizada através da modelagem matemática, que permite realizar a simulação de um processo de descarga real através de modelos matemáticos. Estes modelos são classificados em categorias: os modelos eletroquímicos, os modelos elétricos, os modelos analíticos, os modelos estocásticos, os modelos via teoria de identificação de sistemas e os modelos híbridos. Este trabalho é realizado utilizando a categoria de modelos híbridos. Estes modelos são constituídos através da união de pelo menos dois modelos pertencentes a categorias diferentes, conseguindo agregar as vantagens dos modelos utilizados nesta união. Neste sentido, o objetivo deste trabalho é realizar a modelagem matemática do tempo de vida de baterias utilizando os modelos híbridos encontrados na literatura técnica, realizando uma análise comparativa entre o nível de acurácia dos mesmos. São usados perfis de descarga constantes e os dados experimentais são obtidos de uma plataforma de testes, considerando baterias de Lítio Íon Polímero. Nos dados experimentais é realizado um tratamento estatístico, a fim de identificar a presença de valores outliers e médias experimentais diferentes estatisiticamente. As simulações computacionais são realizadas no software MatLab e as validações dos modelos híbridos ocorre através da comparação dos resultados das simulações com os dados obtidos da plataforma de testes. Após as validações, constatou-se que todos os modelos híbridos utilizados neste trabalho são acurados, apresentando erro médio inferior a 5%, independente da presença de valores outliers. Por fim, comparando os valores dos erros, é concluído que o modelo híbrido proposto por Zhang é o modelo mais acurado, seguido pelo modelo híbrido de Kim e de Gomes. Também foi possível observar que os menores erros foram encontrados na presença de valores outliers. / 99 f.

Detecção de outliers desempenha um importante papel para descoberta de conhecimento em grandes bases de dados. O estudo é motivado por inúmeras aplicações reais como fraudes de cartões de crédito, detecção de falhas em componentes industriais, intrusão em redes de computadores, aprovação de empréstimos e monitoramento de condições médicas. Um outlier é definido como uma observação que desvia das outras observações em relação a uma medida e exerce considerável influência na análise de dados. Embora existam inúmeras técnicas de aprendizado de máquina para tratar desse problemas, a maioria delas não faz uso de conhecimento prévio sobre os dados. Técnicas de aprendizado semissupervisionado para detecção de outliers são relativamente novas e incluem apenas um pequeno número de rótulos da classe normal para construir um classificador. Recentemente um modelo semissupervisionado baseado em rede foi proposto para classificação de dados empregando um mecanismo de competição e cooperação de partículas. As partículas são responsáveis pela propagação dos rótulos para toda a rede. Neste trabalho, o modelo foi adaptado a fim de detectar outliers através da definição de um escore de outlier baseado na frequência de visitas. O número de visitas recebido por um outlier é significativamente diferente dos demais objetos de mesma classe. Essa abordagem leva a uma maneira não tradicional de tratar os outliers. Avaliações empíricas sobre bases artificiais e reais demonstram que a técnica proposta funciona bem para bases desbalanceadas e atinge precisão comparável às obtidas pelas técnicas tradicionais de detecção de outliers. Além disso, a técnica pode fornecer novas perspectivas sobre como diferenciar objetos, pois considera não somente a distância física, mas também a formação de padrão dos dados / Outloier detection plays an important role for discovering knowledge in large data sets. The study is motivated by plethora of real applications such as credit card frauds, fault detection in industrial components, network instrusion detection, loan application precoessing and medical condition monitoring. An outlier is defined as an observation that deviates from other observations with respect to a measure and exerts a substantial influence on data analysis. Although numerous machine learning techniques have been developed for attacking this problem, most of them work with no prior knowledge of the data. Semi-supervised outlier detection techniques are reçlatively new and include only a few labels of normal class for building a classifier. Recently, a network-based semi-supervised model was proposed for data clasification by employing a mechanism based on particle competiton and cooperation. Such particle competition and cooperaction. Such particles are responsible for label propagation throughout the network. In this work, we adapt this model by defining a new outlier score based on visit frequency counting. The number of visits received by an outlier is significantly different from the remaining objects. This approach leads to an anorthodox way to deal with outliers. Our empirical ecaluations on both real and simulated data sets demonstrate that proposed technique works well with unbalanced data sets and achieves a precision compared to traditional outlier detection techniques. Moreover, the technique might provide new insights into how to differentiate objects because it considers not only the physical distance but also the pattern formation of the data

No description available.

We present a methodology for improving the detection of outlying Fire Service’s reports based on domain knowledge and dialogue with Fire & Rescue domain experts. The outlying report is considered as element which is significantly different from the remaining data. Outliers are defined and searched on the basis of domain knowledge and dialogue with experts. We face the problem of reducing high data dimensionality without loosing specificity and real complexity of reported incidents. We solve this problem by introducing a knowledge based generalization level intermediating between analysed data and experts domain knowledge. In the methodology we use the Formal Concept Analysis methods for both generation appropriate categories from data and as tools supporting communication with domain experts. We conducted two experiments in finding two types of outliers in which outliers detection was supported by domain experts.