With the wide deployment of data intensive Internet applications and continued advances in sensing technology and biotechnology, large multidimensional datasets, possibly containing privacy-conscious information have been emerging. Mining such datasets has become increasingly common in business integration, large-scale scientific data analysis, and national security. The proposed research aims at exploring the geometric properties of the multidimensional datasets utilized in statistical learning and data mining, and providing novel techniques and frameworks for mining very large datasets while protecting the desired data privacy. The first main contribution of this research is the development of iVIBRATE interactive visualization-based approach for clustering very large datasets. The iVIBRATE framework uniquely addresses the challenges in handling irregularly shaped clusters, domain-specific cluster definition, and cluster-labeling of the data on disk. It consists of the VISTA visual cluster rendering subsystem, and the Adaptive ClusterMap Labeling subsystem. The second main contribution is the development of ``Best K Plot'(BKPlot) method for determining the critical clustering structures in multidimensional categorical data. The BKPlot method uniquely addresses two challenges in clustering categorical data: How to determine the number of clusters (the best K) and how to identify the existence of significant clustering structures. The method consists of the basic theory, the sample BKPlot theory for large datasets, and the testing method for identifying no-cluster datasets. The third main contribution of this research is the development of the theory of geometric data perturbation and its application in privacy-preserving data classification involving single party or multiparty collaboration. The key of geometric data perturbation is to find a good randomly generated rotation matrix and an appropriate noise component that provides satisfactory balance between privacy guarantee and data quality, considering possible inference attacks. When geometric perturbation is applied to collaborative multiparty data classification, it is challenging to unify the different geometric perturbations used by different parties. We study three protocols under the data-mining-service oriented framework for unifying the perturbations: 1) the threshold-satisfied voting protocol, 2) the space adaptation protocol, and 3) the space adaptation protocol with a trusted party. The tradeoffs between the privacy guarantee, the model accuracy and the cost are studied for the protocols.

Existem bases para as quais os dados são naturalmente representados por mais de uma visão. Por exemplo, imagens podem ser descritas por atributos de cores, textura e forma. Proteínas podem ser caracterizadas pela sequência de aminoácidos e pela representação tridimensional. A unificação das diferentes visões de uma base de dados pode ser problemática porque elas podem não ser comparáveis entre si ou podem apresentar diferentes graus de importância. Esses graus de importância podem, inclusive, se manifestar de maneira local, de acordo com a subestrutura dos dados em questão. Isso motivou o surgimento de algoritmos de agrupamento de dados capazes de lidar com bases multi-representadas (i.e., que possuem mais de uma visão dos dados), como o algoritmo SCAD. Esse algoritmo se mostrou promissor em experimentos relatados na literatura, mas possui problemas críticos identificados neste trabalho que o impedem de funcionar em determinados cenários. Tais problemas foram solucionados por meio da proposição de uma nova versão do algoritmo, denominada ASCAD, fundamentada em provas formais sobre a sua convergência. Foram desenvolvidas versões relacionais do algoritmo ASCAD, capazes de lidar com bases descritas apenas por relações de proximidade entre os objetos. Foi desenvolvido também um índice de validação interna e relativa de agrupamento voltado para dados multi-representados. A avaliação de agrupamento possibilístico e de bi-agrupamento por meio da comparação entre solução encontrada e solução de referência (validação externa) também foi explorada. Algoritmos de bi-agrupamento têm ganhado um interesse crescente da comunidade de análise de expressão gênica. No entanto, pouco se conhece do comportamento e das propriedades das medidas voltadas para validação externa de bi-agrupamento, o que motivou uma análise teórica e empírica dessas medidas. Essa análise mostrou que a maioria das medidas de biagrupamento possui problemas críticos e destacou duas delas como sendo as mais promissoras. Foram inclusas nessa análise três medidas de agrupamento particional não exclusivo, cujo uso na comparação de bi-agrupamentos é possível por meio de uma nova abordagem de avaliação de bi-agrupamento proposta nesta tese. Agrupamento particional não exclusivo faz parte de um domínio mais geral de soluções, i.e., o domínio dos agrupamentos possibilísticos. Observou-se algumas falhas conceituais importantes das medidas de agrupamento possibilístico, o que motivou o desenvolvimento de novas medidas e de uma análise empírica e conceitual envolvendo 34 medidas. Uma das medidas propostas se destacou como sendo a única que apresentou avaliações imparciais com relação ao número de grupos, o valor máximo de similaridade ao comparar a solução ideal encontrada com a solução de referência e avaliações sensíveis às diferenças das soluções em todos os cenários considerados / There are data sets for which the instances are naturally represented by more than one view. For example, images can be described by attributes of color, texture, and shape. Proteins can be characterized by the amino acid sequence and by their three-dimensional description. The unification of different views of a data set can be problematic because they may not be comparable or may have different degrees of importance. These degrees of importance may even manifest itself locally, according to the data substructures. This prompted the emergence of clustering algorithms capable of handling multi-represented data sets (i.e., data sets having more than one view) as the SCAD algorithm. This algorithm has shown promising results in experiments reported in the literature, but it has critical problems identified in this work that hinder its application in certain scenarios. These problems were solved here by proposing a new version of the algorithm, called ASCAD, based on formal proofs about its correctness. We developed relational versions for ASCAD, capable of handling data sets described only by the proximities between the instances. We also developed an index for internal and relative validation of multi-represented data clusterings. The evaluation of possibilistic clustering and bi-clustering by comparing the found and reference solutions (external validation) was also explored. Bi-clustering algorithms have gained increasing interest from the community of gene expression analysis. However, little is known of the behavior and properties of the measures aimed at external validation of bi-clustering, which motivated a theoretical and empirical analysis of these measures in this work. This analysis showed that most bi-clustering measures has critical issues and highlighted two of the measures as being the most promising. We included in this analysis three measures of non-exclusive partitional clustering, whose use in comparing bi-clusterings is possible through a new approach proposed in this thesis. Non-exclusive partitional clustering belong to a more general domain of solutions, i.e., the domain of possibilistic clusterings. There are some important conceptual flaws in the measures of possibilistic clustering, which motivated us to develop new measures and to conceptually and empirically analyse 34 measures. One of the proposed measures stood out as being the one who presented unbiased evaluations regarding the number of clusters, the maximum similarity when comparing the optimal solution with the reference one, and evaluations sensitive to solution differences in all scenarios considered

