On using supervised clustering analysis to improve classification performance

During the past decade, graph-based learning methods have proved to be an effective tool to make full use of both labeled and unlabeled data samples to improve learning performance. These methods try to discover the intrinsic structures and discriminative information embedded in the data, by building one or more graphs to model the relationship among the data samples. Consequently, how to build an effective graph is the core problem. In this paper we introduce a novel graph-based classification method, called Supervised clustering-based Regularized Least Squares Classification (SuperRLSC), in which local and global graphs of the data are built by supervised clustering. The motivation is that supervised clustering may discover more actual data structures compared to unsupervised clustering. In our algorithm, we firstly employ supervised k-means to partition the whole training dataset into several meaningful clusters in order to discover the intrinsic and discriminative structures. We then use the discovered structures to build local and global graphs of the data. The local graph reveals local geometric and discriminative structures, while the global graph reveals global discriminative information. Finally a hybrid local/global graph-based regularization term is embedded into supervised classification (i.e., RLSC in this paper). To validate the effectiveness of our algorithm, a series of experiments are performed on several UCI benchmark datasets. The results show that our algorithm can achieve better or at least comparable performance to the other graph-based algorithms and the traditional state-of-the-art supervised classification methods.