Made available in DSpace on 2013-08-07T18:43:07Z (GMT). No. of bitstreams: 1 000449231-Texto+Completo-0.pdf: 1860025 bytes, checksum: 1ace09799e27fa64938e802d2d91d1af (MD5) Previous issue date: 2012 / In the Data Mining area experiments have been carried out using Ensemble Classifiers. We experimented Random Forests to evaluate the performance when randomness is applied. The results of this experiment showed us that the impact of randomness is much more relevant in Random Forests when compared with other algorithms, e. g., Bagging and Boosting. The main purpose of this work is to decrease the effect of randomness in Random Forests. To achieve the main purpose we implemented an extension of this method named Stochastic Random Forests and specified the strategy to increase the performance and stability combining the results. At the end of this work the improvements achieved are presented. / Na área de Mineração de Dados, experimentos vem sendo realizados utilizando Conjuntos de Classificadores. Estes experimentos são baseados em comparações empíricas que sofrem com a falta de cuidados no que diz respeito à questões de aleatoriedade destes métodos. Experimentamos o Random Forests para avaliar a eficiência do algoritmo quando submetido a estas questões. Estudos sobre os resultados mostram que a sensibilidade do Random Forests é significativamente maior quando comparado com a de outros métodos encontrados na literatura, como Bagging e Boosting. O proposito desta dissertação é diminuir a sensibilidade do Random Forests quando submetido a aleatoriedade. Para alcançar este objetivo, implementamos uma extensão do método, que chamamos de Random Forests Estocástico. Logo especificamos como podem ser alcançadas melhorias no problema encontrado no algoritmo combinando seus resultados. Por último, um estudo é apresentado mostrando as melhorias atingidas no problema de sensibilidade.

Made available in DSpace on 2015-08-18T02:05:38Z (GMT). No. of bitstreams: 1 000473651-Texto+Completo-0.pdf: 15125610 bytes, checksum: 0ae5116bc2669408e12c87781990c0a8 (MD5) Previous issue date: 2015 / Frequent Itemsets Mining (FIM) is a data mining task used to find relations between dataset items. Apriori is the traditional algorithm of the Generate-and-Test class to discover these relations. Recent studies show that this algorithm and others of this task are not adapted to execute in contexts with uncertainty because these algorithms are not prepared to handle with the probabilities associated to items of the dataset. Nowadays, data with uncertainty occur in many applications, for example, data collected from sensors, information about the presence of objects in satellite images and data from application of statistical methods. Due to big datasets with associated uncertainty, new algorithms have been developed to work in this context: UApriori, UF-Growth and UH-Mine. UApriori, specially, is an algorithm based in expected support, often addressed by scientific community. On the one hand, when this algorithm is applied to big datasets, in a context with associated probabilities to dataset items, it does not present good scalability. On the other hand, some works have evolved the Apriori algorithm joining with the model of programming MapReduce, in order to get a better scalability. With this model, it is possible to discover frequent itemsets using parallel and distributed computation. However, these works focus their efforts on discovering frequent itemsets on deterministic datasets. This thesis present the development, implementation and experiments applied to three algorithms: UAprioriMR, UAprioriMRByT and UAprioriMRJoin. The three cited algorithms evolve the traditional algorithm Apriori, integrating the model of programming MapReduce, on contexts with uncertainty. The algorithm UAprioriMRJoin is a hybrid algorithm based on the UAprioriMR and UAprioriMRByT algorithms. The experiments expose the good performance of the UAprioriMRJoin algorithm, when applied on big datasets, with many distinct items and a small average number of items per transaction in a cluster of nodes. / Frequent Itemsets Mining (FIM) é uma tarefa de mineração de dados utilizada para encontrar relações entre os itens de um dataset. O Apriori é um tradicional algoritmo da classe Generateand- Test para descobrir tais relações. Estudos recentes mostram que este e outros algoritmos desta tarefa não estão aptos para executar em contextos onde haja incerteza associada, pois eles não estão preparados para lidar com as probabilidades existentes nos itens do dataset. A incerteza nos dados ocorre em diversas aplicações como, por exemplo, dados coletados de sensores, informações sobre a presença de objetos em imagens de satélite e dados provenientes da aplicação de métodos estatísticos. Dada a grande quantidade de dados com incertezas associadas, novos algoritmos têm sido desenvolvidos para trabalharem neste contexto: UApriori, UF-Growth e UH-Mine. O UApriori, em especial, é um algoritmo baseado em suporte esperado, abordado frequentemente pela comunidade acadêmica. Quando este algoritmo é aplicado sobre grandes datasets, em um contexto com probabilidades associadas aos itens do dataset, ele não apresenta boa escalabilidade. Por outro lado, alguns trabalhos têm adaptado o algoritmo Apriori para trabalhar com o modelo de programação MapReduce, a fim de prover uma melhor escalabilidade. Utilizando este modelo, é possível descobrir itens frequentes de modo paralelo e distribuído. No entanto, tais trabalhos focam seus esforços na descoberta de itens frequentes sobre datasets determinísticos. Esta tese apresenta o desenvolvimento, implementação e os experimentos realizados, a partir da aplicação e discussão de três algoritmos: UAprioriMR, UAprioriMRByT e UAprioriMRJoin. Os três algoritmos citados evoluem o algoritmo tradicional Apriori para que possam executar com o modelo de programação MapReduce sobre contextos com incerteza associada. O algoritmo UAprioriMRJoin é um algoritmo híbrido com base nos algoritmos UAprioriMR e UAprioriMRByT. Os experimentos revelam o bom desempenho do algoritmo UAprioriMRJoin quando aplicado sobre grandes datasets, com muitos atributos e um número médio pequeno de itens por transação, em um cluster de nodos.

