A associação é uma tarefa de mineração de dados que tem sido muito utilizada em problemas reais, porém o grande número de regras de associação que podem ser geradas dificulta a identificação de conhecimento interessante aos usuários. Para apoiar a identificação de regras interessantes podem ser utilizadas medidas de avaliação de conhecimento, que normalmente são classificadas como objetivas ou subjetivas. As medidas objetivas são mais gerais, mas podem não ser suficientes por não considerarem aspectos relacionados ao usuário ou ao domínio da aplicação. Por outro lado pode haver dificuldade em se obter a subjetividade do usuário necessária para o cálculo das medidas subjetivas. Diante desse contexto, neste trabalho é proposta uma metodologia para identificação de regras de associação interessantes que combina análises com medidas objetivas e subjetivas, visando aproveitar as vantagens de cada tipo e facilitar a participação do especialista. As medidas objetivas são utilizadas para selecionar algumas regras potencialmente interessantes para serem avaliadas por um especialista. As medidas subjetivas são calculadas utilizando essas regras com as avaliações do especialista. Essas medidas subjetivas então são utilizadas para auxiliar a identificação de regras interessantes de acordo com o conhecimento obtido durante a avaliação. Para viabilizar a aplicação dessa metodologia foi desenvolvido um módulo computacional de exploração de regras de associação com medidas subjetivas, denominado RulEE-SEAR. Utilizando esse módulo e outras ferramentas já existentes foi realizado um estudo de caso com uma base de dados real sobre qualidade de vida urbana. Nesse estudo de caso o processo de identificação de regras de associação interessantes foi realizado com especialista da área e verificou-se a viabilidade da metodologia proposta. / Association is a data mining task which has been applied in several real problems. However, due to the huge number of association rules that can be generated, it is hard for users to identify interesting knowledge. To assist users in finding interesting rules, evaluation measures can be used. Those measures are usually divided into objective and subjective. Objective measures are more general, but they can be insufficient because they do not consider user's and domain's features. On the other hand, getting users's knowledge and interest needed to calculate subjective measures can be a difficult task. In this context, a methodology to identify interesting association rules is proposed in this work. This methodology combines analysis with objective and subjective measures, aiming to use the advantages of each kind of measure and to make user's participation easier. Objective measures are used to select some potentially interesting rules for the user's evaluation. These rules and the evaluation are used to calculate subjective measures. Then, the subjective measures are used to assist the user in identifying interesting rules according to the knowledge obtained during the evaluation. To make the methodology use practicable, a computational module, named RulEE-SEAR, was developed to explore the association rules with subjective measures. Using this module and other existing tools, a case study was done. A urban life quality database was used and a specialist in this area participated in the interesting association rules identification. That case study showed that the methodology proposed is feasible.

Aspect-based sentiment analysis is the field of study which extracts and interpret the sentiment, usually classified as positive or negative, towards some target or aspect in an opinionated text. This doctoral dissertation details an empirical study of techniques and methods for aspect extraction in aspect-based sentiment analysis with the focus on Portuguese. Three different approaches were explored: frequency-based, relation-based and machine learning. In each one, this work shows a comparative study between a Portuguese and an English corpora and the differences found in applying the approaches. In addition, richer linguistic knowledge is also explored by using syntatic dependencies and semantic roles, leading to better results. This work lead to the establishment of new benchmarks for the aspect extraction in Portuguese. / A análise do sentimento orientada a aspectos é o campo de estudo que extrai e interpreta o sentimento, geralmente classificado como positivo ou negativo, em direção a algum alvo ou aspecto em um texto de opinião. Esta tese de doutorado detalha um estudo empírico de técnicas e métodos para extração de aspectos em análises de sentimentos baseadas em aspectos com foco na língua Portuguesa. Foram exploradas três diferentes abordagens: métodos baseados na frequências, métodos baseados na relação e métodos de aprendizagem de máquina. Em cada abordagem, este trabalho mostra um estudo comparativo entre um córpus para o Português e outro para o Inglês e as diferenças encontradas na aplicação destas abordagens. Além disso, o conhecimento linguístico mais rico também é explorado pelo uso de dependências sintáticas e papéis semânticos, levando a melhores resultados. Este trabalho resultou no estabelecimento de novos padrões de avaliação para a extração de aspectos em Português.