Com o advento da tecnologia de microarray, uma grande quantidade de dados de expressão gênica encontra-se disponível. Após a extração das taxas de expressão dos genes, técnicas de formação de clusters são utilizadas para a análise dos dados. Diante da diversidade do conhecimento que pode ser extraído dos dados de expressão gênica, existe a necessidade de diferentes técnicas de formação de clusters. O modelo dinâmico desenvolvido em (Zhao et. al. 2003a) apresenta diversas características interessantes para o problema de formação de clusters, entre as quais podemos citar: a não necessidade de fornecer o número de cluster, a propriedade de multi-escala, serem altamente paralelos e, principalmente, permitirem a inserção de regras e mecanismos mais complexos para a formação dos clusters. Todavia, este modelo apresenta dificuldades em determinar clusters de formato e tamanho arbitrários, além de não realizar a clusterização hierárquica, sendo estas duas características desejáveis para uma técnica de clusterização. Neste trabalho, foram desenvolvidas três técnicas para superar as limitações do modelo dinâmico proposto em (Zhao et. al. 2003a). O Modelo1, o qual é uma simplificação do modelo dinâmico original, porém mais eficiente. O Modelo2, que a partir da inserção de um novo conjunto de elementos no modelo dinâmico, permite a formação de clusters de formato e tamanho arbitrário. E um algoritmo para a clusterização hierárquica que utiliza o Modelo1 como bloco de construção. Os modelos desenvolvidos foram aplicados em dados biológicos, segmentando imagens de microarray e auxiliando na análise do conjunto expressão de genes de St. Jude Leukemia. / With the advent of microarray technology, a large amount of gene expression data is now available. Clustering is the computational technique usually employed to analyze and explore the data produced by microarrays. Due to the variety of information that can be extracted from the expression data, many clustering techniques with different approaches are needed. In the work proposed by (Zhao et. al. 2003a), the dynamical model for data clustering has several interesting features to the clustering task: the number of clusters does not need to be known, the multi-scale property, high parallelism, and it is flexible to use more complex rules while clustering the data. However, two desirable features for clustering techniques are not present: the ability to detect different clusters sizes and shapes, and a hierarchical representation of the clusters. This project presents three techniques, overcoming the restrictions of the dynamical model proposed by (Zhao et. al. 2003a). The first technique, called Model1, is more effective than the original model and was obtained simplifying it. The second technique, called Model2, is capable of detecting different clusters sizes and shapes. The third technique consists in a hierarchical algorithm that uses Model1 as a building block. The techniques here developed were used with biological data. Microarray image segmentation was performed and the St. Jude Leukemia gene expression data was analyzed and explored.

