Unsupervised image clustering is a challenging and often ill-posed problem. Existing image descriptors fail to capture the clustering criterion well, and more importantly, the criterion itself may depend on (unknown) user preferences. Semi-supervised approaches such as distance metric learning and constrained clustering thus leverage user-provided annotations indicating which pairs of images belong to the same cluster (must-link) and which ones do not (cannot-link). These approaches require many such constraints before achieving good clustering performance because each constraint only provides weak cues about the desired clustering. In this work, we propose to use image attributes as a modality for the user to provide more informative cues. In particular, the clustering algorithm iteratively and actively queries a user with an image pair. Instead of the user simply providing a must-link/cannot-link constraint for the pair, the user also provides an attribute-based reasoning e.g. "these two images are similar because both are natural and have still water'' or "these two people are dissimilar because one is way older than the other''. Under the guidance of this explanation, and equipped with attribute predictors, many additional constraints are automatically generated. We demonstrate the effectiveness of our approach by incorporating the proposed attribute-based explanations in three standard semi-supervised clustering algorithms: Constrained K-Means, MPCK-Means, and Spectral Clustering, on three domains: scenes, shoes, and faces, using both binary and relative attributes. / Master of Science

Nesta tese, são estudados algoritmos para agrupamento de dados, com particular ênfase em Agrupamento de Dados com Restrições, no qual, além dos objetos a serem agrupados, são fornecidos pelo usuário algumas informações sobre o agrupamento desejado. Como fundamentação para o agrupamento, são considerados os modelos de mistura finitos, em especial, com componentes gaussianos, usualmente chamados de modelos de mistura de gaussianas. Dentre os principais problemas que os algoritmos desenvolvidos nesta tese de doutorado buscam tratar destacam-se: (i) estimar parâmetros de modelo de mistura de gaussianas; (ii) como incorporar, de forma eficiente, restrições no processo de aprendizado de forma que tanto os dados quanto as restrições possam ser adicionadas de forma online; (iii) estimar, via restrições derivadas de conceitos pré-determinados sobre os objetos (usualmente chamados de classes), o número de grupos destes conceitos. Como ferramenta para auxiliar no desenvolvimento de soluções para tais problemas, foram utilizados algoritmos evolutivos que operam com mais de uma solução simultaneamente, além de utilizarem informações de soluções anteriores para guiar o processo de busca. Especificamente, foi desenvolvido um algoritmo evolutivo baseado na divisão e união de componentes para a estimação dos parâmetros de um modelo de mistura de gaussianas. Este algoritmo foi comparado com o algoritmo do mesmo gênero considerado estado-da-arte na literatura, apresentando resultados competitivos e necessitando de menos parâmetros e um menor custo computacional. Nesta tese, foram desenvolvidos dois algoritmos que incorporam as restrições no processo de agrupamento de forma online. Ambos os algoritmos são baseados em algoritmos bem-conhecidos na literatura e apresentaram, em comparações empíricas, resultados melhores que seus antecessores. Finalmente, foram propostos dois algoritmos para se estimar o número de grupos por classe. Ambos os algoritmos foram comparados com algoritmos reconhecidos na literatura de agrupamento de dados com restrições, e apresentaram resultados competitivos ou melhores que estes. A estimação bem sucedida do número de grupos por classe pode auxiliar em diversas tarefas de mineração de dados, desde a sumarização dos dados até a decomposição de problemas de classificação em sub-problemas potencialmente mais simples. / In the last decade, researchers have been giving considerable attention to the field of Constrained Clustering. Algorithms in this field assume that along with the objects to be clustered, the user also provides some constraints about which kind of clustering (s)he prefers. In this thesis, two scenarios are studied: clustering with and without constraints. The developments are based on finite mixture models, namely, models with Gaussian components, which are usually called Gaussian Mixture Models (GMMs). In this context the main problems addressed are: (i) parameter estimation of GMMs; (ii) efficiently integrating constraints in the learning process allowing both constraints and the data to be added in the modeling in an online fashion; (iii) estimating, by using constraints derived from pre-determined concepts (usually named classes), the number of clusters per concept. Evolutionary algorithms were adopted to develop solutions for such problems. These algorithms analyze more than one solution simultaneously and use information provided by previous solutions to guide the search process. Specifically, an evolutionary algorithm based on procedures that perform splitting and merging of components to estimate the parameters of a GMM was developed. This algorithm was compared to an algorithm considered as the state-of-the-art in the literature, obtaining competitive results while requiring less parameters and being more computationally efficient. Besides the aforementioned contributions, two algorithms for online constrained clustering were developed. Both algorithms are based on well known algorithms from the literature and get better results than their predecessors. Finally, two algorithms to estimate the number of clusters per class were also developed. Both algorithms were compared to well established algorithms from the literature of constrained clustering, and obtained equal or better results than the ones obtained by the contenders. The successful estimation of the number of clusters per class is helpful to a variety of data mining tasks, such as data summarization and problem decomposition of challenging classification problems.

