Some Algorithms Research On Support Vector Machines

Support Vector Machine(SVM) is a kind of generalized learning machine and a new technique of data mining. It is a new tool to solve problems in machine learning by optimization methods. The critical problem of SVM is to solve a large scale convex quadratic problem. Decomposition algorithm is a simple and effective method for solving SVM and its main technique is how to select a working set. Privacy preserving support vector machine(PPSVM) is a new research field on the base of privacy preserving data mining(PPDM) algorithm. PPSVM is widely applied in bank, insurance company, medical research institute. This paper mainly focuses on the simplified decomposition algorithm for soving SVM and PPSVM for distributed data, and the main work is as follows:Firstly, We overview current research on SVM and show our main works.As we know, the critical problem is to solve a convex quadratic programming problem for both original SVM model and privacy preserving support vectro machine model which we mainly discussed in our dissertation.In Chapter 2, Based on the significance of Support Vector in general simplified algorithms, We theoretically analyze the relation between the Support Vectors and the corresponding multipliers and set forth the geometrical relation between the support vectors and the decision surface by making the graph. Furthermore, we also analyze the geometrical meaning of the pair of violating KKT condition by analyzing the termination conditions.In Chapter 3, By analyzing and constrasting all kinds of working set selection method, we put forward a new decomposition algorithm for soving a kind of large scale SVM model with a single linear equality constraint and box constraints. At each iteration, a descent search direction is selected among a suitable set of sparse feasible directions which have even components to reduce the iteration numbers. The global convergence of the algorithm model is proved by assuming the points of the level set have at least one group index strictly between the lower and upper bounds. Numerical experiments show that our algorithm is effective.In next chapters, we focus our attention on privacy preserving support vector machine algorithm.In Chapter 4 and Chapter 5, two novel privacy-preserving support vector machine (PPSVM) classifiers are put forward for vertically partitioned data and horizontally partitioned data. For vertically partitioned data, the classifier is simple and direct, and it does not reveal the privately-held data. For horizontally partitioned data, by secure multi-party computation technique, the proposed SVM classifier is public but does not reveal the privately-held data. We prove the feasibility of our algorithms by using matrix factorization theory and Our PPSVM algorithms have accuracy comparable to that of an ordinary SVM classifier based on the original data. Numerical experiments show the security without using the secure multi-party computation.In Chapter 6, by a kind of security technique for soving the multiplication of two matrices in chapter 5, we put forward a novel privacy-preserving support vector machine (SVM) classifier on arbitrary partitioned data. The proposed SVM classifier, which is public but does not reveal the privately-held data, has accuracy comparable to that of an ordinary SVM classifier based on the original data. We prove the feasibility of our algorithms by using matrix factorization theory and show the security by using the secure multi-party computation.