Label propagation algorithm based on Roll-back detection and credibility assessment

The traditional label propagation algorithm (LPA) iteratively propagates labels from a small number of labeled samples to many unlabeled ones based on the sample similarities. However, due to the randomness of label propagations, and LPA's weak ability to deal with uncertain points, the label error may be continuously expanded during the propagation process. In this paper, the algorithm label propagation based on roll-back detection and credibility assessment (LPRC) is proposed. A credit evaluation of the unlabeled samples is carried out before the selection of samples in each round of label propagation, which makes sure that the samples with more certainty can be labeled first. Furthermore, a roll-back detection mechanism is introduced in the iterative process to improve the label propagation accuracy. At last, our method is compared with 9 algorithms based on UCI datasets, and the results demonstrated that our method can achieve better classification performance, especially when the number of labeled samples is small. When the labeled samples only account for 1% of the total sample number of each synthetic dataset, the classification accuracy of LPRC improved by at least 26.31% in dataset circles, and more than 13.99%, 15.22% than most of the algorithms compared in dataset moons and varied, respectively. When the labeled samples account for 2% of the total sample number of each dataset in UCI datasets, the accuracy (take the average value of 50 experiments) of LPRC improved in an average value of 23.20% in dataset wine, 20.82% in dataset iris, 4.25% in dataset australian, and 6.75% in dataset breast. And the accuracy increases with the number of labeled samples.