Um dos desafios mais interessantes que a Engenharia Informática enfrenta hoje em dia pode ser encarado como a resolução de uma questão básica: como extrair conhecimento de dados armazenados? O Data Mining tenta responder a esta questão pois é seu grande objectivo a extracção de conhecimento previamente desconhecido e potencialmente útil na forma de padrões. Esta área tem recebido recentemente grande atenção por parte da comunidade industrial e de investigação. Quando a quantidade de conhecimento gerado é grande, o que acontece tipicamente quando se utiliza técnicas de descoberta de Regras de Associação, a selecção de padrões interessantes torna-se um problema sério para o utilizador humano: este é o problema de Pós-Processamento de Regras Associação. Assim, um dos problemas centrais em Data Mining consiste no desenvolvimento de boas medidas de interesse dos padrões descobertos.

Esta dissertação centra-se nesta problemática, concentrando-se na criação de uma metodologia que seja adequada para o Pós-Processamento de Regras de Associação. O âmbito desta dissertação está na recolha de conhecimento para o sector dos Vinhos e de Bebidas Espirituosas. Como forma de proporcionar o imprescindível enquadramento real inerente a esta matéria, a investigação foi feita com base nos problemas enfrentados por uma organização no tecido empresarial português.

A completude dos algoritmos de descoberta de regras de associação tem como consequência a geração de um elevado número de regras. Para além da utilização de medidas de interesse para a identificação de regras potencialmente úteis, podemos recorrer a ambientes de exploração de conjuntos de regras. Nesta apresentação, para além de uma introdução geral a esta problemática descreve-se o ambiente PEAR (post processing environment for association rules), assim como possíveis extensões.

Different clustering algorithms will, in general, produce different data partitions when applied to the same data set. On this talk I address the problem of robust clustering as a problem of combining data partitions (forming a clustering ensemble) produced by multiple clusterings. I propose and analyze a voting mechanism on pair wise associations for combiningdata partitions, based on the concept of evidence accumulation. The evidence accumulation method is applied to the combination of "weak" clusterers, using the K-means to produce clustering ensembles. Experimental results show the ability of the technique to identify arbitrarily shaped and sized clusters. Formulated under an information-theoretical framework, and taking consistency and robustness as key features, I then define objective functions and optimality criteria to evaluate a clustering combination technique; mutual information is the underlying concept, used in the definition of quantitative measures of agreement between data partitions; robustness is assessed by variance analysis based on bootstrapping. It is shown that the evidence accumulation technique attempts to optimize the given criteria, although optimality is not ensured in all situations.

This work presents an hybrid adaptive system for induction of forest of trees from data streams.
Our system has been designed for continuous data. It uses analytical techniques to choose the splitting criteria, and the information gain to estimate the merit of each possible splitting-test. The number of examples required to evaluate the splitting criteria is based on the Hoeffding bound. For multi-class problems, the algorithm builds a binary tree for each possible pair of classes leading to a forest of trees. We study the behavior of the system in different problems and demonstrate its utility in large and medium data sets.

We present a parallel algorithm for the efficient extraction of binding-site consensus from genomic sequences. This algorithm is based on an existing approach for extracting structured motifs. A structured motif consists of an ordered collection of p boxes, p substitution rates and p-1 distances between successive boxes. The contents of the boxes, which represent the extracted motifs, are unknown at the start of the process and are found by the algorithm using a suffix tree as the fundamental data structure.

By partitioning the structured motif searching space we divide the most demanding part of the algorithm by a number of processors that can be loosely coupled. In this way we obtain, under conditions that are easily met, a speedup that is linear on the number of available processing units. This speedup is verified by both theoretical and experimental analysis.

Predicting protein structure is a fundamental problem in biology, especially in the genomic era where over one third of newly discovered genes have unknown structure and function. Because sequence and structure data (hence training sets) continue to grow exponentially, this area is ideally suited for machine learning approaches. Neural networks, in particular, have had remarkable success and have led, for instance, to the construction of the best secondary structure predictors. We will provide an overview of our own work and the state-of-the-art for several structure prediction problem including: (1) prediction of protein secondary structures; (2) prediction of relative solvent accessibility; (3) prediction of contacts; (4) prediction of three-dimensional protein structures; (5) prediction of interchain beta-sheet quaternary structures; using machine learning methods. The methods we have developed are based on the theory of graphical models but use deterministic recursive neural networks to speed up learning. We will discuss their applicability to other problems and the lessons learnt for the design of complex neural network architectures.

Multiple sequence alignment is a central and challenging problem in Bioinformatics. Several approaches to it have been tried, some very specialised (heuristic search based on progressive alignment) and some using generic techniques (genetic algorithms, dynamic programming, branch-and-cut). I describe a prototype SAT-based approach that sometimes finds better alignments than standard alignment packages. It is much slower but will be improved in future work.

Clustering is the process of grouping a set of physical or abstract objects into classes of similar objects called clusters. According to this definition a cluster is a collection of objects similar to one another within the same cluster and dissimilar to the objects in other clusters. In gene expression data analysis, and by using a microarray gene expression matrix, clustering can be used to group genes according to their expression under multiple conditions, group conditions based on the expression of a number of genes, or even to group genes and conditions simultaneously. On the first part of the talk, I will briefly talk about partitional and hierarchical clustering algorithms (“classical clustering”), that partition data objects into several non-overlapping groups (each object belongs to only one cluster). I will then talk about fuzzy clustering algorithms, which are strongly based on the theory of fuzzy sets, and partition data objects into possibly overlapping groups, allowing one object to belong to several clusters with a different membership degree. Finally, I will talk about biclustering, which in the case of microarray data analysis, stands for simultaneous clustering of both genes and conditions.

Microarray experiments analyse biological systems under controlled conditions and try to infer biologically meaningful information from the differences observed between gene expression profiles. Actually, one gets spot fluorescence profiles, related but not exactly the mRNA concentration in the samples studied. This talk will focus on the relation between the spot fluorescence values and the desired mRNA concentration, the factors that affect this relation and how to deal with them during the data analysis step. Data normalization and transformation procedures will be discussed.

Os resultados obtidos em biologia molecular, tal como em outras áreas de estudo, têm sido na sua maior parte publicados na literatura científica sobre a área. A literatura é um conjunto enorme de informação não estruturada, o que torna penoso o acesso aos resultados nela documentados. Para lidar com este problema, foram criadas ao longo dos últimos anos bases de dados que organizam de forma sistematizada esses resultados. Contudo, o crescimento destas bases de dados nas últimas décadas tem sido exponencial, tornando a sua actualização um processo impossível quando feito manualmente, e sujeito a muitos erros quando automaticamente. Os maiores problemas na extracção automática de informação da literatura são a nomenclatura e as diferentes classificações dadas às entidades biológicas (e.g. genes, proteínas). Desta forma, muitos dos resultados obtidos em biologia molecular continuam ainda só descritos na literatura.

A apresentação será constituída pelos seguintes tópicos:
1. Breve introdução à problemática da Extracção de Informação e “Text Mining”.
2. Descrição da nossa participação na KDD-Cup 2002, competição internacional de Extracção de Informação da Literatura Biológica. Comparação de resultados e conclusões obtidas.
3. Apresentação do projecto ReBIL (“Relating Biological Information through Literature”), onde desenvolvemos técnicas de extracção automática de informação da literatura assumindo o dogma da biologia molecular, que afirma que a função de uma entidade biológica está relacionada com a sua estrutura.