¹State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University, Beijing 100044，China
²Center for Industrial and Applied Mathematics, University of South Australia, Mawson Lakes, Australia

---

Abstract—Principal curves can learn high-accuracy data from multiple low-accuracy data. However, the current proposed algorithms based on global optimization are too complex and have high computational complexity. To address these problems and in the inspiration of the idea of divide and conquer, this paper proposes a Greedy algorithm based on dichotomy and simple averaging, named as KPCg algorithm. After that, three simulation data sets of sinusoidal, zigzag and spiral trajectories are used to test the performance of the KPCg algorithm and we compare it with the k-segment algorithm proposed by Verbeek. The results show that the KPCg algorithm can efficiently learn highaccuracy data from multiple low-accuracy data with constraint endpoints and have advantages in accuracy, computational speed and scope of application.

Index Terms—Principal curves algorithm; principal of nearest neighbor; adaptive radius; dichotomy; simple averaging

[PDF]

Cite: Shiying Yang, Dewang Chen, Xiangyu Zeng, Peter Pudney, "A Greedy Algorithm for Constraint Principal Curves," Journal of Computers vol. 9, no. 5, pp. 1125-1130, 2014.