Game-Theoretic Optimization for Scale Fair Spectral Clustering
摘要
Spectral clustering, a fundamental unsupervised learning algorithm, is extensively applied in machine learning and data science. With advancements in fairness research, fair spectral clustering has gained prominence, which mainly focuses on group fairness and individual fairness to reduce the decision bias on sensitive attributes. Existing algorithms typically rectify inequalities for specific individuals or groups through resource reallocation, but often face challenges with disproportionately large or small cluster sizes. This paper introduces Game-Theoretic Optimization for Scale Fair Spectral Clustering (GTSC) to enhance fairness in spectral clustering with unbalanced cluster sizes. The algorithm models data points as strategic agents in a game and uses a dynamic competition mechanism and Gini coefficient adjustment to balance the cluster size. By introducing fairness constraints in the objective function, the penalty for cluster size differences is dynamically adjusted. In addition, a dynamic threshold merging strategy is used to coordinate the optimization of cluster quality and scale fairness. Experimental results demonstrate that GTSC outperforms existing scale fairness algorithms across various datasets, achieving clustering outcomes that meet the expected criteria.