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.