Improved weighted local linear embedding algorithm based on Laplacian eigenmaps

Abstract

To solve the shortcomings of local linear embedding (LLE), such as sensitive to noise and poor generalization ability for new samples, an improved weighted local linear embedding algorithm based on Laplacian eigenmaps (IWLLE-LE) is proposed in this paper. In the proposed algorithm, Laplacian eigenmaps are used to reconstruct the objective function of dimensionality reduction. The weights of it are introduced by combining the geodesic distance with Euclidean distance, which can effectively represent the manifold structure of nonlinear data. Compared the existing LLE algorithm, the proposed one better maintains the original manifold structure of the data. The merit of the proposal is enhanced by the theoretical analysis and numerical experiments, where the classification recognition rate is 2%–8% higher than LLE.

Keywords

Local linear embedding Laplace feature map geodesic distance manifold structure

1. Introduction

Many problems in pattern recognition begin with the pre-processing of raw dimensional signals, such as face images, speech spectrograms, medical image signals for medical diagnose [1, 2, 3]. For convenience of subsequent operations such as classification, regression, image processing and error detection, the reprocessing should extract and highlight the inherent properties hidden in the high-dimensional observations and represent the intrinsic structures in a more compact and efficient way. However, the representations need be learned or discovered automatically in the case that no prior knowledge about the data is known. Dimension reduction is an unsupervised learning method, which can achieve effective dimension reduction. Dimensionality reduction methods are mainly divided into two types, linear dimensionality reduction and nonlinear dimensionality reduction. Linear dimensionality reduction includes principal component analysis (PCA) [4] and multidimensional scaling (MDS) [5].

However, with the improvement of data acquisition technology, the data that needs to be processed is mostly non-linear in reality. As a result, nonlinear dimensionality reduction methods such as kernel-PCA (KPCA) [6], generalized discriminant analysis (GDA), and kernel direct discriminant analysis (KDDA) [7] were proposed to solve the problem of nonlinearity in data distribution. However, these methods may have trouble when very large number of observations are needed to be processed. All of these kernel-based algorithms have some further problems of large training sample, overfitting, and finding suitable kernel functions for each specific data set.

Another important nonlinear dimensionality reduction is mainly represented by manifold learning. It assumes that the data is located at or close to one or more smooth manifolds, and the dimensionality reduction is performed by maintaining the geometric topology implied by the data. Classical manifold learning has locally linear embedding (LLE) [8], Laplacian eigenmaps (LE) [9, 10], Isometric mapping (ISOMAP) [11] and Local tangent space alignment (LTSA) [12].

As a classic nonlinear learning algorithm, the LLE algorithm is intuitive, easy to implement, and globally optimal without the need for iteration. Unlike clustering methods for local dimension reduction, LLE maps its inputs to a low dimensional space, and its optimizations do not involve local minima. By keeping the local symmetries of local linear relation, LLE is able to learn the global structure of nonlinear manifolds.

However, LLE also has many problems. The algorithm is sensitive to noise and has poor generalization ability for new samples. It does not make good use of category information at the same time. In recent years, researchers have proposed a number of improved algorithms. Zou et al. have proposed an improved LLE algorithm [13] using geodesic distance instead of Euclidean distance, which can better describe the flow between neighbours. Donoho et al. proposed a Hessian local linear embedding [14], which replaced the Laplacian operator with a Hessian operator, and improved the ability to process data with unevenness. Kouropteva et al. proposed a supervised local linear embedding algorithm (SLLE) using class labels [15]. By adding weights, they considered the influence of category information on the neighbour distance, where it made the same-class samples closer in the low-dimensional space and non-similar samples farther apart.

LE is also a nonlinear dimensionality reduction algorithm [16, 17, 18] which uses the concept of Laplacian Spectrum to construct the local nearest neighbour relationship of sample points, and map local domain relations into low-dimensional space. By keeping the local distance relation in the low-dimensional space, LE can learn the whole structure of the non-linear manifold. In [19], a Laplacian eigenmaps of adaptive distance weights was proposed, which was better than the original Laplacian eigenmaps for the distance of the manifold structure.

