Um dos principais interesses na descoberta do conhecimento e mineração de dados é a indução de regras de associação. Regras de associação caracterizam as relações entre os dados a partir de um conjunto de dados estruturado com transações, onde cada transação contém um subconjunto de itens. Seja X e Y dois conjuntos de itens disjuntos, então a regra X → Y define um relacionamento, isto é, a dependência ou a co-ocorrência entre os conjuntos X e Y. Um dos algoritmos mais conhecidos para geração de regras de associação é o algoritmo Apriori. Ele explora regras de associação que respeitam o limiar suporte mínimo, ou seja, as regras devem aparecer em uma quantidade mínima de transações. Esse limiar tem a capacidade de controlar a quantidade de regras extraídas durante a mineração. Entretanto, a frequência ou suporte não consegue medir o nível de interesse de uma regra. Para medir a importância ou interesse de uma regra em relação a outras foram desenvolvidas medidas de interesse. Tais medidas são calculadas a partir das frequências dos conjuntos de itens X, Y e do par XY. Apesar das medidas de interesse realizarem uma filtragem das regras desinteressantes, elas não acarretam na diminuição no tempo de execução da mineração. Para vencer essa dificuldade, técnicas que exploram diretamente regras de associação ótimas foram desenvolvidas. Um conjunto de regras de associação ótimas é um conjunto de regras que otimiza uma determinada medida de interesse. Na literatura existem muitos trabalhos que buscam esse tipo de conjunto de regras de forma direta e eficiente. O trabalho corrente segue esta mesma direção e visou a melhoria dessa tarefa por descobrir uma quantidade arbitrária de regras de associação ótimas. As abordagens anteriores apresentam um entrave em especial, que é a utilização do algoritmo Apriori. Tal técnica realiza uma busca em largura sobre os conjuntos de itens. No entanto, as técnicas mais promissoras que descobrem regras ótimas realizam busca em profundidade sobre o espaço de busca de regras. Em virtude dessa característica, neste trabalho foi adotada a técnica FP-growth, que realiza uma busca em profundidade sobre os conjuntos de itens explorados. Além da adoção da técnica FP-growth, foram desenvolvidas novas estratégias de poda e uma nova estratégia de busca na travessia do espaço de regras. Todas essas inovações foram adicionadas aos algoritmos desenvolvidos no corrente trabalho e proporcionaram melhor eficiência (tempo de execução) em relação ao algoritmo baseline em todos os testes. Tais testes foram realizados sobre conjuntos de dados reais e artificiais. / The induction of association rules is one of the main interests in knowledge discovery and data mining. Association rules describe the relationships between data from a transactional dataset, so that each transaction contains a subset of items. Let X and Y be two disjoint itemsets, then any rule X → Y defines a relationship that represents the dependence or co-occurrence between itemsets X and Y. Apriori is the best-known algorithm to generate association rules. It generates association rules that satisfy a user defined minimum support threshold. This means the rules should occur at least in an arbitrary number of transactions from a dataset. This threshold limits the number of association rules generated by Apriori. Yet, it is not possible to measure the interest of a rule through support. For that, interestingness measures were developed to assess the importance or interest of a rule. The values of these interestingness measures are obtained through frequencies of X, Y and XY. However, it is still an expensive task mining all the association rules and then filter them according to an interestingness measure. To overcome this difficulty, techniques to induce optimal association rules have been developed. Optimal association rules are a ruleset that optimize an arbitrary interestingness measure. In the literature, there are many papers which aim at searching for optimal association rules directly and efficiently. The current MSc thesis follows this direction, aiming at improving this objective. Previous approaches share one obstacle in particular: the use of Apriori. This algorithm performs a breadth-first search on the itemsets space. However, the most promising techniques to find optimal rules perform a depth-first search on the space of rules. Hence, in this research we adopted the FP-growth algorithm, which performs a depth-first search on the itemsets space. Besides using this algorithm, new rule pruning techniques and a new search space traversing on the space rules were developed. The algorithms developed in the current research contain all these innovations. In all tests, the proposed algorithms surpassed the baseline algorithms in terms of efficiency. These tests were conducted on real and articial datasets.

