Paralelización y optimización de DBSGRAPH

Abstract

Dentro del aprendizaje automático existen varias categorías entre las que destacan aprendizaje supervisado y aprendizaje no supervisado. Concretamente, el aprendizaje no supervisado identifica dentro de un grupo de datos no etiquetados un conjunto de patrones o similitudes entre los datos. Los algoritmos no supervisados se dividen a su vez en análisis de componente principal y clustering. Los algoritmos de clustering permiten agrupar en diferentes conjuntos y asignar una etiqueta a un grupo de datos concretos similares entre ellos. Dependiendo del tipo de algoritmo de clustering es posible separar los datos en regiones linealmente o no linealmente separables, identificar el ruido o valores atípicos dentro de los datos, calcular la densidad de los conjuntos obtenidos, calcular el grado de pertenencia de un dato a una clase para así permitir diferenciar entre el núcleo de la clase y la periferia y otras propiedades adicionales. Aunque en ocasiones, no todas las propiedades citadas anteriormente son verificadas por todos los algoritmos de clustering. Es decir, hay algoritmos que sacrifican algunas de estas para reforzar otras. Los principales problemas de los algoritmos de clustering recaen en la inicialización de los parámetros ideales para el posterior funcionamiento idóneo de los diferentes modelos de análisis. Entre los algoritmos más populares encontramos kmedias, cuyo principal problema es encontrar el número de clusters o conjuntos idóneos para inicializar el modelo y la separación de los clusters en regiones linealmente separables o DBSCAN, que necesita de dos parámetros de entrada, un valor de entrada llamado epsilon y otro para el mínimo número de datos por conjunto. En este trabajo se va a presentar un algoritmo basado en grafos, componentes conexas y la centralidad de cercanía que permite resolver problemas de clustering. Este algoritmo no presenta ningún parámetro de entrada a diferencia de otros métodos de la literatura y permite asignar un grado de pertenencia de cada elemento a su clase correspondiente.---ABSTRACT---Machine learning has different categories where supervised learning and unsupervised learning are the most noteworthy. Unsupervised learning is capable of identifying inside of an unlabeled dataset a group or cluster of data with similarities between them. Unsupervised learning algorithms can be divided in principal component analysis and clustering or cluster analysis. Cluster analysis models groups of data in sets where data is quite similar between them and assign these sets a label. Depending on the cluster algorithm, the model is capable of separating data in linear or non-linear regions, identifying noise or outliers inside the dataset, calculate the density of each cluster, calculate the pertenency degree of a value inside a set and calculate other properties. Sometimes, not all the properties cited aboved are fullfiled by all classifiers. The main problem of cluster analysis is the initialization of parameters. As an example, k-means, has problems identifying the value k, which describes the number of clusters and also, this clusters are only linear separable. Also, BDSCAN, needs two parameters, one called epsilon and the other parameter is the minimun number of points inside a cluster. In this thesis it will be presented and algortihm that will try to solve clustering problems with the help of concepts of Graph theory like connected components and closeness centrality.