No contexto de Redes Complexas, particularmente das redes sociais, grupos de objetos densamente conectados entre si, esparsamente conectados a outros grupos, são denominados de comunidades. Detecção dessas comunidades tornou-se um campo de crescente interesse científico e possui inúmeras aplicações práticas. Nesse contexto, surgiram várias pesquisas sobre estratégias multinível para particionar redes com elevada quantidade de vértices e arestas. O objetivo dessas estratégias é diminuir o custo do algoritmo de particionamento aplicando-o sobre uma versão reduzida da rede original. Uma possibilidade dessa estratégia, ainda pouco explorada, é utilizar heurísticas de refinamento local para melhorar a solução final. A maioria das abordagens de refinamento exploram propriedades gerais de redes complexas, tais como corte mínimo ou modularidade, porém, não exploram propriedades inerentes de domínios específicos. Por exemplo, redes sociais são caracterizadas por elevado coeficiente de agrupamento e assortatividade significativa, consequentemente, maximizar tais características pode conduzir a uma boa solução e uma estrutura de comunidades bem definida. Motivado por essa lacuna, neste trabalho é proposto um novo algoritmo de refinamento, denominado RSim, que explora características de alto grau de transitividade e assortatividade presente em algumas redes reais, em particular em redes sociais. Para isso, adotou-se medidas de similaridade híbridas entre pares de vértices, que utilizam os conceitos de vizinhança e informações de comunidades para interpretar a semelhança entre pares de vértices. Uma análise comparativa e sistemática demonstrou que o RSim supera os algoritmos de refinamento habituais em redes com alto coeficiente de agrupamento e assortatividade. Além disso, avaliou-se o RSim em uma aplicação real. Nesse cenário, o RSim supera todos os métodos avaliado quanto a eficiência e eficácia, considerando todos os conjuntos de dados selecionados. / In the context of complex networks, particularly social networks, groups of densely interconnected objects, sparsely linked to other groups are called communities. Detection of these communities has become a field of increasing scientific interest and has numerous practical applications. In this context, several studies have emerged on multilevel strategies for partitioning networks with high amount of vertices and edges. The goal of these strategies is to reduce the cost of partitioning algorithm by applying it on a reduced version of the original network. The possibility for this strategy, yet little explored, is to apply local refinement heuristics to improve the final solution. Most refinement approaches explore general properties of complex networks, such as minimum cut or modularity, however, do not exploit inherent properties of specific domains. For example, social networks are characterized by high clustering coefficient and significant assortativity, hence maximize such characteristics may lead to a good solution and a well-defined community structure. Motivated by this gap, in this thesis, we propose a new refinement algorithm, called RSim, which exploits characteristics of high degree of transitivity and assortativity present in some real networks, particularly social networks. For this, we adopted hybrid similarity measures between pairs of vertices, using the concepts of neighborhood and community information to interpret the similarity between pairs of vertices. A systematic and comparative analysis showed that the RSim statistically outperforms usual refinement algorithms in networks with high clustering coefficient and assortativity. In addition, we assessed the RSim in a real application. In this scenario, the RSim surpasses all evaluated methods in efficiency and effectiveness, considering all the selected data sets.