Um dos principais interesses na descoberta do conhecimento e mineração de dados é a indução de regras de associação. Regras de associação caracterizam as relações entre os dados a partir de um conjunto de dados estruturado com transações, onde cada transação contém um subconjunto de itens. Seja X e Y dois conjuntos de itens disjuntos, então a regra X → Y define um relacionamento, isto é, a dependência ou a co-ocorrência entre os conjuntos X e Y. Um dos algoritmos mais conhecidos para geração de regras de associação é o algoritmo Apriori. Ele explora regras de associação que respeitam o limiar suporte mínimo, ou seja, as regras devem aparecer em uma quantidade mínima de transações. Esse limiar tem a capacidade de controlar a quantidade de regras extraídas durante a mineração. Entretanto, a frequência ou suporte não consegue medir o nível de interesse de uma regra. Para medir a importância ou interesse de uma regra em relação a outras foram desenvolvidas medidas de interesse. Tais medidas são calculadas a partir das frequências dos conjuntos de itens X, Y e do par XY. Apesar das medidas de interesse realizarem uma filtragem das regras desinteressantes, elas não acarretam na diminuição no tempo de execução da mineração. Para vencer essa dificuldade, técnicas que exploram diretamente regras de associação ótimas foram desenvolvidas. Um conjunto de regras de associação ótimas é um conjunto de regras que otimiza uma determinada medida de interesse. Na literatura existem muitos trabalhos que buscam esse tipo de conjunto de regras de forma direta e eficiente. O trabalho corrente segue esta mesma direção e visou a melhoria dessa tarefa por descobrir uma quantidade arbitrária de regras de associação ótimas. As abordagens anteriores apresentam um entrave em especial, que é a utilização do algoritmo Apriori. Tal técnica realiza uma busca em largura sobre os conjuntos de itens. No entanto, as técnicas mais promissoras que descobrem regras ótimas realizam busca em profundidade sobre o espaço de busca de regras. Em virtude dessa característica, neste trabalho foi adotada a técnica FP-growth, que realiza uma busca em profundidade sobre os conjuntos de itens explorados. Além da adoção da técnica FP-growth, foram desenvolvidas novas estratégias de poda e uma nova estratégia de busca na travessia do espaço de regras. Todas essas inovações foram adicionadas aos algoritmos desenvolvidos no corrente trabalho e proporcionaram melhor eficiência (tempo de execução) em relação ao algoritmo baseline em todos os testes. Tais testes foram realizados sobre conjuntos de dados reais e artificiais. / The induction of association rules is one of the main interests in knowledge discovery and data mining. Association rules describe the relationships between data from a transactional dataset, so that each transaction contains a subset of items. Let X and Y be two disjoint itemsets, then any rule X → Y defines a relationship that represents the dependence or co-occurrence between itemsets X and Y. Apriori is the best-known algorithm to generate association rules. It generates association rules that satisfy a user defined minimum support threshold. This means the rules should occur at least in an arbitrary number of transactions from a dataset. This threshold limits the number of association rules generated by Apriori. Yet, it is not possible to measure the interest of a rule through support. For that, interestingness measures were developed to assess the importance or interest of a rule. The values of these interestingness measures are obtained through frequencies of X, Y and XY. However, it is still an expensive task mining all the association rules and then filter them according to an interestingness measure. To overcome this difficulty, techniques to induce optimal association rules have been developed. Optimal association rules are a ruleset that optimize an arbitrary interestingness measure. In the literature, there are many papers which aim at searching for optimal association rules directly and efficiently. The current MSc thesis follows this direction, aiming at improving this objective. Previous approaches share one obstacle in particular: the use of Apriori. This algorithm performs a breadth-first search on the itemsets space. However, the most promising techniques to find optimal rules perform a depth-first search on the space of rules. Hence, in this research we adopted the FP-growth algorithm, which performs a depth-first search on the itemsets space. Besides using this algorithm, new rule pruning techniques and a new search space traversing on the space rules were developed. The algorithms developed in the current research contain all these innovations. In all tests, the proposed algorithms surpassed the baseline algorithms in terms of efficiency. These tests were conducted on real and articial datasets.

