Department of Electrical and Computer Engineering, National University of Singapore, Singapore.
IEEE Trans Image Process. 2010 Apr;19(4):858-66. doi: 10.1109/TIP.2009.2038764. Epub 2009 Dec 22.
The graph construction procedure essentially determines the potentials of those graph-oriented learning algorithms for image analysis. In this paper, we propose a process to build the so-called directed l1-graph, in which the vertices involve all the samples and the ingoing edge weights to each vertex describe its l1-norm driven reconstruction from the remaining samples and the noise. Then, a series of new algorithms for various machine learning tasks, e.g., data clustering, subspace learning, and semi-supervised learning, are derived upon the l1-graphs. Compared with the conventional k-nearest-neighbor graph and epsilon-ball graph, the l1-graph possesses the advantages: (1) greater robustness to data noise, (2) automatic sparsity, and (3) adaptive neighborhood for individual datum. Extensive experiments on three real-world datasets show the consistent superiority of l1-graph over those classic graphs in data clustering, subspace learning, and semi-supervised learning tasks.
图构建过程本质上决定了那些面向图的学习算法在图像分析中的潜力。在本文中，我们提出了一种构建所谓的有向 l1 图的过程，其中顶点包含所有样本，而每个顶点的入边权重描述了从其余样本和噪声中对该顶点进行 l1 范数驱动重建的过程。然后，基于 l1 图推导出了一系列用于各种机器学习任务的新算法，例如数据聚类、子空间学习和半监督学习。与传统的 k-最近邻图和ε-球图相比，l1 图具有以下优势：(1)对数据噪声具有更大的鲁棒性，(2)自动稀疏性，以及(3)针对单个数据点的自适应邻域。在三个真实数据集上的大量实验表明，在数据聚类、子空间学习和半监督学习任务中，l1 图优于那些经典图。
