Research On The Intelligent Random Walks On Graph For Classification Algorithms And Applications

Recently, under the consumption of smoothness and clustering consistency, random walks on graph was mainly employed to design a class of label propagation algorithms, where the labeled nodes are able to propagate their labels to neighboring unlabeled nodes during the random walk process. Due to the memoryless and constraintless of such walk, it is easy to get the analytic solution of such kind of iterative algorithms. Though, multistep transition among the nodes seems redundant in many real applications that usually require biased and related walk. Worsemore, those analytic solutions often involve complicated matrix operation thus affecting their scalability. Usually, each node is treated equally in this free random walk, but the noise and error embeded in some nodes will also be exteneded and expanded. As a result, the effective utilize of labeled nodes deserves study.In contrast to unlimited random walk, we pay more attention to certain complex random walk. Such as the walk of ant colony in Ant Colony Optimization algorithm, the walk behavior of individual ant is constrained in the form of foraging, graph exploring and returning to nest etc. In specific, ant can visit every node only once; moreover, it maintains a memory of history tour information by which to move to the optimal solution besides the heuristic probability. The vast potential of interdiscipline research or hybrid algorithms has always been acknowledged. Taking the Data Mining as an example, it is an organic combination of Database technology, Statistics and Machine Learning, and has become an inevitable trend for promoting the development of Artificial Intelligence.In this context, this paper proposes this study, which creatively integrates Swarm Intelligence, Random Walk and Machine Learning ideas for data mining and analysis. Then considering the classification problems, we present our Intelligent Random Walk concept starting by viewing the labeled data as a swarm from the whole level, and then imposing certain constraints and guidances on its members. By doing so, we established a Swarm Random Walk (SRW) Framework and derived three learning strategies dedicated to coping with problems with respect to supervised classification, semi-supervised classification and evolutionary classification. Contributions of this thesis are as follows:The complementary swarm random walk learning is studied. Based on the SRW model, we propose a combinatory optimization strategy by the help of complementary lazy random walk. By applying this strategy into existing basic random walk classifier, we present a supervised lazy random walk classifier and its extended version--supervised multi-step random walk classifier. Experiments prove that our combinatory optimization strategy can improve the classifier performance significantly, and furthur the real-world application test shows that our classifier is better than conventional supervised classifier.The diversed swarm random walk learning is addressed. In correspondence to the multiple labels in classification, the SRW model is furthur developed so that the whole swarm can be divided into different types of groups. Under this setting, we propose a Ants Random Walk (ARW) classification algorithm, which turns the classification problem into the scramble for resources (unlabeled nodes) among diversed ant colonies. We discussed in detail about the graph construction, heuristic value, pheromone propagation and pheromone update by one colony of ants. Experimental results show the superiority against other semi-supervised classification methods. Later, in view of our previously proposed Confidence-based Label Porpagation (CLP) method, we bring the same idea into our ARW algorihtm and produce a Confidence-based Ants Random Walk (CARW) classification algorithm. CLP and CARW are both experimentally proved to be effective.The evolutionary swarm random walk learning is investigated. Inspired by the static CARW algorithm, we propose an Evolutionary Ants Random Walk classification (EARW) algorithm to deal with the dynamic classification problem. In this algorithm, each ant colony is able to send its members to propagate its unique pheromone on the unlabeled instances for labeling them indirectly. Meanwhile, the unlabeled instances are treated as unlabeled ants, who have their preference for joining one of those labeled colonies. This preference is considered as homing feedback during the pheromone update process. Afterwards, the natural selection process is triggered so as to maintain the smoothness of this swarm. Theoretical explanation and experimental results show the fitness and excellence of our proposed algorithm for evolutionary data classification.