Advances in Well-Structured Partition Method and its Careful Seeding

Clustering from pairwise dissimilarities is essential when original features are unavailable, yet many dissimilarity-based methods are highly sensitive to the initial partition and can converge to poor local optima. We revisit the Well-Structured Partition (WSP) framework, which models a dissimilarity matrix through an interpretable decomposition into between-cluster isolation and withincluster heterogeneity under a binary, row-stochastic membership constraint. In this paper the estimation is carried out by an alternating optimization scheme that maximize the explained variance of dissimilarities because WSP admits a sumof-squares-type decomposition of dissimilarities linking the total Frobenius norm of dissimilarities to the fitted classification structure and its residual part (error), providing an interpretable goodness-of-fit criterion of the classification structure. We further highlight the connection between WSP and well-known combinatorial optimization problems, thus positioning WSP into well-established Operation Research literature. In fact, the equivalence of the WSP to a clique/transitivityconstrained formulation which is a clustering methodology included among NPhard problems. For this reason, it is clear why initialization in WSP is also crucial and here studied. To improve accuracy in the solution, we propose WSP++, a mathematical reformulation of the WSP and a careful seeding strategy inspired by K-means++, which selects representative units via distance-based probabilities and builds an informative starting partition. The fast implementation of WSP based on incremental updates reduces computational cost. Some simulation evidences indicate that WSP++ improves accuracy and sta