Há várias décadas, pesquisadores em ciências sociais buscam formas gráficas para expressar as relações humanas na sociedade. O advento do computador e, mais recentemente, da internet, possibilitou o surgimento de um campo que tem despertado a atenção de estudiosos das áreas de visualização de informação e de ciências sociais, o da visualização de redes sociais. Esse campo tem o potencial de revelar e explorar padrões que podem beneficiar um número muito grande de aplicações e indivíduos em áreas tais como comércio, segurança em geral, redes de conhecimento e pesquisa de mercado. Grande parte dos algoritmos de visualização de redes sociais são baseados em grafos, destacando relacionamentos entre indivíduos e grupos de indivíduos, mas dando pouca atenção aos seus demais atributos. Assim, este trabalho apresenta um conjunto de soluções para representar e explorar visualmente redes sociais levando em consideração tais atributos. A primeira solução faz uso de redes heterogêneas, onde tanto indivíduos quanto comunidades são representados no grafo; a segunda solução utiliza técnicas de visualização baseadas em projeção multidimensional, que promovem o posicionamento dos dados no plano de acordo com algum critério de similaridade baseado em atributo; e a última solução coordena múltiplas visões para focar rapidamente em regiões de interesse. Os resultados indicam que as soluções proveem um poder de representação e identificação de conceitos não facilmente detectados por formas convencionais de visualização e exploração de grafos, com indícios fornecidos através dos estudos de caso e da realização de avaliações com usuários. Este trabalho fornece um estudo das áreas de visualização em grafos para a análise de redes sociais bem como uma implementação das soluções de integração da visualização em redes com as projeções multidimensionais / For decades, social sciences researchers have searched for graphical forms to express human social relationships. The development of computer science and more recently of the Internet has given rise to a new field of research for visualization and social sciences professionals, that of social network visualization. This field can potentially offer new opportunities in reveal new patterns that can benefit a large number of applications and individuals in fields such as commerce, security, knowledge networks and marketing. A large part of social network visualization algorithms and systems relies on graph representations, highlighting relationships amongst individuals and groups of individuals, but mostly neglecting the other available attributes of individuals. Thus, this work presents a set of tools to represent and explore social networks visually, taking into consideration the attributes of the nodes. The first technique employs heterogeneous networks, where both individuals and communities are represented in the graph; the second solution uses visualization techniques based on multidimensional projection, which promote the placement of data in the plane according to some similarity criterion based on attribute; still another proposed technique coordinates multiple views in order to speed up focus in regions of interest in the data sets. The results indicate that the solutions promote high degree of representation power and that concept identification not easily obtained via other methods is possible; the evidence comes from case studies as well as a user evaluation. This work includes a study in the area of graph visualization for social network analysis as well as a system implementing the proposed solutions, that integrate network visualization and multidimensional projections to extract patterns from social networks

