Deep Embedding Clustering Driven by Sample Stability

1 Introduction

Clustering [Xu and Wunsch, 2005], one of the most crucial tasks in machine learning, aims to group similar samples into the same cluster while separating dissimilar ones into different clusters. Traditional clustering methods such as k-means [MacQueen, 1967b], spectral clustering [Ng et al., 2001; Yang et al., 2018], Gaussian mixture model [Bishop and Nasrabadi, 2006; Reynolds, 2009] and hierarchical clustering [Sneath and Sokal, 1962; Johnson, 1967; Koga et al., 2007] have achieved tremendous success over the past decades. However, these methods depend on manually extracted features, making them impractical for high-dimensional and unstructured data. Benefiting from the development of deep representation learning, deep clustering arises and has attracted increasing attention recently.

∗The corresponding author

The existing deep clustering methods can be roughly categorized into three types: First, the pseudo labeling deep clustering method [Niu et al., 2020; Niu et al., 2022] filters out a subset of samples with high confidence and trains in a supervised manner, yet, the performance of this method heavily relies on the quality of the filtered pseudo labels, which is susceptible to model capability and hyper-parameter tuning. Second, the self-training deep clustering method [Xie et al., 2016; Guo et al., 2017a] optimizes the distribution of cluster assignments by minimizing the KL-divergence between the assignment distribution and an auxiliary distribution, but the performance of this method is limited by the construction method of the auxiliary distribution. Third, the contrastive deep clustering method [Jaiswal et al., 2020; Jing and Tian, 2020] aims to pull the positive pairs close while pushing the negative pairs far away, this method relies on the construction approach of positive and negative sample pairs. In summary, despite the proposal of numerous excellent deep clustering methods, most of them rely on artificially constructed pseudo targets that require prior knowledge and may heavily impact the clustering results.

In this paper, inspired by traditional clustering methods based on sample stability [Li et al., 2019; Li et al., 2020], we propose a deep embedding clustering algorithm driven by sample stability (DECS). Different from prior methods, our method eliminates the requirement of a pseudo target, and clustering using sample stability as a constraint.

Specifically, our method consists of two stages: representation learning and clustering. In the representation learning stage, we employ a convolutional autoencoder [Guo et al., 2017b] to map the raw data into a latent embedding space that captures the underlying structure of the data. This is

the learned feature representations preserve the essential information from the original input. Subsequently, in the clustering stage, we retain the encoder module of the autoencoder and compute the soft assignment probabilities of each sample to all cluster centroids based on the learned embedding representations, which we refer to as co-association probability. Then, we compute the level of determinacy for each sample with respect to all cluster centers and further calculate the stability of all samples by considering their determinacy levels regarding each cluster center. To the best of our knowledge, our method is the first to utilize the deterministic relationship between samples and centroids for clustering, and innovatively employ the instability of samples as a loss to optimize the parameters of deep neural networks. In summary, the main contributions of this work are as follows:

• The concept of sample stability is extended into deep clustering, and a novel loss function that effectively captures both intra-class and inter-class relationships among the samples is proposed. This approach is then applied in a joint learning framework, which comprises an autoencoder and a clustering layer.
• The model's convergence is theoretically analyzed, providing evidence that clustering with internal sample relationship driven by sample stability can indeed converge.
• Experiments are conducted on five image datasets to validate the effectiveness of our method. The experimental results demonstrate that our approach outperforms the state-of-the-art methods.

2 RelatedWork

This work is closely related to convolutional autoencoder and sample stability, which are briefly introduced in this section.

2.1 Convolutional Autoencoder

Autoencoder is an unsupervised neural network model widely used for tasks like data dimensionality reduction and feature extraction. Deep Embedded Clustering (DEC) [Xie et al., 2016] was the pioneer in utilizing denoising autoencoders for joint learning of feature representations and cluster assignments. Subsequent works, such as IDEC [Guo et al., 2017a], FCDEC-DA [Guo et al., 2018], SDEC [Ren et al., 2019], and others, have built upon DEC's autoencoder framework, and achieved remarkable clustering results.