Submitted by Fernanda Rodrigues de Lima (fernanda.rlima@ufpe.br) on 2018-08-17T21:55:27Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Mauricio Aldenor dos Santos.pdf: 3088895 bytes, checksum: 53a5e877c5c57c34635e64d58ff43740 (MD5) / Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-08-24T21:07:37Z (GMT) No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Mauricio Aldenor dos Santos.pdf: 3088895 bytes, checksum: 53a5e877c5c57c34635e64d58ff43740 (MD5) / Made available in DSpace on 2018-08-24T21:07:37Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Mauricio Aldenor dos Santos.pdf: 3088895 bytes, checksum: 53a5e877c5c57c34635e64d58ff43740 (MD5) Previous issue date: 2017-06-20 / 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.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2016. / Made available in DSpace on 2017-02-14T03:06:56Z (GMT). No. of bitstreams: 1 343948.pdf: 14369382 bytes, checksum: e0cac31809638d99cc3af79fe29381bd (MD5) Previous issue date: 2016 / Vários métodos de mineração de dados têm sido propostos no últimosanos para descobrir diferentes tipos de padrões entre dois ou mais objetosem movimento. Apenas algumas obras identificam anomalias nocomportamento de objetos em torno de determinadas regiões de interesse(ROI), tais como câmeras de vigilância, edifícios comerciais, etc,que podem ser de interesse para diversos domínios de aplicação, principalmentena área de segurança. Neste trabalho são definidos novos tiposde comportamento anômalo de objetos em movimento em relação à regiãode interesse, incluindo surround, escape, return e avoidance. Combase nesses tipos de comportamento anômalo é proposto: (i) um algoritmopara calcular estes comportamentos; (ii) um conjunto de funçõespara pesar o grau de comportamento anômalo de cada objeto em movimento;e (iii) uma classificaçao dos objetos em movimento de acordocom o grau de comportamento anômalo em relação a um conjunto deregiões. O método proposto é avaliado com dados reais de trajetóriase é mostrado que o trabalho relacionado mais próximo não detecta oscomportamentos propostos e classifica os objetos considerando apenasum tipo de movimento anômalo.<br> / Abstract : Several data mining methods have been proposed in the last few yearsfor discovering different types of patterns among two or more movingobjects. Only a few works identify unusual behavior of objects aroundgiven Regions of Interest (ROI), such as surveillance cameras, commercialbuildings, etc, that may be interesting for several applicationdomains, mainly for security. In this thesis we define new types ofunusual behavior of moving objects in relation to ROI, including surround,escape, return, and avoidance. Based on these types of unusualbehavior we (i) present an algorithm to compute these behaviors, (ii)define a set of functions to weight the degree of unusual behavior ofevery moving object in the database, and (iii) rank the moving objectsaccording to the degree of unusual behavior in relation to a set of ROIs.We evaluate the proposed method with real trajectory data and showthat the closest work does not detect the proposed behaviors and ranksobjects considering only one type of unusual movement.