Dada a grande quantidade e diversidade de dados textuais sendo criados diariamente, as aplicações do processo de Mineração de Textos são inúmeras e variadas. Nesse processo, a qualidade da solução final depende, em parte, do modelo de representação de textos adotado. Por se tratar de textos em língua natural, relações sintáticas e semânticas influenciam o seu significado. No entanto, modelos tradicionais de representação de textos se limitam às palavras, não sendo possível diferenciar documentos que possuem o mesmo vocabulário, mas que apresentam visões diferentes sobre um mesmo assunto. Nesse contexto, este trabalho foi motivado pela diversidade das aplicações da tarefa de classificação automática de textos, pelo potencial das representações no modelo espaço-vetorial e pela lacuna referente ao tratamento da semântica inerente aos dados em língua natural. O seu desenvolvimento teve o propósito geral de avançar as pesquisas da área de Mineração de Textos em relação à incorporação de aspectos semânticos na representação de coleções de documentos. Um mapeamento sistemático da literatura da área foi realizado e os problemas de classificação foram categorizados em relação à complexidade semântica envolvida. Aspectos semânticos foram abordados com a proposta, bem como o desenvolvimento e a avaliação de sete modelos de representação de textos: (i) gBoED, modelo que incorpora a semântica obtida por meio de conhecimento do domínio; (ii) Uni-based, modelo que incorpora a semântica por meio da desambiguação lexical de sentidos e hiperônimos de conceitos; (iii) SR-based Terms e SR-based Sentences, modelos que incorporam a semântica por meio de anotações de papéis semânticos; (iv) NASARIdocs, Babel2Vec e NASARI+Babel2Vec, modelos que incorporam a semântica por meio de desambiguação lexical de sentidos e embeddings de palavras e conceitos. Representações de coleções de documentos geradas com os modelos propostos e outros da literatura foram analisadas e avaliadas na classificação automática de textos, considerando datasets de diferentes níveis de complexidade semântica. As propostas gBoED, Uni-based, SR-based Terms e SR-based Sentences apresentam atributos mais expressivos e possibilitam uma melhor interpretação da representação dos documentos. Já as propostas NASARIdocs, Babel2Vec e NASARI+Babel2Vec incorporam, de maneira latente, a semântica obtida de embeddings geradas a partir de uma grande quantidade de documentos externos. Essa propriedade tem um impacto positivo na performance de classificação. / Text Mining applications are numerous and varied since a huge amount of textual data are created daily. The quality of the final solution of a Text Mining process depends, among other factors, on the adopted text representation model. Despite the fact that syntactic and semantic relations influence natural language meaning, traditional text representation models are limited to words. The use of such models does not allow the differentiation of documents that use the same vocabulary but present different ideas about the same subject. The motivation of this work relies on the diversity of text classification applications, the potential of vector space model representations and the challenge of dealing with text semantics. Having the general purpose of advance the field of semantic representation of documents, we first conducted a systematic mapping study of semantics-concerned Text Mining studies and we categorized classification problems according to their semantic complexity. Then, we approached semantic aspects of texts through the proposal, analysis, and evaluation of seven text representation models: (i) gBoED, which incorporates text semantics by the use of domain expressions; (ii) Uni-based, which takes advantage of word sense disambiguation and hypernym relations; (iii) SR-based Terms and SR-based Sentences, which make use of semantic role labels; (iv) NASARIdocs, Babel2Vec and NASARI+Babel2Vec, which take advantage of word sense disambiguation and embeddings of words and senses.We analyzed the expressiveness and interpretability of the proposed text representation models and evaluated their classification performance against different literature models. While the proposed models gBoED, Uni-based, SR-based Terms and SR-based Sentences have improved expressiveness, the proposals NASARIdocs, Babel2Vec and NASARI+Babel2Vec are latently enriched by the embeddings semantics, obtained from the large training corpus. This property has a positive impact on text classification performance.

Social media services have a growing impact in our society. Individuals often rely on social media to get their news, decide which products to buy or to communicate with their friends. As consequence of the widespread adoption of social media, a large volume of data on how users behave is created every day and stored into large databases. Learning how to analyze and extract useful knowledge from this data has a number of potential applications. For instance, a deeper understanding on how legitimate users interact with social media services could be explored to design more accurate spam and fraud detection methods. This PhD research is based on the following hypothesis: data generated by social media users present patterns that can be exploited to improve the effectiveness of tasks such as prediction, forecasting and modeling in the domain of social media. To validate our hypothesis, we focus on designing data mining methods tailored to social media data. The main contributions of this PhD can be divided into three parts. First, we propose Act-M, a mathematical model that describes the timing of users actions. We also show that Act-M can be used to automatically detect bots among social media users based only on the timing (i.e. time-stamp) data. Our second contribution is VnC (Vote-and-Comment), a model that explains how the volume of different types of user interactions evolve over time when a piece of content is submitted to a social media service. In addition to accurately matching real data, VnC is useful, as it can be employed to forecast the number of interactions received by social media content. Finally, our third contribution is the MFS-Map method. MFS-Map automatically provides textual annotations to social media images by efficiently combining visual and metadata features. Our contributions were validated using real data from several social media services. Our experiments show that the Act-M and VnC models provided a more accurate fit to the data than existing models for communication dynamics and information diffusion, respectively. MFS-Map obtained both superior precision and faster speed when compared to other widely employed image annotation methods. / O impacto dos serviços de mídia social em nossa sociedade é crescente. Indivíduos frequentemente utilizam mídias sociais para obter notícias, decidir quais os produtos comprar ou para se comunicar com amigos. Como consequência da adoção generalizada de mídias sociais, um grande volume de dados sobre como os usuários se comportam é gerado diariamente e armazenado em grandes bancos de dados. Aprender a analisar e extrair conhecimentos úteis a partir destes dados tem uma série de potenciais aplicações. Por exemplo, um entendimento mais detalhado sobre como usuários legítimos interagem com serviços de mídia social poderia ser explorado para projetar métodos mais precisos de detecção de spam e fraude. Esta pesquisa de doutorado baseia-se na seguinte hipótese: dados gerados por usuários de mídia social apresentam padrões que podem ser explorados para melhorar a eficácia de tarefas como previsão e modelagem no domínio das mídias sociais. Para validar esta hipótese, foram projetados métodos de mineração de dados adaptados aos dados de mídia social. As principais contribuições desta pesquisa de doutorado podem ser divididas em três partes. Primeiro, foi desenvolvido o Act-M, um modelo matemático que descreve o tempo das ações dos usuários. O autor demonstrou que o Act-M pode ser usado para detectar automaticamente bots entre usuários de mídia social com base apenas nos dados de tempo. A segunda contribuição desta tese é o VnC (Vote-and- Comment), um modelo que explica como o volume de diferentes tipos de interações de usuário evolui ao longo do tempo quando um conteúdo é submetido a um serviço de mídia social. Além de descrever precisamente os dados reais, o VnC é útil, pois pode ser empregado para prever o número de interações recebidas por determinado conteúdo de mídia social. Por fim, nossa terceira contribuição é o método MFS-Map. O MFS-Map fornece automaticamente anotações textuais para imagens de mídias sociais, combinando eficientemente características visuais e de metadados das imagens. As contribuições deste doutorado foram validadas utilizando dados reais de diversos serviços de mídia social. Os experimentos mostraram que os modelos Act-M e VnC forneceram um ajuste mais preciso aos dados quando comparados, respectivamente, a modelos existentes para dinâmica de comunicação e difusão de informação. O MFS-Map obteve precisão superior e tempo de execução reduzido quando comparado com outros métodos amplamente utilizados para anotação de imagens.

