Fast and convergence-guaranteed algorithm for linear separation  

作　　者：LIU ZhiYong ZHANG David LI YuGang 

机构地区：[1]Adcaneed Research Center, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China [2]Center for Multimedia Signal Processing/Department of Computing, Hong Kong Polytechnic University, Kowloon, Hong Kong [3]School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, China [4]Key Laboratory of Computer System and Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China

出　　处：《Science China(Information Sciences)》2010年第4期729-737,共9页中国科学（信息科学）（英文版）

基　　金：supported by the CRC and UGC fund in Hong Kong, the National Natural Science Foundation of China (Grand No. 60752001); the National Basic Research Program of China (Grant No. 2007CB310805)

摘　　要：Efficient linear separation algorithms are important for pattern classification applications. In this paper, an algorithm is developed to solve linear separation problems in n-dimensional space. Its convergence feature is proved. The proposed algorithm is proved to converge to a correct solution whenever the two sets are separable. The complexity of the proposed algorithm is analyzed, and experiments on both randomly generated examples and real application problems were carried out. While analysis shows that its time complexity is lower than SVM that needs computations for quadratic programming optimization, experiment results show that the developed algorithm is more efficient than the least-mean-square （LMS）, and the Perceptron.Efficient linear separation algorithms are important for pattern classification applications. In this paper, an algorithm is developed to solve linear separation problems in n-dimensional space. Its convergence feature is proved. The proposed algorithm is proved to converge to a correct solution whenever the two sets are separable. The complexity of the proposed algorithm is analyzed, and experiments on both randomly generated examples and real application problems were carried out. While analysis shows that its time complexity is lower than SVM that needs computations for quadratic programming optimization, experiment results show that the developed algorithm is more efficient than the least-mean-square （LMS）, and the Perceptron.

关 键 词：linear separation problem classification CONVERGENCE EFFICIENCY COMPLEXITY 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术] TP18[自动化与计算机技术—计算机科学与技术]