Submitted by Fernanda Rodrigues de Lima (fernanda.rlima@ufpe.br) on 2018-10-08T20:40:03Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Mailson Melo dos Santos Filho.pdf: 1618446 bytes, checksum: 2d7170f25c5f5001042914b1ce30dde9 (MD5) / Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-11-22T17:16:18Z (GMT) No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Mailson Melo dos Santos Filho.pdf: 1618446 bytes, checksum: 2d7170f25c5f5001042914b1ce30dde9 (MD5) / Made available in DSpace on 2018-11-22T17:16:18Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Mailson Melo dos Santos Filho.pdf: 1618446 bytes, checksum: 2d7170f25c5f5001042914b1ce30dde9 (MD5) Previous issue date: 2015-09-09 / CNPq / Os sistemas de suporte à decisão são utilizados para auxiliar os gestores na tomada de decisão, inclusive, de alto nível. Eles implementam todas as etapas do processo de extração de conhecimento em banco de dados (KDD - Knowledge-Discovery in Databases) e o ambiente de consultas a dados e conhecimento, incluindo simulação de cenários sobre os indicadores do negócio (KPIs - Key Performance Indicators). As ferramentas OLAP (Online Analytical Processing) oferecem um ambiente para consultas que permite a análise de um grande volume de dados, por meio de cruzamento entre dados, apresentação de perspectiva de processamento multinível (hierarquias) para os dados e funções de perfuração e fatiamento dos conjuntos entre outras. Estas ferramentas têm interface amigável com o decisor humano apresentando gráficos, modelos e sumarizações, mas são limitadas a operações diretas e à validação de conhecimento humano sobre os dados do negócio. No processo de KDD, a mineração de dados usa inteligência artificial e estatística para extração de conhecimento dos dados e para apoiar a decisão humana em atividades de inferência e previsão. OLAM (Online Analytical Mining) é um conceito equivalente ao OLAP para navegação sobre o conhecimento extraído e sobre o efeito da sua aplicação na tomada de decisões sobre o desempenho do negócio tanto nos indicadores técnicos de inteligência artificial quanto nos KPIs. No entanto, não foi encontrado ferramental genérico que permita realizar de forma sistemática o OLAM. A proposta desse trabalho é mostrar que algumas operações fundamentais de OLAM podem ser implementadas por meio de ferramentas OLAP, mediante amostragem de dados com independência estatística submetidos à mineração e a certas transformações de dados. O trabalho é validado por meio de um problema de decisão binária, no qual a resposta do algoritmo de mineração de dados (escore de propensão) sobre a massa de dados estatisticamente independente passa a ser uma medida no data warehouse. O trabalho demonstra que essa abordagem permite a geração de cubos associado à classe-alvo e aos KPIs para avaliação de desempenho, tornando a ferramenta OLAP capaz de realizar OLAM. Ao final, o trabalho analisa as principais limitações das ferramentas OLAP que as impede de implementar OLAM com mais flexibilidade e as implicações conceituais e operacionais para serem superadas. / Decision support systems are used to assist managers inclusive in making high-level decisions. They implement all stages of knowledge extraction process in database (KDD - Knowledge Discovery in Databases) and the environment queries to data and knowledge, including simulation scenarios on the business indicators (KPIs - Key Performance Indicators). The OLAP (Online Analytical Processing) provides an environment for queries that allows analysis of large volumes of data through data merging, multilevel processing perspective presentation (hierarchies) for data and drilling functions and slicing of among other sets of functions. These tools have user-friendly interface with the human decision maker presenting graphics, models and summarization, but are limited to direct operations and human knowledge validation on business data. In the process of KDD, data mining uses artificial intelligence and statistical techniques for knowledge extraction in inference and forecasting activities for supporting human decision. OLAM (Online Analytical Mining) is a concept equivalent to OLAP to navigation on the extracted knowledge and the effect of applying them in making decisions about business performance both in technical indicators artificial intelligence as the KPIs. However, it was not found generic tools that allows perform systematically the OLAM. The purpose of this paper is to show that some fundamental operations of OLAM can be implemented by means of OLAP tools, sampled data with statistical independence subject to certain mining and data transformations. The job is validated by means of a binary decision problem, in which the response data mining algorithm (propensity score) statistically independent data about the mass becomes a measure in the data warehouse. The work demonstrates that this approach allows the generation of cubes associated with class-blalvo and KPIs for performance evaluation, making OLAP tool capable of performing OLAM. Finally, the paper analyzes the main limitations of OLAP tools that prevents them from implementing OLAM with more flexibility and the conceptual and operational implications for trying to overcome.