Due to the limited ability of fully connected layers in extracting features from high-dimensional data, such as images, convolutional autoencoder [Guo et al., 2017b] was proposed by incorporating Convolutional Neural Networks (CNNs) into autoencoders, which showed improved adaptation to image-related tasks. DEPICT [Ghasedi Dizaji et al., 2017], ConvDEC-DA [Guo et al., 2018], DBC [Li et al., 2018], StatDEC [Rezaei et al., 2021], and so on, have adopted convolutional autoencoders instead of fully connected autoencoders in order to learn feature representations and achieve superior clustering results.

2.2 Sample Stability

The concept of sample stability [Li et al., 2019] was first proposed in clustering ensembles. Clustering methods based on sample stability aim to explore the indeterminacy of sample relationships and identify sets of samples with stable relationships. These approaches leverage pairwise relationships between samples for clustering, which reduces the impact of indeterminate relationships among samples.

Given a set of clustering results, the co-association probability between two samples can be represented by their frequency of belonging to the same cluster based on their similarity. A co-association probability value of one indicates high determinacy that the samples belong to the same cluster, while a value of zero indicates high determinacy that they do not belong to the same cluster. However, when the value falls between zero and one, it becomes difficult to definitively determine whether the two samples belong to the same cluster, resulting in a low determinacy. Due to the insufficiency of using co-association probabilities alone in reflecting the level of determinacy regarding whether two samples belong to the same cluster, the determinacy function [Li et al., 2019] was proposed to evaluate the level of determinacy between two samples. Then, the stability of sample xi is defined as the average level of determinacy among sample xi and all other samples based on their co-association probability values:

where n represents the number of samples in the dataset, and pij ∈ P, P = {pij|1 ≤ i ≤ n, 1 ≤ j ≤ n} denote the coassociation probability of sample xi and xj , and fq (·) denote the determinacy function.

Subsequently, SSC [Li et al., 2020] extended the concept of sample stability from cluster ensembles to clustering analysis and proposed a new function for measuring sample stability in cluster analysis, and the theoretical validity of sample stability was analyzed in this work.

Although the clustering methods based on sample stability [Li et al., 2019; Li et al., 2020] provide new ideas for clustering, these methods are heuristic approaches that only use sample stability as an evaluation function. However, utilizing sample's stability to guide clustering optimization has not been well studied.

3 Method

In this section, we present the proposed Deep Embedding Clustering Driven by Sample Stability (DECS) model. Our model first trains a convolutional autoencoder and then utilizes sample stability as guidance to accomplish clustering. Fig.1 illustrates the overall process.

3.1 ProblemFormulation

In this paper, we aim to cluster a set of n samples X = {xi}ni=1 from the input space X ∈ Rd into k classes using a clustering network. Distinguishing with the prior works, we reconsider the problem of clustering in deep neural networks by introducing constraints on the relationships among samples, and make the first attempt to reduce the calculation of sample stability from n2 to kn. Our method first employs an autoencoder to map the sample set X into a representation space, and then utilizes sample stability as a constraint to achieve sample clustering.

To this end, the objective function of our framework can be formulated as:

where Lr and Lc represent the reconstruction loss and clustering loss, respectively.

3.2 Extract Features with Convolutional Autoencoder

To accurately represent each sample with an embedding vector, we employ a convolutional autoencoder as the feature extractor, an encoder fθe is used to map a sample xi ∈ X to its latent embedding vector zi ∈ Z, while a decoder gθd reconstructs xi from its embedding vector zi. To be specific, given a set of samples X = {xi ∈ Rd}ni=1 , a random transformation Trandom is applied to each sample xi to obtain the augmented sample x′i = Trandom (xi), and then serve as the inputs of convolutional autoencoder, which extracts the latent embedding representation of each sample from its internal layers by minimizing the reconstruction loss:

where n represent the number of samples.

The convolutional encoder is utilized to capture the essential information of the samples, while a convolutional decoder is employed to validate and enhance the representation ability of the embedding vectors. This process can be expressed as:

where θe and θd represent the parameters of the convolutional encoder and decoder, respectively, σ is the activation function such as ReLU, H denotes the group of latent feature maps, Wi and bi correspond to the filter and bias of the ith feature map in the encoder, similarly, ˜W and ci are the corresponding parameter in the decoder, and ∗ denotes the convolution operation.

3.3 Clustering with Sample Stability

In the clustering stage, we utilize the encoder trained in the previous stage as the feature extractor and then fine-tune the encoder using sample stability as guidance, which ensures that it learns cluster-oriented sample representations. For the sake of writing and understanding, we consider only a single sample and describe the computational processes in vector form in the following description. We introduce the notation I ∈ R1×k as a row vector with all ones, and T denotes the transpose of a vector.

In the clustering stage, we first perform k-means clustering in the embedding space to obtain initial centroids m = [m1,m2, . . . ,mk] ∈ Rk×d , where k and d represent the number and dimension of centroids, respectively. Next, we calculate the assignment probability between a sample embedding zi and the centers m of all clusters by a Student's t-distribution:

where qi ∈ R1×k , Zi = IT · zi represents the dimension broadcasting of the embedding representation for the ith sample xi, and E is an identity matrix.

Then, the determinacy among sample xi and all centroids is determined by a mapping function as follow:

here, t represents the co-association probability at the lowest level of determinacy, which is adaptively determined using Otsu's method, Qi = qi - t,Qi ∈ R1×k indicates the offset of qi with respect to the threshold t, diag denotes the construction of a diagonal matrix from a vector, and 1(·) repre-

Algorithm 1 Algorithm of DECS

Input: Dataset X, Number of cluster k, Maximum iterations MaxIter;

Output: Cluster center m, Cluster assignment s;

• 1: Initialize autoencoder's weight by (2) with X;
• 2: Initialize m and s with k-means algorithm;
• 3: while iter ≤MaxIter do
• 4: compute the co-association probability matrix of samples x ∈ X and centers m by (5);
• 5: compute the determinacy between samples x ∈ X and centers m by (6);
• 6: compute the stability sq of n samples x ∈ X by (7);
• 7: update encoder's weight and m by optimizing (16)(17);
• 8: end while
• 9: return Cluster center m, Cluster assignment s by maximizing sq.

sents an indicator function that equals one only when a certain condition is satisfied, and zero otherwise.

After obtaining the determinacy relationship between each sample-center pair, the stability of sample xi can be calculated based on the following formula:

here, k represents the number of clusters, λ is a proportionality coefficient, tr denotes the trace of a matrix. That is, the first and second terms of Eq. (7) represent the mean and variance of fqi, respectively.

Based on the above discussion, we can obtain the stability of each sample. During the process of clustering, we utilize instability as the loss and optimize the network parameters by minimizing this loss. Thus, our clustering loss function can be formulated as:

where n denotes the number of samples, sq = {sqi}ni=1 , sq ∈ Rn×1 represents the stability of the n samples.

By optimizing this objective function, we can gradually move each sample close to its corresponding cluster and farther away from other clusters. This results in a high level of stability of all samples, close to one. The training steps of the proposed DECS are shown in Algorithm 1.

3.4 Optimization and Convergence Analysis

At each epoch, our model jointly optimizes the cluster centers {mj} and neural network parameters θ using stochastic gradient descent with momentum. Firstly, the gradients of Lc with respect to sq can be expressed as follows:

Secondly, the gradient of stability sqi of the ith sample with respect to deterministic fqi can be written as:

We proof the correctness of Eq. (10) as follow:

Proof. According to Eq. (7),

So, we can easily conclude Eq. (10).

Thirdly, the gradient of determinacy fq (qij) with respect to qij can be written as follow:

and thus the gradient of determinacy fqi with respect to qi can be written as

where qij and fq (qij) represents the j th element of qi and fqi, respectively.

Lastly, for simplicity, we let α = 1 and

The gradient of qi with respect to zi and m can be expressed separately as:

