Low-Density Cut Based Tree Decomposition for Large-Scale SVM Problems

Lifang He, Hong-Han Shuai, Xiangnan Kong, Zhifeng Hao, Xiaowei Yang, Philip S. Yu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

The current trend of growth of information reveals that it is inevitable that large-scale learning problems become the norm. In this paper, we propose and analyze a novel Low-density Cut based tree Decomposition method for large-scale SVM problems, called LCD-SVM. The basic idea here is divide and conquer: use a decision tree to decompose the data space and train SVMs on the decomposed regions. Specifically, we demonstrate the application of low density separation principle to devise a splitting criterion for rapidly generating a high-quality tree, thus maximizing the benefits of SVMs training. Extensive experiments on 14 real-world datasets show that our approach can provide a significant improvement in training time over state-of-the-art methods while keeps comparable test accuracy with other methods, especially for very large-scale datasets.

Original languageEnglish
Title of host publicationProceedings - 14th IEEE International Conference on Data Mining, ICDM 2014
EditorsRavi Kumar, Hannu Toivonen, Jian Pei, Joshua Zhexue Huang, Xindong Wu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages839-844
Number of pages6
Volume2015-January
EditionJanuary
ISBN (Electronic)9781479943029
DOIs
StatePublished - 26 Jan 2015
Event14th IEEE International Conference on Data Mining, ICDM 2014 - Shenzhen, China
Duration: 14 Dec 201417 Dec 2014

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
NumberJanuary
Volume2015-January
ISSN (Print)1550-4786

Conference

Conference14th IEEE International Conference on Data Mining, ICDM 2014
CountryChina
CityShenzhen
Period14/12/1417/12/14

Keywords

  • Support vector machines
  • decision tree
  • large scale
  • splitting criterion

Fingerprint Dive into the research topics of 'Low-Density Cut Based Tree Decomposition for Large-Scale SVM Problems'. Together they form a unique fingerprint.

Cite this