O problema de agrupamento de dados em grafos consiste em encontrar clusters de nós em um dado grafo, ou seja, encontrar subgrafos com alta conectividade. Esse problema pode receber outras nomenclaturas, algumas delas são: problema de particionamento de grafos e problema de detecção de comunidades. Para modelar esse problema, existem diversas formulações matemáticas, cada qual com suas vantagens e desvantagens. A maioria dessas formulações tem como desvantagem a necessidade da definição prévia do número de grupos que se deseja obter. Entretanto, esse tipo de informação não está contida em dados para agrupamento, ou seja, em dados não rotulados. Esse foi um dos motivos da popularização nas últimas décadas da medida conhecida como modularidade, que tem sido maximizada para encontrar partições em grafos. Essa formulação, além de não exigir a definição prévia do número de clusters, se destaca pela qualidade das partições que ela fornece. Nesta Tese, metaheurísticas Greedy Randomized Search Procedures para dois modelos existentes para agrupamento em grafos foram propostas: uma para o problema de maximização da modularidade e a outra para o problema de maximização da similaridade intra-cluster. Os resultados obtidos por essas metaheurísticas foram melhores quando comparadas àqueles de outras heurísticas encontradas na literatura. Entretanto, o custo computacional foi alto, principalmente o da metaheurística para o modelo de maximização da modularidade. Com o passar dos anos, estudos revelaram que a formulação que maximiza a modularidade das partições possui algumas limitações. A fim de promover uma alternativa à altura do modelo de maximização da modularidade, esta Tese propõe novas formulações matemáticas de agrupamento em grafos com e sem pesos que visam encontrar partições cujos clusters apresentem alta conectividade. Além disso, as formulações propostas são capazes de prover partições sem a necessidade de definição prévia do número de clusters. Testes com centenas de grafos com pesos comprovaram a eficiência dos modelos propostos. Comparando as partições provenientes de todos os modelos estudados nesta Tese, foram observados melhores resultados em uma das novas formulações propostas, que encontrou partições bastante satisfatórias, superiores às outras existentes, até mesmo para a de maximização de modularidade. Os resultados apresentaram alta correlação com a classificação real dos dados simulados e reais, sendo esses últimos, em sua maioria, de origem biológica / Graph clustering aims at identifying highly connected groups or clusters of nodes of a graph. This problem can assume others nomenclatures, such as: graph partitioning problem and community detection problem. There are many mathematical formulations to model this problem, each one with advantages and disadvantages. Most of these formulations have the disadvantage of requiring the definition of the number of clusters in the final partition. Nevertheless, this type of information is not found in graphs for clustering, i.e., whose data are unlabeled. This is one of the reasons for the popularization in the last decades of the measure known as modularity, which is being maximized to find graph partitions. This formulation does not require the definition of the number of clusters of the partitions to be produced, and produces high quality partitions. In this Thesis, Greedy Randomized Search Procedures metaheuristics for two existing graph clustering mathematical formulations are proposed: one for the maximization of the partition modularity and the other for the maximization of the intra-cluster similarity. The results obtained by these proposed metaheuristics outperformed the results from other heuristics found in the literature. However, their computational cost was high, mainly for the metaheuristic for the maximization of modularity model. Along the years, researches revealed that the formulation that maximizes the modularity of the partitions has some limitations. In order to promote a good alternative for the maximization of the partition modularity model, this Thesis proposed new mathematical formulations for graph clustering for weighted and unweighted graphs, aiming at finding partitions with high connectivity clusters. Furthermore, the proposed formulations are able to provide partitions without a previous definition of the true number of clusters. Computational tests with hundreds of weighted graphs confirmed the efficiency of the proposed models. Comparing the partitions from all studied formulations in this Thesis, it was possible to observe that the proposed formulations presented better results, even better than the maximization of partition modularity. These results are characterized by satisfactory partitions with high correlation with the true classification for the simulated and real data (mostly biological)

