150
5: Mahesh Pal, Pakorn Watanachaturaporn
The number of classifiers created by this method is generally much larger
than the previous method. However, the number of training data vectors required for each classifier is much smaller. The ratio of training data vector size
for one class against another is also 1 : 1. Therefore, this method is considered
more symmetric than the one-against -the-rest method. Moreover, the memory
required to create the kernel matrix K (Xi, Xj) is much smaller. However, the
main disadvantage of this method is the increase in the number of classifiers
as the number of classes increases. For example, for a ten class problem, 45
classifiers will be created.
5.4.3
Classification based on Decision Directed Acyclic Graph
and Decision Tree Structure
Platt et al. (2000) proposed a multiclass classification method called Directed
Acyclic Graph SVM (DAGSVM) based on the Decision Directed Acyclic Graph
(DDAG) structure that has a tree-like structure (see Fig. 5.4). The DDAG
method in essence is similar to pairwise classification in that, for an M class
classification problem, the number of binary classifiers is equal to !M(M - 1)
and each classifier is trained to classify two classes of interest. Each classifier
is treated as a node in the graph structure. Nodes in DDAG are organized in
a triangle with the single root node at the top and increasing thereafter in an
increment of one in each layer until the last layer that will have M nodes. The
i-node in layer j < M is connected to the ith and (i + 1)th nodes in the (j + 1)th
layer.
The DDAG evaluates an input vector X starting at the root node and moves
to the next layer based on the output values. For instance, it exits to the left
edge if the output from the binary classifier is negative, and it exits to the right
edge if the output from the binary classifier is positive. The binary classifier
of the next node is then evaluated. The path followed is called the evaluation
path. The DDAG method basically eliminates one class from the list at each
layer. The list initially contains all the classes. Each node evaluates the first class
against the last class in the list. For example, the root node evaluates class 1
against class M. The evaluation at each layer results in one class out of the two
classes, and the other class is eliminated from the list. The process then tests
the first and the last class in the new list. The procedure is terminated when
only one class remains in the list. The class label associated with the input data
will be the class label of the node in the final layer of the evaluation path or the
class remaining in the list. Although the number of binary classifiers is still the
same as in the pairwise classification method, the inputs are evaluated M - 1
times instead of ! M(M - 1) times.
A classification based on a decision tree structure has also been proposed by
Takahashi and Abe (2002). Each node of the decision tree structure is a binary
classifier that separates either one class or some number of classes from the
remaining classes. The number of binary classifiers needed by this approach
is equal to M - 1. However, there are numerous ways to build the decision
5: Mahesh Pal, Pakorn Watanachaturaporn
The number of classifiers created by this method is generally much larger
than the previous method. However, the number of training data vectors required for each classifier is much smaller. The ratio of training data vector size
for one class against another is also 1 : 1. Therefore, this method is considered
more symmetric than the one-against -the-rest method. Moreover, the memory
required to create the kernel matrix K (Xi, Xj) is much smaller. However, the
main disadvantage of this method is the increase in the number of classifiers
as the number of classes increases. For example, for a ten class problem, 45
classifiers will be created.
5.4.3
Classification based on Decision Directed Acyclic Graph
and Decision Tree Structure
Platt et al. (2000) proposed a multiclass classification method called Directed
Acyclic Graph SVM (DAGSVM) based on the Decision Directed Acyclic Graph
(DDAG) structure that has a tree-like structure (see Fig. 5.4). The DDAG
method in essence is similar to pairwise classification in that, for an M class
classification problem, the number of binary classifiers is equal to !M(M - 1)
and each classifier is trained to classify two classes of interest. Each classifier
is treated as a node in the graph structure. Nodes in DDAG are organized in
a triangle with the single root node at the top and increasing thereafter in an
increment of one in each layer until the last layer that will have M nodes. The
i-node in layer j < M is connected to the ith and (i + 1)th nodes in the (j + 1)th
layer.
The DDAG evaluates an input vector X starting at the root node and moves
to the next layer based on the output values. For instance, it exits to the left
edge if the output from the binary classifier is negative, and it exits to the right
edge if the output from the binary classifier is positive. The binary classifier
of the next node is then evaluated. The path followed is called the evaluation
path. The DDAG method basically eliminates one class from the list at each
layer. The list initially contains all the classes. Each node evaluates the first class
against the last class in the list. For example, the root node evaluates class 1
against class M. The evaluation at each layer results in one class out of the two
classes, and the other class is eliminated from the list. The process then tests
the first and the last class in the new list. The procedure is terminated when
only one class remains in the list. The class label associated with the input data
will be the class label of the node in the final layer of the evaluation path or the
class remaining in the list. Although the number of binary classifiers is still the
same as in the pairwise classification method, the inputs are evaluated M - 1
times instead of ! M(M - 1) times.
A classification based on a decision tree structure has also been proposed by
Takahashi and Abe (2002). Each node of the decision tree structure is a binary
classifier that separates either one class or some number of classes from the
remaining classes. The number of binary classifiers needed by this approach
is equal to M - 1. However, there are numerous ways to build the decision