A note on the $k$-means clustering for missing data
Authors: Yoshikazu Terada
Xin Guan
Venue: Accepted by TMLR ()

Abstract: The classical $k$-means clustering algorithm requires complete data and cannot be directly applied when observations contain missing entries. An intuitive and computationally efficient extension addresses this issue by minimizing the $k$-means loss over the observed entries only, a strategy considered in several studies. This method is known as $k$-POD clustering. In this paper, we provide a theoretical analysis of this approach and demonstrate that it is generally inconsistent, even under the missing completely at random (MCAR) assumption. Specifically, we show that the expected loss being minimized asymptotically differs from the original $k$-means objective, leading to biased estimates of cluster centers in the large-sample limit. This highlights a fundamental limitation: the method may fail to recover the true underlying cluster structure, even in settings where $k$-means performs well on fully observed data. Nevertheless, when the missing rate per variable is sufficiently low and the dimensionality is high, the method can still produce stable and practically useful results, making it a viable alternative when the complete-case analysis is ineffective.

Published in Transactions on Machine Learning Research (06/2025)
A note on the k-means clustering for missing data
Yoshikazu Terada
Graduate School of Engineering Science, The University of Osoka Center for Advanced Integrated Intelligence Research, RIKEN
Xin Guan
www..uinncc@thook... ac.jp
Graduate School of Information Sciences, Tohoku University
Reviewed OpenReview: https: openreview. net/ forum? id=peglTvePXS
Abstract
The classical k-means clustering algorithm requires complete data and camnot be directly applied when observations contain missing entries. An intuitive and computationally effi- cient extension addresses this issue by minimizing the k-means loss over the observed entries only, a strategy considered in several studies. This method is known as k-POD clustering. In this paper, we provide theoretical analysis of this approach and demonstrate that it is generally inconsistent, even under the missing completely at random (MCAR) assumption. Specifically, we show that the expected loss being minimized asymptotically differs from the original k-means objective, leading to biased estimates of cluster centers in the large-sample limit. This highlights a fundamental limitation: the mothod may fail to recover the truc underlying cluster structure, even settings where k-means performs well on fully observed data. Nevertheless, when the missing rate per variable is sufficiently low and the dimen- sionality is high, the method can still produce stable and practically useful results, making it viable alternative when the complete-case analysis is ineffective.
1 Introduction
The k-means clustering is one of the most well-known clustering algorithms, which provides partition minimizing the sum of within-cluster variances. When a given data matrix has missing entries, most clus- tering algorithms, including k-means clustering, cannot be applied, whereas missing data are common in various real data applications (c.g., Wagstaff & Laidler (2005)). Hore, we consider the k-means clustering for missing data. There are two common approaches for handling missing entries: complete-case analysis and imputation, both of which can be used as preprocessing steps prior to the clustering (Himmelspach & Conrad 2010). However, since we delete all data points with missing entries in complete-casc analysis, the number of complete cases could be too small in multivariate data. The imputation approach works well when the assumptions on hidden probabilistic model are correct, while it is often complicated and its computational cost is high QLee & Harel 2022). Another approach is to modify the Euclidean distance used in k-means clustering. For example, the partial distance that involves only the observed dimensions is a popular choice (Wagstaff) 2004 [ithio & Maitra 2018: Datta et al. 2018), the main problem is that the modificd mcasurements for distance may not reflect the true structure based on all dimensions and may not even be distance measure.
As natural extension of the k-means clustering for missing data, the k-POD clustering is proposed by Chi et al. (2016), which can be considered as a special case of the matrix completion issuc (o.g., see Jain et al. (2013)). For a data matrix X = (rig) the set of indexes Ω C (1,..., x (1....,p) indicates the observed entries. The projection P onto an index set Ω is introduced to replace the missing entries with zero. That is, [Pa(X)]i Mi if (i.j) E Q otherwisc. Further write a binary matrix U (ug)лxk for the cluster membership, where ug if ith observation belongs to ith cluster. The i cluster centers are denoted by matrix M (Mn))xpp the Ith row of which represents the Ith cluster center. Then, the loss

---

