Asymmetric Locality Preserving Projection andIts Application to k-Nearest Neighbor Method
Yoshio Iwai Masashi Nishiyama Hiroki Yoshimura
Graduate School of Engineering, Tottori University
iwai@ike.tottori-u.ac.jp
Abstract
In recent years, many methods for data compression
and structure extraction from various types of massive
data using multivariate analysis have been proposed.
The locality preserving projection, which uses a symmetric similarity matrix, is one of these data compression methods. However, the similarity matrix expressing the characteristic of data may often not be symmetric in real. In this study, we propose an asymmetriclocality preserving projection that expands the locality
preserving projection from a symmetric similarity matrix method to one that uses an asymmetric similarity
matrix. We also show the experimental results of its
application to the k-nearest neighbor method as an example.

1

Introduction

In recent years, a large amount of data has become
available online, collected various sensors. The extraction of data structure from large-scale databases formining various information and dimensional compression for reducing the data processing costs are tasks
that often must be performed. Multivariate analysis isoften used for dimensional reduction and structure extraction. Many of these multivariate analysis methods
can be expressed using an extended pairwise representation [1, 2]. Similarly, as is well-known, the locality
preserving projection (LPP) is also expressed using anextended pairwise representation. Because a covariance matrix or a Gramian matrix is used as a statistical index for linking multivariates, it is assumed thatthese matrices are symmetric in the extended pairwise
representation.
An LPP using a symmetric similarity matrix is often
applied to data compression. However, the similarity
matrix expressing the characteristic of data may often
not to be symmetric in real. For example, it is known
that the Smith-Waterman and BLAST scores [3] formeasuring the similarity between DNA and protein sequences in bioinformatics, and the tangent distant kernel [4] and Simpson score [5] used in image classiﬁcation may not be symmetric.
In this research, we propose an extension of the LPP
from a method that uses a symmetric similarity matrix
to one that uses an asymmetric similarity matrix. We
can apply the proposed asymmetric LPP (ALPP) toclassiﬁcation problems that have both label similarityand data proximity. We also present some experimental results to conﬁrm the eﬀectiveness of our method.

2 LPP [6]In this section, we brieﬂy explain the LPP [6].
Let {xi } ∈ Rm be the training data and let X =( x1 x2 · · · xn ) be a data matrix. Further, let
S LPP be a symmetric similarity matrix. Then, the LPP
is expressed as follows:⎡⎤n
12Wopt = arg min ⎣S LPP W xi − W xj  ⎦2 i,j=1 ijW= arg min tr W XLX T W T s.t. W XDX T W T = Im ,W

where L = D − S LPP is called a graph Laplacian matrix and Im is a m-dimensional identity matrix. Inaddition, W expresses a linear mapping that embeds
training data xi into the subspace.
Various similarity matrices can be considered; however, typical similarity matrices are as follows:
LPP=Sij

exp −xi − xj 02γ2xi − xj  < ε,otherwise

orLPP=Sij

10xi ∈ Nε (xj ) ∪ xj ∈ Nε (xi ),otherwise

where  is a constant that determines the neighborhoodand N represents the neighborhood. The above optimization problem results in the following generalized
eigenvalue problem:XLX T W T = λXDX T W T .
The optimized solution W is obtained by arranging theeigenvectors in ascending order of the magnitude of theeigenvalues of the generalized eigenvalue problem.

3 Representation of Asymmetric Similarity
As mentioned above, the LPP assumes that a similarity matrix is a symmetric matrix, but this is notalways the case in the real world. As shown in Fig. 1,
this often occurs when a data point xj is not in its
own neighborhood Nk (xi ) in the k-nearest neighbormethod. In order to apply an asymmetric matrix toa symmetric matrix method, a symmetric matrix series expansion of the asymmetric matrix can be used
to approximate an asymmetric matrix. In this paper,
we utilize the method using the Hermitian matrix proposed by Chino et al. [7].

xjxi

N k (x j )xi ∈N k (x j )4 ALPPx j ∉N k (xi )N k (xi )Figure 1. Asymmetric proximity of a threenearest neighbor method