A segmentação de imagens e, em visão computacional, uma tarefa de grande importância, para a qual existem várias abordagem. A complexidade de tais abordagens está relacionada à natureza da imagem e também ao grau de precisão da segmentação, que e um conceito bastante subjetivo, normalmente associado a semelhança que apresenta a segmentaçã produzida pela visão humana. Na segmentação de imagens baseada em algoritmos de agrupamento em grafos, geralmente os pixels da imagem compôem os nós do grafo e as arestas representam a similaridade entre estes nós. Assim, a segmentação pode ser obtida por meio do agrupamento dos nós do grafo. É importante salientar, no entanto, que as técnicas de agrupamento em grafos surgiram no contexto de reconhecimento de padrões, cujo objetivo primario era o tratamento de dados diversos que não envolviam imagens. O uso de tais tecnicas para a segmentação de imagens e relativamente recente e revela alguns problemas desaadores. O primeiro deles é a deficiente escalabilidade de alguns métodos, o que impede o seu uso efetivo em imagens de altas dimensões. Outra questão é a falta de estudos que avaliam as medidas de similaridade na montagem do grafo e critérios que aferem a qualidade do agrupamento para a área específica de segmentação de imagens. Em outras palavras, faltam na literatura análises mais específicas que indiquem quais algoritmos de agrupamento em grafos são mais efetivos para a segmentação de imagens e que procurem associar (ou correlacionar) as várias medidas de similaridade e métricas de qualidade de agrupamento que produzam segmentações mais precisas. Neste trabalho é apresentada a avaliação de 6 algoritmos de agrupamento em grafos formulados em base a 3 categorias identificadas (agrupamento espectral, algoritmos de particionamento multinível e algoritmos para detectar comunidades) e aplicadas na segmentação automática de imagens de cenas naturais com grandes dimensões. Esta avaliação objetiva aferir, sobretudo, a qualidade da segmentação, a escalabilidade, o desempenho de 7 funções de similaridade formuladas, e também visa corroborar a existência da correlação entre a qualidade do agrupamento e a qualidade da segmentação. Para reduzir o esforço computacional e contribuir com a escalabilidade dos algoritmos formulados é utilizado um algoritmo de pré-processamento (SLIC) que agrupa váarios pixels da imagem em uma unica região (superpixels), o que contribui para reduzir o tamanho do grafo e, consequentemente, reduzindo o custo computacional do agrupamento. Os resultados demostram que os algoritmos formulados LP (Label Propagation) e FG (Fast Greedy) apresentam boa escalabilidade e boa qualidade de segmentação. Seis das sete funções de similaridade avaliadas apresentam um bom desempenho, independentemente do algoritmo de agrupamento empregado. É mostrado também que exites correlação entre a medida de qualidade de agrupamento conhecido como índice de silhueta e a qualidade de segmentação, ou seja, quanto maior o valor de silhueta, melhor a segmentação. A qualidade de segmentação foi avaliada quantitativamente, utilizando-se um conjunto de imagens segmentadas manualmente / Image segmentation is an important task within computer vision for which many approaches are available. The complexity of such approaches are intrinsically related with the nature of the image and also the desired accuracy aimed at. Image segmentation accuracy, however, is a subjective concept and is normally associated with how much it resembles segmentation produced by the human vision system. In graphbased clustering image segmentation algorithms, pixels are normally represented as nodes and edges convey the similarity between such nodes. Hence, segmentation may be attained by means of grouping node of a graph. It is important, though, to point out that graph-based clustering techniques rst appeared in the context of pattern recognition and its primary data source were not images. The usage of such techniques for image segmentation is a recent trend and poses some challenge issues. The first is the poor scalability that many methods exhibit, impairing its application in images of larger dimensions. Another issues is that lack of studies that assess the goodness of similarity measures employed in graph computation and also clustering quality criteria assessments for the specic area of image processing. In other words, there is no evidences in the literature on how effective graph-based clustering algorithms are for image segmentation and no studies that associate similarity functions and clustering quality metrics with image processing quality. This work presents an evaluation of six graph-based clustering algorithms according to three major categories found in the literature (spectral clustering, multi layer partitioning algorithms and community detectors) applied to automatic segmentation of image of larger dimensions. This evaluation takes into account segmentation quality, scalability, the performance of seven similarity functions and, nally, bring some insights on the correlation between clustering and segmentation quality. To reduce computational costs and enhance scalability of the methods we employ a pre processing algorithm (SLIC) which combines many pixels into one single region (superpixel). This contributes to reduce the graph size and, consequently, the cost of clustering. Results have shown that the LP (Label Propagation) and FG (Fast Greedy) algorithms exhibit good scalability and good segmentation. Six out of the seven similarity functions presented good performance, regardless the clustering algorithm. We also have shown that there is correlation between clustering quality and image segmentation quality, when the Silhouette measure is employed. That is, the higher the Silhouette values, the better the segmentation. Image segmentation quality has been quantitatively assessed by means of ground-truth data or user segmented images