Topic hierarchies are efficient ways of organizing document collections. These structures help users to manage the knowledge contained in textual data. These hierarchies are usually obtained through unsupervised hierarchical clustering algorithms. By not considering the context of the user in the formation of the hierarchical groups, unsupervised topic hierarchies may not attend the user\'s expectations in some cases. One possible solution for this problem is to employ semi-supervised clustering algorithms. These algorithms incorporate the user\'s knowledge through the usage of constraints to the clustering process. However, in the context of semi-supervised hierarchical clustering, the works in the literature do not efficient explore the selection of cases (instances or cluster) to add constraints, neither the interaction of the user with the clustering process. In this sense, in this work we introduce two semi-supervised hierarchical clustering algorithms: HCAC (Hierarchical Confidence-based Active Clustering) and HCAC-LC (Hierarchical Confidence-based Active Clustering with Limited Constraints). These algorithms employ an active learning approach based in the confidence of cluster merges. When a low confidence merge is detected, the user is invited to decide, from a pool of candidate pairs of clusters, the best cluster merge in that point. In this work, we employ HCAC and HCAC-LC in the extraction of topic hierarchies through the SMITH framework, which is also proposed in this thesis. This framework provides a series of well defined activities that allow the user\'s interaction in the generation of topic hierarchies. The active learning approach used in the HCAC-based algorithms, the kind of queries employed in these algorithms, as well as the SMITH framework for the generation of semi-supervised topic hierarchies are innovations to the state of the art proposed in this thesis. Our experimental results indicate that HCAC and HCAC-LC outperform other semi-supervised hierarchical clustering algorithms in diverse scenarios. The results also indicate that semi-supervised topic hierarchies obtained through the SMITH framework are more intuitive and easier to navigate than unsupervised topic hierarchies / Hierarquias de tópicos são formas eficientes de organização de coleções de documentos, auxiliando usuários a gerir o conhecimento materializado nessas publicações textuais. Tais hierarquias são usualmente construídas por meio de algoritmos de agrupamento hierárquico não supervisionado. Entretanto, por não considerarem o contexto do usuário na formação dos grupos, hierarquias de tópicos não supervisionadas nem sempre conseguem atender as suas expectativas. Uma solução para este problema e o emprego de algoritmos de agrupamento semissupervisionado, os quais incorporam o conhecimento de domínio do usuário por meio de restrições. Entretanto, para o contexto de agrupamento hierárquico semissupervisionado, não são eficientemente explorados na literatura métodos de seleção de casos (instâncias ou grupos) para receber restrições, bem como não há formas eficientes de interação do usuário com o processo de agrupamento hierárquico. Dessa maneira, neste trabalho, dois algoritmos de agrupamento hierárquico semissupervisionado são propostos: HCAC (Hierarchical Confidence-based Active Clustering) e HCAC-LC (Hierarchical Confidence-based Active Clustering with Limited Constraints). Estes algoritmos empregam uma abordagem de aprendizado ativo baseado na confiança de uma junção de clusters. Quando uma junção de baixa confiança e detectada, o usuário e convidado a decidir, em um conjunto de pares de grupos candidatos, a melhor junção naquele ponto. Estes algoritmos são aqui utilizados na extração de hierarquias de tópicos por meio do framework SMITH, também proposto nesse trabalho. Este framework fornece uma série de atividades bem definidas que possibilitam a interação do usuário para a obtenção de hierarquias de tópicos. A abordagem de aprendizado ativo utilizado nos algoritmos HCAC e HCAC-LC, o tipo de restrição utilizada nestes algoritmos, bem como o framework SMITH para obtenção de hierarquias de tópicos semissupervisionadas são inovações ao estado da arte propostos neste trabalho. Os resultados obtidos indicam que os algoritmos HCAC e HCAC-LC superam o desempenho de outros algoritmos hierárquicos semissupervisionados em diversos cenários. Os resultados também indicam que hierarquias de tópico semissupervisionadas obtidas por meio do framework SMITH são mais intuitivas e fáceis de navegar do que aquelas não supervisionadas