3.1

Hermitian Representation of Asymmetry [7]Let S be a real asymmetric (so-called general) similarity matrix. Matrix S can be separated into realsymmetric matrix S symm and real alternative matrix
S skew as follows:
S = S symm + S skew ,
sij + sji
S symm =,2

S skew =sij − sji2.

Here, we deﬁne the Hermitian matrix H as follows:
H = S symm + iS skew

(i2 = −1).

Real symmetric matrix S symm is used for the real partof H, and real alternative matrix S skew is used for theimaginary part of H. Because H is an Hermitian matrix, it can be decomposed using a unitary matrix Uand a real diagonal matrix Λ as follows:

Using H deﬁned in the previous section, we can simply rewrite the objective function of the LPP as follows:⎡⎤n
12Wopt = arg min ⎣Hij W xi − W xj  ⎦ .
2 i,j=1
W
Here, as H is a complex matrix, this optimization isa minimization with complex numbers. At a glance,
this objective function itself has no meaning because
the complex numbers cannot be totally ordered1. Notethat when this objective function is concretely calculated, we obtainn

1 Hij W xi − W xj 2
2 i,j=1n=

1
Hij {(W xi ,W xi )−2(W xi ,W xj )+(W xj ,W xj )}2i,j=1=nnn n1
(W xi , W xi )Hij −Hij (W xi , W xj )2 i=1
j=1
i=1 j=1nn1
(W xj , W xj )Hij+
2 j=1i=1

H = U ΛU ∗ ,∗where U is the Hermitian conjugate matrix. Matrix His complex, but the eigenvalue matrix is a real matrix.
Letting U = Ur + iUc , we obtain
H = (Ur ΛUrT + Uc ΛUcT ) + i(Uc ΛUrT − Ur ΛUcT ).
Because the imaginary part Uc is derived from theasymmetric component, the metric obtained from thesymmetric component is corrected by the asymmetriccomponent Uc .
If H is a positive (negative) deﬁnite matrix, concretely, if all the eigenvalues of the eigenvalue matrix
Λ are the same sign, the norm and inner product canbe deﬁned by the following equation:
√11
xH = (x, Hx) = xT U ΛU ∗ x = (Λ 2 U ∗ x, Λ 2 U ∗ x).
This equation is no diﬀerent from the metric calculation used in machine learning, i.e., it is possible toconstruct a Hilbert space with H as the measure.

3.2

Extension of the Hermitian Representationof Asymmetry

As mentioned above, the Chino’s method [7] equallyadds symmetric components and asymmetric components to the Hermitian matrix. In order to control
the eﬀect of asymmetric components on its norm more
freely, we propose the following representation to express asymmetric similarity:
H = (1 − α)S symm + αiS skew

(i2 = −1, 0  α  1).

In this formulation, it is possible to adjust the eﬀectof asymmetric components, such that only asymmetric components are considered when α = 1, and only
symmetric components are considered when α = 0.

=nn1(W xi , W xi )(Hij + Hji )2 i=1
j=1−n nHij (W xi , W xj ).

i=1 j=1
symm
symm
skew
skew
= Sji, Sij= −Sji, if we set
Because Sij
D as follows:⎞⎛n(Hij + Hji )⎠ ,D = diag ⎝j=1

Dii =n(Hij + Hji )j=1=n
j=1=2Symm
Symm
Skew
skew
Sij+ iSij+ Sji+ iSjin
j=1

⎛Symm

Sij= 2Dii,⎝Dii=n
j=1⎞Symm ⎠,Sij

we can rewrite the objective function as follows:n1 2Hij W xi − W xj 
2 i,j=1nn n1Dii (W xi , W xi ) −Hij (W xi , W xj )2 i=1i=1 j=1= tr W XD X T W T − tr W XHX T W T
(L = D − H),= tr W XLX T W T=

1 This objective function has meaning if we take the absolute value of the term on the right side, but discussion will benecessary about the validity of the function used in applications.