O agrupamento de dados é uma técnica fundamental em aplicações de diversos campos do mercado e da ciência, como, por exemplo, no comércio, na biologia, na psiquiatria, na astronomia e na mineração da Web. Ocorre que em um subconjunto desses campos, como engenharia industrial, ciências sociais, engenharia sísmica e recuperação de documentos, as bases de dados são usualmente descritas apenas pelas proximidades entre os objetos (denominadas bases de dados relacionais). Mesmo em aplicações nas quais os dados não são naturalmente relacionais, o uso de bases relacionais permite que os dados em si sejam mantidos sob sigilo, o que pode ser de grande valia para bancos ou corretoras, por exemplo. Nesta dissertação é apresentada uma revisão de algoritmos de agrupamento de dados que lidam com bases de dados relacionais, com foco em algoritmos que produzem partições rígidas (hard ou crisp) dos dados. Particular ênfase é dada aos algoritmos evolutivos, que têm se mostrado capazes de resolver problemas de agrupamento de dados com relativa acurácia e de forma computacionalmente eficiente. Nesse contexto, propõe-se nesta dissertação um novo algoritmo evolutivo de agrupamento capaz de operar sobre dados relacionais e também capaz de estimar automaticamente o número de grupos nos dados (usualmente desconhecido em aplicações práticas). É demonstrado empiricamente que esse novo algoritmo pode superar métodos tradicionais da literatura em termos de eficiência computacional e acurácia / Data clustering is a fundamental technique for applications in several fields of science and marketing, as commerce, biology, psychiatry, astronomy, and Web mining. However, in a subset of these fields, such as industrial engineering, social sciences, earthquake engineering, and retrieval of documents, datasets are usually described only by proximities between their objects (called relational datasets). Even in applications where the data are not naturally relational, the use of relational datasets preserves the datas secrecy, which can be of great value to banks or brokers, for instance. This dissertation presents a review of data clustering algorithms which deals with relational datasets, with a focus on algorithms that produce hard or crisp partitions of data. Particular emphasis is given to evolutionary algorithms, which have proved of being able to solve problems of data clustering accurately and efficiently. In this context, we propose a new evolutionary algorithm for clustering able to operate on relational datasets and also able to automatically estimate the number of clusters (which is usually unknown in practical applications). It is empirically shown that this new algorithm can overcome traditional methods described in the literature in terms of computational efficiency and accuracy

Acrescente capacidade de armazenamento introduziu novos desafios no contexto de exploração de grandes bases de dados de músicas. Esse trabalho consiste em investigar técnicas de comparação de músicas representadas por sinais polifônicos, com o objetivo de encontrar similaridades, permitindo a identificação de músicas cover em grandes bases de dados. Técnicas de extração de características a partir de sinais musicais foram estudas, como também métricas de comparação a partir das características obtidas. Os resultados mostraram que é possível encontrar um novo método de identificação de covers com um menor custo computacional do que os existentes, mantendo uma boa precisão / The growing capacity in storage and transmission of songs has introduced a new challenges in the context of large music data sets exploration. This work aims at investigating techniques for comparison of songs represented by polyphonic signals, towards identifying cover songs in large data sets. Techniques for music feature extraction were evaluated and compared. The results show that it is possible to develop new methods for cover identification with a lower computational cost when compared to existing solutions, while keeping the good precision

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