Image annotation is defined as generating a set of textual words for a given image, learning from the available training data consisting of visual image content and annotation words. Methods developed for image annotation usually make use of region clustering algorithms to quantize the visual information. Visual codebooks are generated from the region clusters of low level visual features. These codebooks are then, matched with the words of the text document related to the image, in various ways. In this thesis, we propose a new image annotation technique, which improves the representation and quantization of the visual information by employing the available but unused information, called side information, which is hidden in the system. This side information is used to semi-supervise the clustering process which creates the visterms. The selection of side information depends on the visual image content, the annotation words and the relationship between them. Although there may be many different ways of defining and selecting side information, in this thesis, three types of side information are proposed. The first one is the hidden topic probability information obtained automatically from the text document associated with the image. The second one is the orientation and the third one is the color information around interest points that correspond to critical locations in the image. The side information provides a set of constraints in a semi-supervised K-means region clustering algorithm. Consequently, in generation of the visual terms from the regions, not only low level features are clustered, but also side information is used to complement the visual information, called visterms. This complementary information is expected to close the semantic gap between the low level features extracted from each region and the high level textual information. Therefore, a better match between visual codebook and the annotation words is obtained. Moreover, a speedup is obtained in the modified K-means algorithm because of the constraints brought by the side information. The proposed algorithm is implemented in a high performance parallel computation environment.