where the graph Laplacian matrix L is a complex matrix with imaginary parts S skew . In order to avoid atrivial solution W = 0, we introduce the same constraint as used in the LPP as follows:

Table 1. Classiﬁcation results of PCA
positive negativetrue251
13false31740

W XD X T W T = Im .

2nd Component

In short, the optimization problem of the LPP with anasymmetric similarity matrix is formulated as follows:Wopt = arg min tr W XLX T W T s.t. W XD X T W T=Im .
WBecause L is a Hermitian matrix and its eigenvalues
are real numbers, the trace of the objective function
also becomes a real number. This optimization problem, therefore, becomes meaningful. Using the methodof Lagrangian multipliers, we deﬁne the objective function J(W ) as follows:
J(W ) = W XLX T W T − λ W XD X T W T − Im .
Then, partial diﬀerentiation is performed with W T , weobtain the following equation:∂J(W ) = XLX T W T − λXD X T W T = 0.
∂W T
∴ XLX T W T = λXD X T W T .
Solution W can be obtained by solving the generalized
eigenvalue problem for complex matrices and arranging
the eigenvectors in ascending order of the magnitudeof the eigenvalues. Although D is a real matrix, because L is a Hermitian matrix, the eigenvalues are realnumbers, but the eigenvectors are complex vectors, so
W is the projection of the complex subspace.

5Experimental Results

As an application example of the ALPP, we implemented the k-nearest neighbor method and compared
it with the other dimensional reduction methods. As
comparative methods, we implemented principle component analysis (PCA) and the LPP.

5.1

Data SetIn this experiment, we used the USPS handwritten
digit database2 [8]. We used 7,291 images as the training data of a binary classiﬁcation problem, of which weused 1,005 images of “1” as positive examples and weused 6,268 images of other digits as negative examples.
We determined that the number of dimensions of theprojected subspace was two using visual observation.
For the classiﬁcation, we used the k-nearest neighbormethod in the projected subspace, and we conducted
the experiment with k=3. We used 254 images as positive examples, 1,753 images as negative examples, and,in total, we used 2,007 images for the evaluation.
We used the following equation for the similarity matrix of the LPP so that classiﬁcation became feasible:
LPP
Sij
=

1 l(xi ) = l(xj ),0otherwise

2 Available from https://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/

1st Component

Figure 2. Projected subspace of PCA
where l(.) is a class label. Data with the same classlabel is assigned 1, and 0 is given to data with otherclass labels. This similarity matrix is symmetric.
The similarity matrix of the ALPP adds the following neighborhood similarity to the symmetric similarity matrix of the LPP:
asymSij=10xi ∈ Nk (xj )otherwise.

As a result, the similarity matrix of the ALPP becomesasymmetric. In short, this similarity matrix has boththe similarity of the identity of the learning labels andthe similarity of the data proximity. In this experiment, we used α = 1/2.

5.2

Results and Discussion

The PCA classiﬁcation result is shown in Table 1,
and the result of dimensional reduction is shown in
Fig. 2. In PCA, the subspace is not divided into thepositive and negative examples, and both data aregrouped together. The classiﬁcation result, however,is good.
The classiﬁcation result of LPP is shown in Table 2,
and the result of dimensional reduction is shown in
Fig. 3. In LPP, the subspace separates the positive andnegative examples because the similarity matrix is designed to gather nearby examples using the class label
identities. The data, however, crosses at the boundary
between the positive and negative examples, and therecognition rate of LPP is below that of PCA.
Table 3 shows the recognition rate when the subspace projected by ALPP is two dimensional space.
The performance of ALPP is slightly improved in comparison to LPP. Because the subspace projected by
ALPP is a complex subspace, the number of dimensions of the subspace is four. Figs. 4 (a) and (b) show
graphs in which the horizontal axis is the ﬁrst component and the vertical axis is the second component
for the real and imaginary parts, respectively, of its
components. As shown in Fig. 4 (a), the test data areseparated into two classes in the real part, and the datais concentrated at the origin in the imaginary part, asshown in Fig. 4 (b). This means that there is almost
Table 2. Classiﬁcation results of LPP
positive negative
true
248
16
false
91734

