Clusterização multidimensional via otimização da função do estimador de densidade Kernel

Abstract

Resumo: Neste trabalho, apresentamos três novos algoritmos para clusterização de dados multidimensionais baseados na múltipla otimização da função do estimador de densidade kernel Gaussiano, o MulticlusterKDE, o AdditiveclusterKDE e o TreeKDE. Os algoritmos propostos possuem a principal vantagem de não exigirem, a priori, o número de clusters, além de serem simples de implementar, bem definidos e sempre convergirem em um número finito de etapas, independentemente do conjunto de dados a ser agrupado. Além dos algo­ ritmos, propomos ainda uma nova métrica de validação interna de clusterização, o índice de Densidade da Clusterização (índice CD), baseado na máxima razão entre a dispersão interna dos clusters e a separação entre centroides. Visando facilitar a compreensão dos algoritmos propostos, os quais foram implementados no Software R, descrevemos detalhadamente suas metodologias e procedimentos, exemplificando cada um dos seus passos por meio de um problema simples, bidimensional, com um número reduzido de observações e uma estrutura de grupos bem definida. Na sequência, realizamos experimentos numéricos comparando os três algoritmos propostos a alguns outros já consagrados na literatura, sendo: K-means, K-medoids, CLARA, GMM, DIANA, CLINK, PdfCluster e DBSCAN. Os experimentos conduzidos tiveram três vertentes: explorar e analisar as diferentes características dos algoritmos de clusterização aplicados em problemas bidimensionais; medir a qualidade das clusterizações propiciadas pelos algoritmos em problemas de dimensões variadas; avaliar o comportamento dos algoritmos de clusterização aplicados a problemas de classificação. Os dados utilizados consistem em problemas práticos provenientes da literatura e de pacotes do Software R, além de problemas cujos dados foram gerados randomicamente. Os resultados numéricos evidenciaram que os algoritmos MulticlusterKDE, AdditiveclusterKDE e TreeKDE são promissores e competitivos para a clusterização de dados multidimensionais, quando comparados aos outros algoritmos da literatura supra citados, uma vez que esses apresentam bons desempenhos, não necessitam da especificação do número de clusters e conseguem identificar grupos de alta densidade. Quanto ao índice CD, resultados preliminares revelaram que quando comparado com métricas já consagradas na literatura, tais como o índice DB e o coeficiente de silhueta, é eficiente para avaliar clusterização de dados multidimensionais uma vez que apresentou uma concordância substancial com o índice DB a um custo de execução similar, e uma concordância significativa com o coeficiente de silhueta a um custo execução consideravelmente menor, comprovando sua qualidade como métrica de validação interna para clusterização de dados multidimensionais.

Abstract: ln this thesis we present three new algorithms for multidimensional data clustering based on multiple optimization of the Gaussian kernel density estimator function, the MulticlusterKDE, AdditiveclusterKDE and TreeKDE. The suggested algorithms have the main advantage of not requiring, a priori, the number of clusters, besides the fact that they are simple to implement, are well defined and always converge in a finite number of steps, regardless of the dataset to be clustered. ln addition to the algorithms, we also propose a new internal clustering validation metric, the Clustering Density índex (CD índex), based on the maximum ratio between the internal dispersion of clusters and the separation between centroids. ln order to facilitate the understanding of the suggested algorithms, which were implemented in the software R, we describe in detail its methodologies and procedures, exemplifying each of its steps by means of a simple two-dimensional problem, with a reduced number of observations and a well-defined structure of groups. After this, we performed numerical tests by comparing the three proposed algorithms with some others already established in the literature, as follows: K-means, K-medoids, CLARA, GMM, DIANA, CLINK, PdfCluster and DBSCAN. The experiments conducted had three main aspects: to explore and analyze the different characteristics of clustering algorithms applied to two-dimensional problems; to measure the quality of clustering provided by the algorithms in problems of different dimensions; to evaluate the performance of clustering algorithms applied to classification problems. The input data consist of practice problems sourced from the literature and from Software R packages, as well as problems whose data were randomly generated. The numerical results showed that MulticlusterKDE, AdditiveclusterKDE and TreeKDE algorithms are promising and competitive for multidimensional data clustering when compareci with other algorithms in the abovementioned literature, since they have good performance, do not require specification of the number of clusters and can identify high-density clusters. Regarding the CD índex, preliminary results showed that when compareci to metrics already established in the literature, such as the DB índex and the silhouette coefficient, it is an accurate way to evaluate the clustering of multidimensional data since it showed substantial agreement with the DB índex at a similar execution cost, and significant agreement with the silhouette coefficient at a considerably lower execution cost, hence proving its quality as an internal validation metric for multidimensional data clustering.