Neste trabalho a detecção de novidade é tratada como o problema de identificação de conceitos emergentes em dados que podem ser apresentados em um fluxo contínuo. Considerando a relação intrínseca entre tempo e novidade e os desafios impostos por fluxos de dados, uma nova abordagem é proposta. OLINDDA (OnLIne Novelty and Drift Detection Algorithm) vai além da classficação com uma classe e concentra-se no aprendizado contínuo não-supervisionado de novos conceitos. Tendo aprendido uma descrição inicial de um conceito normal, prossegue à análise de novos dados, tratando-os como um fluxo contínuo em que novos conceitos podem aparecer a qualquer momento. Com o uso de técnicas de agrupamento, OLINDDA pode empregar diversos critérios de validação para avaliar grupos em termos de sua coesão e representatividade. Grupos considerados válidos produzem conceitos que podem sofrer fusão, e cujo conhecimento é continuamente incorporado. A técnica é avaliada experimentalmente com dados artificiais e reais. O módulo de classificação com uma classe é comparado a outras técnicas de detecção de novidade, e a abordagem como um todo é analisada sob vários aspectos por meio da evolução temporal de diversas métricas. Os resultados reforçam a importância da detecção contínua de novos conceitos, assim como as dificuldades e desafios do aprendizado não-supervisionado de novos conceitos em fluxos de dados / In this work novelty detection is treated as the problem of identifying emerging concepts in data that may be presented in a continuous ow. Considering the intrinsic relationship between time and novelty and the challenges imposed by data streams, a novel approach is proposed. OLINDDA, an OnLIne Novelty and Drift Detection Algorithm, goes beyond one-class classification and focuses on the unsupervised continuous learning of novel concepts. Having learned an initial description of a normal concept, it proceeds to the analysis of new data, treating them as a continuous ow where novel concepts may appear at any time. By the use of clustering techniques, OLINDDA may employ several validation criteria to evaluate clusters in terms of their cohesiveness and representativeness. Clusters considered valid produce concepts that may be merged, and whose knowledge is continuously incorporated. The technique is experimentally evaluated with artificial and real data. The one-class classification module is compared to other novelty detection techniques, and the whole approach is analyzed from various aspects through the temporal evolution of several metrics. Results reinforce the importance of continuous detection of novel concepts, as well as the dificulties and challenges of the unsupervised learning of novel concepts in data streams

