[pt] Devido ao grande aumento da competitividade e da, cada vez maior, demanda por eficiência, muitas empresas perceberam que é necessário repensar e melhorar seus processos. Para atingir este objetivo, elas têm cada vez mais buscado técnicas computacionais que sejam capazes de extrair novas informações e conhecimentos de suas grandes bases de dados. Os processos das empresas, normalmente, possuem momentos em que uma decisão deve ser tomada. É razoável esperar que casos similares tenham decisões parecidas sendo tomadas ao longo do processo. O objetivo desta dissertação é criar um minerador de decisão que seja capaz the automatizar a tomada de decisão dentro de um processo. A primeira parte do trabalho consiste na identificação dos pontos de decisão em uma rede de Petri. Em seguida, transformamos a tomada de decisão em um problema de classificação no qual cada possibilidade da decisão se torna uma classe. Para fazer a automatização, é utilizada uma árvore de decisão treinada com os atributos dos dados que estão presentes nos logs dos eventos. Um estudo de caso real é utilizado para validar que o minerador de decisão é confiável para processos reais. / [en] Due to the increasing competitiveness and demand for higher performance, many companies realized that it is necessary to rethink and enhance their business processes. In order to achieve this goal, companies have been turning to computational techniques that are capable of extracting new information and insights from their, ever-increasing, datasets. Business processes, normally, have many places where a decision has to be made. It is reasonable to expect that similar inputs have the same decisions made to them during the process. The goal of this dissertation is to create a decision miner that automates the decision-making inside a process. First, we will identify decision points in a Petri net model. Then, we will transform the decision-making problem into a classification one, where each of the possible decisions becomes a class. In order to automate the decision-making, a decision tree is trained using data attributes from the event logs. A real world case study is used to validate that the decision miner is reliable when using real world data.

Air traffic communication is one of the most vital systems for air traffic management controllers. It is used every day to allow millions of people to travel safely and efficiently across the globe. But many of the systems considered industry-standard are used without any sort of encryption and authentication meaning that they are vulnerable to different wireless attacks. In this thesis vulnerabilities within an air traffic management system called ADS-B will be investigated. The structure and theory behind this system will be described as well as the reasons why ADS-B is unencrypted. Two attacks will then be implemented and performed in an open-source air traffic management simulator called openScope. ADS-B data from these attacks will be gathered and combined with actual ADS-B data from genuine aircrafts. The collected data will be cleaned and used for machine learning purposes where three different algorithms will be applied to detect attacks. Based on our findings, where two out of the three machine learning algorithms used were able to detect 99.99% of the attacks, we propose that machine learning algorithms should be used to improve ADS-B security. We also think that educating air traffic controllers on how to detect and handle attacks is an important part of the future of air traffic management.