No description available.

El uso de las redes para modelar sistemas complejos es creciente en multitud de ambitos. Son extremadamente utiles para representar interacciones entre genes, relaciones sociales, intercambio de informaci on en Internet o correlaciones entre precios de acciones burs atiles, por nombrar s olo algunos ejemplos. Analizando la estructura de estas redes, comprendiendo c omo interaccionan sus distintos elementos, podremos entender mejor c omo se comporta el sistema en su conjunto. A menudo, los nodos que conforman estas redes tienden a formar grupos altamente conectados. Esta propiedad es conocida como estructura de comunidades y esta tesis doctoral se ha centrado en el problema de c omo mejorar su detecci on y caracterizaci on. Como primer objetivo de este trabajo, se encuentra la generaci on de m etodos e cientes que permitan caracterizar las comunidades de una red y comprender su estructura. Segundo, pretendemos plantear una serie de pruebas donde testar dichos m etodos. Por ultimo, sugeriremos una medida estad stica que pretende ser capaz de evaluar correctamente la calidad de la estructura de comunidades de una red. Para llevar a cabo dichos objetivos, en primer lugar, se generan una serie de algoritmos capaces de transformar una red en un arbol jer arquico y, a partir de ah , determinar las comunidades que aparecen en ella. Por otro lado, se ha dise~nado un nuevo tipo de benchmarks para testar estos y otros algoritmos de detecci on de comunidades de forma e ciente. Por ultimo, y como parte m as importante de este trabajo, se demuestra que la estructura de comunidades de una red puede ser correctamente evaluada utilizando una medida basada en una distribuci on hipergeom etrica. Por tanto, la maximizaci on de este ndice, llamado Surprise, aparece como la estrategia id onea para obtener la partici on en comunidades optima de una red. Surprise ha mostrado un comportamiento excelente en todos los casos analizados, superando cualitativamente a cualquier otro m etodo anterior. De esta manera, aparece como la mejor medida propuesta para este n y los datos sugieren que podr a ser una estrategia optima para determinar la calidad de la estructura de comunidades en redes complejas. / Aldecoa García, R. (2013). Detección de comunidades en redes complejas [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/31638 / Premios Extraordinarios de tesis doctorales

Cone Beam Computed Tomography (CBCT) is a medical imaging technique routinely employed for diagnosis and treatment of patients with cranio-maxillo-facial defects. CBCT 3D reconstruction and segmentation of bones such as mandible or maxilla are essential procedures in orthodontic treatments. However, CBCT images present characteristics that are not desirable for processing, including low contrast, inhomogeneity, noise, and artifacts. Besides, values assigned to voxels are relative Hounsfield Units (HU), unlike traditional Computed Tomography (CT). Such drawbacks render CBCT segmentation a difficult and time-consuming task, usually performed manually with tools designed for medical image processing. We introduce two interactive two-stage methods for 3D segmentation of CBCT data: i) we first reduce the CBCT image resolution by grouping similar voxels into super-voxels defining a graph representation; ii) next, seeds placed by users guide graph clustering algorithms, splitting the bones into mandible and skull. We have evaluated our segmentation methods intensively by comparing the results against ground truth data of the mandible and the skull, in various scenarios. Results show that our methods produce accurate segmentation and are robust to changes in parameter settings. We also compared our approach with a similar segmentation strategy and we showed that it produces more accurate segmentation of the mandible and skull. In addition, we have evaluated our proposal with CT data of patients with deformed or missing bones. We obtained more accurate segmentation in all cases. As for the efficiency of our implementation, a segmentation of a typical CBCT image of the human head takes about five minutes. Finally, we carried out a usability test with orthodontists. Results have shown that our proposal not only produces accurate segmentation, as it also delivers an effortless and intuitive user interaction. / Tomografia Computadorizada de Feixe Cônico (TCFC) é uma modalidade para obtenção de imagens médicas 3D do crânio usada para diagnóstico e tratamento de pacientes com defeitos crânio-maxilo-faciais. A segmentação tridimensional de ossos como a mandíbula e a maxila são procedimentos essências em tratamentos ortodônticos. No entanto, a TCFC apresenta características não desejáveis para processamento digital como, por exemplo, baixo contraste, inomogeneidade, ruído e artefatos. Além disso, os valores atribuídos aos voxels são unidades de Hounsfield (HU) relativas, diferentemente da Tomografia Computadorizada (TC) tradicional. Esses inconvenientes tornam a segmentação de TCFC uma tarefa difícil e demorada, a qual é normalmente realizada por meio de ferramentas desenvolvidas para processamento digital de imagens médicas. Esta tese introduz dois métodos interativos para a segmentação 3D de TCFC, os quais são divididos em duas etapas: i) redução da resolução da TCFC por meio da agrupamento de voxels em super-voxels, seguida da criação de um grafo no qual os vértices são super-voxels; ii) posicionamento de sementes pelo usuário e segmentação por algoritmos de agrupamento em grafos, o que permite separar os ossos rotulados. Os métodos foram intensamente avaliados por meio da comparação dos resultados com padrão ouro da mandíbula e do crânio, considerando diversos cenários. Os resultados mostraram que os métodos não apenas produzem segmentações precisas, como também são robustos a mudanças nos parâmetros. Foi ainda realizada uma comparação com um trabalho relacionado, gerando melhores resultados tanto na segmentação da mandíbula quanto a do crânio. Além disso, foram avaliadas TCs de pacientes com ossos faltantes e quebrados. A segmentação de uma TCFC é realizada em cerca de 5 minutos. Por fim, foram realizados testes com usuarios ortodontistas. Os resultados mostraram que nossa proposta não apenas produz segmentações precisas, como também é de fácil interação.