Published in Transactions on Machine Learning Research (06/2025)
function of the k-POD clustering is defined as
min U.M
PPa - U such that U E (0, 1 and
ua (i I,..., 1(),
where || (Ein at)) 1/2 denotes the Frobenius norm of a matrix A (ai))xxp- When Q {1.....n)) x PI, the above loss is equivalent to that of the k-means clustering. Therefore, the k- POD clustering ignores the missing entries in the k-means clustering. The simple and fast majorization- minimization algorithm can solve the optimization of the above loss. In each iteration of the MM algorithm, missing entries are imputed using the center of the cluster to which the corresponding observation belongs, followed by applying k- k-manns clustering to the imputed data. In this sense, k-POD clustering can be regarded as a natural extension of the k-means clustering for missing data. This loss function also considered in Lithio Maitra (2018), and they develop a more efficient algorithm. The k-POD clustering stably performs even under a large proportion of missingness. The numerical experiments in Chi et al. (2016) show that the k-POD clustering works well under various cases. As mentioned in Chi et al. (2016). should note that
the k-POD clustering has the common limitations as the k-means clustcring. It still seems to work well in those settings where the k-means clustering works.
Interestingly, Wang et al. 2019 independently proposes the following k-means clustering for missing data:
min Y - UM such that Y E R PY = Px)(), U E (0,
Y Y,U.M
h ua = for all i 1....,n. n.
and Σ
This mothod is identical to the k-POD clustoring since the optimal solution of this problem should satisfy Pae (Y) = (U where f2 is the complement of Ω
In this paper, unfortunately, will show that the k-POD clustering provides essentially different partition of the data space with the k-means clustering even under the simplest missing mechanism called the missing completely at random (MCAR). More preciscly, the estimated partition obtained by k-POD clustering may converge to a limit different from that of k-means clustering in the large-sample regime. This implies that k-POD clustering can fail to recover the true underlying cluster structure, even in settings where k-means clustering works well. By contrast, under the MCAR mechanism, the k-means clustering with complete cases (i.e., complete-case analysis) shares the same asymptotic limit as that of k-means clustering.
To explain this problem, we demonstrate an illustrative example in Figure Grey data points are generated from two-dimensional Gaussian uixture distribution (n = 104), and the ith row (sa,, 2322) is randomly observed with probabilities (2).9)) = (1/3, 2/33), where g (j = 1,2) is the probability of the jth dimension being observed. Here, the number of complete cases is approximately 2200. The green dotted line is the cluster boundary of the k-mean clustering with complete cases and almost the same as the cluster boundary of k-means with all grey data points. However, the cluster boundary of the k-POD clustering (blue dashed line) is completely different from these boundaries. The essential reason for the distortion result of the k-OOD clustering lies in the difference between the expected losses of the k-means and k-POD clusterings. As shown later, the expected loss function of the k-POD clustering can be written as the weighted sum of the expected losses of the k-means clustering using parts of variables.
2 Inconsistency of k-POD clustering
In this paper, we adopt the notation conventions recommended by TMLR. Specifically, non-random (deter- ministic) scalars are denoted by italic letters (e.g., rý), and non-random vectors by bold italic letters (e.g.. r). Random quantities are distinguished by upright fonts (e.g., Σy. r). Let X, be a p-dimensional independent sample from a population distribution P. Write = (xx))xp- Here, we simply consider the missing completely at random mechanism. Let rij- = 1 xay observed and rty = 0 if x, is missing. The re- sponse indicator vectors r (ra....., rip) (i 1, 1,...,), n) are independently distributed from multinomial
2

---