Nesta tese são investigados três problemas básicos em aprendizado supervisionado: seleção de atributos, composição de atributos e combinação de classificadores simbólicos. A seleção de atributos é uma atividade de pré-processamento de dados que seleciona um subconjunto de atributos do conjunto original de exemplos. Existem, basicamente, três abordagens que são empregadas para a seleção de atributos: embutida, filtro e wrapper; as duas últimas pesquisadas neste trabalho. Os experimentos realizados, utilizando diversos indutores e conjuntos de exemplos, para avaliar as abordagens filtro e wrapper nos permitem concluir que o uso de filtros deve ser considerado antes de se cogitar a utilização de wrappers, no caso de existirem muitos atributos para descrever os exemplos. Sob a perspectiva de compreensibilidade do conhecimento induzido, a análise sobre o impacto da seleção de atributos em um classificador simbólico mostrou um aumento do número de regras e do número de condições por regra. A composição de atributos, também conhecida como indução construtiva, é outra atividade de pré-processamento de dados. Dentre as várias abordagens de composição de atributos (guiada por dados, por hipótese, por conhecimento e multi-estratégia), nesta tese é proposta uma metodologia para composição de atributos guiada pelo conhecimento. Os resultados dos experimentos realizados utilizando a metodologia proposta mostram que, mesmo com o auxílio do usuário/especialista, é difícil construir atributos derivados que sejam realmente relevantes para aprender o conceito embutido nos conjuntos de exemplos analisados de repositórios (naturais), os quais, muitas vezes, já foram pré-processados. Esse fato foi confirmado, por um trabalho posterior, com dados do mundo real, no qual a metodologia proposta mostrou seu potencial. A combinação de classificadores, simbólicos ou não, é uma atividade de mineração de dados. Na realidade, uma das preocupações do Aprendizado de Máquina simbólico é que os classificadores induzidos devem ser fáceis de serem compreendidos pelos seres humanos. Para isso, deve-se escolher o indutor com bias mais adequado para cada tipo de situação, já que pesquisas mostraram que não existe o 'melhor' indutor para todos os domínios. Aliada a essa escolha, é possível fazer uso de vários classificadores, combinando-os num único classificador final, formando um ensemble. Os ensembles possuem a tendência de melhorar o desempenho na classificação de exemplos não vistos durante o processo de aprendizado. Entretanto, o emprego de ensembles dificulta a compreensão humana sobre o comportamento do classificador final, já que ele deixa de ser simbólico, mesmo assumindo que cada classificador individual que o compõe seja simbólico. Na realidade, a combinação de classificadores simbólicos - provenientes de diferentes indutores - em um classificador final também simbólico é um tópico novo de pesquisa, ainda com poucos resultados divulgados. Com o objetivo de preencher essa lacuna, é proposto e desenvolvido neste trabalho o sistema Xruler. Para isso, inicialmente foi definido o formato padrão de regras PBM, o qual fornece uma perspectiva unificada sob a qual todo classificador simbólico pode ser convertido e analisado. Dentre outros componentes, o sistema Xruler possui um algoritmo de cobertura que pode ser aplicado ao conjunto de regras induzidas por diversos indutores para se obter um classificador simbólico final. Nos experimentos realizados com o sistema Xruler os resultados obtidos mostraram aumento da precisão e redução do número de regras. Sob o aspecto sintático das regras, isso pode ser considerado um avanço no sentido de uma maior compreensibilidade por seres humanos do conjunto final de regras.

