A study of the relationship between support vector machine and Gabriel graph
Wan Zhang, Irwin King · 2003
One of the major tasks in the support vector machine (SVM) algorithm is to locate the discriminant boundary in classification task. It is crucial to understand various approaches to this particular task. In this paper, we survey several different methods of finding the boundary from different disciplines. In particular, we examine SVM from the statistical learning theory, the convex hull problem from the computational geometry's point of view, and Gabriel's graph from the computational geometry perspective to describe their theoretical connections and practical implementation implications. Moreover, we implement these methods and demonstrate their respective results on the classification accuracy and run time complexity. Finally, we conclude with some discussions about these three different techniques.