Search

Classifiers Performance. The document contains information on the ensemble learning approach with regards to the performance of each classifier. (PDF 1280 kb)

FACEPE O trabalho proposto nesta dissertação, se trata de um novo algoritmo evolucionário para a área de Subgroup Discovery “SD”, com foco na mineração de padrões em conjuntos de dados numéricos de alta dimensionalidade. Subgroup Discovery é uma técnica descritiva para mineração de dados, cujo objetivo é encontrar e descrever subgrupos em conjuntos de dados, a partir de propriedades de interesse previamente definidas. A área em questão possui uma ampla gama de aplicações e casos de uso, porém poucas dessas técnicas são capazes de atuar adequadamente sobre atributos numéricos contínuos. O que pode ser considerado um problema, tendo em vista que conjuntos de dados provenientes do mundo real recorrentemente possuem atributos de diferentes tipos. Para poder trabalhar com dados contínuos, algumas técnicas de SD demandam discretização prévia de tais atributos. Porém, esse tipo de solução tende a trazer perda de informações e resultados imprecisos. Devido ao rápido desenvolvimento das tecnologias de coleta e armazenamento de dados, problemas cada vez mais complexos tendem a surgir. Um bom exemplo, são os conjuntos de dados de alta dimensionalidade, que, por sua vez, podem possuir centenas de milhares de atributos, tornando ainda mais desafiadora a tarefa de mineração de padrões e consequentemente, a descoberta de subgrupos. Até o momento, não existem trabalhos publicados na área com foco em conjuntos numéricos de alta dimensionalidade. Então, o rabalho aqui proposto visa otimizar o processo de descoberta de subgrupos por meio de dois aspectos principais, que são: i) trabalhar adequadamente com dados contínuos sem eixar de abranger categóricos, e ii) propor uma estratégia evolucionária capaz de lidar com conjuntos de dados de alta dimensionalidade. Após a realização de um amplo estudo experimental, o algoritmo proposto se demonstrou competitivo e, muitas vezes, superior em relação a outras técnicas do estado da arte e trabalhos recém-publicados na área. The work proposed in this dissertation, is a new evolutionary algorithm for the Subgroup Discovery “SD” area, and its main focus is the mineration of patterns in high dimensionality numerical datasets. Subgroup Discovery is a descriptive technique for data mining, which aims to find and describe subgroups in data, accordingly to predefined interest properties. The SD area have a wide range of applications and use cases, but few are able to perform properly over continuous numerical attributes, what can be seen as a problem, given that real word related datasets, usually have mixed data types. To work with continuous data, some SD techniques require a previous discretization, but this kind of solution may lead to information loss and imprecise results. The fast development of data collecting and storage technologies is leading to the emergence of new complex problems, such as high dimensional data, which can easily have hundreds of thousands attributes, making the pattern mining task and consequently subgroup discovery, even harder in those scenarios. To the moment this work is being presented, there are no published techniques in the area, that address the problem of high dimensional numerical datasets; so the proposed algorithm aims to optimize the subgroup discovery process by means of: Properly representation of numerical data without neglecting categorical data; together with an evolutionary strategy able to deal with high dimensionality data. After an extensive experimental study, the proposed algorithm showed itself competitive and many times superior when compared with other state of the art techniques and recently published works.