A demanda por métodos de análise e descoberta de conhecimento em grandes bases de dados tem fortalecido a pesquisa em Mineração de Dados. Dentre as tarefas associadas a essa área, tem-se Regras de Associação. Vários algoritmos foram propostos para tratamento de Regras de Associação, que geralmente tˆem como resultado um elevado número de regras, tornando o Pós-processamento do conhecimento uma etapa bastante complexa e desafiadora. Existem medidas para auxiliar essa etapa de avaliação de regras, porém existem lacunas referentes a inexistência de um método intuitivo para priorizar e selecionar regras. Além disso, não é possível encontrar metodologias específicas para seleção de regras considerando mais de uma medida simultaneamente. Esta tese tem como objetivo a proposição, desenvolvimento e implementação de uma metodologia para o Pós-processamento de Regras de Associação. Na metodologia proposta, pequenos grupos de regras identificados como potencialmente interessantes são apresentados ao usuário especialista para avaliação. Para tanto, foram analisados métodos e técnicas utilizadas em Pós-processamento de conhecimento, medidas objetivas para avaliação de Regras de Associação e algoritmos que geram regras. Dessa perspectiva foram realizados experimentos para identificar o potencial das medidas a serem empregadas como filtros de Regras de Associação. Uma avaliação gráfica apoiou o estudo das medidas e a especificação da metodologia proposta. Aspecto inovador da metodologia proposta é a utilização do método de Pareto e a combinação de medidas para selecionar as Regras de Associação. Por fim foi implementado um ambiente para avaliação de Regras de Associação, denominado ARInE, viabilizando o uso da metodologia proposta. / The large demand of methods for knowledge discovery and analysis in large databases has continously increased the research in data mining area. Among the tasks associated to this area, one can find Association Rules. Several algorithms have been proposed for treating Association Rules. However, these algorithms give as results a huge amount of rules, making the knowledge post-processing phase very complex and challeging. There are several measures that can be used in this evaluation phase, but there are also some limitations regarding to the ausence of an intuitive method to rank and select rules. Moreover, it is not possible to find especific methodologies for selecting rules, considering more than one measure simultaneously. This thesis has as objective the proposal, development and implementation of a postprocessing methodology for Association Rules. In the proposed methodology, small groups of rules, which have been identified as potentialy interesting, are presented to the expert for evaluation. In this sense, methods and techniques for knowledge post-processing, objective measures for rules evaluation, and Association Rules algorithms have been analized. From this point of view, several experiments have been realized for identifying the potential of such measures to be used to filter Association Rules. The study of measures and the specification of the proposed methodology have been supported by a graphical evaluation. The novel aspect of the proposed methodology consists on using the Pareto’s method and combining measures for selecting Association Rules. Finally, an enviroment for evaluating Association Rules, named as ARInE, has been implemented according to the proposed methodology.