min x; mIl min 1 n | UM Published in Transactions on Machine Learning Research (06/2025)
Figure 1: An illustrative example showing that the k-POD clustering fails. (solid and circle: k-means clustering with all data points, dotted and square: k-means clustering with complete cases, triangle and dashed: k-OOD clustering with missing data).
distribution over the 2" possible missingness patterns and are completely independent with X. We assume that P(r1 = 1p) where 1p = ()) E IRP
Let be the number of clusters. For given cluster centers M (H1,.... (R)) R the empirical loss of the k-means clustering is
((KM) (M)
(M)
n
where μr is the Ith row of M. Using similar calculation, the empirical loss of the k-POD clustering be written as
T(KPOD) (M)
(x - mm5)
n
n
Let MKM = arg minm Z(KM) (M) be the estimator of the k-means clustering. Pollard 1981 shows that, as the sample size goes to infinily, the estimator Męм converges to the minimizer of the expected loss of the k-means clustering, that is,
(KM) (M)
min
x1
11ll3
ISiSk
Similarly, we can define the expected loss of the k-POD clustering
L (KPOD) (M)
min
riy (X15 pmy)²
ISISk
As the first result, we show that the expected loss the &-POD clustering can be represented as the weighted sum of all possible expected k-means losses with parts of variables.
Proposition 2.1. Let rı = TTp Under the above assumptions,
(KPOD) (M) (
Σ
P(r = rr] (M r))
rEfo.132
where = (ri....,ry) Tp) E (0, and (K r) is the expected loss of the k-meons clustering using dimensions with ry 1:
L (KM) (M =E
min
[x1 m1s)
1=1
3

---

Published in Transactions on Machine Learning Research (06/2025)
2.5
7.0
1.5
1.0
0.5
0.0
-0.5
0.D
0.5
1.0
1.5
2.0
2.5
An illustrative example show why (KPOD) and (KM)) yield different optimal solutions. (red points: the optimal solution of the k-means clustering, blue points: the empirical solution of the k-POD clustering with data points).
Figure 2:
Proof. From the basic property of the conditional expectation, we immediately obtain
1 [(KPOD)(M) = Er,
Ex, ln
(ı5(1 - m1j) rı min Isisk
Σ
P(r = (KM) |r),
rE(0.1)
which completes the proof.
Now, we will show the inconsistency of the k-POD clustering from the viewpoint of k-means clustering, Write MKrOD arg migmi (KKPOD) (M) for estimator of cluster center matrix by the k-POD clustering. Write MKPOD for the set of optimal cluster center matrices of the expected loss (KPOD) (i.e., MKPOD arg minM L (KPOOD) (M)). We note that (KPOD) might have multiple optimal solutions even when (KM) has the unique optimal solution up to relabelling. For example, according to the following theorem, we can assume that the triangular points are close enough to a pair of optimal centers for L (KPOD) Figure [ In this case, as this Gaussian mixture symmetric about the y-axis, the pair of points symmetric to the triangular points across the y-axis is also near optimal.
The following thcorem shows the convergence of the k-POD clustcring in the large sample limit. The proof is given in the supplementary material.
Theorem 2.2. Assume that ||x||| is bounded almost surely. Then we have, as n goes to infinily,
L (KPOD) (MкPоо) + min L (KPOD) (M) and Makkpon,MMkpon + a.s.,
M
where d Mi = miin JM- - -M
In general, since L (KPOD) and ((KM) have different optimal solutions, MKPOD does not converge to an optimal solution of the expected k-means loss L (KM), Therefore, the estimated partition of the data space by the k-POD clustcring is generally different from that by the k-mcans clustering.
Example 2.1. Here, we present tuooddmmesioonal toy erample to illustrate why ((POD)) and [(KM) may yield different optimal solutions. We consider population distribution that is uniform over the union of two rectangles: [0.0, 2.0) x [0.0, 1.0] (0.0, 2.0] x [1.5, 2.0], with the number of clusters set to two. In this case, the optimal solution for [(KM) corresponds to pl
(KM) (1.0, 0.5)T and μ1z (KM) (1.0, 2.0)T, shown as red points We assume that each entry is independently missing with probability 50%. Under this selling, the BODO objective be expressed
in Figure ?
L (KPOD) (M)
1 { (KM) (K(M)((M) (M (0,1)T) - (KMM)(M (1,0) + (KM) (M (
4
4

---

Published in Transactions on Machine Learning Research (06/2025)
(), the optimal solutions lie along the dotted line in Figure & For ((KM) (M (1, only the irvelevant variable is observed, and the resulling optimal solutions lie along the dot-dashed line in Figure entirely unrelated to the underlying cluster structure. The loss (KMM) (M (1,1)T) is identical to the k-means loss L(KM), If (IMM(( (1,1)T) were excluded from the above equation, the optimal centers should be located al the inlersection of the dolled and dol-dashed lines. Due to the influence of the irvelevant component I [((MM) | (1,0)T), the k-POD solution drawm away from the true cluster centers and instead lies at an intermediate position between the k-means solution and the intersection points. In fact, the blue points in Figure & show the empirical solution of k-POD clustering with 10*, which clearly demonstrates this undesirable phenomenon.
For L ((KM)
For high-dimensional data, even if the missing rate of each variable is low, the number of complete cases could be very small. In such cases, the k-POD clustering provides much better results than the complete-case analysis. Thus, for high-dimensional data with few missing components, the k-POD clustering could be a suitable choice.
3 Simulations
In this scction, we illustrate some numerical simulations to verify the inconsistency of k-POD. We consider the seitings in which k-means itself can perform well. The Gaussian mixture model x ~ Σi= NP 2)) is used to generate the original data, where N (uf, x7) is the p-dimensional Gaussian distribution with mean pf and covariance Mj, and कy is the mixture weight of the (th component. The missing completely at random mechanism is considered in this section. We generate the original complete data matrix X (xx)) )ax from the above mixture model and the indicator matrix R = (Fi))axp from the Bernoulli distribution, that is, Eij...., :Tn is an independent sample from the Bernoulli distribution with the probability of success qj E (0, 1]. Then the incomplete data matrix is generated by X and R, that is, Xij is observed if ri = 1 and X;j is missing if rzy = O. To measure the bias of the estimator of a cluster center matrix by the k-POD clustering MKPOD, we take the mean square error between MKPOD and MEM to be the criterion, which is given by
MSE(MKPOD. MRM) Σ min |KPODD - MkM,
where PKrOD, and P.M. are the ith rows of MKPOD and MRM: respectively, and the minimization with respect to I' is to eliminate the influence of index permutation. Since MMM is the minimizer of the expected loss of the k-means clustering, it is unknown. We here substitute it by the estimator of the k-means clustering with the sample size n = 10". Since the loss function of the k-POD) clustering is highly non-convex, as with the original k-mcans clustering, we use multiple random initializations and select the solution with the lowest loss value. More precisely, to initialize the cluster centers in the presence of missing values, we proceed as follows. We first compute the column-wist means of the observed entries and use these to impute the missing values in the data, matrix. Each missing entry is replaced with the corrosponding column mean. We then randomly select l data points from the imputed data to serve the initial cluster centers. If any of the selected points are duplicated (i.e., some centers are identical due to imputation), we add small random noise to each entry of the initial centers to ensure diversity and numerical stability. To mitigate the effect of local minima, we perform 1000 random initializations and retain the solution with the lowest loss. Here, we should note that Chi et al. (001)) provides the R package kpodclustr including the implementation of the k-PO clustcring with a single specific initialization, which often provides poor local minima with higher loss values.
We first examine the inconsistency of the k-POD clustering by analyzing the trend of the MSE as the sample size n increases, under the sctting described in Figure 1 For comparison, we also include the results of k-means clustering applied to the complete cases, as well as those of k-means clustering applied to the fully observed (original) data. Figure g shows that the MSE of k-means with complete cases (dotted line) gradually approaches that of k-mcans with all original data (solid line) as n increases. In contrast, the MSE of k-D clustering (dashed line) also converges as n increases, but not to zero. The significant gap between the dashed and solid lines, therefore, indicates the inconsistency of the k clustering.
5

---

Published in Transactions on Machine Learning Research (06/2025)
20
1.5
MSE
1.0
05
0.
1000
2000
3000
4000
5000
Figure 3:
The MSEs of the estimated cluster centers (dashed line: the k-POD clustering, solid line: the k-means clustering, dotted line: the k-mcans clustcring with complete cases).
We further compare the bias of the k-POD clustering in estimating cluster centers using several synthetic datasets with n = 10 The synthetic data are generaled from a Gaussian mixture model (13) I,) and then scaled that each variable has unit sample variance. Missing values are then introduced completely random (MCAR), with equal probabilities across all variables, based on the fully observed synthetic datasets. We consider the following three settings for the dimensionality and cluster structure of the Gaussian mixture model:
(1) Two-dimensional setting (p = 2): The component means are set as μi = (0,0) 12 = (3, (3,0),, and #3 (1.5, v6.75)
(2) Five-dimensional setting (p= 5): The first two dimensions of the component means are the same as in Setting (1), with the remaining dimensions set to zero.
(3) Filly-dimensional setting (p = -0): Same as Setting (2), except for the number of dimensions.
The missing rate for each variable, denoted by g, set uniformly across variables and takes values in (10%, 30%, 50%). All reported values are the means and standard deviations of the MSEs over 100 rep- etitions. Note that for Setting (3), when the missing rate exceeds 10%, complete-case analysis cannot be performed due to the lack of fully observed samples.
Table 1 summariizes the mean squared errors (MSEs) of different methods across multiple synthetic datasets: Oracle (i.e., k-means clustering applied to the synthetic data prior to missing value generation), Complete- case (i.c., k-moans clustering applied to complete cases only), and k-POD (i.c., k-POD clustering applicd to incomplete data). It can be observed that, for most datasets, the MSE of the k-POD clustering is generally larger than that of the other methods, indicating a substantial bias in the estimated cluster centers when using k-POD clustering. In high-dimensional settings, even when the missing rate for each variable is low, the number of complete cases may be too small, rendering complete-case analysis less effective. As shown in the last row of Table 1 k-POD clustering performs well, whereas complete-case analysis fails due to the insufficient number of fully observed samples. Therefore, in such scenarios, k-POD clustering tends to be more stable and may be more suitable for practical applications.
To further illustrate the behavior of k-POD clustering, we consider a well-separated case which the dis- tances between cluster centers are set to before scaling in Sctting (3). Figure 4 presents the estimated cluster centers obtained using k-means clustering complete data. When the missing rate is g 10%, the centers estimated by k-POD clustering are nearly identical to those obtained by k-means clustering with the original data. However, when the missing rate increases to 30% the estimated centers by k-POD clustering deviate significantly. Since the k-POD loss corresponds to a weighted sum of k-means losses over all possible subsets of observed variables, the influence of irrelevant features becomes more pronounced as their number increases.
the complete data and k-POD clustering on the in-
Finally, we present a real data example using the Wine dataset from the UCI Machine Learning Repository hhttp://archive ics uci edu/ml). This dataset contains the results of chemical analysis of wine samples

---

Published in Transactions on Machine Learning Research (06/2025)
Table 1: Mean squared error (MSE) comparison across different methods. Standard deviations are reported
in parentheses.
Setting
p
Miss. rate
Oracle
Complete
k-POD
(1)
2
10%
0.001 (0.001)
0.002 (0.001)
0.011 (0.003)
1
2
30%
0.003 (0.002)
0.072 (0.011)
(1)
2
50%
0.004 (0.003)
0.181 (0.023)
(2)
5
10%
0.012 (0.007)
0.020 (0.014)
0.161 (0.046)
(2
5
30%
0.070 (0.036)
1.617 (0.446)
22
5
50%
0.996 (1.232)
3.237 (0.661)
50
10%
0.186 (0.035)
21.279 (3.012)
0.782 (1.191)
50
30%
NA
7.584 (0.677)
50
50%
NA
8.662 (0.836)
6-
Estimated centers (q= 10%)
(b) First two dimensions (0=10%)
d
(c) Estimated centers (q 30%) (d) First two dimensions (q 30%)
Figure 4: Estimated centers (circle: k-means with the original data, triangle: k-POD with missing data). In
(a) and (c), the horizontal axis represents the dimension index, while the vertical axis indicates the center value each dimension.
produced in the same region of Italy. Although all wines were cultivated under similar environmental conditions, they originate from three different grape cultivars. In analysis, treat these three cultivars as the ground-truth cluster structure. The dataset consists of 178 wine samples, each represented by 13 chemical features. In the following, we use data standardized to have zero mean and unit variance for each variable.
We randomly select 50 samples a validation set and use the remaining 128 samples for training. It is important that the training procedure unsupervised and does not make use of the true cluster labels. To evaluate performance under missing data scenarios, randomly introduce missingness into
7

---

Published in Transactions on Machine Learning Research (06/2025)
Table 2: Average misclassification rates (standard deviations in parentheses) on the Wine dataset. Setting (a): original features only. Setting (b): with 50 additional irrelevant features.
Setting Miss. rate
Training Error
Validation Error
0%
0.036 (0.012)
0.036 (0.021)
(a)
10%
0.049 (0.017)
0.040 (0.023)
30%
0.093 (0.024)
0.044 (0.026)
0%
0.068 (0.022)
0.070 (0.030)
(b)
10%
0.085 (0.028)
0.079 (0.034)
30%
0.195 (0.061)
0.133 (0.067)
the training data at fixed rates (10% and 30%). We then apply the k-POD clustering algorithm to the incomplete training data and compute the misclassification rates on both the training and validation sets. This procedure is repeated 100 times.
To assess performance in high- digh-dimensional settings with irrelevant features, we additionally generate inde- pendent 50 noise variables from standard normal distribution and append them to the original dataset. We then repeal the same procedure and compare the resulting accuracies. The average misclassification rates are summarized in Table 2 For reference, we also report the clustering performance the classical k-means algorithm applied to the original dataset, without any artificially introduced missing values (i.e., the 0% missingness cases in Table [). As shown in Table / the results exhibit a similar pattern to those observed in the previous simulation study. These findings suggest. that k-POD clustering may be unreliable when the missing rate is high, and should, therefore, be applied with caution in such scenarios.
4 Conclusions
In this paper, we have examined the theoretical properties of the k-means clustering in the presence of missing data, with particular emphasis the k-POD method, natural and widely used extension of the classical k-means algorithm for missing data. We have shown that the &-POD clustering is theoretically inconsistent, even under the most favorable assumption that the data are missing completely at random. More preciscly, as the sample size tonds to infinity, the k-POD estimator does not converge to the optimal solution of the original k-means objective but rather to the minimizer of weighted sum of k-means losses computed over subsets of variables defined by the missingness patterns.
This theoretical insight reveals fundamental limitation of the k-POD approach: it may fail to recover the underlying cluster structure, even when the classical k-means clustering performs well on fully observed data. Nonetheless, the k-POD clustering remains effective, specifically when the missing rate in each variable is sufficiently low and the data are high-dimensional.
These findings highlight the necessity of rigorous understanding of the theoretical behavior of cluster- ing algorithms in the presence of missing data. We emphasize the importance of exercising cantion when applying k-means-lype methods to incomplete datasets, even when their formulations appear intuitive computationally appealing.
Morcover, beyond the immediate implications for practitioners using k-POD clustering, our findings also highlight fundamental challenges in exlending k-means-type algorithms to settings with missing data. For highly incomplete data or incomplete data with a complex missing mechanism, we strongly recommend using modcl-basod clustering methods (c.g., Gaussian mixture models) within a likelihood-basee framework (Little & Rubin 2002). The demonstrated inconsistency of k-POD may guide the development and analysis of future clustering methods under incomplete data scenarios.
8

---

Published in Transactions on Machine Learning Research (06/2025)
Acknowledgments
This rescarch was supported by JSPS, Japan KAKENHI Grant (JP20K19756, JP20H00601, and JP24K14855 to YT), the MEXT Project for Seismologg Toward Research Innovation with Data of Earthquakes (STAR-E, JPJ010217 to YT), and China Scholarship Council (NO. 202108050077 XG). The authors wish express our thanks to Ms. Jiayu Li for her helpful discussions.
References
Jocelyn T. Chi, Eric C. Chi, and Richard G. Baraniuk. k-pod: method for k-means clustering of missing data. The American Statistician, 70(1):91-99) 99, 2016.
Shounak Datta, Supritam Bhattacharjee, and Swagatam Das. Clustering with missing features: a penalized dissimilarity measure based approach. Machine Learning, 107:1987 2025, 2018.
Ludmila Himmelspach and Stefan Conrad. Clustering approaches for data with missing values: Comparison and evaluation. In The Fifth International Conference on Digital Information Management (ICDIM), pp. 19-28. IEEE, 2010.
Prateck Jain, Pranceth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fisth annual ACM symposium on Theory of compuling, pp- 665-674, 2013.
Jung W. Lee and Ofer Harel. Incomplete clustering analysis via multiple imputation. Journal of Applied Statistics, pp. 1 18, 2022.
Andrew Lithio and Ranjan Maitra. An efficient k-mcans-type algorithm for clustering datasets with in- complete records. Stalisticol Analysis and Dala Mining: The ASA Dala Science Journal, 11(6):296 311, 2018.
Roderick J.A. Little and Donald B. Rubin. Statistical analysis with missing data, Second Edition. John Wiley Sons, 2002.
David Pollard. Strong consistency of k-means clustering. The Annals of Statistics, 9:135-140, 1981.
Adrianus W. van der Vaart. Asymptotic statistics. Cambridge university press, 2000.
Kiri L. Wagstaff. Clustering with missing values: No imputation required. In Classification, Clustering, and Data Mining Applications: Proccedings of the Meeting of the International Federation of Classification Societies (IFCS), Illinois Institute of Technology, Chicago, 15-18 July 2004, pp. $49-658. Springer, 2004.
Kiri L. Wagstaff and Victoria G. Laidler. Making the most of missing values: Object clustering with partial data astronomy. In Astronomical data analysis software and systems XIV, volume 347, pp. 172, 2005.
Siwei Wang, Miaomiao Li, Ning Hu, En Zhu, Jingtao Hu, Xinwang Liu, and Jianping Yin. k-means clustering with incomplete data. IEEE Access, 7:69162-6911 2019.
A Proof of Theorem 1
The proof is similar to the proofs for the consistency of the classical k-mcans. For simplicity of notation, omit the superscript (KPOD) from ((PPOD)) (M) and T,(KPOD) through the appendix. Let C> 0 be a positive constant such that ||x||| C almost surely. Let B(C') == (x IR ||ж||| S C'} be the closed ball, By the k-POD algorithm, can ensure that the estimated centers of the k-POD clustering are in B(C). Define (C)C) {M E R μ E B(C), 1= 1...., for C' 0.
We write M, E arg migminee..CC i. for an estimator of cluster center matrix by the k-POD clustering, and write M for the set of optimal cluster center matrices of the expected loss L (i.e.
9

---

Published in Transactions on Machine Learning Research (06/2025)
M argmin L(M)). Any element of M is denoted by M We note that M is not neces- sarily unique.
Since (CC) is compact, (C) is also compact under the topology induced by the Hausdorff metric. The following lemma gives the uniform strong law of large numbers and the continuity of the expected loss on such compact set (C)
Lemma A.1. Under the assumption in Theorem 1, the followings hold for C > 0:
(a) The uniform law of large numbers holds:
lim n- (C)
sup
[M) LLM) 0.8., and
(b) The loss function ((M) is continuous on & (C).
Now, we ready to prove Theorem
Proof of Theorem 1. The first result is the immediate consequence from (a) of Lemma A.1 Thus, we will show the second result. By the optimality of M,, we have
M-EM" lup T.n (M,)
inf L. 50 a.s.
By the strong law of large numbers,
MM E M"; lim sup inf M.E (M S lim sup (M²' su
L(M") a.s.
Thus, we obtain
> lim sup Em (Mn) lim sup inf M-EM
(MM) 2 lim E, (M,) L(M") a.s.
By the contimuity of the expected loss L, we have
Vg 0;
min MEL,,s(C)
L(M) min L(M), MEEI(C)
where (C) = {M E Ex(C) d(M, 2 8). Thus, from (a) Lemma A.1 the above inequality leads that for any
inf inf (C)),s(C)
(M 2
inf L(M) > L(M") 2 lim simsup L. (M.) a.s. McEL,s(C)
This gives that there exists no N almost surely such that
Vn no: (C)
i.( > (M,)) inf
If d(M,, M-) 2 8 for some n 2 no. have inf meL, Ln (M)) Ln (M,), which is impossible. Therefore, conclude that lim d(M,, M³) = 0 a.s.
B Proofs of Lemma 1
Here, we provide the proof of Lemma A.1
10

---

Published in Transactions on Machine Learning Research (06/2025)
Proof of Lemma A.1 For any M (Mi,.... p ( R define the function gMa(;;)) Ro x {0, - R
to be gM (2. r) = minggik | ii ol Let g = ( M E Ex(C)).
sup MM
9M r.,, -E (x +0 a.s.
n
From Theorem 19.4 in van der Vaart (2000), it suffices to show that for each 0 there exists fi- nite class Ge such that for each 9M 9, there are functions IM IM E Ge with 9M S S 9M and E [xMM(x), ri) (x1, <.
For > O, let Dg be a finite subset of B(C) such that
Vμ E B(C); Ev E Ds; ||I ml < 6.
Define DR,s = {M E Ec(C) u E Ds, == I....,k).. kj. For each d > O, we give the finite class Ge of the form:
(1 worl VE VED
Go
min Islck
For fixed M Es(C), take V (A) E R such that Dj and || - vill < 8 for any 1=1,-. -....,,k k. Then lor gM E G, we give the corresponding upper and lower bounds in Gs to be
(x) min (1 - us vrrl - 6)² and (x, = min ISISk
-
or
isisk
We first show that 9M- 9M < GM. Since ÿM and āM are determined by V that satisfies || mill < 6, we have for any = 1....,K k and (I,r) E R' x 13",
8 8 oor -or- porlls w - is o orrll +
It follows that gm- S AM S JM. A simple computation gives
E. [[ r1) (
=E p(r / ( (M( r)) dP(x)
rE(0,1)
P(r: P(r== =r) //6 (1zor- + +0)² 2000)=(()) (lrl-- ")² dP(x)
< Σ
rE(U,1}p
Σ P(ri r) Σ ||zor- |lo0r 48k ( (IleliP(a)+C))
45
rE(U,1}
This yields E (( - (xi, <e.
Next, we prove the continuity of L(M) on Ex(C). If M, V e Ed(C) are chosen to safisfy max miny | mill < 5,
vE (1,...,k); (0))) (1,..., k): || well < 8.
11

---

Published in Transactions on Machine Learning Research (06/2025)
Moreover, we have
((M) - L(V)
E P(r =r) /
min 2 - pv o orl
min 1sisk
-oor morl? dP(x)
ISPSk
rE(0,13
<
Σ
P(ri =r) /
max 1sisk
(1 (r(()) or| - o dp(x)
rE(0,1}
ISISA P(r: = r) /
Σ
max ((1zor- - + +8)² --rl dp(x)
rE(0,1)
s 28
Σ
P(r (r)= /
max 1elsk
( dp(x) + + - 4C8+0
(E(0.1)2
Similarly, we obtain L(V) L(M) < <405 + 52, which completes the proof.
12


Reviews:
[{"review_id": "6Jnc84TDAp", "reviewer": "Reviewer_5Abs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I enjoyed the paper and think it's a nice insight to an important and widely used algorithm. The one thing that is missing imo is a comparison to an EM type strategy for missing data, which seems like the most natural solution to me. EM for the Gaussian mixture model can easily be extended to impute missing values, and the same could be done for k-means by adding a step in each iteration that sets missing values to the centroid value for the cluster the data point is in. It is not obvious to me whether this could be analyzed theoretically (I suspect not), but it would be a valuable addition to the numerical experiments. \n\nMinor comment: don't use \"On the other hand\" with \"on the one hand\" first.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider K means clustering with missing values. The previously propsed k-POD calculates distances ignoring missing elements. The main result of the paper is that k-POD does not recover the \"true\" k-means centroids in the large sample limit. This result is actually relatively straightforward to derive and is backed up by various nice simulated and \"real\" data results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Numerical comparison to imputation in each iteration of k means.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Nsx0qJZ6Zt", "reviewer": "Reviewer_599s", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is clear, concise and well presented. The results are not at all surprising, but are nonetheless instructive and worthwhile additions to the literature.\n\n- The experimental set-up is (for the most part) appropriate to demonstrate the main points made by the paper.\n\nWeaknesses:\n\n- The \"real data\" example doesn't seem to add much, if anything, to the paper. Since there is no methodological contribution being made the simulation experiments do a far better job showing what the authors are presenting.\n\n- Whenever dealing with kmeans clustering problems it is hard to tell if any of the experimental results are just arising because the problems are NP hard. Although I appreciate the authors have explained their approach, they also mention that the implementation of kpod in the R package often leads to poor local minima. It seems more could potentially be done to mitigate the potential that the results arise at least partly due to poor solutions obtained and not poor globally optimal solutions (see below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper shows that the intuitively pleasing k-POD clustering model for k-means like clustering in the context of missingness is inconsistent for the k-means problem even in the MCAR missingness regime. Some experiments are given to illustrate the potential practical implications of this biasedness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As mentioned, I think the paper does a pretty good job as-is in showing what it sets out to. My only request is that the authors attempt to better eliminate the potential for experimental results being too heavily influenced by algorithmic issues and not theoretical ones. A potential for this would be to initialise kPOD with the \"oracle\" solution for the kmeans. Accepting this is obviously not a possibility in practice, the experiments are trying to illustrate the implications of a theoretical truth, and so I don't think this is a big issue. If kPOD takes a good kmeans solution at initialisation, and turns it into a poor one, this is also strong evidence to show the potential issues with kPOD. I would also suggest the removal of the \"real data\" example, although I do not feel strongly about this point and so do not \"request\" it, per se.", "broader_impact_concerns": "None apparent", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ovwvuE12z8", "reviewer": "Reviewer_UsuP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- It is an interesting observation that k-POD might not be consistent and the theory seems sound. \n\nWeaknesses\n- In my opinion there is one missing piece about why the bias in general does not vanish. It is possible it is in literature but I missed it.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors showed that the solution a widely adapted k-means extension to handling missing data concentrates on its population minimal, which in general might not be the same as the original k-means clustering with full data access, even under missing completely at random setup.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major comment \n- The authors mentioned after Theorem 2.2 that the optimal solution of $L^{KPOD}$ and $L^{KM}$ are in general different. This needs elaboration (e.g., some intuition on why it is not the same, a citation saying they are under some general condition not the same) or put as an assumption when stating inconsistency e.g., in conclusion. As I understood Thm. 2.2 showed that the k-POD estimator concentrates, so bias is the only way to get inconsistency. I agree with the authors that there is no particular reason that they should be the same but if it is not shown anywhere else the authors should at least provide some evidence this is indeed the case. And I think finite sample simulation is not enough for this purpose since it does not exclude the possibility that the bias vanishes in a very slow rate. \n\nMinor comment\n- Please consider keeping track of conditioning in the notations used in and around Prop. 2.1 (e.g. $\\mathbb{E}[\\dots|\\mathbf{r}]$ if you are conditioning). Is there a typo in the second equation in Prop 2.1?", "broader_impact_concerns": "Clustering is an extremely widely encountered task and missing data is more than common. Knowing that a widely used method might not be consistent with full data access method under missing complete at random is an important information for scientists dealing with these data.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)