Pith. sign in

REVIEW 8 minor 51 references

Modified K-means Algorithm with Local Optimality Guarantees

T0 review · 0 major / 8 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The K-means algorithm can converge to a clustering that is not locally optimal, and a minimal post-processing patch restores a finite-time local optimality guarantee.

desk verdict A correct, well-supported correction of a long-standing misconception about Lloyd's algorithm, with a simple and honest fix; the caveats are scope (min-index ties) and a couple of overstated novelty claims. read the letter →

arxiv 2506.06990 v2 pith:2TPC4TQZ submitted 2025-06-08 cs.LG math.OCstat.ML

Mingyi Li , Michael R. Metel , Akiko Takeda This is my paper
classification cs.LGmath.OCstat.ML MSC 90C2662H30
keywords K-meanslocaloptimalityBregmandivergencecounterexamplecontinuousrelaxationdiscretetie-breakingclusteringloss
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper attacks a belief that has accompanied K-means for decades: that when the algorithm stops, it has reached at least a locally optimal clustering. It exhibits a one-dimensional counterexample with five points and two clusters in which the algorithm terminates at centers $c_1=-2$, $c_2=2$ with the middle point tied, and yet every positive fraction of that point moved to the second cluster strictly decreases the clustering loss. The paper then proves that appending either of two small routines to K-means, one checking assignment ties and one scanning single-point reassignments, makes the algorithm terminate in finitely many iterations at a provable local optimum. The per-iteration time complexity remains $O(NK\Gamma_\phi(d))$ for a general Bregman divergence, so the guarantee comes without an asymptotic slowdown. If the claims hold, K-means users who rely on local optimality can verify and repair their solutions at negligible extra cost.

What carries the argument

The load-bearing object is the exact change-in-loss formula of Lemma 4.1. Here C-local means locally optimal in the continuous relaxation where assignments may be fractional, and D-local means optimal among the finitely many assignments that differ by moving one point. For a point $g$ moved from cluster $a$ to cluster $b$ by fraction $\alpha$, the formula expresses $\Delta_\alpha(g,a,b)$ as $\alpha w_g(D(x_g,(c^*_P)_b)-D(x_g,(c^*_P)_a))$ minus the center-shift terms $(s_a(P)-\alpha w_g)D((c^*_{P_{\mathrm{new}}})_a,(c^*_P)_a)$ and $(s_b(P)+\alpha w_g)D((c^*_{P_{\mathrm{new}}})_b,(c^*_P)_b)$. This reduces local optimality to a finite check: a solution is D-local exactly when $\Delta_1(g,a,b)\ge 0$ for every adjacent single-point move, and it is C-local when no partial move can lower the loss. Theorem 4.3 supplies the companion characterization: if the set $A(C^*_P)$ of optimal assignments for the current centers is not a singleton and all centers are distinct, then moving from $P$ to any adjacent point in $A(C^*_P)$ strictly decreases $F$. Function 1 (C-LO) uses this by detecting a tie and switching the tied point to the alternative cluster; Function 2 (D-LO) scans all $N(K-1)$ adjacent assignments and makes the first strictly improving move. Because these are single-point updates with precomputed cluster masses $s_k(P)$, the center updates cost $O(d)$ each and the overall per-iteration complexity stays $O(NK\Gamma_\phi(d))$.

What would settle it

Run the paper's five-point instance with minimum-index tie-breaking in any standard implementation: if the algorithm does not terminate at cluster centers $c_1=-2$, $c_2=2$ with $x_3=0$ assigned to cluster 1, or if the clustering loss computed after moving a positive fraction of $x_3$ to cluster 2 is not strictly smaller than the loss at that fixed point, then the counterexample fails.

Watch

Extended reading notes

Core claim

