Submitted by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:41Z No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:55Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:27:03Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Made available in DSpace on 2017-10-09T16:27:11Z (GMT). No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) Previous issue date: 2017-05-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Let G = (V, E) be a simple and undirected graph. An edge-coloring is an assignment of colors to the edges of the graph such that any two adjacent edges receive different colors. The chromatic index of a graph G is the smallest number of colors such that G has an edge-coloring. Clearly, a lower bound for the chromatic index is the degree of the vertex of higher degree, denoted by ?(G). In 1964, Vizing proved that chromatic index is ?(G) or ?(G) + 1. The Classification Problem is to determine if the chromatic index is ?(G) (Class 1 ) or if it is ?(G) + 1 (Class 2 ). Let n be number of vertices of a graph G and let m be its number of edges. We say G is overfull if m > (n-1) 2 ?(G). Every overfull graph is Class 2. A graph is subgraph-overfull if it has a subgraph with same maximum degree and it is overfull. It is well-known that every overfull and subgraph-overfull graph is Class 2. The Overfull Conjecture asserts that every graph with ?(G) > n 3 is Class 2 if and only if it is subgraph-overfull. In this work we prove the Overfull Conjecture to a particular class of graphs, known as split-comparability graphs. The Overfull Conjecture was open to this class. / Dado um grafo simples e não direcionado G = (V, E), uma coloração de arestas é uma função que atribui cores às arestas do grafo tal que todas as arestas que incidem em um mesmo vértice têm cores distintas. O índice cromático é o número mínimo de cores para obter uma coloração própria das arestas de um grafo. Um limite inferior para o índice cromático é, claramente, o grau do vértice de maior grau, denotado por ?(G). Em 1964, Vizing provou que o índice cromático ou é ?(G) ou ?(G) + 1, surgindo assim o Problema da Classificação, que consiste em determinar se o índice cromático é ?(G) (Classe 1 ) ou ?(G) + 1 (Classe 2 ). Seja n o número de vértices de um grafo G e m seu número de arestas. Dizemos que um grafo é sobrecarregado se m > (n-1) 2 ?(G). Um grafo é subgrafo-sobrecarregado se tem um subgrafo de mesmo grau máximo que é sobrecarregado. É sabido que se um grafo é sobrecarregado ou subgrafo-sobrecarregado ele é necessariamente Classe 2. A Conjectura Overfull é uma famosa conjectura de coloração de arestas e diz que um grafo com ?(G) > n 3 é Classe 2 se e somente se é subgrafo-sobrecarregado. Neste trabalho provamos a Conjectura Overfull para uma classe de grafos, a classe dos grafos split-comparabilidade. Até este momento a Conjectura Overfull estava aberta para esta classe.

In this study, to increase inference speed of convolutional neural networks, the optimization technique low-rank tensor decomposition has been implemented and applied to AlexNet which had been trained to classify dog breeds. Due to a small training set, transfer learning was used in order to be able to classify dog breeds. The purpose of the study is to investigate how effective low-rank tensor decomposition is when the training set is limited. The results obtained from this study, compared to a previous study, indicate that there is a strong relationship between the effects of the tensor decomposition and how much available training data exists. A significant speed up can be obtained in the different convolutional layers using tensor decomposition. However, since there is a need to retrain the network after the decomposition and due to the limited dataset there is a slight decrease in accuracy. / För att öka inferenshastigheten hos faltningssnätverk, har i denna studie optimeringstekniken low-rank tensor decomposition implementerats och applicerats på AlexNet, som har tränats för att klassificera hundraser. På grund av en begränsad mängd träningsdata användes transfer learning för uppgiften. Syftet med studien är att undersöka hur effektiv low-rank tensor decomposition är när träningsdatan är begränsad. Jämfört med resultaten från en tidigare studie visar resultaten från denna studie att det finns ett starkt samband mellan effekterna av low-rank tensor decomposition och hur mycket tillgänglig träningsdata som finns. En signifikant hastighetsökning kan uppnås i de olika faltningslagren med hjälp av low-rank tensor decomposition. Eftersom det finns ett behov av att träna om nätverket efter dekompositionen och på grund av den begränsade mängden data så uppnås hastighetsökningen dock på bekostnad av en viss minskning i precisionen för modellen.