Geografiska informationssystems användning blir allt viktigare i dagens samhälle där spatiala data kan lagras, hämtas, analyseras och visualiseras. Genom att sammanställa spatiala data kan en bild av verkligheten abstraheras. Detaljerad information om vägnat och företeelser (refuger, bullerplank, skyltar etcetera) för analys leder till ett effektivare drift- och underhållsarbete. Vilket i sin tur ger en ökad framkomlighet för trafikanter. Teknikföretaget Triona har en kartapplikation där utmaningar har uppstått gällande algoritmisk knytning av inmätta refuger (benämnd Norge-datasamlingen) till det norska vägnatet. En refug ar en upphöjning i gatan som avgränsar körfalt och påminner om en trottoar i utseendet. Denna fallstudie behandlade ett delproblem där klassificering av refuger skulle kunna underlätta knytningen och förutsättningarna for analys. Syftet med studien kan sammanfattas till att presentera förslag på metoder for att klassificera refugerna med övervakad maskininlärning. Med algoritmerna K-nearest neighbors (KNN) och Decision tree studerades möjligheten att automatiskt klassificera refugerna. En refug bestod av en vektorpolygon vilket är en lista med koordinater. Polygonens hörn bestod av koordinatparen latitud och longitud. Norge-datasamlingen var inte i forväg kategoriserad till sina elva typer och kunde därfor inte anvandas. En datasamling med 2157 refuger med sju typer från Portland, USA tillämpades i stället. De spatiala vektorpolygonerna transformerades med Elliptical Fourier Descriptors (EFD). Maskinlärningsmodellerna tränades på att klassificera refugerna baserat på matematiska approximationer av dess konturer från EFD. Slutsatser kunde dras genom att refugtypernas konturer analyserades och prestationer observerades. Prestationer utvärderades utifrån traffsäkerhet med kompletterande mätvarden som precision och återkallelse på Portland-datasamlingen. Traffsäkerhet är andelen rätta klassificeringar av refugerna. KNN uppnådde 64 % och Decisiontree 69 % traffsäkerhet. Då båda datasamlingarna var verkliga exempel på refuger i vägnat kunde ett antagande göras att det inte skulle bli en mycket högre traffsäkerhet om studiens metod appliceras på Norge-datasamlingen. Modellernas prestationer bedömdes därmed inte vara tillrackligt bra for en rekommendation. / Geographical information systems are becoming increasingly important in today´s society where spatial data can be stored, collected, analysed, and visualized. By compiling spatial data reality can be abstracted. Detailed information on road networks and objects (traffic islands, noise barriers, signs, etcetera) for analysis leads to more efficient operation and maintenance work. Which in turn provides increased accessibility for road users. The technology company Triona has a map application where algorithmic connection of traffic islands (Norway-dataset) to the Norwegian road network has been challenging. A traffic island is an elevation in the street that delimits lanes and is reminiscent of a sidewalk in appearance. This case study addressed a sub-problem where classification of traffic islands could facilitate the connection and prerequisites for analysis. The aim was to present methods that could classify the traffic islands with supervised machine learning. With the algorithms K-nearest neighbors (KNN) and Decision tree, the possibility of automatically classifying the traffic islands was studied. A traffic island consisted of a vector polygon which is a list storing its corners (latitude and longitude). The Norway-dataset was not previously labelled into its eleven types. A data collection of 2157 refuges with seven types from Portland, USA was therefore applied instead. The traffic islands were transformed with Elliptical Fourier Descriptors which extracted an approximation of its contours to train the machine learning models on. Conclusions could be drawn by analysing the contours and observing performance. Performance was evaluated based on accuracy with precision and recall on the Port-land-dataset. Accuracy is the proportion of correct classifications. KNN achieved 64% and Decision Tree 69% accuracy. As both datasets contained real traffic islands in road networks, an assumption could be made that the accuracy would not be much higher if applied on the Norway-dataset. The result was not considered sufficient for a recommendation.