Proof. According to Eq. (5),

Based on Eq. (13), we can easily conclude Eq. (14) and Eq. (15).

Therefore, the gradients of Lc with respect to the latent embedding zi and cluster centroid m are be computed as:

Then, the gradients ∂Lc ∂zi are propagated to the neural network and used in backpropagation to compute the network's parameter gradient ∂Lc ∂θ . Through iterating these updates, the model finds the optimal clustering result. The training process is repeated until the convergence condition is met.

To validate the correctness of the optimization process, Fig.2 presents the graphs of functions and their derivatives involved in computing sample stability for the case of two classes.

Furthermore, We have theoretically proven the convergence of the loss Lc with respect to the centroids m.

Proof.

Lemma 1. [Nesterov, 1998] Let f be Lipschitz continuous on the ball B2 (x∗ , R) with the constant M and ||x0 - x∗ || ≤ R.

Then

where hi represents the step size and M is termed as the Lipschitz constant.

According to Lemma 1, its convergence can be determined by the initial solution and step size when the loss function satisfies Lipschitz continuity. Consequently, we can conclude based on Lemma 1 that the objective function Lc is convergence i.f.f. || ▽ Lc|| ≤ M. In other words, to verify the convergence of Lc, it is necessary to prove the existence of an upper bound for its derivative.

For the sake of simplicity, a centroid mj is used as an example for the convergence analysis, and we only consider the case where qij < t, while the case of qij ≥ t can be similarly treated. We can know:

where sq(xi), fq(qij) and qij represents the stability of ith sample, determinacy and co-association probability of the ith sample with respect to the j th centroid.

For the first term of the Eq.(19), it is clear that ∂Lc ∂sq(xi) = - 1n , and as for the second item, we know that:

here, µ represents the mean of {fq(qij)}kj=1 and 0 ≤ f q(qij ) ≤ 1.

For the third term of the Eq.(19), in the case of qij < t:

and for the last term of the Eq.(19), we know that:

where, zi represents the ith sample embedding, 1 + ||zi - mj ||2 /α ≥ 1, and qij (1 - qij) ≤ 1 4 due to 0 ≤ qij ≤ 1.

According to the above analysis, we can conclude that the upper bound for the loss Lc:

That is to say, there exists M > 0 such that ||▽Lc|| ≤ M, where M = 2(1+2λ)(α+1) 4nkt2α max(||zi -mj||). In fact, there exists an upper boundary of ||zi -mj|| for any real-world dataset.

4 Experiments

In this section, we evaluate the effectiveness of the proposed DECS method on five benchmark datasets. We also present the visualization of sample distribution and analyze how these hyperparameters impact the performance.

4.1 Datasets and EvaluationMetrics

In order to validate the performance and generality of the proposed method, we perform experiments on five image datasets, as shown in Table 2. Considering that clustering tasks are fully unsupervised, the training and test split are merged in all our experiments.

Two widely-used unsupervised evaluation metrics including cluster accuracy(ACC) and normalized mutual information(NMI) are used to validate the performance of the proposed model. Higher values of these metrics indicate better clustering performance.

4.2 Baseline Methods

In the comparative experiments, our proposed method was compared with several representative conventional baseline, including: k-means [MacQueen, 1967a], GMM [Reynolds, 2009], sc-Ncut [Shi and Malik, 2000], SC-LS [Chen and Cai, 2011] and AC-GDL [Zhang et al., 2013]. In addition, our method was compared with several state-of-the-art deep clustering algorithms. To ensure the fairness of our experiments, we have selected comparative methods that utilize autoencoders as feature extractors, including: DEC [Xie et al.,

2016], IDEC [Guo et al., 2017a], DCEC [Guo et al., 2017b], VaDE [Jiang et al., 2016], JULE [Yang et al., 2016], DEPICT [Ghasedi Dizaji et al., 2017], IDCEC [Lu et al., 2022], TELL [Peng et al., 2022], AdaGAE [Li et al., 2021], MI-ADM [Jabi et al., 2019], DSCDA [Yang et al., 2019], DynAE [Mrabah et al., 2020], ASPC-DA [Guo et al., 2019], TDEC [Zhang et al., 2023] and DeepDPM [Ronen et al., 2022].