Uma representação estruturada dos documentos em um formato apropriado para a obtenção automática de conhecimento, sem que haja perda de informações relevantes em relação ao formato originalmente não-estruturado, é um dos passos mais importantes da mineração de textos, pois a qualidade dos resultados obtidos com as abordagens automáticas para obtenção de conhecimento de textos estão fortemente relacionados à qualidade dos atributos utilizados para representar a coleção de documentos. O Modelo de Espaço de Vetores (MEV) é um modelo tradicional para obter uma representação estruturada dos documentos. Neste modelo, cada documento é representado por um vetor de pesos correspondentes aos atributos do texto. O modelo bag-of-words é a abordagem de MEV mais utilizada devido a sua simplicidade e aplicabilidade. Entretanto, o modelo bag-of-words não trata a dependência entre termos e possui alta dimensionalidade. Diversos modelos para representação dos documentos foram propostos na literatura visando capturar a informação de relação entre termos, destacando-se os modelos baseados em frases ou termos compostos, o Modelo de Espaço de Vetores Generalizado (MEVG) e suas extensões, modelos de tópicos não-probabilísticos, como o Latent Semantic Analysis (LSA) ou o Non-negative Matrix Factorization (NMF), e modelos de tópicos probabilísticos, como o Latent Dirichlet Allocation (LDA) e suas extensões. A representação baseada em modelos de tópicos é uma das abordagens mais interessantes uma vez que elas fornece uma estrutura que descreve a coleção de documentos em uma forma que revela sua estrutura interna e as suas inter-relações. As abordagens de extração de tópicos também fornecem uma estratégia de redução da dimensionalidade visando a construção de novas dimensões que representam os principais tópicos ou assuntos identificados na coleção de documentos. Entretanto, a extração é eficiente de informações sobre as relações entre os termos para construção da representação de documentos ainda é um grande desafio de pesquisa. Os modelos para representação de documentos que exploram a correlação entre termos normalmente enfrentam um grande desafio para manter um bom equilíbrio entre (i) a quantidade de dimensões obtidas, (ii) o esforço computacional e (iii) a interpretabilidade das novas dimensões obtidas. Assim,é proposto neste trabalho o modelo para representação de documentos Latent Association Rule Cluster based Model (LARCM). Este é um modelo de extração de tópicos não-probabilístico que explora o agrupamento de regras de associação para construir uma representação da coleção de documentos com dimensionalidade reduzida tal que as novas dimensões são extraídas a partir das informações sobre as relações entre os termos. No modelo proposto, as regras de associação são extraídas para cada documento para obter termos correlacionados que formam expressões multi-palavras. Essas relações entre os termos formam o contexto local da relação entre termos. Em seguida, aplica-se um processo de agrupamento em todas as regras de associação para formar o contexto geral das relações entre os termos, e cada grupo de regras de associação obtido formará um tópico, ou seja, uma dimensão da representação. Também é proposto neste trabalho uma metodologia de avaliação que permite selecionar modelos que maximizam tanto os resultados na tarefa de classificação de textos quanto os resultados de interpretabilidade dos tópicos obtidos. O modelo LARCM foi comparado com o modelo LDA tradicional e o modelo LDA utilizando uma representação que inclui termos compostos (bag-of-related-words). Os resultados dos experimentos indicam que o modelo LARCM produz uma representação para os documentos que contribui significativamente para a melhora dos resultados na tarefa de classificação de textos, mantendo também uma boa interpretabilidade dos tópicos obtidos. O modelo LARCM também apresentou ótimo desempenho quando utilizado para extração de informação de contexto para aplicação em sistemas de recomendação sensíveis ao contexto. / A structured representation of documents in an appropriate format for the automatic knowledge extraction without loss of relevant information is one of the most important steps of text mining, since the quality of the results obtained with automatic approaches for the text knowledge extraction is strongly related to the quality of the selected attributes to represent the collection of documents. The Vector Space model (VSM) is a traditional structured representation of documents. In this model, each document is represented as a vector of weights that corresponds to the features of the document. The bag-of-words model is the most popular VSM approach because of its simplicity and general applicability. However, the bag-of-words model does not include dependencies of the terms and has a high dimensionality. Several models for document representation have been proposed in the literature in order to capture the dependence among the terms, especially models based on phrases or compound terms, the Generalized Vector Space Model (GVSM) and their extensions, non-probabilistic topic models as Latent Semantic Analysis (LSA) or Non-negative Matrix Factorization (NMF) and still probabilistic topic models as the Latent Dirichlet Allocation (LDA) and their extensions. The topic model representation is one of the most interesting approaches since it provides a structure that describes the collection of documents in a way that reveals their internal structure and their interrelationships. Also, this approach provides a dimensionality reduction strategy aiming to built new dimensions that represent the main topics or ideas of the document collection. However, the efficient extraction of information about the relations of terms for document representation is still a major research challenge nowadays. The document representation models that explore correlated terms usually face a great challenge of keeping a good balance among the (i) number of extracted features, (ii) the computational performance and (iii) the interpretability of new features. In this way, we proposed the Latent Association Rule Cluster based Model (LARCM). The LARCM is a non-probabilistic topic model that explores association rule clustering to build a document representation with low dimensionality in a way that each dimension is composed by information about the relations among the terms. In the proposed approach, the association rules are built for each document to extract the correlated terms that will compose the multi-word expressions. These relations among the terms are the local context of relations. Then, a clustering process is applied for all association rules to discover the general context of the relations, and each obtained cluster is an extracted topic or a dimension of the new document representation. This work also proposes in this work an evaluation methodology to select topic models that maximize the results in the text classification task as much as the interpretability of the obtained topics. The LARCM model was compared against both the traditional LDA model and the LDA model using a document representation that includes multi-word expressions (bag-of-related-words). The experimental results indicate that LARCM provides an document representation that improves the results in the text classification task and even retains a good interpretability of the extract topics. The LARCM model also achieved great results as a method to extract contextual information for context-aware recommender systems.