Weed resistance to control measures, particularly herbicides, is a growing problem in agriculture. In the case of herbicides, resistance is sometimes connected to genetic changes that directly affect the target site of the herbicide. Other cases are less straightforward where resistance arises without such a clear-cut mechanism. Understanding the genetic and gene regulatory mechanisms that may lead to the rapid evolution of resistance in weedy species is critical to securing our food supply. To study this phenomenon, we exposed young Arabidopsis plants to sublethal levels of one of four weed management stressors, glyphosate herbicide, trifloxysulfuron herbicide, mechanical clipping, and shading. To evaluate responses to these stressors we collected data on gene expression and regulation via epigenetic modification (methylation) and small RNA (sRNA). For all of the treatments except shade, the stress was limited in duration, and the plants were allowed to recover until flowering, to identify changes that persist to reproduction. At flowering, DNA for methylation bisulfite sequencing, RNA, and sRNA were extracted from newly formed rosette leaf tissue. Analyzing the individual datasets revealed many differential responses when compared to the untreated control for gene expression, methylation, and sRNA expression. All three measures showed increases in differential abundance that were unique to each stressor, with very little overlap between stressors. Herbicide treatments tended to exhibit the largest number of significant differential responses, with glyphosate treatment most often associated with the greatest differences and contributing to overlap. To evaluate how large datasets from methylation, gene expression, and sRNA analyses could be connected and mined to link regulatory information with changes in gene expression, the information from each dataset and for each gene was united in a single large matrix and mined with classification algorithms. Although our models were able to differentiate patterns in a set of simulated data, the raw datasets were too noisy for the models to consistently identify differentially expressed genes. However, by focusing on responses at a local level, we identified several genes with differential expression, differential sRNA, and differential methylation. While further studies will be needed to determine whether these epigenetic changes truly influence gene expression at these sites, the changes detected at the treatment level could prime the plants for future incidents of stress, including herbicides. / Doctor of Philosophy / Growing resistance to herbicides, particularly glyphosate, is one of the many problems facing agriculture. The rapid rise of resistance across herbicide classes has caused some to wonder if there is a mechanism of adaptation that does not involve mutations. Epigenetics is the study of changes in the phenotype that cannot be attributed to changes in the genotype. Typically, studies revolve around two features of the chromosomes: cytosine methylation and histone modifications. The former can influence how proteins interact with DNA, and the latter can influence protein access to DNA. Both can affect each other in self-reinforcing loops. They can affect gene expression, and DNA methylation can be directed by small RNA (sRNA), which can also influence gene expression through other pathways. To study these processes and their role in abiotic stress response, we aimed to analyze sRNA, RNA, and DNA from Arabidopsis thaliana plants under stress. The stresses applied were sublethal doses of the herbicides, glyphosate and trifloxysulfuron, as well as mechanical clipping and shade to represent other weed management stressors. The focus of the project was to analyze these responses individually and together to find epigenetic responses to stresses routinely encountered by weeds. We tested RNA for gene expression changes under our stress conditions and identified many, including some pertaining to DNA methylation regulation. The herbicide treatments were associated with upregulated defense genes and downregulated growth genes. Shade treated plants had many downregulated defense and other stress response genes. We also detected differential methylation and sRNA responses when compared to the control plants. Changes to methylation and sRNA only accounted for about 20% of the variation in gene expression. While attempting to link the epigenetic process of methylation to gene expression, we connected all the data sets and developed computer programs to try to make correlations. While these methods worked on a simulated dataset, we did not detect broad patterns of changes to epigenetic pathways that correlated strongly with gene expression in our experiment's data. There are many factors that can influence gene expression that could create noise that would hinder the algorithms' abilities to detect differentially expressed genes. This does not, however, rule out the possibility of epigenetic influence on gene expression in local contexts. Through scoring the traits of individual genes, we found several that interest us for future studies.

Third Generation (3G) wireless networks have been well studied and optimized with traditional radio resource management techniques, but still there is room for improvement. Cognitive radio technology can bring significantcant network improvements by providing awareness to the surrounding radio environment, exploiting previous network knowledge and optimizing the use of resources using machine learning and artificial intelligence techniques. Cognitive radio can also co-exist with legacy equipment thus acting as a bridge among heterogeneous communication systems. In this work, an approach for applying cognition in wireless networks is presented. Also, two machine learning techniques are used to create a hybrid cognitive engine. Furthermore, the concept of cognitive radio resource management along with some of the network applications are discussed. To evaluate the proposed approach cognition is applied to three typical wireless network problems: improving coverage, handover management and determining recurring policy events. A cognitive engine, that uses case-based reasoning and a decision tree algorithm is developed. The engine learns the coverage of a cell solely from observations, predicts when a handover is necessary and determines policy patterns, solely from environment observations. / Ph. D.