2nd Component

Figure 3. Projected subspace LPP
Table 3. Classiﬁcation result of ALPP (twodimensional complex space)positive248
6

negative161737

no component of the imaginary part of the projected
data.
Just as for LPP, the data crosses at the boundary
between positive and negative examples, and the recognition rate of ALPP is below that of PCA. Most datais on the real axis and the projected subspace is like
one-dimensional space. This is because the similarity
matrix itself is an asymmetric matrix but it is nearlya symmetric matrix. Because the size of the similarity
matrix is 7, 291 × 7, 291, there are approximately 20
million symmetric pairs of elements. The number ofasymmetric components in this experiment was 8,132
pairs, which was about 0.3% of the total. In orderto evaluate the performance of ALPP, it seems necessary to conduct experiments using data with stronger
asymmetry.
Finally, we show the examples that are correctlyclassiﬁed by the ALPP method but incorrectly classiﬁed by the LPP method in Fig. 5. The leftmost column
shows the test image and other columns show the nearest training images. The upper row shows the training images selected by the LPP method and the lowerrow shows the training images selected by the ALPP
method. As shown in this ﬁgure, the ALPP method
gathers more similar images of positive examples thanthe LPP method.

6Conclusion

2nd Component

2nd Component

We have proposed an ALPP that expands the LPP
from a symmetric similarity matrix to an asymmetric similarity matrix using the Hermitian matrix forasymmetric representation. When we simply replace

1st Component(a) real part

1st NN

2nd NN

3rd NNmethodPN

P

N

LPP
N

ALPP
PN
P
P
Figure 5. Classiﬁcation example

1st Component

truefalsetest

1st Component(b) imaginary part

Figure 4. Projected subspace of ALPP (twodimensional complex space)the optimization problem with one using the Hermitian matrix, the optimization problem becomes complex, which cannot be totally ordered and sometimes
does not make sense. We have, however, shown thatit could be calculated well by devising a method to doso.
Although it is necessary to examine the meaningof the distance between two points on the complex
subspace obtained by the ALPP, our method can beapplied in many ways because there is an enormous
amount of data with asymmetric similarly in the realworld. In this paper, we have not compared and examined a wide variety of data. We will evaluate theperformance of our method by increasing the variety
of experimental data in future. We will also consider
whether it can be applied to other methods that use
the pairwise expression, e.g., sparse learning, or metriclearning.

References[1] M. Sugiyama, T. Ide, S. Nakajima, and J. Sense, “Semisupervised local fisher discriminant analysis for dimensionality reduction,” Machine Learning, Vol. 78, No. 12, pp. 35–61, 2010.
[2] A. Kimura, M. Sugiyama, H. Sakano, and H. Kameoka,“Designing various component analysis at will via generalized pairwise expression,” IPSJ Trans. on Mathematical Modeling and Its Applications, Vol. 6, No. 1,pp. 136–145, 2013.
[3] S.F. Altschul, W. Gish, W. Miller, E.W. Myers, andD.J. Lipman, “Basic local alignment search tool,” Molecular Biology, Vol. 215, pp. 403–410, 1990.
[4] B. Haasdonk and D. Keysers, “Tangent distance kernels
for support vector machines,” Proc. of ICPR, Vol. 2,pp. 864–868, 2002.
[5] J. Laub and K.R. Müller, “Feature discovery in nonmetric pairwise data,” Machine Learning Research,
Vol. 5, pp. 801–808, 2004.
[6] X. He and P. Niyogi, “Locality preserving projection,”
Advances in Neural Information Processing Systems,
Vol. 16, 2003.
[7] N. Chino and K. Shiraiwa, “Geometrical structures ofsome non-distance models for asymmetric MDS,” Behaviormetrika, Vol. 20, pp. 35–47, 1993.
[8] J.J. Hull, “A database for handwritten text recognition
research,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 16, No. 5, pp. 550–554, 1994.