Nesta tese são investigados três problemas básicos em aprendizado supervisionado: seleção de atributos, composição de atributos e combinação de classificadores simbólicos. A seleção de atributos é uma atividade de pré-processamento de dados que seleciona um subconjunto de atributos do conjunto original de exemplos. Existem, basicamente, três abordagens que são empregadas para a seleção de atributos: embutida, filtro e wrapper; as duas últimas pesquisadas neste trabalho. Os experimentos realizados, utilizando diversos indutores e conjuntos de exemplos, para avaliar as abordagens filtro e wrapper nos permitem concluir que o uso de filtros deve ser considerado antes de se cogitar a utilização de wrappers, no caso de existirem muitos atributos para descrever os exemplos. Sob a perspectiva de compreensibilidade do conhecimento induzido, a análise sobre o impacto da seleção de atributos em um classificador simbólico mostrou um aumento do número de regras e do número de condições por regra. A composição de atributos, também conhecida como indução construtiva, é outra atividade de pré-processamento de dados. Dentre as várias abordagens de composição de atributos (guiada por dados, por hipótese, por conhecimento e multi-estratégia), nesta tese é proposta uma metodologia para composição de atributos guiada pelo conhecimento. Os resultados dos experimentos realizados utilizando a metodologia proposta mostram que, mesmo com o auxílio do usuário/especialista, é difícil construir atributos derivados que sejam realmente relevantes para aprender o conceito embutido nos conjuntos de exemplos analisados de repositórios (naturais), os quais, muitas vezes, já foram pré-processados. Esse fato foi confirmado, por um trabalho posterior, com dados do mundo real, no qual a metodologia proposta mostrou seu potencial. A combinação de classificadores, simbólicos ou não, é uma atividade de mineração de dados. Na realidade, uma das preocupações do Aprendizado de Máquina simbólico é que os classificadores induzidos devem ser fáceis de serem compreendidos pelos seres humanos. Para isso, deve-se escolher o indutor com bias mais adequado para cada tipo de situação, já que pesquisas mostraram que não existe o 'melhor' indutor para todos os domínios. Aliada a essa escolha, é possível fazer uso de vários classificadores, combinando-os num único classificador final, formando um ensemble. Os ensembles possuem a tendência de melhorar o desempenho na classificação de exemplos não vistos durante o processo de aprendizado. Entretanto, o emprego de ensembles dificulta a compreensão humana sobre o comportamento do classificador final, já que ele deixa de ser simbólico, mesmo assumindo que cada classificador individual que o compõe seja simbólico. Na realidade, a combinação de classificadores simbólicos - provenientes de diferentes indutores - em um classificador final também simbólico é um tópico novo de pesquisa, ainda com poucos resultados divulgados. Com o objetivo de preencher essa lacuna, é proposto e desenvolvido neste trabalho o sistema Xruler. Para isso, inicialmente foi definido o formato padrão de regras PBM, o qual fornece uma perspectiva unificada sob a qual todo classificador simbólico pode ser convertido e analisado. Dentre outros componentes, o sistema Xruler possui um algoritmo de cobertura que pode ser aplicado ao conjunto de regras induzidas por diversos indutores para se obter um classificador simbólico final. Nos experimentos realizados com o sistema Xruler os resultados obtidos mostraram aumento da precisão e redução do número de regras. Sob o aspecto sintático das regras, isso pode ser considerado um avanço no sentido de uma maior compreensibilidade por seres humanos do conjunto final de regras.