[pt] Métodos ensemble como random forest, boosting e bagging foram extensivamente estudados e provaram ter uma acurácia melhor do que usar apenas um preditor. Entretanto, a desvantagem é que os modelos obtidos utilizando esses métodos podem ser muito mais difíceis de serem interpretados do que por exemplo, uma árvore de decisão. Neste trabalho, nós abordamos o problema de construir uma árvore de decisão que aproximadamente reproduza um conjunto de árvores, explorando o tradeoff entre acurácia e interpretabilidade, que pode ser alcançado quando a reprodução exata do conjunto de árvores é relaxada. Primeiramente, nós formalizamos o problem de obter uma árvore de decisão de uma determinada profundidade que seja a mais aderente ao conjunto de árvores e propomos um algoritmo de programação dinâmica para resolver esse problema. Nós também provamos que a árvore de decisão obtida por esse procedimento satisfaz garantias de generalização relacionadas a generalização do modelo original de conjuntos de árvores, um elemento crucial para a efetividade dessa árvore de decisão em prática. Visto que a complexidade computacional do algoritmo de programação dinâmica é exponencial no número de features, nós propomos duas heurísticas para gerar árvores de uma determinada profundidade com boa aderência em relação ao conjunto de árvores. Por fim, nós conduzimos experimentos computacionais para avaliar os algoritmos propostos. Quando utilizados classificadores mais interpretáveis, os resultados indicam que em diversas situações a perda em acurácia é pequena ou inexistente: restrigindo a árvores de decisão de profundidade 6, nossos algoritmos produzem árvores que em média possuem acurácias que estão a 1 por cento (considerando o algoritmo de programção dinâmica) ou 2 por cento (considerando os algoritmos heurísticos) do conjunto original de árvores. / [en] Ensemble methods in machine learning such as random forest, boosting, and bagging have been thoroughly studied and proven to have better accuracy than using a single predictor. However, their drawback is that they give models that can be much harder to interpret than those given by, for example, decision trees. In this work, we approach in a principled way the problem of constructing a decision tree that approximately reproduces a tree ensemble, exploring the tradeoff between accuracy and interpretability that can be obtained once exact reproduction is relaxed. First, we formally define the problem of obtaining the decision tree of a given depth that is most adherent to a tree ensemble and give a Dynamic Programming algorithm for solving this problem. We also prove that the decision trees obtained by this procedure satisfy generalization guarantees related to the generalization of the original tree ensembles, a crucial element for their effectiveness in practice. Since the computational complexity of the Dynamic Programming algorithm is exponential in the number of features, we also design heuristics to compute trees of a given depth with good adherence to a tree ensemble. Finally, we conduct a comprehensive computational evaluation of the algorithms proposed. The results indicate that in many situations, there is little or no loss in accuracy in working more interpretable classifiers: even restricting to only depth-6 decision trees, our algorithms produce trees with average accuracies that are within 1 percent (for the Dynamic Programming algorithm) or 2 percent (heuristics) of the original random forest.

[pt] As árvores de decisão são estruturas comumente utilizadas em cenários nos quais modelos explicáveis de Aprendizado de Máquina são desejados, por serem visualmente intuitivas. Na literatura existente, a busca por explicabilidade em árvores envolve a minimização de métricas como altura e número de nós. Nesse contexto, definimos uma métrica de explicabilidade, chamada de explanation size, que reflete o número de atributos necessários para explicar a classificação dos exemplos. Apresentamos também um algoritmo, intitulado SER-DT, que obtém uma aproximação O(log n) (ótima se P diferente NP) para a minimização da altura no pior caso ou caso médio, assim como do explanation size no pior caso ou caso médio. Em uma série de experimentos, comparamos a implementação de SER-DT com algoritmos conhecidos da área, como CART e EC2, além de testarmos o impacto de parâmetros e estratégias de poda nesses algoritmos. SER-DT mostrou-se competitivo em acurácia com os algoritmos citados, mas gerou árvores muito mais explicáveis. / [en] Decision trees are commonly used structures in scenarios where explainable Machine Learning models are desired, as they are visually intuitive. In the existing literature, the search for explainability in trees involves minimizing metrics such as depth and number of nodes. In this context, we define an explainability metric, called explanation size, which reflects the number of attributes needed to explain the classification of examples. We also present an algorithm, called SER-DT, which obtains an O(log n) approximation (optimal if P different NP) for the minimization of depth in the worst/average case, as well as of explanation size in the worst/average case. In a series of experiments, we compared the SER-DT implementation with well-known algorithms in the field, such as CART and EC2 in addition to testing the impact of parameters and pruning strategies on these algorithms. SER-DT proved to be competitive in terms of accuracy with the aforementioned algorithms, but generated much more explainable trees.

