Esta dissertação de mestrado tem por objetivo analisar os conjuntos-K, uma hierarquia de redes neurais biologicamente mais plausíveis, e aplicá-los ao problema de classificação de imagética motora através do eletroencefalograma (EEG). A imagética motora consiste no ato de processar um movimento motor da memória humana de longo tempo para a memória de curto prazo. A imagética motora deixa um rastro no sinal do EEG que torna possível a identificação e classificação dos diferentes movimentos motores. A tarefa de classificação de imagética motora através do EEG é reconhecida como complexa devido à não linearidade e quantidade de ruído da série temporal do EEG e da pequena quantidade de dados disponíveis para aprendizagem. Os conjuntos-K são um modelo conexionista que simula o comportamento dinâmico e caótico de populações de neurônios do cérebro e foram modelados com base em observações do sistema olfatório feitas por Walter Freeman. Os conjuntos-K já foram aplicados em diversos domínios de classificação diferentes, incluindo EEG, tendo demonstrado bons resultados. Devido às características da classificação de imagética motora, levantou-se a hipótese de que a aplicação dos conjuntos-K na tarefa pudesse prover bons resultados. Um simulador para os conjuntos-K foi construído para a realização dos experimentos. Não foi possível validar a hipótese levantada no trabalho, dado que os resultados dos experimentos realizados com conjuntos-K e imagética motora não apresentaram melhorias significativas para a tarefa nas comparações realizadas. / This dissertation aims to examine the K-sets, a hierarchy of biologically plausible neural networks, and apply them to the problem of motor imagery classification through electroencephalogram (EEG). Motor imagery is the act of processing a motor movement from long-term to short-term memory. Motor imagery leaves a trail in the EEG signal, which makes possible the identification and classification of different motor movements. Motor imagery classification is a complex problem due to non-linearity of the EEG time series, low signal-to-noise ratio, and the small amount of data typically available for learning. K-sets are a connectionist model that simulates the dynamic and chaotic behavior of populations of neurons in the brain, modeled based on observations of the olfactory system by Walter Freeman. K-sets have already been used in several different classification domains, including EEG, showing good results. Due to the characteristics of motor imagery classification, a hypothesis that the application of K-sets in the task could provide good results was raised. A simulator for K-sets was created for the experiments. Unfortunately, the hypothesis could not be validated, as the results of the conducted experiments with K-sets and motor imagery showed no significant improvements in comparison in the task performed.

Esta dissertação descreve a aplicação do KIII, um modelo de rede neural biologicamente mais plausível, para a previsão de séries temporais econômicas. Os conjuntos K são modelos conexionistas baseados em populações de neurônios e foram usados em muitas aplicações de aprendizado de máquina, incluindo previsões de séries temporais. Nesta dissertação, este método foi aplicado ao IPCA, um índice de preços ao consumidor brasileiro pesquisado pelo IBGE em 13 regiões metropolitanas. Os valores abrangem o período de agosto de 1994 a junho de 2017. Os experimentos foram realizados utilizando quatro modelos não-paramétricos (KIII, kNN contínuo, RNAs clássicas e SVM) e seis métodos paramétricos: ARIMA, SARIMA, Médias Móveis, SES, Holt, Holt-Winters Aditivo e Holt-Winters Multiplicativo. A médida estatística RMSE foi utilizada para comparar o desempenho dos métodos. Os conjuntos KIII de Freeman funcionaram bem como um filtro, melhorando o desempenho do método, mas não foram um bom método de previsão, sendo superado, na maior parte dos experimentos, por outros métodos de previsão de séries temporais. Esta dissertação contribui com o uso de modelos não paramétricos para prever a inflação em um país em desenvolvimento. / This thesis describes the application of KIII, a biologically more plausible neural network model, for forecasting economic time series. K-sets are connectionist models based on neural populations and have been used in many machine learning applications, including time series prediction. In this thesis, this method was applied to IPCA, a Brazilian consumer price index surveyed by IBGE in 13 metropolitan areas. The values ranged from August 1994 to June 2017. Experiments were performed using four non-parametric models (KIII, continuous kNN, classical ANN, and SVM) and four parametric methods: ARIMA, SARIMA, Moving Average, SES, Holt, Additive HoltWinters, and Multiplicative HoltWinters. The statistical metric RMSE was used to compare methods performance. Freemans KIII sets worked well as filter, improving method performance, but it was not a good prediction method, and was overcome in most experiments by other time series prediction methods. This thesis contributes with the use of non-parametrics models for forecasting inflation in a developing country.