The central discovery is that the standard K-means algorithm, under the deterministic minimum-index tie-breaking convention, is not guaranteed to produce a local optimum. The counterexample uses five points on a line: $x=(-4,-2,0,1.5,2.5)$ with $K=2$ and squared Euclidean distance. Starting from centers $0$ and $2.5$, the algorithm converges to the assignment $P^*$ with clusters $\{-4,-2,0\}$ and $\{1.5,2.5\}$, centers $-2$ and $2$. At this assignment $x_3=0$ is exactly tied; the tie rule keeps it in the first cluster, so the algorithm stops. Yet for any $\alpha\in(0,1]$, moving a fraction $\alpha$ of $x_3$ to the second cluster changes the loss by $\frac{d}{d\alpha}f = -20\alpha(\alpha+12)/((\alpha-3)^2(\alpha+2)^2)<0$, so the loss strictly decreases along a feasible continuous path. Thus the fixed point is not CJ-local, not C-local, and not D-local. The paper's positive result is that a modified algorithm, LO-K-means, which appends a tie-resolution step (C-LO) or a single-point local improvement scan (D-LO) after the usual K-means iterations, converges in finite iterations to a C-local or D-local solution for the weighted K-means problem with any Bregman divergence, at the same per-iteration time and space complexity.

Load-bearing premise

The counterexample and the convergence analysis presuppose that whenever points are equally close to several cluster centers, K-means always assigns them to the smallest cluster index; if a library uses randomized or otherwise different tie-breaking, the specific bad fixed point and the proof that K-means can get stuck do not carry over verbatim.

Editorial extensions

If this is right

  • If the counterexample is right, the common statement that K-means converges to a local optimum is false under deterministic minimum-index tie-breaking; the algorithm's monotone decrease in the clustering loss is not enough to certify local optimality.
  • Appending Function 1 after convergence gives a cheap certificate of C-local optimality: if no tie is found, the solution is C-local; if a tie is found, the first move strictly decreases the loss.
  • Appending Function 2 (or Min-D-LO) guarantees D-local optimality in finitely many iterations, and since D-local implies C-local and CJ-local, this single check yields the strongest of the three local-optimality notions.
  • Because the per-iteration time complexity is unchanged, existing K-means implementations, including accelerated and seeded variants, can incorporate the modification without changing their asymptotic cost.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The counterexample is tied to minimum-index tie-breaking. Under randomized tie-breaking, the same five-point instance may leave the bad assignment with positive probability, so the practical frequency of non-local convergence in real libraries is a property of the library's tie rule, not of K-means as an abstract algorithm.
  • The change-in-loss formula suggests a natural diagnostic for any K-means run: compute $\Delta_1$ over all adjacent moves at the output; a negative value is immediately an improving reassignment. This could serve as a certificate of local optimality in production pipelines without changing the clustering result.
  • The same single-point-move analysis may be applicable to other partitional algorithms whose cluster representatives are weighted means under a Bregman divergence, such as Bregman k-medians or mixture-style updates, giving analogous local-optimality certificates.
  • One testable extension is to measure how often the D-LO improvement step fires on high-dimensional real datasets; the paper reports that C-local failures are rare there while D-local failures are common, which suggests that the discrete notion is the practically relevant one.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 8 minor

Summary. The paper studies the local optimality properties of Lloyd's K-means algorithm for the weighted K-means problem with Bregman divergences. It presents a five-point one-dimensional counterexample showing that, under min-index tie-breaking, K-means can converge to an assignment that is neither D-local, C-local, nor CJ-local. It then proposes LO-K-means, a modification that appends a corrective step (C-LO or D-LO/Min-D-LO) once K-means has converged, and proves that the modified algorithm converges in finitely many iterations to a C-local or D-local solution with the same per-iteration time complexity as K-means. The paper also reports experiments on synthetic and real datasets showing that the modifications reduce clustering loss at modest additional cost.

Significance. If the results are correct, the paper corrects a widespread misconception by providing a concrete, easily checkable counterexample to the claim that Lloyd's algorithm always converges to a locally optimal solution. The proposed LO-K-means variants are simple, drop-in compatible with existing K-means implementations, and come with finite-convergence guarantees under a general Bregman divergence, which is a useful extension beyond squared Euclidean distance. The theoretical proofs are detailed and, with minor exceptions, rigorous; the counterexample algebra is verified, and the numerical experiments support the main claims. The availability of code adds reproducibility value.

