Unified K-Means Clustering with Label-Guided Manifold Learning

Thank you very much for your recognition and valuable comments. We provide the following responses according to your questions:

1. Explain the formula (20) to (24)

A: We compute the $\ell_{2,1}$-norm of the cluster indicator matrix $\mathbf{F}^\top$ and then maximize this term to achieve balanced clustering. Equations (20) to (24) are used to prove that when maximizing the $\ell_{2,1}$-norm of matrix $\mathbf{F}^\top$, its optimal solution is a discrete matrix $\mathbf{F}$. We will make a detail explanation for them.

2. Is label matrix F a discrete hard label or a continuous label

A: We have demonstrated that problem (24) reaches a maximum when $\mathbf{F}$ is a discrete indicator matrix, and thus, the final optimized matrix $\mathbf{F}$ is a discrete hard label.

3. The difference of the proposed method from existing works addressing centroid initialization sensitivity and its advantages

A: To avoid the impact of center initialization on K-means clustering, methods such as K-means++, K-sum, and K-sum-X have been proposed. K-means++ randomly selects a point from the dataset as the first cluster center. For all unselected points in the dataset, it calculates the minimum Euclidean distance to the currently selected center and then randomly selects the next cluster center based on the squared distance as a probability weight, until convergence. Although K-means++ alleviates the sensitivity of K-means to initial centers to some extent, it still relies on the computation of cluster centers and may be affected by outliers. K-sum and K-sun-X, on the other hand, do not directly compute cluster centers but perform clustering based on the relationships between data points. While these two methods address the sensitivity of K-means to initial centers, they do not consider balanced clustering. Compared with these methods, our methods introduces the $\ell_{2,1}$-norm regularization term to prevent certain clusters from containing too few or too many data samples, addressing the impact of imbalanced datasets on the model and achieving more balanced clustering results.

Thank you very much for your recognition and valuable comments. Here are our responses:

1. Connection to manifold learning and its advantages

A: We have shown the equivalence between K-means and manifold learning by transforming K-means into the form of manifold learning using the cluster indicator matrix to construct the similarity matrix $\mathbf{S}$. This transformation eliminates the need to compute cluster centers and allows K-means to explore the local manifold structure of the data, making it suitable for nonlinear datasets.

2. The significance of balanced clustering

A: Many clustering algorithms like K-Means are based on distance tend to assign more data samples to larger clusters, which may lead to a decrease in algorithm performance because some datasets may contain outliers or noise. K-means may group the majority of samples into one cluster while assigning outliers to another cluster. Balanced clustering can avoid it by ensuring the sample number of each cluster to be roughly the same, thereby achieving better stability and reliability. In summary, balanced clustering enhances resistance to outliers.

3. The reason for that the final model is min tr(FᵀDF) without the matrix P, and the relationship between matrix P and matrix F

A: According to Theorem 3.1, $\mathbf{G} = \mathbf{F}\mathbf{P}^{-1/2}$, where $\mathbf{P} = diag(p_1, \ldots, p\_c)$ and $p\_k = \sum\_{i=1}^{n} \mathbf{F}\_{ik}$. Since $\mathbf{F}$ is a cluster indicator matrix, $\mathbf{F}\_{ik} = 1$ when the $i$-th sample belongs to the $k$-th cluster. Each column of the matrix represents a class. Therefore, we can say that the $k$-th element of matrix $\mathbf{P}$ is actually the number of samples in the $k$-th cluster, which can also be rewritten as $\mathbf{P} = \mathbf{F}^\top \mathbf{F}$. Our model implements balanced clustering, ensuring that the number of samples in each cluster is equal. Thus, $\mathbf{P} = \mathbf{F}^\top \mathbf{F} = \frac{n}{c}\mathbf{I}$, where $n$, $c$, and $\mathbf{I}$ represent the number of samples, the number of clusters, and the identity matrix, respectively. Ignoring the constant term, the optimization problem $\min tr(\mathbf{G}^\top \mathbf{D} \mathbf{G})$ becomes $\min tr(\mathbf{F}^\top \mathbf{D} \mathbf{F})$.

4. How to choose the parameter $a$ for the low-pass filtering distance

A: Our low-pass filtering distance assigns a smaller distance to samples with high similarity and a larger distance to samples with low similarity, effectively pulling similar samples closer and pushing dissimilar samples farther apart. The advantage is that it increases the discriminability of samples by making dissimilar samples more distant. The parameter $a$ controls the degree of this pulling and pushing. However, a higher value of $a$ is not always better because it may also push similar samples farther apart, which is not conducive to clustering. Therefore, we choose $a = 1$ or $2$ for our low-pass filtering distance to better handle nonlinearly separable data.

Thank you very much for your recognition and valuable comments. Here are our responses:

1. Necessity of balanced clustering

A: Many clustering algorithms like K-Means are based on distance tend to assign more data samples to larger clusters, which may lead to a decrease in algorithm performance because some datasets may contain outliers or noise. K-means may group the majority of samples into one cluster while assigning outliers to another cluster. Balanced clustering can avoid it by ensuring the sample number of each cluster to be roughly the same, thereby achieving better stability and reliability. In summary, balanced clustering enhances resistance to outliers.

2. The reason for better performance against other centerless methods (K-sum and K-sum-x)

A: K-sum is a clustering algorithm based on a k-NN graph, and K-sum-X is a variant of K-sum that does not rely on a k-NN graph but directly uses features for clustering. These two comparison algorithms do not require the initialization and computation of cluster centers. Compared with these two methods, our method further introduces a balance regularization term, which has been demonstrated to be effective to improve clustering performance. Thus, our method achieves better performance than these two methods.

3. The technique to optimize the non-convex $\ell_{2,1}$-norm regularization term

