Clustering with Penalty for Joint Occurrence of Objects: Computational Aspects
This work addresses the computational challenges of an existing clustering method for researchers and practitioners dealing with object incidence data, providing incremental improvements to its practical application.
This paper investigates the computational aspects of a clustering method that minimizes the joint occurrence of objects from the same cluster within given sets. The authors prove the problem is NP-hard and propose a genetic algorithm augmented with a renumbering procedure, a local search heuristic, and a simplified initial solution, demonstrating significant performance enhancements in simulations.
The method of Holý, Sokol and Černý (Applied Soft Computing, 2017, Vol. 60, p. 752-762) clusters objects based on their incidence in a large number of given sets. The idea is to minimize the occurrence of multiple objects from the same cluster in the same set. In the current paper, we study computational aspects of the method. First, we prove that the problem of finding the optimal clustering is NP-hard. Second, to numerically find a suitable clustering, we propose to use the genetic algorithm augmented by a renumbering procedure, a fast task-specific local search heuristic and an initial solution based on a simplified model. Third, in a simulation study, we demonstrate that our improvements of the standard genetic algorithm significantly enhance its computational performance.