Random Walk Learning On Graph

Traditional machine learning and data mining techniques usually require strict hypothesis or large amount of prior knowledge. Performance of those techniques could be reduced when the real-world problems do not satisfy their preconditions or can not provide sufficient prior knowledge. Recently, more and more such learning problems challenging the traditional learning methods are arising. Random walk provides an effective approach for solving those difficult problems.Random walk has already been successfully used in information retrieval, and now is gradually applied to machine learning and data mining. We propose random walk learning approach on graph, which takes random walk as a fundamental technique to deal with problems in supervised learning, semi-supervised learning and unsupervised learning. Contributions of this thesis are as follows.(1) Random walk classifier model. Based on the random walk theory on graph, we propose basic random walk classifier model, complementary random walk classifier model and combinatorial random walk classifier model. Under these models, we discuss the setting and the performance of their best classifiers, and also provide their implementation methods for the lazy classifiers. Theoretical analysis proves that our combinatory method can improve the classifier performance significantly.(2) Multilevel random walk. Inspired by the theory of simple random walk, we propose a unified framework for semi-supervised learning, i.e. multilevel random walk (MRW). MRW can produce numerous multi-class label propagation algorithms by constructing various component random walk models based on prior knowledge. It is demonstrated that MRW not only covers most of the existing label propagation algorithms, but also can produce more novel component propagation algorithms, whose solutions can also be recovered under the regularization framework. In addition, we also provide an effective balancing strategy to improve the classification performance on datasets with imbalanced labeled data. Experimental results show that MRW's component propagation algorithm and the balancing strategy are both very effective.(3) Random walk cellular automata clustering. Inspired by the behaviors of gregarious ant colonies, we propose an ant sleeping model ( ) with cellular automata. Under this model, we further present a random walk ant clustering (RWAC) algorithm. In the algorithm data object are represented by artificial ants which make random walk to gather with the ants in the same class and to depart from the ones of different classes. By random walking, the whole ant colony is finally organized into multiple independent sub-groups as the clusters. In order to improve the clustering speed and quality of RWAC, we also provide an ant greedy walk strategy and a self-adaptive parameter updating method. Our experiments result show that, compared with other ant clustering algorithms, RWAC is more intuitive, easier to operate, and has advantages in self-organization, effectiveness and robustness on high dimensional complex clustering problems.