Feng GAO, Wenzhu SUN, Jianling QU, Yazhou DI, Yang CHEN

Heuristic sample reduction method for support vector data description

Support vector data description (SVDD) has become one of the most promising methods for one-class classification for finding the boundary of the training set. However, SVDD has a time complexity of O (N 3 ) and a space complexity of O (N 2 ). When dealing with very large sizes of training sets, e.g., a training set of the aeroengine gas path parameters with the size of N > 106 sampled from several months of flight data, SVDD fails. To solve this problem, a method called heuristic sample reduction (HSR) is proposed for obtaining a reduced training set that is manageable for SVDD. HSR maintains the classification accuracy of SVDD by building the reduced training set heuristically with the samples selected from the original. For demonstration, several artificial datasets and real-world datasets are used in the experiments. In addition, a practical example of the training set of the aeroengine gas path parameters is also used to compare the performance of SVDD based on the proposed HSR with conventional SVDD and other improved methods. The experimental results are very encouraging.

PDF

___

[1] Tax D, Duin RP. Support vector domain description. Pattern Recognit Lett 1999; 20: 11911199.
[2] Tax D. One class classification: concept-learning in the absence of counter-examples. PhD, University of Delft, Delft, the Netherlands, 2001.
[3] Guo SM, Chen LC, Tsai JSH. A boundary method for outlier detection based on support vector domain description. Pattern Recognit 2009; 42: 7783.
[4] Lee K, Kim DW, Lee D, Lee KH. Improving support vector data description using local density degree. Pattern Recognit 2005; 38: 17681771.
[5] Wang S, Yu J, Lapira E, Lee J. A modified support vector data description based novelty detection approach for machinery components. Appl Soft Comput 2012; 13: 11931205.
[6] Peng X, Xu D. Efficient support vector data descriptions for novelty detection. Neural Comput Appl 2012; 21: 20232032.
[7] Liu YH, Liu YC, Chen YJ. Fast support vector data descriptions for novelty detection. IEEE T Neural Networ 2010; 21: 12961313.
[8] Park J, Kang D, Kim J, Kwok JT, Tsang IW. SVDD-based pattern denoising. Neural Comput 2007; 19: 19191938.
[9] Camastra F, Verri A. A novel kernel method for clustering. IEEE T Pattern Anal 2005; 27: 801805.
[10] Ben-Hur A, Horn D, Siegelmann HT, Vapnik V. Support vector clustering. J Mach Learn Res 2002; 2: 125137.
[11] Huang G, Chen H, Zhou Z, Yin F, Guo K. Two-class support vector data description. Pattern Recognit 2011; 44: 320329.
[12] Choi YS. Least squares one-class support vector machine. Pattern Recognit Lett 2009; 30: 12361240.
[13] Platt JC. Fast training of support vector machines using sequential minimal optimization. In: Sch¨olkopf B, Burges CJC, Smola AJ, editors. Advances in Kernel MethodsSupport Vector Learning. Cambridge, MA, USA: MIT Press, 1999. pp. 185208.
[14] Sch¨olkopf B, Platt JC, Shawe-Taylor J, Smola AJ, Williamson RC. Estimating the support of a high-dimensional distribution. Neural Comput 2001; 13: 14431471.
[15] Kim PJ, Chang HJ, Song DS, Choi JY. Fast support vector data description using k-means clustering. In: ISNN 2007 4th International Symposium on Neural Networks; 37 June 2007; Nanjing, China. pp. 506514.
[16] Hart PE. The condensed nearest neighbor rule. IEEE T Inform Theory 1968; 14: 515516.
[17] Gates GW. The reduced nearest neighbor rule. IEEE T Inform Theory 1972; 18: 431433.
[18] Ritter G, Woodruff H, Lowry S, Isenhour T. An algorithm for a selective nearest neighbor decision rule. IEEE T Inform Theory 1975; 21: 665669.
[19] Hastie T, Tibshirani R. Discriminant adaptive nearest neighbor classification. IEEE T Pattern Anal 1996; 18: 607616.
[20] Wilson DR, Martinez TR. Reduction techniques for instance-based learning algorithms. Mach Learn 2000; 38: 257286.
[21] Aha DW, Kibler D, Albert MK. Instance-based learning algorithms. Mach Learn 1991; 6: 3766.
[22] Rico-Juan JR, Inesta JM. New rank methods for reducing the size of the training set using the nearest neighbor rule. Pattern Recognit Lett 2012; 33: 654660.
[23] Angiulli F. Prototype-based domain description for one-class classification. IEEE T Pattern Anal 2012; 34: 1131 1144.
[24] Yuan Y. Forecasting the movement direction of exchange rate with polynomial smooth support vector machine. Math Comput Model 2012; 57: 932944.
[25] Camps-Valls G, Martin-Guerrero J, Rojo-Alvarez J, Soria-Olivas. Fuzzy sigmoid kernel for support vector classifiers. Neurocomputing 2004; 62: 501506.
[26] Yuan C, Casanent D. Support vector machines for class representation and discrimination. In: International Joint Conference on Neural Networks; 2024 July 2003; Portland, OR, USA. pp. 16101615.
[27] Su T, Dy J. A deterministic method for initializing K-means clustering. In: 16th IEEE International Conference on Tools with Artificial Intelligence; 1517 November 2004; Boca Raton, FL, USA. pp. 784789.
[28] Hamerly G, Elkan C. Learning the k in k-means. Adv Neural Inf Process Syst 2004; 16: 281.
[29] Bischof H, Leonardis A, Selb A. MDL principle for robust vector quantisation. Pattern Anal Appl 1999; 2: 5972.
[30] Bradley AP. The use of the area under the ROC curve in the evaluation of machine learning algorithms. Pattern Recognit 1997; 30: 11451159.
[31] Hu L, Hu NQ, Qin GJ. Support vector machines detection method for turbopump test data analysis. J Propul Technol 2008; 29: 244248.
[32] Refaeilzadeh P, Tang L, Liu H. Cross-validation. In: Liu L, Ozsu MT, editors. Encyclopedia of Database Systems. ¨ Berlin, Germany: Springer, 2009. pp. 532538.