Label propagation based on local information with adaptive determination of number and degree of neighbor׳s similarity

In many practical applications of machine vision, a small number of samples are labeled and therefore, classification accuracy is low. On the other hand, labeling by humans is a very time consuming process, which requires a degree of proficiency. Semi-supervised learning algorithms may be used as a proper solution in these situations, where ε-neighborhood or k nearest neighborhood graphs are employed to build a similarity graph. These graphs, on one hand, have a high degree of sensitivity to noise. On the other hand, optimal determination of ε and k parameters is a complex task. In some classification algorithms, sparse representation (SR) is employed in order to overcome these obstacles. Although SR has its own advantages, SR theory in its coding stage does not reflect local information and it requires a time consuming and heavy optimization process. Locality-constrained Linear Coding (LLC) addresses these problems and regards the local information in the coding process. In this paper we examine the effectiveness of using local information in form of label propagation algorithm and present three new label propagation modifications. Experimental results on three UCI datasets, two face databases and a biometric database show that our proposed algorithms have higher classification rates compared to other competitive algorithms.