Enhanced Unsupervised Discriminant Dimensionality Reduction for Nonlinear Data

1 Introduction

Nowadays, high-dimensional data has become ubiquitous due to the development of data collection, posing significant challenges in data processing and analysis. High-dimensional data increases the computational complexity of data processing and may result in the curse of dimensionality and overfitting problem [Chen et al., 2013]. Therefore, dimensionality reduction attracts increasing attention for handling high-dimensional data, and numerous dimension reduction methods [Wang et al., 2020; Kambhatla and Leen, 1997; Ma and Zhu, 2013] are developed, including both unsupervised methods and supervised methods.

The most popular unsupervised dimensionality reduction methods are principal component analysis (PCA) [Wold et al., 1987], locality preservation projection (LPP) [He and Niyogi, 2003], and Neighborhood Preserving Embedding (NPE) [He et al., 2005]. PCA leverages linear transformation to map high-dimensional data into a low-dimensional subspace by maximizing the sample variance, which fully preserves the information of the original data and simultaneously reduces the dimension. However, PCA mainly focuses on maximizing the overall variance of the projected data [Nanga et al., 2021] but ignores the local information between samples, which results in performance degradation in some cases. Compared with PCA, LPP/NPE can retain local features in the original data by considering the relationship between adjacent samples. Besides, as their non-linear version, Laplacian Eigenmaps (LE) [Belkin and Niyogi, 2003] and Locally Linear Embedding (LLE) [Roweis and Saul, 2000] can better capture nonlinear structures in the data. However, without the instruction of labels, these methods generally cannot well exploit the discriminant information of the original data.

∗Corresponding Author

Linear discriminant analysis (LDA) [Fisher, 1936] is a classical supervised dimension reduction method, which seeks a projection matrix by enforcing the projective interclass distance to be larger and the intra-class distance to be smaller. LDA helps to extract the discriminant features of samples during dimension reduction, which is beneficial for improving classification performance. Besides, since LDA focuses on differences between clusters and concentrates less on local variations and noises, it performs better when data is corrupted with noise or outliers. However, LDA requires reliable data labels for dimension reduction, while large-scale data annotation can be costly and challenging [Zhang et al., 2020; Heck et al., 2016], which limits the practical application of LDA.

To mitigate this issue and meanwhile maintain the advantages of LDA, several unsupervised LDA methods are proposed [Wang et al., 2014; Deng et al., 2019]. Niijima et al. [2008] extended Laplacian LDA (LLDA) [Tang et al., 2006] to unsupervised cases and developed an LLDA-based recursive feature elimination (LLDA-RFE), which is able to handle high-dimensional data efficiently. LDA-UEL leverages unsupervised ensemble learning to guide LDA for unsupervised dimension reduction [Deng et al., 2019]. Ding et al. [2007] developed LDA-Km by combining the LDA and K-means into a coherent framework. LDA-Km leverages Kmeans to generate cluster labels to guide the LDA to adaptively select the subspace with the most discriminative features. Similarly, Wang et al. [2023] developed an unsupervised LDA (Un-LDA) method by jointly performing clustering and subspace learning. Wu et al. developed a general framework for dimensionality reduction of k-means clustering [Wu et al., 2020]. However, it relies on K-means to guide LDA for feature selection, while K-means suffers from sensitivity to the cluster centroid initialization, which significantly affects the clustering results and makes it less robust to outliers.

To address these problems, we propose a novel unsupervised LDA method for dimension reduction using centerless K-means. In this method, we unify centerless K-means and LDA in a general framework, which guides LDA in selecting subspaces most appropriate for clustering with cluster labels generated by centerless K-means. The adopted centerless Kmeans compute the clustering labels with the pairwise distance of samples rather than the distance between samples and centroids. Thus, it eliminates the requirement of computing centroids and improves the robustness of clustering. Besides, we use the learned label matrix to construct similarity matrix and the within-cluster scatter matrix for LDA, which simultaneously maintains the neighboring relationship and cluster structure relationship of LDA. Moreover, the dimension of the learned subspace is not limited to cluster number. The main contributions of the work can be summarized as follows:

• We propose a novel unsupervised linear discriminant analysis method by fusing centerless K-means and LDA into a unified framework, which simultaneously exploit discriminative structure and local neighbor structure.
• We employ centerless K-means to guide LDA, which avoids the calculation to cluster centroid and improves model robustness. Additionally, we introduce Butterworth filter distance to build distance matrix, which is able to handle nonlinear data.
• We conducted extensive experiments and comparisons on seven benchmark datasets, whose results clearly demonstrate the superiority of our method.

2 RelatedWork

2.1 Linear Discriminant Analysis

Given a set of input data xi(i = 1, 2, ..., n) ∈ Rd×1 and the projection matrix W ∈ Rd×t , LDA aims to separate the n samples of different classes in the new feature space yi = W⊤xi as much as possible, and the samples of the same class are as close as possible, to obtain samples with greater discriminability. For multiple classification problems, normalize all samples so that their mean is 0 and suppose that there are m classes, mk is the number of samples of the k-th class and uk represents the mean of class k, the optimization objective of LDA is

where the between-class scatter matrix

the within-class scatter matrix

and there is the total scatter matrix

Bringing Sb = St-Sw into Eq. (1), then it can be rewritten as follows:

2.2 K-means Clustering

As we all know, K-means clustering is to find the points closest to the centroid of the cluster and then group them together until each sample is closest to the corresponding centroid of the cluster, let A1,A2, · · · ,Am denotes mdifferent clusters, its optimization problem is as follows:

With simple algebra, we have:

Thus, we can see Eq. (6) is equal to tr(Sw),

2.3 Unsupervised LDA

Both K-means clustering and LDA rely on minimizing the intra-class distance between samples and centroids. Given a linear projection y =W⊤x, the within-class scatter distance in the subspace can be expressed as:

where Sw represents the within-class scatter matrix, xi is the i-th sample, uk is the mean of the k-th cluster, andW is the projection matrix.This is equivalent to performing K-means clustering in the subspace. This connection between LDA and K-means allows for the implementation of unsupervised LDA. Ding et al. [2007] and Wang et al. [2023] leveraged this relationship, integrating K-means clustering with LDA to propose the following optimization model:

This unsupervised LDA model employs K-means and is sensitive to cluster centroid initialization. Different initializations of cluster centroids yield distinct clustering outcomes, and the cluster centroids are susceptible to the influence of noisy data points, which can compromise the accuracy and robustness of the resulting clustering. Therefore, selecting appropriate cluster centroids is essential for achieving superior clustering performance. Furthermore, suboptimal initialization can result in the algorithm converging to local optima or negatively impacting its convergence rate [Arthur and Vassilvitskii, 2007; Celebi et al., 2013]. Another significant limitation is that it is still a global subspace learning method and does not consider the local manifold structure, which is important for clustering. To address these challenges, our method combines centerless K-means with LDA to eliminate the need to calculate the cluster centroid and mitigating the impact of noise on the clustering performance. Besides, we employ the pseudo labels to construct similarity matrix, which retains the discriminative structure and simultaneously exploit the local manifold structure.

3 ProposedMethodology

3.1 Motivations and Objectives

We first introduce the following Theorem 1 to implement the centerless K-means, which is the basis of our method.

Theorem 1. Given a set of input data X = {x1, x2, . . . , xn} ∈ Rd×n , assuming there are m clusters, where uk represents the mean of k-th cluster, Ak represents the optimized k-th cluster, and S is the similarity matrix, there is

where

Proof: Let uk = 1 mk ∑ xi∈Ak xi, mk represents the number of samples in the k-th clusters, Eq. (6) is expanded as follows:

Similarly, the right side of Eq. (10) is expanded as follows:

With Eq. (12) and Eq. (13), Theorem 1 is proved. From Theorem 1, we can conclude that, for the objective function of K-means, we can use the pairwise distance between neighbor samples to replace the distance between samples and the cluster centroid for optimization, under the condition where the similarity matrix S constructed from cluster labels. Specifically, suppose the matrix F ∈ Ind is a discrete and sparse cluster indicator matrix where each row fi represents the cluster label of i-th sample. If i-th(i = 1, 2, . . . , n) samples belong to k-th(k = 1, 2, . . . ,m) cluster, then Fik = 1, otherwise, Fik = 0. Because a sample belongs to only one cluster, so each row has only one element that is 1, and the rest of the elements are 0. Then, we can calculate Sij by Sij = ⟨fi, fj⟩. By introducing a discrete label matrix F, the K-means in Eq. (6) is equivalent to:

By replacing K-means objective with Eq. (14), it can avoid the sensitivity to centroid initialization and improve the robustness of clustering. We can then rewrite the within-cluster scatter distance in Eq. (8) as follows:

By substituting Eq. (15) into Eq. (5), we obtain our unsupervised LDA model that integrates centerless K-means clustering and LDA dimensionality reduction into a unified framework.

This framework enables simultaneous clustering and dimensionality reduction without requiring the input of true labels. In other words, we can obtain both the cluster indicator matrix F and the projection matrix W at the same time. By simplifying Eq. (16) and substituting Sij = ⟨fi, fj⟩ into it, we can obtain our final objective function:

Since there are two variables W and F in Eq. (17) that need to be solved, we utilize the optimization techniques described in [Wang et al., 2015; Xu et al., 2016] to implement an alternating optimization strategy. This approach allows us to iteratively update each variable. The specific steps for optimizing each variable are in the following subsection.

3.2 Optimization

(1) Fix F to solve W.

When F is fixed, the similarity matrix Sij is also fixed, solving Eq. (17) is equivalent to solving

Define Laplacian matrix of S as L = DS - S, where DS is the degree matrix of S, which is a diagonal matrix and its diagonal element is defined by (DS)ii = ∑j Sij. Thus, Eq. (18) can be written as

where Sl = XLX⊤. From Eq. (19), we can see that its denominator is the objective of LPP, which makes our method capable of exploiting local manifold structure.

According to [Fisher, 1936], Eq. (19) can be solved by the Lagrange multiplier method StW = λSlW, which performs eigenvalue decomposition on Sl-1St to obtain the target projection matrix W. However, obtaining an exact solution through eigenvalue decomposition directly using the trace ratio form is challenging, and the results may not converge. To address this issue, we transform the trace ratio problem into a trace difference problem [Wang et al., 2007]. By introducing a hyperparameter λ, the trace ratio problem described in Eq. (19) can then be reformulated into the following trace difference form for effective resolution:

According to Eq. (20), we only need to perform eigenvalue decomposition on St - λSl. Then, we order the eigenvalues

Algorithm 1 The whole process of solving problem (17)

Input: A set of input data X; hyperparameter λ

Initialization: W: setting an identity matrix to the first t rows; F: setting an identity matrix to every m rows

Output: Projection matrixW ∈ Rd×t , cluster indication matrix F ∈ Rn×m

• 1: while not converge do
• 2: Update F by solving Eq. (25);
• 3: UpdateWby solving Eq. (20);
• 4: end while
• 5: return Projection matrixW, cluster indicator matrix F

and take the t eigenvectors corresponding to the first t largest eigenvalues to compose the matrixW.

(2) Fix W to solve F.

Since the matrix W is fixed, tr(W⊤XX⊤W) is a constant, Eq.(12) become

where distance matrix D is expressed in terms of square Euclidean distance Dij = ||yi -yj||22 = ||W⊤(xi -xj)||22 . In addition to square Euclidean distance, we also introduce the Butterworth filter distance from [Lu et al., 2024] to obtain the distance matrix D, i.e.,

where Ω is a hyperparameter, and G is the similarity matrix, whose computation method is referred to [Lu et al., 2024]. By using the Butterworth filter distance to reduce the influence of outliers and deal with nonlinear data more effectively, the clustering effect of our method can be effectively improved. In the experimental part of Section 4, we can see that the clustering effect of Butterworth filter distance is better than that of Euclidean distance.

Because each row of the matrix F is independent and each row has only two discrete values of 0 and 1, in which only one element is 1 and the rest is 0, it is difficult to directly obtain its optimal solution. [Lu et al., 2023; Gao et al., 2023; Pei et al., 2023] proposed a good solution, first fixed the other rows, and then solved line by line to find the position of element 1 to get the whole cluster indicator matrix F. The concretesolving process is as follows:

When solving i-th row fi of the cluster indicator matrix F, the problem (21) can be rewritten as

Substituting Dii = 0 into Eq. (23), it becomes

where d⊤i = (Di1 Di2 · · · Din) ,Dii = 0, so the optimal solution to problem (21) can be expressed as

The whole algorithm flow of solving the problem (17) is shown in Algorithm 1.

3.3 Computational Complexity Analysis