A descoberta de Regras de Associação é uma tarefa de mineração de dados que procura identificar padrões em datasets, permitindo, após a sua interpretação, identificar conhecimento específico acerca do problema em análise. A Mineração de Regras de Associação pode ser usada como uma metodologia para descobrir hipóteses ou teorias candidatas em um domínio do conhecimento. No entanto, o processo de Mineração de Regras de Associação gera um grande número de regras superando a capacidade de exploração do usuário. Esse fato pode tornar o processo de análise inviável, além de afetar negativamente o resultado de alguns algoritmos de extração de conhecimento. Diante disso, várias abordagens foram propostas para guiar o usuário na exploração das Regras de Associação descobertas, em especial com a utilização de estruturas de Rede, que permitem analisar as relações existentes entre as regras. Neste contexto, esse trabalho foi motivado pelo potencial uso de Redes na otimização da identificação do conhecimento, em processos de Mineração de Regras de Associação, formulando abordagens explicáveis. Outra motivação surge da lacuna referente ao uso de Redes em tarefas multialvo inerente de várias aplicações do mundo real. O desenvolvimento deste trabalho teve o intento de avançar as pesquisas da área de Mineração de Regras de Associação com o uso de Redes em relação a métodos de geração de hipóteses validáveis com um ou dois itens objetivo, tanto em relação à interpretabilidade como na expressividade das representações construídas. Um Mapeamento Sistemático da literatura da área foi realizado com a finalidade de conhecer o estado da arte sobre como o uso das Redes pode auxiliar nos processos de Mineração de Regras de Associação. Neste trabalho é proposto e desenvolvido um método de seleção e avaliação das medidas de suporte e confiança mínimos referentes a extração de Regras de Associação com o uso de Medidas de Centralidade de Redes, cuja contribuição principal foi a elaboração de um critério objetivo para extração de Regras de Associação. Foram também propostas, desenvolvidas e validadas duas novas Redes, as Redes de Regras de Associação Filtradas (Filtered-ARNs) e as Redes de Regras de Associação Multialvo (MTARNs) que promoveram um impacto positivo na identificação do conhecimento por meio da comprovação matemática da influência entre os elementos de uma Regra de Associação e ampliaram a capacidade de extração do conhecimento em estudos de aplicações multialvo. / The discovery of Association Rules is a data mining task that seeks to identify patterns in datasets, allowing, after its interpretation, to determine specific knowledge about the problem under analysis. Association Rules Mining can be used as a methodology for discovering hypotheses or candidate theories in a knowledge domain. However, the Association Rules Mining process generates a large number of rules that exceed the users ability to exploit. This fact may make the analysis process impracticable, as well as negatively affect the outcome of some knowledge extraction algorithms. Therefore, several approaches were proposed to guide the user in the exploration of the discovered Association Rules, especially with the use of Network structures, which allow to analyze the relations between the rules. In this context, this work was motivated by the potential use of Networks in the optimization of knowledge identification, in Association Rules Mining processes, formulating explanable approaches. Another motivation arises from the gap regarding the use of Networks in multi-target tasks inherent to several real-world applications. The development of this work was intended to advance the research of the Association Rules Mining with the use of Networks with methods of generating validate hypotheses with one or two target items, both about the interpretability and in the expressiveness of representations built. A Systematic Mapping of the literature of the area was carried out with the purpose of knowing the state of the art on how the use of the Networks can help in the Mining processes of Association Rules. In this work, a method of selection and evaluation of the minimum support and trust measures regarding the extraction of Association Rules with the use of Network Centralization Measures was proposed and developed, whose main contribution was the elaboration of an objective criterion for extraction of Association Rules. Two new networks were also introduced, developed and validated, the Filtered Association Rules Networks (Filtered-ARNs) and the Multi-Target Association Rules Networks (MTARNs) that promoted a positive impact on the identification of knowledge through mathematical proof of the influence between the elements of an Association Rule and extended the capacity of knowledge extraction in studies of multi-target applications.

