Performance of a novel algorithm for clustering (hdbscan) applied to covariance matrices

Abstract

The use of grouping algorithms to divide and classify information in some phenomena is much easier in these modern times due to the advances in computing. However, measuring the efficiency and performance of these algorithms is necessary to identify the best methods to achieve the clustering. There exist several clustering or classification algorithms in literature such as KNN and k-means. More recently, the HDBSCAN, a density-based spatial hierarchical clustering algorithm, has been proposed. This algorithm has the ability to detect arbitrarily shaped clusters and it requires the specification of fewer parameters for achieving the best possible classification when compared to its competitors. Simulation studies have shown that this algorithm outperforms its competitors when clustering objects with several features. Nonetheless, the HDBSCAN algorithm has not been used for clustering of covariance matrices. Hence, this thesis proposes the use of the HDBSCAN algorithm for clustering covariance matrices, a task that could have applications in different areas such as time series, image processing, among others. A comparison of the performance of HDBSCAN with DBSCAN, K-NN and k-means is done using simulation studies. The scenarios of the simulation studies focus mainly on the sample size (number of matrices), number of clusters, size of the matrices, and distance metric. The relevance of this study is that, to our best knowledge, the HDBSCAN has not been implemented for clustering of covariance matrices. One of the factors having a large influence in the performance of a clustering algorithm is the distance metric. In this work, a revision of distance metrics between matrices is given. In particular, this thesis considers an affine invariant transformation (AIRM) to the calculate distance between symmetric positive definite matrices (SPD). This metric is compared with some popular distance metrics for matrices. Simulation studies suggest that the combination of distance metric AIRM and HDBSCAN exhibit the higher computational cost for large arrays of matrices. Nonetheless, this combination is effective for clustering high-dimensional matrices. K-means and HDBSCAN have comparable results for small number of clusters and high-dimensional covariance matrices. However, when the input parameters of the algorithms change, purity values for HDBSCAN do not change considerably (i.e., HDBSCAN is more robust to changes of input parameters). K-means algorithm suffers when the input parameters are manipulated, a sensitive issue when dealing with real problems. These findings demonstrate that HDBSCAN offers the highest robustness and performance for the four analyzed algorithms, a result that is consistent with previous finding for vectors.

El uso de algoritmos de agrupamiento para dividir y clasificar información en algunos fenómenos es mucho más fácil en estos tiempos modernos debido al avance en la computación. Sin embargo, medir la eficiencia y el desempeño de estos algoritmos es necesario para identificar los mejores métodos para lograr el agrupamiento. Existen muchos algoritmos de agrupamiento o de clasificación en la literatura tales como KNN y K-means. Mas recientemente, HDBSCAN, un algoritmo jerárquico espacial basado en densidad ha sido propuesto. Este algoritmo tiene la habilidad de detector clústeres de densidad arbitraria y requiere la especificación de menos parámetros para lograr la mejor clasificación posible comparado con sus competidores. Los Estudios de simulación han mostrado que este algoritmo supera a sus competidores cuando se agrupan objetos con muchas características. Sin embargo, el algoritmo HDBSCAN no ha sido usado para agrupar matrices de covarianza. Por tanto, esta tesis propone el uso de HDBSCAN para agrupar matrices de covarianza, una tarea que podría tener aplicaciones en diferentes áreas como ser series de tiempo, procesamiento de imágenes, entre otros. Una comparación de desempeño de HDBSCAN con DBSCAN, K-NN y K-means es hecha usando estudios de simulación. Los escenarios se enfocan principalmente en el tamaño de muestra (número de matrices), numero de clústeres, tamaño de matrices, y la métrica de distancia. La relevancia de este estudio es que, a nuestro saber, HDBSCAN no ha sido implementado para el agrupamiento de matrices de covarianza. Uno de los factores que tiene una gran influencia en el desempeño de los algoritmos de agrupamiento es la métrica de distancia. En este trabajo, una revisión de las métricas de distancia entre matrices es hecho. En particular, esta tesis considera la transformación invariante afín (AIRM) para calcular la distancia entre matrices definidas positivas simétricas (SPD). Esta métrica es comparada con algunas métricas de distancia para matrices muy populares. Los estudios de simulación sugieren que la combinación de la métrica de distancia AIRM y HDBSCAN exhiben un mayor costo computacional para largos arreglos de matrices. En todo caso, esta combinación es efectiva para matrices de alta dimensión. K-means y HDBSCAN tienen resultados comparables para bajo número de clústeres y matrices de alta dimensión. Sin embargo, cuando el parámetro de entrada de los algoritmos cambia, los valores de pureza para HDBSCAN no cambian considerablemente (i.e. HDBSCAN es más robusto para cambios en los parámetros de entrada). K-means sufre cuando el parámetro de entrada es manipulado, un asunto delicado cuando se trata con problemas de la vida. Estos hallazgos demuestran que HDBSCAN ofrece la mayor robustez y desempeño para los cuatro algoritmos analizados, un resultado consistente con previos hallazgos para vectores.