Esta tesis se divide en dos partes. La primera parte contiene el estudio de tres pesos o profundidades, asociados a conjuntos finitos de puntos en el plano: el peso definido por las capas convexas, convex depth (introducido por Hubert (72) y Barnett (76)), la separabilidad lineal, también conocido por location, halfspace o Tukey depth (Tukey 75) y el peso Delaunay (Green 81). De la noción de peso, se obtiene una estratificación de los conjuntos de puntos en el plano en capas y una partición del plano en regiones o niveles, cuyas fronteras son conocidas por depth contours. Se definen los conceptos de capa y nivel en los tres pesos señalados y se estudian sus propiedades y complejidades. Chazelle obtuvo métodos para hallar en tiempo óptimo las capas convexas, que coinciden con las fronteras de los niveles convexos. En esta tesis, para los pesos de separabilidad lineal y Delaunay, se proporcionan algoritmos de obtención, tanto de capas como de niveles, y de cálculo del peso de un punto nuevo que se incorpore a la nube. De forma independiente, han sido obtenidos para el peso de la separabilidad lineal los algoritmos de construcción de los niveles, location depth contours, y el de cálculo del peso de un punto nuevo, por Miller et al. (01). Para los tres pesos mencionados, se analizan árboles generadores, poligonizaciones o triangulaciones, con peso mínimo, donde el peso se ha considerado como la suma de los pesos de las aristas de dichas estructuras. Se obtienen propiedades generales entorno a la caracterización de tales estructuras y algoritmos de obtención para alguna de ellas. Se definen dos pesos relacionados con la separabilidad mediante cuñas: el peso según dominación isotética y la separabilidad . En ambos, se dan algoritmos para el cálculo de los pesos de los puntos de un conjunto dado. La separabilidad  está estrechamente relacionada con la enumeración eficiente de (,k)-sets. Se realiza un estudio combinatorio del conjunto de (,k)-sets para nubes de puntos en el plano y se describen algoritmos de construcción de todos los (,k)-sets en cada uno de los cuatro casos posibles, según sean,  o k, fijos o variables. En la segunda parte, se tratan diversos problemas de transversalidad. Se obtienen resultados acerca de la caracterización de las permutaciones realizables, tanto como polígonos simples, como convexos, sobre arreglos de rectas. Para colecciones de segmentos en el plano, se definen cuña y círculo transversales separadores. Se realiza un análisis del orden de estos elementos transversales separadores y se obtienen diversos algoritmos de decisión de existencia de los mismos y construcción de todos ellos. Para colecciones de círculos, también se define el círculo transversal separador y se obtiene un algoritmo de existencia y construcción de dichos círculos para círculos con el mismo radio. / This thesis can be divided into two parts. The first part contains the study of three weights or depths associated to finite point sets in the plane: the convex depth convex hull peeling depth (introduced by Hubert (72) and Barnett (76)), the location depth (also known by halfspace or Tukey depth (Tukey (75)), and the Delaunay depth (Green (81)).From any notion of depth, a stratification of the point sets of the plane into layers and a partition of the plane into regions or levels are obtained. The boundaries of the levels are known by depth contours. We define the concepts of layers and levels for all three depths and we study their properties and their complexities. Chazelle obtained methods to find the layers, which are the boundaries of the convex levels, with an optimal time algorithm. We present the algorithms for constructing the layers and levels, in location and Delaunay depths. Also, for both depths, we show algorithms to calculate the depth of a new point joining the cloud. In an independent way, the algorithms to obtain the levels (location depth contours) and to calculate the location depth of a new point, are obtained by Miller et al. (01).For each one of the three mentioned depths, we study the geometric structures (spanning trees, polygonizations and triangulations) with minimum weight, where this weight has been considered as t-weight (the addition of the weight of their edges). We obtain general properties about the characterization of such structures and some algorithms to obtain them. We define two depths related with the separability by wedges: the isothetic-domination and the -separability which generalizes the location depth. We develop the algorithms in order to obtain the depths of all points of a given set in both cases. The -separability (in particular the location depth) is closely related with the efficient enumeration of the (,k)-sets. We make a combinatorial study of the (,k)-sets for point sets in the plane. We give lower and upper bounds for the maximum number of the (,k)-sets and we give algorithms for constructing all them, in each one of the four cases according to the case where  or k are fixed or variable.In the second part, we consider some transversality problems. We obtain results about the characterization of the realizable permutations both as simple and as convex polygons, over arrangements of lines. We also study some transversality problems with wedges and circles. We have defined the separating transversal wedge and the separating transversal circle for sets of segments. We analyze the size of the set of the transversal elements. Furthermore, we obtain some decision algorithms on the existence and construction of all of them. Finally, we define also the separating transversal circle for sets of circles and we obtain an algorithm for sets of circles with the same radius.

Esta dissertação descreve a aplicação do KIII, um modelo de rede neural biologicamente mais plausível, para a previsão de séries temporais econômicas. Os conjuntos K são modelos conexionistas baseados em populações de neurônios e foram usados em muitas aplicações de aprendizado de máquina, incluindo previsões de séries temporais. Nesta dissertação, este método foi aplicado ao IPCA, um índice de preços ao consumidor brasileiro pesquisado pelo IBGE em 13 regiões metropolitanas. Os valores abrangem o período de agosto de 1994 a junho de 2017. Os experimentos foram realizados utilizando quatro modelos não-paramétricos (KIII, kNN contínuo, RNAs clássicas e SVM) e seis métodos paramétricos: ARIMA, SARIMA, Médias Móveis, SES, Holt, Holt-Winters Aditivo e Holt-Winters Multiplicativo. A médida estatística RMSE foi utilizada para comparar o desempenho dos métodos. Os conjuntos KIII de Freeman funcionaram bem como um filtro, melhorando o desempenho do método, mas não foram um bom método de previsão, sendo superado, na maior parte dos experimentos, por outros métodos de previsão de séries temporais. Esta dissertação contribui com o uso de modelos não paramétricos para prever a inflação em um país em desenvolvimento. / This thesis describes the application of KIII, a biologically more plausible neural network model, for forecasting economic time series. K-sets are connectionist models based on neural populations and have been used in many machine learning applications, including time series prediction. In this thesis, this method was applied to IPCA, a Brazilian consumer price index surveyed by IBGE in 13 metropolitan areas. The values ranged from August 1994 to June 2017. Experiments were performed using four non-parametric models (KIII, continuous kNN, classical ANN, and SVM) and four parametric methods: ARIMA, SARIMA, Moving Average, SES, Holt, Additive HoltWinters, and Multiplicative HoltWinters. The statistical metric RMSE was used to compare methods performance. Freemans KIII sets worked well as filter, improving method performance, but it was not a good prediction method, and was overcome in most experiments by other time series prediction methods. This thesis contributes with the use of non-parametrics models for forecasting inflation in a developing country.

Esta dissertação de mestrado tem por objetivo analisar os conjuntos-K, uma hierarquia de redes neurais biologicamente mais plausíveis, e aplicá-los ao problema de classificação de imagética motora através do eletroencefalograma (EEG). A imagética motora consiste no ato de processar um movimento motor da memória humana de longo tempo para a memória de curto prazo. A imagética motora deixa um rastro no sinal do EEG que torna possível a identificação e classificação dos diferentes movimentos motores. A tarefa de classificação de imagética motora através do EEG é reconhecida como complexa devido à não linearidade e quantidade de ruído da série temporal do EEG e da pequena quantidade de dados disponíveis para aprendizagem. Os conjuntos-K são um modelo conexionista que simula o comportamento dinâmico e caótico de populações de neurônios do cérebro e foram modelados com base em observações do sistema olfatório feitas por Walter Freeman. Os conjuntos-K já foram aplicados em diversos domínios de classificação diferentes, incluindo EEG, tendo demonstrado bons resultados. Devido às características da classificação de imagética motora, levantou-se a hipótese de que a aplicação dos conjuntos-K na tarefa pudesse prover bons resultados. Um simulador para os conjuntos-K foi construído para a realização dos experimentos. Não foi possível validar a hipótese levantada no trabalho, dado que os resultados dos experimentos realizados com conjuntos-K e imagética motora não apresentaram melhorias significativas para a tarefa nas comparações realizadas. / This dissertation aims to examine the K-sets, a hierarchy of biologically plausible neural networks, and apply them to the problem of motor imagery classification through electroencephalogram (EEG). Motor imagery is the act of processing a motor movement from long-term to short-term memory. Motor imagery leaves a trail in the EEG signal, which makes possible the identification and classification of different motor movements. Motor imagery classification is a complex problem due to non-linearity of the EEG time series, low signal-to-noise ratio, and the small amount of data typically available for learning. K-sets are a connectionist model that simulates the dynamic and chaotic behavior of populations of neurons in the brain, modeled based on observations of the olfactory system by Walter Freeman. K-sets have already been used in several different classification domains, including EEG, showing good results. Due to the characteristics of motor imagery classification, a hypothesis that the application of K-sets in the task could provide good results was raised. A simulator for K-sets was created for the experiments. Unfortunately, the hypothesis could not be validated, as the results of the conducted experiments with K-sets and motor imagery showed no significant improvements in comparison in the task performed.

Cette thèse est une contribution à un problème classique de la géométrie algorithmique et combinatoire : l’étude des k-sets d’un ensemble V de n points du plan. Nous introduisons d’abord la notion de chaîne d’inclusion de convexes qui est un ordonnancement des points de V tel qu’aucun point n’appartient à l’enveloppe convexe de ceux qui le précèdent. Tout k-set d’une sous-suite commençante de la chaîne est appelé un k-set de la chaîne. Nous montrons que le nombre de ces k-sets est un invariant de V et qu’il est égal au nombre de régions du diagramme de Voronoï d’ordre k de V. Nous en déduisons un algorithme en ligne pour construire les k-sets des sommets d’une ligne polygonale simple dont chaque sommet est à l’extérieur de l’enveloppe convexe des sommets qui le précèdent sur la ligne. Si c est le nombre total de k-sets construits, la complexité de notrealgorithme est en O(n log n+c log^2 k) et est équivalente, par k-set construit, à celle du meilleur algorithme connu. Nous montrons ensuite que la méthode algorithmique classique de division-fusion peut être adaptée à la construction des k-sets de V. L’algorithme qui en résulte a une complexité enO(n log n+c log^2 k log(n/k)), où c est le nombre maximum de k-sets d’un ensemble de n points.Nous prouvons enfin que les centres de gravité des k-sets d’une chaîne d’inclusion de convexes sont les sommets d’une triangulation qui appartient à la même famille de triangulations, dites centroïdes, que le dual du diagramme de Voronoï d’ordre k. Nous en d´déduisons un algorithme qui construit des triangulations centroïdes particulières en temps O(n log n+k(n-k) log^2 k), ce qui est plus efficace que les algorithmes connus jusque là. / This thesis is a contribution to a classical problem in computational and combinatorial geometry: the study of the k-sets of a set V of n points in the plane. First we introduce the notion of convex inclusion chain that is an ordering of the points of V such that no point is inside the convex hull of the points that precede it. Every k-set of an initial sub-sequence of the chain is called a k-set of the chain. We prove that the number of these k-sets is an invariant of V and is equal to the number of regions in the order-k Voronoi diagram of V. We then deduce an online algorithm for the construction of the k-sets of the vertices of a simple polygonal line such that every vertex of this line is outside the convex hull of all its preceding vertices on the line. If c is the total number of k-sets built with this algorithm, the complexity of our algorithm is in O(n log n + c log^2k) and is equal, per constructed k-set, to the complexity of the best algorithm known. Afterward, we prove that the classical divide and conquer algorithmic method can be adapted to the construction of the k-sets of V. The algorithm has a complexity of O(n log n + c log^2k log(n/k)), where c is the maximum number of k-sets of a set of n points. We finally prove that the centers of gravity of the k-sets of a convex inclusion chain are the vertices of a triangulation belonging to the family of so-called centroid triangulations. This family notably contains the dual of the order-k Voronoi diagram. We give an algorithm that builds particular centroid triangulations in O(n log n + k(n- k) log^2 k) time, which is more efficient than all the currently known algorithms.