2. Prototype-Construction Problem and Its Solution
We assume that a set of training samples is given and that the samples' class types are also specified. Each sample is represented as a vector in n-dimensional Euclidean space. For two vectors v = (v1, v2, …, vn) and w = (w1, w2, …, wn) in this space, their distance is defined as
1. Introduction
In pattern recognition, one deals with either binary classification in which each object is classified as one of two classes, or multi-class classification in which each object is classified as one of N classes, N > 2. SVM (Vapnik [11]) is very effective for binary classification and it can be used for multi-classification by decomposing the problem into binary classification sub-problems. Two useful methods for decomposing the problem (Hsu and Lin [1]) are one-against-one (Knerr et al. [5]) and DAGSVM (Platt et al. [8]). In the training phase, both methods require solving N(N-1)/2 binary classification problems. In the testing phase, the one-against-one technique conducts N(N-1)/2 classifications, while DAGSVM technique employs a directed acyclic graph that has N(N1)/2 nodes and N leaves. The number of classifications for each object is reduced to N-1 in DAGSVM. The drawback of SVM is that, when the number of classes N becomes large, it incurs exhaustive amount of training time and produces an extremely large set of support vectors. For large-scale pattern matching, a long-employed approach is the nearest-neighbor (NN) (Dasarathy [3]) classification method. The NN method, which matches each object with all training samples and finds the nearest
dist ( v, w ) = ∑ | vi - wi | 2 .
i =1
n
A prototype can be any n-dimensional vector whose class type is also specified. Let type(x) denote the class type of x, when x is either a sample or a prototype. A set P of prototypes is said to be a solution to the problem of prototype construction if the following condition holds for every sample s. There exists a prototype p in P such that type(p) = type(s) and dist(s, p) < dist(s, q) for all other q in P. If P is a solution for prototype-construction, more than one prototype for the same class type may be found in P. If we examine the attraction domain of each prototype p, defined as the set of all samples for which p is the nearest prototype, we find that it contains samples of the same class type. For this reason, each p in P can serve as the representative of its neighboring samples. We now present a learning algorithm that solves the prototype-construction problem. The algorithm dynamically alters the number of prototypes as well as their locations, and is thus called dynamic algorithm (DA). It is given below.

上一页下一页