background image
Parallelization of the Incremental Proximal
Support Vector Machine Classifier using a
Heap-based Tree Topology
Amund Tveit and H
avard Engum
Department of Computer and Information Science,
Norwegian University of Science and Technology,
N-7491 Trondheim, Norway
{amundt,havare}@idi.ntnu.no
Abstract. Support Vector Machines (SVMs) are an efficient data min-
ing approach for classification, clustering and time series analysis. In
recent years, a tremendous growth in the amount of data gathered has
changed the focus of SVM classifier algorithms from providing accurate
results to enabling incremental (and decremental) learning with new data
(or unlearning old data) without the need for computationally costly re-
training with the old data. In this paper we propose two efficient paral-
lelized algorithms based on heaps of processing nodes for classification
with the incremental proximal SVM introduced by Fung and Mangasar-
ian.
1
Introduction
Support Vector Machines (SVMs) is an exceptionally efficient data mining ap-
proach for classification, clustering and time series analysis [13]. This is pri-
marily due to SVMs highly accurate results that are competitive with other
data mining approaches, e.g. artificial neural networks (ANNs) and evolution-
ary algorithms (EAs). In recent years tremendous growth in the amount of data
gathered (e.g. user clickstreams on the web, in e-commerce and in intrusion de-
tection systems), has changed the focus of SVM classifier algorithms to not only
provide accurate results, but to also enable online learning, i.e. incremental and
decremental learning, in order to handle concept drift of classes [4, 5].
Fung and Mangasarian introduced the Incremental and Decremental Lin-
ear Proximal Support Vector Machine (PSVM) for binary classification [6], and
showed that it was able to be trained extremely fast, i.e. with 1 billion examples
(500 increments of 2 million) in 2 hours and 26 minutes on relatively low-end
hardware (400 MHz Pentium II). This has later been extended to support ef-
ficient support of incremental multicategorical classification [7] and soft-decay
decremental learning [8]. Proximal SVMs has also been shown to perform at a
similar level of accuracy as regular SVMs and at the same time being significantly
faster [9].
126
Parallel and Incremental PSVM Classifiers

<< - < - > - >>