A: The $\ell_{2,1}$-norm regularization is indeed a non-smooth problem, making our final model (26) difficult to solve directly using coordinate descent. Therefore, we perform a first-order Taylor expansion on the regularization term and transmit it into an iterative problem as (29), which is a convex function with respect to matrix $\mathbf{F}$, successfully addressing the non-convex issue of $\ell_{2,1}$-norm regularization term.

4. The reason of same method’s different performance across different datasets

A: Datasets may have vastly different distributions and structures. Some datasets may have clear and separable clusters, while others may have overlapped or nested clusters. The complex structure of datasets can affect clustering performance. For example, the FERET and Mpeg7 datasets have dimensions of 6400 and 6000, respectively, and numbers of clusters of 200 and 70. Unsupervised clustering methods might not realize satisfactory performance when directly applied to these high-dimensional datasets with many clusters. For the balanced CMUPIE dataset, comparison algorithms achieve an average clustering accuracy of 0.1920, while our method, with the balance regularization term, reaches 0.3478. Overall, the different structures of datasets directly affect clustering performance, but our method, with the introduction of the balance term, performs better than other K-means clustering methods.

Thank you very much for your recognition and valuable comments. Here are our responses:

1. The method relies on selection of $\lambda$

A: In the model proposed in this paper, the parameter $\lambda$ is a hyperparameter associated with the $\ell_{2,1}$-norm of the matrix $\mathbf{F}$. It plays a role in regulating the balance of clustering results in the objective function. By adjusting the value of $\lambda$, we can control the extent to which the model focuses on the balance of clusters. When the value of $\lambda$ is large, the model will emphasize the balance of samples in each cluster more, making the number of data points in each cluster as close as possible. The selection of $\lambda$ depends on the structural characteristics of the dataset. A larger $\lambda$ is assigned when the dataset has equal sample sizes per class to ensure balance, while a smaller $\lambda$ is used for uneven distributions to balance results while respecting the original structure. The selection of $\lambda$ will impact the performance, demonstrating the regularization term of $\ell_{2,1}$-norm is effective.

2. Centerless strategy may introduce extra computational overhead

A: Our centerless strategy indeed eliminates the dependence on initial centroids, thereby enhancing the robustness of the algorithm. The core of the centerless strategy lies in computing the distances between sample pairs rather than the distances from samples to cluster centers. This requires us to construct a distance matrix $\mathbf{D} \in \mathbb{R}^{n \times n}$, and then build a similarity matrix $\mathbf{S} \in \mathbb{R}^{n \times n}$ through the cluster indicator matrix $\mathbf{F} \in \mathbb{R}^{n \times c}$, where $\mathbf{S} = \mathbf{F}\mathbf{F}^\top$. We initialize and update the cluster indicator matrix $\mathbf{F}$ instead of relying on the initialization and update of centroids. The complexity required to update the cluster indicator matrix $\mathbf{F}$ through formula (36) is $\mathcal{O}(n^2 c)$ for each iteration. Here, we introduce an acceleration strategy by precomputing and storing $\mathbf{F}^\top \mathbf{D}$, which has a time complexity of $\mathcal{O}(n^2 c)$. Then, we iteratively solve for matrix $\mathbf{F}$ with a time complexity of $\mathcal{O}(n c)$. Therefore, the overall computational complexity of updating $\mathbf{F}$ is $\mathcal{O}(n^2 c + t_1 n c)$, $t_1$ represents the number of iterations. Therefore, the centerless strategy truly increases the complexity, but the acceleration strategy helps to alleviate the computational burden. Although our complexity is $\mathcal{O}(n^2)$, the convergence experiment in the appendix shows that our model can converge quickly within 5 iterations.

3. Initialization of $\mathbf{F}$

A: We initialize the $\mathbf{F} \in \mathbb{R}^{n \times c}$ by setting an identity matrix to every $c$ rows. Specifically, we take the first $c$ rows as an identity matrix, then the second $c$ rows as an identity matrix, and so on.

4. Convergence conditions for Algorithm 1 and Algorithm 2

A: The convergence condition for Algorithm 1 is to check whether the difference between the updated matrix $\mathbf{F}$ and the previous matrix $\mathbf{F}$ is zero. If the difference is zero, the algorithm terminates. For Algorithm 2, we calculate the difference between the objective function values before and after each update of matrix $\mathbf{F}$. If the difference is less than $10^{-6}$, the loop terminates.

5. The reason of "problem (24) only reaches a maximum when F is a discrete label matrix"

A: Problem (24) is a convex optimization problem because the function ${\sum_{k=1}}\mathbf{F}^{2}\_{ik}$ is convex, and the constraints $0 \leq \mathbf{F}\_{ik} \leq 1$, and $\sum\_{k=1}^c \mathbf{F}\_{ik} = 1$ define a compact set. According to convex optimization theory, if a convex optimization problem has a solution on a compact set, then the solution must lie at one of the extreme points of that set. For the compact set $\lbrace \mathbf{f} \in \mathbb{R}^c | \mathbf{f}^\top \mathbf{1} = 1, \mathbf{f} \geq 0 \rbrace$, its extreme points can only be the $c$ one-hot vectors. Thus, we can conclude that problem (24) only reaches a maximum when $\mathbf{F}$ is a discrete indicator matrix.

6. Does graph construction introduce additional computational complexity?

A: In Appendix A.4, we provide details on how to construct the input graph for the low-pass filtering distance. The computational complexity for selecting anchor points using the DAS method and constructing the anchor graph is $\mathcal{O}(nrd + nr \log(r))$, where $n$, $r$, and $d$ represent the number of samples, anchor points, and dimensions, respectively. Therefore, the graph construction will only incur a linear complexity with regard to sample number, which is efficient and will not introduce additional computational complexity.