Asymptotic properties of kernel k-meansfor high dimensional data
Kento Egashiraa , Kazuyoshi Yatab , Makoto Aoshimaba Department of Information Sciences, Tokyo University of Scienceb Institute of Mathematics, University of Tsukuba

1Introduction

Cluster analysis can be divided into two types: hierarchical and partitional. Hierarchicalclustering groups data into dendrograms based on their cluster similarities determined bya preset linkage function. A dendrogram enables the observation of the process of merging or dividing clusters. For discussions on hierarchical cluster analyses, see the works ofEveritt et al. [6] and Hastie et al. [8], among others. Partitional clustering, as its namesuggests, divides data into a pre-determined number of clusters. K-means can be given on
behalf of partitional clustering. Notably, k-means has been approved as a useful tool for
analyzing microarray gene expression data. A characteristic of such data is that the number of variables was considerably larger than the sample size, giving high-dimensional,
low-sample-size (HDLSS) scenarios. Substantial work on HDLSS asymptotic clusteringhas been performed in recent years. For example, Liu et al. [10] proposed a two-way
split statistical-signiﬁcance-of-clustering (SigClust) method for HDLSS data. Ahn et al.
[1] proposed hierarchical divisive clustering for high-dimensional asymptotics. Huang etal. [7] modiﬁed SigClust using a soft thresholding approach. Kimes et al. [9] proposeda method for sequentially testing the statistical signiﬁcance of hierarchical clustering bycontrolling the family-wise error rate in HDLSS settings. Yata and Aoshima [14] presented
the consistency properties of sample principal component scores and applied them to clustering in high-dimensional settings. Nakayama et al. [12] investigated HDLSS clustering
using kernel principal component analysis. Borysov et al. [3] studied the behaviors ofhierarchical clustering under several asymptotic settings from a moderate dimension for
HDLSS; however, the theoretical assumptions were considered to be strict for HDLSS dataowing to several simultaneous asymptotic settings. Egashira et al. [5] explores practicalassumptions to indicate the behavior of hierarchical clustering and obtained theoreticalresults in multiclass settings. Given this background, asymptotic properties of k-means in
the HDLSS settings seems to have not been studied suﬃciently.
In this talk, we investigate k-means when both the dimension and sample size approachinﬁnity at ﬁrst. Then, we explores kernel k-means in the HDLSS context theoretically.
Especially, we mension kernel k-means with gaussian kernel function and compare performance of it to conventional k-means in the multiclass HDLSS context.

2Introduction of k-means

