Unified K-Means Clustering with Label-Guided Manifold Learning
Authors: Qianqian Wang
Mengping Jiang
Zhengming Ding
Quanxue Gao
Venue: ICML 2025 poster (2025)
Keywords: Balanced clustering
unsupervised learning
low-pass filtering distance.
Primary area: general_machine_learning->clustering
TL;DR: This paper introduces a unified manifold-enhanced K-means clustering framework, removing centroid initialization, using multiple distances, and maximizing ℓ2,1-norm for balance, showing top performance on diverse datasets.

Abstract: K-Means clustering is a classical and effective unsupervised learning method attributed to its simplicity and efficiency. However, it faces notable challenges, including sensitivity to random initial centroid selection, a limited ability to discover the intrinsic manifold structures within nonlinear datasets, and difficulty in achieving balanced clustering in practical scenarios. To overcome these weaknesses, we introduce a novel framework for K-Means that leverages manifold learning. This approach eliminates the need for centroid calculation and utilizes a cluster indicator matrix to align the manifold structures, thereby enhancing clustering accuracy. Beyond the traditional Euclidean distance, our model incorporates Gaussian kernel distance, K-nearest neighbor distance, and low-pass filtering distance to effectively manage data that is not linearly separable. Furthermore, we introduce a balanced regularizer to achieve balanced clustering results. The detailed experimental results demonstrate the efficacy of our proposed methodology.

Unified K-Means Clustering with Label-Guided Manifold Learning
Qianqian Wang' Mengping Jiang'
Zhengming Ding? Quanxue Gao
Abstract
sum of squared distances between each data point and its corresponding centroid within cluster.
K-Means clustering is a classical and effective un- supervised learning method attributed its sim- plicity and efficiency. However, it faces notable challenges, including sensitivity to random initial centroid selection, a limited ability to discover the intrinsic manifold structures within nonlinear datasets, and difficulty in achieving balanced clus- tering in practical scenarios. To overcome these weaknesses, we introduce a novel framework for K-Means that leverages manifold learning. This approach eliminates the need for centroid calcu- lation and utilizes a cluster indicator matrix to align the manifold structures, thereby enhancing clustering accuracy. Beyond the traditional Eu- clidean distance, our model incorporates Gaussian kernel distance, K-nearest neighbor distance, and low-pass filtering distance to effectively manage data that is not linearly separable. Furthermore, we introduce a balanced regularizer to achieve balanced clustering results. The detailed exper- imental results demonstrate the efficacy of our proposed methodology.
While K-Means excels in processing linearly separable data, it has limitations when dealing with nonlinearly separable data (Bai & Liang, 2020; Lu et al., 2024; Cheng et al., 2024). This because it utilizes Euclidean distance to mea- sure the distance between data points, making it incapable of dividing nonlinearly separable clusters. To address these limitations, researchers have proposed various improvement methods. For instance, Kernel K-Means (KKM) (Schölkopf et al., 1998) introduces a kernel function to map data into a high-dimensional space, where the transformed data be- come linearly separable. This has led to the development of the Multi-Kernel K-Means (MKKM) algorithm (Du et al., 2015; Yao et al., 2020; Wang al., 2022: Liu, 2022), which utilizes multiple kernel functions capture the nonlinear structure of data better. Another solution is spectral cluster- ing (Ng et al., 2001: Zhou et al., 2020; Ding et al., 2024), an algorithm based on graph theory (Yang et al., 2023b), which utilizes the similarity matrix between data points to project them into a low-dimensional feature space and then applies the traditional K-Means algorithm, making suitable for complex nonlinear data and irregularly shaped clusters (Fettal et al., 2023; Yang et al., 2023a).
1. Introduction
However, the aforementioned K-Means methods all require the initialization of cluster centroids, which can easily lead to suboptimal local solutions rather than the optimal global solution (Nie et al., 2022). K-Means++ (Arthur & Vassil- vitskii, 2006) adopts an improved initialization method that selects initial centroids according to probabilistic distri- bution, resulting in more uniform distribution of initial centroids and reducing the risk of falling into inferior local minima. Nie el al. proposed the Coordinate Descent Method for solving K-Means (CDKM), which can solve a better lo- cal minima of the objective function and effectively address the problem of forming empty clusters (Nie al., 2022). Nevertheless, these methods still require the computation of cluster centroids, which are calculated based on the mean of all points within cluster. Consequently, outliers can sig- nificantly impact the clustering results (Wang & Su, 201 1; Huang et al., 2021; Heidari et al., 2024). Both (Lu et al., 2023) and (Pei et al., 2023) introduce centerless variants of K-Means, which minimize the distance between samples within the cluster instead of the distance between samples
Clustering is an unsupervised learning technique aiming at organizing data groups that exhibit similar characteris- ties without labels (Nie et al., 2023). It has been widely applied in Web data analysis and information retrieval (Fu et al., 2023; He et al., 2024). K-Means (Hartigan& & Wong, 1979; Lloyd, 1982) is one of the simplest and most popular clustering algorithms (Liu al., 2023). Its core concept is partitioning data points into mutually exclusive clus- ters, and with each centroid representing a cluster, each data point is assigned to the cluster associated with its nearest centroid. The algorithm achieves this by minimizing the
'Scooo of Communication Engineering, Xidian University, Xi'an, China. 'Department of Computer Science, Tulane Univer- sity, New Orleans, LA. Correspondence to: Quanxue Gao <qx- gao @ .ediii..dducn>...
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

is scaling parameter, we can Unified K-Means Clustering with Label-Guided Manifold Learning
and the centroids. Therefore, these methods eliminate the need for initializing and updating the cluster centroid, thus
2. Related Work
2.1. K-Means
preventing their negative influence and leading to more ro- bust results and improved clustering performance.
Given data X = {x1, X2,
xx E Rdx=, the num- ber of cluster centroids c, and the cluster centroids u, n4
Although these methods address the centroid initialization problem, they generally overlook the issue balanced clus- tering, resulting in a bias towards larger clusters and smaller clusters being absorbed by larger ones (Malinen & Fränti, 2014). Even worse, all samples might be assigned gle cluster. Balanced clustering, minimize the mean squared eгror (MSE) meanwhile con- sidering the balance of cluster sizes, thus avoiding trivial solutions. Regularized K-Means (RKM) (Lin et al., 2019) introduces regularization terms to control the size of each cluster for achieving balanced clustering, while Discrete and Balanced Spectral Clustering with Scalability (DBSC) mod- ifies the objective function of spectral clustering to promote balanced spectral clustering (Wang et al., 2023). However, these methods ignore the manifold structure and thus cannot exploit explicit cluster distribution.
1
X (k 1,,,.... me is the number of samples
T i=1
in the k-th cluster, the K-Means clustering algorithm aims to minimize the sum of squared distances between each sam- ple and its corresponding cluster centroid. The objective function of K-Means can be expressed as:
sin- the contrary, seeks to
min F
X
Ub
Fik
S.L.
Fe Ind
(I)
1=1
where F E Raxe is a cluster cluster indicator matrix. The i-th row f of matrix F represents the label vector for the i-th sample. Fi 1 indicates that the i-th sample belongs to the k-th cluster, and FiR 0 otherwise. This means that each sample's i label vector f' is one-hot label.
To mitigate these problems, we propose novel unified K-Means clustering framework. We transform traditional K- Means into a label-guided manifold learning version without the need to compute the cluster centroids, thereby improv- ing the robustness of clustering. Specifically, we use the learned cluster indicator matrix to construct a similarity ma- trix, which ensures the consistency of the data manifold structure and cluster labels. Moreover, we maximize the bal- anced regularization term ensure the balance of clustering results and provide the theoretical proof of its effectiveness. Finally, we further introduce four different distances, i.e., Euclidean distance, K-nearest neighbor distance, Gaussian kernel distance, and low-pass filtering distance, which are suitable for nonlinearly separable data and make it adaptive to datasets of various structures. The main contributions of this work can be summarized as follows:
2.2. Kernel K-Means
Kernel K-Means is generalization of the traditional K- Means clustering algorithm. First, a nonlinear mapping func- tion ø is used to map the data points to a higher-dimensionall feature space, and then the traditional K-Means algorithm is applied. Taking the Gaussian kernel K-Means as an ex- ample, its objective function can be expressed as:
Tl
min u.FFF
Σ lxx(x))
uu uell2
Fi
s.t. F Ind
(2)
where u
Σ o(x)) is the centroid of the k-th cluster in the feature space. By em- ploying the Gaussian kernel function K(x,y) x y
Decentralization: We propose a unified K-Means clus- tering framework that eliminates centroid calculations and hence improves the robustness outliers.
exp 20
implicitly compute the inner product or distance in the high-dimensional feature space without the need to explicitly calculate the feature vector @(x). The objective is to minimize the sum of squared distances between each data point and its assigned cluster centroid in the feature space, which allows for the discovery of nonlinear structures of the data.
Label-Guided Manifold Learning: We construct the similarity matrix using learnable cluster indicator matrix, ensuring the consistency of the data's manifold structure and its labels.
We introduce a balanced regular- ization term that maximizes f -norm of the cluster indicator matrix to ensure the balance of clustering results.
Cluster Balance:
2.3. Fuzzy K-Means
We introduce four different distance matrices to explore different K-Means variants and improve clustering performance on nonlinearly separable and complex data.
Four Distance Metries:
Fuzzy K- K-Means is an extension of the traditional K-Means algorithm and diverges from the hard clustering of the tradi- tional K-Means by employing soft clustering, which permits each data point to belong to multiple clusters with certain
2