minor comments (8)
  1. [Appendix D.4 (proof of Theorem 4.4)] The sentence 'This solution is also C-local and CJ-local by??2.5??2.8' contains unresolved placeholder references that should be replaced with Propositions 2.5 and 2.8.
  2. [Throughout] The numbering is inconsistent: Definition 2.1 is cited as 'Theorem 2.1' in Appendix D.2, Proposition 2.2 is cited as 'Theorem 2.2' in the proof of Theorem 4.3 and in Lemma D.2's proof, and Lemma 4.1 is cited as 'Theorem 4.1' in Section 4.2 and in the proof of Theorem 4.3.
  3. [Section 3.1] The phrase 'for any ϵ>0 in Theorem 2.7' should refer to Definition 2.7, not a theorem.
  4. [Appendix D.3 (proof of Theorem 4.3)] The proof asserts that 'Since x_g ≠ (c*_P)_a, Theorem 2.2 implies that s_a(P)-αw_g > 0'; this is false when α=1 and x_g is the sole point in cluster a, in which case the factor s_a(P)-αw_g is zero and the corresponding Bregman term vanishes, so the strict decrease still holds but the argument should be restated to cover this boundary case.
  5. [Table 11] In the News20 dataset 2, K=25, D-LO row, the time entry '50,,235' appears to be a typo.
  6. [Section 5.2] The text equates the proportion of improved losses with the proportion of runs in which K-means did not converge to a C-local solution; making the reliance on Theorem 4.3 explicit in the figure caption would improve clarity.
  7. [Section 4.4] The statement that the empty-cluster correction has complexity O(K^2 d) = O(N K d) uses the standing assumption N > K; citing that assumption in the theorem statement would avoid confusion.
  8. [Section 3] The tie-breaking rule is stated as min-index following NumPy's argmin; the claim that the analysis extends to any deterministic rule is not proved, so consider adding a remark or proof for that extension, or qualifying the claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the counterexample, local-optimality conditions, and LO-K-means guarantees are derived by direct calculation and self-contained descent arguments, not by fitted inputs or self-citations.

full rationale

The paper's central claims are self-contained. The Section 3.1 counterexample is a direct calculation: K-means with minimum-index tie-breaking converges to P* with centers c1=-2 and c2=2, and the paper explicitly derives f(hat-P, hat-C) and its derivative d/d-alpha f = -20 alpha (alpha+12)/((alpha-3)^2 (alpha+2)^2) < 0 for 0<alpha<=1, showing a feasible continuous descent direction from the converged point. This is not a renaming of the output or a fitted parameter; it is an independent verification that the K-means fixed point fails the stated local-optimality definitions. The local-optimality definitions are taken from external prior work (Newby and Ali, 2015), and the implications among D-local, C-local, and CJ-local are proved in Section B rather than assumed. The algorithmic results are also derived from first principles: Lemma 4.1 computes the exact change in F under a single-point transfer using Bregman divergence properties; Theorem 4.3 establishes that a non-singleton A(C*) yields an adjacent strictly improving move; and Functions 1 and 2 implement exactly those moves. Theorem 4.4's finite termination follows from the finiteness of S1 and strict descent of F, not from any pre-certified output. The only scoping caveat is the explicit minimum-index tie-breaking rule, stated in Section 3 and used to construct the counterexample; this is an assumption about the analyzed algorithm, not a circular dependence of the results on their conclusions. The paper contains no self-citations by the authors, and no load-bearing step is justified solely by unpublished or same-author prior work. Numerical experiments are demonstrations used to support the practical relevance, not inputs to the proofs. The comparison with the authors' claimed novelty is external and does not provide the load-bearing support for any theorem. Overall, no prediction or derivation reduces by construction to its own inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper fits no free parameters to data; the clustering-loss improvements are empirical outputs, not inputs to the proofs. The theoretical results rely on standard convex-analysis facts (concavity of F, Wendell-Hurter), the Bregman optimal-center formula, and two stated assumptions: X subset of int dom(phi) and min-index tie-breaking. No new entities are introduced.