Nesta tese, são estudados algoritmos para agrupamento de dados, com particular ênfase em Agrupamento de Dados com Restrições, no qual, além dos objetos a serem agrupados, são fornecidos pelo usuário algumas informações sobre o agrupamento desejado. Como fundamentação para o agrupamento, são considerados os modelos de mistura finitos, em especial, com componentes gaussianos, usualmente chamados de modelos de mistura de gaussianas. Dentre os principais problemas que os algoritmos desenvolvidos nesta tese de doutorado buscam tratar destacam-se: (i) estimar parâmetros de modelo de mistura de gaussianas; (ii) como incorporar, de forma eficiente, restrições no processo de aprendizado de forma que tanto os dados quanto as restrições possam ser adicionadas de forma online; (iii) estimar, via restrições derivadas de conceitos pré-determinados sobre os objetos (usualmente chamados de classes), o número de grupos destes conceitos. Como ferramenta para auxiliar no desenvolvimento de soluções para tais problemas, foram utilizados algoritmos evolutivos que operam com mais de uma solução simultaneamente, além de utilizarem informações de soluções anteriores para guiar o processo de busca. Especificamente, foi desenvolvido um algoritmo evolutivo baseado na divisão e união de componentes para a estimação dos parâmetros de um modelo de mistura de gaussianas. Este algoritmo foi comparado com o algoritmo do mesmo gênero considerado estado-da-arte na literatura, apresentando resultados competitivos e necessitando de menos parâmetros e um menor custo computacional. Nesta tese, foram desenvolvidos dois algoritmos que incorporam as restrições no processo de agrupamento de forma online. Ambos os algoritmos são baseados em algoritmos bem-conhecidos na literatura e apresentaram, em comparações empíricas, resultados melhores que seus antecessores. Finalmente, foram propostos dois algoritmos para se estimar o número de grupos por classe. Ambos os algoritmos foram comparados com algoritmos reconhecidos na literatura de agrupamento de dados com restrições, e apresentaram resultados competitivos ou melhores que estes. A estimação bem sucedida do número de grupos por classe pode auxiliar em diversas tarefas de mineração de dados, desde a sumarização dos dados até a decomposição de problemas de classificação em sub-problemas potencialmente mais simples. / In the last decade, researchers have been giving considerable attention to the field of Constrained Clustering. Algorithms in this field assume that along with the objects to be clustered, the user also provides some constraints about which kind of clustering (s)he prefers. In this thesis, two scenarios are studied: clustering with and without constraints. The developments are based on finite mixture models, namely, models with Gaussian components, which are usually called Gaussian Mixture Models (GMMs). In this context the main problems addressed are: (i) parameter estimation of GMMs; (ii) efficiently integrating constraints in the learning process allowing both constraints and the data to be added in the modeling in an online fashion; (iii) estimating, by using constraints derived from pre-determined concepts (usually named classes), the number of clusters per concept. Evolutionary algorithms were adopted to develop solutions for such problems. These algorithms analyze more than one solution simultaneously and use information provided by previous solutions to guide the search process. Specifically, an evolutionary algorithm based on procedures that perform splitting and merging of components to estimate the parameters of a GMM was developed. This algorithm was compared to an algorithm considered as the state-of-the-art in the literature, obtaining competitive results while requiring less parameters and being more computationally efficient. Besides the aforementioned contributions, two algorithms for online constrained clustering were developed. Both algorithms are based on well known algorithms from the literature and get better results than their predecessors. Finally, two algorithms to estimate the number of clusters per class were also developed. Both algorithms were compared to well established algorithms from the literature of constrained clustering, and obtained equal or better results than the ones obtained by the contenders. The successful estimation of the number of clusters per class is helpful to a variety of data mining tasks, such as data summarization and problem decomposition of challenging classification problems.

Topic hierarchies are efficient ways of organizing document collections. These structures help users to manage the knowledge contained in textual data. These hierarchies are usually obtained through unsupervised hierarchical clustering algorithms. By not considering the context of the user in the formation of the hierarchical groups, unsupervised topic hierarchies may not attend the user\'s expectations in some cases. One possible solution for this problem is to employ semi-supervised clustering algorithms. These algorithms incorporate the user\'s knowledge through the usage of constraints to the clustering process. However, in the context of semi-supervised hierarchical clustering, the works in the literature do not efficient explore the selection of cases (instances or cluster) to add constraints, neither the interaction of the user with the clustering process. In this sense, in this work we introduce two semi-supervised hierarchical clustering algorithms: HCAC (Hierarchical Confidence-based Active Clustering) and HCAC-LC (Hierarchical Confidence-based Active Clustering with Limited Constraints). These algorithms employ an active learning approach based in the confidence of cluster merges. When a low confidence merge is detected, the user is invited to decide, from a pool of candidate pairs of clusters, the best cluster merge in that point. In this work, we employ HCAC and HCAC-LC in the extraction of topic hierarchies through the SMITH framework, which is also proposed in this thesis. This framework provides a series of well defined activities that allow the user\'s interaction in the generation of topic hierarchies. The active learning approach used in the HCAC-based algorithms, the kind of queries employed in these algorithms, as well as the SMITH framework for the generation of semi-supervised topic hierarchies are innovations to the state of the art proposed in this thesis. Our experimental results indicate that HCAC and HCAC-LC outperform other semi-supervised hierarchical clustering algorithms in diverse scenarios. The results also indicate that semi-supervised topic hierarchies obtained through the SMITH framework are more intuitive and easier to navigate than unsupervised topic hierarchies / Hierarquias de tópicos são formas eficientes de organização de coleções de documentos, auxiliando usuários a gerir o conhecimento materializado nessas publicações textuais. Tais hierarquias são usualmente construídas por meio de algoritmos de agrupamento hierárquico não supervisionado. Entretanto, por não considerarem o contexto do usuário na formação dos grupos, hierarquias de tópicos não supervisionadas nem sempre conseguem atender as suas expectativas. Uma solução para este problema e o emprego de algoritmos de agrupamento semissupervisionado, os quais incorporam o conhecimento de domínio do usuário por meio de restrições. Entretanto, para o contexto de agrupamento hierárquico semissupervisionado, não são eficientemente explorados na literatura métodos de seleção de casos (instâncias ou grupos) para receber restrições, bem como não há formas eficientes de interação do usuário com o processo de agrupamento hierárquico. Dessa maneira, neste trabalho, dois algoritmos de agrupamento hierárquico semissupervisionado são propostos: HCAC (Hierarchical Confidence-based Active Clustering) e HCAC-LC (Hierarchical Confidence-based Active Clustering with Limited Constraints). Estes algoritmos empregam uma abordagem de aprendizado ativo baseado na confiança de uma junção de clusters. Quando uma junção de baixa confiança e detectada, o usuário e convidado a decidir, em um conjunto de pares de grupos candidatos, a melhor junção naquele ponto. Estes algoritmos são aqui utilizados na extração de hierarquias de tópicos por meio do framework SMITH, também proposto nesse trabalho. Este framework fornece uma série de atividades bem definidas que possibilitam a interação do usuário para a obtenção de hierarquias de tópicos. A abordagem de aprendizado ativo utilizado nos algoritmos HCAC e HCAC-LC, o tipo de restrição utilizada nestes algoritmos, bem como o framework SMITH para obtenção de hierarquias de tópicos semissupervisionadas são inovações ao estado da arte propostos neste trabalho. Os resultados obtidos indicam que os algoritmos HCAC e HCAC-LC superam o desempenho de outros algoritmos hierárquicos semissupervisionados em diversos cenários. Os resultados também indicam que hierarquias de tópico semissupervisionadas obtidas por meio do framework SMITH são mais intuitivas e fáceis de navegar do que aquelas não supervisionadas