Though there are many improved LLE at present, it still uses K-nearest neighbour method to select points instead of choosing the nearest neighbour points. Hence the shortcomings such as sensitive to noise and sparse sampling are not fully overcame. It can not achieve good dimension reduction effect in these complex data environments. How to solve this shortcoming is a challenge at present. LE is insensitive to noise and has a lower time complexity for obtaining the distance weight by the thermonuclear function. In this paper, an improved weighted local linear embedding algorithm based on Laplacian eigenmaps (IWLLE-LE) is proposed with the characteristics of Laplacian map reconstruction. Furthermore, the geodesic distance is introduced in the IWLLE-LE, which can effectively describe the distance of the sample neighbours on the manifold.

2. Main related technology introduction

2.1 Locally linear embedding

LLE algorithm consists of three steps: firstly, the K-nearest neighbour method is used to get the nearest neighbour points of each sample. Then the weight coefficients of linear representation of each sample point in the original space are solved. Finally, the image of the sample points in the low-dimensional space is obtained by using the weight coefficients of the sample points in the original space. They are described as follows.

Considering the data set $X=[x_{1},x_{2},\ldots,x_{n}],x_{i}\in R^{D}$ , and determining the $k$ -nearest neighbors of the sample $x_{i}$ , we find the linear relationship between $x_{i}$ and the $k$ -nearest neighbors, that is to find the weight coefficient of the linear relationship.

$\displaystyle\min\sum_{i=1}^{n}\left\|{x_{i}-\sum_{j=1}^{k}{w_{ij}x_{j}}}% \right\|^{2}$ $\displaystyle\text{s.t. }\sum_{j=1}^{k}{w_{ij}}=1$ (1)

Assuming that the projection of D-dimension sample set $\{{x_{1},x_{2},\ldots,x_{n}}\},x_{i}\in R^{D}$ corresponding to D in low-dimension space is $Y=[y_{1},y_{2},\ldots,y_{n}],y_{i}\in R^{d}$ , it is desirable to maintain the same linear relationship.

$\displaystyle\min\sum_{i}^{n}\left\|{y_{i}-\sum_{j=1}^{k}{w_{ij}y_{j}}}\right% \|^{2}$ $\displaystyle\text{s.t. }\frac{1}{n}\sum_{i=1}^{n}{y_{i}}y_{i}^{\rm T}=I,\sum_% {i=1}^{n}{y_{i}}=0$ (2)

where $I$ is the identity matrix. Then we set

$\displaystyle M=(I-W)^{\rm T}(I-W)$ (3)

where $W=[w_{1,}w_{2},\ldots,w_{n}]$ , and the value of the $i$ -th row and the $j$ -th column is $w_{ij}$ . The feature vectors corresponding to the second to ( $d+1$ )-th small eigenvalues of the matrix $M$ are the result of dimensionality reduction.

2.2 Laplacian eigenmaps

Given the data set $X=[x_{1},x_{2},\ldots,x_{n}],x_{i}\in R^{D}$ , the $k$ nearest neighbors of the sample $x_{i}$ , set the $k$ neighbors as a matrix $X_{i}^{k}=[x_{i1},x_{i2},\ldots,x_{ik}]$ , where $x_{ij}$ is the $j$ th neighbor of $x_{i}$ . And assign a weight value $w_{ij}$ to each neighbor distance through a thermonuclear function.

$\displaystyle w_{ij}=\begin{cases}\exp\left(-{\displaystyle\frac{\|{x_{i}-x_{j% }}\|^{2}}{\alpha}}\right),&\text{if }x_{j}\in X_{i}^{k}\\ 0,&\text{if }x_{j}\notin X_{i}^{k}\end{cases}$ (4)

Let $Y=[y_{1},y_{2},\ldots,y_{n}],y_{i}\in R^{d}$ denotes the low dimensional map of data set $X$ . We can solve $Y$ by constructing the following optimization problem

$\displaystyle\min\sum_{i,j=1}^{n}{\|{y_{i}-y_{j}}\|^{2}w_{ij}^{le}}$ $\displaystyle\text{s.t. }\sum_{i=1}^{n}{y_{i}}=0,\sum_{i=1}^{n}{\|{y_{i}}\|^{2% }}=I$ (5)

