Cluster ensembles are collections of individual solutions to a given clustering problem which are useful or necessary to consider in a wide range of applications. The R package clue provides an extensible computational environment for creating and analyzing cluster ensembles, with basic data structures for representing partitions and hierarchies, and facilities for computing on these, including methods for measuring proximity and obtaining consensus and "secondary" clusterings. (author's abstract)

O sucesso dos Sistemas de Gerenciamento de Banco de Dados (SGBDs) em aplicações envolvendo dados tradicionais (números e textos curtos) encorajou o seu uso em novos tipos de aplicações, que exigem a manipulação de dados complexos. Séries temporais, dados científicos, dados multimídia e outros são exemplos de Dados Complexos. Inúmeras áreas de aplicação têm demandado soluções para o gerenciamento de dados complexos, dentre as quais a área de informática médica. Dados complexos podem também ser estudos com técnicas de descoberta de conhecimentos, conhecidas como KDD (Knowledge Discovery in Database), usando alguns algoritmos de detecção de agrupamentos apropriados. Entretanto, estes algoritmos possuem custo computacional elevado, o que dificulta a sua utilização em grandes conjuntos de dados. As técnicas já desenvolvidas na Área de Bases de Dados para indexação de espaços métricos usualmente consideram o conjunto de maneira uniforme sem levar em conta a existência de agrupamentos nos dados, por isso as estruturas buscam maximizar a eficiência das consultas para todo o conjunto simultaneamente. No entanto muitas vezes as consultas por similaridade estão limitadas a uma região específica do conjunto de dados. Neste contexto, esta dissertação propõe a criação de um novo método de acesso, que seja capaz de indexar de forma eficiente dados métricos, principalmente para conjuntos que contenham agrupamentos. Para atingir esse objetivo este trabalho também propõe um novo algoritmo para detecção de agrupamentos em dados métricos tornando mais eficiente a escolha do medoide de determinado conjunto de elementos. Os resultados dos experimentos mostram que os algoritmo propostos FAMES e M-FAMES podem ser utilizados para a detecção de agrupamentos em dados complexos e superam os algoritmos PAM, CLARA e CLARANS em eficácia e eficiência. Além disso, as consultas por similaridade realizadas com o método de acesso métrico proposto FAMESMAM mostraram ser especialmente apropriados para conjuntos de dados com agrupamentos / The success of Database Management System (DBMS) for applications with traditional data (numbers and short texts) has encouraged its use in new types of applications that require manipulation of complex data. Time series, scientific data and other multimedia data are examples of complex data. Several application fields, like medical informatics, have demanded solutions for managing complex data. Complex data can also be studied by means of Knowledge Discovery Techniques (KDD) applying appropriate clustering algorithms. However, these algorithms have high computational cost hindering their use in large data sets. The techniques already developed in the Databases research field for indexing metric spaces usually consider the sets have a uniform distribution, without taking into account the existence of clusters in the data, therefore the structures need to generalize the efficiency of queries for the entire set simultaneously. However the similarity searching is often limited to a specific region of the data set. In this context, this dissertation proposes a new access method able to index metric data efficiently, especially for sets containing clusters. It also proposes a new algorithm for clustering metric data so that selection of a medoid from a particular subset of elements becomes more efficient. The experimental results showed that the proposed algorithms FAMES and M-FAMES can be used as a clustering technique for complex data that outperform PAM, CLARA and CLARANS in effectiveness and efficiency. Moreover, the similarity searching performed with the proposed metric access method FAMESMAM proved to be especially appropriate to data sets with clusters

O sucesso dos Sistemas de Gerenciamento de Banco de Dados (SGBDs) em aplicações envolvendo dados tradicionais (números e textos curtos) encorajou o seu uso em novos tipos de aplicações, que exigem a manipulação de dados complexos. Séries temporais, dados científicos, dados multimídia e outros são exemplos de Dados Complexos. Inúmeras áreas de aplicação têm demandado soluções para o gerenciamento de dados complexos, dentre as quais a área de informática médica. Dados complexos podem também ser estudos com técnicas de descoberta de conhecimentos, conhecidas como KDD (Knowledge Discovery in Database), usando alguns algoritmos de detecção de agrupamentos apropriados. Entretanto, estes algoritmos possuem custo computacional elevado, o que dificulta a sua utilização em grandes conjuntos de dados. As técnicas já desenvolvidas na Área de Bases de Dados para indexação de espaços métricos usualmente consideram o conjunto de maneira uniforme sem levar em conta a existência de agrupamentos nos dados, por isso as estruturas buscam maximizar a eficiência das consultas para todo o conjunto simultaneamente. No entanto muitas vezes as consultas por similaridade estão limitadas a uma região específica do conjunto de dados. Neste contexto, esta dissertação propõe a criação de um novo método de acesso, que seja capaz de indexar de forma eficiente dados métricos, principalmente para conjuntos que contenham agrupamentos. Para atingir esse objetivo este trabalho também propõe um novo algoritmo para detecção de agrupamentos em dados métricos tornando mais eficiente a escolha do medoide de determinado conjunto de elementos. Os resultados dos experimentos mostram que os algoritmo propostos FAMES e M-FAMES podem ser utilizados para a detecção de agrupamentos em dados complexos e superam os algoritmos PAM, CLARA e CLARANS em eficácia e eficiência. Além disso, as consultas por similaridade realizadas com o método de acesso métrico proposto FAMESMAM mostraram ser especialmente apropriados para conjuntos de dados com agrupamentos / The success of Database Management System (DBMS) for applications with traditional data (numbers and short texts) has encouraged its use in new types of applications that require manipulation of complex data. Time series, scientific data and other multimedia data are examples of complex data. Several application fields, like medical informatics, have demanded solutions for managing complex data. Complex data can also be studied by means of Knowledge Discovery Techniques (KDD) applying appropriate clustering algorithms. However, these algorithms have high computational cost hindering their use in large data sets. The techniques already developed in the Databases research field for indexing metric spaces usually consider the sets have a uniform distribution, without taking into account the existence of clusters in the data, therefore the structures need to generalize the efficiency of queries for the entire set simultaneously. However the similarity searching is often limited to a specific region of the data set. In this context, this dissertation proposes a new access method able to index metric data efficiently, especially for sets containing clusters. It also proposes a new algorithm for clustering metric data so that selection of a medoid from a particular subset of elements becomes more efficient. The experimental results showed that the proposed algorithms FAMES and M-FAMES can be used as a clustering technique for complex data that outperform PAM, CLARA and CLARANS in effectiveness and efficiency. Moreover, the similarity searching performed with the proposed metric access method FAMESMAM proved to be especially appropriate to data sets with clusters

A análise de agrupamentos (cluster analysis) é o conjunto de ferramentas estatísticas de análise multivariada para encontrar ou revelar a existência de grupos em uma amostra. A literatura apresenta muitos métodos para particionar um conjunto de dados. Porém, ao utilizá-los, o pesquisador muitas vezes se depara com o problema de decidir em quantos grupos deverá ser feita essa divisão, bem como comparar agrupamentos obtidos por diferentes métodos estabelecendo quão semelhantes eles são. Neste trabalho é feita uma revisão dos principais métodos de comparação de agrupamentos e é apresentada uma nova técnica para a escolha do número ideal de grupos, baseada na diferença de entropias. Afim de avaliá-la, estudos de simulação foram realizados comparando-a com outras técnicas conhecidas: a estatística Gap e a silhueta média. Os resultados indicaram que a nova proposta é tão ou mais eficiente que as demais, no sentido de encontrar o número correto de grupos. Além disso, ela também é computacionalmente mais rápida e de simples implementação. Duas aplicações a dados reais são apresentadas, ambas na área de genética. / Cluster analysis is the set of multivariate statistical techniques to uncover or discover groups in a sample. There?s plenty of methods in the literature to partition a dataset. But, when doing so, the user is frequently faced with the problem of choosing the appropriate number of groups and, also, how to compare clusterings obtained through different methods and establish how similar they are. In the present work, it is presented a revision of methods to compare clusterings and proposed a new technique to choose the appropriate number of groups, based on the difference of entropies. To evaluate it, a simulation study was made comparing it with other already known techniques: the Gap statistic and the silhouette. The results indicated that the new approach is more or as efficient as the others, in the sense of finding the correct number of clusters. Moreover, it is computationally faster and simple to implement. Two application are shown, both in genetics.

A análise de agrupamentos (cluster analysis) é o conjunto de ferramentas estatísticas de análise multivariada para encontrar ou revelar a existência de grupos em uma amostra. A literatura apresenta muitos métodos para particionar um conjunto de dados. Porém, ao utilizá-los, o pesquisador muitas vezes se depara com o problema de decidir em quantos grupos deverá ser feita essa divisão, bem como comparar agrupamentos obtidos por diferentes métodos estabelecendo quão semelhantes eles são. Neste trabalho é feita uma revisão dos principais métodos de comparação de agrupamentos e é apresentada uma nova técnica para a escolha do número ideal de grupos, baseada na diferença de entropias. Afim de avaliá-la, estudos de simulação foram realizados comparando-a com outras técnicas conhecidas: a estatística Gap e a silhueta média. Os resultados indicaram que a nova proposta é tão ou mais eficiente que as demais, no sentido de encontrar o número correto de grupos. Além disso, ela também é computacionalmente mais rápida e de simples implementação. Duas aplicações a dados reais são apresentadas, ambas na área de genética. / Cluster analysis is the set of multivariate statistical techniques to uncover or discover groups in a sample. There?s plenty of methods in the literature to partition a dataset. But, when doing so, the user is frequently faced with the problem of choosing the appropriate number of groups and, also, how to compare clusterings obtained through different methods and establish how similar they are. In the present work, it is presented a revision of methods to compare clusterings and proposed a new technique to choose the appropriate number of groups, based on the difference of entropies. To evaluate it, a simulation study was made comparing it with other already known techniques: the Gap statistic and the silhouette. The results indicated that the new approach is more or as efficient as the others, in the sense of finding the correct number of clusters. Moreover, it is computationally faster and simple to implement. Two application are shown, both in genetics.

<p>Recent literature has investigated the use of different clustering techniques for analysis of gene expression data. For example, self-organizing maps (SOMs) have been used to identify gene clusters of clear biological relevance in human hematopoietic differentiation and the yeast cell cycle (Tamayo et al., 1999). Hierarchical clustering has also been proposed for identifying clusters of genes that share common roles in cellular processes (Eisen et al., 1998; Michaels et al., 1998; Wen et al., 1998). Systematic evaluation of clustering results is as important as generating the clusters. However, this is a difficult task, which is often overlooked in gene expression studies. Several gene expression studies claim success of the clustering algorithm without showing a validation of complete clusterings, for example Ben-Dor and Yakhini (1999) and Törönen et al. (1999).</p><p>In this dissertation we propose an evaluation approach based on a relative entropy measure that uses additional knowledge about genes (gene annotations) besides the gene expression data. More specifically, we use gene annotations in the form of an enzyme classification hierarchy, to evaluate clusterings. This classification is based on the main chemical reactions that are catalysed by enzymes. Furthermore, we evaluate clusterings with pure statistical measures of cluster validity (compactness and isolation).</p><p>The experiments include applying two types of clustering methods (SOMs and hierarchical clustering) on a data set for which good annotation is available, so that the results can be partly validated from the viewpoint of biological relevance.</p><p>The evaluation of the clusters indicates that clusters obtained from hierarchical average linkage clustering have much higher relative entropy values and lower compactness and isolation compared to SOM clusters. Clusters with high relative entropy often contain enzymes that are involved in the same enzymatic activity. On the other hand, the compactness and isolation measures do not seem to be reliable for evaluation of clustering results.</p>

Clustering helps users gain insights from their data by discovering hidden structures in an unsupervised way. Unlike classification tasks that are evaluated using well-defined target labels, clustering is an intrinsically subjective task as it depends on the interpretation, need and interest of users. In many real-world applications, multiple meaningful clusterings can be hidden in the data, and different users are interested in exploring different perspectives and use cases of this same data. Despite this, most existing clustering techniques only attempt to produce a single clustering of the data, which can be too strict. In this thesis, a general method is proposed to discover multiple alternative clusterings of the data, and let users select the clustering(s) they are most interested in. In order to cover a large set of possible clustering solutions, a diverse set of clusterings is first generated based on various projections of the data. Then, similar clusterings are found, filtered, and aggregated into one representative clustering, allowing the user to only explore a small set of non-redundant representative clusterings. We compare the proposed method against others and analyze its advantages and disadvantages, based on artificial and real-world datasets, as well as on images enabling a visual assessment of the meaningfulness of the discovered clustering solutions. On the other hand, extensive studies and analysis concerning a variety of techniques used in the method are made. Results show that the proposed method is able to discover multiple interesting and meaningful clustering solutions.

Recent literature has investigated the use of different clustering techniques for analysis of gene expression data. For example, self-organizing maps (SOMs) have been used to identify gene clusters of clear biological relevance in human hematopoietic differentiation and the yeast cell cycle (Tamayo et al., 1999). Hierarchical clustering has also been proposed for identifying clusters of genes that share common roles in cellular processes (Eisen et al., 1998; Michaels et al., 1998; Wen et al., 1998). Systematic evaluation of clustering results is as important as generating the clusters. However, this is a difficult task, which is often overlooked in gene expression studies. Several gene expression studies claim success of the clustering algorithm without showing a validation of complete clusterings, for example Ben-Dor and Yakhini (1999) and Törönen et al. (1999). In this dissertation we propose an evaluation approach based on a relative entropy measure that uses additional knowledge about genes (gene annotations) besides the gene expression data. More specifically, we use gene annotations in the form of an enzyme classification hierarchy, to evaluate clusterings. This classification is based on the main chemical reactions that are catalysed by enzymes. Furthermore, we evaluate clusterings with pure statistical measures of cluster validity (compactness and isolation). The experiments include applying two types of clustering methods (SOMs and hierarchical clustering) on a data set for which good annotation is available, so that the results can be partly validated from the viewpoint of biological relevance. The evaluation of the clusters indicates that clusters obtained from hierarchical average linkage clustering have much higher relative entropy values and lower compactness and isolation compared to SOM clusters. Clusters with high relative entropy often contain enzymes that are involved in the same enzymatic activity. On the other hand, the compactness and isolation measures do not seem to be reliable for evaluation of clustering results.

In our current political climate, state level legislators have become increasingly impor- tant. Due to cuts in funding and growing focus at the national level, public oversight for these legislators has drastically decreased. This makes it difficult for citizens and activists to understand the relationships and commonalities between legislators. This thesis provides three contributions to address this issue. First, we created a data set containing over 1200 features focused on a legislator’s activity on bills. Second, we created embeddings that represented a legislator’s level of activity and engagement for a given bill using a custom model called Democracy2Vec. Third, we provided a case study focused on the 2015-2016 California State Legislator and had our results verified by a political expert. Our results show that our embeddings can explain relationships between legislator and how they will likely act during the legislative process.

Le clustering est le processus de partitionnement d’un ensemble de données en groupes, de sorte que les instances du même groupe sont plus semblables les unes aux autres qu’avec celles de tout autre groupe. De nombreux algorithmes de clustering ont été proposés, mais aucun d’entre eux ne s’avère fournir une partitiondes données pertinente dans toutes les situations. Le clustering par consensus vise à améliorer le processus de regroupement en combinant différentes partitions obtenues à partir de divers algorithmes afin d’obtenir une solution de consensus de meilleure qualité. Dans ce travail, une nouvelle méthode de clustering par consensus, appelée MultiCons, est proposée. Cette méthode utilise la technique d’extraction des itemsets fréquents fermés dans le but de découvrir les similitudes entre les différentes solutions de clustering dits de base. Les similitudes identifiées sont représentées sous une forme de motifs de clustering, chacun définissant un accord entre un ensemble de clusters de bases sur le regroupement d’un ensemble d’instances. En traitant ces motifs par groupes, en fonction du nombre de clusters de base qui définissent le motif, la méthode MultiCons génère une solution de consensus pour chaque groupe, générant par conséquence plusieurs consensus candidats. Ces différentes solutions sont ensuite représentées dans une structure arborescente appelée arbre de consensus, ouConsTree. Cette représentation graphique facilite la compréhension du processus de construction des multiples consensus, ainsi que les relations entre les instances et les structures d’instances dans l’espace de données / Clustering is the process of partitioning a dataset into groups, so that the instances in the same group are more similar to each other than to instances in any other group. Many clustering algorithms were proposed, but none of them proved to provide good quality partition in all situations. Consensus clustering aims to enhance the clustering process by combining different partitions obtained from different algorithms to yield a better quality consensus solution. In this work, a new consensus clustering method, called MultiCons, is proposed. It uses the frequent closed itemset mining technique in order to discover the similarities between the different base clustering solutions. The identified similarities are presented in a form of clustering patterns, that each defines the agreement between a set of base clusters in grouping a set of instances. By dividing these patterns into groups based on the number of base clusters that define the pattern, MultiCons generates a consensussolution from each group, resulting in having multiple consensus candidates. These different solutions are presented in a tree-like structure, called ConsTree, that facilitates understanding the process of building the multiple consensuses, and also the relationships between the data instances and their structuring in the data space. Five consensus functions are proposed in this work in order to build a consensus solution from the clustering patterns. Approach 1 is to just merge any intersecting clustering patterns. Approach 2 can either merge or split intersecting patterns based on a proposed measure, called intersection ratio