A mineração de dados é um processo computacionalmente caro, que se apoia no pré-processamento dos dados para aumentar a sua eficiência. As técnicas de redução de elementos do conjunto de dados, principalmente a amostragem de dados se destacam no pré-processamento. Os dados reais são caracterizados pela não uniformidade da distribuição, grande quantidade de atributos e presença de elementos considerados ruídos. Para esse tipo de dado, a amostragem uniforme, na qual cada elemento tem a mesma probabilidade de ser escolhido, é inefiiente. Os dados nos últimos anos, vem passando por transformações. Assim, não só o seu volume tem aumentado significantemente, mas também a maneira de como eles são representados. Os dados usualmente são divididos apenas em dados tradicionais (número e pequenas cadeias de caracteres) e dados complexos (imagens, cadeias de DNA, vídeos, etc). Entretanto, uma representação mais rica, na qual não só os elementos do conjunto são representados mas também a suas ligações, vem sendo amplamente utilizada. Esse novo tipo de dado, chamado rede complexa, fez surgir uma nova área de pesquisa chamada mineração de redes complexas ou de grafos, já que estes são utilizados na representação das redes complexas. Para esta nova área é necessário o desenvolvimento de técnicas que permitam a mineração de grandes redes complexas, isto é, redes com centenas de milhares de elementos(nós) e ligações(arestas). Esta tese teve como objetivo explorar a redução de elementos em conjuntos de dados chamados desbalanceados, isto é, que possuem agrupamentos ou classes de tamanhos bastantes distintos, e que também possuam alta quantidade de atributos e presença de ruídos. Além disso, esta tese também explora a mineração de redes complexas com a extração de padrões e propriedades e o desenvolvimento de algoritmos eficientes para a classificação das redes em reais e sintéticas. Também é proposto a mineração de redes complexas utilizando gerenciadores de base de dados para a mineração de cliques de tamanho 4 e 5 e a apresentação da extensão do coeficiente de clusterização / Data mining is an expensive computational process speeded up by data preprocessing. Data reduction techniques, as data sampling are useful during the data preprocessing. Real data are known for presenting non-uniform data distribution, a large amount of attributes and noise. For this type of data, uniform sampling, which selects elements with the same probability, is inefficient. Over the past years, the data available to mining have been changed. Not only have their volume increased but also data format. Data are usually divided into traditional (number and small chains of character) and complex (images, DNA, videos, etc). However, a rich representation, in which not only elements but also the connections among the elements have been used, is necessary. This new data type, which is called complex network and is usually modeled as a graph, has created a new research area, called graph mining or complex network mining, which requires the development of new mining techniques to allow mining large networks, that is, networks with hundreds of thousands of nodes and edges. The present thesis aims to explore the data reduction in unbalanced data, that is, data that have clusters with very different sizes, a large amount of attributes and noise. It also explores complex network mining with two basic findings: useful new patterns, which allow distinguishing real from synthetic networks and mining cliques of sizes 4 and 5 using database systems, discovering interesting power laws and presenting a new cluster coefficient formula