Knowledge Discovery in Databases (KDD) is a broad area in Artificial Intelligence concerned with the extraction of useful information and insights from a given dataset. Among the distinct extraction methodologies, an important subclass of KDD tasks, called Subgroup Discovery (SD), undertakes the discovery of interesting subsets in the data. Many Evolutionary Algorithms (EAs) have been proposed to solve the Subgroup Discovery task with considerable success in low dimensional datasets. Some of these, however, have been shown to perform poorly in high dimensional problems. The currently best performing Evolutionary Algorithm for Subgroup Discovery in high dimensional datasets, SSDP, has a peculiar way of initializing its populations, limiting the individuals to the smallest possible size. As with most population-based techniques, the outcome of an Evolutionary Algorithm is usually dependent on the initial set of solutions, which are typically generated at random. The impact of choosing one initialization technique over another in the final presented solution has been the topic of many published works in the broad area of evolutionary computation. Despite this, there is still a lack of studies which approach this topic in the specific scenario of Subgroup Discovery tasks, especially when considering high dimensional datasets. The ultimate goal of this research project is to evaluate the impact of initial population generation in the end result of the overall Evolutionary Algorithm used to solve a Subgroup Discovery task in high dimensional data. Specifically, we provide new initialization methods, designed for the specific characteristics of Subgroup Discovery tasks, which can be used in virtually any EA. Our conducted experiments show that, by just changing the initialization method, state of the art Evolutionary Algorithms have their performance increased in high dimensional datasets. Descoberta de Conhecimento em Bases de Dados (KDD) é uma área ampla em Inteligência Artificial que se preocupa com a extração de informações e insights úteis a partir de um conjunto de dados. Dentre as diferentes metodologias de extração, uma importante subclasse de tarefas de KDD, chamada de Descoberta de Subgrupos (SD), lida com a descoberta de subconjuntos interessantes dentro dos dados. Vários Algoritmos Evolucionários (EAs) foram propostos para resolver a tarefa de descobrir subgrupos com sucesso considerável em bases de dados de baixa dimensionalidade. A literatura já mostrou, no entanto, que alguns desses tem uma performance baixa em problemas de alta dimensionalidade. O algoritmo evolucionário para descoberta de subgrupos com, atualmente, a melhor performance em bases de alta dimensionalidade, SSDP, possui uma forma peculiar de inicializar sua população, limitando os indivíduos ao menor tamanho possível. Assim como na maioria das técnicas baseadas em população, o resultado de um algoritmo evolucionário é, em geral, dependente do conjunto de soluções inicial, que é tipicamente gerado de forma aleatória. Escolher uma técnica de inicialização sob outra tem grande impacto na solução final apresentada, e este já foi o tópico de trabalhos publicados na área de computação evolucionária. Apesar disso, faltam trabalhos que estudem este tópico no caso específico de descoberta de subgrupos, especialmente quando são consideradas bases de alta dimensionalidade. O objetivo final desta pesquisa é avaliar o impacto da geração da população inicial no resultado final de um algoritmo evolucionário no contexto de uma tarefa de descoberta de subgrupos em dados de alta dimensionalidade. Especificamente, são apresentados novos métodos de inicialização, projetados para as características específicas de tarefas de descoberta de subgrupos, que podem ser utilizadas em praticamente qualquer algoritmo evolucionário. Os experimentos conduzidos mostram que mudar o método de inicialização é o suficiente para aumentar a performance de algoritmos evolucionários o estado da arte em bases de dados de alta dimensionalidade.

