Support Vector Machine(SVM) is an important tool in machine learning. SVM has shown good performances in applications such as face detection, object recognition and information retrieval.Current SVM algorithms become slow in dealing with large data sets. Therefore, exploration of efficient SVM algorithms is important in both theory and practice. Since geometric descriptions of SVM have been known, it is possible using geometric algorithms in SVM. This study is focused on the geometric algorithms for Support Vector Machine and kernel clustering. The main work is summarized as follows. 1. Gilbert algorithm is a very popular algorithm in colli-sion detection in robotics and also in classification in pattern recognition. However, the major drawback of Gilbert algorithm is that in many cases it becomes very slow as it approaches the final solution and the vertices selection vibrates in these cases. In this work, a) We prove theoretically that when the selection of vertices vibrates among several points, the algorithm will converge to the hyper-plane determined by these points. b)Based on the above results, an improved Gilbert algorithm for computing the distance between two convex polytopes is presented. The algorithm can avoid the slow convergence of the original one. Numerical simulation demonstrates the effectiveness and advantage of the improved algorithm. 2. We propose a simplified Support Vector Machine. The method is based on visible faces of the convex hull. We use an iterative projection algorithm in searching for the reduced vector set. Experimental results on real data sets as well as synthetic data sets indicate that the proposed method is effective while preserving good generalization performance. 3. Core Vector Machine (CVM) is an efficient kernel method for large data classification. It has prominent advantages in dealing with large data sets in high-dimensional space. In this work, we present a novel geometric framework between CVM and the traditional Support Vector Machine (SVM). It is believed that the obtained geometric relationship will be helpful in analyzing CVM. 4. Kernel Grower is a novel kernel clustering method proposed recently by Camastra and Verri (2005). It shows good performance for various data sets and compares favora-bly with respect to popular clustering algorithms. However, the main drawback of the method is the weak scaling ability in dealing with large data sets. In this work, we propose a scaled-up Kernel Grower method using core-sets, which is significantly faster than the original method for large data clustering. Meanwhile, it can deal with very large data sets. Numerical experiments on benchmark data sets as well as synthetic data sets show the efficiency of the proposed method. The method is also applied to real image segmentation to illustrate its performance.
修改评论