We wish to understand brain; discover its sophisticated ways of calculations to invent improved computational methods. To decipher any complex system, first its components should be understood. Brain comprises neurons. Neurobiologists use morphologic properties like “somatic perimeter”, “axonal length”, and “number of dendrites” to classify neurons. They have discerned two types of neurons: “interneurons” and “pyramidal cells”, and have a consensus about five classes of interneurons: PV, 2/3, Martinotti, Chandelier, and NPY. They still need a more refined classification of interneurons because they suppose its known classes may contain subclasses or new classes may arise. This is a difficult process because of the great number and diversity of interneurons and lack of objective indices to classify them. Machine learning—automatic learning from data—can overcome the mentioned difficulties, but it needs a data set to learn from. To meet this demand neurobiologists compiled a data set from measuring 67 morphologic properties of 220 interneurons of mouse brains; they also labeled some of the samples—i.e. added their opinion about the sample’s classes. This project aimed to use machine learning to determine the true number of classes within the data set, classes of the unlabeled samples, and the accuracy of the available class labels. We used K-means, seeded K-means, and constrained K-means, and clustering validity techniques to achieve our objectives. Our results indicate that: the data set contains seven classes; seeded K-means outperforms K-means and constrained K-means; chandelier and 2/3 are the most consistent classes, whereas PV and Martinotti are the least consistent ones.