Made available in DSpace on 2019-03-30T00:05:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2018-05-14 / Clustering ensembles (CE) is an approach that takes advantage of a set of clusterings, known as base partitions, to generate a consensus solution. The related literature has shown that usually the consensus partition has better quality in comparison with the single base partitions. This work tackles the CE problem from a hedonic game theoretical perspective. In the formulated cooperative game, the points (instances or objects) are viewed as players, while clusters are regarded as coalitions. The preferences of each player are stored in an evidence-accumulation matrix, obtained through the base partitions, which has properties that guarantee the existence of at least one Nash stable coalition structure. That is, a coalition structure where players do not have the incentive to move from their own coalition to another existent coalition. To achieve this kind of solution, we proposed the HGCE (Hedonic Game based Clustering Ensemble) algorithm, which is based on the best dynamics approach. Initially each player is in a singleton coalition, composed by itself. After that, in each iteration, each player has the option to switch to a new coalition where it will obtain a better payoff. This process repeats itself until it reaches an equilibrium, where players do not benefit anymore by changing coalitions. Because different coalition structures may emerge due to the order of the playes, we also developed a version of HGCE where the final solution is independent of the players ordering. Empirical experiments conducted on several data sets have shown that the coalition structure obtained by HGCE is frequently a better clustering solution in comparison with clusterings generated from others well known CE algorithms. The experiments also show that HGCE is computational efficient and resilient to random perturbations on the base partitions used as input of the algorithm. Keywords: Clustering, Clustering ensemble, Coalition, Hedonic games, Cooperative game theory. / Clustering ensembles (CE) é uma abordagem que se aproveita de um conjunto de cluster- ings, conhecidos como partições-base, para produzir uma partição consenso. A literatura tem demonstrado que a qualidade das partições obtidas pela abordagem CE é geralmente superior à qualidade das partições-base, quando consideradas individualmente. Este tra- balho aborda o problema de CE sob a perspectiva dos jogos hedônicos. No jogo cooperativo formulado, os pontos (instâncias ou objetos) são vistos como jogadores, enquanto os clus- ters são encarados como coalizões. As preferências de cada jogador são armazenadas em uma matriz de similaridade, obtida através das partições-base, que contém propriedades que garantem a existência de pelo menos uma estrutura de coalizão Nash estável. Ou seja, uma estrutura de coalizão em que os jogadores não possuem o incentivo de mudar de suas próprias coalizões para outra coalizão existente. Para alcançar esse tipo de solução, nós propusemos o algoritmo HGCE (Hedonic Game based Clustering Ensemble) que é baseado na abordagem de best response dynamics. Inicialmente, cada jogador está em uma coalizão com um elemento, composta por ele mesmo. Depois disso, em cada iteração, cada jogador pode se mover para uma nova coalizão, caso ele obtenha um payoff melhor. Este processo se repete até um equilíbrio ser alcançado, em que nenhum jogador se beneficia em mudar de coalizão. Pelo fato de diferentes estruturas de coalizão emergirem de acordo com a ordem dos jogadores, nós também desenvolvemos uma versão do algoritmo HGCE que é independente da ordem dos jogadores. Experimentos empíricos conduzidos em diversos conjuntos de dados mostram que a estrutura de coalizão obtida pelo algoritmo HGCE, em grande parcela dos casos, é uma solução de clustering melhor quando comparada com soluções obtidas por outros algoritmos que também adotam a abordagem de CE. Os experimentos mostram que o HGCE é computacionalmente eficiente e se demonstra resiliente a perturbações nas partições-base utilizadas como entrada do algoritmo. Palavras-chave: Clustering, Clustering ensembles, Coalizão, Jogos hedônicos, Teoria dos jogos cooperativos.

Made available in DSpace on 2013-08-07T18:43:36Z (GMT). No. of bitstreams: 1 000422461-Texto+Completo-0.pdf: 1656872 bytes, checksum: 4520cf1ef2435e86327deed3e89baed9 (MD5) Previous issue date: 2009 / Model trees are a particular case of decision trees employed to solve regression problems, where the variable to be predicted is continuous. They have the advantage of presenting an interpretable output, helping the end-user to get more confidence in the prediction and providing the basis for the end-user to have new insight about the data, confirming or rejecting hypotheses previously formed. Moreover, model trees present an acceptable level of predictive performance in comparison to most techniques used for solving regression problems. Since generating the optimal model tree is a NPComplete problem, traditional model tree induction algorithms make use of a greedy top-down divideand- conquer strategy, which may not converge to the global optimal solution. In this work, we propose the use of the evolutionary algorithms paradigm as an alternate heuristic to generate model trees in order to improve the convergence to global optimal solutions. We test the predictive performance of this new approach using public UCI data sets, and we compare the results with traditional greedy regression/model trees induction algorithms. Results show that our approach presents a good tradeoff between predictive performance and model comprehensibility, which may be crucial in many data mining applications. / Árvores-modelo são um caso particular de árvores de decisão aplicadas na solução de problemas de regressão, onde a variável a ser predita é contínua. Possuem a vantagem de apresentar uma saída interpretável, auxiliando o usuário do sistema a ter mais confiança na predição e proporcionando a base para o usuário ter novos insights sobre os dados, confirmando ou rejeitando hipóteses previamente formadas. Além disso, árvores-modelo apresentam um nível aceitável de desempenho preditivo quando comparadas à maioria das técnicas utilizadas na solução de problemas de regressão. Uma vez que gerar a árvore-modelo ótima é um problema NP-Completo, algoritmos tradicionais de indução de árvores-modelo fazem uso da estratégia gulosa, top-down e de divisão e conquista, que pode não convergir à solução ótima-global. Neste trabalho é proposta a utilização do paradigma de algoritmos evolutivos como uma heurística alternativa para geração de árvores-modelo. Esta nova abordagem é testada por meio de bases de dados de regressão públicas da UCI, e os resultados são comparados àqueles gerados por algoritmos gulosos tradicionais de indução de árvores-modelo. Os resultados mostram que esta nova abordagem apresenta uma boa relação custo-benefício entre desempenho preditivo e geração de modelos de fácil interpretação, proporcionando um diferencial muitas vezes crucial em diversas aplicações de mineração de dados.