Utilizing the Lagrangian multiplier method, the optimization problem Eq. (2.2) can be translated into the following generalized eigenvalue problem

$\displaystyle Ly=\lambda Dy$ (6)

The feature vector corresponding to the second to ( $d+1$ )-th small feature value of Eq. (6) is the mapping result of high-dimensional data in low-dimensional space.

3. Improved LLE algorithm

In this section, LLE algorithm is improved from the following aspects: (1) Combining with the LE algorithm, we construct a new optimization problem in low-dimensional mapping, which can improve the robustness of the algorithm when the amount of data is insufficient or noisy. (2) To overcome the difficulties of LLE parameter selection, we introduce a new method of weight construction by combining geodesic distance with Euclidean distance. It can reduce the error caused by sparsity and large curvature problems.

Figure 1.

Selection of adjacent points for manifold learning. (a) Euclidean distance. (b) Geodesic distance.

3.1 Weight setting

In a low-dimensional objective function of LLE, two weights are used. However, only the distance factor is considered and the structural factor is ignored in the two weights. In addition, only the thermonuclear weight is used in the second weight. We take into account both the distance factor and the structural factor in the second weight, and define the weight $w^{\prime}_{ij}$ as the product of the distance weight $w_{ij}^{D}$ and the structure weight $w_{ij}^{S}$

$\displaystyle\begin{cases}w^{\prime}_{ij}=w_{ij}^{D}\cdot w_{ij}^{S}\\ w_{ij}^{D}=\exp({-D_{G}(x_{i},x_{ij})}/{d_{G}})^{2}\\ w_{ij}^{S}=({D_{E}(x_{i},x_{ij})}/{D_{G}(x_{i},x_{ij})})^{2}\end{cases}$ (7)

In Eq. (7), $D_{E}(x_{i},x_{ij})$ and $D_{G}(x_{i},x_{ij})$ represent the Euclidean distance and geodetic distance of the sample $x_{i}$ and the neighboring point $x_{ij}$ , respectively, and $d_{G}$ represents the average of all the geodesic distances in the neighborhood.

Figure 2.

Processing results of sparse Swiss Roll data by different algorithms. (a) Sparse Swiss Roll, (b) IWLE-LLE, (c) LLE, (d) LE.

For the distance weight $w_{ij}^{D}$ , the median distance of the $d_{G}$ is determined in the local neighborhood. The farther the neighbor point $x_{ij}$ is from the sample $x_{i}$ , the smaller the weight $w_{ij}^{D}$ corresponding to the neighbor point. In the structural weight $w_{ij}^{S}$ , we select the ratio of the Euclidean distance $D_{E}(x_{i},x_{ij})$ to the geodesic distance $D_{G}(x_{i},x_{ij})$ to describe the linearity degree of the local neighborhood of $x_{i}$ . Figure 1 shows that a far neighbor point $u$ deviating from the manifold structure brings a large geodesic distance $D_{G}(x_{i},x_{ij})$ , a little the ratio ${D_{E}(x,u)}/{D_{G}(x,u)}$ and a little $w_{xu}^{S}$ . In other word, the point $u$ has little impact on reconstruction. But the neighbor point $v$ is closer to manifold structure, then the geodetic distance $D_{G}(x,v)$ will more approaches European distance $D_{E}(x,v)$ and the weight $w_{xv}^{S}$ is larger, that is to say, the point $v$ has great influence on reconstruction.

Figure 3.

Processing results of noisy Swiss Roll data by different algorithms. (a) Swiss Roll data with Gauss noise, (b) IWLE-LLE, (c) LLE, (d) LE.

3.2 Objective function of low-dimensional map

Mapping high-dimensional data to low-dimensional space requires not only maintaining a local linear structure, but also introducing a local neighbor relationship. By adding the weight of Eq. (7) above to increase the robustness of the model, we construct the following optimization problem:

$\displaystyle\min\sum_{i=1}^{n}\left\|y_{i}\!-\!\sum_{j=1}^{k}{w_{ij}y_{j}}% \right\|^{2}\!+\!\beta\sum_{i=1}^{n}{\sum_{j=1}^{k}\|{y_{i}\!-\!y_{j}}\|^{2}w^% {\prime}_{ij}}$ $\displaystyle\text{s.t. }\sum_{i=1}^{n}{y_{i}=0,\sum_{i=1}^{n}{D_{ii}\|{y_{i}}% \|^{2}}}=I$ (8)