Cette thèse s'inscrit dans la problématique de l'indexation et la recherche d'images par le contenu dans des bases d'images volumineuses. Les systèmes traditionnels de recherche d'images par le contenu se composent généralement de trois étapes : l'indexation, la structuration et la recherche. Dans le cadre de cette thèse, nous nous intéressons plus particulièrement à l'étape de structuration qui vise à organiser, dans une structure de données, les signatures visuelles des images extraites dans la phase d'indexation afin de faciliter, d'accélérer et d'améliorer les résultats de la recherche ultérieure. A la place des méthodes traditionnelles de structuration, nous étudions les méthodes de regroupement des données (clustering) qui ont pour but d'organiser les signatures en groupes d'objets homogènes (clusters), sans aucune contrainte sur la taille des clusters, en se basant sur la similarité entre eux. Afin de combler le fossé sémantique entre les concepts de haut niveau sémantique exprimés par l'utilisateur et les signatures de bas niveau sémantique extraites automatiquement dans la phase d'indexation, nous proposons d'impliquer l'utilisateur dans la phase de clustering pour qu'il puisse interagir avec le système afin d'améliorer les résultats du clustering, et donc améliorer les résultats de la recherche ultérieure. En vue d'impliquer l'utilisateur dans la phase de clustering, nous proposons un nouveau modèle de clustering semi-supervisé interactif en utilisant les contraintes par paires (must-link et cannot-link) entre les groupes d'images. Tout d'abord, les images sont regroupées par le clustering non supervisé BIRCH (Zhang et al., 1996). Ensuite, l'utilisateur est impliqué dans la boucle d'interaction afin d'aider le clustering. Pour chaque itération interactive, l'utilisateur visualise les résultats de clustering et fournit des retours au système via notre interface interactive. Par des simples cliques, l'utilisateur peut spécifier les images positives ainsi que les images négatives pour chaque cluster. Il peut aussi glisser les images entre les clusters pour demander de changer l'affectation aux clusters des images. Les contraintes par paires sont ensuite déduites en se basant sur les retours de l'utilisateur ainsi que les informations de voisinage. En tenant compte de ces contraintes, le système réorganise les clusters en utilisant la méthode de clustering semi-supervisé proposée dans cette thèse. La boucle d'interaction peut être répétée jusqu'à ce que le résultat du clustering satisfasse l'utilisateur. Différentes stratégies pour déduire les contraintes par paires entre les images sont proposées. Ces stratégies sont analysées théoriquement et expérimentalement. Afin d'éviter que les résultats expérimentaux dépendent subjectivement de l'utilisateur humain, un agent logiciel simulant le comportement de l'utilisateur humain pour donner des retours est utilisé pour nos expérimentations. En comparant notre méthode avec la méthode de clustering semi-supervisé la plus populaire HMRF-kmeans (Basu et al., 2004), notre méthode donne de meilleurs résultats. / This thesis deals with the problem of Content-Based Image Retrieval (CBIR) on large image databases. Traditional CBIR systems generally rely on three phases : feature extraction, feature space structuring and retrieval. In this thesis, we are particularly interested in the structuring phase, which aims at organizing the visual feature descriptors of all images into an efficient data structure in order to facilitate, accelerate and improve further retrieval. The visual feature descriptor of each image is extracted from the feature extraction phase. Instead of traditional structuring methods, clustering methods which aim at organizing image descriptors into groups of similar objects (clusters), without any constraint on the cluster size, are studied. In order to reduce the “semantic gap” between high-level semantic concepts expressed by the user and the low-level features automatically extracted from the images, we propose to involve the user in the clustering phase so that he/she can interact with the system so as to improve the clustering results, and thus improve the results of further retrieval. With the aim of involving the user in the clustering phase, we propose a new interactive semi-supervised clustering model based on pairwise constraints (must-link and cannot-link) between groups of images. Firstly, images are organized into clusters by using the unsupervised clustering method BIRCH (Zhang et al., 1996). Then the user is involved into the interaction loop in order to guide the clustering process. In each interactive iteration, the user visualizes the clustering results and provide feedback to the system via our interactive interface. With some simple clicks, the user can specify the positive and/or negative images for each cluster. The user can also drag and drop images between clusters in order to change the cluster assignment of some images. Pairwise constraints are then deduced based on the user feedback as well as the neighbourhood information. By taking into account these constraints, the system re-organizes the data set, using the semi-supervised clustering proposed in this thesis. The interaction loop can be iterated until the clustering result satisfies the user. Different strategies for deducing pairwise constraints are proposed. These strategies are theoretically and experimentally analyzed. In order to avoid the subjective dependence of the clustering results on the human user, a software agent simulating the behaviour of the human user for providing feedback to the system is used in our experiments. By comparing our method with the most popular semi-supervised clustering HMRF-kmeans (Basu et al., 2004), our method gives better results.

No description available.