Diversos métodos têm sido desenvolvidos para a organização da crescente quantidade de documentos textuais. Esses métodos frequentemente fazem uso de algoritmos de agrupamento para organizar documentos que referem-se a um mesmo assunto em um mesmo grupo, supondo que conteúdos de documentos de um mesmo grupo são similares. Porém, existe a possibilidade de que documentos pertencentes a grupos distintos também apresentem características semelhantes. Considerando esta situação, há a necessidade de desenvolver métodos que possibilitem a organização flexível de documentos, ou seja, métodos que possibilitem que documentos sejam organizados em diferentes grupos com diferentes graus de compatibilidade. O agrupamento fuzzy de documentos textuais apresenta-se como uma técnica adequada para este tipo de organização, uma vez que algoritmos de agrupamento fuzzy consideram que um mesmo documento pode ser compatível com mais de um grupo. Embora tem-se desenvolvido algoritmos de agrupamento fuzzy que possibilitam a organização flexível de documentos, tal organização é avaliada em termos do desempenho do agrupamento de documentos. No entanto, considerando que grupos de documentos devem possuir descritores que identifiquem adequadamente os tópicos representados pelos mesmos, de maneira geral os descritores de grupos tem sido extraídos utilizando alguma heurística sobre um conjunto pequeno de documentos, realizando assim, uma avaliação simples sobre o significado dos grupos extraídos. No entanto, uma apropriada extração e avaliação de descritores de grupos é importante porque os mesmos são termos representantes da coleção que identificam os tópicos abordados nos documentos. Portanto, em aplicações em que o agrupamento fuzzy é utilizado para a organização flexível de documentos, uma descrição apropriada dos grupos obtidos é tão importante quanto um bom agrupamento, uma vez que, neste tipo de agrupamento, um mesmo descritor pode indicar o conteúdo de mais de um grupo. Essa necessidade motivou esta tese, cujo objetivo foi investigar e desenvolver métodos para a extração de descritores de grupos fuzzy para a organização flexível de documentos. Para cumprir esse objetivo desenvolveu se: i) o método SoftO-FDCL (Soft Organization - Fuzzy Description Comes Last ), pelo qual descritores de grupos fuzzy at são extraídos após o processo de agrupamento fuzzy, visando identicar tópicos da organização flexível de documentos independentemente do algoritmo de agrupamento fuzzy utilizado; ii) o método SoftO-wFDCL ( Soft Organization - weighted Fuzzy Description Comes Last ), pelo qual descritores de grupos fuzzy at também são extraídos após o processo de agrupamento fuzzy utilizando o grau de pertinência dos documentos em cada grupo, obtidos do agrupamento fuzzy, como fator de ponderação dos termos candidatos a descritores; iii) o método HSoftO-FDCL (Hierarchical Soft Organization - Fuzzy Description Comes Last ), pelo qual descritores de grupos fuzzy hierárquicos são extraídos após o processo de agrupamento hierárquico fuzzy, identificando tópicos da organização hierárquica flexível de documentos. Adicionalmente, apresenta-se nesta tese uma aplicação do método SoftO-FDCL no contexto do programa de educação médica continuada canadense, reforçando a utilidade e aplicabilidade da organização flexível de documentos / Several methods have been developed to organize the growing number of textual documents. Such methods frequently use clustering algorithms to organize documents with similar topics into clusters. However, there are situations when documents of dffierent clusters can also have similar characteristics. In order to overcome this drawback, it is necessary to develop methods that permit a soft document organization, i.e., clustering documents into different clusters according to different compatibility degrees. Among the techniques that we can use to develop methods in this sense, we highlight fuzzy clustering algorithms (FCA). By using FCA, one of the most important steps is the evaluation of the yield organization, which is performed considering that all analyzed topics are adequately identified by cluster descriptors. In general, cluster descriptors are extracted using some heuristic over a small number of documents. The adequate extraction and evaluation of cluster descriptors is important because they are terms that represent the collection and identify the topics of the documents. Therefore, an adequate description of the obtained clusters is as important as a good clustering, since the same descriptor might identify one or more clusters. Hence, the development of methods to extract descriptors from fuzzy clusters obtained for soft organization of documents motivated this thesis. Aiming at investigating such methods, we developed: i) the SoftO-FDCL (Soft Organization - Fuzzy Description Comes Last) method, in which descriptors of fuzzy clusters are extracted after clustering documents, identifying topics regardless the adopted fuzzy clustering algorithm; ii) the SoftO-wFDCL (Soft Organization - weighted Fuzzy Description Comes Last) method, in which descriptors of fuzzy clusters are also extracted after the fuzzy clustering process using the membership degrees of the documents as a weighted factor for the candidate descriptors; iii) the HSoftO-FDCL (Hierarchical Soft Organization - Fuzzy Description Comes Last) method, in which descriptors of hierarchical fuzzy clusters are extracted after the hierarchical fuzzy clustering process, identifying topics by means of a soft hierarchical organization of documents. Besides presenting these new methods, this thesis also discusses the application of the SoftO-FDCL method on documents produced by the Canadian continuing medical education program, presenting the utility and applicability of the soft organization of documents in real-world scenario

