Clustering ensembles: A hedonic game theoretical approach. (September 2018)

• Record Type: Journal Article
• Authors: Sandes, Nelson C.; Coelho, André L.V.
• Is Part Of: Pattern recognition. Volume 81(2018:Sep.)
• Page Start: 95
• Page End: 111
• Publication Date: 2018-09
• Subjects: Data clustering -- Clustering ensemble -- Hedonic game -- Nash stability -- Evidence accumulation; 62H30 -- 91A12 -- 91A80; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2018.03.017
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: We investigate a new clustering ensemble algorithm (HGCE) based on hedonic games. HGCE can always produce a Nash and individually stable consensus partition as final solution. We compare HGCE with other well-known clustering ensemble methods on several data sets. HGCE ranked first in the statistical comparisons conducted with two external validity measures. HGCE is stable to perturbations to the base partitions and converged fast in all experiments. Abstract: Clustering ensembles (CE) comprise a class of pattern recognition methods that take a set of data clusterings (base partitions) as input and generate a consensus, better-quality partition as output. This work tackles the CE problem from a hedonic game theoretical perspective. In the modeled cooperative game, data points are viewed as players while clusters are regarded as coalitions. Interestingly, we show that by using an evidence-accumulation based similarity measure our novel Hedonic Game based Clustering Ensemble (HGCE) algorithm always converges to a Nash stable coalition structure, that is, to a clustering solution that cannot be unilaterally improved from the standpoint of each data point. A variant of the algorithm is also introduced, which is insensitive to the way the data points are ordered in the data set. In order to assess the potentials of HGCE and contrast its performance with that exhibited by a number of CE methods, experiments have been conducted on several artificial and real-world data sets, the majority of which related to bioinformatics. Overall, the empirical results and statistical tests relative to two well-known external validity measures ratify the usefulness and competitiveness of the proposed approach, also showing that HGCE is computationally efficient and resilient to random perturbations to the set of base partitions.