Cone Beam Computed Tomography (CBCT) is a medical imaging technique routinely employed for diagnosis and treatment of patients with cranio-maxillo-facial defects. CBCT 3D reconstruction and segmentation of bones such as mandible or maxilla are essential procedures in orthodontic treatments. However, CBCT images present characteristics that are not desirable for processing, including low contrast, inhomogeneity, noise, and artifacts. Besides, values assigned to voxels are relative Hounsfield Units (HU), unlike traditional Computed Tomography (CT). Such drawbacks render CBCT segmentation a difficult and time-consuming task, usually performed manually with tools designed for medical image processing. We introduce two interactive two-stage methods for 3D segmentation of CBCT data: i) we first reduce the CBCT image resolution by grouping similar voxels into super-voxels defining a graph representation; ii) next, seeds placed by users guide graph clustering algorithms, splitting the bones into mandible and skull. We have evaluated our segmentation methods intensively by comparing the results against ground truth data of the mandible and the skull, in various scenarios. Results show that our methods produce accurate segmentation and are robust to changes in parameter settings. We also compared our approach with a similar segmentation strategy and we showed that it produces more accurate segmentation of the mandible and skull. In addition, we have evaluated our proposal with CT data of patients with deformed or missing bones. We obtained more accurate segmentation in all cases. As for the efficiency of our implementation, a segmentation of a typical CBCT image of the human head takes about five minutes. Finally, we carried out a usability test with orthodontists. Results have shown that our proposal not only produces accurate segmentation, as it also delivers an effortless and intuitive user interaction. / Tomografia Computadorizada de Feixe Cônico (TCFC) é uma modalidade para obtenção de imagens médicas 3D do crânio usada para diagnóstico e tratamento de pacientes com defeitos crânio-maxilo-faciais. A segmentação tridimensional de ossos como a mandíbula e a maxila são procedimentos essências em tratamentos ortodônticos. No entanto, a TCFC apresenta características não desejáveis para processamento digital como, por exemplo, baixo contraste, inomogeneidade, ruído e artefatos. Além disso, os valores atribuídos aos voxels são unidades de Hounsfield (HU) relativas, diferentemente da Tomografia Computadorizada (TC) tradicional. Esses inconvenientes tornam a segmentação de TCFC uma tarefa difícil e demorada, a qual é normalmente realizada por meio de ferramentas desenvolvidas para processamento digital de imagens médicas. Esta tese introduz dois métodos interativos para a segmentação 3D de TCFC, os quais são divididos em duas etapas: i) redução da resolução da TCFC por meio da agrupamento de voxels em super-voxels, seguida da criação de um grafo no qual os vértices são super-voxels; ii) posicionamento de sementes pelo usuário e segmentação por algoritmos de agrupamento em grafos, o que permite separar os ossos rotulados. Os métodos foram intensamente avaliados por meio da comparação dos resultados com padrão ouro da mandíbula e do crânio, considerando diversos cenários. Os resultados mostraram que os métodos não apenas produzem segmentações precisas, como também são robustos a mudanças nos parâmetros. Foi ainda realizada uma comparação com um trabalho relacionado, gerando melhores resultados tanto na segmentação da mandíbula quanto a do crânio. Além disso, foram avaliadas TCs de pacientes com ossos faltantes e quebrados. A segmentação de uma TCFC é realizada em cerca de 5 minutos. Por fim, foram realizados testes com usuarios ortodontistas. Os resultados mostraram que nossa proposta não apenas produz segmentações precisas, como também é de fácil interação.

