Fuzzy C-means and clustering algorithms: a comparative study

Abstract

Clustering is a technique that groups observations in a dataset based on the distance to the centre of the clusters. One of the first clustering algorithms was K-Means (KM), which is especially accurate at recognising well-separated clusters. Afterwards, Fuzzy C-Means (FCM) was formulated to improve the accuracy of KM with datasets containing overlapping clusters. Since then, other derivatives of FCM have been developed to improve it: Gustafson Kessel Fuzzy C-Means (GKFCM) performs better for non-spherical clusters, Fuzzy C-Means++ (FCM++) and Suppressed-Fuzzy C-Means (S-FCM) improve FCM's efficiency and Possibilistic C-Means (PCM) is more accurate for datasets with noise and outliers. In this project, I have compared KM, FCM, GKFCM, FCM++, S-FCM and PCM to check how each evolution has improved its predecessor. This comparison is centralised around FCM. I have validated parameters such as computational efficiency, performance and accuracy. I have found that, among all the algorithms, FCM has the best performance for datasets with overlapping clusters, even though S-FCM improves its computational efficiency. Also, KM is the most efficient algorithm and GKFCM performs well with non-spherical clusters. However, it is less accurate. Finally, PCM has not shown any advantage over FCM. This project is a starter point for future investigations of the conditions under which every algorithm works better. Most of the datasets used here are synthetic datasets, based on near-ideal characteristics. Nevertheless, real-world datasets are expected to have more complex structures for which the choice of algorithms require a more thorough investigation.

La clusterització de dades és una tècnica que agrupa les observacions d'un conjunt de dades en funció de la distància al centre dels clústers. Un dels primers algoritmes de clusterització va ser el K-Means (KM), que és especialment acurat per a reconèixer grups de clústers separats. El Fuzzy C-Means (FCM) va ser formulat per a millorar la precisió del KM amb clústers superposats. S'han desenvolupat altres algorismes derivats del FCM per a millorar-lo: el Gustafson Kessel Fuzzy C-Means (GKFCM), per a clústers no esfèrics, el Fuzzy C-Means++ (FCM++) i el Suppressed Fuzzy C-Means (S-FCM), més eficients, i el Possibilistic C-Means (PCM), més precís per a observacions atípiques. En aquest projecte, he comparat el KM, el FCM, el GKFCM, el FCM++, el S-FCM i el PCM i les millores dels nous respecte als predecessors, centrant-ho al voltant del FCM. He validat paràmetres com l'eficiència computacional, el rendiment i la precisió. He trobat que, d'entre tots els algorismes, el FCM té el millor rendiment per a conjunts de dades amb clústers superposats i el KM és l'algorisme més eficient. El GKFCM funciona bé amb clústers no esfèrics, però no és del tot precís. Finalment, el PCM no ha mostrat cap avantatge respecte al FCM. Aquest projecte és un punt de partida per a futures investigacions sobre els algorismes de clusterització, ja que la majoria dels conjunts de dades utilitzats aquí són conjunts de dades sintètiques, basades en característiques ideals. I s'espera que els conjunts de dades reals tinguin estructures més complexes.

El clustering es una técnica que agrupa las observaciones de un conjunto de datos en función de la distancia al centro de los clústeres. Uno de los primeros algoritmos de agrupamiento fue el K-Means (KM), que es especialmente preciso para reconocer clústeres bien separados. Posteriormente, el Fuzzy C-Means (FCM) se formuló para mejorar la precisión del KM con conjuntos de datos que contienen grupos superpuestos. Desde entonces, se han desarrollado otros derivados del FCM para mejorarlo: Gustafson Kessel Fuzzy C-Means (GKFCM), para grupos no esféricos, Fuzzy C-Means ++ (FCM ++) y Suppressed-Fuzzy C-Means (S-FCM) para mejorar la eficiencia del FCM y Possibilistic C-Means (PCM), más preciso para conjuntos de datos con ruido y valores atípicos. En este proyecto, he comparado KM, FCM, GKFCM, FCM ++, S-FCM y PCM con el objetivo de comprobar de qué manera cada uno de ellos ha mejorado a su predecesor. Esta comparación está centralizada en FCM. He validado parámetros como la eficiencia computacional, el rendimiento y la precisión. He descubierto que, de entre todos los algoritmos, FCM tiene el mejor rendimiento para conjuntos de datos con grupos superpuestos, aunque S-FCM mejora su eficiencia computacional. Además, KM es el algoritmo más eficiente de todos en términos absolutos, y GKFCM se desempeña bien con clústeres no esféricos, aunque es menos preciso. Finalmente, PCM no ha mostrado ninguna ventaja sobre FCM. Este proyecto es un punto de partida para futuras investigaciones acerca de las condiciones en las que cada algoritmo funciona mejor. La mayoría de los conjuntos de datos utilizados aquí son conjuntos de datos sintéticos con características casi ideales. Sin embargo, se espera que los conjuntos de datos reales tengan estructuras más complejas para las que la elección del mejor algoritmo a utilizar requiere una investigación más exhaustiva.