assumptions (5)
  • standard math F(P) = min_C f(P,C) is concave on the assignment polytope.
    Used in Proposition 2.5 and the proof of D-local implying C-local (Appendix B). It follows from F being the pointwise infimum of affine functions of P.
  • domain assumption All data points lie in int dom(phi), are unique, and N > K.
    Stated in Sections 2.1 and 2.2. The closed-form optimal center formula (4) and the empty-cluster handling (Proposition B.1) require points in the interior of the Bregman domain, distinct points, and more points than clusters.
  • ad hoc to paper Ties in the nearest-center assignment are broken by the minimum index, following NumPy's argmin convention.
    Section 3 and Algorithm 1, Step 2. The counterexample and the convergence analysis depend on this deterministic rule; the authors state the analysis extends to any deterministic rule, but randomized tie-breaking is not analyzed.
  • standard math Wendell and Hurter's Corollary 2, used to establish CJ-local optimality from partial optimality with a unique optimal assignment set.
    Invoked in the proof of Theorem 4.2 (Appendix D.3). The conditions of the corollary are verified in the proof.
  • standard math For a fixed cluster assignment with non-empty clusters, the unique optimal center is the weighted mean of the assigned points (Banerjee et al., 2005, Proposition 1).
    Proposition 2.2; foundational for the center update step and for Lemma 4.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Modified K-means Algorithm with Local Optimality Guarantees." pith.science (2026). https://pith.science/paper/2TPC4TQZ

@misc{pith2026250606990,
  author       = {Pith},
  title        = {Pith review of: Modified K-means Algorithm with Local Optimality Guarantees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2TPC4TQZ}},
  note         = {Machine review of arXiv:2506.06990}
}
read the original abstract

The K-means algorithm is one of the most widely studied clustering algorithms in machine learning. While extensive research has focused on its ability to achieve a globally optimal solution, there still lacks a rigorous analysis of its local optimality guarantees. In this paper, we first present conditions under which the K-means algorithm converges to a locally optimal solution. Based on this, we propose simple modifications to the K-means algorithm which ensure local optimality in both the continuous and discrete sense, with the same computational complexity as the original K-means algorithm. As the dissimilarity measure, we consider a general Bregman divergence, which is an extension of the squared Euclidean distance often used in the K-means algorithm. Numerical experiments confirm that the K-means algorithm does not always find a locally optimal solution in practice, while our proposed methods provide improved locally optimal solutions with reduced clustering loss. Our code is available at https://github.com/lmingyi/LO-K-means.

Figures

Figures reproduced from arXiv: 2506.06990 by the authors.

Figure 1
Figure 1. The proportion of cases where the clustering loss is improved over K-means by using C-LO across two different initialization methods and dimensions, with D equal to the squared Euclidean distance. These plots indicate the proportion of instances where K-means did not converge to a C-local solution. Each N, K cell represents the results from 1,000 runs of both algorithms. Darker colors indicate a higher frequency of … view at source ↗
Figure 2
Figure 2. The average improvement ratio of the clustering loss when C-LO improves over K-means across two different initialization methods and dimensions, with D equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of both algorithms. Darker colors indicate a higher percentage of clustering loss improvement. 5.3.2. RESULTS In real-world datasets, where features are real numbers, it is… view at source ↗
Figure 3
Figure 3. The clustering loss progression for four runs of D-LO, Min-D-LO, and their common K-means iterations on the News20 dataset with (N = 2, 000, d = 1, 089) with K = 10. The clustering losses are normalized such that the clustering loss achieved by the K-means algorithm upon convergence is set to 100%. the K-means algorithm used in scikit-learn. Our final experiments compared our methods with the D￾local algorithm propo… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: The average rate of increase in the number of iterations when C-LO improves over K-means across two different initialization methods and dimensions, with D equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of both algorithms…
Figure 5
Figure 5. Figure 5: The average number of times the new step was invoked when C-LO improved over K-means across two different initialization methods and dimensions, with D equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of all algorithms. Dar…
Figure 6
Figure 6. Figure 6: The proportion of cases where the clustering loss is improved over K-means by using D-LO across two different initialization methods and dimensions, with D equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of both algorithms…
Figure 7
Figure 7. Figure 7: The average improvement rate of the clustering loss when D-LO improves over K-means across two different initialization methods and dimensions, with D equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of both algorithms. The…
Figure 8
Figure 8. Figure 8: The average rate of increase in the number of iterations when D-LO improves over K-means across two different initialization methods and dimensions, with D equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of both algorithms…
Figure 9
Figure 9. Figure 9: The average number of times the new step was invoked when D-LO improves over K-means across two different initialization methods and dimensions, with D equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of all algorithms. Dar…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

