Clique Partitioning for Clustering: A Comparison with K-Means and Latent Class Analysis

Abstract

The clique partitioning (CP) model has been recognized for many years as a useful conceptual construct for clustering problems. Computational difficulty, however, has limited the adoption of this perspective as a useful model in practice. In this article, we illustrate the use of a new formulation for the clique partitioning problem that is readily solvable by basic metaheuristic methodologies such as Tabu Search. As such, this new model enables the widespread use of CP for clustering in practice. In this article, we present test results demonstrating that our CP model is an attractive alternative to well-known methods such as K-means and Latent Class (LC) clustering. Ours is the first article in the literature making such comparisons.

Keywords:

• Clique partitioning
• Clustering
• Latent class modeling
• K-means
• Metaheuristics
• Silhouette coefficients
• Tabu search

Mathematics Subject Classification:

• 62H30
• 68T10

Acknowledgments

The authors would like to express their appreciation to Drs. Vermunt and Magidson for sharing the data sets used in this article along with the results they obtained using their Latent Class methodology.