Métodos de agrupamento hierárquico de textos são muito úteis para analisar o conhecimento embutido em coleções textuais, organizando os documentos textuais em grupos e subgrupos para facilitar a exploração do conhecimento em diversos níveis de granularidade. Tais métodos pertencem à área de aprendizado não supervisionado de máquina, uma que vez obtêm modelos de agrupamento apenas pela observação de regularidades existentes na coleção textual, sem supervisão humana. Os métodos tradicionais de agrupamento assumem que a coleção textual é representada apenas pela informação técnica, ou seja, palavras e frases extraídas diretamente dos textos. Por outro lado, em muitas tarefas de agrupamento existe conhecimento adicional e valioso a respeito dos dados, geralmente extraído por um processo avançado com apoio de usuários especialistas do domínio do problema. Devido ao alto custo para obtenção desses dados, esta informação adicional é definida como privilegiada e usualmente está disponível para representar apenas um subconjunto dos documentos textuais. Recentemente, um novo paradigma de aprendizado de máquina denominado LUPI (Learning Using Privileged Information) foi proposto por Vapnik para incorporar informação privilegiada em métodos aprendizado supervisionado. Neste trabalho de doutorado, o paradigma LUPI foi estendido para aprendizado não supervisionado, em especial, para agrupamento hierárquico de textos. Foram propostas e avaliadas abordagens para lidar com diferentes desafios existentes em tarefas de agrupamento, envolvendo a extração e estruturação da informação privilegiada e seu uso para refinar ou corrigir modelos de agrupamento. As abordagens propostas se mostraram eficazes em (i) consenso de agrupamentos, permitindo combinar diferentes representações e soluções de agrupamento; (ii) aprendizado de métricas, em que medidas de proximidades mais robustas foram obtidas com base na informação privilegiada; e (iii) seleção de modelos, em que a informação privilegiada é explorada para identificar relevantes estruturas de agrupamento hierárquico. Todas as abordagens apresentadas foram investigadas em um cenário de agrupamento incremental, permitindo seu uso em aplicações práticas caracterizadas pela necessidade de eficiência computacional e alta frequência de publicação de novo conhecimento textual. / Hierarchical text clustering methods are very useful to analyze the implicit knowledge in textual collections, enabling the organization of textual documents into clusters and subclusters to facilitate the knowledge browsing at various levels of granularity. Such methods are classified as unsupervised machine learning, since the clustering models are obtained only by observing regularities of textual data without human supervision. Traditional clustering methods assume that the text collection is represented only by the technical information, i.e., words and phrases extracted directly from the texts. On the other hand, in many text clustering tasks there is an additional and valuable knowledge about the problem domain, usually extracted by an advanced process with support of the domain experts. Due to the high cost of obtaining such expert knowledge, this additional information is defined as privileged and is usually available to represent only a subset of the textual documents. Recently, a new machine learning paradigm called LUPI (Learning Using Privileged Information) was proposed by Vapnik to incorporate privileged information into supervised learning methods. In this thesis, the LUPI paradigm was extended to unsupervised learning setting, in particular for hierarchical text clustering. We propose and evaluate approaches to deal with different challenges for clustering tasks, involving the extraction and structuring of privileged information and using this additional information to refine or correct clustering models. The proposed approaches were effective in (i) consensus clustering, allowing to combine different clustering solutions and textual representations; (ii) metric learning, in which more robust proximity measures are obtained from privileged information; and (iii) model selection, in which the privileged information is exploited to identify the relevant structures of hierarchical clustering. All the approaches presented in this thesis were investigated in an incremental clustering scenario, allowing its use in practical applications that require computational efficiency as well as deal with high frequency of publication of new textual knowledge.

Técnicas de agrupamento de dados usualmente assumem que o conjunto de dados é de tamanho fixo e pode ser alocado na memória. Neste contexto, um desafio consiste em aplicar técnicas de agrupamento em bases de dados de tamanho ilimitado, com dados gerados continuamente e em ambientes dinâmicos. Dados gerados nessas condições originam o que se convencionou chamar de Fluxo Contínuo de Dados (FCD). Em aplicações de FCD, operações de acesso aos dados são restritas a apenas uma leitura ou a um pequeno número de acessos aos dados, com limitações de memória e de tempo de processamento. Além disso, a distribuição dos dados gerados por essas fontes pode ser não estacionária, ou seja, podem ocorrer mudanças ao longo do tempo, denominadas de mudanças de conceito. Nesse sentido, algumas técnicas de agrupamento em FCD foram propostas na literatura. Muitas dessas técnicas são baseadas no algoritmo das k-Médias. Uma das limitações do algoritmo das k-Médias consiste na definição prévia do número de grupos. Ao se assumir que o número de grupos é desconhecido a priori e que deveria ser estimado a partir dos dados, percorrer o grande espaço de soluções possíveis (tanto em relação ao número de grupos, k, quanto em relação às partições possíveis para um determinado k) torna desafiadora a tarefa de agrupamento de dados - ainda mais sob a limitação de tempo e armazenamento imposta em aplicações de FCD. Neste contexto, essa tese tem como principais contribuições: (i) adaptar algoritmos que têm sido usados com sucesso em aplicações de Fluxo Contínuo de Dados (FCD) nas quais k é conhecido para cenários em que se deseja estimar o número de grupos; (ii) propor novos algoritmos para agrupamento que estimem k automaticamente a partir do FCD; (iii) avaliar sistematicamente, e de maneira quantitativa, os algoritmos propostos de acordo com as características específicas dos cenários de FCD. Foram desenvolvidos 14 algoritmos de agrupamento para FCD capazes de estimar o número de grupos a partir dos dados. Tais algoritmos foram avaliados em seis bases de dados artificiais e duas bases de dados reais amplamente utilizada na literatura. Os algoritmos desenvolvidos podem auxiliar em diversas áreas da Mineração em FCD. Os algoritmos evolutivos desenvolvidos mostraram a melhor relação de custo-benefício entre eficiência computacional e qualidade das partições obtidas. / Several algorithms for clustering data streams based on k-Means have been proposed in the literature. However, most of them assume that the number of clusters, k, is known a priori by the user and can be kept fixed throughout the data analysis process. Besides the dificulty in choosing k, data stream clustering imposes several challenges to be dealt with, such as addressing non-stationary, unbounded data that arrives in an online fashion. In data stream applications, the dataset must be accessed in order and that can be read only once or a small number of times. In this context, the main contributions of this thesis are: (i) adapt algorithms that have been used successfully in data stream applications where k is known to be able to estimate the number of clusters from data; (ii) propose new algorithms for clustering to estimate k automatically from the data stream; (iii) evaluate the proposed algorithms according to diferent scenarios. Fourteen clustering data stream algorithms were developed which are able to estimate the number of clusters from data. They were evaluated in six artificial datasets and two real-world datasets widely used in the literature. The developed algorithms are useful for several data mining tasks. The developed evolutionary algorithms have shown the best trade-off between computational efficiency and data partition quality.