The focus of this study is the development and evaluation of a new partially supervised learning framework. This framework belongs to an emerging field in machine learning that augments unsupervised learning processes with some elements of supervision. It is based on proximity fuzzy clustering, where an active learning process is designed to query for the domain knowledge required in the supervision. Furthermore, the framework is extended to the parametric optimization of the kernel function in the proximity fuzzy clustering algorithm, where the goal is to achieve interesting non-spherical cluster structures through a non-linear mapping. It is demonstrated that the performance of kernel-based clustering is sensitive to the selection of these kernel parameters. Proximity hints procured from domain knowledge are exploited in the partially supervised framework. The theoretic developments with proximity fuzzy clustering are evaluated in several interesting and practical applications. One such problem is the clustering of a set of graphs based on their structural and semantic similarity. The segmentation of music is a second problem for proximity fuzzy clustering, where the aim is to determine the points in time, i.e. boundaries, of significant structural changes in the music. Finally, a time series prediction problem using a fuzzy rule-based system is established and evaluated. The antecedents of the rules are constructed by clustering the time series using proximity information in order to localize the behavior of the rule consequents in the architecture. Evaluation of these efforts on both synthetic and real-world data demonstrate that proximity fuzzy clustering is well suited for a variety of problems. / Digital Signals and Image Processing

In fields across science and engineering, we are increasingly faced with problems where the number of variables or features we need to estimate is much larger than the number of observations. Under such high-dimensional scaling, for any hope of statistically consistent estimation, it becomes vital to leverage any potential structure in the problem such as sparsity, low-rank structure or block sparsity. However, data may deviate significantly from any one such statistical model. The motivation of this thesis is: can we simultaneously leverage more than one such statistical structural model, to obtain consistency in a larger number of problems, and with fewer samples, than can be obtained by single models? Our approach involves combining via simple linear superposition, a technique we term dirty models. The idea is very simple: while any one structure might not capture the data, a superposition of structural classes might. Dirty models thus searches for a parameter that can be decomposed into a number of simpler structures such as (a) sparse plus block-sparse, (b) sparse plus low-rank and (c) low-rank plus block-sparse. In this thesis, we propose dirty model based algorithms for different problems such as multi-task learning, graph clustering and time-series analysis with latent factors. We analyze these algorithms in terms of the number of observations we need to estimate the variables. These algorithms are based on convex optimization and sometimes they are relatively slow. We provide a class of low-complexity greedy algorithms that not only can solve these optimizations faster, but also guarantee the solution. Other than theoretical results, in each case, we provide experimental results to illustrate the power of dirty models. / text

No description available.