FACEPE Esta tese tem o objetivo de propor soluções para a mineração de subgrupos no contexto de bases de dados de alta dimensionalidade. A mineração de subgrupos (do inglês subgroup discovery) representa uma poderosa ferramenta para análise exploratória de dados, uma vez que apresenta informações normalmente não detectadas pela estatística tradicional. O objetivo da mineração de subgrupos é identificar conjuntos de características que discriminem um grupo alvo dos demais (ex. tratamentos médicos de sucesso dos fracassados). Existem diversas heurísticas para mineração de subgrupos, mas nenhuma delas com foco em bases de alta dimensionalidade. Isso representa uma importante lacuna na área, uma vez que se torna mais natural a necessidade de se extrair informações de conjuntos de dados de alta dimensionalidade. Nas áreas de bioinformática e classificação de documentos, por exemplo, é comum a extração de conhecimento a partir de bases com número de atributos na ordem de 10⁴. É comum também nos algoritmos de mineração de subgrupos o uso de muitos parâmetros de ajuste não trivial. Isso dificulta o uso de tais técnicas, principalmente por usuários de áreas não relacionadas à mineração de dados. Nesse contexto, nós propomos a primeira heurística para mineração de subgrupos com foco em bases de dados de alta dimensionalidade que utiliza apenas dois parâmetros. Outro problema da área é assegurar que os subgrupos retornados não sejam redundantes entre si e que representem de forma ampla os dados do alvo da investigação. No entanto, subgrupos considerados redundantes podem representar soluções mais fáceis de serem aplicadas num problema. Assim, nós propomos uma forma inovadora de controlar a redundância, minimizando o risco do descarte prematuro de subgrupos relevantes e gerando mais informações para o usuário. Por fim, nós desenvolvemos um modelo baseado em mineração de subgrupos para o problema de descrição do perfil de comunidades (do inglês group profiling), que consiste no processo de construção de perfis descritivos para comunidades em redes sociais. A proposta teve como principais diferenciais gerar descrições multivariadas e com alta cobertura global. This doctoral aims to propose solutions for subgroup discovery problems focusing on high dimensional data sets. Subgroup discovery represents a powerful tool for exploratory data analysis as it presents information normally not detected by traditional statistical methods. The purpose of subgroup discovery is to identify sets of characteristics that discriminate one target group from the other (e.g. successful medical treatments of failures). There are several heuristics for subgroup discovery, but none of them focuses on high dimensional data sets. This represents an important gap in the area as it becomes more natural to extract information from high dimensional data sets. In the bioinformatics and document classification realms, for example, it is common to have knowledge extraction from data sets with number of attributes on the order of 10⁴. The use many non-trivial adjustment parameters is also common in subgroup discovery algorithms. In this context, we propose the first heuristic for subgroup mining focusing on high dimensional data sets that use only two parameters. Another problem in this area is to ensure that the returned subgroups are not redundant with each other and that they represent broadly the data of the research. However, subgroups considered redundant may represent easier solutions to a problem. Thus, we propose an innovative way of controlling redundancy, minimizing the risk of premature discarding of relevant subgroups and generating more information for the user. Finally, we have developed a subgroup mining model for the group profiling problem, which is the process of constructing descriptive profiles for communities in social networks. The distinct aspect of the research was the proposal to generate multivariate descriptions with high global coverage.

Um grande desafio do crescimento exponencial dedados no mundo é a extração de conhecimento em bases de alta dimensionalidade. Essa característica é muito comum em bases de domínio biomédico. Uma técnica utilizada para extração do conhecimento é chamada de mineração de Padrões Discriminativos (PDs) que objetiva em contrar informações interessantes que ocorram com frequência desproporcional em uma classe(atributo) em relação as outras. A maioria dos algoritmos exaustivos para mineração de PDstem sidos propostos com o objetivo de solucionar problemas dedados tradicionais de baixa dimensionalidade. Dessa maneira se tornou criticamente necessário investigar se esses algoritmos podem ser aplicados a dados biomédicos de alta dimensionalidade. Esse trabalho tem como objetivo comparar o comportamento das abordagens exaustivas dos PDs em bases reais comum se de alta dimensionalidade. Para isso experimentos foram realizados com os algoritmos APRIORI-SD, SD-Map eRCS, utilizando bases da UCI(Machine Learning Repository) e biomédicas de microarrays. Os experimentos revelaram que os algoritmos não são os mais apropriados as bases biomédicas de alta dimensionalidade, entretanto para um algoritmo houve algum retorno dePD e dois algoritmos tiveram bons desempenho sem bases tradicionais de baixa dimensionalidade. A major challenge of exponential data growth in the world is the extraction of knowledge in high dimensional databases. This feature is very common on biomedical domain bases. A technique used to extract knowledge is called Discriminative Patterns mining(DPs) that aims to find interesting information that occurs disproportionately in one class (attribute) in relation to the others. Most of the exhaustive algorithms for DPmining have been proposed with the aim of solving traditional low-dimensional data problems. In this way it has become critically necessary to investigate whether these algorithms can be applied to high dimensional biomedical data. The objective of this work is to compare the behavior of the exhaustive approaches of PDs in common and high dimensionality real bases. For this purpose experiments were performed using the APRIORI-SD, SD-Map and RCS algorithms, using the bases of the UCI(Machine Learning Repository) and biomedical microarrays. The experiments revealed that the algorithms are not the most appropriate biomedical bases of high dimensionality, However for an algorithm there was some return of PDs and two algorithms had good performances in traditional bases of low dimensionality.