Diversas áreas de pesquisa são dedicadas à compreensão de fenômenos que exigem a coleta ininterrupta de sequências de amostras, denominadas fluxos de dados. Esses fenômenos frequentemente apresentam comportamento variável e são estudados por meio de indução não supervisionada baseada em agrupamento de dados. Atualmente, o processo de agrupamento tem exibido sérias limitações em sua aplicação a fluxos de dados, devido às exigências impostas pelas variações comportamentais e pelo modo de coleta de dados. Embora tem-se desenvolvido algoritmos eficientes para agrupar fluxos de dados, há a necessidade de estudos sobre a influência de variações comportamentais nos parâmetros de algoritmos (e.g., taxas de aprendizado e limiares de proximidade), as quais interferem diretamente na compreensão de fenômenos. Essa lacuna motivou esta tese, cujo objetivo foi a proposta de uma abordagem para a adaptação do viés indutivo de algoritmos de agrupamento de fluxos de dados de acordo com variações comportamentais dos fenômenos em estudo. Para cumprir esse objetivo projetou-se: i) uma abordagem baseada em uma nova arquitetura de rede neural artificial que permite avaliação de comportamento de fenômenos por meio da estimação de cadeias de Markov e entropia de Shannon; ii) uma abordagem para adaptar parâmetros de algoritmos de agrupamento tradicional de acordo com variações comportamentais em blocos sequenciais de dados; e iii) uma abordagem para adaptar parâmetros de agrupamento de acordo com a contínua avaliação da estabilidade de dados. Adicionalmente, apresenta-se nesta tese uma taxonomia de técnicas de detecção de variação comportamental de fenômenos e uma formalização para o problema de agrupamento de fluxos de dados / Several research fields have described phenomena that produce endless sequences of samples, referred to as data streams. These phenomena usually present behavior variation and are studied by means of unsupervised induction based on data clustering. In order to cope with the characteristics of data streams, researchers have designed clustering algorithms with low time and space complexity requirements. However, predefined and static parameters (thresholds, number of clusters and learning rates) found in current algorithms still limit the application of clustering to data streams. This limitation motivated this thesis, which proposes a continuous approach to evaluate behavior variations and adapt algorithm inductive bias by changing its parameters. The main contribution of this thesis is the proposal of three approaches to adapt induction bias: i) an approach based on the design of an adaptive artificial self-organizing neural network architecture that enables behavior evaluation by means of Markov chain and Shannon entropy estimations; ii) an approach to adapt traditional data clustering algorithms according to behavior variations in sequences of data chunks; and iii) an approach based on the proposed neural network architecture to continuously adapt parameters by means of the evaluation of data stability. Additionally, in order to analyze the essential characteristics of data streams, this thesis presents a formalization for the problem of data stream clustering and a taxonomy on approaches to detect behavior variations

