Transcript Overview of SVM - Carleton University

On Utillizing LVQ3-Type
Algorithms to Enhance
Prototype Reduction Schemes
Sang-Woon Kim and B. John Oommen*
Myongji University, Carleton University*
Outline of the Study





Introduction
Overview of the Prototype Reduction Schemes
The Proposed Reduction Method
Experiments & Discussions
Conclusions
Workshop on PRIS’ 2002
Introduction (1)
 The Nearest Neighbor (NN) Classifier :
 A widely used classifier, which is simple and yet one
of the most efficient classification rules in practice.
 However, its application often suffers from the
computational complexity caused by the huge
amount of information.
Workshop on PRIS’ 2002
Introduction (2)
 Solving strategies to the problem :
 Reducing the size of the design set without sacrificing
the performance.
 Accelerating the speed of computation by eliminating
the necessity of calculating many distances.
 Increasing the accuracy of the classifiers designed
with limited samples.
Workshop on PRIS’ 2002
Motivation of the Study
In NN classifications, prototypes near the
boundary play more important roles.
The prototypes need to be moved or adjusted
towards the classification boundary.
The proposed approach is based on this
philosophy, namely that of creating and
adjusting.
Workshop on PRIS’ 2002
Prototype Reduction Schemes
- Conventional Approaches -
 The Condensed Nearest Neighbor (CNN) :
 The RNN, SNN, ENN, mCNN rules
 The Prototypes for Nearest Neighbor (PNN)
classifiers
 The Vector Quantization (VQ) & Bootstrap (BT)
techniques
 The Support Vector Machines (SVM)
Workshop on PRIS’ 2002
A Graphical Example (PNN)
Workshop on PRIS’ 2002
LVQ3 Algorithm
 An improved LVQ algorithm :
 Learning Parameters :
 Initial vectors
 Learning rates :
 Iteration numbers
 Training Set = Placement + Optimizing:
Workshop on PRIS’ 2002
Support Vector Machines (SVM)
 The SVM has a capability of extracting vectors which
support the boundary between two classes, and they
can satisfactorily represent the global distribution
structure.
Workshop on PRIS’ 2002
Extension by Kernels
Workshop on PRIS’ 2002
The Proposed Method
 First, the CNN, PNN, VQ, SVM are employed to
select initial prototype vectors.
 Next, an LVQ3-type learning is performed to
adjust the prototypes:
 Perform the LVQ3 with Tip to select w
 Perform the LVQ3 with Tip to select e
 Repeat the above steps to obtain the best w* and e*
 Finally, determine the best prototypes by
invoking the learning n times with Tip and Tio.
Workshop on PRIS’ 2002
Experiments
 The proposed method is tested with artificial and
real benchmark design data sets, and compared
with the conventional methods.
 The one-against-all NN classifier is designed.
 Benchmark data sets :
Workshop on PRIS’ 2002
Workshop on PRIS’ 2002
Workshop on PRIS’ 2002
Experimental Results (3)
Workshop on PRIS’ 2002
Experimental Results (4)
Workshop on PRIS’ 2002
Data Compression Rates
Workshop on PRIS’ 2002
Classification Error Rates (%)
- Before Adjusting -
Workshop on PRIS’ 2002
Classification Error Rates (%)
- After Adjusting with LVQ3 -
Workshop on PRIS’ 2002
Conclusions
 The method provides a principled way of choosing
prototype vectors for designing NN classifiers.
 The performance of a classifier trained with the
method is better than that of the CNN, PNN, VQ,
and SVM classifier.
 The future work is to expand this study into large
data set problems such as data mining and text
categorization.
Workshop on PRIS’ 2002