masterThesis
A fuzzy partitional clustering algorithm with adaptative euclidean distance and entropy regularization
Autor
RIZO RODRÍGUEZ, Sara Inés
Institución
Resumen
Data Clustering is one of the most important issues in data mining and machine learning. Clustering is a task of discovering homogeneous groups of the studied objects. Recently, many researchers have a significant interest in developing clustering algorithms. The most problem in clustering is that we do not have prior information knowledge about the given dataset. The traditional clustering approaches are designed for searching clusters in the entire space. However, in high-dimensional real world datasets, there are usually many irrelevant dimensions for clustering, where the traditional clustering methods work often improperly. Subspace clustering is an extension of traditional clustering that enables finding subspace clusters only in relevant dimensions within a data set. However, most subspace clustering methods usually suffer from the issue that their complicated parameter settings are almost troublesome to be determined, and therefore it can be difficult to implement these methods in practical applications. This work proposes a partitioning fuzzy clustering algorithm with entropy regularization and automatic variable selection through adaptive distance where the dissimilarity measure is obtained as the sum of the Euclidean distance between objects and prototypes calculated individually for each variable. The main advantage of the proposed approach to conventional clustering methods is the possibility of using adaptive distances, which change with each iteration of the algorithm. This type of dissimilarity measure is adequate to learn the weights of the variables dynamically during the clustering process, leading to an improvement of the performance of the algorithms. Another advantage of the proposed approach is the use of the entropy regularization term that serves as a regulating factor during the minimization process. The proposed method is an iterative three-step algorithm that provides a fuzzy partition, a representative for each fuzzy cluster. For this, an objective function that includes a multidimensional distance function as a measure of dissimilarity and entropy as the regularization term is minimized. Experiments on simulated, real world and image data corroborate the usefulness of the proposed algorithm. CNPq O agrupamento de dados é uma das questões mais importantes na mineração de dados e na aprendizagem de máquinas. O objetivo principal é descobrir grupos homogêneos nos objetos estudados. A maior dificuldade é que não se tem conhecimento prévio sobre o conjunto de dados. Usualmente as abordagens de agrupamento tradicionais são projetadas para pesquisar grupos em todo o espaço. No entanto, em conjuntos de dados reais de alta dimensão, geralmente existem muitas características irrelevantes para o agrupamento, onde os métodos tradicionais não apresentam bom performance. O agrupamento em subespaços é uma extensão do agrupamento tradicional que permite encontrar grupos em subespaços gerados apenas pelas variáveis relevantes do conjunto de dados. No entanto a maioria desses métodos precisam configurações de parâmetros não triviais e portanto o uso desses métodos em aplicações práticas é dificultado devido a encontrar a parametrização apropriada. Este trabalho propõe um algoritmo de agrupamento particional difuso com regularização de entropia e seleção automática de variáveis. A seleção de variáveis é feita através de distância adaptativa sendo a medida de dissimilaridade a soma das distâncias Euclidiana entre padrões e protótipos para cada variável. A principal vantagem da abordagem proposta sobre os métodos de agrupamento convencionais é a possibilidade do uso de distâncias adaptativas, as quais mudam a cada iteração do algoritmo. Este tipo de medida de dissimilaridade é adequado ao aprendizado dos pesos das variáveis dinamicamente durante o processo de agrupamento, levando a uma melhora do desempenho dos algoritmos. Outra vantagem da abordagem proposta é o uso do termo de regularização da entropia que serve como um fator regulador durante o processo de minimização. O método proposto é um algoritmo iterativo de três passos que fornece uma partição difusa, um representante para cada grupo difuso e aprende um peso de relevância para cada variável em cada grupo. Para isto é minimizada uma função objetivo que inclui uma função de distância multidimensional como medida de dissimilaridade e entropia como o termo de regularização. Os experimentos realizados em conjuntos de dados simulados, do mundo real e em imagens corroboram a utilidade do algoritmo proposto.