We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Fatemeh Azmandian, Ayse Yilmazer, Jennifer G. Dy, Javed A. Aslam, David R. Kaeli. Harnessing the Power of GPUs to Speed Up Feature Selection for Outlier Detection[J]. Journal of Computer Science and Technology, 2014, 29(3): 408-422. DOI: 10.1007/s11390-014-1439-4
Citation: Fatemeh Azmandian, Ayse Yilmazer, Jennifer G. Dy, Javed A. Aslam, David R. Kaeli. Harnessing the Power of GPUs to Speed Up Feature Selection for Outlier Detection[J]. Journal of Computer Science and Technology, 2014, 29(3): 408-422. DOI: 10.1007/s11390-014-1439-4

Harnessing the Power of GPUs to Speed Up Feature Selection for Outlier Detection

More Information
  • Author Bio:

    Fatemeh Azmandian received her M.S. and Ph.D. degrees in computer engineering from Northeastern University, Boston. Dr. Azmanian's publications present the results of her research in utilizing data mining and machine learning techniques for a wide array of applications, including cloud storage, virtualization, cybersecurity, and radiotherapy treatment planning. Since 2012, Dr. Azmandian has brought her skills and talent to EMC Corporation. She is a member of IEEE.

  • Received Date: August 30, 2013
  • Revised Date: January 27, 2014
  • Published Date: May 04, 2014
  • Acquiring a set of features that emphasize the differences between normal data points and outliers can drastically facilitate the task of identifying outliers. In our work, we present a novel non-parametric evaluation criterion for filter-based feature selection which has an eye towards the final goal of outlier detection. The proposed method seeks the subset of features that represent the inherent characteristics of the normal dataset while forcing outliers to stand out, making them more easily distinguished by outlier detection algorithms. Experimental results on real datasets show the advantage of our feature selection algorithm compared with popular and state-of-the-art methods. We also show that the proposed algorithm is able to overcome the small sample space problem and perform well on highly imbalanced datasets. Furthermore, due to the highly parallelizable nature of the feature selection, we implement the algorithm on a graphics processing unit (GPU) to gain significant speedup over the serial version. The benefits of the GPU implementation are two-fold, as its performance scales very well in terms of the number of features, as well as the number of data points.
  • [1]
    Schölkopf B, Smola A, Müller K R. Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 1998, 10(5): 1299-1319.
    [2]
    Kira K, Rendell L A. A practical approach to feature selection. In Proc. the 9th ICML, July 1992, pp.249-256.
    [3]
    Liu H, Motoda H. Feature Selection for Knowledge Discovery and Data Mining. Kluwer Academic Publishers, 1998.
    [4]
    Kohavi R, John G H. Wrappers for feature subset selection. Artificial Intelligence, 1997, 97(1/2): 273-324.
    [5]
    Dash M, Liu H. Feature selection for classification. Intelligent Data Analysis, 1997, 1(1/4): 131-156.
    [6]
    Guyon I, Elisseeff A. An introduction to variable and feature selection. J. Machine Learning Research, 2003, 3: 1157-1182.
    [7]
    Nguyen H V, Gopalkrishnan V. Feature extraction for outlier detection in high-dimensional spaces. In Proc. the 4th Int. Workshop. Feature Selection in Data Mining, June 2010, pp.66-75.
    [8]
    Azmandian F, Yilmazer A, Dy J et al. GPU-accelerated feature selection for outlier detection using the local kernel density ratio. In Proc. the 12th ICDM, December 2012, pp.51-60.
    [9]
    Tibshirani R. Regression shrinkage and selection via the lasso. J. Royal Statistical Society, Series B, 1996, 58(1): 267-288.
    [10]
    Song L, Bedo J, Borgwardt K M et al. Gene selection via the BAHSIC family of algorithms. Bioinformatics, 2007, 23(3): i490-i498.
    [11]
    Wu X, Yu K, Ding W et al. Online feature selection with streaming features. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(5): 1178-1192.
    [12]
    Chen X W, Wasikowski M. FAST: A ROC-based feature selection metric for small samples and imbalanced data classification problems. In Proc. the 14th KDD, August 2008, pp.124-132.
    [13]
    Aggarwal C, Yu S. An effective and effcient algorithm for high-dimensional outlier detection. The VLDB Journal, 2005, 14(2): 211-221.
    [14]
    de Vries T, Chawla S, Houle M E. Density-preserving projections for large-scale local anomaly detection. Knowledge and Information Systems, 2012, 32(1): 25-52.
    [15]
    Branch J W, Giannella C, Szymanski B K et al. In-network outlier detection in wireless sensor networks. Knowledge and Information Systems, 2013, 34(1): 23-54.
    [16]
    Hido S, Tsuboi Y, Kashima H et al. Statistical outlier detection using direct density ratio estimation. Knowledge and Information Systems, 2011, 26(2): 309-336.
    [17]
    Sugiyama M, Yamada M, von Bünau P et al. Direct densityratio estimation with dimensionality reduction via leastsquares hetero-distributional subspace search. Neural Networks, 2011, 24(2): 183-198.
    [18]
    Smola A, Song L, Teo C H. Relative novelty detection. In Proc. the 12th AISTATS, April 2009, pp.536-543.
    [19]
    Hawkins D M. Identification of Outliers. London, New York: Chapman and Hall, 1980.
    [20]
    Breunig M M, Kriegel H P, Ng R T et al. LOF: Identifying density-based local outliers. ACM SIGMOD Record, 2000, 29(2): 93-104.
    [21]
    Horn R A, Johnson C R. Matrix Analysis. Cambridge, New York: Cambridge University Press, 1985.
    [22]
    Balcan M F, Blum A. On a theory of learning with similarity functions. In Proc. the 23rd International Conference on Machine Learning (ICML), June 2006, pp.73-80.
    [23]
    Parzen E. On estimation of a probability density function and mode. The Annals of Mathematical Statistics, 1962, 33(3): 1065-1076.
    [24]
    Rosenblatt M. Remarks on some nonparametric estimates of a density function. The Annals of Mathematical Statistics, 1956, 27(3): 832-837.
    [25]
    Devijver P A, Kittler J. Pattern Recognition: A Statistical Approach. Englewood Cliffs, NJ: Prentice Hall, 1982.
    [26]
    Masaeli M, Fung G, Dy J G. From transformation-based dimensionality reduction to feature selection. In Proc. the 27th ICML, June 2010, pp.751-758.
    [27]
    Kirk D B, Hwu W W. Programming Massively Parallel Processors: A Hands-on Approach (Applications of GPU Computing Series). Morgan Kaufmann Publishers, 2010.
    [28]
    Lv Q, Josephson W,Wang Z et al. Multi-probe LSH: Effcient indexing for high-dimensional similarity search. In Proc. the 33rd VLDB, Sept. 2007, pp.950-961.
    [29]
    Arya S, Mount D M, Netanyahu N S et al. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM, 1998, 45(6): 891-923.
    [30]
    Garcia V, Debreuve E, Barlaud M. Fast k nearest neighbor search using GPU. In Proc. Workshop on Computer Vision and Pattern Recognition, June 2008.
    [31]
    Azmandian F, Dy J G, Aslam J A et al. Local kernel density ratio-based feature selection for outlier detection. In Proc. the 4th Asian Conf. Machine Learning, Nov. 2012, pp.49-64.
    [32]
    Güvenir H A, Acar B, Demiröz G et al. A supervised machine learning algorithm for arrhythmia analysis. In Proc. Computers in Cardiology Conference, September 1998, pp.433-436.
  • Related Articles

    [1]Jian Chen, Kai-Qi Zhang, Tian Ren, Zhen-Qing Wu, Hong Gao. GAM: A GPU-Accelerated Algorithm for MaxRS Queries in Road Networks[J]. Journal of Computer Science and Technology, 2022, 37(5): 1005-1025. DOI: 10.1007/s11390-022-2330-3
    [2]Zhi-Guang Chen, Yu-Bo Liu, Yong-Feng Wang, Yu-Tong Lu. A GPU-Accelerated In-Memory Metadata Management Scheme for Large-Scale Parallel File Systems[J]. Journal of Computer Science and Technology, 2021, 36(1): 44-55. DOI: 10.1007/s11390-020-0783-9
    [3]Sunghun Jo, Yuna Jeong, Sungkil Lee. GPU-Driven Scalable Parser for OBJ Models[J]. Journal of Computer Science and Technology, 2018, 33(2): 417-428. DOI: 10.1007/s11390-018-1827-2
    [4]Jing Li, Lei Liu, Yuan Wu, Xiang-Hua Liu, Yi Gao, Xiao-Bing Feng, Cheng-Yong Wu. Pragma Directed Shared Memory Centric Optimizations on GPUs[J]. Journal of Computer Science and Technology, 2016, 31(2): 235-252. DOI: 10.1007/s11390-016-1624-8
    [5]Peng Du, Jie-Yi Zhao, Wan-Bin Pan, Yi-Gang Wang. GPU Accelerated Real-time Collision Handling in Virtual Disassembly[J]. Journal of Computer Science and Technology, 2015, 30(3): 511-518. DOI: 10.1007/s11390-015-1541-2
    [6]Yun-Cen Huang, Jie-Qing Feng, Matthias NieBner, Yuan-Min Cui, Baoguang Yang. Feature-Adaptive Rendering of Loop Subdivision Surfaces on Modern GPUs[J]. Journal of Computer Science and Technology, 2014, 29(6): 1014-1025. DOI: 10.1007/s11390-014-1486-x
    [7]Yan Li, Yun-Quan Zhang, Yi-Qun Liu, Guo-Ping Long, Hai-Peng Jia. MPFFT: An Auto-Tuning FFT Library for OpenCL GPUs[J]. Journal of Computer Science and Technology, 2013, 28(1): 90-105. DOI: 10.1007/s11390-013-1314-8
    [8]Jie-Yi Zhao, Min Tang, Ruo-Feng Tong. Connectivity-Based Segmentation for GPU-Accelerated Mesh Decompression[J]. Journal of Computer Science and Technology, 2012, 27(6): 1110-1118. DOI: 10.1007/s11390-012-1289-x
    [9]Chun-Tao Hong, De-Hao Chen, Yu-Bei Chen, Wen-Guang Chen, Wei-Min Zheng, Hai-Bo Lin. Providing Source Code Level Portability Between CPU and GPU with MapCG[J]. Journal of Computer Science and Technology, 2012, 27(1): 42-56. DOI: 10.1007/s11390-012-1205-4
    [10]Feng Wang , Can-Qun Yang, Yun-Fei Du, Juan Chen, Hui-Zhan Yi, Wei-Xia Xu. Optimizing Linpack Benchmark on GPU-Accelerated Petascale Supercomputer[J]. Journal of Computer Science and Technology, 2011, 26(5): 854-865. DOI: 10.1007/s11390-011-0184-1

Catalog

    Article views (21) PDF downloads (1483) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return