51 extracted references · 48 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Ackermann, M. R. Algorithms for the Bregman k-Median Problem . PhD thesis, University of Paderborn, 2009

    work page 2009

  3. [3]

    NP-hardness of Euclidean sum-of-squares clustering

    Aloise, D., Deshpande, A., Hansen, P., and Popat, P. NP-hardness of Euclidean sum-of-squares clustering . Machine Learning, 75: 0 245--248, 2009

    work page 2009

  4. [4]

    and Vassilvitskii, S

    Arthur, D. and Vassilvitskii, S. k-means++: The Advantages of Careful Seeding . In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\ 1027--1035. SIAM, 2006

    work page 2006

  5. [5]

    F., Dick, T., and White, C

    Balcan, M.-F. F., Dick, T., and White, C. Data-Driven Clustering via Parameterized Lloyd's Families . In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018

    work page 2018

  6. [6]

    S., Ghosh, J., and Lafferty, J

    Banerjee, A., Merugu, S., Dhillon, I. S., Ghosh, J., and Lafferty, J. Clustering with Bregman divergences . Journal of Machine Learning Research , 6 0 (58): 0 1705--1749, 2005

    work page 2005

  7. [7]

    Toward Live Drum Separation Using Probabilistic Spectral Clustering Based on the Itakura-Saito Divergence

    Battenberg, E., Huang, V., and Wessel, D. Toward Live Drum Separation Using Probabilistic Spectral Clustering Based on the Itakura-Saito Divergence . In 45th Conference on Applications of Time-Frequency Processing in Audio. AES, 2012

    work page 2012

  8. [8]

    H., Bolte, J., and Teboulle, M

    Bauschke, H. H., Bolte, J., and Teboulle, M. A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications . Mathematics of Operations Research, 42 0 (2): 0 330--348, 2016

    work page 2016