A alta disponibilidade de informações em saúde por meio de sistemas de informação só pode ser proporcionada com a utilização de sistemas que sejam capazes de trocar dados de forma segura e consistente. Para isso, estes sistemas necessitam ser interoperáveis, capazes de trocar informações. Uma das características mais importantes de tais sistemas é a utilização de terminologias em saúde, permitindo a codificação dos termos clínicos de maneira robusta e consistente. Algumas das terminologias mais conhecidas e utilizadas são: SNOMED-CT, ICD-CM, ICD, LOINC, NANDA, TUSS, CBHPM, Tabela de Procedimentos SUS, entre outras. Quando os sistemas não se utilizam de uma mesma terminologia para codificação de um mesmo conceito é necessário a realização de mapeamentos e traduções entre as terminologias. O mapeamento entre terminologias consiste em estabelecer as associações pertinentes às terminologias para que cada termo pertencente a uma possa ser associado a algum termo da outra. Este mapeamento, geralmente, é criado por especialistas de domínio, que atuam analisando as duas terminologias em questão e estabelecendo manualmente estas associações. Neste trabalho, propomos uma metodologia que visa facilitar a realização deste tipo de mapeamento, por meio da utilização de dois recursos: Regras de Associação, para extração das associações preexistentes entre as terminologias em registros clínicos; e Busca Textual, para pareamento entre conceitos das duas terminologias baseado na identificação de termos comuns. O auxílio à criação destes mapeamentos é proporcionado por meio de sugestões de relações existentes entre as terminologias. Como resultado deste trabalho obtivemos uma metodologia genérica de mapeamento entre terminologias capaz de auxiliar com sucesso os especialistas. Em aproximadamente 40% dos casos os especialistas concordaram com uma das sugestões apresentadas. De forma complementar, obtivemos o mapeamento parcial entre duas terminologias: a ICD9-CM e a TUSS, utilizadas como caso de uso para validação da metodologia. / The high availability of health information through information systems can be provided only with the use of systems that are able to exchange data securely and consistently. To this end, these systems need to be interoperable, capable of exchanging information that is understood both at one end as the other. One of the most important characteristics of such systems is the use of terminologies in health, allowing the coding of clinical terms in a robust and consistent manner. Some of the most known and used terminologies are: SNOMED-CT, ICD-CM, ICD, LOINC, NANDA, TUSS, CBHPM, and SUS Procedures Table, among others. When systems do not use the same terminology for encoding the same concept, it is necessary to perform mappings and translations between the terminologies. The mapping between terminologies consists on establishing the relevant associations present in terminologies, so that each term belonging to one can be associated unambiguously to the terms belonging to another. This mapping is typically created by domain experts who work analyzing the two terms in question and manually setting these associations. In this paper, we propose a methodology that aims to facilitate this type of mapping, through the use of two frameworks: Association Rules, for the extraction of preexisting associations between the terminologies in clinical records; and Textual Search, for pairing between the two terminologies concepts based on the identification of common terms. The creation of these mappings by experts is aided by the method suggesting links between the terminologies through the Association Rules or Textual Search. As a result of this work we obtained a generic methodology for mapping between terminologies able to successfully assist the experts. In approximately 40% of cases the experts agreed with the suggestions. As a complement, we obtained a partial mapping between two specific terminologies for coding surgical procedures: the ICD9-CM and TUSS, used as use case to validate the methodology.

Sistemas de informações geográficas permitem armazenar, manipular e armazenar, manipular e analisar dados espaciais e aspectos descritivos desses dados. A análise de dados espaciais pode ser realizada por meio de técnicas de extração de regras de associação, ou seja, regras que descrevem relacionamentos entre os dados. Porém, a mineração de regras de associação não considera as relações topológicas existentes entre dados georreferenciados. Para solucionar esse problema, Koperski and Han (1995) e Malerba et al. (2001) propuseram um processo de extração de regras integrado ao algoritmo de mineração e utilizavam predicados lógicos para representar as regras. Como alternativa a essa solução, este trabalho propõe pré-processar os dados referenciados para encontrar relações topológicas em separado e aplicar um algoritmo de mineração de regras de associação disponí?vel pela comunidade acadêmica. As regras geradas devem apresentar características descritivas dos dados e relações topológicas. Para atingir esse objetivo foi especificado um processo de extração de regras em dados georreferenciados e implementado um módulo de pré-processamento que extrai relações topológicas. O módulo foi avaliado por meio de um estudo de caso utilizando o sistema de informação geográfica da cidade de Jaboticabal, no contexto de planejamento urbano. As regras encontradas foram analisadas por um especialista utilizando as medidas de suporte e confiança. Além disso, uma análise sobre o tempo de processamento e consumo de memória para encontrar as relações topológicas foi realizada, mostrando que é possível extrair padrões utilizando o processo e o módulo proposto neste trabalho. / Geographic information systems are used to store, manipulate, and analyze spatial data and its descriptive aspects. Spatial data analysis can be done by searching association rules that describe relationships between the data. However, georeferenced data present topological relations unknown to traditional mining association rule algorithms. To solve this problem, Koperski and Han (1995) and Malerba et al. (2001) proposed a topological relation extraction process integrated to a mining association rule algorithm. This process requires all data to be translated as logical predicates. As an alternative to this solution, this work proposes to break down this process by pre-processing the georeferenced data to find topological relations, then executing traditional mining association rule algorithms. The resulting rules must present descriptive characteristics of the data and topological relations. To reach this objective, a process of rule extraction in georeferenced data was specified, in addition to a pre-processing module implementation. This module was evaluated by using a case study that uses a geographic information system of the city of Jaboticabal, in the context of urban planning. The generated rules were analyzed by a specialist using the measures of support and confidence. In addition, an analysis regarding the processing time and memory consumption was provided to find the topological relations, which shows that it is possible to extract the patterns with the proposed process and module.

