Research On Data’s Topological Structure Based On Triplet-Induced Graph

Graph is commonly used to model the relationships among data points. However, con-ventional strategies to establish graph models are mostly based on pairwise/doublet relations, which do not make full use of the latent topological structures in data. In this paper, we have proposed two different triplet-induced graphs for the unsupervised and supervised scenarios, re-spectively. Besides, practical comparison experiments well validate the graphs’effectiveness. Main contributions of this paper lie in three-folds:(1) In the unsupervised scenario, we propose a triplet-induced graph which is subsequently applied to simultaneous feature selection and clustering. A novel triplet-based ordinal locality preserving loss function is presented to preserve the relative neighborhood proximities of each data point in feature selection. Through a Laplacian matrix, the loss function is integrated into a general framework for simultaneous feature selection and clustering. Extensive comparison experiments on several benchmark datasets well validate the encouraging gain in clustering from our proposed method.(2) In the supervised scenario, the other triplet-induced graph is presented and applied to analysis dictionary learning (ADL) in pattern classification. A proposed discriminative topology preserving loss function and an additional code consistent term provide a discriminative sparse coding space. In this space, neighbors with different labels are repelled by a large margin and same-label neighbors are orderly preserved, which is beneficial to k Nearest Neighbor (kNN) classification.Experiments on several commonly used databases show that our proposed method not only significantly improves the discriminative ability of ADL, but also outperforms state-of-the-art synthesis dictionary learning methods.(3) Half-quadratic technique and alternate search strategy are used to speed up the opti-mization process of each aforementioned application. For each proposed model, we provide detailed convergence analysis. Experimental results indicate the following aspects:(Ⅰ) Triplet-induced graph models have both theoretical and practical value. (Ⅱ) Feature selection can be conducive to distance-based clustering tasks if ordinal locality is well treated. (Ⅲ) Preserving discriminative topology in ADL can contribute to kNN-based pattern classification tasks.