Methodology

To address the aforementioned challenges, we propose a novel method named Transferable Deep Clustering Model (TDCM). To ensure the shared clustering knowledge among domains can be learned unsupervisely, we propose an end-to-end learning framework that jointly optimizes the feature extraction encoder and a learnable clustering module, as depicted in Figure 2(a).

The framework aims to utilize the learned model parameters to capture the shared intra-cluster and inter-cluster structure derived from trained cluster patterns. Consequently, this enables effective transfer of the shared knowledge to unseen data from new domains. To adjust the learned knowledge to the target domains, instead of optimizing a fixed set of centroids, a novel learnable attention-based module is proposed to automatically adapt centroids to the new domains, as shown in Figure 2(b). Therefore, the learned clustering model is not restricted to the trained source domains and can be easily generalized to other domains. Specifically, this module integrates a cluster-driven bi-partite attention block to update centroids, considering the similarity relationships among data samples and capturing underlying structures and patterns. Furthermore, we provide theoretical evidence to demonstrate the strong expressive power of the proposed attention-based module in representing the relationships among data samples. Our theoretical analysis reveals that traditional centroid-based clustering models like k-means or GMM can be considered as special cases of our model. This theoretical proof highlights the enhanced capabilities of our approach compared to traditional clustering methods, emphasizing its potential for mining complex cluster patterns from data.

Transferrable Cluster Centroids Learning Framework

As previously discussed, existing deep clustering models typically treat centroids as fixed learnable parameters, which limits their ability to generalize effectively to unseen data. To address this limitation, we propose a novel clustering framework that can dynamically adjust the centroids based on the extracted sample embeddings. Consequently, the centroids are dynamically adapted based on the distribution of sample embeddings, endowing the model with the capability to effectively transfer to new domains. As depicted in Figure 2(a), an encoder g is first utilized to extract latent embeddings Z=gϕ(X;ϕ). Then the adaption process involves forward pass on a series of centroids updating blocks: cj(0)j=1K→cj(1)j=1K→…cj(L)j=1K, where each block consists of two steps: assignment and update. In the assignment step of the l-th (l∈[0,L]) block, we compute the probability δij that assigns the data sample zi to the current cluster centroid cj(l) using a score function ℓzi,cj(l), which captures the underlying similarity relationships among samples. Subsequently, we update the cluster centroids based on the assigned data points. The updating process can be mathematically formalized as: where τ denotes the temperature hyper-parameter.

(1) cj(l+1)=1∑iN∑jKδij(l+1)∑i=1Nδij(l+1)zi,δij(l+1)=expℓzi,cj(l)/τ∑j=1Kexpℓzi,cj(l)/τ,

Learnable Centroids Updating Module

Given the overall updating procedure described earlier, a key consideration is the choice of the score function ℓzi,cj to capture the similarity relationship between samples and centroids, thereby capturing the underlying cluster structure. Traditionally, a common approach is to use handcrafted score functions like the Euclidean distance ℓzi,cj=zi-cj2. However, designing a specific score function requires domain knowledge and lacks generalizability across different domains.

To address this issue, we propose a learnable score function ℓzi,cj;W by introducing learnable weights W that automatically capture the relational metrics between samples in a data-driven manner. Notably, the formulation in Equation 1 resembles a bi-partite graph structure of centroids and samples, which is illustrated in Figure 2(b). An attention-like mechanism, which selectively allocates resources based on the relevance of information, can be constructed based on the bi-partite structure. Since the goal of updating centroids is to gradually push centroids to represent a group of similar samples, ideally the score function ℓzi,cj;W should achieve its maximum value when zi=cj. However, a common design of attention mechanism can not guarantee this property due to the arbitrary choice of learnable parameters W (see our proof in Appendix Theorem A.1).

To solve this issue from a theoretical perspective, we propose a novel clustering-driven bi-partite attention module with appropriate constraints on the parameters of learnable matrices. Specifically, the score function is designed as ℓzi,cj;WQ,WK=-σWQzi-cj(l)⋅WKzi-cj(l)/τ with two learnable weight matrices and we rewrite the Equation 1 as: where WQ and WK are two learnable real-symmetic matrices and σ is a continuous non-decreasing nonlinear activation function (e.g. ReLU [22] or LeakyReLU [19]).