Made available in DSpace on 2014-06-06T02:01:22Z (GMT). No. of bitstreams: 1 000458539-Texto+Completo-0.pdf: 3705446 bytes, checksum: de3d802acba0f10f03298ee0277b51b1 (MD5) Previous issue date: 2014 / The usefulness of data mining and the process of Knowledge Discovery in Databases (KDD) has increased its importance as grows the volume of data stored in large repositories. A promising area for knowledge discovery concerns oil prospection, in which data used differ both from traditional and geographical data. In palaeogeographic data, temporal dimension is treated according to the geologic time scale, while the spatial dimension is related to georeferenced data, i. e. , latitudes and longitudes on Earth’s surface. This approach differs from that presented by spatio-temporal data mining algorithms found in literature, arising the need to evolve the existing ones to the context of this research. This work presents the development of a solution to employ a density-based spatio-temporal algorithm for mining palaeogeographic data on the Earth’s surface. An evolved version of the ST-DBSCAN algorithm was implemented in Java language making use of Weka API, where improvements were carried out in order to allow the data mining algorithm to solve a variety of research problems identified. A set of experiments that validate the proposed implementations on the algorithm are presented in this work. The experiments show that the solution developed allow palaeogeographic data mining by applying appropriate formulas for calculating distances over the Earth’s surface and, at the same time, treating the temporal dimension according to the geologic time scale. / O uso da mineração de dados e do processo de descoberta de conhecimento em banco de dados (Knowledge Discovery in Databases (KDD)) vem crescendo em sua importância conforme cresce o volume de dados armazenados em grandes repositórios. Uma área promissora para descoberta do conhecimento diz respeito à prospecção de petróleo, onde os dados usados diferem tanto de dados tradicionais como de dados geográficos. Nesses dados, a dimensão temporal é tratada de acordo com a escala de tempo geológico, enquanto a escala espacial é relacionada a dados georeferenciados, ou seja, latitudes e longitudes projetadas na superfície terrestre. Esta abordagem difere da adotada em algoritmos de mineração espaço-temporal presentes na literatura, surgindo assim a necessidade de evolução dos algoritmos existentes a esse contexto de pesquisa. Este trabalho apresenta o desenvolvimento de uma solução para uso do algoritmo de mineração de dados espaço-temporais baseado em densidade ST-DBSCAN para mineração de dados paleogeográficos na superfície terrestre. O algoritmo foi implementado em linguagem de programação Java utilizando a API Weka, onde aperfeiçoamentos foram feitos a fim de permitir o uso de mineração de dados na solução de problemas de pesquisa identificados. Como resultados, são apresentados conjuntos de experimentos que validam as implementações propostas no algoritmo. Os experimentos demonstram que a solução desenvolvida permite a mineração de dados paleogeográficos com a aplicação de fórmulas apropriadas para cálculo de distâncias sobre a superfície terrestre e, ao mesmo tempo, tratando a dimensão temporal de acordo com a escala de tempo geológico.