A grande quantidade de dados gerada em diversas áreas do conhecimento cria a necessidade do desenvolvimento de técnicas de mineração de dados cada vez mais eficientes e eficazes. Técnicas de agrupamento têm sido utilizadas com sucesso em várias áreas, especialmente naquelas em que não há conhecimento prévio sobre a organização dos dados. Contudo, a utilização de diferentes algoritmos de agrupamento, ou variações de um mesmo algoritmo, pode gerar uma ampla variedade de resultados. Tamanha variedade cria a necessidade de métodos para avaliar e selecionar bons resultados. Uma forma de avaliar esses resultados consiste em utilizar índices de validação de agrupamentos. Entretanto, uma grande diversidade de índices de validação foi proposta na literatura, o que torna a escolha de um único índice de validação uma tarefa penosa caso os desempenhos dos índices comparados sejam desconhecidos para a classe de problemas de interesse. Com a finalidade de obter um consenso entre resultados, é possível combinar um conjunto de agrupamentos ou índices de validação em uma única solução final. Combinações de agrupamentos (clustering ensembles) foram bem sucedidas em obter soluções robustas a variações no cenário de aplicação, o que faz do uso de comitês de agrupamentos uma alternativa interessante para encontrar soluções de qualidade razoável, segundo diferentes índices de validação. Adicionalmente, utilizar uma combinação de índices de validação pode tornar a avaliação de agrupamentos mais completa, uma vez que uma maioria dos índices combinados pode compensar o fraco desempenho do restante. Em alguns casos, não é possível lidar com um único conjunto de dados centralizado, por razões físicas ou questões de privacidade, o que gera a necessidade de distribuir o processo de mineração. Combinações de agrupamentos também podem ser estendidas para problemas de agrupamento de dados distribuídos, uma vez que informações sobre os dados, oriundas de diferentes fontes, podem ser combinadas em uma única solução global. O principal objetivo desse trabalho consiste em investigar técnicas de combinação de agrupamentos e de índices de validação aplicadas na seleção de agrupamentos para combinação e na mineração distribuída de dados. Adicionalmente, algoritmos evolutivos de agrupamento são estudados com a finalidade de selecionar soluções de qualidade dentre os resultados obtidos. As técnicas desenvolvidas possuem complexidade computacional reduzida e escalabilidade, o que permite sua aplicação em grandes conjuntos de dados ou cenários em que os dados encontram-se distribuídos / The large amount of data resulting from different areas of knowledge creates the need for development of data mining techniques increasingly efficient and effective. Clustering techniques have been successfully applied to several areas, especially when there is no prior knowledge about the data organization. Nevertheless, the use of different clustering algorithms, or variations of the same algorithm, can generate a wide variety of results, what raises the need to create methods to assess and select good results. One way to evaluate these results consists on using cluster validation indexes. However, a wide variety of validation indexes was proposed in the literature, which can make choosing a single index challenging if the performance of the compared indexes is unknown for the application scenario. In order to obtain a consensus among different options, a set of clustering results or validation indexes can be combined into a single final solution. Clustering ensembles successfully obtained results robust to variations in the application scenario, which makes them an attractive alternative to find solutions of reasonable quality, according to different validation indexes. Moreover, using a combination of validation indexes can promote a more powerful evaluation, as the majority of the combined indexes can compensate the poor performance of individual indexes. In some cases, it is not possible to work with a single centralized data set, for physical reasons or privacy concerns, which creates the need to distribute the mining process. Clustering ensembles can be extended to distributed data mining problems, since information about the data from distributed sources can be combined into a single global solution. The main objective of this research resides in investigating combination techniques for validation indexes and clustering results applied to clustering ensemble selection and distributed clustering. Additionally, evolutionary clustering algorithms are studied to select quality solutions among the obtained results. The techniques developed have scalability and reduced computational complexity, allowing their usage in large data sets or scenarios with distributed data

Um sistema de aprendizado supervisionado é um programa capaz de realizar decisões baseado na experiência contida em casos resolvidos com sucesso. As regras de classificação induzidas por um sistema de aprendizado podem ser analisadas segundo dois critérios: a complexidade dessas regras e o erro de classificação sobre um conjunto independente de exemplos. Sistemas de aprendizado têm sido desenvolvidos na prática utilizando diferentes paradigmas incluindo estatística, redes neurais, bem como sistemas de aprendizado simbólico proposicionais e relacionais. Diversos métodos de aprendizado podem ser aplicados à mesma amostra de dados e alguns deles podem desempenhar melhor que outros. Para uma dada aplicação, não existem garantias que qualquer um desses métodos é necessariamente o melhor. Em outras palavras, não existe uma análise matemática que possa determinar se um algoritmo de aprendizado irá desempenhar melhor que outro. Desta forma, estudos experimentais são necessários. Neste trabalho nos concentramos em uma tarefa de aprendizado conhecida como classificação ou predição, na qual o problema consiste na construção de um procedimento de classificação a partir de um conjunto de casos no qual as classes verdadeiras são conhecidas, chamado de aprendizado supervisionado. O maior objetivo de um classificador é ser capaz de predizer com sucesso a respeito de novos casos. A performance de um classificador é medida em termos da taxa de erro. Técnicas experimentais para estimar a taxa de erro verdadeira não somente provêem uma base para comparar objetivamente as performances de diversos algoritmos de aprendizado no mesmo conjunto de exemplos, mas também podem ser uma ferramenta poderosa para projetar um classificador. As técnicas para estimar a taxa de erro são baseadas na teoria estatística de resampling. Um ambiente chamado AMPSAM foi implementado para ajudar na aplicação dos métodos de resampling em conjuntos de exemplos do mundo real. AMPSAM foi projetado como uma coleção de programas independentes, os quais podem interagir entre si através de scripts pré-definidos ou de novos scripts criados pelo usuário. O ambiente utiliza um formato padrão para arquivos de exemplos o qual é independente da sintaxe de qualquer algoritmo. AMPSAM também inclui ferramentas para particionar conjuntos de exemplos em conjuntos de treinamento e teste utilizando diferentes métodos de resampling. Além do método holdout, que é o estimador de taxa de erro mais comum, AMPSAM suporta os métodos n-fold cross-validation --- incluindo o leaning-one-out --- e o método bootstrap. As matrizes de confusão produzidas em cada iteração utilizando conjuntos de treinamento e teste podem ser fornecidas a um outro sistema implementado chamado SMEC. Este sistema calcula e mostra graficamente algumas das medidas descritivas mais importantes relacionadas com tendência central e dispersão dos dados. Este trabalho também relata os resultados experimentais a respeito de medidas do erro de classificação de três classificadores proposicionais e relacionais bem conhecidos, utilizando ambos os sistemas implementados, em diversos conjuntos de exemplos freqüentemente utilizados em pesquisas de Aprendizado de Máquina. / A learning system is a computer program that makes decisions based on the accumulative experience contained in successfully solved cases. The classification rules induced by a learning system are judged by two criteria: their classification error on an independent test set and their complexity. Practical learning systems have been developed using different paradigms including statistics, neural nets, as well as propositional and relational symbolic machine learning. Several learning methods can be applied to the same sample data and some of them may do better than others. Still, for a given application, there is no guarantee that any of these methods will work or that any single method is necessarily the best one. In other words, there is not a mathematical analysis method that can determine whether a learning system algorithm will work well. Hence, experimental studies are required. In this work we confine our attention to the learning task known as classification or prediction, where the problem concerns the construction of a classification procedure from a set of data for which the true classes are known, and is termed supervised learning. The overall objective of a classifier is to be able to predict successfully on new data. Performance is measured in terms of the error rate. Error rate estimation techniques not only provide a basis for objectively comparing the error rate of several classifiers on the same data and then estimating their future performance on new data, but they can also be a powerful tool for designing a classifier. The techniques of error rate estimation are based on statistical resampling theory. In this work, rules induced complexity of propositional and relational learning systems as well as several resampling methods to estimate the true error rate are discussed. An environment called AMPSAM has been implemented to aid in the application of resampling methods to real world data sets. AMPSAM consists of a collection of interdependent programs that can be bound together either by already defined or by new user defined scripts. The environment uses a common file format for data sets which is independent of any specific classifier scheme. It also includes facilities for splitting data sets up into test and training sets using different methods. Besides holdout, which is the most common accuracy estimation method, AMPSAM supports n-fold cross-validation --- including leaving-one-out --- and bootstrap. The confusion matrices produced in each run using those test and training sets can be input to another system called SMEC. This system calculates and graphically displays some of the most important descriptive measures related to central tendency and dispersion of those data. This work also reports the results of experiments measuring the classification error of three well known propositional and relational classifiers, using the implemented systems, on several data sets commonly used in Machine Learning research.