Dentre as técnicas de mineração existentes encontra-se a associação, responsável por identificar relações que ocorrem no conjunto de dados. Embora a associação seja uma das técnicas mais utilizadas, a quantidade de padrões extraídos pode vir a sobrecarregar o usuário de tal maneira que encontrar algo interessante dentre a imensidão de padrões obtidos passa a ser um novo desafio. Para solucionar esse problema, uma grande parte dos trabalhos relacionados à associação está voltada a etapa de pós-processamento. Esses trabalhos geralmente propõem abordagens de pós-processamento que visam, segundo determinada estratégia, facilitar a busca pelos padrões interessantes ao domínio. Nos últimos anos, essas abordagens têm incluído no processo o conhecimento e/ou interesse do usuário sobre o domínio. Contudo, nas abordagens atualmente existentes, o usuário deve, por meio de algum formalismo descrever explicitamente seu conhecimento e/ou interesse, requerendo do usuário um tempo considerável, podendo levar, inclusive, a especificações incompletas e/ou incorretas. Além disso, na maioria das vezes, o usuário não tem ideia do que é provavelmente interessante, nem a partir de quais relações iniciar a busca. Nota-se, portanto, que um dos desafios dessas abordagens é considerar o conhecimento e/ou interesse do usuário. Além disso, é necessário considerar também o número de regras que o usuário analisará. A análise de regras feita por um especialista é custosa e, na maioria dos casos, o usuário quer explorar as regras geradas sem limitar a exploração ao conhecimento que ele já possui. Portanto, é importante que o usuário avalie o menor número de regras possível e, com base nessa avaliação, abordagens de pós-processamento consigam o auxiliar na busca pelas regras que ele poderá considerar interessante. Para tanto, é proposto neste trabalho que o pós-processamento seja tratado como um problema de classificação semissupervisionada transdutiva, uma vez que permite que o usuário rotule, considerando classes pré-definidas (por exemplo, \"Interessante\" ou \"Não Interessante\"), apenas algumas regras do conjunto a ser explorado para que todas as outras regras sejam automaticamente rotuladas. Além disso, por meio da definição dos rótulos de algumas regras, é possível capturar implicitamente o conhecimento e/ou interesse do usuário sobre o domínio. Para tanto, é necessário que as regras sejam modeladas de maneira a permitir: (a) selecionar as regras a serem rotuladas pelo usuário a fim de capturar implicitamente seu conhecimento e/ou interesse; (b) propagar os rótulos das regras já classificadas pelo usuário a todas as outras regras não rotuladas. Desse modo, neste trabalho, as regras foram modeladas via redes, uma vez que: (i) uma vasta quantidade de medidas de exploração de redes pode ser utilizada, em conjunto com as informações fornecidas pelo usuário, a fim de viabilizar o item (a); (ii) algoritmos de propagação de rótulos podem ser utilizados a fim de viabilizar o item (b). Diante do apresentado, ressalta-se que as contribuições deste trabalho estão na capacidade de se extrair o conhecimento e/ou interesse do usuário de acordo com as características da base de dados e direcionar sua exploração sem a necessidade de se definir previamente o que será explorado. Além disso, os resultados obtidos demonstram a capacidade da PARLP em direcionar o usuário para o conhecimento considerado interessante, reduzindo, para tanto, a quantidade de regras a serem exploradas. Por fim, este trabalho contribui também para demonstrar que é possível tratar o pós-processamento de regras de associação como um problema de propagação de rótulos. / One of the existing data mining techniques is association rules, responsible for identifying relationships that occur in the data set. Although the association rule is one of the most widely used techniques, the amount of extracted patterns can overload the user in such a way that finding interesting patterns among the large amount of obtained patterns becomes a challenge. To solve this problem, a large part of the association-related work is focused on the post-processing step. These works generally propose a post-processing approaches that, according to a certain strategy, aims facilitating the search for interesting patterns. Nowadays, approaches have included the user knowledge in the domain and / or interests on the process. However, in the current existing approaches, the user knowledge and/or interest must be explicitly described by some formalism, requiring a considerable time and may even lead to incomplete and / or incorrect specifications. In addition, the user has no idea what probably is interesting or which patterns to begin the searching. Notice that one of the challenges of these approaches is to consider the knowledge and / or user interest. In addition, consider the number of rules the user will examine is necessary. The analysis of the rules by an expert is expensive and, in most cases, the user wants to explore the rules generated without limiting exploration to the knowledge he already has. Therefore, the user evaluate the fewest amount of rules possible is important and, based on this assessment, the post-processing approaches be able to assist in the search for the rules that he may consider interesting. So, in this work is proposed that the post-processing is treated as a transductive semi supervised classification problem, since it allows the user to label some rules based on two predefined classes (e.g. \"interesting\"or \"not interesting\"), in a way that just a small amount of the rule set needs to be explored and all other association rules are automatically labeled. Furthermore, you can implicitly capture the knowledge and / or user interest in the domain by labeling some rules. Thus, the rules need to be modeled to allow: (a) select the rules to be labeled by the user to implicitly capture their knowledge and / or interest; (b) propagate the rules\' labels classified by the user to all not labeled rules. To do so, the rules were modeled via networks in this work, due to: (i) a large amount of network measures can be used in conjunction with the information provided by the user, to make item (a) possible; (ii) label propagation algorithms can be used in order to make item (b) possible. Therefore, we highlight that the contributions of this work are the ability to extract knowledge and / or user interest according to database characteristics and direct the user exploration without previously defining what will be explored. In addition, the results demonstrate that the proposed approach is able to direct the user to the knowledge considered interesting, reducing the amount of rules to be explored. Finally, this work also contributes to demonstrate that treat the post-processing of association rules as a problem of propagation of labels is possible.

Neste estudo, foi proposta a exploração de um banco de dados, com informações de exames de eletrocardiogramas (ECG), utilizado pelo sistema denominado Tele-ECG do Instituto Dante Pazzanese de Cardiologia, aplicando a técnica de data mining (mineração de dados) para encontrar padrões que colaborem, no futuro, para a aquisição de conhecimento na análise de eletrocardiograma. A metodologia proposta permite que, com a utilização de data mining, investiguem-se dados à procura de padrões sem a utilização do traçado do ECG. Três pacotes de software (Weka, Orange e R-Project) do tipo open source foram utilizados, contendo, cada um deles, um conjunto de implementações algorítmicas e de diversas técnicas de data mining, além de serem softwares de domínio público. Regras conhecidas foram encontradas (confirmadas pelo especialista médico em análise de eletrocardiograma), evidenciando a validade dessa metodologia. / In this study, the exploration of electrocardiograms (ECG) databases, obtained from a Tele-ECG System of Dante Pazzanese Institute of Cardiology, has been proposed, applying the technique of data mining to find patterns that could collaborate, in the future, for the acquisition of knowledge in the analysis of electrocardiograms. The proposed method was to investigate the data looking for patterns without the use of the ECG traces. Three Data-mining open source software packages (Weka, Orange and R - Project) were used, containing, each one, a set of algorithmic implementations and various data mining techniques, as well as being a public domain software. Known rules were found (confirmed by medical experts in electrocardiogram analysis), showing the validity of the methodology.

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.

Mineração de Dados é um processo de natureza iterativa e interativa responsável por identificar padrões em grandes conjuntos de dados, objetivando extrair conhecimento válido, útil e inovador a partir desses. Em Mineração de Dados, Regras de Associação é uma técnica que consiste na identificação de padrões intrínsecos ao conjunto de dados. Essa técnica tem despertado grande interesse nos pesquisadores de Mineração de Dados e nas organizações, entretanto, a mesma possui o inconveniente de gerar grande volume de conhecimento no formato de regras, dificultando a análise e interpretação dos resultados pelo usuário. Nesse contexto, este trabalho tem como objetivo principal generalizar e eliminar Regras de Associação não interessantes e/ou redundantes, facilitando, dessa maneira, a análise das regras obtidas com relação à compreensibilidade e tamanho do conjunto de regras. A generalização das Regras de Associação é realizada com o uso de taxonomias. Entre os principais resultados deste trabalho destacam-se a proposta e a implementação do algoritmo GART e do módulo computacional RulEE-GAR. O algoritmo GART (Generalization of Association Rules using Taxonomies - Generalização de Regras de Associação usando Taxonomias) utiliza taxonomias para generalizar Regras de Associação. Já o módulo RulEE-GAR, além de facilitar o uso do algoritmo GART durante a identificação de taxonomias e generalização de regras, provê funcionalidades para analisar as Regras de Associação generalizadas. Os experimentos realizados, neste trabalho, mostraram que o uso de taxonomias na generalização de Regras de Associação pode reduzir o volume de um conjunto de regras. / Data Mining refers to the process of finding patterns in large data sets. The Association Rules in Data Mining try to identify intrinsic behaviors of the data set. This has motivated researchers of Data Mining and organizations. However, the Association Rules have the inconvenient of generating a great amount of knowledge in the form of rules. This makes the analysis and interpretation of the results difficult for the user. Taking this into account, the main objective of this research is the generalization and elimination of non-interesting and/or redundant Association Rules. This facilite the analysis of the rules with respect to the compreensibility and the size of the rule set. The generalization is realized using taxonomies. The main results of this research are the proposal and the implementation of the algorithm GART and of the computational module RulEE-GAR. The algorithm GART (Generalization of Association Rules using Taxonomies) uses taxonomies to generalize Association Rules. The module RulEE-GAR facilitates the use of the algorithm GART in the identification of taxonomies and generalization of rules and provide functionalities to the analysis of the generalized Association Rules. The results of experiments showed that the employment of taxonomies in the generalization of Association Rules can reduce the size of a rule set.

Uma representação estruturada dos documentos em um formato apropriado para a obtenção automática de conhecimento, sem que haja perda de informações relevantes em relação ao formato originalmente não-estruturado, é um dos passos mais importantes da mineração de textos, pois a qualidade dos resultados obtidos com as abordagens automáticas para obtenção de conhecimento de textos estão fortemente relacionados à qualidade dos atributos utilizados para representar a coleção de documentos. O Modelo de Espaço de Vetores (MEV) é um modelo tradicional para obter uma representação estruturada dos documentos. Neste modelo, cada documento é representado por um vetor de pesos correspondentes aos atributos do texto. O modelo bag-of-words é a abordagem de MEV mais utilizada devido a sua simplicidade e aplicabilidade. Entretanto, o modelo bag-of-words não trata a dependência entre termos e possui alta dimensionalidade. Diversos modelos para representação dos documentos foram propostos na literatura visando capturar a informação de relação entre termos, destacando-se os modelos baseados em frases ou termos compostos, o Modelo de Espaço de Vetores Generalizado (MEVG) e suas extensões, modelos de tópicos não-probabilísticos, como o Latent Semantic Analysis (LSA) ou o Non-negative Matrix Factorization (NMF), e modelos de tópicos probabilísticos, como o Latent Dirichlet Allocation (LDA) e suas extensões. A representação baseada em modelos de tópicos é uma das abordagens mais interessantes uma vez que elas fornece uma estrutura que descreve a coleção de documentos em uma forma que revela sua estrutura interna e as suas inter-relações. As abordagens de extração de tópicos também fornecem uma estratégia de redução da dimensionalidade visando a construção de novas dimensões que representam os principais tópicos ou assuntos identificados na coleção de documentos. Entretanto, a extração é eficiente de informações sobre as relações entre os termos para construção da representação de documentos ainda é um grande desafio de pesquisa. Os modelos para representação de documentos que exploram a correlação entre termos normalmente enfrentam um grande desafio para manter um bom equilíbrio entre (i) a quantidade de dimensões obtidas, (ii) o esforço computacional e (iii) a interpretabilidade das novas dimensões obtidas. Assim,é proposto neste trabalho o modelo para representação de documentos Latent Association Rule Cluster based Model (LARCM). Este é um modelo de extração de tópicos não-probabilístico que explora o agrupamento de regras de associação para construir uma representação da coleção de documentos com dimensionalidade reduzida tal que as novas dimensões são extraídas a partir das informações sobre as relações entre os termos. No modelo proposto, as regras de associação são extraídas para cada documento para obter termos correlacionados que formam expressões multi-palavras. Essas relações entre os termos formam o contexto local da relação entre termos. Em seguida, aplica-se um processo de agrupamento em todas as regras de associação para formar o contexto geral das relações entre os termos, e cada grupo de regras de associação obtido formará um tópico, ou seja, uma dimensão da representação. Também é proposto neste trabalho uma metodologia de avaliação que permite selecionar modelos que maximizam tanto os resultados na tarefa de classificação de textos quanto os resultados de interpretabilidade dos tópicos obtidos. O modelo LARCM foi comparado com o modelo LDA tradicional e o modelo LDA utilizando uma representação que inclui termos compostos (bag-of-related-words). Os resultados dos experimentos indicam que o modelo LARCM produz uma representação para os documentos que contribui significativamente para a melhora dos resultados na tarefa de classificação de textos, mantendo também uma boa interpretabilidade dos tópicos obtidos. O modelo LARCM também apresentou ótimo desempenho quando utilizado para extração de informação de contexto para aplicação em sistemas de recomendação sensíveis ao contexto. / A structured representation of documents in an appropriate format for the automatic knowledge extraction without loss of relevant information is one of the most important steps of text mining, since the quality of the results obtained with automatic approaches for the text knowledge extraction is strongly related to the quality of the selected attributes to represent the collection of documents. The Vector Space model (VSM) is a traditional structured representation of documents. In this model, each document is represented as a vector of weights that corresponds to the features of the document. The bag-of-words model is the most popular VSM approach because of its simplicity and general applicability. However, the bag-of-words model does not include dependencies of the terms and has a high dimensionality. Several models for document representation have been proposed in the literature in order to capture the dependence among the terms, especially models based on phrases or compound terms, the Generalized Vector Space Model (GVSM) and their extensions, non-probabilistic topic models as Latent Semantic Analysis (LSA) or Non-negative Matrix Factorization (NMF) and still probabilistic topic models as the Latent Dirichlet Allocation (LDA) and their extensions. The topic model representation is one of the most interesting approaches since it provides a structure that describes the collection of documents in a way that reveals their internal structure and their interrelationships. Also, this approach provides a dimensionality reduction strategy aiming to built new dimensions that represent the main topics or ideas of the document collection. However, the efficient extraction of information about the relations of terms for document representation is still a major research challenge nowadays. The document representation models that explore correlated terms usually face a great challenge of keeping a good balance among the (i) number of extracted features, (ii) the computational performance and (iii) the interpretability of new features. In this way, we proposed the Latent Association Rule Cluster based Model (LARCM). The LARCM is a non-probabilistic topic model that explores association rule clustering to build a document representation with low dimensionality in a way that each dimension is composed by information about the relations among the terms. In the proposed approach, the association rules are built for each document to extract the correlated terms that will compose the multi-word expressions. These relations among the terms are the local context of relations. Then, a clustering process is applied for all association rules to discover the general context of the relations, and each obtained cluster is an extracted topic or a dimension of the new document representation. This work also proposes in this work an evaluation methodology to select topic models that maximize the results in the text classification task as much as the interpretability of the obtained topics. The LARCM model was compared against both the traditional LDA model and the LDA model using a document representation that includes multi-word expressions (bag-of-related-words). The experimental results indicate that LARCM provides an document representation that improves the results in the text classification task and even retains a good interpretability of the extract topics. The LARCM model also achieved great results as a method to extract contextual information for context-aware recommender systems.