Browse Prior Art Database

2n-Tree Classifiers

IP.com Disclosure Number: IPCOM000121693D
Original Publication Date: 1991-Sep-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 4 page(s) / 204K

Publishing Venue

IBM

Related People

Dom, BE: AUTHOR [+2]

Abstract

This invention is a scheme for doing pattern classification. It has two major aspects: (1) the classifier itself, which is a lookup table (LUT) implemented as a 2n-tree; and (2) training schemes specific to the 2n-tree structure.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 28% of the total text.

2n-Tree Classifiers

      This invention is a scheme for doing pattern
classification. It has two major aspects:  (1) the classifier itself,
which is a lookup table (LUT) implemented as a 2n-tree; and (2)
training schemes specific to the 2n-tree structure.

      In what follows, it is assumed that objects (e.g., patterns)
are being classified by performing a set of feature measurements,
thus forming a feature vector (x = {xi}) corresponding to the object.
These feature vectors identify points in feature space.  The feature
space is either explicitly or implicitly segmented into various
regions corresponding to the various classes of objects. The task of
the classifier, in this model, is to identify the region containing
the feature vector and thereby label it (the vector), while the task
of the training procedure is to perform the segmentation of feature
space and represent it in a form usable by the classifier.
The Classification Tree

      It is assumed that the features are represented as m-bit binary
integers.  Thus, the feature space is discrete and occupies a finite
n-dimensional hypercube of side length 2m .  The classification tree
used in this invention corresponds to the following recursive
decomposition of that feature space.  Each node in the tree is either
a leaf or an interior node (decision node) with 2n children.  The
root node of the tree corresponds to the entire feature space and the
set of all its children corresponds to the complete feature space
divided into 2n nonoverlapping, equally-sized hypercubes, each 2m-1
on a side, and each of their children corresponds to a hypercube of
size 2m-2, and so on.  The tree may be diagrammed in the standard
two-dimensional form as follows.

      First, an arbitrary ordering of the features is selected.  This
ordering is indicated by the subscripts {x1,x2,...}, etc.  The
branches originating at the root node are then labeled by the
high-order bits of the features. Thus, the leftmost branch would
correspond to all feature high-order bits being 0, and the next one
to the right would correspond to only the nth feature having its
high-order bit equal to 1, etc., with the rightmost branch
corresponding to all high- order bits being 1's.  At the next level
(level 1), the next to the highest order bits are tested and so on
with low-order bits being tested at m-1 level nodes, all mth level
nodes being leaves.  For n = 2, the tree takes the form of the
well-known quadtree data structure.

      When the tree is ready to be used for classification (i.e., it
has been "trained"), the leaves contain class labels.  A feature
vector is classified by searching down the tree, accessing smaller
and smaller cells of feature space that contain the feature vector,
until a leaf is reached.  The class label stored at that leaf is then
assigned to the vector in question.
Training Algorithms

      Straightforwad LUT Programming (SLP):  In this case, any
classifier tra...