This master thesis project is carried out by one student at the Royal Institute of Technology in collaboration with Cybercom Group. The aim was to evaluate and compare system design strategies for fruit recognition in harvesting robots and the performance of supervised machine learning classification methods when applied to this specific task. The thesis covers the basics of these systems; to which parameters, constraints, requirements, and design decisions have been investigated. The framework is used as a foundation for the implementation of both sensing system, and processing and classification algorithms. A plastic tomato plant with fruit of varying maturity was used as a basis for training and testing, and a Kinect v2 for Windows including sensors for high resolution color-, depth, and IR data was used for image acquisition. The obtained data were processed and features of objects of interest extracted using MATLAB and a SDK for Kinect provided by Microsoft. Multiple views of the plant were acquired by having the plant rotate on a platform controlled by a stepper motor and an Ardunio Uno. The algorithms tested were binary classifiers, including Support Vector Machine, Decision Tree, and k-Nearest Neighbor. The models were trained and validated using a five fold cross validation in MATLABs Classification Learner application. Peformance metrics such as precision, recall, and the F1-score, used for accuracy comparison, were calculated. The statistical models k-NN and SVM achieved the best scores. The method considered most promising for fruit recognition purposes was the SVM. / Det här masterexamensarbetet har utförts av en student från Kungliga Tekniska Högskolan i samarbete med Cybercom Group. Målet var att utvärdera och jämföra designstrategier för igenkänning av frukt i en skörderobot och prestandan av klassificerande maskininlärningsalgoritmer när de appliceras på det specifika problemet. Arbetet omfattar grunderna av dessa system; till vilket parametrar, begränsningar, krav och designbeslut har undersökts. Ramverket användes sedan som grund för implementationen av sensorsystemet, processerings- och klassifikationsalgoritmerna. En tomatplanta i pplast med frukter av varierande mognasgrad användes som bas för träning och validering av systemet, och en Kinect för Windows v2 utrustad med sensorer för högupplöst färg, djup, och infraröd data anvöndes för att erhålla bilder. Datan processerades i MATLAB med hjälp av mjukvaruutvecklingskit för Kinect tillhandahållandet av Windows, i syfte att extrahera egenskaper ifrån objekt på bilderna. Multipla vyer erhölls genom att låta tomatplantan rotera på en plattform, driven av en stegmotor Arduino Uno. De binära klassifikationsalgoritmer som testades var Support Vector MAchine, Decision Tree och k-Nearest Neighbor. Modellerna tränades och valideras med hjälp av en five fold cross validation i MATLABs Classification Learner applikation. Prestationsindikatorer som precision, återkallelse och F1- poäng beräknades för de olika modellerna. Resultatet visade bland annat att statiska modeller som k-NN och SVM presterade bättre för det givna problemet, och att den sistnömnda är mest lovande för framtida applikationer.

It is essential for a bank to estimate the credit risk it carries and the magnitude of exposure it has in case of non-performing customers. Estimation of this kind of risk has been done by statistical methods through decades and with respect to recent development in the field of machine learning, there has been an interest in investigating if machine learning techniques can perform better quantification of the risk. The aim of this thesis is to examine which method from a chosen set of machine learning techniques exhibits the best performance in default prediction with regards to chosen model evaluation parameters. The investigated techniques were Logistic Regression, Random Forest, Decision Tree, AdaBoost, XGBoost, Artificial Neural Network and Support Vector Machine. An oversampling technique called SMOTE was implemented in order to treat the imbalance between classes for the response variable. The results showed that XGBoost without implementation of SMOTE obtained the best result with respect to the chosen model evaluation metric. / Det är nödvändigt för en bank att ha en bra uppskattning på hur stor risk den bär med avseende på kunders fallissemang. Olika statistiska metoder har använts för att estimera denna risk, men med den nuvarande utvecklingen inom maskininlärningsområdet har det väckt ett intesse att utforska om maskininlärningsmetoder kan förbättra kvaliteten på riskuppskattningen. Syftet med denna avhandling är att undersöka vilken metod av de implementerade maskininlärningsmetoderna presterar bäst för modellering av fallissemangprediktion med avseende på valda modelvaldieringsparametrar. De implementerade metoderna var Logistisk Regression, Random Forest, Decision Tree, AdaBoost, XGBoost, Artificiella neurala nätverk och Stödvektormaskin. En översamplingsteknik, SMOTE, användes för att behandla obalansen i klassfördelningen för svarsvariabeln. Resultatet blev följande: XGBoost utan implementering av SMOTE visade bäst resultat med avseende på den valda metriken.

