An Improved Algorithm For Inverse Problem Of Svms Based On Clustering

Support vector machines are very important classification technique in the field of machine learning, this theory is based on statistical learning theory. Because of its good generalization capability, this classification technique has been applied to many fields, but the disadvantage of high time complexity is the reason why this excellent classification technique can't have further development. The proposition of inverse problem of SVMs is motivated by designing a heuristic algorithm for generating decision trees with high generalization capability. The inverse problem is how to split a given dataset into two clusters such that the margin between the two clusters attains maximum. The incredible time complexity makes it difficult to apply to the data with certain scale. Our works concerns how to improve the efficiency of solving the inverse problem of SVMs.An improved algorithm for inverse problem of SVMs based on clustering is proposed based on the thorough research to the inverse problem. First, the reason why the time complexity of solving this problem is very high is discussed; enumerating all the possible cases is recognized as the problem. Second, the characteristic of clustering is analyzed, and finding that clustering is helpful to decrease the time complexity of solving the inverse problem. A new strategy is proposed as follows:performing the data preprocessing, converging the data into limited number of clusters, we replace the original algorithm which enumerating all the splitting in all points by getting the best splitting in all clusters. Finally, the proposed algorithm is implemented and some experiments are presented, also we comparing it with the algorithm which converging the data by K-means clustering algorithm. The experiment results show that the proposed algorithm is efficient and reasonable.