Our algorithm flow is mainly divided into two parts: one is to solve the calculation matrix F according to Eq. (25), and the other is to solve the matrix W according to the eigenvalue decomposition of Eq. (20). The computational complexity of the former is O(n2m), while the latter, St - λSw is a symmetric matrix, so the symmetric QR algorithm is used for the real symmetric matrix, so its time complexity is O(d3 ). If T is the number of iterations, then the total complexity of our algorithm is O(T(d3 + n2m)). Although the complexity of each iteration is O(d3 ), our algorithm can converge after no more than 5 iterations, that is, T ≤ 5. Moreover, our method can obtain a better clustering result.

4 Experiments

To validate the effectiveness of our proposed model, we have extensively tested it on a Toy dataset and a diverse set of seven benchmark datasets. Moreover, we selected ten comparison methods. Our experiments were conducted on a Windows 11 desktop computer with a 13th Gen Intel(R) Core(TM) CPU, and MATLAB R2023a.

4.1 Experiment on Noises Dataset

To evaluate the noise resistance and robustness of our proposed method, we designed a two-dimensional noises dataset comprising 2 clusters and 43 samples. As shown in Figure 1.(a), there are 20 samples in the Cluster 1 and 23 samples in the Cluster 2, the three samples far from the centroid of the Cluster 2 are noises. The Figure 1.(b) is the clustering labels of the K-means method on the noises dataset, and the Figure 1.(c) is the labels of our method on the noises dataset. K-means is to minimize the distance between samples and their nearest cluster centroids. However, due to the influence of cluster centroid calculations, K-means tends to merge two clusters that are originally close to each other, while grouping distant noise samples into a single cluster. In contrast, our method calculates the distances between sample pairs, thereby avoiding the computation of cluster centroids. This approach enhances the clustering performance in the presence of noise and demonstrates superior robustness.

4.2 Experimental Settings

Datasets: We selected seven benchmark datasets to verify the performance of our proposed method, which are FaceV5 [Team, 2009], Isolet [Fanty and Cole, 1990], JAFFE [Lyons et al., 1999], MSRC V2 [Winn and Jojic, 2005], ORL [Cai et al., 2010], UMIST [Hou et al., 2013] and Yaleface [Georghiades et al., 1997]. The details of these benchmark datasets are shown in Table 1.

Metrics: To evaluate the performance of our algorithm, We employed three widely accepted clustering evaluation metrics: Accuracy (ACC), Normalized Mutual Information (NMI), and Purity. Higher values of these metrics indicate superior clustering performance.

Comparison methods:

We selected five clustering methods without dimension reduction, i.e., regularized k-means (RKM) [Lin et al., 2019], Ksum [Pei et al., 2023], Ksum-x [Pei et al., 2023], Kmeans [Hartigan and Wong, 1979], CDKM [Nie et al., 2022] for comparison. Besides, to effectivelyly evaluate model performance, we also compare our method with another five clustering methods with subspace learning, including two methods of dimensionality reduction before clustering: PCA [Turk and Pentland, 1991]+K-means and LPP [He and Niyogi, 2003]+K-means, and three unsupervised LDA methods: LDA-Km [Ding and Li, 2007], Un-RTLDA, and UnTRLDA [Wang et al., 2023].

4.3 Clustering Performance

The experimental results of our proposed method and ten comparison methods in seven benchmark datasets are shown in Table 2. Our proposed method can achieve the best clustering result for the ORL dataset when λ is 0.08, and the remaining six datasets FaceV5, Isolet, JAFFE, MSRC V2, UMIST and Yaleface have the best clustering performance when λ is equal to or close to 0.05. Moreover, the different dimensions of the subspace will also affect the clustering results, so We sequentially select the subspace dimensions ranging from 150 to the dimension d of data X with an interval of 20 for traversal. In both the comparison methods and our method, to ensure accuracy, we repeat the experiment ten times and then take the maximum value.

In the tables, we use two different distance measures, square Euclidean distance and Butterworth filter distance, to verify the performance of our method, where "ours" represents the results of square Euclidean distance and "ours(btw)" represents the results of Butterworth filter distance. The anchor rate and Ω of FaceV5, JAFFE, MSRC V2, ORL, UMIST and Yaleface datasets are 0.08 and 0.01, while the anchor rate and Ω of Isolet datasets are 0.08 and 0.001. It can be seen that our method has obvious advantages when using Butterworth filter distance and can achieve better results.