在目前的企業環境中，很多企業致力於管理和應用組織知識，來維持他們的核心能力和創造競爭優勢。有效率的管理組織知識，能減少解決問題的時間和成本，並增加組織學習和創新能力。並且，由於累積知識資源的需求，很多企業開始發展知識庫，以儲存組織及個人的知識，用來增加組織整體的效率、支援日常的運作以及企業策略的操作。 知識管理是現代的典範，可用來有效管理組織知識，進而改善組織績效。知識管理的目的是強調管理知識的流動及流程。在知識管理流程方面，主要區分為知識擷取、整合、儲存/歸類、散播和應用知識等程序。另外，資訊技術可用來協助知識管理，並能使知識管理更有效率。知識管理的主要議題之ㄧ是知識的擷取，由於目前知識來源的提供，主要是透過知識工作者，可是它對於知識工作者而言，是一種額外的負擔。因此，設計一個有效的方法來自動產生組織知識，以減輕他們的額外負擔，將是一個很重要的課題。第二個相當重要的議題是知識整合，由於不同來源的知識，可能造成組織知識的衝突，因此設計一個知識整合方法，把不同來源的知識整合成一個完整的知識，組織將會逐漸增加這方面的需求。 分類在很多應用中是常遭遇的問題，例如財務預測、疾病診斷等。在過去，分類規則常藉由決策樹的方法所產生，並用於解決分類的問題。在本論文中，提出兩個以遺傳規劃為基礎的知識擷取方法和兩個以遺傳規劃為基礎的知識整合方法，分別支援知識管理流程中的知識擷取和知識整合。 在兩個所提的知識擷取方法中，第一個方法是著重在快速和容易地找到想要的分類樹，但是，此方法可能會產生結構較複雜的分類樹。第二個方法是修正第一個方法，產生一個較精簡和應用性高的分類樹。這些所獲得的分類樹，能被轉換成規則集合，並匯入知識庫中，幫助企業決策的制定和日常的運作。 此外，在兩個所提的知識整合方法中，第一個方法，能自動結合多重的知識來源成為一個整合的知識，並可匯入知識庫中，但是此方法只考慮到單一時間點的整合。第二個方法則是可以解決不同時間點的知識整合問題。另外，本論文提出三個新的遺傳運算子，在演化過程中，可用來解決規則集合中有重複、包含和衝突等常見的問題，因而可以產生較精簡及一致性高的分類規則。最後，本論文採用信用卡資料及乳癌資料來驗證所提方法的可行性，實驗結果皆獲得良好的成效。 / In today’s business environment, many enterprises make efforts in managing and applying organizational knowledge to sustain their core competence and create competitive advantage. The effective management of organizational knowledge can reduce the time and cost of solving problems, improve organizational performance, and increase organizational learning as well as innovative competence. Moreover, due to the need to accumulate knowledge resources, many enterprises have devoted to developing their knowledge repositories. These repositories store organizational and individual knowledge that are used to increase overall organization efficiency, support daily operations, and implement business strategies. Knowledge management (KM) is the modern paradigm for effective management of organizational knowledge to improve organizational performance. The intent of KM is to emphasize knowledge flows and the main process of acquisition, integration, storage/categorization, dissemination, and application. Furthermore, extant information technologies can provide a way of enabling more effective knowledge management. One of the important issues in knowledge management is knowledge acquisition. It is an extra burden for knowledge workers to contribute their knowledge into repositories, such that designing an effective method for abating an extra burden to automatically generate organizational knowledge will play a critical role in knowledge management. A second rather important issue in knowledge management is knowledge integration from different knowledge sources. Designing a knowledge-integration method to combine multiple knowledge sources will gradually become a necessity for enterprises. Classification problems, such as financial prediction and disease diagnosis, are often encountered in many applications. In the past, classification trees were often generated by decision-tree methods and commonly used to solve classification problems. In this dissertation, we propose two GP-based knowledge-acquisition methods and two GP-based knowledge-integration methods to support knowledge acquisition and knowledge integration respectively in the knowledge management processes for classification tasks. In the two proposed knowledge-acquisition methods, the first one is fast and easy to find the desired classification tree. It may, however, generate a complicated classification tree. The second method then further modifies the first method and produces a more concise and applicatory classification tree than the first one. The classification tree obtained can be transferred into a rule set, which can then be fed into a knowledge base to support decision making and facilitate daily operations. Furthermore, in the two proposed knowledge-integration methods, the former method can automatically combine multiple knowledge sources into one integrated knowledge base; nevertheless, it focuses on a single time point to deal with such knowledge-integration problems. The latter method then extends the former one to handle integrating situations properly with different time points. Additionally, three new genetic operators are designed in the evolving process to remove redundancy, subsumption and contradiction, thus producing more concise and consistent classification rules than those without using them. Finally, the proposed methods are applied to credit card data and breast cancer data for evaluating their effectiveness. They are also compared with several well-known classification methods. The experimental results show the good performance and feasibility of the proposed approaches.