RNA Sequencing has recently emerged as a breakthrough technology for microRNA (miRNA) discovery. This technology has allowed the discovery of thousands of miRNAs in a large number of species. However, despite the benefits of this technology, it also carries its own limitations, including the need for sequencing read libraries and of the genome. Differently, ab initio computational methods need only the genome as input to search for genonic locus likely to give rise to novel miRNAs. In the core of most of these methods, there are predictive models induced by using data mining techniques able to distinguish between real (positive) and pseudo (negative) miRNA precursors (pre-miRNA). Nevertheless, the applicability of current literature ab initio methods have been compromised by high false detection rates and/or by other computational difficulties. In this work, we investigated how the main aspects involved in the induction of predictive models for pre-miRNA affect the predictive performance. Particularly, we evaluate the discriminant power of feature sets proposed in the literature, whose computational costs and composition vary widely. The computational experiments were carried out using sequence data from 45 species, which covered species from eight phyla. The predictive performance of the classification models induced using large training set sizes (≥ 1; 608) composed of instances extracted from real and pseudo human pre-miRNA sequences did not differ significantly among the feature sets that lead to the maximal accuracies. Moreover, the differences in the predictive performances obtained by these models, due to the learning algorithms, were neglectable. Inspired by these results, we obtained a feature set which can be computed 34 times faster than the less costly among those feature sets, producing the maximal accuracies, albeit the proposed feature set has achieved accuracy within 0.1% of the maximal accuracies. When classification models using the elements previously discussed were induced using small training sets (120) from 45 species, we showed that the feature sets that produced the highest accuracies in the classification of human sequences were also more likely to produce higher accuracies for other species. Nevertheless, we showed that the learning complexity of pre-miRNAs vary strongly among species, even among those from the same phylum. These results showed that the existence of specie specific features indicated in previous studies may be correlated with the learning complexity. As a consequence, the predictive accuracies of models induced with different species and same features and instances spaces vary largely. In our results, we show that the use of training examples from species phylogenetically more complex may increase the predictive performances for less complex species. Finally, by using ensembles of computationally less costly feature sets, we showed alternative ways to increase the predictive performance for many species while keeping the computational costs of the analysis lower than those using the feature sets from the literature. Since in miRNA discovery the number of putative miRNA loci is in the order of millions, the analysis of putative miRNAs using a computationally expensive feature set and or inaccurate models would be wasteful or even unfeasible for large genomes. In this work, we explore most of the learning aspects implemented in current ab initio pre-miRNA prediction tools, which may lead to the development of new efficient ab initio pre-miRNA discovery tools / O sequenciamento de pequenos RNAs surgiu recentemente como uma tecnologia inovadora na descoberta de microRNAs (miRNA). Essa tecnologia tem facilitado a descoberta de milhares de miRNAs em um grande número de espécies. No entanto, apesar dos benefícios dessa tecnologia, ela apresenta desafios, como a necessidade de construir uma biblioteca de pequenos RNAs, além do genoma. Diferentemente, métodos computacionais ab initio buscam diretamente no genoma regiões prováveis de conter miRNAs. A maioria desses métodos usam modelos preditivos capazes de distinguir entre os verdadeiros (positivos) e pseudo precursores de miRNA - pre-miRNA - (negativos), os quais são induzidos utilizando técnicas de mineração de dados. No entanto, a aplicabilidade de métodos ab initio da literatura atual é limitada pelas altas taxas de falsos positivos e/ou por outras dificuldades computacionais, como o elevado tempo necessário para calcular um conjunto de atributos. Neste trabalho, investigamos como os principais aspectos envolvidos na indução de modelos preditivos de pre-miRNA afetam o desempenho preditivo. Particularmente, avaliamos a capacidade discriminatória de conjuntos de atributos propostos na literatura, cujos custos computacionais e a composição variam amplamente. Os experimentos computacionais foram realizados utilizando dados de sequências positivas e negativas de 45 espécies, cobrindo espécies de oito filos. Os resultados mostraram que o desempenho preditivo de classificadores induzidos utilizando conjuntos de treinamento com 1608 ou mais vetores de atributos calculados de sequências humanas não diferiram significativamente, entre os conjuntos de atributos que produziram as maiores acurácias. Além disso, as diferenças entre os desempenhos preditivos de classificadores induzidos por diferentes algoritmos de aprendizado, utilizando um mesmo conjunto de atributos, foram pequenas ou não significantes. Esses resultados inspiraram a obtenção de um conjunto de atributos menor e que pode ser calculado até 34 vezes mais rapidamente do que o conjunto de atributos menos custoso produzindo máxima acurácia, embora a acurácia produzida pelo conjunto proposto não difere em mais de 0.1% das acurácias máximas. Quando esses experimentos foram executados utilizando vetores de atributos calculados de sequências de outras 44 espécies, os resultados mostraram que os conjuntos de atributos que produziram modelos com as maiores acurácias utilizando vetores calculados de sequências humanas também produziram as maiores acurácias quando pequenos conjuntos de treinamento (120) calculados de exemplos de outras espécies foram utilizadas. No entanto, a análise destes modelos mostrou que a complexidade de aprendizado varia amplamente entre as espécies, mesmo entre aquelas pertencentes a um mesmo filo. Esses resultados mostram que a existência de características espécificas em pre-miRNAs de certas espécies sugerida em estudos anteriores pode estar correlacionada com a complexidade de aprendizado. Consequentemente, a acurácia de modelos induzidos utilizando um mesmo conjunto de atributos e um mesmo algoritmo de aprendizado varia amplamente entre as espécies. i Os resultados também mostraram que o uso de exemplos de espécies filogeneticamente mais complexas pode aumentar o desempenho preditivo de espécies menos complexas. Por último, experimentos computacionais utilizando técnicas de ensemble mostraram estratégias alternativas para o desenvolvimento de novos modelos para predição de pre-miRNA com maior probabilidade de obter maior desempenho preditivo do que estratégias atuais, embora o custo computacional dos atributos seja inferior. Uma vez que a descoberta de miRNAs envolve a análise de milhares de regiões genômicas, a aplicação prática de modelos preditivos de baixa acurácia e/ou que dependem de atributos computacionalmente custosos pode ser inviável em análises de grandes genomas. Neste trabalho, apresentamos e discutimos os resultados de experimentos computacionais investigando o potencial de diversas estratégias utilizadas na indução de modelos preditivos para predição ab initio de pre-miRNAs, que podem levar ao desenvolvimento de ferramentas ab initio de maior aplicabilidade prática