When Euclidean square distance is used, the clustering results of Isolet, JAFFE, MSRC V2, ORL, UMIST and Yaleface are better than those of the five pure clustering algorithms, which shows that our method effectively improves the performance of clustering. At the same time, on the seven benchmark data, we also conducted the experiment of dimensionality reduction before clustering, and the results are as follows: PCA+K-means and LPP+K-means in the three tables. Our method has the same better effect, because our method is not a simple method of dimensionality reduction before clustering, but a unity of both, and adopts a centerless clustering method. Therefore, our method breaks through the limitations of traditional dimension reduction clustering and improves the clustering effect.

LDA's two unsupervised expansion methods, LDA-Km and Un-RTLDA, Un-TRLDA, show high clustering results on seven benchmark datasets, though the Un-TRLDA method is difficult to converge on the dataset Isolet, so the clustering effect on this dataset is not accurate, which also shows that the combination of clustering process and subspace selection process, and the method of data clustering and subspace selection at the same time can effectively reduce the dimension disaster and greatly improve the clustering effect. However, after using Butterworth filter distance, the clustering performance of our method exceeds all the above comparison methods. This is because Butterworth filter distance adopts the nonlinear mapping method and uses prior adjacency graph information, which can better process data and mine data information, thus improving the clustering accuracy more effectively.

4.4 T-SNE Visualization

Figure 2 shows the results of T-SNE visualizations of different algorithms on the JAFFE dataset, each of which divides the JAFFE dataset into ten clusters. The Figure 2.(a) shows the true labels of the JAFFE dataset, and the Figure 2.(b)-(e) show the labels obtained by the comparison clustering algorithms, and the Figure 2.(f) shows the visualization of our method. It can be observed that our method distinctly separates ten samples with clear boundaries, whereas the four comparative algorithms all tend to group samples that are close but belong to two different clusters into one. This is because our method incorporates LDA for dimensionality reduction, performing clustering in the subspace to enhance clustering performance. Additionally, by calculating the distances between sample pairs rather than the distance from samples to cluster centroids, our approach is better equipped to handle nonlinear data.

4.5 Parameter Analysis

Figure 3 illustrates the impact of the parameter λ, with values of 0.0001, 0.001, 0.01, 0.1, and 1, on the clustering performance across six datasets. By examining the three evaluation metrics ACC, NMI, and Purity, it is evident that variations in λ affect the clustering performance on Isolet and MSRC V2 datasets. Different datasets exhibit varying trends in these metrics as λ increases, indicating that the sensitivity of clustering performance to λ values differs among the datasets. These findings suggest that selecting an appropriate λ value is crucial to optimize clustering performance in specific datasets.

4.6 Convergence Analysis

Furthermore, an experiment was conducted to assess the convergence of our method by observing the objective function across multiple iterations on six benchmark datasets. The experimental results, depicted in Figure 4, indicate that our method consistently reaches a stable objective function value with minimal iterations across diverse datasets, thus affirming its strong convergence performance.

5 Conclusion

In this paper, we propose a novel unsupervised discriminative dimension reduction method that successfully integrates the centerless K-means algorithm with Linear Discriminant Analysis (LDA) into a unified framework. This approach not only eliminates the reliance on cluster centroids, which is common in traditional clustering algorithms, thereby enhancing the robustness of the model, but also explores the local neighborhood structure of the data. Additionally, we construct a similarity matrix using a learnable label matrix, which maintains both the neighboring relationships and the cluster structure relationships. Furthermore, by incorporating the Butterworth filter distance to handle nonlinear data, the applicability of the model is further enhanced. The experimental results of our framework on multiple benchmark datasets demonstrate the method's excellent performance in unsupervised dimension reduction and clustering tasks, effectively capturing both the discriminative structure and the local neighborhood structure of the data.

Acknowledgments

This work is supported by the National Natural Science Foundation of China under Grant 62176203, the Fundamental Research Funds for the Central Universities (ZYTS25267, QTZX25004), and the Science and Technology Project of Xi'an (Grant 2022JH-JSYF-0009), Open Project of Anhui Provincial Key Laboratory of Multimodal Cognitive Computation, Anhui University (No. MMC202416), Selected Support Project for Scientific and Technological Activities of Returned Overseas Chinese Scholars in Shaanxi Province 202302, and the Xidian Innovation Fund (Project NoYJSJ25007).