A grande quantidade de dados gerada em diversas áreas do conhecimento cria a necessidade do desenvolvimento de técnicas de mineração de dados cada vez mais eficientes e eficazes. Técnicas de agrupamento têm sido utilizadas com sucesso em várias áreas, especialmente naquelas em que não há conhecimento prévio sobre a organização dos dados. Contudo, a utilização de diferentes algoritmos de agrupamento, ou variações de um mesmo algoritmo, pode gerar uma ampla variedade de resultados. Tamanha variedade cria a necessidade de métodos para avaliar e selecionar bons resultados. Uma forma de avaliar esses resultados consiste em utilizar índices de validação de agrupamentos. Entretanto, uma grande diversidade de índices de validação foi proposta na literatura, o que torna a escolha de um único índice de validação uma tarefa penosa caso os desempenhos dos índices comparados sejam desconhecidos para a classe de problemas de interesse. Com a finalidade de obter um consenso entre resultados, é possível combinar um conjunto de agrupamentos ou índices de validação em uma única solução final. Combinações de agrupamentos (clustering ensembles) foram bem sucedidas em obter soluções robustas a variações no cenário de aplicação, o que faz do uso de comitês de agrupamentos uma alternativa interessante para encontrar soluções de qualidade razoável, segundo diferentes índices de validação. Adicionalmente, utilizar uma combinação de índices de validação pode tornar a avaliação de agrupamentos mais completa, uma vez que uma maioria dos índices combinados pode compensar o fraco desempenho do restante. Em alguns casos, não é possível lidar com um único conjunto de dados centralizado, por razões físicas ou questões de privacidade, o que gera a necessidade de distribuir o processo de mineração. Combinações de agrupamentos também podem ser estendidas para problemas de agrupamento de dados distribuídos, uma vez que informações sobre os dados, oriundas de diferentes fontes, podem ser combinadas em uma única solução global. O principal objetivo desse trabalho consiste em investigar técnicas de combinação de agrupamentos e de índices de validação aplicadas na seleção de agrupamentos para combinação e na mineração distribuída de dados. Adicionalmente, algoritmos evolutivos de agrupamento são estudados com a finalidade de selecionar soluções de qualidade dentre os resultados obtidos. As técnicas desenvolvidas possuem complexidade computacional reduzida e escalabilidade, o que permite sua aplicação em grandes conjuntos de dados ou cenários em que os dados encontram-se distribuídos / The large amount of data resulting from different areas of knowledge creates the need for development of data mining techniques increasingly efficient and effective. Clustering techniques have been successfully applied to several areas, especially when there is no prior knowledge about the data organization. Nevertheless, the use of different clustering algorithms, or variations of the same algorithm, can generate a wide variety of results, what raises the need to create methods to assess and select good results. One way to evaluate these results consists on using cluster validation indexes. However, a wide variety of validation indexes was proposed in the literature, which can make choosing a single index challenging if the performance of the compared indexes is unknown for the application scenario. In order to obtain a consensus among different options, a set of clustering results or validation indexes can be combined into a single final solution. Clustering ensembles successfully obtained results robust to variations in the application scenario, which makes them an attractive alternative to find solutions of reasonable quality, according to different validation indexes. Moreover, using a combination of validation indexes can promote a more powerful evaluation, as the majority of the combined indexes can compensate the poor performance of individual indexes. In some cases, it is not possible to work with a single centralized data set, for physical reasons or privacy concerns, which creates the need to distribute the mining process. Clustering ensembles can be extended to distributed data mining problems, since information about the data from distributed sources can be combined into a single global solution. The main objective of this research resides in investigating combination techniques for validation indexes and clustering results applied to clustering ensemble selection and distributed clustering. Additionally, evolutionary clustering algorithms are studied to select quality solutions among the obtained results. The techniques developed have scalability and reduced computational complexity, allowing their usage in large data sets or scenarios with distributed data