---

Unified K-Means Clustering with Label-Guided Manifold Learning
degree of membership. This approach offers enhanced flex- ibility, particularly adept handling scenarios where the boundaries between data points are not distinctly defined. The objective function of fuzzy K-Means can be articulated as follows:
Letting the similarity matrix S FP-1F" PP-.FT. then
S1 = FP (1 = F1 Q1
(8)
Equation (8) means that Q is degree matrix of S, then
Equation (7) can be written as:
n
min U2.
x
u F s.L. F.F. F 0,
2
(3)
tr(X(Q - FP F X
xx:
Xj 31125,, Sij (9)
where is all-one vector; is parameter that controls the fuzziness of the membership function; a larger m indicates higher fuzziness.
=1
Therefore, according to Equation (5), Equation (7), and Equation (9), we can conclude that Equation (4) holds and Theorem 1 is proved.
3. A Unified Centerless Framework
Since S GG S (B' g' is the i-th row of G, if the elements of the distance matrix D are defined as Di x; x5ا1 then we have
The K-Means method and variants described above rely on the calculation of cluster centers, making them suscep- tible outliers, which negatively affect clustering sults. To address this issue, we first introduce Theorem 1, transforming the K-Means clustering into a label-guided manifold learning version, which is also equal to unified centerless framework.
min
xx
x, x111
11 Sij
trintrrG DG)
(10)
According to Equation (4), we have:
Theorem Let x; be the i-th sample of data matrix X, Us be the centroid of the k-th cluster. Then, have
X u Fa = min tr (nintr(GTDG)) DG)
(1I)
116
x 1
1 Fik
ΣΣ i=1
x x, S.g.
(4)
1=
Drawing from the Equation (11), we have derived a unified centerless framework for K-Means and manifold learning. This framework not only dispenses with the calculation of cluster centroids but also employs cluster indicator matrix to construct a similarity matrix S, thereby preserving the consistency between the data's 's manifold structure and its labels. In what follows, will discuss the version of K-Means, Kernel K-Means, and Fuzzy K-Means.
where S is the similarity matrix that represents the manifold structure of the data. is constructed from the cluster indicator matrix F, such that GG where G P E Roxe is diagonal matrix, and PRK E Fik
FP-1/2
Proof. Expanding the left side of Equation (4) yields:
(1) K-Means: According to Theorem 1, the objective of traditional K-Means can be reformulated as follows:
x;X;
Fise
2tr
x, mu Fas
+ ug Fix)
min
||x x, x min tr DG)
DGG
min tr (FP-1/2) D(FP-1/2)
(12)
Taking the partial derivative with respect to un and setting it to zero, we find:
min mintr(F (FTT)) s.1. F Tnd
xj F.
Xf.Pr!
(6)
where F E guxe denotes the cluster indicator matrix, and
Pb*
D Raxa represents the distance matrix.
where fg the k-th column vector of F.
(2) Kernel K-Means: When applied Theorem in the kernel space, Equation (2) can be rewritten as
Substituting Equation (6) back into Equation (5) and letting ik.
Q Rax* be diagonal matrix where Q 2 F
that Equation (5) is simplified to:
min F
[x((x)) - o(xx))1 min tr(G DG)
tr
X:X;
Q
tr
X X
min (r DF(FTF)
s.t. F Ind
1=
=tQ(X(Q - FP F
(13)
3

---

Unified K-Means Clustering with Label-Guided Manifold Learning
(x,, x,) + K Xx) 2K (x;;,)) The novel form Equation (13) of Kernel K-Means avoids reliance cluster centroids, en- hancing the method's 's capacity to handle nonlinear data and imparting greater robustness of clustering results.
where Dij [|x(x,) (xxx)
Lemma 1. According to the Cauchy-Schware inequality, let
(ai, 02,-...5 ....... ae) E RRox1,
[1. 1, .... .1] RRox1
Then, we have
Ka, c)1 s ||aa|22
|||l| -
Σ ag S ||l|| v +1+1++... +1)
(3) Fuzzy K-Means: Let Wi ik
F G WP-1/2, GG and P E Rexe be a diagonal matrix where РиК E ik According Theorem I, Equation (3) can be reformulated
k=1
||l|| Ve
ak
(19)
min
xx
Si min grintr(GTT DG) F
The equality holds if and only ifa =
Op.
(14)
According to Lemma 1, maximizing
F 2,, Σi= 0k:
= =min tr W () F. 0
is equivalent maximizing ||a||2. Equation (18), we obtain
By substituting into
F
where the elements of the distance matrix D are defined as Dij = |x, - x,,
n
Therefore, we can say that K-Means, Kernl K-Means, and Fuzzy K-Means are all unified in our centerless manifold framework minp tr(G DG).
|al| =
Σ of
F
F2
(20)
Thus, we have
4. Methodology
max ||al| = max ||all2 max
F
(21)
4.1. Motivation and Objective
We substitute G = FP 1/2 into Equation (10) and rewrite the unified K-Means as minp tr(F (P) Since the cluster indicator matrix F discrete and challenging to optimize directly, and it does ensure balanced cluster- ing, we introduce a balanced regularization term based 22 -norm and obtain the overall objective:
Obviously, each row f of F is independent, so for each row, we have
max F.A
F ik
s.t. 0 S Fik S 1, Σ Fx =1
(22)
1=
The solution to maximizing Equation (22) should be realized when f' has only one element equal to and the rest are O, and the maximum value of Equation (22) should be 1. Thus, we can conclude that Equation (22) of rows reach maximum only when F is discrete cluster indicator matrix.
min tr(F' (F(P)=)) - >||FTI lla.1
s.t. F.FF 0,
(15)
where A is balance parameter. Then, prove that maxi- mizing ||FT 1l2.1 helps to address both issues via Theorem 2.
In this case, F F E Rexe is diagonal matrix whose k- th diagonal element is the number of samples in the k-th cluster, hence:
Theorem Given n1 + + +... ne = n, where ny 2 0 represents the number of samples the k-th cluster. By
achieving the following balanced regularization term, F is
discrete and exhibits balanced cluster distribution, i.e.,
the maximum will be attained when n1
122
ne-
0x.
fg
fg = VTk
(23)
max |
11,,1 s.t. F > O. F1=11
-
(16)
where n& is the number of samples of the k-th cluster, fa is the k-th column of the matrix F.
Proof. Let f _a represents k-th column of F. The f2r1 of the cluster indicator matrix F E Rexn is defined as follows:
According to 01 02 _.... aes we have yni V/222 VTo. and the equality holds if and only if 712 n. n//c.
n a& (17)
Theorem 2 demonstrates that Equation (16) can achieve an approximate cluster balance. When the optimal solution is
12,1
F2 ik
achieved, (F F) V "I. Consequently, our objective
where
function in the Equation (15) can be simplified to:
04
F2
/ fr
(18)
min tr T DF) - A||FT 12,11 s.t. F 0, Fl
(24)
i=1
F

---

Unified K-Means Clustering with Label-Guided Manifold Learning
When Equation (24) achieves the optimal solution, F is discrete and each cluster is balanced.
for the i-th row h', H = [(h')
(Ho) 1]
f
Foj
(h') (Ho) Fa. Note that tr(H F) tr(H H F), and
4.2. Optimization
we have:
The -norm in Equation (24) is difficult to solve directly by gradient descent because of its non-smooth property. To simplify the optimization process, we define f(F)
DF AH -FT) + (Fo) dw
+ (f) d Fo (Fo) ( Doo
|IFT 12,1 and perform first-order Taylor expansion at F(
A(h) f -HH)) FF
as follows:
(30)
Then, removing items related to variable fi, through the properties of trace operation, have:
f(F) = f(F()) + (Vf(F()), F(D)
(25)
where ((t) is the solution the t-th iteration, and (F(( the gradient of || ||,,1- The derivative of [ |2,1 with
tr(F DF - AH AH " + F d (F(h) (F + (2F d. - A(h')T)
(31)
respect to F is denoted as H. given by:
tr (FAFT)
F H
211
FA
(26)
Thus, the problem of updating the i-th row of F can be:
OF
OF
min f((')) Da + (2F di X(h')") f1=1
where A is a diagonal matrix and A&k [T fo E R the kitth column of F.
(32)
As D. = 0(i = 1,,, ,.,,,,,,,),) .n). Equation (32) can be:
Ignoring the constant in the Equation (25), we solve the Equation (24) iteratively as follows
min f f2F, d:0 - A(h')T) + min (2F (22FTd. d; -Ahh)
f
F(++1) = min tr(F' DF) (F)) - (VF(F(') F)
(33)
F
(27)
where d, is the i-th column of D, D = 0. denotes the solution before f is updated. Then, the solution of f can be:
min tr(F DF) Atr(H
So we approximate Equation (24) to Equation (28), is updated by solving the following problem:
1, b arg min d, ))
Fib
(34)
0, otherwise.
min F20,F1=1
tr(F' DF) - F))(H"F)
(28)
The detailed optimization for F summarized in Ap- pendix A.
f Fo Fo D
D d where f Rixe is da Doo
Let F
4.3. Complexity Analysis
the i-th row of the matrix F, Fo ((n-)xx represents the matrix formed by all rows of matrix F except for the i-th row f' d E (= denotes the column vector consisting of all elements of the i-th column d, excluding the element D; of matrix D. Lastly, Doo E (m) represents the matrix formed by all elements of matrix D except for those in the i-th row and i-th column. Obviously, tr(F DF) (r(F' DF), and we have:
When updating the i-th row of F, we compute F d; X(h'),, which requires a time complexity of O(nc) and addition operations. Thus, updating all rows of F necessi- tates complexity of O(n²c), with addition operations. Therefore, the algorithm requires Onn"c nc) for each iter- ation. To address this, we propose acceleration strategy to reduce the time complexity to (nc) during the iteration process. Our algorithm's 's acceleration strategy and pseudo- code flow can be found in the Appendix A.
DR
J
f
DF = ( (Fo)
de Doo
Fo
(29)
=(f') D + (Fo)
do + (f*)
d.FFF.
5. Four methods of calculating distance matrix
(Fo) Fo
In order to demonstrate the applicability of our method to variety of different datasets, we present the following four methods of calculating distance matrices:
h Ho
Let H
h is the i-th row of H. Ho E R (R=-1)) 1)xe
represents the matrix formed by all rows of matrix H except
1. Fuclidean square distance: D,j = ||x; - X,
5

---

Unified K-Means Clustering with Label-Guided Manifold Learning
2. K nearest neighbor distance:
||: -xyll x; E Nx(x)) or xrxj E (xx)))
Dij =
otherwise
where a is large constant, (x,) is the K nearest neigh- bors of the sample x,,
3. Gaussian kernel distance: Dij = [lx(x;) - xx2))112=
K (x,,x; x;) + Xj)
2x,,; xz): where
(a) Two-spiral Dataset
(b) No-structure Dataset
Φ(x) represents the nonlinear mapping of sam- ple x, and the Gaussian Kernel is y(x,y) =
Figure 1. Toy datasets.
X yll" a is scaling parameter.
exp
20²
(Tzortzis & Likas, 2008), RKM (Lin et al., 2019), CDKM (Nie et al., 2022), K-sum (Pei et al., 2023), and K-sum-x (Pei et al., 2023).
4. Low-pass filtering distance: In addition to the three dis- tances mentioned above, we have also introduced low-pass filter distance. A low-pass filter allows low frequencies to pass and blocks high frequencies. With a cutoff frequency 1
6.2. Clustering performance
its amplitude-frequeee frequency characteristic is given We 2TT' by [((WW] = VI+ + (w 2T)² Inspired by this charac-
The experimental results of our method utilizing four dis- tance matrices and six comparative algorithms on ten bench- mark datasets are presented in Tables 1 to 3. The parameter values of our model are in the Appendix A. It is evident that algorithms such as K-Means, RKM, and CDKM, which rely on the initialization of cluster centroids, are susceptible to the influence of these centroids. Additionally, their use of Euclidean squared distance impedes their ability to effec- tively handle complex data structures, resulting inferior clustering performance compared to K-sum and K-sum- X, which leverage neighborhood relationships and do not require cluster centroid initialization. However, these lat- ter approaches operate under the assumption of balanced datasets, potentially limiting their applicability to certain specific data distributions.
teristic, when the similarity matrix R is used as input, if we want to retain samples with high similarity and filter out samples with low similarity to address the issue of non- linear separability, we can rewrite the distance matrix as Diy = a 2 w= R.j. where is hyperparam- eter. Through this filtering function, we can see that the higher the similarity, the smaller the distance, and the lower the similarity, the bigger the distance. This retains samples with high similarity, filters out samples with low similarity, and effectively preserves the intrinsic manifold structure of the data, which can better handle nonlinear separable data.
6. Experiments
In contrast, our four distance-based models employ a center- less approach, all of which have yielded notably improved results. Particularly, ric, which harnesses nonlinear mapping to transform the data's similarity relationships into distance relationships, has demonstrated exceptional performance. This low-pass filtering distance preserves the manifold structure of the data and the consistency of the labels, where higher similarity corresponds shorter distances and lower similarity corre- sponds to larger distances. Consequently, when confronted with non-linearly separable datasets, our low-pass filtering distance- based model exhibits superior clustering outcomes.
In this chapter, we conducted relevant experiments on two toy datasets and ten benchmark datasets, and selected 6 classic clustering comparison algorithms for comparison. Our experiments were conducted on Windows 11 system, 13th Gen Intel(R) Core(TM) CPU, and MATLAB R2023a.
low-pass filtering distance met-
6.1. Benchmark datasets
Datasets: We selected the following ten datasets: CMUPIE (Sim et al., 2002), digits (Kusetogullari al., 2020), FERET (Phillips al., 2000), Mpeg7 (Bober, 2001), olivetti (Samaria & Harter, 1994), Palm', Pengdigits (Liu & Wech- sler, 1997), PEAL (Wang& & Tang, 2004). STL.10 (Coates et al., 2011), and USPS (Hull, 1994). Detailed information on the datasets is provided in the Appendix A.
6.3. Toy datasets
To verify the feasibility of our method nonlinear datasets and demonstrate that our method can achieve cluster balance, we only created the following two datasets.
Comparison Methods: We selected the following six com- parison methods: K-Means (Hartigan& & Wong, 1979), KKM
Two-spiral Dataset: There are a total of four hundred sam- ples, divided into two clusters, with 200 samples in each
http://wwww.ccoll..oo///j.nt.n
6

---

Unified K-Means Clustering with Label-Guided Manifold Learning
Table I. The clustering performances on the CMUPTE, digits, FERET, and Mpeg7 datasets.
Datasets
CMUPIE
digits
FERET
Mpeg7
Methods
ACC
NMI
Purity
ACC
NMI
Purity
ACC
NMI
Purity
ACC
NMI
Purity
K-Means
0.1968
0.4121
0.2145
0.4353
0.4439
0.5966
0.2651
0.6514
0.2975
0.4557
0,6595
0,4856
KKM
0.1915
0.3770
0.2118
0.4368
0.4526
0.6008
0.2157
0.5807
0.2407
0,4993
0.6892
0.5236
RKM
0.1740
0.4182
0.1859
0.4042
0.4181
0.5833
0.3121
0.7090
0.3236
0.5264
0.7126
0,5521
CDKM
0.1994
0.4146
0.2187
0,4338
0.4438
0.5975
0.2834
0.6819
0.3168
0.5091
0.7196
0.5440
K-sum
0.2150
0.4764
0.2283
0.1390
0.3416
0.7422
0.2879
0.6993
0.2921
0,5386
0.7257
0,5721
K-sum-x
0.1754
0.4208
0.1824
0.1412
0.3417
0.7405
0.2936
0.7056
0.3079
0.5393
0.7288
0.5629
Our-ED
0.1765
0.4200
0.1891
0.3855
0.4195
0.5395
0.3000
0.7071
0.3086
0,5714
0.7463
0,5979
Our-KNN
0.3634
0.6375
0.3736
0.4570
0.4636
0.6058
0.3193
0.7183
0.3321
0,5600
0.7280
0,5800
Our-K-ED
0.2171
0,4844
0.2297
0.4550
0.4461
0.5848
0.3107
0.7117
0.3207
0.5650
0.7413
0.5900
Our-L.
0.6341
0.8174
0.6436
0.5073
0.5076
0.6305
0.3257
0.7233
0.3343
0,4600
0.6602
0,4821
Table 2. The clustering performances on the olivetti, Palm, USPS, and Pendigits datasets.
Datasets
olivetti
Palm
USPS
Pendigits
Methods
ACC
NMI
Purity
ACC
NMI
Purity
ACC
NMI
Purity
ACC
NMI
Purity
K-Means
0.4488
0.4697
0.4856
0.7047
0.8947
0.7558
0.6458
0.6026
0.7129
0.6963
0.6705
0.7260
KKM
0.4900
0.4862
0.5233
0.6620
0.8732
0.7065
0.6872
0.6437
0.7565
0.7859
0.7139
0.7859
RKM
0.4922
0.4671
0.5144
0.7690
0.9180
0.7825
0.6241
0.5748
0.7003
0.7296
0.6639
0.7296
CDKM
0.4617
0.4795
0.4896
0.7225
0.9052
0.7745
0.6526
0.6094
0.7237
0.7027
0.6697
0.7226
K-sum
0.4233
0.4282
0.4656
0.8405
0.9405
0.8520
0.6802
0.6274
0.7486
0.7562
0.6743
0.7562
K-sum-x
0.4322
0.4099
0.4467
0.8145
0.9321
0.8295
0.6502
0,5853
0.7150
0.7768
0.7001
0.7768
Our-ED
0,5078
0.4910
0,5256
0.8460
0.9401
0,8555
0.6539
0,5842
0.7164
0.7816
0.7056
0.7816
Our-KNN
0.5767
0.5361
0.5933
0,8585
0.9456
0.8665
0.7545
0.6690
0.7545
0.8406
0.7719
0.8406
Our-K-ED
0.5478
0.5229
0,5700
0.8325
0.9362
0.8440
0.7595
0.6559
0.7595
0.8579
0.7784
0,8579
Our-LF
0,8322
0.8181
0.8322
0.9055
0.9674
0.9105
0.8450
0.7803
0.8450
0.8322
0.7612
0.8322
CDKM use Euclidean distance and are affected by the ini- tialization of cluster centroids, so they cannot effectively separate the nonlinearly separable dataset. Although KKM uses the kernel method to calculate, it still relies on the calculation of cluster centroids, while our method does not require the calculation of cluster centroids and can well maintain the inherent structure of the data.
Table 3. The clustering performances on the PEAL and STL10
datasets.
Datasets
PEAL
STL10
Methods
ACC
NMI
Purity
ACC
NMI
Purity
K-Mcans
0.7206
0.8939
0.7539
0.8088
0.8049
0.8328
KKM
0.7087
0.8624
0.7296
0,9162
0.8548
0.9162
RKM
0.8072
0.9129
0.8181
0.9422
0,8796
0.9422
No-structure Dataset: A dataset of 400 samples without
CDKM
0.7296
0.8967
0.7617
0,8094
0.8053
0.8333
structure as shown in Figure 1.(b), with each sample ran-
K-sum
0.8770
0.9424
0.8811
0.9220
0.8502
0.9220
domly distributed on this two-dimensional plane, which can be used to verify that our method can ensure cluster bal- ance during clustering. For the unstructured dataset, we conducted binary clustering, three-cluster clustering, four- cluster clustering, and five-cluster clustering, as shown in Figure 3. Regardless of how many clusters the unstructured dataset is divided into, cluster balance can be achieved, with the number of samples in each cluster basically remaining consistent.
K-sum-x
0.8491
0.9291
0.8537
0.9215
0.8505
0.9215
Our-ED
0.8596
0.9321
0.8640
0,9212
0,8500
0,9212
KNN-KNN
0.8919
0.9417
0.8939
0.9198
0.8357
0.9198
Our-K-ED
0.8602
0.9317
0.8649
0.9228
0.8516
0.9228
Our-LF
0.8854
0,9446
0.8889
0.9539
0.8969
0.9539
cluster. As can be seen from Figure 1.(a), this is nonlin- early separable data, which can be used to verify the ability of our method to handle nonlinearly separable data. As shown in Figure 2, the results of K-Means, KKM, CDKM, and our method on the double spiral dataset. K-Means and
Under the ideal cluster balance condition, when n = 400 samples are divided into c 2, 3, 4, 5 clusters, the sample number of each cluster should be n/c = 200, 133, 100, 80.
7

---

Unified K-Means Clustering with Label-Guided Manifold Learning
(a) K-Mcans
(b) KKM
(c) CDKM
(d) Ours(LF)
Figure& 2. The clustering results of method and three comparison methads K-Means, KKM and CDKM the two-spiral dataset.
Our(LF)
(a) (Mo0201,199)
(b) Three 13,,132,322)
(c) Four (03,99,100,98)
(d) (1,0080,,,,777822
K-Means
06
66
05
(e) Two(191,209)
(18tc(168,113,11199
(g) Four(96, 10,,,,99,9
(h) 69ve(79,91,69,66
Figure 3. The clustering results of our method the no-structure dataset, different colors represent different clusters.
Appendix A.
Table 4. The value of SSe.
Two clusters
Three clusters
Four clusters
Five clusters
Methods
7. Conclusion
Ours (LF)
2
11
14
18
In this paper, we introduce a novel unified K-Means cluster- ing framework that achieves balanced clustering and elimi- nates the need for computing cluster centroids. Specifically, first unifies the multiple versions of K-Means into label- guided manifold learning version, which utilizes the cluster indicator matrix to construct the similarity matrix and ex- ploit the discriminative manifold structure guided by pseudo labels. Furthermore, it incorporates mnorm based bal- anced regularization to enforce producing a more robust and balanced clustering outcome. Four different distance metrics are introduced enhance the method's flexibility and adaptivity to different data distributions. Especially, the adopted low-pass filtering distance effecttvely handles nonlinear data structures. Finally, experiments on both toy and benchmark datasets demonstrate that our method out- performs comparison approaches.
K-Means
162
1821
106
856
If we make quantitative analysis, and calculate every clustering, the eлror sum of squares of each cluster is SSe Ei= (n - =) the larger the value, the worse balance, the smaller the value, the better the balance. The specific calculation results can be seen in Table 4.
Moreover, from Figure 3.(d) and (e), clustering is not simple linear clustering, and cluster is not just around cluster centroid, which also indicates that our method has good anti-noise performance.
that our
More experiments, including T-SNE visualization, pa- rameter and convergence analysis, can be found in the
8

---

Unified K-Means Clustering with Label-Guided Manifold Learning
Acknowledgements
Fettal, C., Labiod, L., and Nadif, M. Scalable attributed- graph subspace clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 7559-7567, 2023.
This work is supported by the National Natural Sci- ence Foundation of China under Grant 62176203, the Fundamental Research Funds for the Central Universi- ties (ZYTS25267, QTZX25004), and the Science and Technology Project of Xi'an (Grant 2022JH-ISYF-00009, Open Project of Anhui Provincial Key Laboratory of Mul- timodal Cognitive Computation, Anhui University (No, MMC202416), Selected Support Project for Scientific and Technological Activities of Returned Overseas Chinese Scholars Shaanxi Province 2023-02, and the Xidian Inno- vation Fund (Project NoYJSJ25007).
Fu, T., Zhao, X., and Yan, R. Delving into global dialogue structures: Structure planning augmented response selec- tion for multi-turn conversations. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 495 1955505, 2023.
Hartigan, J. A. and Wong, M. A. Algorithm as 136: A k-means clustering algorithm. Applied Statistics, 28(1): 100-108, 1979.
Impact Statement
He, X., Liu, S., Keung, J., and He, Co-clustering for federated recommender system. In Proceedings of the ACM Web Conference, pp. 3821-3832, 2024.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Heidari, J., Daneshpour, N., and Zangeneh, A. A novel
k-means and k-medoids algorithms for clustering non- spherical-shapp clusters non-sensitive to outliers. Pattern Recognition, 155: 10639, 2024.
References
Arthur, D. and Vassilvitskii, S. k-means++: The advantages of careful seeding. Technical report, Stanford, 2006.
Huang, S., Kang, Z., Xu, Z., and Liu, Q. Robust deep k-means: An effective and simple method for data clus- tering. Pattern Recognition, 117:107996, 2021.
Bai, L. and Liang, J. A three-level optimization model for nonlinearly separable clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3211-3218, 2020.
Hull, J. J. A database for handwritten text recognition research. IEEE Transactions on pattern analysis and machine intelligence, 16(5):500-554, 1994.
Bober, M. Mpeg-7 visual shape descriptors. IEEF Transac- tions on circuits and systems for video technology, 11(6): 716-719, 2001.
Kusetogullari, H., Yavariabdi, A., Cheddad, A., Grahn, H., and Hall, J. Ardis: swedish historical handwritten digit dataset. Neural Computing and Applications, 32(21): 16505-16518, 2020.
Cheng, D., Huang, J., Zhang, S., Xia, S., Wang, G., and Xie, J. K-means clustering with natural density peaks for discovering seittrary-shapee clusters. IEEE Transactions on Neural Networks and Learning Systems, 3008) 11090, 2024.
Li, X., Zhang, H., Wang, R., and Nie, F. Multiview cluster- ing: A scalable and parameter-fres bipartite graph fusion method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(1):330-2 2022.
Coates, A., Ng, A., and Lee, H. An analysis of single-layer networks in unsupervised feature learning. In Proceed- ings of the International Conference on Artificial Intelli- gence and Statistics, volume 15, pp. 215-223, 2011.
Lin, W., He, Z., and Xiao, M. Balanced clustering: A uniform model and fast algorithm. In Proceedings of the International Joint Conference Artificial Intelligence, pp. 2987-2993, 2019.
Ding, L., Li, C., Jin, D., and Ding. S. Survey of spectral clustering based on graph theory. Pattern Recognition, 151:110366, 2024.
Liu, C. and Wechsler, H. Pendigit: Pendigit recognition using mlp and rbf networks. Technical report, Boston University, Center for Adaptive Systems and Department Cognitive and Neural Systems, 1997.
Du, I.., Zhou, P., Shi, I.., Wang, H., Fan, M., Wang, W., and Shen, Y.-D. Robust multiple kernel k-means using 121- norm. In Proceedings of the International Joint Confer- ence on Artificial Intelligence, volume 15, pp. 3476-3482, 2015.
Liu, H., Chen, J., Dy, J., and Fu, Y. Transforming complex problems into k-means solutions. IEEE transactions on pattern analysis and machine intelligence, 45(7):9149 9168, 2023.

---

Unified K-Means Clustering with Label-Guided Manifold Learning
Liu, W., He, J., and Chang, S.-F. Large graph construction for scalable semi-supervised learning. In Proceedings of the International Conference on International Conference on Machine Learning. pp. 679-686, 2010.
Schölkopf, B., Smola, A., and Müller, K.-R. Nonlinear com- ponent analysis kernel eigenvalue problem. Neural computation, 10(5):1299-131 1299-131, 1998.
Sim, T., Baker, S., and Bsat, M. The emu pose, illumina- tion, and expression (pie) database. In Proceedings of IEEE International Conference on Automatic Face Ges- ture Recognition, pp. 53-58, 2002.
Liu, X. Simplemkkm: Simple multiple kernel k-means. IEEE Transactions on Pattern Analysis and Machine In- telligence, 45(4):5174-5186 2022.
Lloyd, S. Least squares quantization in pem. IEEE Trans- actions on Information Theory, 28(2): 1982.
Tzortzis, and I Likas, A. The global kernel k-means clus- tering algorithm. In IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computa- tional Intelligence), pp. 1977-1984, 2008
Lu, H., Gao, Q., Wang, Q.. Yang, M., and Xia, W. Center- less multi-view k-means based on the adjacency matrix. In Proceedings of the AAAI Conference on Artificial In- telligence, volume 37, pp. 8949-8956, 2023.
Wang. J. and Su, X. An improved k-means clustering algo- rithm. In IEEE International Conference on Communica- tion Software and Networks, pp. 44-46, 2011.
Lu, H., Xu, H., Wang, Q., Gao, Q., Yang, M., and Gao, X. Efficient multi-view k-means for image clustering. IEEE Transactions Image Processing, 33:273-284, 2024.
Wang. R., Lu, J., Lu, Y., Nie, F., and Li, X. Discrete and parameter- multiple kernel k-means. IEEE Transac- tions on Image Processing, 31:2796-2800 2808, 2022.
Malinen, M. I. and Fränti, P. Balanced k-means for clus- tering. In Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition, pp. 32 41. Springer, 2014.
Wang. R., Chen, H., Lu, Y.. Zhang, Q. Nie, F., and Li, X. Discrete and balanced spectral clustering with scalabil- ity. IEEE Transactions on Pattern Analysis and Machine 2023.
Intelligence, 45 45(12);
Ng, A., Jordan, M., and Weiss, Y. On spectral clustering: Analysis and an algorithm. In Advances in Neural Infor- mation Processing Systems, volume 14, 2001.
Wang. X. and Tang, X. A unified framework for subspace face recognition. IEEE Transactions on pattern analysis and machine intelligence, 26(9):1222-1228, 2004.
Nie, F., Wang, X., Jordan, M. I., and Huang, H. The con- strained laplacian rank algorithm for graph-based cluster- ing. In Proceedings of the AAA/ Conference on Artificial Intelligence, pp. 1969-1976, 2016.
Yang, W., Wang, Y., Tang, C., Tong. H., Wei, A., and Wu, X.
One step multi-view spectral clustering via joint adaptive graph learning and matrix factorization. Neurocomputing, 524:95-103 105, 2023a.
Nie, F., Xue, J., Wu, D., Wang, R., Li, H., and Li, Coordi- nate descent method for k-means. IEEE Transactions Pattern Analysis and Machine Intelligence, 44(5):2371- 2385, 2022.
Yang. X., Zhu, M., Cai, Y., Wang. Z., and Nie, F. Fast spec- tral clustering with self-adapted bipartite graph learning. Information Sciences, 644:118810 10, 2023b.
Nie, F., Li, Z., Wang, R., and Li, X. An effective and efficient algorithm for k-means clustering with new for- mulation. IEEE Transactions on Knowledge and Data Engineering. (5(4):3433-344) 2023.
Yao, Y., Li, Y., Jiang, B., and Chen, H. Multiple kemel k-means clustering by selecting representative kemels. IEEE Transactions on Neural Networks and Learning Systems, 32(1 (2(1))4983-4996 2020.
Pei, S., Chen, Nie, F., Wang, R., and Li, X. Centerless clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):167-181, 2023.
Zhou, S., Liu, X., Liu, J., Guo, X., Zhao, Y., Zhu, E., Zhai, Y., Yin, J., and Gao, W. Multi-view spectral clustering with optimal neighborhood laplacian matrix. In Proceed- ings of the AAAI conference on artificial intelligence, volume 34, pp. 6965-696599 6972, 2020.
Phillips, P. J., Moon, H., Rizvi, S. A., and Rauss, J. The feret evaluation methodology for recogniccnnn algo- rithms. IEEE Transactions on pattern analysis and ma- chine intelligence, 120100:09001104, 2000.
Samaria, F. S. and Harter, A. C. Parameterisation of a stochastic model for human face identification. In Pro- ceedings of IEEE Workshop on Applications of Computer Vision, pp. 138-142, 1994.
10

---

Unified K-Means Clustering with Label-Guided Manifold Learning
A. Appendix
A.I. Acceleration strategy
To enhance the algorithm's efficiency, we calculate and retain the values of 2F d; A(h') for i = 2,,,.... which requires (n²)) time complexity. This allows the resolution of each row, as referenced in Equation (34), to be completed with only e addition operations, resulting in a cumulative total of additions for each iteration.
Before updating the i-th row f' of F, we record the index p corresponding the non-zero element in f'. Then, calculate no changes are necessary; however, if b differs from p. the adjustments to 2f D Xhg for k = p, b are expressed as follows:
Equation (34) to obtain b. If
2f, D 2h2 + D 2 2d,, 2f Ah +- 2f Ah2 2d,
(35)
where fp is the p-th column of F, fg is the b-th column of F. hp is the p-th column of H, h, is the b-th column of H. d; is the i-th column of D. This process involves just two additional operations. Each iteration for this step takes 2v additions, where U S n. Consequently, this method reduces the time complexity per iteration from On ne) to O(ne + 2n), which simplifies to O(nc).
Overall, this approach significantly minimizes the computational load of the algorithm, improving its efficiency. The comprehensive flow of the algorithm can be found in Algorithms and 2.
Algorithm Optimizing
Input: distance matrix D E IR matrix H, hyperparameter X. Initialize: cluster indicator matrix F E Rxxe
Calculate and store 2F D AH n2 = while not converge do for to n do Update p by the index of element in f if n 1 then
continue end if
Compute = argmin(2F' d. T(hh)TTa
if A p then
Update 2f, D Ah (k: p, via Equation (35)
end if end for end while Output E =x
Algorithm 2 Solving problem (24)
Input: distance matrix D E [Raxn, cluster number c, hyperparameter X. Initialize: cluster indicator matrix F e xxx while not converge do Update matrix H by Equation (26); Update matrix by Algorithm I; end while Output F E Rx
A.2. Convergence Analysis
To address the non-smooth issue of the inorm in the objective function (24), we performed Taylor expansion on ((F) || l|2,1 and then solved for the cluster indicator matrix F through multiple iterations. The F(++1) obtained at the
(t + 1) iteration can be derived from:
( = min (r DF) At
(36)

---

Unified K-Means Clustering with Label-Guided Manifold Learning
Since D is a positive definite matrix and ir(H' F) is linear function of F, the formula is convex in F. Because F is discrete cluster indicator matrix with elements valued 0 or 1, and D and H are fixed matrices, the value of the formula varies within a finite range. Furthermore, by updating F through solving the minimization problem, the value of the objective function does not increase. Specifically, after each update, the value of the objective function either remains unchanged or decreases. All iterative results are located in the compact set {F F1 = 1, F > 0}. Therefore, our model convergent and will obtain an optimal solution during the iteration process.
A.3. The information of benchmark datasets
Table 5. The information of datasets.
Datasets
Samples
Features
Clusters
Type
CMUPIE
2856
1024
68
images
digits
4000
256
10
images
FERET
1400
6400
200
images
Mpeg7
1400
6000
70
images
olivetti
900
2500
10
images
Palm
2000
256
100
images
Pendigits
10,992
16
10
images
PEAL
30,863
256
1,040
images
STL10 13000
2048
10
images
USPS
9,298
256
10
images
A.4. Parameter setting
Since Equation (24) contains the parameter X, we need to set the parameter À for all four distances. In addition, Our-KNN
||x ||x- yl?
needs to set the value of the nearest neighbor K; using the Gaussian kernel function K(x,y) exp
the
20
Our-K-ED contains the parameter d.
While utilizing the Low-pass filtering distance defined as Diş = a ( w = R.j. we employ the directly alternate
sampling (DAS) method (Li et al., 2022) to select r anchor points (where r < n)), denoted as A E ıdxrr, The number of selecting anchor points is configured according the ratio range provided (Li al., 2022), where the anchor ratio from 0.1 to 0.9 with a step of 0.1. Subsequently, we apply the method from (Nie al., 2016) to obtain the corresponding anchor graph T Raxr Let p represent the number of neighboring anchor points for each sample; the specific computation formula for the anchor graph T is as follows:
{
M(.. - (xx.,,,,) ph(x, p a
i P
T
- a(x..a)
(37)
j>
where Xx) ||x;
ys1l and a, represents the j-th neighboring anchor point. Finally, based (Liu al., 2010) and the anchor graph T, we can derive the input matrix R for the Low-pass filtering distance as:
R TA TT
(38)
where A grxr has diagonal elements defined A EL= Tiy, with all other elements being zero.
Our-ED: The values of À for CMUPIE, digits, FERET, Mpeg7, olivetti, Palm, Pengdigits, PEAL, STL10, and USPS are 7696000, 2886000, 1000, 1200, 1801000, 13126000, 500000, 88000, 500000, 52600.
Our-KNN: The values of (K, X) for CMUPIE, digits, FERET, Mpeg7, olivetti, Palm, Pengdigits, PEAL, STL10, and USPS are (20, 15000000), (100, 300000), (12, 500000), (19, 2000), (80, 300000), (10, 100000), (712, 100000), (29, 80000), (1000, 80000), (445, 50000).
Our-K-ED: The values (a, A) for CMUPIE, digits, FERET, Mpeg7, olivetti, Palm, Pengdigits, PEAL, STL10, and USPS are 10.1, 0,001), (0.2, 9), (0.2, 0.001), (1, 0.8), (0.5, 9), (0.8, 0.1), (0.09, 500), (16, 0.04), (0.5, 0.001), (0.1, 0.7).
12

---

Unified K-Means Clustering with Label-Guided Manifold Learning
Our-LF: The values of À for CMUPIE, digits, FERET, Mpeg7, olivetti, Palm, Pengdigits, PEAL, STL10, and USPS are 0.43, 0.71, 0.57, 0.23, 0.2, 0.74, 0.6, 0.15, 0.1, 0.82.
A.5. T-SNE visualization the USPS dataset
We have visualized the performance of various methods on the USPS dataset, shown in Figure (. depicts the true cluster labels, while Figure 4.(b)-(g) present the results of the six comparative algorithms. The final subfigure showcases method based the low-pass filtering distance metric.
Examining the true label representation in Figure 4.(a), we observe that clusters 4 and 6, as well as clusters and 10, are relatively proximal to one another. Among the six comparative methods, regardless of whether they are based on Euclidean distance or KNN distances, they struggle to accurately recognize the underlying cluster relationships between these two pairs of closely related clusters. contrast, our low-pass filtering distance-basee clustering approach able to effectively differentiate these proximal clusters, and the resulting clustering outcomes closely align with the true label distribution, exhibiting the most favorable performance.
This visual analysis highlights the ability of our low-pass filtering distance metric to better preserve the inherent manifold structure and cluster proximities present in the USPS dataset, leading to superior clustering outcomes compared to the alternative algorithms considered.
(a) True label
(b) K-Means
(c) KKM
(d) RKM
(c) CDKM
(f) K-sum
(g) K-sum-x
(h) Ours
Figure T-SNE Visualization the clustering effect of our method and comparison methods on the USPS database.
A.6. Parameter analysis
In Figure 5, we further discuss the impact of the parameter À associated with the balanced regularization term on the clustering performance across different datasets. We selected four datasets CMUPIE, digits, olivetti and Palm to investigate this relationship.
The results indicate that the clustering performance exhibits varying trends as a function of À for the different datasets. However, emerges where the clustering performance first inereases and then decreases À is increased. This suggests that the selection of an appropriate value for À is crucial, as overly large small values can lead to suboptimal clustering outcomes.
The observed trends highlight the importance of dataset-specific parameter tuning to achieve the best clustering performance. The careful selection of the À parameter, which controls the sparsity and regularization the model, plays a significant role the effectiveness of the clustering algorithms across diverse data domains.
13

---

Unified K-Means Clustering with Label-Guided Manifold Learning
A.7. Convergence
As shown in Figure 6, our method exhibits rapid convergence on the four evaluated datasets. The final objective function values reach balanced and stable state, and the clustering performance also gradually stabilizes with increasing iteration counts. This observation demonstrates the strong convergence properties of our algorithm and the effectiveness of the optimization process underlying our algorithm.
CMUPIE
(b) digits
(c) olivetti
(d) palm
Figure 5. The evaluations of clustering performance with parameter À on CMUPIE and digits datasets.
311
Qsede paruraato
Olpestiv
ACC Parly
300
(a) CMUPIE
(b) digits
(c) olivetti
(d) palm
Figure 6. Objective loss and clustering performance with iterations on CMUPIE and digits datasets.
14


Reviews:
[{"review_id": "rGCeU9ZLrV", "reviewer": "Reviewer_w5A2", "summary": "This work introduces an innovative centerless K-means clustering framework combined with manifold learning to improve clustering robustness and accuracy. By eliminating centroid initialization and utilizing a label matrix for similarity computation, the proposed method aligns manifold structures with class labels. Additionally, four distance metrics, including low-pass filtering distance, are incorporated to enhance adaptability to complex data. Theoretical derivations and comprehensive experiments on benchmark datasets demonstrate the effectiveness of the approach.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your recognition and valuable comments. Here are our responses:\n\n**1. The method relies on selection of $\\lambda$**\n\n**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.\n\n\n**2. Centerless strategy may introduce extra computational overhead**\n\n**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.\n\n**3. Initialization of $\\mathbf{F}$**\n\n**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. \n\n**4. Convergence conditions for Algorithm 1 and Algorithm 2**\n\n**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.\n\n**5. The reason of \"problem (24) only reaches a maximum when F is a discrete label matrix\"**\n\n**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.\n\n**6. Does graph construction introduce additional computational complexity?**\n\n**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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "K-means clustering has gained widespread attention for its simplicity and effectiveness. However, it inevitably struggles with nonlinear data and requires cluster centroid initialization, making it susceptible to noise. This paper reconstructs the K-means objective based on label-guided manifold learning, effectively addressing these shortcomings in the relevant field.", "essential_references_not_discussed": "I personally believe that the related work it mentions is quite comprehensive.", "other_strengths_and_weaknesses": "This paper proposes a centerless K-Means clustering method based on manifold learning, which enhances clustering stability and robustness while improving adaptability to nonlinear data structures. Experimental results indicate that it outperforms traditional K-Means and some improved methods. \n\nHowever, this approach relies on the selection of the parameter $\\lambda$. Additionally, although its centerless strategy eliminates sensitivity to initial centroids, it may introduce extra computational overhead under certain data distributions.", "other_comments_or_suggestions": "The authors should pay more attention to some formatting details. For example, equation (12) does not explain what the matrix D is, the notation for the trace (tr) in equation (16) is inconsistent, as it uses both text and character formats, along with a series of similar issues.", "questions_for_authors": "1.\tHow is the matrix F initialized, and what are the convergence conditions for Algorithm 1 and Algorithm 2?\n2.\tWhy is there the conclusion that \"The solution to the maximization problem (24) should be realized when F_i has only one element equal to 1 and the rest are 0, and the maximum value should be 1. Thus, we can conclude that the problem (24) only reaches a maximum when F is a discrete label matrix\"?\n3.\tThe input to the low-pass filter distance is a graph; does the graph construction process introduce additional computational complexity?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oQ3X4AtUgx", "reviewer": "Reviewer_sTfJ", "summary": "The manuscript presents a new balanced k-means clustering framework based on manifold learning for k-means clustering problem. The framework formulates balanced k-means as an optimization problem about the clustering label matrix and realizes clustering in one step by minimizing the objective function. In this paper, it is proved that k-means is equivalent to manifold learning under certain circumstances. Unlike traditional k-means, the model does not require centroid initialization, which the authors claim could lead to more robust results. The convergence can be accelerated by a pre-computational strategy.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your recognition and valuable comments. Here are our responses:\n\n**1. Necessity of balanced clustering**\n\n**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.\n\n**2. The reason for better performance against other centerless methods (K-sum and K-sum-x)**\n\n**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.\n\n**3. The technique to optimize the non-convex $\\ell_{2,1}$-norm regularization term**\n\n**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.\n\n**4. The reason of same method’s different performance across different datasets**\n\n**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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. The paper presents Theorems 3.1 and 4.1, both of which are accompanied by proofs. Theorem 3.1 establishes the equivalence between K-means and manifold learning, with a proof that is clear and well-structured, and Theorem 4.1 discusses the ability of this method that supports the balanced clustering.", "experimental_designs_or_analyses": "Yes. The dataset used in the experiment covers a wide range of categories and quantities, enabling a comprehensive presentation of the results. Additionally, the comparison of experimental methods includes advanced models from the past three years, enhancing the credibility of the experimental results.", "relation_to_broader_scientific_literature": "Compared to previous studies, the highlights of this research lie in centerless clustering, which effectively reduces the impact of outliers on clustering results. Additionally, by incorporating manifold learning, the method better handles nonlinear structured data. Lastly, the introduction of a balanced regularization term ensures more balanced clustering results and prevents trivial solutions.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength: The advantage of this research lies in the innovative combination of two traditional machine learning methods, K-means and manifold learning, and the rigorous derivation process that demonstrates the scientific validity of the approach. Furthermore, its effectiveness is well demonstrated through comprehensive datasets and experimental comparisons.  \n\nWeakness: However, the explanation of the necessity of balanced clustering is somewhat lacking. Providing additional clarification on this aspect would enhance the readability of the paper.", "other_comments_or_suggestions": "The subheadings of Figures 6(b), (c), and (d) contain errors and should be replaced with the correct dataset names.", "questions_for_authors": "1.\tIn the comparative experiments, K-sum and K-sum-x should also be centerless clustering methods. Why does your method achieve better results?  \n2.\tThe \\(\\ell_{2,1}\\) norm regularization is generally a non-convex problem. What techniques or methods are used in the paper to achieve the optimization objective?  \n3.\tFrom the evaluation results on different datasets, why does the same method exhibit significant differences in performance across different datasets? What are the underlying reasons for this?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "iqLutaI9TA", "reviewer": "Reviewer_DEHu", "summary": "In this paper, a novel K-Means clustering was proposed, named unified K-Means clustering with label-guided manifold learning, to solve the problems of traditional K-Means algorithm, such as the sensitivity of initial centroid selection, the limited recognition ability of intrinsic manifold structure of nonlinear data sets, and the difficulty of achieving balanced clustering in practical scenarios. The method does not need to calculate cluster centers and uses labels to guide the exploration of the nonlinear structure of the data. It realizes the cluster balance with L2,1-norm and achieves high clustering accuracy and robustness. Extensive experiments are performed, whose results prove the superiority of the proposed method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your recognition and valuable comments. Here are our responses:\n\n**1. Connection to manifold learning and its advantages**\n\n**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.\n\n**2. The significance of balanced clustering**\n\n**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.\n\n**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**\n\n**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})$.\n\n**4. How to choose the parameter $a$ for the low-pass filtering distance**\n\n**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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I reviewed the correctness of the proofs for the theoretical claims presented in the paper, specifically focusing on Theorem 3.1 and Theorem 4.1, and there is no problem.", "experimental_designs_or_analyses": "Yes, the authors selected 10 multi-view datasets and 6 comparison methods, using ACC, NMI and Purity as clustering measures. Data sets range from small data sets to large data sets with sample sizes of 10,000 and 30,000. The comparison method also includes the SOTA variants of K-Means. There is no obvious problem with the experimental designs or analyses.", "relation_to_broader_scientific_literature": "The paper's main contribution is the unified K-Means clustering with label-guided manifold learning and diverse distance metrics. It enhances robustness and achieves broader applications on nonlinear data, supported by comprehensive experiments that validate the method's effectiveness.", "essential_references_not_discussed": "The related works covered in this paper are relatively comprehensive, involving traditional k-means, fuzzy k-means, kernel k-means for handling nonlinear data, balanced clustering method RKM, and k-means with centered variants CDKM and k-sum and k-sum-x without centers, etc.", "other_strengths_and_weaknesses": "Strengths:  \n1. The authors proposed a novel K-Means clustering, named unified K-Means clustering with label-guided manifold learning, which addresses the weakness of K-means that is sensitive to the initialization of cluster centers and achieves a broader application on nonlinear data.\n2. The authors imposed a L2,1-norm constraint on the clustering indicator matrix, allowing the model to achieve class balance during clustering. Detailed logical reasoning and proof processes were provided to enhance readability.\n3. The authors also employed different distance matrices to enhance the model's generalization ability.\nWeaknesses:  \n1. The paper is on the basis of manifold learning but provides little discussion on how it is connected to manifold learning and its advantages.", "other_comments_or_suggestions": "1. What is the significance of balanced clustering? The authors should emphasize this issue in Introduction.  \n2. The authors should carefully check the paper. For example, in Equation (16), it seems matrix F is missing in some minimization operations.\n3. The unified framework is defined as min tr(GᵀDG), but the final model is min tr(FᵀDF) without the matrix P. The authors should provide a detailed explanation for this issue.", "questions_for_authors": "1.In Equation (14), matrix G is constructed from matrices F and P. Why is matrix P not present in the final expression? What is the relationship between matrix P and matrix F?\n2. How is the parameter a for the low-pass filtering distance chosen?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Nm8RUyRvtP", "reviewer": "Reviewer_YTpU", "summary": "This paper introduces a framework that integrates K-means clustering, Kernel K-means clustering, and Fuzzy K-means clustering with manifold learning. This framework aims to tackle the challenges of initial centroid sensitivity, handling nonlinear datasets, and achieving balanced clustering in traditional K-means clustering.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your recognition and valuable comments. We provide the following responses according to your questions:\n\n**1. Explain the formula (20) to (24)**\n\n**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.\n\n**2. Is label matrix F a discrete hard label or a continuous label**\n\n**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.\n\n**3. The difference of the proposed method from existing works addressing centroid initialization sensitivity and its advantages**\n\n**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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes. The experiments on benchmark datasets and toy datasets demonstrate the method's excellent clustering performance, its ability to handle nonlinear data, and its capacity for balanced clustering.", "theoretical_claims": "Yes, the paper presents several theoretical claims, and the theoretical claims in this paper are overall correct and supported by the corresponding proof.", "experimental_designs_or_analyses": "Yes. The experimental design of the work follows existing works, and the analyses are overall reasonable.", "relation_to_broader_scientific_literature": "The unified framework proposed by the authors addresses both the sensitivity of K-means to cluster centers and its inability to handle nonlinearity, as well as the issue of balanced clustering.", "essential_references_not_discussed": "In both the introduction and the comparison algorithms, the authors discussed essential relevant works.", "other_strengths_and_weaknesses": "This paper introduces a unified framework that addresses both the sensitivity of K-means to cluster centers and its inability to handle nonlinearity, and proposes a low-pass filtering distance metric. It achieves superior experimental results. The shortcomings can be found in the comments and questions.", "other_comments_or_suggestions": "There are some typos, such as the comparison algorithm K-sum-x being written as K-sum-X in Section 6.2.", "questions_for_authors": "1. Formulas (20) to (24) are not very logical; please restate them.\n2. Is the label matrix F a discrete hard label or a continuous label?\n3. The issue associated with K-means that is sensitive to centroid initialization is a well-recognized challenge, and has been studied by several works. What differentiates the proposed method from existing approaches, and what advantages does it offer?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper focuses on three issues in K-means clustering, sensitivity to initial centroid selection, limited ability to discern the intrinsic manifold structures, difficulty in achieving balanced clustering. To solve them, this paper utilizes a label matrix to generate a similarity matrix to align manifold structures with labels, and  integrates Gaussian kernel distance and K-nearest neighbor distance as well as low-pass filtering distance. Further, this paper designs a $\ell_{2,1}$ regularizer to improve the balanced clustering results. Experiments confirm the effectiveness of the proposed algorithm. 



After rebuttal, all reviews are positive about this manuscript and recognize its contributions. After reading the manuscript and responses, I agree with reviewers and recommend an acceptance for this manuscript.
Decision: Accept (poster)