Show all 51 references
  1. [9]

    S., Sherali, H

    Bazaraa, M. S., Sherali, H. D., and Shetty, C. M. Nonlinear Programming: Theory and Algorithms . John Wiley & Sons, 2006

    2006

  2. [10]

    Benson, H. P. Concave Minimization: Theory, Applications and Algorithms . In Handbook of Global Optimization , pp.\ 43--148. Springer, 1995

    1995

  3. [11]

    Berthold, M. R. and H \"o ppner, F. On Clustering Time Series Using Euclidean Distance and Pearson Correlation . arXiv preprint arXiv:1601.02213, 2016

    2016 arXiv

  4. [12]

    Application of learning analytics using clustering data Mining for Students’ disposition analysis

    Bharara, S., Sabitha, S., and Bansal, A. Application of learning analytics using clustering data Mining for Students’ disposition analysis . Education and Information Technologies, 23: 0 957--984, 2018

    2018

  5. [13]

    Bregman, L. M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming . USSR Computational Mathematics and Mathematical Physics , 7 0 (3): 0 200--217, 1967

    1967

  6. [14]

    O., Chiang, M

    Brown, P. O., Chiang, M. C., Guo, S., Jin, Y., Leung, C. K., Murray, E. L., Pazdor, A. G., and Cuzzocrea, A. Mahalanobis Distance Based K-Means Clustering . In Big Data Analytics and Knowledge Discovery, pp.\ 256--262. Springer, 2022

    2022

  7. [15]

    Cap \'o , M., P \'e rez, A., and Lozano, J. A. An efficient approximation to the K-means clustering for massive data . Knowledge-Based Systems, 117: 0 56--69, 2017

    2017

  8. [16]

    and Gionis, A

    Chawla, S. and Gionis, A. k -means -- : A unified approach to clustering and outlier detection . In Proceedings of the 2013 SIAM International Conference on Data Mining, pp.\ 189--197. SIAM, 2013

    2013

  9. [17]

    Modeling wine preferences by data mining from physicochemical properties

    Cortez, P., Cerdeira, A., Almeida, F., Matos, T., and Reis, J. Modeling wine preferences by data mining from physicochemical properties . Decision Support Systems, 47 0 (4): 0 547--553, 2009

    2009

  10. [18]

    Visual Categorization with Bags of Keypoints

    Csurka, G., Dance, C., Fan, L., Willamowski, J., and Bray, C. Visual Categorization with Bags of Keypoints . In Workshop on Statistical Learning in Computer Vision, ECCV, 2004

    2004

  11. [19]

    S., Mallela, S., and Kumar, R

    Dhillon, I. S., Mallela, S., and Kumar, R. A Divisive Information--Theoretic Feature Clustering Algorithm for Text Classification . Journal of Machine Learning Research, 3: 0 1265--1287, 2003

    2003

  12. [20]

    and Nielsen, F

    Dupin, N. and Nielsen, F. Partial K-Means with M Outliers: Mathematical Programs and Complexity Results . In International Conference on Optimization and Learning , pp.\ 287--303. Springer, 2023

    2023

  13. [21]

    Using the Triangle Inequality to Accelerate k-Means

    Elkan, C. Using the Triangle Inequality to Accelerate k-Means . In Proceedings of the 20th International Conference on Machine Learning, pp.\ 147--153, 2003

    2003

  14. [22]

    Fisher, R. A. The Use of Multiple Measurements in Taxonomic Problems . Annals of Eugenics, 7 0 (2): 0 179--188, 1936

    1936

  15. [23]

    G., Mathiasen, A., Nielsen, J

    Gr nlund, A., Larsen, K. G., Mathiasen, A., Nielsen, J. S., Schneider, S., and Song, M. Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D . arXiv preprint arXiv:1701.07204, 2017

    2017 arXiv

  16. [24]

    and Rozho n , V

    Grunau, C. and Rozho n , V. Adapting k-means Algorithms for Outliers . In Proceedings of the 39th International Conference on Machine Learning, pp.\ 7845--7886. PMLR, 2022

    2022

  17. [25]

    and Elkan, C

    Hamerly, G. and Elkan, C. Learning the k in k-means. In Advances in Neural Information Processing Systems, volume 16. MIT Press, 2003

    2003

  18. [26]

    Han, S., Mao, H., and Dally, W. J. Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding . In 4th International Conference on Learning Representations, 2016

    2016

  19. [27]

    and Saito, S

    Itakura, F. and Saito, S. Analysis synthesis telephony based on the maximum likelihood method . In 6th International Congress on Acoustics, 1968

    1968

  20. [28]

    Jain, A. K. Data clustering: 50 years beyond K-means . Pattern Recognition Letters, 31 0 (8): 0 651--666, 2010

    2010

  21. [29]

    M., Netanyahu, N

    Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., and Wu, A. Y. A local search approximation algorithm for k-means clustering. Computational Geometry, 28 0 (2): 0 89--112, 2004

    2004

  22. [30]

    Kim, S., Hooper, C. R. C., Gholami, A., Dong, Z., Li, X., Shen, S., Mahoney, M. W., and Keutzer, K. SqueezeLLM: Dense-and-Sparse Quantization . In Proceedings of the 41st International Conference on Machine Learning, pp.\ 23901--23923. PMLR, 2024

    2024

  23. [31]

    and Leibler, R

    Kullback, S. and Leibler, R. A. On Information and Sufficiency . The Annals of Mathematical Statistics, 22 0 (1): 0 79--86, 1951

    1951

  24. [32]

    An Algorithm for Vector Quantizer Design

    Linde, Y., Buzo, A., and Gray, R. An Algorithm for Vector Quantizer Design . IEEE Transactions on Communications, 28 0 (1): 0 84--95, 1980

    1980

  25. [33]

    and Shih, Y.-Y

    Liu, D.-R. and Shih, Y.-Y. Integrating AHP and data mining for product recommendation based on customer lifetime value . Information & Management, 42 0 (3): 0 387--400, 2005

    2005

  26. [34]

    Least squares quantization in PCM

    Lloyd, S. Least squares quantization in PCM . IEEE Transactions on Information Theory, 28 0 (2): 0 129--137, 1982

    1982

  27. [35]

    Martino, A., Ghiglietti, A., Ieva, F., and Paganoni, A. M. A k-means procedure based on a Mahalanobis type distance for clustering multivariate functional data . Statistical Methods & Applications, 28: 0 301--322, 2019

    2019

  28. [36]

    V., Tolledo, D., Machado, J., Baptista, L

    Martins, M. V., Tolledo, D., Machado, J., Baptista, L. M. T., and Realinho, V. Early Prediction of student’s Performance in Higher Education: A Case Study . Trends and Applications in Information Systems and Technologies, 1: 0 166--175, 2021

    2021

  29. [37]

    Student Engagement Level in e-Learning Environment: Clustering Using K-means

    Moubayed, A., Injadat, M., Shami, A., and Lutfiyya, H. Student Engagement Level in e-Learning Environment: Clustering Using K-means . American Journal of Distance Education, 34 0 (2): 0 137--156, 2020

    2020

  30. [38]

    and Kanehisa, M

    Nakai, K. and Kanehisa, M. Expert system for predicting protein localization sites in gram-negative bacteria . Proteins: Structure, Function, and Bioinformatics, 11 0 (2): 0 95--110, 1991

    1991

  31. [39]

    and Kanehisa, M

    Nakai, K. and Kanehisa, M. A knowledge base for predicting protein localization sites in eukaryotic cells . Genomics, 14 0 (4): 0 897--911, 1992

    1992

  32. [40]

    and Ali, M

    Newby, E. and Ali, M. M. A trust--region--based derivative free algorithm for mixed integer programming . Computational Optimization and Applications, 60: 0 199--229, 2015

    2015

  33. [41]

    numpy.argmin -- NumPy v2.2 Manual

    NumPy Developers . numpy.argmin -- NumPy v2.2 Manual . https://numpy.org/doc/stable/reference/generated/numpy.argmin.html, 2025. Accessed: 2025-01-27

    2025

  34. [42]

    and Moore, A

    Pelleg, D. and Moore, A. X-means: Extending K-means with Efficient Estimation of the Number of Clusters . In Proceedings of the 17th International Conference on Machine Learning, pp.\ 727--734, 2000

    2000

  35. [43]

    and Xia, Y

    Peng, J. and Xia, Y. A Cutting Algorithm for the Minimum Sum-of-Squared Error Clustering . In Proceedings of the 2005 SIAM International Conference on Data Mining , pp.\ 150--160. SIAM, 2005

    2005

  36. [44]

    Rockafellar, R. T. Convex Analysis . Princeton University Press, 1970

    1970

  37. [45]

    The 20 newsgroups text dataset

    scikit-learn developers. The 20 newsgroups text dataset. https://scikit-learn.org/0.19/datasets/twenty_newsgroups.html, 2017. Accessed: 2025-01-20

    2017

  38. [46]

    KMeans - scikit-learn documentation

    scikit-learn developers. KMeans - scikit-learn documentation . https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html, 2025. Accessed: 2025-01-13

    2025

  39. [47]

    Selim, S. Z. and Ismail, M. A. K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality . IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6 0 (1): 0 81--87, 1984

    1984

  40. [48]

    A Comparison of Document Clustering Techniques

    Steinbach, M., Karypis, G., and Kumar, V. A Comparison of Document Clustering Techniques . In KDD-2000 Workshop on Text Mining, 2000

    2000

  41. [49]

    Kullback - - Leibler Divergence-Based Fuzzy C-Means Clustering Incorporating Morphological Reconstruction and Wavelet Frames for Image Segmentation

    Wang, C., Pedrycz, W., Li, Z., and Zhou, M. Kullback - - Leibler Divergence-Based Fuzzy C-Means Clustering Incorporating Morphological Reconstruction and Wavelet Frames for Image Segmentation . IEEE Transactions on Cybernetics, 52 0 (8): 0 7612--7623, 2022

    2022

  42. [50]

    and Song, M

    Wang, H. and Song, M. Ckmeans.1d.dp: Optimal k -means Clustering in One Dimension by Dynamic Programming . The R Journal , 3 0 (2): 0 29--33, 2011

    2011

  43. [51]

    Wendell, R. E. and Hurter Jr, A. P. Minimization of a Non-Separable Objective Function Subject to Disjoint Constraints . Operations Research, 24 0 (4): 0 643--657, 1976

    1976

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.