(2) δij(l+1)=exp-σWQzi-cj(l)⋅WKzi-cj(l)/τ∑j=1Kexp-σWQzi-cj(l)⋅WKzi-cj(l)/τ,WQ=WQ⊤,WK=WK⊤,

Theorem 4.1. The score function ℓzi,cj;WQ,WK=-σWQzi-cj(l)⋅WKzi-cj(l)/τ defined in Equation 2 can guarantee that ∀zi∈Rb, we have ℓzi,cj≤ℓcj,cj.

Proof. We first define p=zi-cj(l) and rewrite the score function as ℓ=-σWQp⋅WKp/τ. We rewrite the inner product part as Since WQ and WK are two real-symmetic matrices, WQ⊤WK is a positive-definite matrix. For any nonzero real vector p, we have p⊤WQ⊤WKp>0. In addition, due to the property of continuous and non-decreasing, the nonlinear activation function would not change the ordering of values. Therefore, for all zi∈Rb, we have ℓzi,cj≤ℓcj,cj. □

WQp⋅WKp=pWQ⊤⋅WKp=p⊤WQ⊤WKp.

In addition to theoretical property that our centroids updating module can group similar samples within same clusters, we further prove that our defined score function in Equation 2 can theoretically have stronger expressive power in representing the similarity relationship between data samples than traditional clustering technique such as k-means or GMM by the following theorems:

Theorem 4.2. The score function of k-means and GMM models are special cases of our defined score function ℓzi,cj;WQ,WK in Equation 2.

The proof for k-means algorithm is straightforward given here and the proof for GMM models can be found in the Appendix.

Proof. By setting the nonlinear function σ as identity function and both WQ and WK as identity matrix I, we can rewrite the score function as ℓzi,cj=-zi-cj22/τ, which is the negative squared Euclidean distance. Then the model is equalize to a soft k-means centroids updating step. By setting τ→0+, the process converges to the traditional k-means algorithm.

Unsupervised Learning Objective Function

In order to optimize the parameters of the proposed model, the overall objective function of our framework can be written as: Here the first term ℒclustering is aimed at maximizing the similarity scores within clusters: where α(l) are hyperparameters to tune the balance between blocks and orthogonal constraints are incorporated to prevent the trivial solution of scale changes in the embeddings. We can treat the constraints as a Lagrange multiplier and solve an equivalent problem by substituting the constraint to a regularization term.

(3) mingϕ,WQ,WKℒclustering+βℒentropy.

(4) ℒclustering=-∑lLα(l)∑iN∑jKδij(l)ℓgϕxi,cj(l);WQ,WK,s.t.WQWQ⊤=I,WKWK⊤=I

Besides the clustering loss term, the entropy loss term is aimed at avoiding the trivial solution of assigning all samples to one single cluster: where πj(l) reflects the size of each clusters.

(5) ℒentropy=-∑lLαl∑jKπjllogπjl,πj(l)=∑iδij(l)=∑iexp-σWQxijWKxij/τ∑j=1Kexp-σWQxijWKxij/τ,xij=zi-cj(l-1)

Initialization of centroids.

Many previous studies use the centroids provided by traditional clusteing methods such as k-means on the latent embeddings as the initialization of centroids. However, these methods usually requires to load all data samples into the memory, which can be hardly generalize to a mini-batch version due to the permutation invariance of cluster centroids. To solve this issue, we propose to initialize the centroids cj(0)j=1K before blocks as a set of orthogonal vectors in the embedding space, e.g. identity matrix I.

Complexity Analysis

Here we present the complexity analysis of our proposed dynamic centroids update module. In each block, we need to compute the pair-wise scores between centroids and data samples in Equation 2. Assuming the embedding space dimension is denoted as b, the time complexity to calculate the score functions in one block is ONKb2. Consequently, performing L blocks would entail a time complexity of OLNKb2, where N represents the number of samples and K denotes the number of centroids. It is important to note that our framework naturally supports a mini-batch version, which significantly enhances the scalability of the model and improves its efficiency.