In this section, we introduce k-means. The k-means algorithm is a clustering method used
to divide a dataset into distinct clusters. It aims to minimize the within-cluster variance,
which is a measure of how similar the data points within each cluster are to each other.
The k-means algorithm applied to a given dataset X can be formulated as the following optimization problem, using a pre-deﬁned number of clusters k. The mathematicalformulation of k-means is given bykXX
b 1 , ..., Cb k } = argmin{C∥x − C i ∥2C 1 ,...,C k i=1 x∈C isubject to ∪ki=1 C i = X, C i ∩ C j = ∅ (i ̸= j).
b 1 , ..., Cb k } is given as the result of clustering
where C i = and ∥ · ∥is Euclidean norm. {Cby k-means.
The optimization problem above is generally solved by the following k-means algorithm
using k initial centroids.
Here is a step-by-step explanation of the k-means algorithm:
Initialize: Set k initial centroids ci (∈ X), i = 1, ..., k.
Assign: For each given data point x ∈ X, assign it to C i if i = arg minkj=1 ∥x − cj ∥2 .
Repeat this process for all data points to construct sets C i , i = 1, ..., k.
Update: Treat the arithmetic mean of the data points within each C i as the new initialvalue, and execute Step 2 to update sets C i , i = 1, ..., k. Repeat this step until
the sets from the previous step match the updated sets.
b i , i = 1, ..., k which is the result ofTerminate: Deﬁne the converged sets from Step 3 as C
the k-means algorithm.
The ﬁnal result of the k-means algorithm is a set of k clusters, each represented by its
centroid. The algorithm strives to minimize the sum of squared distances between the datapoints and their assigned centroids. It’s important to note that the k-means algorithm canbe sensitive to the initial placement of the centroids and may converge to a suboptimal
solution. To mitigate this, it is common to run the algorithm multiple times with diﬀerent initializations and choose the clustering result with the lowest overall within-cluster
variance. We acknowledge the importance of considering computational complexity andconvergence speed while primarily focusing on investigating the theoretical properties ofk-means and kernel k-means in high dimensional settings. In the next section, we show
asymptotic properties of k-means under HDLSS settings.

3

Asymptotic Behaviors of k-means for binary class

Suppose we have q independent and d-variate populations, Πi , with an unknown mean
vector µi , and an unknown covariance matrix, Σi for i = 1, ..., q. We suppose thattr(Σi ) ≤ tr(Σj )for i < j without loss of generality. We have independent
P and identically distributed
observations, xi1 , . . . , xini from Πi for i = 1, ..., q. Let Nq = qi=1 ni , X i = {xi1 , . . . , xini },Ki = Var[∥xij − µi ∥2 ] for i = 1, ..., q, ∆Σ,ij = |tr(Σi ) − tr(Σj )|, ∆ij = ∥µi − µj ∥2 fori, j = 1, ..., q.
In this section, we consider asymptotic properties in binary setting, q = 2 as d →∞ when N2 is ﬁxed. Suppose two class situation, q = 2. We introduce the following
assumptions:(A-i): tr(Σ2i )/∆212 → 0, i = 1, 2, as d → ∞;(A-ii): Ki /∆212 → 0, i = 1, 2, as d → ∞.
Note that Ki = 2tr(Σ2i ) when Πi is Gaussian; thus, (A-i) and (A-ii) are equivalent when
Πi , i = 1, 2 are Gaussian. These assumptions are fairly common in HDLSS settings. See
the works of Aoshima and Yata [2], Nakayama et al. [11], and Egashira et al. [4, 5].
Theorem 3.1. Suppose q = 2 and initial observation, ci ∈ X i for i = 1, 2. Assume (A-i),(A-ii) and some regularity conditions. Whenlim supd→∞∆Σ,12<1∆12b 1, Cb 2 } = {X 1 , X 2 }) → 1 as d → ∞ when N2 is ﬁxed.
holds, the probability, P ({CAcknowledgments
The research of the second author was partially supported by Grant-in-Aid for ScientiﬁcResearch (C), JSPS, under Contract Number 22K03412. The research of the third author
was partially supported by Grants-in-Aid for Scientiﬁc Research (A) and Challenging
Research (Exploratory), JSPS, under Contract Numbers 20H00576 and 22K19769.

References[1] Ahn, J., Lee, M.H., Yoon, Y.J. (2012). Clustering high dimension, low sample size
data using the maximal data piling distance. Statistica Sinica, 22, 443–464.
[2] Aoshima, M., Yata, K. (2014). A distance-based, misclassiﬁcation rate adjusted classiﬁer for multiclass, high-dimensional data. Annals of the Institute of Statistical Mathematics, 66, 983–1010.

[3] Borysov, P., Hannig, J., Marron, J.S. (2014). Asymptotics of hierarchical clustering
for growing dimension. Journal of Multivariate Analysis, 124, 465–479.
[4] Egashira, K., Yata, K., Aoshima, M. (2021). Asymptotic properties of distanceweighted discrimination and its bias correction for high-dimension, low-sample-size
data. Japanese Journal of Statistics and Data Science, 4, 821–840.
[5] Egashira, K., Yata, K., Aoshima, M. (2023). Asymptotic properties of hierarchicalclustering in high-dimensional settings. Journal of Multivariate Analysis, in press.
[6] Everitt, B.S., Landau, S., Leese, M. (2001). Cluster Analysis. Arnold, New York.
[7] Huang, H., Liu, Y., Yuan, M., Marron, J.S. (2015). Statistical Signiﬁcance of Clustering using Soft Thresholding. Journal of Computational and Graphical Statistics,24, 975–993.
[8] Hastie, T., Tibshirani, R., Friedman, J. (2009). The Elements of Statistical Learning:
Data Mining, Inference, and Prediction, Second Edition, Springer, New York.
[9] Kimes, P.K., Liu, Y., Neil, H.D., Marron, J.S. (2017) Statistical signiﬁcance for hierarchical clustering. Biometrics, 73, 811–821.
[10] Liu, Y., Hayes, D.N., Nobel, A., Marron, J.S.(2008). Statistical signiﬁcance of clustering for high-dimension, low-sample size data. Journal of the American StatisticalAssociation, 103, 1281–1293.
[11] Nakayama, Y., Yata, K., Aoshima, M. (2017). Support vector machine and its bias
correction in high-dimension, low-sample-size settings. Journal of Statistical Planningand Inference, 191, 88–100.
[12] Nakayama, Y., Yata, K., Aoshima, M. (2021). Clustering by principal component
analysis with Gaussian kernel in high-dimension, low-sample-size settings. Journal ofMultivariate Analysis, 185, 104779.
[13] Yata, K., Aoshima, M. (2010). Eﬀective PCA for high-dimension, low-sample-sizedata with singular value decomposition of cross data matrix. Journal of MultivariateAnalysis, 101, 2060–2077.
[14] Yata, K., Aoshima, M. (2020). Geometric consistency of principal component scoresfor high-dimensional mixture models and its application. Scandinavian Journal ofStatistics, 47, 899–921.