Graph Based Learning Under Graph Partition Criterion

Graph-based learning is a relatively new-subfield of machine leaning since the beginning of twenty-first century.After nearly ten years of development,it already has several valuable applications in pattern recognition,data mining,artificial intelligence and so on.Graph-based learning approaches use a graph to express the distribution information and relationship information of data,and it means that the change of peoples' data mind: Paying more attention on the relationship between data,rather than the elusive causal relationship.The dissertation forms graph-based learning framework and approaches under graph partition criterion,among these graph-based learning approaches.Though the state-of-the-art graph-based approaches under graph partition criterion can solve different problems in each field,they lack a unified learning framework.In this dissertation,we theoretical build a graph-based learning framework under graph partition criterion in mathematic,and then understand graph-based approaches under graph partition criterion in a unified framework.Main works are: Studying three basic problems in machine learning by graph-based learning under graph partition criterion,which are unsupervised learning,semi-supervised learning and supervised learning problems.Besides,we expand graph-based learning approaches by considering co-regularization,multiple regularization and path transmission.The main achievements and contributions of the dissertation are listed as follows:(1)A graph-based learning framework is proposed under graph partition criterion.The relationship between graph-based learning and two basic assumption in machine learning are summarized.We analysis elements in the original graph cut problem(NP hard problem)and propose a reasonable graph-based learning framework under graph partition criterion by relaxing constraints in the original graph cut problem more properly.The proposed framework supports various kinds of graph partition criterions.Constraints relaxing strategy keeps nonnegativity strictly,while emphasizes orthogonality and discreteness.The proposed framework owns favorable expansibility and can derive graph-based unsupervised learning,semi-supervised learning,supervised learning,co-regularized learning,and multiple regularized learning approaches.This partbuilds the theoretical foundation of graph-based learning under graph partition criterion.(2)A graph-based unsupervised learning approach is proposed under graph partition criterion.Based on the framework in chapter two,we propose a effective graph-based unsupervised learning approach under graph partition criterion by achieving constraints relaxing requirements.The proposed approach only keeps the nonnegativity constraint strictly and then incorporates the orthogonality and discreteness constraint into the objective function by designing Logdet regularizer.Accordingly,we design a algorithm,analysis its complexity,and prove its convergency.The experiments verify algorithm's unsupervised clustering performance.(3)A graph-based semi-supervised learning approach is proposed under graph partition criterion.Based on the framework in chapter two,we propose a effective graph-based semi-supervised learning approach under graph partition criterion by designing methods to incorporate prior information.Focusing on semi-supervised classification and clustering problems,we propose four prior information incorporating methods to improve traditional approaches' week ability in incorporating prior information.We review relevant approaches and design the corresponding algorithm.In addition,we analysis the algorithm's complexity and show its convergency.The experiments verify algorithm's semi-supervised classification and clustering performance.(4)A graph-based supervised learning approach is proposed under graph partition criterion.Based on analyzing the key steps of the graph-based supervised learning under graph partition criterion,we propose a effective graph-based supervised learning approach.We conduct isometric projection for samples with different labels,and the weekness that the interval between samples with different labels may be infinite of traditional graph-based supervised learning approaches is improved.Concretely,A graph-based supervised learning approach is proposed by designing multiple variable matrices to expand the ridge regression into graph-based learning domain.Furthermore,we consider the smoothness of dimensionality and the the sparsity of the projection matrix to formulate sparse smooth ridge regression approach.Accordingly,we design a algorithm and verify algorithm's supervised classification performance experimentally.(5)A graph-based co-regularized learning approach is proposed under graph partition criterion.Based on the framework in chapter two and the approach in chapter three,we propose a effective graph-based co-regularized learning approach under graph partition criterion by designing methods to incorporate multiple graphs.The proposed approach improves the graph-based learning approach's ability in learning multiple graphs.Focusing on unsupervised and semi-supervised learning problems,we propose six multiple graphs incorporating methods to enrich graph-based co-regularized learning approaches.Accordingly,we design a algorithm and verify algorithm's unsupervised clustering performance experimentally.(6)A graph-based multi-regularized learning approach is proposed under graph partition criterion.Based on the observation on the natural nonnegative demand of the nonnegative matrix factorization approach,we incorporate the nonnegative matrix factorization into the framework in chapter two as the multiple regularizer,and propose a effective graph-based multi-regularized learning approach under graph partition criterion.The proposed approach improves the graph-based learning approach's ability in data representation and can obtain a explicit projection in unsupervised(or semi-supervised)learning.We study relevant approaches and design the corresponding algorithm.The experiments verify algorithm's unsupervised clustering,semi-supervised classification and semi-supervised clustering performance.(7)A graph-based learning approach is proposed for measuring and analyzing the collectiveness in public video scene.Focusing on this popular and difficult problem,we first define the theme of the scene's collectiveness,then we expand the graph-based learning and propose a new collectiveness measurement approach by path spreading and exponent generating function.We also testify the graph-based unsupervised learning approach under graph partition by scene partiton experiment.Scene partiton paves the way to pattern classification and abnormality detection of collective motions.This part is meaningful for public security,and the proposed approach is showed experimentally in collectiveness measure and collectiveness motion partiton.