Dois dos principais fatores do aumento da performance em aplicações single-thread – frequência de operação e exploração do paralelismo no nível das instruções – tiveram pouco avanço nos últimos anos devido a restrições de potência. Neste contexto, considerando a natureza tolerante a imprecisões (i.e.: suas saídas podem conter um nível aceitável de ruído sem comprometer o resultado final) de muitas aplicações atuais, como processamento de imagens e aprendizado de máquina, a computação aproximativa torna-se uma abordagem atrativa. Esta técnica baseia-se em computar valores aproximados ao invés de precisos que, por sua vez, pode aumentar o desempenho e reduzir o consumo energético ao custo de qualidade. No atual estado da arte, a forma mais comum de exploração da técnica é através de redes neurais (mais especificamente, o modelo Multilayer Perceptron), devido à capacidade destas estruturas de aprender funções arbitrárias e aproximá-las. Tais redes são geralmente implementadas em um hardware dedicado, chamado acelerador neural. Contudo, essa execução exige uma grande quantidade de área em chip e geralmente não oferece melhorias suficientes que justifiquem este espaço adicional. Este trabalho tem por objetivo propor um novo mecanismo para fazer computação aproximativa, baseado em reúso aproximativo de funções e trechos de código. Esta técnica agrupa automaticamente entradas e saídas de dados por similaridade, armazena-os em uma tabela em memória controlada via software. A partir disto, os valores quantizados podem ser reutilizados através de uma busca a essa tabela, onde será selecionada a saída mais apropriada e desta forma a execução do trecho de código será substituído. A aplicação desta técnica é bastante eficaz, sendo capaz de alcançar uma redução, em média, de 97.1% em Energy-Delay-Product (EDP) quando comparado a aceleradores neurais. / Two of the major drivers of increased performance in single-thread applications - increase in operation frequency and exploitation of instruction-level parallelism - have had little advances in the last years due to power constraints. In this context, considering the intrinsic imprecision-tolerance (i.e., outputs may present an acceptable level of noise without compromising the result) of many modern applications, such as image processing and machine learning, approximate computation becomes a promising approach. This technique is based on computing approximate instead of accurate results, which can increase performance and reduce energy consumption at the cost of quality. In the current state of the art, the most common way of exploiting the technique is through neural networks (more specifically, the Multilayer Perceptron model), due to the ability of these structures to learn arbitrary functions and to approximate them. Such networks are usually implemented in a dedicated neural accelerator. However, this implementation requires a large amount of chip area and usually does not offer enough improvements to justify this additional cost. The goal of this work is to propose a new mechanism to address approximate computation, based on approximate reuse of functions and code fragments. This technique automatically groups input and output data by similarity and stores this information in a sofware-controlled memory. Based on these data, the quantized values can be reused through a search to this table, in which the most appropriate output will be selected and, therefore, execution of the original code will be replaced. Applying this technique is effective, achieving an average 97.1% reduction in Energy-Delay-Product (EDP) when compared to neural accelerators.

A Clusterização de dados em grupos oferece uma maneira de entender e extrair informações relevantes de grandes conjuntos de dados. A abordagem em relação a aspectos como a representação dos dados e medida de similaridade entre clusters, e a necessidade de ajuste de parâmetros iniciais são as principais diferenças entre os algoritmos de clusterização, influenciando na qualidade da divisão dos clusters. O uso cada vez mais comum de grandes conjuntos de dados aliado à possibilidade de melhoria das técnicas já existentes tornam a clusterização de dados uma área de pesquisa que permite inovações em diferentes campos. Nesse trabalho é feita uma revisão dos métodos de clusterização já existentes, e é descrito um novo método de clusterização de dados baseado na identificação de comunidades em redes complexas e modelos computacionais inspirados biologicamente. A técnica de clusterização proposta é composta por duas etapas: formação da rede usando os dados de entrada; e particionamento dessa rede para obtenção dos clusters. Nessa última etapa, a técnica de otimização por nuvens de partículas é utilizada a fim de identificar os clusters na rede, resultando em um algoritmo de clusterização hierárquico divisivo. Resultados experimentais revelaram como características do método proposto a capacidade de detecção de clusters de formas arbitrárias e a representação de clusters com diferentes níveis de refinamento. / DAta clustering is an important technique to understand and to extract relevant information in large datasets. Data representation and similarity measure adopted, and the need to adjust initial parameters, are the main differences among clustering algorithms, interfering on clusters quality. The crescent use of large datasets and the possibility to improve existing techniques make data clustering a research area that allows innovation in different fields. In this work is made a review of existing data clustering methods, and it is proposed a new data clustering technique based on community dectection on complex networks and bioinspired models. The proposed technique is composed by two steps: network formation to represent input data; and network partitioning to identify clusters. In the last step, particle swarm optimization technique is used to detect clusters, resulting in an hierarchical clustering algorithm. Experimental results reveal two main features of the algorithm: the ability to detect clusters in arbitrary shapes and the ability to generate clusters with different refinement degrees