where $\beta$ is a compromise parameter. In Optimization problem Eq. (3.2), the local linear relationship is weighted in the first term and the local neighbor structure is weighted in the second term, which reduce the influence of the points in the non-manifold on the solution of the optimization problem under the abnormal points or sparse data. $D$ is a diagonal array, where $D_{ii}=\sum_{j=1}^{n}{w^{\prime}_{ij}}$ . The optimization problem Eq. (3.2) is equivalent to the followings.

$\displaystyle\min tr(Y^{\rm T}MY)+\beta tr(Y^{\rm T}LY)$ $\displaystyle\text{s.t. }Y^{\rm T}DY=I,Y^{\rm T}DI=0$ (9)

where $M=(I-W)^{\rm T}(I-W)$ , $L=D-W^{\prime}$ . Let $B=M+\beta L$ , and then Eq. (3.2) can be converted to

$\displaystyle\min tr(Y^{\rm T}BY)$ $\displaystyle\text{s.t. }Y^{\rm T}DY=I,Y^{\rm T}DI=0$ (10)

Following the Lagrange multiplier method, Eq. (3.2) can be transformed into a generalized eigenvalue problem:

$\displaystyle BY=\lambda DY$ (11)

The feature vector corresponding to the second to the $d+1$ -th small eigenvalues of Eq. (11) is the results of dimensionality reduction.

4. Results and analysis

To evaluate the performance of dimensionality reduction of the IWLLE-LE, several experiments are made to compare IWLLE-LE to two manifold learning algorithms LLE and LE on manifold datasets. In the first experiment, the artificial dataset Swiss roll of manifold learning is used to verify the performance of IWLLE-LE for sparse samples and anti-noise points. In the second experiment, five real-world data sets including two face datasets, Wine dataset, heart dataset and Iris dataset [20], are used to demonstrate the performance of dimensionality reduction and classification about the three algorithms. In the experiments, the geodesic distance is calculated by Dijkstra method.

4.1 Artificial data experiment

In the first experiment, the performance of sparse samples is tested by 400 data from the Swiss roll dataset, and 800 noise-added data are used to test the anti-noise performance of IWLLE-LE.

Figure 2 shows the results that 400 sparse Swiss roll data are processed by the three different algorithms. The IWLLE-LE algorithm is used to reduce the dimensionality of the sparse Swiss roll data, and it is well developed in the two-dimensional space. Although the uppermost yellow sample points and the blue-green sample points have partial overlap, there is still a good data neighbour relationship. The colour gradation is more gradual, and the sample points of each colour are more evenly distributed in the low-dimensional space. The original characteristics of the data and the relationship between the neighbours are well maintained. The colour mixing phenomenon doesn’t occur, and the structural information of the data is well preserved. However, the LLE and LE algorithms don’t maintain well relationship between the neighbours no matter how we adjust the parameter of neighbour points $k$ and the parameter of the thermonuclear function $\alpha$ . The LLE dimensionality reduction result in Fig. 2c shows that the blue points are covered with the yellow points and the green points, and the yellow is divided into two sections. The data structure of the original sample is seriously damaged. Such dimensionality reduction data cannot use effectively to classification. The IWLLE-LE algorithm has obvious advantages in dealing with sparse data by comparing it with the LLE and LE algorithms.

Figure 3 shows results that 800 data with Gaussian noise are processed by three algorithms. The Fig. 3b shows that after dimensionality reduction, the data points of IWLLE-LE are evenly distributed, the colour of the sample points is gradually expanded, only the yellow part overlaps slightly, and the structure information of the original data remains intact. The Gaussian noise makes the neighbour relationship between data more confusing, therefore, the dimensionality reduction results of LLE and LE algorithms are still not ideal, but the IWLLE-LE algorithm is minimally affected by Gaussian noise and still has good results and strong robustness.

Figure 4.

Separability results on the heart dataset.

Figure 5.

Separability results on the wine dataset.

Figure 6.

ORL face image example.

Figure 7.

Yale face image example.

5. Real data experiments