Dans cette thèse nous étudierons des problématiques de graphes. Nous proposons deux études théoriques sur la recherche et l'énumération de cliques et quasi-cliques. Ensuite nous proposons une étude appliquée sur la propagation d'information dans un graphe d'entités nommées. Premièrement, nous étudierons la recherche de cliques dans des graphes compressés. Les problèmes MCE et MCP sont des problèmes rencontrés dans l'analyse des graphes. Ce sont des problèmes difficiles, pour lesquels des solutions adaptées doivent être conçues pour les grands graphes. Nous proposons de travailler sur une version compressée du graphe. Nous montrons les bons résultats obtenus par notre méthode pour l'énumération de cliques maximales. Secondement, nous étudierons l'énumération de quasi-cliques maximales. Nous proposons un algorithme distribué qui énumère l'ensemble des quasi-cliques maximales. Nous proposons aussi une heuristique qui liste des quasi-cliques plus rapidement. Nous montrons l'intérêt de l'énumération de ces quasi-cliques par une évaluation des relations en regardant la co-occurrence des noeuds dans l'ensemble des quasi-cliques énumérées. Troisièmement, nous travaillerons sur la diffusion d'événements dans un graphe d'entités nommées. De nombreux modèles existent pour simuler des problèmes de diffusion de rumeurs ou de maladies dans des réseaux sociaux ou des problèmes de propagation de faillites dans les milieux bancaires. Nous proposons de répondre au problème de diffusion d'événements dans des réseaux hétérogènes représentant un environnement économique du monde. Nous proposons un problème de diffusion, nommé problème de classification de l'infection, qui consiste à déterminer quelles entités sont concernées par un événement. Pour ce problème, nous proposons deux modèles inspirés du modèle de seuil linéaire auxquels nous ajoutons différentes fonctionnalités. Finalement, nous testons et validons nos modèles sur un ensemble d'événements / In this thesis we will study graph problems. We will study theoretical problems in pattern research and applied problems in information diffusion. We propose two theoretical studies on the identification/detection and enumeration of dense subgraphs, such as cliques and quasi-cliques. Then we propose an applied study on the propagation of information in a named entities graph. First, we will study the identification/detection of cliques in compressed graphs. The MCE and MCP are problems that are encountered in the analysis of data graphs. These problem are difficult to solve (NP-Hard for MCE and NP-Complete for MCP), and adapted solutions must be found for large graphs. We propose to solve these problems by working on a compressed version of the initial graph. We show the correct results obtained by our method for the enumeration of maximal cliques on compressed graphs. Secondly, we will study the enumeration of maximal quasi-cliques. We propose a distributed algorithm that enumerates the set of maximal quasi-cliques of the graph. We show that this algorithm lists the set of maximal quasi-cliques of the graph. We also propose a heuristic that lists a set of quasi-cliques more quickly. We show the interest of enumerating these quasi-cliques by an evaluation of relations by looking at the co-occurrence of nodes in the set of enumerated quasi-cliques. Finally, we work on the event diffusion in a named entities graph. Many models exist to simulate diffusion problems of rumors or diseases in social networks and bankruptcies in banking networks. We address the issue of significant events diffusion in heterogeneous networks, representing a global economic environment. We propose a diffusion problem, called infection classification problem, which consists to dertemine which entities are concerned by an event. To solve this problem we propose two models inspired by the linear threshold model to which we add different features. Finally, we test and validate our models on a set of events

[pt] Os sistemas de inferência fuzzy são técnicas de aprendizado de máquina que possuem a capacidade de modelar incertezas matematicamente. Eles são divididos em sistemas de inferências fuzzy tipo-1 e fuzzy tipo-2. O sistema de inferência fuzzy tipo-1 vem sendo amplamente aplicado na solução de diversos problemas referentes ao aprendizado de máquina, tais como, controle, classificação, clusterização, previsão, dentre outros. No entanto, por apresentar uma melhor modelagem matemática das incertezas, o sistema de inferência fuzzy tipo-2 vem ganhando destaque ao longo dos anos. Esta melhora modelagem vem também acompanhada de um aumento do esforço matemático e computacional. Visando reduzir tais pontos para solucionar problemas de classificação, este trabalho apresenta o desenvolvimento e a comparação de duas funções de pertinência Gaussiana para um sistema de inferência fuzzy tipo-2 intervalar usando o método superior e inferior. São utilizadas as funções de pertinência Gaussiana com incerteza na média e com incerteza no desvio padrão. Ambos os modelos fuzzy abordados neste trabalho são treinados por algoritmos baseados em informações de primeira ordem. Além disso, este trabalho propõe a extensão dos modelos fuzzy tipo-2 intervalar para apresentarem múltiplas saídas, reduzindo significativamente o custo computacional na solução de problemas de classificação multiclasse. Finalmente, visando contextualizar a utilização desses modelos em aplicações de engenharia mecânica, este trabalho apresenta a solução de um problema de detecção de falhas em turbinas a gás, utilizadas em aeronaves. / [en] Fuzzy logic systems are machine learning techniques that can model mathematically uncertainties. They are divided into type-1 fuzzy, and type-2 fuzzy logic systems. The type-1 fuzzy logic system has been widely applied to solve several problems related to machine learning, such as control, classification, clustering, prediction, among others. However, as it presents a better mathematical modeling of uncertainties, the type-2 fuzzy logic system has received much attention over the years. This modeling improvement is also accompanied by an increase in mathematical and computational effort. Aiming to reduce these issues to solve classification problems, this work presents the development and comparison of two Gaussian membership functions for a type-2 interval fuzzy logic system using the upper and lower method. Gaussian membership functions with uncertainty in the mean and with uncertainty in the standard deviation are used. Both fuzzy models covered in this work are trained by algorithms based on first order information. Furthermore, this work proposes the extension of interval type-2 fuzzy models to present multiple outputs, significantly reducing the computational cost in solving multiclass classification problems. Finally, aiming to contextualize the use of these models in mechanical engineering applications, this work presents the solution of a problem of fault detection in aircraft gas turbines.