Building k-edge-connected neighborhood graph for distance-based data projection

被引：19
作者：
Li, Y [1 ]
机构：
[1] Western Michigan Univ, Dept Comp Sci, Kalamazoo, MI 49008 USA
来源：
PATTERN RECOGNITION LETTERS | 2005年 / 26卷 / 13期
关键词：
data projection; dimensionality reduction; manifold learning; neighborhood graph;
D O I：
10.1016/j.patrec.2005.03.021
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Neighborhood graph construction is the first step of data projection based on geodesic distances. This paper presents an approach for constructing a k-edge-connected neighborhood graph. The approach works by applying a greedy algorithm to add edges in a non-decreasing order of edge length to the neighborhood graph if end vertices of each edge are not yet k-edge-connected on the graph. The approach is applicable to a wide range of data including data distributed in clusters. It is compared with other approaches through experiments. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：2015 / 2021
页数：7
相关论文
共 15 条
  • [1] Balasubramanian M, 2002, SCIENCE, V295
  • [2] Cox T., 2001, MULTIDIMENSIONAL SCA
  • [3] Curvilinear component analysis: A self-organizing neural network for nonlinear mapping of data sets
    Demartines, P
    Herault, J
    [J]. IEEE TRANSACTIONS ON NEURAL NETWORKS, 1997, 8 (01): : 148 - 154
  • [4] THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS
    EDMONDS, J
    KARP, RM
    [J]. JOURNAL OF THE ACM, 1972, 19 (02) : 248 - &
  • [5] Endre Tarjan R., 1974, P 6 ANN ACM S THEOR, P185
  • [6] Even S., 1975, SIAM Journal on Computing, V4, P507, DOI 10.1137/0204043
  • [7] Ford LR, 1956, CAN J MATH, V8, P399, DOI [DOI 10.4153/CJM-1956-045-5, 10.4153/CJM-1956-045-5]
  • [8] Garay M., 1979, COMPUTERS INTRACTABI
  • [9] Kruskal J. B., 1956, Proc. of American Mathematical Society, V7, P48, DOI [10.1090/S0002-9939-1956-0078686-7, DOI 10.1090/S0002-9939-1956-0078686-7]
  • [10] Lee J. A., 2000, P 8 EUR S ART NEUR N
12