O operador de agrupamento e as funções de agregação são as principais ferramentas utilizadas para sumarizar dados em um Sistema de Gerenciamento de Base de Dados Relacionais (SGBDR). O operador de agrupamento funciona criando partições nos dados utilizando comparações por identidade, e permite que sejam aplicadas funções de agregação que retornam um único valor representando o grupo como um todo. Entretanto, para dados métricos, agrupamento utilizando identidade tem pouca utilidade. Neste caso, adotar o conceito de similaridade é frequentemente uma abordagem mais promissora. A literatura apresenta alguns operadores que podem agrupar os dados utilizando similaridade. Todos eles utilizam um limiar de valor de distância para atribuir os elementos aos grupos. No entanto, estes operadores não obtêm resultados satisfatórios quando a distribuição dos dados apresenta variações significativas na densidade de objetos em diferentes regiões do espaço. Para alcançar melhores resultados nestas situações, propusemos um novo operador que atribui os grupos utilizando uma eleição envolvendo grupos já atribuídos. Também propusemos generalizações, para os operadores existentes e propostos, para trabalhar com uma quantidade de vizinhos mais próximos e aproximação dos vizinhos mais próximos ao invés de um limiar de distância. Para possibilitar a inclusão destes operadores em SGBDR, propusemos uma extensão à Structured Query Language (SQL) e novas funções de agregação. Implementamos estes operadores em nosso framework em C++ usando a biblioteca Arboretum. Para avaliar os métodos propostos, analisamos tanto qualidade dos resultados quanto tempo de execução, utilizando conjuntos de dados reais e sintéticos. Os operadores propostos alcançaram melhores resultados quanto à qualidade de resultados, e mantiveram os tempos de execução similares. Os operadores que utilizam aproximação aos vizinhos mais próximos produziram resultados de qualidade similar quando comparados aos operadores que utilizando os vizinhos mais próximos, podendo ser executados em menor tempo que estes. / The grouping operator and aggregation functions are the primary tools used to summarize data inside a Relational Database Management Systems (RDBMS). The grouping operator works creating partitions in data using identity comparisons, and allow applying aggregation functions that return a single value that represent the entire group. However, for metric data, grouping by identity is seldom useful. In this case, adopting the concept of the similarity is often a better approach. The literature presents few operators that can group data using similarity. All of them use a distance threshold value to assign the elements in groups. However, these operators do not achieve satisfactory results when the data distribution present a significant variation in the density of objects in different regions of the space. To achieve better results in these situations, we have proposed a novel operator that assign groups using an election involving already assigned groups. We also proposed generalizations to existing and proposed operators to work with an amount of nearest neighbors and approximate neighbors instead of a distance threshold. To support these operators in RDBMS, we propose an extension to Structured Query Language (SQL) and new aggregation functions. Our proposed algorithms can run the proposed and existing operators. We implemented these operators in our framework in C++ using Arboretum library. To evaluate the proposed methods, we assess both results quality and the execution time, using both real and synthetic datasets. The proposed operators achieved better results comparing the quality and maintained similar executing time. The operators that use the approximate nearest neighbors produced similar quality results comparing with the operators that use the exact neighbors and can execute faster than that.

Nas últimas décadas, a quantidade de informações armazenadas no formato digital tem crescido de forma exponencial, levando à necessidade cada vez maior de produção de ferramentas computacionais que auxiliem na geração do conhecimento a partir desses dados. A área de Aprendizado de Máquina fornece diversas técnicas capazes de identificar padrões nesses conjuntos de dados. Dentro dessas técnicas, este trabalho destaca o Aprendizado de Máquina Não Supervisionado onde o objetivo é classificar as entidades em clusters (grupos) mutuamente exclusivos baseados na similaridade entre as instâncias. Os clusters não são pré-definidos e daí o elemento não supervisionado. Organizar esses dados em clusters que façam sentido é uma das maneiras mais fundamentais de entendimento e aprendizado. A análise de clusters é o estudo dos métodos para agrupamento e se divide entre hierárquico e particional. A classificação hierárquica é uma sequência encadeada de partições enquanto que na particional há somente uma partição. O interesse deste trabalho são as técnicas baseadas em uma caminhada determinística parcialmente auto repulsiva conhecida como caminhada do turista. Partindo da hipótese de que é possível utilizar a caminhada do turista como uma técnica de Aprendizado de Máquina Não Supervisionado, foi implementado um algoritmo hierárquico baseado na caminhada do turista proposto por Campiteli et al. (2006). Foi avaliado, através de diferentes conjuntos de imagens médicas, como essa técnica se compara com técnicas hierárquicas tradicionais. Também é proposto um novo algoritmo de Aprendizado de Máquina Não Supervisionado particional baseado na caminhada do turista, chamado de Tourist Walk Partitional Clustering (TWPC). Os resultados mostraram que a técnica hierárquica baseada na caminhada do turista é capaz de identificar clusters em conjuntos de imagens médicas através de uma árvore que não impõe uma estrutura binária, com um número menor de hierarquias e uma invariabilidade à escala dos dados, resultando em uma estrutura mais organizada. Mesmo que a árvore não seja diretamente baseada nas distâncias dos dados, mas em um ranking de vizinhos, ela ainda preserva uma correlação entre suas distâncias cofenéticas e as distâncias reais entre os dados. O método particional proposto TWPC foi capaz de encontrar, de forma eficiente, formas arbitrárias de clusters com variações inter-cluster e intra-cluster. Além disso o algoritmo tem como vantagens: ser determinístico; funcionar com interações locais, sem a necessidade de conhecimento a priori de todos os itens do conjunto; incorporar o conceito de ruído e outlier; e funcionar com um ranking de vizinhos, que pode ser construído através de qualquer medida. / In the last decades, the amount of data stored in digital format has grown exponentially, leading to the increasing need to produce computational tools that help generate knowledge from these data. The Machine Learning field provides several techniques capable of identifying patterns in these data sets. Within these techniques we highlight the Unsupervised Machine Learning where the objective is to classify the entities in mutually exclusive clusters based on the similarity between the instances. Clusters are not predefined and hence the unsupervised element. Organizing this data into clusters that make sense is one of the most fundamental ways of understanding and learning. Cluster analysis is the study of methods for clustering and is divided between hierarchical and partitional. A hierarchical clustering is a sequence of partitions whereas in the partitional clustering there is only one partition. Here we are interested in techniques based on a deterministic partially self-avoiding walk, known as tourist walk. Based on the hypothesis that it is possible to use the tourist walk as an unsupervised machine learning technique, we have implemented a hierarchical algorithm based on the tourist walk proposed by Campiteli et al. (2006). We evaluate this algorithm using different sets of medical images and compare it with traditional hierarchical techniques. We also propose a new algorithm for partitional clustering based on the tourist talk, called Tourist Walk Partitional Clustering (TWPC). The results showed that the hierarchical technique based on the tourist walk is able to identify clusters in sets of medical images through a tree that does not impose a binary structure, with a smaller number of hierarchies and is invariable to scale transformation, resulting in a more organized structure. Even though the tree is not directly based on the distances of the data but on a ranking of neighbors, it still preserves a correlation between its cophenetic distances and the actual distances between the data. The proposed partitional clustering method TWPC was able to find, in an efficient way, arbitrary shapes of clusters with inter-cluster and intra-cluster variations. In addition, the algorithm has the following advantages: it is deterministic; it operates based on local interactions, without the need for a priori knowledge of all the items in the set; it is capable of incorporate the concept of noise and outlier; and work with a ranking of neighbors, which can be built through any measure.

