Grid–SVC: An Improvement in SVC Algorithm, Based On Grid Based Clustering

Authors: Farhad Hadinejad, Hasan Saberi, Saeed Kazem

Abstract:

Support vector clustering (SVC) is an important kernelbased clustering algorithm in multi applications. It has got two main bottle necks, the high computation price and labeling piece. In this paper, we presented a modified SVC method, named Grid–SVC, to improve the original algorithm computationally. First we normalized and then we parted the interval, where the SVC is processing, using a novel Grid–based clustering algorithm. The algorithm parts the intervals, based on the density function of the data set and then applying the cartesian multiply makes multi-dimensional grids. Eliminating many outliers and noise in the preprocess, we apply an improved SVC method to each parted grid in a parallel way. The experimental results show both improvement in time complexity order and the accuracy.

Keywords: Grid–based clustering, SVC, Density function, Radial basis function.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1088288

References:

[1] J. Han and M. Kamber, Data Mining: Concepts and Techniques, 2nd ed. San Francisco: Morgan Kaufmann, 2006, ch. 7, pp. 308–466.
[2] J. A. Hartigan and M. A. Wong, “A K-Means Clustering Algorithm,” J. ROY. STAT. SOC. C-APP., pp. 100–108, 1979.
[3] M. J. Brusco and H. F. K¨ohn, “Optimal partitioning of a data set based on the P-median model,” Psychometrika., vol. 73, pp. 89–105, Murch 2008.
[4] M. Ester, H. P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” Proceedings of Second International Conference on Knowledge Discovery and Data Mining, Portland, pp. 226–231, 1996.
[5] D. Horn, A. BenHur, H. Siegelmann, and V. Vapnik, “A support vector method for clustering,” in Advances in Neural Information ProcessingSystems, ser. Proceedings of the 2000 Conference, T. Leen, T. Dietterich, and V. Tresp, Eds., vol. 13. MIT Press, 2001, pp. 367– 373.
[6] D. Horn, “Clustering via hilbert space,” Physica A, vol. 302, pp. 70–79, 2001.
[7] L. Ping, Z. Chun-Guang, and Z. Xu, “Improved support vector clustering,” ENG. APPL. ARTIF. INTEL., vol. 23, pp. 552–559, 2010.
[8] Y. Sun, Y. Wang, J. Wang, W. Du, and C. Zhou, “A novel svc method based on k-means,” in Second International Conference on Future Generation Communication and Networking, 2008, pp. 55–58.
[9] J. Lee and D. Lee, “An improved cluster labeling method for support vector clustering,” IEEE. T. PATTERN. ANAL., pp. 461–464, 2005.
[10] M. D. Buhmann, Radial Basis Functions: Theory and Implementations. New York: Cambridge University Press, 2004.
[11] C. Aggarwal, C. Procopiuc, J. Wolf, P. S. Yu, and J. S. Park, “Fast algorithms for projected clustering,” in In Proc. 1999 ACM-SIGMOD, Int. Conf. Management of Data (SIGMOD99), philadelphia, PA, June 1999, pp. 61–72.
[12] R. Aggrawal, J. Gehrke, D. Gunopulos, and P. Raghavan, “Automatic subspace clustering of high dimensional data for data mining applications,” in Management of Data (SIGMOD98).
[13] S. Russel and P. Norving, Artificial Intelligence, A modern approach (pages 32-57), 2nd ed. Prentice Hall, 2003.
[14] R. A. Fisher, “The use of multiple measurments in taxonomic problems,” Annals of Eugenics, pp. 179–188, 1936.
[15] R. Fletcher, Practical Methods of Optimization. Chichester: Wiley- Interscience, 1987.
[16] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions. New York: Dover Publications, 1972.
[17] T. Zheng, L. Xiaobin, and J. Yanwei, “Disturbing analysis on spectrum clustering,” Science in China(SeriesE), vol. 37, no. 4, pp. 527–543, 2007.
[18] www.maplesoft.com.
[19] A. BenHur, D. Horn, H. Siegelmann, and V. Vapnik, “Support vector clustering,” Machine Learning Research, vol. 2, pp. 125–137, 2001.
[20] A. J. Khattak, S. I. A.Tirmizi, and S. U. Islam, “Application of meshfree collocation method to a class of nonlinear partial differential equations,” ENG. ANAL. BOUND. ELEM., vol. 33, pp. 661–667, 2009.
[21] M. Dehghan and A. Shokri, “A meshless method for numerical solution of the one-dimensional wave equation with an integral condition using radial basis functions,” Numer. Algorithms., vol. 52, pp. 461–477, 2009.
[22] “Numerical solution of the nonlinear Klein-Gordon equation using radial basis functions,” J. Comput. Appl. Math., vol. 230, pp. 400–410, 2009.
[23] S. U. Islam, S. Haqb, and A. Ali, “A meshfree method for the numerical solution of the RLW equation,” J. Comput. Appl. Math., vol. 223, pp. 997–1012, 2009.
[24] M. D. Buhmann, “Radial basis functions,” Acta Numerica, vol. 16, pp. 1–38, 2000.
[25] S. Sarra, “Adaptive radial basis function method for time dependent partial differential equations,” Appl. Numer. Math., vol. 54, pp. 79–94, 2005.
[26] H. Wendland, Scattered Data Approximation. New York: Cambridge University Press, 2005.