With an increased amount of connected devices and the recent surge of artificial intelligence, the two technologies need more attention to fully bloom as a useful tool for creating new and exciting products. As machine learning traditionally is implemented on computers and online servers this thesis explores the possibility to extend machine learning to an embedded environment. This evaluation of existing machine learning in embedded systems with limited processing capa-bilities has been carried out in the specific context of an application involving classification of basic human movements. Previous research and implementations indicate that it is possible with some limitations, this thesis aims to answer which hardware limitation is affecting clas-sification and what classification accuracy the system can reach on an embedded device. The tests included human motion data from an existing dataset and included four different machine learning algorithms on three devices. Support Vector Machine (SVM) are found to be performing best com-pared to CART, Random Forest and AdaBoost. It reached a classification accuracy of 84,69% between six different included motions with a clas-sification time of 16,88 ms per classification on a Cortex M4 processor. This is the same classification accuracy as the one obtained on the host computer with more computational capabilities. Other hardware and machine learning algorithm combinations had a slight decrease in clas-sification accuracy and an increase in classification time. Conclusions could be drawn that memory on the embedded device affect which al-gorithms could be run and the complexity of data that can be extracted in form of features. Processing speed is mostly affecting classification time. Additionally the performance of the machine learning system is connected to the type of data that is to be observed, which means that the performance of different setups differ depending on the use case. / Antalet uppkopplade enheter ökar och det senaste uppsvinget av ar-tificiell intelligens driver forskningen framåt till att kombinera de två teknologierna för att både förbättra existerande produkter och utveckla nya. Maskininlärning är traditionellt sett implementerat på kraftfulla system så därför undersöker den här masteruppsatsen potentialen i att utvidga maskininlärning till att köras på inbyggda system. Den här undersökningen av existerande maskinlärningsalgoritmer, implemen-terade på begränsad hårdvara, har utförts med fokus på att klassificera grundläggande mänskliga rörelser. Tidigare forskning och implemen-tation visar på att det ska vara möjligt med vissa begränsningar. Den här uppsatsen vill svara på vilken hårvarubegränsning som påverkar klassificering mest samt vilken klassificeringsgrad systemet kan nå på den begränsande hårdvaran. Testerna inkluderade mänsklig rörelsedata från ett existerande dataset och inkluderade fyra olika maskininlärningsalgoritmer på tre olika system. SVM presterade bäst i jämförelse med CART, Random Forest och AdaBoost. Den nådde en klassifikationsgrad på 84,69% på de sex inkluderade rörelsetyperna med en klassifikationstid på 16,88 ms per klassificering på en Cortex M processor. Detta är samma klassifikations-grad som en vanlig persondator når med betydligt mer beräknings-resurserresurser. Andra hårdvaru- och algoritm-kombinationer visar en liten minskning i klassificeringsgrad och ökning i klassificeringstid. Slutsatser kan dras att minnet på det inbyggda systemet påverkar vilka algoritmer som kunde köras samt komplexiteten i datan som kunde extraheras i form av attribut (features). Processeringshastighet påverkar mest klassificeringstid. Slutligen är prestandan för maskininlärningsy-stemet bunden till typen av data som ska klassificeras, vilket betyder att olika uppsättningar av algoritmer och hårdvara påverkar prestandan olika beroende på användningsområde.