本研究以一個食譜分享社群網站為研究對象，針對網站上所提供的食譜建立了運用 kNN 分群演算法的自動分群機制，並利用該網站上使用者的使用行為進行分群後群集的特徵描述參考。 本研究以三個階段建立了一針對食譜領域進行自動分群的資訊系統。第一階段為資料處理，在取得食譜網站上所提供的食譜資料後，雖然已經有相對結構化的格式可直接進行分群運算，然而由使用者所輸入的內容，仍有錯別字、贅詞、與食譜本身直接關連性不高等情形，因此必須進行處理。第二階段為資料分群，利用文字探勘進行內容特徵值的萃取，接著再以資料探勘的技術進行分群，分群的結果將會依群內的特徵、群間的相似度作為分群品質的主要指標。第三階段則為群集特徵分析，利用網站上使用者收藏食譜並加以分類的行為，運用統計的方式找出該群集的可能分類名稱。 本研究實際以 500 篇食譜進行分群實驗，在最佳的一次分群結果中，可得到 10 個食譜群集、平均群內相似度為 0.4482，每個群集可觀察出明顯的相似特徵，並且可藉由網站上使用者的收藏行為，標註出其群集特徵，例如湯品、甜點、麵包、中式料理等類別。 由於網站依照schema.org 所提供的食譜格式標準，針對網站上每一篇食譜內容進行了內容欄位的標記，本研究所實作之食譜分群機制，未來亦可運用在其他同樣採用 schema.org 所提供標準之同類型網站。

Over the past few years, there has been a renewed interest in the consensus problem for ensembles of partitions. Recent work is primarily motivated by the developments in the area of combining multiple supervised learners. Unlike the consensus of supervised classifications, the consensus of data partitions is a challenging problem due to the lack of globally defined cluster labels and to the inherent difficulty of data clustering as an unsupervised learning problem. Moreover, the true number of clusters may be unknown. A fundamental goal of consensus methods for partitions is to obtain an optimal summary of an ensemble and to discover a cluster structure with accuracy and robustness exceeding those of the individual ensemble partitions. The quality of the consensus partitions highly depends on the ensemble generation mechanism and on the suitability of the consensus method for combining the generated ensemble. Typically, consensus methods derive an ensemble representation that is used as the basis for extracting the consensus partition. Most ensemble representations circumvent the labeling problem. On the other hand, voting-based methods establish direct parallels with consensus methods for supervised classifications, by seeking an optimal relabeling of the ensemble partitions and deriving an ensemble representation consisting of a central aggregated partition. An important element of the voting-based aggregation problem is the pairwise relabeling of an ensemble partition with respect to a representative partition of the ensemble, which is refered to here as the voting problem. The voting problem is commonly formulated as a weighted bipartite matching problem. In this dissertation, a general theoretical framework for the voting problem as a multi-response regression problem is proposed. The problem is formulated as seeking to estimate the uncertainties associated with the assignments of the objects to the representative clusters, given their assignments to the clusters of an ensemble partition. A new voting scheme, referred to as cumulative voting, is derived as a special instance of the proposed regression formulation corresponding to fitting a linear model by least squares estimation. The proposed formulation reveals the close relationships between the underlying loss functions of the cumulative voting and bipartite matching schemes. A useful feature of the proposed framework is that it can be applied to model substantial variability between partitions, such as a variable number of clusters. A general aggregation algorithm with variants corresponding to cumulative voting and bipartite matching is applied and a simulation-based analysis is presented to compare the suitability of each scheme to different ensemble generation mechanisms. The bipartite matching is found to be more suitable than cumulative voting for a particular generation model, whereby each ensemble partition is generated as a noisy permutation of an underlying labeling, according to a probability of error. For ensembles with a variable number of clusters, it is proposed that the aggregated partition be viewed as an estimated distributional representation of the ensemble, on the basis of which, a criterion may be defined to seek an optimally compressed consensus partition. The properties and features of the proposed cumulative voting scheme are studied. In particular, the relationship between cumulative voting and the well-known co-association matrix is highlighted. Furthermore, an adaptive aggregation algorithm that is suited for the cumulative voting scheme is proposed. The algorithm aims at selecting the initial reference partition and the aggregation sequence of the ensemble partitions the loss of mutual information associated with the aggregated partition is minimized. In order to subsequently extract the final consensus partition, an efficient agglomerative algorithm is developed. The algorithm merges the aggregated clusters such that the maximum amount of information is preserved. Furthermore, it allows the optimal number of consensus clusters to be estimated. An empirical study using several artificial and real-world datasets demonstrates that the proposed cumulative voting scheme leads to discovering substantially more accurate consensus partitions compared to bipartite matching, in the case of ensembles with a relatively large or a variable number of clusters. Compared to other recent consensus methods, the proposed method is found to be comparable with or better than the best performing methods. Moreover, accurate estimates of the true number of clusters are often achieved using cumulative voting, whereas consistently poor estimates are achieved based on bipartite matching. The empirical evidence demonstrates that the bipartite matching scheme is not suitable for these types of ensembles.