Supervised Local Tangent Space Alignment for Classification

1 Introduction

In many pattern recognition problems, original data taken with various capturing devices are usually of high dimensionality. Dimension reduction has emerged with an aim to obtain compact representations of the original data while reducing unimportant factors. It can make the resulting classification more efficient as fewer variables are being considered which reduces the complexity of the resulting classifier. LTSA proposed in [Zhang and Zha, 2004] is an unsupervised method for nonlinear dimension reduction. It does not make use of the class membership of each point to be projected and lacks generalization to new data. Here we extend LTSA to a supervised version and make it suitable in a changing environment.

2 Local Tangent Space Alignment

LTSA maps a data set X = [x1, . . . , xN], xi ∈ Rm globally to a data set Y = [y1, . . . , yN], yi ∈ Rd with d < m. The brief description of LTSA is presented as follows:

1. Finding k nearest neighbors xij of xi, j = 1, . . . , k. Set Xi = [xij, . . . , xik].
2. Extracting local information by calculating the d largest eigenvectors g1, . . . , gd of the correlation matrix (Xi - ¯xieT )T (Xi - ¯xieT ), and setting Gi = [e/√k, g1, . . . , gd]. Here ¯xi = 1k ∑j xij, e is a kdimensional column vector of all ones.
3. Constructing the alignment matrix B (please refer to [Zhang and Zha, 2004] for details) by locally summing with initial B = 0 as follows:

The neighborhood set Ii represents the set of indices for the k nearest-neighbors of xi. I is an N × N identity matrix.

1. Computing the d+1 smallest eigenvectors of B and setting the global coordinates Y = [u2, . . . , ud+1]T corresponding to the 2nd to d + 1st smallest eigenvalues.

3 Supervised LTSA

Our attempt is to adapt LTSA to a situation when the data come incrementally point by point. We assume that the dimensionality of the embedded space does not grow after projecting a new point to it, i.e., d remains constant.

The proposed technique is based on the fact that new points are assumed to come from those parts of the high-dimensional space that have already been explicitly mapped by LTSA. It implies that when a new point arrives, a task of interpolation should be solved. Let X as an input. For a new point xN+1, its closest neighbor xj is looked for from X. If yj is the projection of xj to the embedded space, there must exist a point yN+1 around yj corresponding to xN+1.

LTSA belongs to unsupervised methods; it does not make use of the class membership of each point. Supervised LTSA (SLTSA) is proposed for classification purposes. The term implies that membership information is employed to form the neighborhood of each point. That is, nearest neighbors of a given point xi are chosen only from representatives of the same class as that of xi. This can be achieved by artificially increasing the shift distances between samples belonging to different classes, but leaving them unchanged if samples are from the same class.

In short, SLTSA is designed specially for dealing with data sets containing multiple classes. The results obtained with the unsupervised and supervised LTSA are expected to be different as is shown in Fig.1. The iris data set [Blake and Merz, 1998] includes 150 4-D data belonging to 3 different classes. Here first 100 data points are selected as training samples and mapped from the 4-D input space to a 2-D feature space using LTSA (Fig.1(b)) and SLTSA (Fig.1(a) ) respectively. In Fig.1(b), three class centers on the feature space are completely separated. However in Fig.1(a) two classes (set 2 and 3) overlap such that their boundary cannot be accurately determined. Fig.1(c; d) respectively show the mapping of unknown test samples to the two feature spaces discovered by LTSA and SLTSA. In Fig.1(d), test samples in different classes can be well distributed around class centers. Thus the classification of test samples can be easily implemented on such space.

4 Results

To examine its performance, SLTSA has been applied to a number of data sets varying in number of samples, dimensions and classes.

The binarydigits set discussed here consists of 20×16pixel binary images of preprocessed handwritten digits. In our experiment only three digits: 0, 1 and 2 are dealt with and some of the data are shown in Fig.2(a). 90 of the 117 binary images are used as training samples and others as test samples. It is clear that the 320-dimensional binarydigits data contain many insignificant features, so removing them can make classification more efficient. The results after dimension reduction from 320 to 2 with LTSA and SLTSA are respectively displayed in Fig.2(b) and 2(c) where two coordinate axes represent the two most important features of the binarydigits data. The figures show that the feature space obtained with SLTSA provides better classification information than LTSA. Actually no cases of misclassification in the test samples occurred if using the SLTSA method, but LTSA will result in the error rate of 18.52% in the best case.

Our experimental results confirm that SLTSA generally leads to better classification performance than LTSA when combined with simple classifiers such as k-nn and lda. Beside this, the performance of SLTSA is comparable with supervised LLE [Kouropteva et al., 2002] and finer than with PCA (please refer to the supplementary document). Maybe the reason is that those points on a high-dimensional input space are more likely to lie close on nonlinear rather than

0.05

linear manifolds. Thus, such linear methods as PCA cannot perform well.

5 Conclusions

The supervised version of LTSA was proposed here. It takes into account class membership during selecting neighbors. Another enhancement to LTSA is to generalize it to new data and make it suitable in a changing, dynamic environment.

We compare SLTSA with LTSA, PCA and supervised LLE on a number of data sets, in order to gain insight into what methods are suitable for data classification. The SLTSA method has been shown to yield very promising classification results in our experiments when combined with some simple classifiers.