Semi-Supervised Clustering with Improved Delaunay Graph Fusion and Pairwise Constraints

In many data mining problems, leveraging structural and local connectivity information can significantly improve clustering performance. This paper presents a novel semi-supervised clustering framework that integrates weighted feature information, Delaunay-based graph construction, and pairwise constraints. First, feature weights are computed based on within-class pairwise variability, emphasizing dimensions that contribute most to local cluster structure. Weighted distances between samples are then calculated, and a Delaunay graph is constructed and filtered using an influence radius, preserving meaningful local geometric relationships while removing redundant edges. To capture higher-order neighborhood information, a GraphSAGE-style embedding propagates feature information through the graph, generating enriched low-dimensional representations of the data. Pairwise constraints are incorporated into the similarity matrix to encode prior knowledge about sample relationships, guiding the clustering process. Finally, semi-supervised clustering is performed using constraint-based spectral clustering. Experiments on benchmark datasets demonstrate that the combination of structural graph information, feature weighting, and pairwise constraints substantially improves clustering accuracy. The proposed framework is flexible and can be effectively applied across diverse data domains.

کلیدواژه ها:

Delaunay graph ، Clustering ، structural knowledge ، pairwise constraints