FRSDE

FRSDE: Fast reduced set density estimator using minimal enclosing ball approximation. Reduced Set Density Estimator (RSDE) is an important technique that can be used to replace the classical Parzen Window estimator (PW) for saving the computational cost. Though RSDE demonstrates a nicer performance in the density accuracy and the computational time compared with several existing methods, it still faces the critical challenge for practical applications because of its high time complexity (no less than O(N 2 )) and space complexity (O(N 2 )) in training the model weighting coefficients on large data sets. In order to overcome this shortcoming, a Fast Reduced Set Density Estimator algorithm (FRSDE) is proposed in this study. First, the relationship between RSDE and the Minimal Enclosing Ball problems (MEB) in computational geometry is revealed. Then, the finding that RSDE is equivalent to a special MEB problem is derived. With this finding, the fast core-set based MEB approximation algorithm is introduced to develop the proposed algorithm FRSDE. Compared with RSDE, FRSDE has the following distinctive advantage: it can guarantee that the upper bound of the time complexity is linear with the size N of a large data set and the upper bound of the space complexity is independent of N. Our experimental results show that the proposed FRSDE has a competitive performance in the density accuracy and an overwhelming advantage over RSDE for large data sets in the data condensation rate and the training time for the weighting coefficients


References in zbMATH (referenced in 15 articles )

Showing results 1 to 15 of 15.
Sorted by year (citations)

  1. Dong, Aimei; Chung, Fu-lai; Wang, Shitong: Semi-supervised classification method through oversampling and common hidden space (2016)
  2. Huang, Chengquan; Chung, Fu-lai; Wang, Shitong: Multi-view L2-SVM and its multi-view core vector machine (2016)
  3. Liu, Ya-Feng; Diao, Rui; Ye, Feng; Liu, Hong-Wei: An efficient inexact Newton-CG algorithm for the smallest enclosing ball problem of large dimensions (2016)
  4. Sreevani; Murthy, C. A.: On bandwidth selection using minimal spanning tree for kernel density estimation (2016)
  5. Wang, Jun; Deng, Zhaohong; Luo, Xiaoqing; Jiang, Yizhang; Wang, Shitong: Scalable learning method for feedforward neural networks using minimal-enclosing-ball approximation (2016)
  6. Hu, Wenjun; Wang, Shitong; Chung, Fu-lai; Liu, Yong; Ying, Wenhao: Privacy preserving and fast decision for novelty detection using support vector data description (2015)
  7. Xie, Zhenping; Sun, Jun; Palade, Vasile; Wang, Shitong; Liu, Yuan: Evolutionary sampling: a novel way of machine learning within a probabilistic framework (2015)
  8. Kulczycki, Piotr; Łukasik, Szymon: An algorithm for reducing the dimension and size of a sample for data exploration procedures (2014)
  9. Xu, Min; Ishibuchi, Hisao; Gu, Xin; Wang, Shitong: Dm-KDE: dynamical kernel density estimation by sequences of KDE estimators with fixed number of components over data streams (2014)
  10. Gu, Xin; Wang, Shitong; Xu, Min: Minimum enclosing ball for domain adaptation (2013)
  11. Hu, Wenjun; Chung, Fu-Lai; Wang, Shitong: The maximum vector-angular margin classifier and its fast training on large datasets using a core vector machine (2012)
  12. Hu, Wenjun; Chung, Fu-Lai; Wang, Shitong; Ying, Wenhao: Scaling up minimum enclosing ball with total soft margin for training on large datasets (2012)
  13. Kristan, Matej; Leonardis, Aleš; Skočaj, Danijel: Multivariate online kernel density estimation with Gaussian kernels (2011)
  14. Wang, Xiaoming; Chung, Fu-Lai; Wang, Shitong: On minimum class locality preserving variance support vector machine (2010)
  15. Deng, Zhaohong; Chung, Fu-Lai; Wang, Shitong: FRSDE: Fast reduced set density estimator using minimal enclosing ball approximation (2008)