Submitted by Kilvya Braga (kilvyabraga@hotmail.com) on 2018-05-16T14:43:46Z No. of bitstreams: 1 YURI ALMEIDA LACERDA - TESE (PPGCC) 2017.pdf: 28353805 bytes, checksum: 0d8453f39b64823b7308c81cc7731524 (MD5) / Made available in DSpace on 2018-05-16T14:43:46Z (GMT). No. of bitstreams: 1 YURI ALMEIDA LACERDA - TESE (PPGCC) 2017.pdf: 28353805 bytes, checksum: 0d8453f39b64823b7308c81cc7731524 (MD5) Previous issue date: 2017 / Capes / A descoberta de conhecimento a partir de grandes repositórios online de fotografias tem sido uma área de pesquisa bastante ativa nos últimos anos. Isso se deve principalmente a três fatores: incorporação de câmeras digitais e sensores de geolocalização aos dispositivos móveis; avanços na conectividade com a Internet; e evolução das redes sociais. As fotografias armazenadas nesses repositórios possuem metadados contextuais que podem ser utilizados em aplicações de descoberta de conhecimento, tais como: detecção de pontos de interesse (POIs); geração de roteiros de viagens; e organização automática de fotografias. A maioria das abordagens para detecção de POIs parte do princípio que as áreas geográficas onde uma grande quantidade de pessoas capturou fotografias indica a existência de um ponto de interesse. Porém, em muitos casos, os POIs estão localizados a uma certa distância desse local na orientação em que a câmera estava direcionada, e não no ponto exato da captura da fotografia. A maioria das técnicas propostas na literatura não consideram o uso da orientação no processo de detecção de pontos de interesses. Dessa forma, este trabalho propõe novos algoritmos e técnicas para detecção de pontos de interesse em cidades turísticas a partir de coleções de fotografias orientadas e georreferenciadas explorando de diversas formas a orientação geográfica. Esta pesquisa comprovou a importância do uso da orientação nos novos algoritmos voltados para detecção de pontos de interesses. Os experimentos, utilizando uma base de dados real de grandes cidades, demonstraram que os algoritmos considerando a orientação conseguem, em alguns cenários, superar os que não a consideram. Também foram propostas novas métricas de avaliação e uma ferramenta para auxiliar as atividades de descoberta de conhecimento baseada em grandes massas de fotografias. / The knowledge discovery from huge photo repositories has been a very active area of research in the last years. This is due to three facts: the incorporation of digital cameras and geolocation sensors in mobile devices; the advances in Internet connectivity; and the evolution of social networks. The photos stored on those repositories have contextual metadata. Those metadata could be used for many applications of knowledge discovering, such as: Point of Interest (POI) detection; generating of tourist guides; and automatic photo organization. Most approaches for POI detection assume that geographic areas with high density of photos indicate the existence of a point of interest in that area. However, in many cases, the POIs are located in a certain distance of that position in direction where camera was aiming, and not in the exact point of photo shooting. Most of related work do not consider the use of orientation in the process of POI detection. In this way, we propose a set of algorithms and techniques for POI discovery in touristic cities using geotagged and oriented photos collection exploring the geographic orientation in different ways. This research has proven the importance of the usage of orientation in the new algorithms for POI detection. In the experiments with collections related to big cities, the algorithms considering orientation, in several scenarios, have beaten those that do not consider. Also, new metrics of evaluation have been proposed and a new framework to assist all the tasks for knowledge discovery based on huge photo collections.