4.3 Experiment Results

Table 1 presents the performance of our method and other comparative methods. For the compared methods, if their results on some datasets were not reported, we ran the released code with hyperparameters mentioned in their papers, and the results are marked by (*) on top. When the code is not publicly available or running the released code is not practical, we replaced the corresponding results with dashes (-).

It be seen from Table 1 that the proposed DECS algorithm achieves superior clustering results across all datasets. Specifically, on the USPS dataset, our algorithm achieves a clustering accuracy of over 99%. It outperforms the secondbest ASPC-DA by 1.0% and 2.5% on ACC and NMI, respectively. Furthermore, our method significantly outperforms several classical shallow baselines, which can be attributed to the utilization of a multi-layer convolutional autoencoder as the feature extractor.

Furthermore, we also performed t-SNE visualization to compare the cluster structures obtained using different clustering algorithms on the USPS dataset, as shown in Fig.3. Specifically, Fig.3 (a)-(e) represent the clustering results obtained by algorithms DEC, TELL, AdaGAE, ASPC-DA, and DeepDPM, respectively, while Fig.3 (f) represents the clustering result of our proposed algorithm. It is evident that our proposed algorithm is able to achieve clearer and more accurate cluster structures, which further proves the effectiveness of the proposed algorithm.

In addition, we have investigated the sensitivity of our model to the parameters α and λ using the USPS, MNIST and Fashion datasets, and the results are shown in Fig.4. Specifically, Fig.4 (a), (c) and (e) display the results of ACC from different parameter settings on USPS, MNIST and Fashion datasets, and Fig.4 (b), (d) and (f) show the results of NMI. According to the figure, we can observe that the variation of hyperparameters has little effect on the clustering performance, which indicates that our model is not sensitive to the initialization of hyperparameters.

4.4 Implementation

For all datasets, we specify that the encoder to consists of four convolutional layers with channel sizes of 32, 64, 128, and 256, respectively. Each convolutional kernel has a size of 3×3 and uses a stride of 2. Furthermore, batch normalization and max pooling layers are added after each convolutional layer. The decoder uses a network that mirrors the encoder's structure. Additionally, ReLU is utilized as the activation function for all convolutional layers in the model.

During the training process, data augmentation techniques such as random rotation, translation, and cropping are applied to improve the neural network's generalization ability. In addition, the autoencoder is trained end-to-end for 500 epochs using the Adam optimizer with default parameters in Keras. Then, the encoder is further trained for 10000 iterations with a batch size of 256. The coefficient λ for variance is set to 0.8 during the calculation of sample stability. Our source code is publicly available at: https://github.com/ChengZhanwen/DECS.

5 Conclusion

In this paper, we proposed a deep embedding clustering algorithm driven by sample stability. The algorithm combines a convolutional autoencoder model with a clustering layer that relies on sample stability. Unlike previous methods, our method constrains the sample using sample stability, eliminating the need for artificially constructed pseudo targets. This mitigated the clustering biases caused by inappropriate pseudo targets and significantly improved the reliability of the clustering results. We analyzed the convergence of the proposed DECS model, and the experimental results on five image datasets indicate that our algorithm achieve superior clustering performance. In the future, incorporating more complex representation learning models and applying our approach to a wider range of real-world datasets may be an intriguing and practical avenue for research.

Acknowledgments

This work was supported by the National Science and Technology Major Project under Grant (No.2021ZD0112400), the National Natural Science Foundation of China (Nos. 62136005, 62106132, 62306170, 62306171), the Science and Technology Major Project of Shanxi (No. 202201020101006), the Special Fund for Science and Technology Innovation Teams of Shanxi Province (No. 202304051001001).

Contribution Statement

All authors conceived this paper. Zhanwen Cheng and Feijiang Li contributed equally to this work.