In this part, there are two different methods to measure the performance of dimensionality reduction. One is to use the separability criterion to measure the performance of dimensionality reduction and the other is to use support vector machine to classify dimensionality reduction data.

First, we define the following separability criterion:

$\displaystyle J=\frac{\sum_{i}{s_{bi}^{2}}}{\sum_{i}{s_{wi}^{2}}}$ (12)

where $s_{bi}^{2}=n_{i}\times(m_{i}-m)^{2}$ is between-class scatter, $m_{i}$ is the sample mean vector of class $i$ , $n_{i}$ is the number of samples of class $i$ , and $m$ is the mean vector of all samples. $s_{wi}^{2}=\sum_{y\in Y_{i}}{(y-m_{i})}^{2}$ is within-class scatter. $Y_{i}=[y_{1},y_{2},\ldots,y_{n_{i}}]$ is sample after dimensionality reduction. According to Fisher’s discriminant idea, the optimal separability is that the samples have the smallest within-class scatter and the largest between-class scatter. In other words, the value of $J$ is the bigger, the separability is the better. We select the wine and heart datasets from the UCI Repository for experiments. Heart dataset has 270 data and the dimension is 13. Wine dataset has 180 data and the dimension is 13. Experiments are carried out on different the number of nearest neighbors $k$ . In order to visualize, let $d=2$ . Figures 4 and 5 give the separability curves when the value of $k$ changes.

It can be seen from the Figs 4 and 5 that the separability of IWLLE-LE algorithm is almost higher than LLE, HLLE regardless of the selection of the number of nearest neighbors $k$ , and IWLLE-LE algorithm has good performance for anti-noise.

The second, we use support vector machine to classify samples after dimensionality reduction. Two face databases and two classification databases are used to verify the performance of the proposed method, which are Olivetti Research Laboratory Database (ORL), Yale Face Database (Yale), wine dataset and Iris dataset. As shown in Table 1, the information description of each dataset is given.

Table 1

Information description of relevant datasets

	ORL	Yale	Iris	Wine
Num	400	165	150	178
Class	10	11	3	3
Dimension	112 $\times$ 92	100 $\times$ 100	4	13
Proportion (training-test)	1:1	6:5	5:3	4:3

ORL database contains 400 images of 40 persons (10 images per person). Facial expressions and facial details are different variations among images. Yale database contains 165 images of 15 persons (11 images per person). Some samples of ORL and Yale are listed in Figs 6 and 7. Each database is divided into two parts as training sets and testing sets. Although testing sets contain all persons, the sample images between the training set and testing set don’t overlap. For the ORL database testing, the first 50% of samples per person are selected as training samples and the rest of samples are used for test. For the Yale face images, the first six samples per person are used for training and the remaining five samples per person are used for testing.

Wine dataset contains 178 samples of three types and Iris dataset contains 150 samples of three types. Every sample from Wine and Iris is 13-dimensional and 4-dimensional, respectively. Hundred samples of both wine and Iris are randomly selected as training samples and the rest of samples are used for test.

Table 2

Real data dimension reduction recognition rate

Data set	Method	Classification accuracy (%)	Dimension $d$	Nearest neighbour number $k$
ORL	WLE-LLE	92.4	96	9
	LLE	86.5	100	12
	HLLE	88.2	90	16
Yale	WLE-LLE	86.8	35	15
	LLE	77.6	40	13
	HLLE	84.2	38	13
Wine	WLE-LLE	86.5	6	14
	LLE	76.2	5	10
	HLLE	83.6	6	12
Iris	WLE-LLE	90.4	2	6
	LLE	89.3	2	7
	HLLE	94.5	2	9

Table 2 shows the best results and the optimal dimensionality which are obtained by LLE, HLLE and IWLLE-LE. Compared with the other algorithms, IWLLE-LE algorithm has much highest classification accuracy on the four data sets. It can be seen that our IWLLE-LE algorithm is average 4%–6% higher than LLE and HLLE. IWLLE-LE also has certain advantages in the wine dataset and the Iris dataset.

6. Conclusion

