Abstract: Aiming at the problem that the traditional Graph Transduction (GT) algorithm is computationally intensive and inaccurate, a semi-supervised classification algorithm based on C-means clustering and graph transduction was proposed. Firstly, the Fuzzy C-Means (FCM) clustering algorithm was used to pre-select unlabeled samples and reduce the range of the GT algorithm. Then, the k-nearest neighbor sparse graph was constructed to reduce the false connection of the similarity matrix, thereby reducing the time of composition, and the label information of the primary unlabeled samples was obtained by means of label propagation. Finally, combined with the semi-supervised manifold hypothesis model, the extended marker data set and the remaining unlabeled data set were used to train the classifier, and then the final classification result was obtained. In the Weizmann Horse data set, the accuracy of the proposed algorithm was more than 96%, compared with the traditional method of only using GT to solve the dependence problem on the initial set of labels, the accuracy was increased by at least 10%. The proposed algorithm was applied directly to the terracotta warriors and horses, and the classification accuracy was more than 95%, which was obviously higher than that of the traditional graph transduction algorithm. The experimental results show that the semi-supervised classification algorithm based on C-means clustering and graph transduction has better classification effect in image classification, and it is of great significance for accurate classification of images.

Key words: C-means clustering, Graph Transduction (GT), semi-supervised classification, similarity matrix, sparse map

摘要： 针对传统图转导（GT）算法计算量大并且准确率不高的问题，提出一个基于C均值聚类和图转导的半监督分类算法。首先，采用模糊C均值（FCM）聚类算法先对未标记样本预选取，缩小图转导算法构图数据集的范围；然后，构建k近邻稀疏图，减少相似度矩阵的虚假连接，进而缩减了构图的时间，通过标记传播的方式得出初选未标记样本的标记信息；最后，结合半监督流形假设模型利用扩充的标记数据集以及剩余未标记数据集进行分类器的训练，进而得出最终的分类结果。在Weizmann Horse数据集下，所提算法分类准确率均达到96%以上，和传统仅使用图转导的分类方法相比，解决了对初始标记集的依赖性问题，将准确率至少提高了10%；将所提算法直接运用到兵马俑数据集，分类准确度也达到95%以上，明显高于传统的图转导算法。实验结果表明，基于C均值聚类和图转导的半监督分类算法，在图像分类方面有较好的分类效果，对图像的精准分类具有研究意义。

关键词: C均值聚类, 图转导, 半监督分类, 相似度矩阵, 稀疏图