Relative density based support vector machine

摘要

As a support vector machine (SVM) has good generalization ability, it has been implemented in various applications. Yet in the process of resolving the mathematical model, it needs to compute the kernel matrix, the dimension of which is equal to the number of data points in the dataset, thereby costing a very high amount of memory. Some improved algorithms are proposed to extract the boundary of the dataset so that the number of data points participating in the training process decreases and the training process can be accelerated. But the prediction accuracy of most of these algorithms is so low that many support vectors are discarded. Moreover, those methods all need to perform the main computation by the kernel function in linear feature space, which increases the computational cost. In this paper, the concept "relative density" is proposed to extract the subset containing support vectors. The measure "relative density" is designed to be more meticulous so that the new method performs more precisely than existing methods. The proposed method makes use of the fact that it has good local characteristics to perform the computations in original space without having to use any kernel function. Therefore, efficiency is also improved. Furthermore, the proposed method can be used to detect noise data, by which an inseparable problem can be transformed into a separable problem so that cross validation can be avoided in various SVM algorithms. This is an advantage that none of the existing SVM methods has. Yet another advantage of this method is that it can be considered as a framework to be used in various SVM methods. This paper presents the details of the proposed accelerated algorithm, having a time complexity of O(n log n), that decreases training time significantly without decreasing prediction accuracy. The effectiveness and efficiency of the method is demonstrated through experiments on artificial and public datasets.