The local linear embedding (LLE) algorithm is sensitive to the number of nearest neighbors $k$ , and fails on dimensionality reduction of sparse data. In order to overcome this difficult problem, a local linear embedding algorithm based on Laplacian eigenmaps is proposed. The proposed algorithm has a good dimensionality reduction effect, and has good performance for sparse sampling and anti-noise.

Future studies should include considering the sample category information in designing classifier after dimensionality reduction and research on dimension reduction of real-time data.

Footnotes

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grants (61472307, 51875457), the Key Research Project of Shaanxi Province (2018GY-018, 2019GY-061), the International S&T Cooperation Program of Shaanxi Province (2019KW-056), and the Xi’an Science and Technology Plan Project (2020KJRC0109).

References

Sable

A.H.

and Talbar

S.N.

, An adaptive entropy based scale invariant face recognition face altered by plastic surgery, Pattern Recognition and Image Analysis 28(4) (2018), 813–829.

Badshah

A.M.

Ahmad

Rahim

et al., Speech emotion recognition from spectrograms with deep convolutional neural network, International Conference on Platform Technology & Service, 2017.

Chaovalitwongse

W.A.

Pottenger

R.S.

and Iasemidis

L.D.

, Pattern-and network-based classification techniques for multichannel medical data signals to improve brain diagnosis, IEEE Transactions on Systems Man & Cybernetics Part A Systems & Humans 41(5) (2011), 977–988.

Wold

Esbensen

and Geladi

, Principal component analysis, Chemometrics & Intelligent Laboratory Systems 2(1) (1987), 37–52.

Steyvers

, Multidimensional scaling, Encyclopedia of Cognitive Science, 2000, pp. 93–103.

Liu

, Gabor-based kernel PCA with fractional power polynomial models for face recognition, IEEE Transactions on Pattern Analysis & Machine Intelligence 26(5) (2004), 572–581.

Y.B.

, WLAN indoor positioning algorithm based on KDDA and SVR, Journal of Electronics & Information Technology 33(4) (2011), 896–901.

Roweis

and Saul

, Nonlinear dimensionality reduction by locally linear embedding, Science 290 (5500) (2000), 2323–2326.

Belkin

and Niyogi

, Laplacian eigenmaps and spectral techniques for embedding and clustering, Advances in Neural Information Processing Systems 14(6) (2002), 585–591.

10.

Wang

, Laplacian eigenmaps, Geometric structure of high-dimensional data and dimensionality reduction, Springer Berlin Heidelberg, 2012, pp. 235–247.

11.

Tenenbaum

Silva

and Langford

, A global geometric framework for nonlinear dimensionality reduction, Science 290(5500) (2000), 2319–2323.

12.

Zhang

Qiao

and Zhang

, An improved local tangent space alignment method for manifold learning, Pattern Recognition Letters 32(2) (2011), 181–189.

13.

Zou

and Huang

T.M.

, A LEE algorithm based on improved distance, Journal of Southwest University for Nationalities (Natural Science Edition) 38(3) (2012).

14.

Donoho

D.L.

and Grimes

, Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data, Proceedings of the National Academy of Sciences of the United States of America 100(10) (2003), 5591.

15.

Kouropteva

Okun

and Pietikäinen

, Supervised locally linear embedding algorithm for pattern recognition, Lecture Notes in Computer Science 2652 (2003), 386–394.

16.

Liu

Jaja

and Pessoa

, LEICA: Laplacian eigenmaps for group ICA decomposition of fMRI data, Neuroimage 169 (2017), 363–373.

17.

Belkin

and Niyogi

, Laplacian eigenmaps for dimensionality reduction and data representation, Neural Computation 15(6) (2014), 1373–1396.

18.

Thida

Eng

H.L.

and Remagnino

, Laplacian eigenmap with temporal constraints for local abnormality detection in crowded scenes, IEEE Transactions on Cybernetics 43(6) (2013), 2147–2156.

19.

Y.J.

and Liu

B.H.

, Laplacian feature mapping based on adaptive neighborhood parameters, Journal of Fuzhou University (Natural Science Edition) 41(2) (2013), 153–157.

20.

Blake

and Merz

, UCI repository for machine learning databases, Dept of Information and Computer Sciences, Univ of California, Irvine, http://www.ics.uci.edu/∼mlearn/MLRepository.html, 1998.