---
abstract: 'K-means is undoubtedly the most widely used partitional clustering algorithm. Unfortunately, due to its gradient descent nature, this algorithm is highly sensitive to the initial placement of the cluster centers. Numerous initialization methods have been proposed to address this problem. Many of these methods, however, have superlinear complexity in the number of data points, making them impractical for large data sets. On the other hand, linear methods are often random and/or order-sensitive, which renders their results unrepeatable. Recently, Su and Dy proposed two highly successful hierarchical initialization methods named Var-Part and PCA-Part that are not only linear, but also deterministic (non-random) and order-invariant. In this paper, we propose a discriminant analysis based approach that addresses a common deficiency of these two methods. Experiments on a large and diverse collection of data sets from the UCI Machine Learning Repository demonstrate that Var-Part and PCA-Part are highly competitive with one of the best random initialization methods to date, i.e., k-means++, and that the proposed approach significantly improves the performance of both hierarchical methods.'
address:
- |
    Department of Computer Science\
    Louisiana State University, Shreveport, LA, USA\
- |
    School of Electrical and Computer Engineering\
    Georgia Institute of Technology, Atlanta, GA, USA\
author:
- 'M. Emre Celebi'
- 'Hassan A. Kingravi'
title: 'Deterministic Initialization of the K-Means Algorithm Using Hierarchical Clustering'
---

Introduction {#sec_intro}
============

Clustering, the unsupervised classification of patterns into groups, is one of the most important tasks in exploratory data analysis [@Jain99]. Primary goals of clustering include gaining insight into data (detecting anomalies, identifying salient features, etc.), classifying data, and compressing data. Clustering has a long and rich history in a variety of scientific disciplines including anthropology, biology, medicine, psychology, statistics, mathematics, engineering, and computer science. As a result, numerous clustering algorithms have been proposed since the early 1950s [@Jain10].

Clustering algorithms can be broadly classified into two groups: hierarchical and partitional [@Jain10]. Hierarchical algorithms recursively find nested clusters either in a top-down (divisive) or bottom-up (agglomerative) fashion. In contrast, partitional algorithms find all the clusters simultaneously as a partition of the data and do not impose a hierarchical structure. Most hierarchical algorithms have quadratic or higher complexity in the number of data points [@Jain99] and therefore are not suitable for large data sets, whereas partitional algorithms often have lower complexity.

Given a data set ${{\mathcal X}}= \{ {{\bf x}}_1, {{\bf x}}_2, \dotsc, {{\bf x}}_N \}$ in $\mathbb{R}^D$, i.e., $N$ points (vectors) each with $D$ attributes (components), hard partitional algorithms divide ${{\mathcal X}}$ into $K$ exhaustive and mutually exclusive clusters $\mathcal{P} = \{ P_1, P_2, \dotsc, P_K \},$ $\;\; \bigcup\nolimits_{i = 1}^K {P_i = {{\mathcal X}}},$ $\;\; P_i \cap P_j = \emptyset$ for $1 \leq i \neq j \leq K$. These algorithms usually generate clusters by optimizing a criterion function. The most intuitive and frequently used criterion function is the Sum of Squared Error (SSE) given by: $$\label{eq_sse}
 \mbox{SSE} = \sum\limits_{i = 1}^K {\sum\limits_{{{\bf x}}_j \in P_i} {\left\| {{{\bf x}}_j - {{\bf c}}_i } \right\|_2^2 } }$$ where $\| . \|_2$ denotes the Euclidean ($\mathcal{L}_2$) norm and ${{\bf c}}_i =
{1 \mathord{\left/ {\vphantom {1 {\left| P_i \right|}}} \right.
 \kern-\nulldelimiterspace} {\left| P_i \right|}}\sum\nolimits_{{{\bf x}}_j \in P_i} {{{\bf x}}_j}$ is the centroid of cluster $P_i$ whose cardinality is $\left| P_i \right|$. The optimization of is often referred to as the minimum SSE clustering (MSSC) problem.

The number of ways in which a set of $N$ objects can be partitioned into $K$ non-empty groups is given by Stirling numbers of the second kind: $$\label{eq_num_parts}
\mathcal{S}(N,K) =
\frac{1}
{{K!}}\sum\limits_{i = 0}^K {( - 1)^{K - i} \left( \begin{gathered}
  K \hfill \\
  i \hfill \\
\end{gathered} \right)} i^N$$ which can be approximated by $K^N/K!$ It can be seen that a complete enumeration of all possible clusterings to determine the global minimum of is clearly computationally prohibitive except for very small data sets [@Kaufman90]. In fact, this non-convex optimization problem is proven to be NP-hard even for $K = 2$ [@Aloise09] or $D = 2$ [@Mahajan12]. Consequently, various heuristics have been developed to provide approximate solutions to this problem [@Tarsitano03]. Among these heuristics, Lloyd’s algorithm [@Lloyd82], often referred to as the (batch) k-means algorithm, is the simplest and most commonly used one. This algorithm starts with $K$ arbitrary centers, typically chosen uniformly at random from the data points. Each point is assigned to the nearest center and then each center is recalculated as the mean of all points assigned to it. These two steps are repeated until a predefined termination criterion is met.

The k-means algorithm is undoubtedly the most widely used partitional clustering algorithm [@Jain10]. Its popularity can be attributed to several reasons. First, it is conceptually simple and easy to implement. Virtually every data mining software includes an implementation of it. Second, it is versatile, i.e., almost every aspect of the algorithm (initialization, distance function, termination criterion, etc.) can be modified. This is evidenced by hundreds of publications over the last fifty years that extend k-means in various ways. Third, it has a time complexity that is linear in $N$, $D$, and $K$ (in general, $D \ll N$ and $K \ll N$). For this reason, it can be used to initialize more expensive clustering algorithms such as expectation maximization [@Bradley98], DBSCAN [@Dash01], and spectral clustering [@Chen11]. Furthermore, numerous sequential [@Kanungo02; @Hamerly10] and parallel [@Chen10] acceleration techniques are available in the literature. Fourth, it has a storage complexity that is linear in $N$, $D$, and $K$. In addition, there exist disk-based variants that do not require all points to be stored in memory [@Ordonez04]. Fifth, it is guaranteed to converge [@Selim84] at a quadratic rate [@Bottou95]. Finally, it is invariant to data ordering, i.e., random shufflings of the data points.

On the other hand, k-means has several significant disadvantages. First, it requires the number of clusters, $K$, to be specified in advance. The value of this parameter can be determined automatically by means of various internal/relative cluster validity measures [@Vendramin10]. Second, it can only detect compact, hyperspherical clusters that are well separated. This can be alleviated by using a more general distance function such as the Mahalanobis distance, which permits the detection of hyperellipsoidal clusters [@Mao96]. Third, due its utilization of the squared Euclidean distance, it is sensitive to noise and outlier points since even a few such points can significantly influence the means of their respective clusters. This can be addressed by outlier pruning [@Zhang03] or using a more robust distance function such as City-block ($\mathcal{L}_1$) distance. Fourth, due to its gradient descent nature, it often converges to a local minimum of the criterion function [@Selim84]. For the same reason, it is highly sensitive to the selection of the initial centers [@Celebi13a]. Adverse effects of improper initialization include empty clusters, slower convergence, and a higher chance of getting stuck in bad local minima [@Celebi11]. Fortunately, except for the first two, these drawbacks can be remedied by using an adaptive initialization method (IM).

A large number of IMs have been proposed in the literature [@Pena99; @He04; @Celebi11; @Celebi13a]. Unfortunately, many of these have superlinear complexity in $N$ [@Lance67; @Astrahan70; @Hartigan79; @Kaufman90; @Likas03; @AlDaoud05; @Redmond07; @AlHasan09; @Cao09; @Kang09], which makes them impractical for large data sets (note that k-means itself has linear complexity). In contrast, linear IMs are often random and/or order-sensitive [@Forgy65; @Jancey66; @MacQueen67; @Ball67; @Tou74; @Spath77; @Bradley98; @Arthur07], which renders their results unrepeatable. Su and Dy proposed two divisive hierarchical initialization methods named Var-Part and PCA-Part that are not only linear, but also deterministic and order-invariant [@Su07]. In this study, we propose a simple modification to these methods that improves their performance significantly.

The rest of the paper is organized as follows. Section \[sec\_init\_methods\] presents a brief overview of some of the most popular linear, order-invariant k-means IMs and the proposed modification to Var-Part and PCA-Part. Section \[sec\_exp\] presents the experimental results, while Section \[sec\_disc\] analyzes these results. Finally, Section \[sec\_conc\] gives the conclusions.

Linear, Order-Invariant Initialization Methods for K-Means {#sec_init_methods}
==========================================================

Overview of the Existing Methods
--------------------------------

Forgy’s method [@Forgy65] assigns each point to one of the $K$ clusters uniformly at random. The centers are then given by the centroids of these initial clusters. This method has no theoretical basis, as such random clusters have no internal homogeneity [@Anderberg73].

MacQueen [@MacQueen67] proposed two different methods. The first one, which is the default option in the Quick Cluster procedure of IBM SPSS Statistics [@Norusis11], takes the first $K$ points in ${{\mathcal X}}$ as the centers. An obvious drawback of this method is its sensitivity to data ordering. The second method chooses the centers randomly from the data points. The rationale behind this method is that random selection is likely to pick points from dense regions, i.e., points that are good candidates to be centers. However, there is no mechanism to avoid choosing outliers or points that are too close to each other [@Anderberg73]. Multiple runs of this method is the standard way of initializing k-means [@Bradley98]. It should be noted that this second method is often mistakenly attributed to Forgy [@Forgy65].

The maximin method [@Gonzalez85] chooses the first center ${{\bf c}}_1$ arbitrarily and the $i$-th ($i \in \{2, 3, \dotsc, K\}$) center ${{\bf c}}_i$ is chosen to be the point that has the greatest minimum-distance to the previously selected centers, i.e., ${{\bf c}}_1, {{\bf c}}_2, \dotsc, {{\bf c}}_{i-1}$. This method was originally developed as a $2$-approximation to the $K$-center clustering problem[^1].

The k-means++ method [@Arthur07] interpolates between MacQueen’s second method and the maximin method. It chooses the first center randomly and the $i$-th ($i \in \{ 2, 3, \dotsc, K \}$) center is chosen to be ${{\bf x}}' \in {{\mathcal X}}$ with a probability of $\frac{{md\left( {{{\bf x}}'} \right)^2 }}{{\sum\nolimits_{j = 1}^N {md({{\bf x}}_j)^2 }}}$, where $md({{\bf x}})$ denotes the minimum-distance from a point ${{\bf x}}$ to the previously selected centers. This method yields an $\Theta(\log{K})$ approximation to the MSSC problem.

The PCA-Part method [@Su07] uses a divisive hierarchical approach based on PCA (Principal Component Analysis) [@Hotelling36]. Starting from an initial cluster that contains the entire data set, the method iteratively selects the cluster with the greatest SSE and divides it into two subclusters using a hyperplane that passes through the cluster centroid and is orthogonal to the principal eigenvector of the cluster covariance matrix. This procedure is repeated until $K$ clusters are obtained. The centers are then given by the centroids of these clusters. The Var-Part method [@Su07] is an approximation to PCA-Part, where the covariance matrix of the cluster to be split is assumed to be diagonal. In this case, the splitting hyperplane is orthogonal to the coordinate axis with the greatest variance.

Figure \[fig\_varpart\_ruspini\] illustrates the Var-Part procedure on a toy data set with four natural clusters [@Ruspini70]. In iteration $1$, the initial cluster that contains the entire data set is split into two subclusters along the Y axis using a line (one-dimensional hyperplane) that passes through the mean point ($92.026667$). Between the resulting two clusters, the one above the line has a greater SSE. In iteration $2$, this cluster is therefore split along the X axis at the mean point ($66.975000$). In the final iteration, the cluster with the greatest SSE, i.e., the bottom cluster, is split along the X axis at the mean point ($41.057143$). In Figure \[part\_d\], the centroids of the final four clusters are denoted by stars.

\

Proposed Modification to Var-Part and PCA-Part {#sec_mod}
----------------------------------------------

Su and Dy [@Su07] demonstrated that, besides being computationally efficient, Var-Part and PCA-Part perform very well on a variety of data sets. Recall that in each iteration these methods select the cluster with the greatest SSE and then project the $D$-dimensional points in this cluster on a partitioning axis. The difference between the two methods is the choice of this axis. In Var-Part, the partitioning axis is the coordinate axis with the greatest variance, whereas in PCA-Part it is the major axis. After the projection operation, both methods use the *mean* point on the partitioning axis as a ‘threshold’ to divide the points between two clusters. In other words, each point is assigned to one of the two subclusters depending on which side of the *mean* point its projection falls to. It should be noted that the choice of this threshold is primarily motivated by computational convenience. Here, we propose a better alternative based on discriminant analysis.

The projections of the points on the partitioning axis can be viewed as a discrete probability distribution, which can be conveniently represented by a histogram. The problem of dividing a histogram into two partitions is a well studied one in the field of image processing. A plethora of histogram partitioning, a.k.a. thresholding, methods has been proposed in the literature with the early ones dating back to the 1960s [@Sezgin04]. Among these, Otsu’s method [@Otsu79] has become the method of choice as confirmed by numerous comparative studies [@Sahoo88; @Lee90; @Trier95; @Sezgin04; @Medina05; @Celebi13b].

Given an image represented by $L$ gray levels $\left\{ 0, 1, \dotsc, L - 1\right\}$, a thresholding method partitions the image pixels into two classes $\mathcal{C}_0 = \left\{ 0, 1, \dotsc, t \right\}$ and $\mathcal{C}_1 = \{ t + 1, t + 2,$ $\dotsc, L - 1 \}$ (object and background, or vice versa) at gray level $t$. In other words, pixels with gray levels less than or equal to the threshold $t$ are assigned to $\mathcal{C}_0$, whereas the remaining pixels are assigned to $\mathcal{C}_1$.

Let $n_i$ be the number of pixels with gray level $i$. The total number of pixels in the image is then given by $n = \sum\nolimits_{i = 0}^{L - 1}{n_i}$. The normalized gray level histogram of the image can be regarded as a probability mass function: $$p_i = \frac{n_i}{n},\quad p_i \ge 0,\quad \sum\limits_{i = 0}^{L - 1} {p_i}  = 1$$

Let $p_0(t) = \sum\nolimits_{i = 0}^t {p_i}$ and $p_1(t) = 1 - p_0(t)$ denote the probabilities of $\mathcal{C}_0$ and $\mathcal{C}_1$, respectively. The means of the respective classes are then given by: $$\begin{array}{l}
 \mu _0 (t) = {{\mu (t)} \mathord{\left/
 {\vphantom {{\mu (t)} {p_0 (t)}}} \right.
 \kern-\nulldelimiterspace} {p_0 (t)}} \\
 \mu _1 (t) = {{\left( {\mu _T  - \mu (t)} \right)} \mathord{\left/
 {\vphantom {{\left( {\mu _T  - \mu (t)} \right)} {p_1 (t)}}} \right.
 \kern-\nulldelimiterspace} {p_1 (t)}} \\
 \end{array}$$ where $\mu(t) = \sum\nolimits_{i = 0}^t {ip_i}$ and $\mu_T  = \mu(L - 1)$ denote the first moment of the histogram up to gray level $t$ and mean gray level of the image, respectively.

Otsu’s method adopts between-class variance, i.e., $\sigma_B^2(t) = p_0(t) p_1(t) \left[ {\mu_0(t) - \mu_1(t)} \right]^2$, from the discriminant analysis literature as its objective function and determines the optimal threshold $t^*$ as the gray level that maximizes $\sigma_B^2(t)$, i.e., $t^* = \mathop {{\mathop{\rm argmax}\nolimits} }\limits_{t \in \left\{0,1,\dotsc,L - 1 \right\}} \sigma_B^2(t)$. Between-class variance can be viewed as a measure of class separability or histogram bimodality. It can be efficiently calculated using: $$\sigma_B^2(t) = \frac{{\left[ {\mu_T p_0(t) - \mu(t)} \right]^2 }}{{p_0(t) p_1(t)}}$$

It should be noted that the efficiency of Otsu’s method can be attributed to the fact that it operates on histogrammed pixel gray values, which are non-negative integers. Var-Part and PCA-Part, on the other hand, operate on the projections of the points on the partitioning axis, which are often fractional. This problem can be circumvented by linearly scaling the projection values to the limits of the histogram, i.e., $0$ and $L-1$. Let $y_i$ be the projection of a point ${{\bf x}}_i$ on the partitioning axis. $y_i$ can be mapped to histogram bin $b$ given by: $$b = \left\lfloor {\frac{{L\left( {y_i - \mathop {\min }\limits_j y_j } \right)}}{{\mathop {\max }\limits_j y_j - \mathop {\min}\limits_j y_j }}} \right\rfloor$$ where $\lfloor z \rfloor$ is the floor function which returns the largest integer less than or equal to $z$.

The computational complexities of histogram construction and Otsu’s method are $\mathcal{O}(N_i)$ ($N_i$: number of points in the cluster) and $\mathcal{O}(L)$, respectively. $L$ is constant in our experiments and therefore the proposed modification does not alter the linear time complexity of Var-Part and PCA-Part.

Figure \[fig\_histo\] shows a histogram where using the mean point as a threshold leads to poor results. This histogram is constructed during the first iteration of PCA-Part from the projections of the points in the Shuttle data set (see Table \[tab\_data\_set\]). As marked on the figure, the mean point of this histogram is $61$, whereas Otsu’s method gives a threshold of $105$. The SSE of the initial cluster is $1,836$. When the mean point of the histogram is used a threshold, the resulting two subclusters have SSE’s of $408$ and $809$. This means that splitting the initial cluster with a hyperplane orthogonal to the principal eigenvector of the cluster covariance matrix at the mean point results in approximately $34$% reduction in the SSE. On the other hand, when Otsu’s threshold is used, the subclusters have SSE’s of $943$ and $101$, which translates to about $43$% reduction in the SSE. In the next section, we will demonstrate that using Otsu’s threshold instead of the mean point often leads to significantly better initial clusterings on a variety of data sets.

![\[fig\_histo\] Comparison of mean point and Otsu’s thresholds](otsupca_shuttle_histo){width="0.8\columnwidth"}

Experimental Results {#sec_exp}
====================

The experiments were performed on $24$ commonly used data sets from the UCI Machine Learning Repository [@Frank12]. Table \[tab\_data\_set\] gives the data set descriptions. For each data set, the number of clusters ($K$) was set equal to the number of classes ($K'$), as commonly seen in the related literature [@He04; @Arthur07; @Su07; @Redmond07; @AlHasan09; @Cao09; @Kang09; @Onoda12].

In clustering applications, normalization is a common preprocessing step that is necessary to prevent attributes with large ranges from dominating the distance calculations and also to avoid numerical instabilities in the computations. Two commonly used normalization schemes are linear scaling to unit range (min-max normalization) and linear scaling to unit variance (z-score normalization). Several studies revealed that the former scheme is preferable to the latter since the latter is likely to eliminate valuable between-cluster variation [@Milligan88; @Su07]. As a result, we used min-max normalization to map the attributes of each data set to the $[0,1]$ interval.

  ID   Data Set                                  $N$   $D$   $K'$
  ---- ------------------------------------ -------- ----- ------
  1    Abalone                                 4,177     7     28
  2    Breast Cancer Wisconsin (Original)        683     9      2
  3    Breast Tissue                             106     9      6
  4    Ecoli                                     336     7      8
  5    Glass Identification                      214     9      6
  6    Heart Disease                             297    13      5
  7    Ionosphere                                351    34      2
  8    Iris (Bezdek)                             150     4      3
  9    ISOLET                                  7,797   617     26
  10   Landsat Satellite (Statlog)             6,435    36      6
  11   Letter Recognition                     20,000    16     26
  12   MAGIC Gamma Telescope                  19,020    10      2
  13   Multiple Features (Fourier)             2,000    76     10
  14   Musk (Clean2)                           6,598   166      2
  15   Optical Digits                          5,620    64     10
  16   Page Blocks Classification              5,473    10      5
  17   Pima Indians Diabetes                     768     8      2
  18   Shuttle (Statlog)                      58,000     9      7
  19   Spambase                                4,601    57      2
  20   SPECTF Heart                              267    44      2
  21   Wall-Following Robot Navigation         5,456    24      4
  22   Wine Quality                            6,497    11      7
  23   Wine                                      178    13      3
  24   Yeast                                   1,484     8     10

  : \[tab\_data\_set\] Data Set Descriptions ($N$: \# points, $D$: \# attributes, $K'$: \# classes)

The performance of the IMs was quantified using two effectiveness (quality) and two efficiency (speed) criteria:

-   [**Initial SSE**]{}: This is the SSE value calculated after the initialization phase, before the clustering phase. It gives us a measure of the effectiveness of an IM by itself.

-   [**Final SSE**]{}: This is the SSE value calculated after the clustering phase. It gives us a measure of the effectiveness of an IM when its output is refined by k-means. Note that this is the objective function of the k-means algorithm, i.e., .

-   [**Number of Iterations**]{}: This is the number of iterations that k-means requires until reaching convergence when initialized by a particular IM. It is an efficiency measure independent of programming language, implementation style, compiler, and CPU architecture.

-   [**CPU Time**]{}: This is the total CPU time in milliseconds taken by the initialization and clustering phases.

All of the methods were implemented in the `C` language, compiled with the `gcc` v4.4.3 compiler, and executed on an Intel Xeon E5520 2.26GHz machine. Time measurements were performed using the `getrusage` function, which is capable of measuring CPU time to an accuracy of a microsecond. The MT19937 variant of the Mersenne Twister algorithm was used to generate high quality pseudorandom numbers [@Matsumoto98].

The convergence of k-means was controlled by the disjunction of two criteria: the number of iterations reaches a maximum of $100$ or the relative improvement in SSE between two consecutive iterations drops below a threshold, i.e., $ {{\left( {\mbox{SSE}_{i - 1} - \mbox{SSE}_i} \right)} \mathord{\left/ {\vphantom {{\left( {\mbox{SSE}_{i - 1} - \mbox{SSE}_i} \right)} {\mbox{SSE}_i}}} \right. \kern-\nulldelimiterspace} {\mbox{SSE}_i}} \leq \varepsilon $, where $\mbox{SSE}_i$ denotes the SSE value at the end of the $i$-th ($i \in \{ 1, 2, \dotsc, 100 \}$) iteration. The convergence threshold was set to $\varepsilon = 10^{-6}$.

In this study, we focus on IMs that have time complexity linear in $N$. This is because k-means itself has linear complexity, which is perhaps the most important reason for its popularity. Therefore, an IM for k-means should not diminish this advantage of the algorithm. The proposed methods, named Otsu Var-Part (`OV`) and Otsu PCA-Part (`OP`), were compared to six popular, linear, order-invariant IMs: Forgy’s method (`F`), MacQueen’s second method (`M`), maximin (`X`), k-means++ (`K`), Var-Part (`V`), and PCA-Part (`P`). It should be noted that among these methods `F`, `M`, and `K` are random, whereas `X`[^2], `V`, `P`, `OV`, and `OP` are deterministic.

We first examine the influence of $L$ (number of histogram bins) on the performance of `OV` and `OP`. Tables \[tab\_num\_bins\_var\] and \[tab\_num\_bins\_pca\] show the initial and final SSE values obtained by respectively `OV` and `OP` for $L = 64, 128, 256, 512, 1024$ on four of the largest data sets (the best values are [underlined]{}). It can be seen that the performances of both methods are relatively insensitive to the value of $L$. Therefore, in the subsequent experiments we report the results for $L = 256$.

  ID   Criterion           $L=64$     $L=128$      $L=256$     $L=512$    $L=1024$
  ---- ------------- ------------ ----------- ------------ ----------- -----------
  9    Initial SSE     [143859]{}      144651       144658      144637      144638
       Final SSE           118267      119127   [118033]{}      118033      118034
  10   Initial SSE           1987        1920     [1919]{}        1920        1920
       Final SSE         [1742]{}    [1742]{}     [1742]{}    [1742]{}    [1742]{}
  11   Initial SSE           3242    [3192]{}         3231        3202        3202
       Final SSE             2742    [2734]{}     [2734]{}    [2734]{}    [2734]{}
  15   Initial SSE      [17448]{}       17504        17504       17504       17504
       Final SSE        [14581]{}   [14581]{}    [14581]{}   [14581]{}   [14581]{}

  : \[tab\_num\_bins\_var\] Influence of $L$ on the effectiveness of Otsu Var-Part ($L$: \# histogram bins)

  ID   Criterion          $L=64$     $L=128$      $L=256$      $L=512$    $L=1024$
  ---- ------------- ----------- ----------- ------------ ------------ -----------
  9    Initial SSE        123527      123095   [122528]{}       123129      123342
       Final SSE          118575      118577       119326   [118298]{}      118616
  10   Initial SSE          1855    [1807]{}         1835         1849        1848
       Final SSE        [1742]{}    [1742]{}     [1742]{}     [1742]{}    [1742]{}
  11   Initial SSE          2994        2997         2995         2995    [2991]{}
       Final SSE        [2747]{}    [2747]{}     [2747]{}     [2747]{}    [2747]{}
  15   Initial SSE         15136       15117        15118    [15116]{}       15117
       Final SSE       [14650]{}   [14650]{}    [14650]{}    [14650]{}   [14650]{}

  : \[tab\_num\_bins\_pca\] Influence of $L$ on the effectiveness of Otsu PCA-Part ($L$: \# histogram bins)

In the remaining experiments, each random method was executed a $100$ times and statistics such as *minimum*, *mean*, and *standard deviation* were collected for each performance criteria. The *minimum* and *mean* statistics represent the *best* and *average* case performance, respectively, while *standard deviation* quantifies the *variability* of performance across different runs. Note that for a deterministic method, the *minimum* and *mean* values are always identical and the *standard deviation* is always $0$.

Tables \[tab\_init\_sse\]–\[tab\_cpu\_time\] give the performance measurements for each method with respect to initial SSE, final SSE, number of iterations, and CPU time, respectively. For each of the initial SSE, final SSE, and number of iterations criteria, we calculated the ratio of the *minimum*/*mean*/*standard deviation* value obtained by each method to the best (least) *minimum*/*mean*/*standard deviation* value on each data set. These ratios will be henceforth referred to as the ‘normalized’ performance criteria. For example, on the Abalone data set (1), the *minimum* initial SSE of `F` is $424.92$ and the best *minimum* initial SSE is $21.57$ and thus the normalized initial SSE is about $20$. This simply means that on this data set `F` obtained approximately $20$ times worse *minimum* initial SSE than the best method. We then averaged[^3] these normalized values over the $24$ data sets to quantify the *overall* performance of each method with respect to each statistic (see Table \[tab\_summary\]). Note that we did not attempt to summarize the CPU time values in the same manner due to the sparsity of the data (see Table \[tab\_cpu\_time\]). For convenient visualization, Figure \[fig\_boxplots\] shows box plots of the normalized performance criteria. Here, the bottom and top end of the whiskers of a box represent the *minimum* and *maximum*, respectively, whereas the bottom and top of the box itself are the $25$th percentile (*Q1*) and $75$th percentile (*Q3*), respectively. The line that passes through the box is the $50$th percentile (*Q2*), i.e., the *median*, while the small square inside the box denotes the *mean*.

Discussion {#sec_disc}
==========

Best Case Performance Analysis
------------------------------

With respect to the *minimum* statistic, the following observations can be made:

-   [**Initial SSE**]{}: `OP` is the best method, followed closely by `P`, `OV`, and `V`. On the other hand, `F` is the worst method, followed by `X`. These two methods give $2$–$3$ times worse *minimum* initial SSE than the best method. It can be seen that multiple runs of random methods do not produce good initial clusterings. In contrast, only a single run of `OP`, `P`, `OV`, or `V` often gives very good results. This is because these methods are approximate clustering algorithms by themselves and thus they give reasonable results even without k-means refinement.

-   [**Final SSE**]{}: `X` is the worst method, while the remaining methods exhibit very similar performance. This homogeneity in performance is because k-means can take two disparate initial configurations to similar (or even identical) local minima. Given the abundance of local minima even in data sets of moderate size and/or dimensionality and the gradient descent nature of k-means, it is not surprising that the deterministic methods (except `X`) perform slightly worse than the random methods as the former methods were executed only once, whereas the latter ones were executed a $100$ times.

-   [**Number of Iterations**]{}: `K` is the best method, followed by `M` and `F`. `X` is the worst method. As in the case of final SSE, random methods outperform deterministic methods due to their multiple-run advantage.

Average Case Performance Analysis
---------------------------------

With respect to the *mean* statistic, the following observations can be made:

-   [**Initial SSE**]{}: `OP` is the best method, followed closely by `P`, `OV`, and `V`. The remaining methods give $1.7$–$3.2$ times worse *mean* initial SSE than any of these hierarchical methods. Random methods exhibit significantly worse *average* performance than the deterministic ones because the former methods can produce highly variable results across different runs (see the standard deviation values in Table \[tab\_init\_sse\]).

-   [**Final SSE**]{}: This is similar to the case of *minimum* final SSE, with the difference that deterministic methods (except `X`) are now slightly better than the random ones. Once again, this is because random methods can produce highly variable results due to their stochastic nature.

-   [**Number of Iterations**]{}: The ranking of the methods is similar to the case of *mean* final SSE.

Consistency Analysis
--------------------

With respect to the *standard deviation* statistic, `F` is significantly better than both `M` and `K`. If, however, the application requires absolute consistency, i.e., exactly the same clustering in every run, a deterministic IM should be used.

CPU Time Analysis
-----------------

It can be seen from Table \[tab\_cpu\_time\] that, on about half of the data sets, each of the IMs require less than a few milliseconds of CPU time. On the other hand, on large and/or high-dimensional data sets efficiency differences become more prominent. It should be noted that each of the values reported in this table corresponds to a single k-means ‘run’. In practice, a random method is typically executed $R$ times, e.g., in this study $R=100$, and the output of the run that gives the least final SSE is taken as the result. Therefore, the total computational cost of a random method is often significantly higher than that of a deterministic method. For example, on the ISOLET data set, which has the greatest $N \times D \times K$ value among all the data sets, `K` took on the average $3,397$ milliseconds, whereas `OP` took $12,460$ milliseconds. The latter method, however, required about $27$ times less CPU time than the former one since the former was executed a total of $100$ times.

Relative Performance Analysis
-----------------------------

We also determined the number of data sets (out of 24) on which `OV` and `OP` respectively performed $\{$worse than/same as/better than$\}$ `V` and `P`. Tables \[tab\_rel\_var\] and \[tab\_rel\_pca\] present the results for `OV` and `OP`, respectively. It can be seen that, with respect to initial SSE and number of iterations criteria, `OV` outperforms `V` more often than not. On the other hand, `OP` frequently outperforms `P` with respect to both criteria. As for final SSE, `OP` performs slightly better than `P`, whereas `OV` performs slightly worse than `V`. It appears that Otsu’s method benefits `P` more than it benefits `V`. This is most likely due to the fact that histograms of projections over the major axis necessarily have a greater dynamic range and variability and thus are more amenable to thresholding compared to histograms of projections over any coordinate axis.

Recommendations for Practitioners
---------------------------------

Based on the analyses presented above, the following recommendations can be made:

-   In general, `X` should not be used. As mentioned in Section \[sec\_init\_methods\], this method was not designed specifically as a k-means initializer [@Gonzalez85]. It is easy to understand and implement, but is mostly ineffective and unreliable. Furthermore, despite its low overhead, this method does not offer significant time savings since it often results in slow k-means convergence.

-   In applications that involve small data sets, e.g., $N < 1,000$, `K` should be used. It is computationally feasible to run this method hundreds of times on such data sets given that one such run takes only a few milliseconds.

-   In time-critical applications that involve large data sets or applications that demand determinism, the hierarchical methods should be used. These methods need to be executed only once and they lead to reasonably fast k-means convergence. The efficiency difference between `V`/`OV` and `P`/`OP` is noticeable only on high dimensional data sets such as ISOLET ($D=617$) and Musk ($D=166$). This is because `V`/`OV` calculates the direction of split by determining the coordinate axis with the greatest variance (in $\mathcal{O}(D)$ time), whereas `P`/`OP` achieves this by calculating the principal eigenvector of the cluster covariance matrix (in $\mathcal{O}(D^2)$ time using the power method [@Hotelling36]). Note that despite its higher computational complexity, `P`/`OP` can, in some cases, be more efficient than `V`/`OV` (see Table \[tab\_cpu\_time\]). This is because the former converges significantly faster than the latter (see Table \[tab\_summary\]). The main disadvantage of these methods is that they are more complicated to implement due to their hierarchical formulation.

-   In applications where an approximate clustering of the data set is desired, the hierarchical methods should be used. These methods produce very good initial clusterings, which makes it possible to use them as standalone clustering algorithms.

-   Among the hierarchical methods, the ones based on PCA, i.e., `P` and `OP`, are preferable to those based on variance, i.e., `V` and `OV`. Furthermore, the proposed `OP` and `OV` methods generally outperform their respective counterparts, i.e., `P` and `V`, especially with respect to initial SSE and number of iterations.

Conclusions {#sec_conc}
===========

In this paper, we presented a simple modification to Var-Part and PCA-Part, two hierarchical k-means initialization methods that are linear, deterministic, and order-invariant. We compared the original methods and their modified versions to some of the most popular linear initialization methods, namely Forgy’s method, Macqueen’s second method, maximin, and k-means++, on a large and diverse collection of data sets from the UCI Machine Learning Repository. The results demonstrated that, despite their deterministic nature, Var-Part and PCA-Part are highly competitive with one of the best random initialization methods to date, i.e., k-means++. In addition, the proposed modification significantly improves the performance of both hierarchical methods. The presented Var-Part and PCA-Part variants can be used to initialize k-means effectively, particularly in time-critical applications that involve large data sets. Alternatively, they can be used as approximate clustering algorithms without additional k-means refinement.

Acknowledgments
===============

This publication was made possible by grants from the Louisiana Board of Regents (LEQSF2008-11-RD-A-12) and National Science Foundation (0959583, 1117457).

[10]{}

A. K. Jain, M. N. Murty, and P. J. Flynn, “[Data Clustering: A Review]{},” [ *ACM Computing Surveys*]{}, vol. 31, no. 3, pp. 264–323, 1999.

A. K. Jain, “[Data Clustering: 50 Years Beyond K-Means]{},” [*Pattern Recognition Letters*]{}, vol. 31, no. 8, pp. 651–666, 2010.

L. Kaufman and P. Rousseeuw, [*[Finding Groups in Data: An Introduction to Cluster Analysis]{}*]{}. Wiley-Interscience, 1990.

D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “[NP-Hardness of Euclidean Sum-of-Squares Clustering]{},” [*Machine Learning*]{}, vol. 75, no. 2, pp. 245–248, 2009.

M. Mahajan, P. Nimbhorkar, and K. Varadarajan, “[The Planar k-Means Problem is NP-hard]{},” [*Theoretical Computer Science*]{}, vol. 442, pp. 13–21, 2012.

A. Tarsitano, “[A Computational Study of Several Relocation Methods for K-Means Algorithms]{},” [*Pattern Recognition*]{}, vol. 36, no. 12, pp. 2955–2966, 2003.

S. Lloyd, “[Least Squares Quantization in PCM]{},” [*IEEE Transactions on Information Theory*]{}, vol. 28, no. 2, pp. 129–136, 1982.

P. S. Bradley and U. Fayyad, “[Refining Initial Points for K-Means Clustering]{},” in [*Proc. of the 15th Int. Conf. on Machine Learning*]{}, pp. 91–99, 1998.

M. Dash, H. Liu, and X. Xu, “[’$1 +1 > 2$’: Merging Distance and Density Based Clustering]{},” in [*Proc. of the 7th Int. Conf. on Database Systems for Advanced Applications*]{}, pp. 32–39, 2001.

W. Y. Chen, Y. Song, H. Bai, C. J. Lin, and E. Y. Chang, “[Parallel Spectral Clustering in Distributed Systems]{},” [*IEEE Transactions on Pattern Analysis and Machine Intelligence*]{}, vol. 33, no. 3, pp. 568–586, 2011.

T. Kanungo, D. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Wu, “[An Efficient K-Means Clustering Algorithm: Analysis and Implementation]{},” [ *IEEE Transactions on Pattern Analysis and Machine Intelligence*]{}, vol. 24, no. 7, pp. 881–892, 2002.

G. Hamerly, “[Making k-means Even Faster]{},” in [*Proc. of the 2010 SIAM Int. Conf. on Data Mining*]{}, pp. 130–140, 2010.

T. W. Chen and S. Y. Chien, “[Bandwidth Adaptive Hardware Architecture of K-Means Clustering for Video Analysis]{},” [*IEEE Transactions on Very Large Scale Integration (VLSI) Systems*]{}, vol. 18, no. 6, pp. 957–966, 2010.

C. Ordonez and E. Omiecinski, “[Efficient Disk-Based K-Means Clustering for Relational Databases]{},” [*IEEE Transactions on Knowledge and Data Engineering*]{}, vol. 16, no. 8, pp. 909–921, 2004.

S. Z. Selim and M. A. Ismail, “[K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality]{},” [*IEEE Transactions on Pattern Analysis and Machine Intelligence*]{}, vol. 6, no. 1, pp. 81–87, 1984.

L. Bottou and Y. Bengio, “[Convergence Properties of the K-Means Algorithms]{},” in [*[Advances in Neural Information Processing Systems 7]{}*]{} (G. Tesauro, D. S. Touretzky, and T. K. Leen, eds.), pp. 585–592, MIT Press, 1995.

L. Vendramin, R. J. G. B. Campello, and E. R. Hruschka, “[Relative Clustering Validity Criteria: A Comparative Overview]{},” [*Statistical Analysis and Data Mining*]{}, vol. 3, no. 4, pp. 209–235, 2010.

J. Mao and A. K. Jain, “[A Self-Organizing Network for Hyperellipsoidal Clustering (HEC)]{},” [*IEEE Transactions on Neural Networks*]{}, vol. 7, no. 1, pp. 16–29, 1996.

J. S. Zhang and Y.-W. Leung, “[Robust Clustering by Pruning Outliers]{},” [ *IEEE Transactions on Systems, Man, and Cybernetics – Part B*]{}, vol. 33, no. 6, pp. 983–999, 2003.

M. E. Celebi, H. Kingravi, and P. A. Vela, “[A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm]{},” [*Expert Systems with Applications*]{}, vol. 40, no. 1, pp. 200–210, 2013.

M. E. Celebi, “[Improving the Performance of K-Means for Color Quantization]{},” [*Image and Vision Computing*]{}, vol. 29, no. 4, pp. 260–271, 2011.

J. M. Pena, J. A. Lozano, and P. Larranaga, “[An Empirical Comparison of Four Initialization Methods for the K-Means Algorithm]{},” [*Pattern Recognition Letters*]{}, vol. 20, no. 10, pp. 1027–1040, 1999.

J. He, M. Lan, C. L. Tan, S. Y. Sung, and H. B. Low, “[Initialization of Cluster Refinement Algorithms: A Review and Comparative Study]{},” in [ *Proc. of the 2004 IEEE Int. Joint Conf. on Neural Networks*]{}, pp. 297–302, 2004.

G. N. Lance and W. T. Williams, “[A General Theory of Classificatory Sorting Strategies - II. Clustering Systems]{},” [*The Computer Journal*]{}, vol. 10, no. 3, pp. 271–277, 1967.

M. M. Astrahan, “[Speech Analysis by Clustering, or the Hyperphoneme Method]{},” Tech. Rep. AIM-124, Stanford University, 1970.

J. A. Hartigan and M. A. Wong, “[Algorithm AS 136: A K-Means Clustering Algorithm]{},” [*Journal of the Royal Statistical Society C*]{}, vol. 28, no. 1, pp. 100–108, 1979.

A. Likas, N. Vlassis, and J. Verbeek, “[The Global K-Means Clustering Algorithm]{},” [*Pattern Recognition*]{}, vol. 36, no. 2, pp. 451–461, 2003.

M. Al-Daoud, “[A New Algorithm for Cluster Initialization]{},” in [*Proc. of the 2nd World Enformatika Conf.*]{}, pp. 74–76, 2005.

S. J. Redmond and C. Heneghan, “[A Method for Initialising the K-Means Clustering Algorithm Using kd-trees]{},” [*Pattern Recognition Letters*]{}, vol. 28, no. 8, pp. 965–973, 2007.

M. Al Hasan, V. Chaoji, S. Salem, and M. Zaki, “[Robust Partitional Clustering by Outlier and Density Insensitive Seeding]{},” [*Pattern Recognition Letters*]{}, vol. 30, no. 11, pp. 994–1002, 2009.

F. Cao, J. Liang, and G. Jiang, “[An Initialization Method for the K-Means Algorithm Using Neighborhood Model]{},” [*Computers and Mathematics with Applications*]{}, vol. 58, no. 3, pp. 474–483, 2009.

P. Kang and S. Cho, “[K-Means Clustering Seeds Initialization Based on Centrality, Sparsity, and Isotropy]{},” in [*Proc. of the 10th Int. Conf. on Intelligent Data Engineering and Automated Learning*]{}, pp. 109–117, 2009.

E. Forgy, “[Cluster Analysis of Multivariate Data: Efficiency vs. Interpretability of Classification]{},” [*Biometrics*]{}, vol. 21, p. 768, 1965.

R. C. Jancey, “[Multidimensional Group Analysis]{},” [*Australian Journal of Botany*]{}, vol. 14, no. 1, pp. 127–130, 1966.

J. MacQueen, “[Some Methods for Classification and Analysis of Multivariate Observations]{},” in [*Proc. of the 5th Berkeley Symposium on Mathematical Statistics and Probability*]{}, pp. 281–297, 1967.

G. H. Ball and D. J. Hall, “[A Clustering Technique for Summarizing Multivariate Data]{},” [*Behavioral Science*]{}, vol. 12, no. 2, pp. 153–155, 1967.

J. T. Tou and R. C. Gonzales, [*[Pattern Recognition Principles]{}*]{}. Addison-Wesley, 1974.

H. Späth, “[Computational Experiences with the Exchange Method: Applied to Four Commonly Used Partitioning Cluster Analysis Criteria]{},” [*European Journal of Operational Research*]{}, vol. 1, no. 1, pp. 23–31, 1977.

D. Arthur and S. Vassilvitskii, “[k-means++: The Advantages of Careful Seeding]{},” in [*Proc. of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms*]{}, pp. 1027–1035, 2007.

T. Su and J. G. Dy, “[In Search of Deterministic Methods for Initializing K-Means and Gaussian Mixture Clustering]{},” [*Intelligent Data Analysis*]{}, vol. 11, no. 4, pp. 319–338, 2007.

M. R. Anderberg, [*[Cluster Analysis for Applications]{}*]{}. Academic Press, 1973.

M. J. Norušis, [*[IBM SPSS Statistics 19 Statistical Procedures Companion]{}*]{}. Addison Wesley, 2011.

T. Gonzalez, “[Clustering to Minimize the Maximum Intercluster Distance]{},” [*Theoretical Computer Science*]{}, vol. 38, no. 2–3, pp. 293–306, 1985.

H. Hotelling, “[Simplified Calculation of Principal Components]{},” [ *Psychometrika*]{}, vol. 1, no. 1, pp. 27–35, 1936.

E. H. Ruspini, “[Numerical Methods for Fuzzy Clustering]{},” [*Information Sciences*]{}, vol. 2, no. 3, pp. 319–350, 1970.

M. Sezgin and B. Sankur, “[Survey over Image Thresholding Techniques and Quantitative Performance Evaluation]{},” [*Journal of Electronic Imaging*]{}, vol. 13, no. 1, pp. 146–165, 2004.

N. Otsu, “[A Threshold Selection Method from Gray Level Histograms]{},” [ *IEEE Transactions on Systems, Man and Cybernetics*]{}, vol. 9, no. 1, pp. 62–66, 1979.

P. K. Sahoo, S. Soltani, and A. K. C. Wong, “[A Survey of Thresholding Techniques]{},” [*Computer Vision, Graphics, and Image Processing*]{}, vol. 41, no. 2, pp. 233–260, 1988.

S. U. Lee, S. Y. Chung, and R. H. Park, “[A Comparative Performance Study of Several Global Thresholding Techniques]{},” [*Computer Vision, Graphics, and Image Processing*]{}, vol. 52, no. 2, pp. 171–190, 1990.

O. D. Trier and T. Taxt, “[Evaluation of Binarization Methods for Document Images]{},” [*IEEE Transactions on Pattern Analysis and Machine Intelligence*]{}, vol. 17, no. 3, pp. 312–315, 1995.

R. Medina-Carnicer, F. J. Madrid-Cuevas, N. L. Fernandez-Garcia, and A. Carmona-Poyato, “[Evaluation of Global Thresholding Techniques in Non-Contextual Edge Detection]{},” [*Pattern Recognition Letters*]{}, vol. 26, no. 10, pp. 1423–1434, 2005.

M. E. Celebi, Q. Wen, S. Hwang, H. Iyatomi, and G. Schaefer, “[Lesion Border Detection in Dermoscopy Images Using Ensembles of Thresholding Methods]{},” [*Skin Research and Technology*]{}, vol. 19, no. 1, pp. e252–e258, 2013.

A. Frank and A. Asuncion, “[UCI Machine Learning Repository]{}.” <http://archive.ics.uci.edu/ml>, 2012. .

T. Onoda, M. Sakai, and S. Yamada, “[Careful Seeding Method based on Independent Components Analysis for k-means Clustering]{},” [*Journal of Emerging Technologies in Web Intelligence*]{}, vol. 4, no. 1, pp. 51–59, 2012.

G. Milligan and M. C. Cooper, “[A Study of Standardization of Variables in Cluster Analysis]{},” [*Journal of Classification*]{}, vol. 5, no. 2, pp. 181–204, 1988.

M. Matsumoto and T. Nishimura, “[Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator]{},” [*ACM Transactions on Modeling and Computer Simulation*]{}, vol. 8, no. 1, pp. 3–30, 1998.

[c|c|r|r|r|r|r|r|r|r]{} & & `F` & `M` & `K` & `X` & `V` & `P` & `OV` & `OP`\
& min & 425 & 33 & 29 & 95 & 24 & 23 & 23 & [22]{}\
& mean & 483 $\pm$ 20 & 46 $\pm$ 10 & 34 $\pm$ 2 & 95 $\pm$ 0 & 24 $\pm$ 0 & 23 $\pm$ 0 & 23 $\pm$ 0 & [22]{} $\pm$ 0\
& min & 534 & 318 & 304 & 498 & 247 & 240 & 258 & [239]{}\
& mean & 575 $\pm$ 15 & 706 $\pm$ 354 & 560 $\pm$ 349 & 498 $\pm$ 0 & 247 $\pm$ 0 & 240 $\pm$ 0 & 258 $\pm$ 0 & [239]{} $\pm$ 0\
& min & 20 & 11 & 9 & 19 & 8 & 8 & 8 & [7]{}\
& mean & 27 $\pm$ 3 & 20 $\pm$ 8 & 13 $\pm$ 2 & 19 $\pm$ 0 & 8 $\pm$ 0 & 8 $\pm$ 0 & 8 $\pm$ 0 & [7]{} $\pm$ 0\
& min & 54 & 26 & 26 & 48 & 20 & [19]{} & [19]{} & 20\
& mean & 61 $\pm$ 2 & 40 $\pm$ 7 & 33 $\pm$ 5 & 48 $\pm$ 0 & 20 $\pm$ 0 & [19]{} $\pm$ 0 & [19]{} $\pm$ 0 & 20 $\pm$ 0\
& min & 42 & 24 & 25 & 45 & 21 & 20 & 21 & [18]{}\
& mean & 48 $\pm$ 2 & 40 $\pm$ 9 & 32 $\pm$ 5 & 45 $\pm$ 0 & 21 $\pm$ 0 & 20 $\pm$ 0 & 21 $\pm$ 0 & [18]{} $\pm$ 0\
& min & 372 & 361 & 341 & 409 & 249 & 250 & 249 & [244]{}\
& mean & 396 $\pm$ 8 & 463 $\pm$ 58 & 450 $\pm$ 49 & 409 $\pm$ 0 & 249 $\pm$ 0 & 250 $\pm$ 0 & 249 $\pm$ 0 & [244]{} $\pm$ 0\
& min & 771 & 749 & 720 & 827 & 632 & [629]{} & 636 & [629]{}\
& mean & 814 $\pm$ 12 & 1246 $\pm$ 463 & 1237 $\pm$ 468 & 827 $\pm$ 0 & 632 $\pm$ 0 & [629]{} $\pm$ 0 & 636 $\pm$ 0 & [629]{} $\pm$ 0\
& min & 26 & 9 & 9 & 18 & 8 & 8 & [7]{} & [7]{}\
& mean & 34 $\pm$ 4 & 28 $\pm$ 23 & 16 $\pm$ 6 & 18 $\pm$ 0 & 8 $\pm$ 0 & 8 $\pm$ 0 & [7]{} $\pm$ 0 & [7]{} $\pm$ 0\
& min & 218965 & 212238 & 210387 & 221163 & 145444 & 124958 & 144658 & [122528]{}\
& mean & 223003 $\pm$ 1406 & 224579 $\pm$ 5416 & 223177 $\pm$ 4953 & 221163 $\pm$ 0 & 145444 $\pm$ 0 & 124958 $\pm$ 0 & 144658 $\pm$ 0 & [122528]{} $\pm$ 0\
& min & 7763 & 2637 & 2458 & 4816 & 2050 & 2116 & 1919 & [1835]{}\
& mean & 8057 $\pm$ 98 & 4825 $\pm$ 1432 & 3561 $\pm$ 747 & 4816 $\pm$ 0 & 2050 $\pm$ 0 & 2116 $\pm$ 0 & 1919 $\pm$ 0 & [1835]{} $\pm$ 0\
& min & 7100 & 4203 & 4158 & 5632 & 3456 & 3101 & 3231 & [2995]{}\
& mean & 7225 $\pm$ 30 & 4532 $\pm$ 165 & 4501 $\pm$ 176 & 5632 $\pm$ 0 & 3456 $\pm$ 0 & 3101 $\pm$ 0 & 3231 $\pm$ 0 & [2995]{} $\pm$ 0\
& min & 4343 & 3348 & 3296 & 4361 & 3056 & 2927 & 3060 & [2923]{}\
& mean & 4392 $\pm$ 13 & 5525 $\pm$ 1816 & 5346 $\pm$ 1672 & 4361 $\pm$ 0 & 3056 $\pm$ 0 & 2927 $\pm$ 0 & 3060 $\pm$ 0 & [2923]{} $\pm$ 0\
& min & 4416 & 5205 & 5247 & 4485 & 3354 & 3266 & 3315 & [3180]{}\
& mean & 4475 $\pm$ 25 & 5693 $\pm$ 315 & 5758 $\pm$ 283 & 4485 $\pm$ 0 & 3354 $\pm$ 0 & 3266 $\pm$ 0 & 3315 $\pm$ 0 & [3180]{} $\pm$ 0\
& min & 53508 & 56841 & 56822 & 54629 & 37334 & 37142 & 37282 & [36375]{}\
& mean & 54312 $\pm$ 244 & 82411 $\pm$ 14943 & 75532 $\pm$ 12276 & 54629 $\pm$ 0 & 37334 $\pm$ 0 & 37142 $\pm$ 0 & 37282 $\pm$ 0 & [36375]{} $\pm$ 0\
& min & 25466 & 25492 & 24404 & 25291 & 17476 & 15714 & 17504 & [15118]{}\
& mean & 25811 $\pm$ 99 & 28596 $\pm$ 1550 & 27614 $\pm$ 1499 & 25291 $\pm$ 0 & 17476 $\pm$ 0 & 15714 $\pm$ 0 & 17504 $\pm$ 0 & [15118]{} $\pm$ 0\
& min & 633 & 275 & 250 & 635 & 300 & 230 & 232 & [222]{}\
& mean & 648 $\pm$ 6 & 423 $\pm$ 74 & 372 $\pm$ 72 & 635 $\pm$ 0 & 300 $\pm$ 0 & 230 $\pm$ 0 & 232 $\pm$ 0 & [222]{} $\pm$ 0\
& min & 152 & 144 & 141 & 156 & 124 & 122 & 123 & [121]{}\
& mean & 156 $\pm$ 1 & 216 $\pm$ 44 & 219 $\pm$ 61 & 156 $\pm$ 0 & 124 $\pm$ 0 & 122 $\pm$ 0 & 123 $\pm$ 0 & [121]{} $\pm$ 0\
& min & 1788 & 438 & 328 & 1818 & 316 & 309 & 276 & [268]{}\
& mean & 1806 $\pm$ 6 & 946 $\pm$ 290 & 494 $\pm$ 115 & 1818 $\pm$ 0 & 316 $\pm$ 0 & 309 $\pm$ 0 & 276 $\pm$ 0 & [268]{} $\pm$ 0\
& min & 834 & 873 & 881 & 772 & 782 & 783 & 792 & [765]{}\
& mean & 838 $\pm$ 1 & 1186 $\pm$ 386 & 1124 $\pm$ 244 & 772 $\pm$ 0 & 782 $\pm$ 0 & 783 $\pm$ 0 & 792 $\pm$ 0 & [765]{} $\pm$ 0\
& min & 269 & 295 & 297 & 277 & 232 & 222 & 225 & [214]{}\
& mean & 281 $\pm$ 4 & 384 $\pm$ 88 & 413 $\pm$ 159 & 277 $\pm$ 0 & 232 $\pm$ 0 & 222 $\pm$ 0 & 225 $\pm$ 0 & [214]{} $\pm$ 0\
& min & 10976 & 11834 & 11829 & 11004 & 8517 & 7805 & 8706 & [7802]{}\
& mean & 11082 $\pm$ 34 & 14814 $\pm$ 1496 & 14435 $\pm$ 1276 & 11004 $\pm$ 0 & 8517 $\pm$ 0 & 7805 $\pm$ 0 & 8706 $\pm$ 0 & [7802]{} $\pm$ 0\
& min & 719 & 473 & 449 & 733 & 386 & 361 & 364 & [351]{}\
& mean & 729 $\pm$ 4 & 601 $\pm$ 59 & 567 $\pm$ 64 & 733 $\pm$ 0 & 386 $\pm$ 0 & 361 $\pm$ 0 & 364 $\pm$ 0 & [351]{} $\pm$ 0\
& min & 78 & 76 & 70 & 87 & 51 & 53 & [50]{} & 51\
& mean & 87 $\pm$ 3 & 113 $\pm$ 22 & 101 $\pm$ 20 & 87 $\pm$ 0 & 51 $\pm$ 0 & 53 $\pm$ 0 & [50]{} $\pm$ 0 & 51 $\pm$ 0\
& min & 144 & 89 & 83 & 115 & 77 & [63]{} & 73 & [63]{}\
& mean & 149 $\pm$ 2 & 110 $\pm$ 8 & 101 $\pm$ 9 & 115 $\pm$ 0 & 77 $\pm$ 0 & [63]{} $\pm$ 0 & 73 $\pm$ 0 & [63]{} $\pm$ 0\

[c|c|r|r|r|r|r|r|r|r]{} & & `F` & `M` & `K` & `X` & `V` & `P` & `OV` & `OP`\
& min & [21]{} & 22 & [21]{} & 25 & [21]{} & [21]{} & [21]{} & [21]{}\
& mean & 23 $\pm$ 1 & 22 $\pm$ 1 & 22 $\pm$ 0 & 25 $\pm$ 0 & [21]{} $\pm$ 0 & [21]{} $\pm$ 0 & [21]{} $\pm$ 0 & [21]{} $\pm$ 0\
& min & [239]{} & [239]{} & [239]{} & [239]{} & [239]{} & [239]{} & [239]{} & [239]{}\
& mean & [239]{} $\pm$ 0 & [239]{} $\pm$ 0 & [239]{} $\pm$ 0 & [239]{} $\pm$ 0 & [239]{} $\pm$ 0 & [239]{} $\pm$ 0 & [239]{} $\pm$ 0 & [239]{} $\pm$ 0\
& min & [7]{} & [7]{} & [7]{} & [7]{} & [7]{} & [7]{} & 8 & [7]{}\
& mean & 8 $\pm$ 1 & 9 $\pm$ 1 & 8 $\pm$ 1 & [7]{} $\pm$ 0 & [7]{} $\pm$ 0 & [7]{} $\pm$ 0 & 8 $\pm$ 0 & [7]{} $\pm$ 0\
& min & [17]{} & [17]{} & [17]{} & 19 & [17]{} & 18 & 18 & 18\
& mean & 19 $\pm$ 1 & 19 $\pm$ 2 & 19 $\pm$ 1 & 19 $\pm$ 0 & [17]{} $\pm$ 0 & 18 $\pm$ 0 & 18 $\pm$ 0 & 18 $\pm$ 0\
& min & [18]{} & [18]{} & [18]{} & 23 & 19 & 19 & 20 & [18]{}\
& mean & 20 $\pm$ 1 & 21 $\pm$ 2 & 20 $\pm$ 2 & 23 $\pm$ 0 & 19 $\pm$ 0 & 19 $\pm$ 0 & 20 $\pm$ 0 & [18]{} $\pm$ 0\
& min & [243]{} & [243]{} & [243]{} & 249 & 248 & [243]{} & 248 & [243]{}\
& mean & 252 $\pm$ 8 & 252 $\pm$ 8 & 252 $\pm$ 8 & 249 $\pm$ 0 & 248 $\pm$ 0 & [243]{} $\pm$ 0 & 248 $\pm$ 0 & [243]{} $\pm$ 0\
& min & [629]{} & [629]{} & [629]{} & 826 & [629]{} & [629]{} & [629]{} & [629]{}\
& mean & [629]{} $\pm$ 0 & 643 $\pm$ 50 & 641 $\pm$ 47 & 826 $\pm$ 0 & [629]{} $\pm$ 0 & [629]{} $\pm$ 0 & [629]{} $\pm$ 0 & [629]{} $\pm$ 0\
& min & [7]{} & [7]{} & [7]{} & [7]{} & [7]{} & [7]{} & [7]{} & [7]{}\
& mean & 8 $\pm$ 1 & 8 $\pm$ 2 & [7]{} $\pm$ 1 & [7]{} $\pm$ 0 & [7]{} $\pm$ 0 & [7]{} $\pm$ 0 & [7]{} $\pm$ 0 & [7]{} $\pm$ 0\
& min & 117872 & 117764 & [117710]{} & 135818 & 118495 & 118386 & 118033 & 119326\
& mean & 119650 $\pm$ 945 & 119625 $\pm$ 947 & 119536 $\pm$ 934 & 135818 $\pm$ 0 & 118495 $\pm$ 0 & 118386 $\pm$ 0 & [118033]{} $\pm$ 0 & 119326 $\pm$ 0\
& min & [1742]{} & [1742]{} & [1742]{} & [1742]{} & [1742]{} & [1742]{} & [1742]{} & [1742]{}\
& mean & [1742]{} $\pm$ 0 & [1742]{} $\pm$ 0 & 1744 $\pm$ 28 & [1742]{} $\pm$ 0 & [1742]{} $\pm$ 0 & [1742]{} $\pm$ 0 & [1742]{} $\pm$ 0 & [1742]{} $\pm$ 0\
& min & 2723 & 2718 & [2716]{} & 2749 & 2735 & 2745 & 2734 & 2747\
& mean & 2772 $\pm$ 29 & 2757 $\pm$ 19 & 2751 $\pm$ 19 & 2749 $\pm$ 0 & 2735 $\pm$ 0 & 2745 $\pm$ 0 & [2734]{} $\pm$ 0 & 2747 $\pm$ 0\
& min & [2923]{} & [2923]{} & [2923]{} & [2923]{} & [2923]{} & [2923]{} & [2923]{} & [2923]{}\
& mean & [2923]{} $\pm$ 0 & [2923]{} $\pm$ 0 & [2923]{} $\pm$ 0 & [2923]{} $\pm$ 0 & [2923]{} $\pm$ 0 & [2923]{} $\pm$ 0 & [2923]{} $\pm$ 0 & [2923]{} $\pm$ 0\
& min & [3127]{} & 3128 & 3128 & 3316 & 3137 & 3214 & 3143 & 3153\
& mean & 3166 $\pm$ 31 & 3172 $\pm$ 29 & 3173 $\pm$ 35 & 3316 $\pm$ 0 & [3137]{} $\pm$ 0 & 3214 $\pm$ 0 & 3143 $\pm$ 0 & 3153 $\pm$ 0\
& min & [36373]{} & [36373]{} & [36373]{} & [36373]{} & [36373]{} & [36373]{} & [36373]{} & [36373]{}\
& mean & 37296 $\pm$ 1902 & 37163 $\pm$ 1338 & 37058 $\pm$ 1626 & [36373]{} $\pm$ 0 & [36373]{} $\pm$ 0 & [36373]{} $\pm$ 0 & [36373]{} $\pm$ 0 & [36373]{} $\pm$ 0\
& min & [14559]{} & [14559]{} & [14559]{} & 14679 & 14581 & 14807 & 14581 & 14650\
& mean & 14687 $\pm$ 216 & 14752 $\pm$ 236 & 14747 $\pm$ 245 & 14679 $\pm$ 0 & [14581]{} $\pm$ 0 & 14807 $\pm$ 0 & [14581]{} $\pm$ 0 & 14650 $\pm$ 0\
& min & [215]{} & [215]{} & [215]{} & 230 & 227 & [215]{} & 229 & 216\
& mean & 217 $\pm$ 4 & 216 $\pm$ 2 & 220 $\pm$ 7 & 230 $\pm$ 0 & 227 $\pm$ 0 & [215]{} $\pm$ 0 & 229 $\pm$ 0 & 216 $\pm$ 0\
& min & [121]{} & [121]{} & [121]{} & [121]{} & [121]{} & [121]{} & [121]{} & [121]{}\
& mean & [121]{} $\pm$ 0 & 122 $\pm$ 5 & 122 $\pm$ 5 & [121]{} $\pm$ 0 & [121]{} $\pm$ 0 & [121]{} $\pm$ 0 & [121]{} $\pm$ 0 & [121]{} $\pm$ 0\
& min & [235]{} & [235]{} & [235]{} & 726 & [235]{} & 274 & 274 & [235]{}\
& mean & 317 $\pm$ 46 & 272 $\pm$ 23 & 260 $\pm$ 31 & 726 $\pm$ 0 & [235]{} $\pm$ 0 & 274 $\pm$ 0 & 274 $\pm$ 0 & [235]{} $\pm$ 0\
& min & [765]{} & [765]{} & [765]{} & [765]{} & 778 & 778 & 778 & [765]{}\
& mean & 778 $\pm$ 3 & 779 $\pm$ 14 & 785 $\pm$ 19 & [765]{} $\pm$ 0 & 778 $\pm$ 0 & 778 $\pm$ 0 & 778 $\pm$ 0 & [765]{} $\pm$ 0\
& min & [214]{} & [214]{} & [214]{} & [214]{} & [214]{} & [214]{} & [214]{} & [214]{}\
& mean & [214]{} $\pm$ 0 & 215 $\pm$ 5 & [214]{} $\pm$ 0 & [214]{} $\pm$ 0 & [214]{} $\pm$ 0 & [214]{} $\pm$ 0 & [214]{} $\pm$ 0 & [214]{} $\pm$ 0\
& min & [7772]{} & [7772]{} & [7772]{} & [7772]{} & 7774 & 7774 & 7774 & [7772]{}\
& mean & 7799 $\pm$ 93 & 7821 $\pm$ 124 & 7831 $\pm$ 140 & [7772]{} $\pm$ 0 & 7774 $\pm$ 0 & 7774 $\pm$ 0 & 7774 $\pm$ 0 & [7772]{} $\pm$ 0\
& min & [334]{} & [334]{} & [334]{} & 399 & 335 & [334]{} & 335 & 335\
& mean & 335 $\pm$ 1 & 336 $\pm$ 3 & 336 $\pm$ 3 & 399 $\pm$ 0 & 335 $\pm$ 0 & [334]{} $\pm$ 0 & 335 $\pm$ 0 & 335 $\pm$ 0\
& min & [49]{} & [49]{} & [49]{} & 63 & [49]{} & [49]{} & [49]{} & [49]{}\
& mean & [49]{} $\pm$ 0 & [49]{} $\pm$ 2 & [49]{} $\pm$ 2 & 63 $\pm$ 0 & [49]{} $\pm$ 0 & [49]{} $\pm$ 0 & [49]{} $\pm$ 0 & [49]{} $\pm$ 0\
& min & [58]{} & [58]{} & [58]{} & 61 & 69 & 59 & 69 & 59\
& mean & 64 $\pm$ 6 & 69 $\pm$ 6 & 63 $\pm$ 5 & 61 $\pm$ 0 & 69 $\pm$ 0 & [59]{} $\pm$ 0 & 69 $\pm$ 0 & [59]{} $\pm$ 0\

[c|c|r|r|r|r|r|r|r|r]{} & & `F` & `M` & `K` & `X` & `V` & `P` & `OV` & `OP`\
& min & 59 & 29 & [22]{} & 100 & 50 & 43 & 31 & 38\
& mean & 90 $\pm$ 11 & 68 $\pm$ 19 & 48 $\pm$ 17 & 100 $\pm$ 0 & 50 $\pm$ 0 & 43 $\pm$ 0 & [31]{} $\pm$ 0 & 38 $\pm$ 0\
& min & 4 & 4 & 4 & 8 & 4 & 4 & 5 & [3]{}\
& mean & 5 $\pm$ 0 & 6 $\pm$ 1 & 6 $\pm$ 1 & 8 $\pm$ 0 & 4 $\pm$ 0 & 4 $\pm$ 0 & 5 $\pm$ 0 & [3]{} $\pm$ 0\
& min & 5 & 5 & [3]{} & 7 & 6 & 7 & 5 & [3]{}\
& mean & 10 $\pm$ 2 & 9 $\pm$ 3 & 7 $\pm$ 2 & 7 $\pm$ 0 & 6 $\pm$ 0 & 7 $\pm$ 0 & 5 $\pm$ 0 & [3]{} $\pm$ 0\
& min & 8 & [6]{} & 7 & 14 & 17 & 7 & 12 & [6]{}\
& mean & 15 $\pm$ 6 & 15 $\pm$ 5 & 14 $\pm$ 5 & 14 $\pm$ 0 & 17 $\pm$ 0 & 7 $\pm$ 0 & 12 $\pm$ 0 & [6]{} $\pm$ 0\
& min & 6 & 5 & [4]{} & 6 & 6 & 5 & 9 & [4]{}\
& mean & 10 $\pm$ 3 & 11 $\pm$ 4 & 9 $\pm$ 3 & 6 $\pm$ 0 & 6 $\pm$ 0 & 5 $\pm$ 0 & 9 $\pm$ 0 & [4]{} $\pm$ 0\
& min & 5 & 5 & 5 & 12 & [3]{} & 4 & [3]{} & 4\
& mean & 11 $\pm$ 3 & 10 $\pm$ 3 & 9 $\pm$ 3 & 12 $\pm$ 0 & [3]{} $\pm$ 0 & 4 $\pm$ 0 & [3]{} $\pm$ 0 & 4 $\pm$ 0\
& min & 4 & 3 & 3 & 3 & 3 & 3 & 4 & [2]{}\
& mean & 5 $\pm$ 1 & 7 $\pm$ 2 & 8 $\pm$ 2 & 3 $\pm$ 0 & 3 $\pm$ 0 & 3 $\pm$ 0 & 4 $\pm$ 0 & [2]{} $\pm$ 0\
& min & 4 & 4 & [3]{} & 6 & 4 & 4 & 6 & [3]{}\
& mean & 9 $\pm$ 3 & 8 $\pm$ 2 & 7 $\pm$ 3 & 6 $\pm$ 0 & 4 $\pm$ 0 & 4 $\pm$ 0 & 6 $\pm$ 0 & [3]{} $\pm$ 0\
& min & 18 & 19 & [14]{} & 32 & 82 & 45 & 59 & 39\
& mean & 43 $\pm$ 15 & 40 $\pm$ 14 & 36 $\pm$ 13 & [32]{} $\pm$ 0 & 82 $\pm$ 0 & 45 $\pm$ 0 & 59 $\pm$ 0 & 39 $\pm$ 0\
& min & 12 & 12 & 11 & 53 & 28 & 27 & [10]{} & 23\
& mean & 28 $\pm$ 8 & 33 $\pm$ 10 & 29 $\pm$ 9 & 53 $\pm$ 0 & 28 $\pm$ 0 & 27 $\pm$ 0 & [10]{} $\pm$ 0 & 23 $\pm$ 0\
& min & 39 & 37 & [31]{} & 73 & 100 & 83 & 67 & 85\
& mean & 75 $\pm$ 19 & 72 $\pm$ 18 & 76 $\pm$ 18 & 73 $\pm$ 0 & 100 $\pm$ 0 & 83 $\pm$ 0 & [67]{} $\pm$ 0 & 85 $\pm$ 0\
& min & [9]{} & 10 & 10 & 35 & 25 & 10 & 26 & [9]{}\
& mean & 18 $\pm$ 5 & 18 $\pm$ 5 & 20 $\pm$ 6 & 35 $\pm$ 0 & 25 $\pm$ 0 & 10 $\pm$ 0 & 26 $\pm$ 0 & [9]{} $\pm$ 0\
& min & [13]{} & 14 & [13]{} & 37 & 14 & 25 & 17 & [13]{}\
& mean & 29 $\pm$ 10 & 30 $\pm$ 10 & 30 $\pm$ 11 & 37 $\pm$ 0 & 14 $\pm$ 0 & 25 $\pm$ 0 & 17 $\pm$ 0 & [13]{} $\pm$ 0\
& min & 4 & 4 & 4 & 8 & 5 & 5 & 5 & [3]{}\
& mean & 6 $\pm$ 1 & 6 $\pm$ 1 & 6 $\pm$ 1 & 8 $\pm$ 0 & 5 $\pm$ 0 & 5 $\pm$ 0 & 5 $\pm$ 0 & [3]{} $\pm$ 0\
& min & [12]{} & [12]{} & 14 & 36 & 16 & 22 & 15 & 59\
& mean & 31 $\pm$ 13 & 33 $\pm$ 14 & 30 $\pm$ 10 & 36 $\pm$ 0 & 16 $\pm$ 0 & 22 $\pm$ 0 & [15]{} $\pm$ 0 & 59 $\pm$ 0\
& min & 14 & 12 & [9]{} & 27 & 25 & 15 & 19 & 16\
& mean & 27 $\pm$ 9 & 31 $\pm$ 14 & 24 $\pm$ 11 & 27 $\pm$ 0 & 25 $\pm$ 0 & 15 $\pm$ 0 & 19 $\pm$ 0 & [16]{} $\pm$ 0\
& min & 8 & [4]{} & [4]{} & 19 & 11 & 10 & 8 & 5\
& mean & 13 $\pm$ 2 & 12 $\pm$ 5 & 11 $\pm$ 4 & 19 $\pm$ 0 & 11 $\pm$ 0 & 10 $\pm$ 0 & 8 $\pm$ 0 & [5]{} $\pm$ 0\
& min & 10 & 8 & 9 & 22 & 30 & 16 & [7]{} & 27\
& mean & 25 $\pm$ 9 & 25 $\pm$ 11 & 23 $\pm$ 9 & 22 $\pm$ 0 & 30 $\pm$ 0 & 16 $\pm$ 0 & [7]{} $\pm$ 0 & 27 $\pm$ 0\
& min & 6 & [3]{} & [3]{} & 5 & 9 & 10 & 12 & [3]{}\
& mean & 12 $\pm$ 5 & 14 $\pm$ 6 & 12 $\pm$ 7 & 5 $\pm$ 0 & 9 $\pm$ 0 & 10 $\pm$ 0 & 12 $\pm$ 0 & [3]{} $\pm$ 0\
& min & 6 & 5 & 4 & 7 & 7 & 7 & 6 & [2]{}\
& mean & 8 $\pm$ 1 & 8 $\pm$ 2 & 7 $\pm$ 2 & 7 $\pm$ 0 & 7 $\pm$ 0 & 7 $\pm$ 0 & 6 $\pm$ 0 & [2]{} $\pm$ 0\
& min & 9 & 11 & 11 & 24 & 20 & [8]{} & 21 & 19\
& mean & 20 $\pm$ 8 & 22 $\pm$ 8 & 20 $\pm$ 8 & 24 $\pm$ 0 & 20 $\pm$ 0 & [8]{} $\pm$ 0 & 21 $\pm$ 0 & 19 $\pm$ 0\
& min & [15]{} & 17 & 18 & 20 & 62 & 50 & 33 & 49\
& mean & 41 $\pm$ 20 & 42 $\pm$ 18 & 40 $\pm$ 18 & [20]{} $\pm$ 0 & 62 $\pm$ 0 & 50 $\pm$ 0 & 33 $\pm$ 0 & 49 $\pm$ 0\
& min & [4]{} & [4]{} & [4]{} & 9 & 5 & 7 & 5 & 5\
& mean & 7 $\pm$ 2 & 8 $\pm$ 3 & 7 $\pm$ 3 & 9 $\pm$ 0 & [5]{} $\pm$ 0 & 7 $\pm$ 0 & [5]{} $\pm$ 0 & [5]{} $\pm$ 0\
& min & [13]{} & [13]{} & 15 & 73 & 33 & 21 & 28 & 32\
& mean & 29 $\pm$ 10 & 31 $\pm$ 11 & 29 $\pm$ 10 & 73 $\pm$ 0 & 33 $\pm$ 0 & [21]{} $\pm$ 0 & 28 $\pm$ 0 & 32 $\pm$ 0\

[c|c|r|r|r|r|r|r|r|r]{} & & `F` & `M` & `K` & `X` & `V` & `P` & `OV` & `OP`\
& min & 20 & 10 & 10 & 40 & 20 & 20 & 20 & 10\
& mean & 43 $\pm$ 7 & 33 $\pm$ 10 & 24 $\pm$ 9 & 40 $\pm$ 0 & 20 $\pm$ 0 & 20 $\pm$ 0 & 20 $\pm$ 0 & 10 $\pm$ 0\
& min & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
& mean & 0 $\pm$ 1 & 0 $\pm$ 1 & 0 $\pm$ 2 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0\
& min & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
& mean & 0 $\pm$ 1 & 0 $\pm$ 1 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0\
& min & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
& mean & 0 $\pm$ 2 & 0 $\pm$ 1 & 0 $\pm$ 2 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0\
& min & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
& mean & 0 $\pm$ 1 & 0 $\pm$ 1 & 0 $\pm$ 1 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0\
& min & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
& mean & 0 $\pm$ 1 & 0 $\pm$ 2 & 1 $\pm$ 2 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0\
& min & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
& mean & 0 $\pm$ 2 & 0 $\pm$ 2 & 0 $\pm$ 2 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0\
& min & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
& mean & 0 $\pm$ 0 & 0 $\pm$ 1 & 0 $\pm$ 1 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0\
& min & 1690 & 1630 & 1580 & 2570 & 6920 & 12160 & 5040 & 12460\
& mean & 3691 $\pm$ 1229 & 3370 $\pm$ 1178 & 3397 $\pm$ 1055 & 2570 $\pm$ 0 & 6920 $\pm$ 0 & 12160 $\pm$ 0 & 5040 $\pm$ 0 & 12460 $\pm$ 0\
& min & 0 & 10 & 10 & 50 & 30 & 50 & 10 & 50\
& mean & 30 $\pm$ 9 & 32 $\pm$ 11 & 32 $\pm$ 10 & 50 $\pm$ 0 & 30 $\pm$ 0 & 50 $\pm$ 0 & 10 $\pm$ 0 & 50 $\pm$ 0\
& min & 380 & 350 & 320 & 670 & 960 & 790 & 620 & 810\
& mean & 710 $\pm$ 174 & 673 $\pm$ 168 & 724 $\pm$ 166 & 670 $\pm$ 0 & 960 $\pm$ 0 & 790 $\pm$ 0 & 620 $\pm$ 0 & 810 $\pm$ 0\
& min & 10 & 10 & 10 & 40 & 20 & 10 & 30 & 20\
& mean & 19 $\pm$ 7 & 19 $\pm$ 7 & 21 $\pm$ 6 & 40 $\pm$ 0 & 20 $\pm$ 0 & 10 $\pm$ 0 & 30 $\pm$ 0 & 20 $\pm$ 0\
& min & 20 & 20 & 20 & 60 & 20 & 80 & 30 & 40\
& mean & 52 $\pm$ 17 & 52 $\pm$ 17 & 57 $\pm$ 20 & 60 $\pm$ 0 & 20 $\pm$ 0 & 80 $\pm$ 0 & 30 $\pm$ 0 & 40 $\pm$ 0\
& min & 10 & 10 & 10 & 30 & 30 & 210 & 20 & 200\
& mean & 22 $\pm$ 7 & 21 $\pm$ 5 & 25 $\pm$ 8 & 30 $\pm$ 0 & 30 $\pm$ 0 & 210 $\pm$ 0 & 20 $\pm$ 0 & 200 $\pm$ 0\
& min & 50 & 50 & 50 & 140 & 60 & 140 & 70 & 280\
& mean & 122 $\pm$ 50 & 126 $\pm$ 53 & 124 $\pm$ 41 & 140 $\pm$ 0 & 60 $\pm$ 0 & 140 $\pm$ 0 & 70 $\pm$ 0 & 280 $\pm$ 0\
& min & 0 & 0 & 0 & 10 & 10 & 10 & 10 & 10\
& mean & 9 $\pm$ 5 & 11 $\pm$ 6 & 8 $\pm$ 5 & 10 $\pm$ 0 & 10 $\pm$ 0 & 10 $\pm$ 0 & 10 $\pm$ 0 & 10 $\pm$ 0\
& min & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
& mean & 0 $\pm$ 2 & 1 $\pm$ 2 & 1 $\pm$ 2 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0\
& min & 40 & 30 & 30 & 50 & 100 & 70 & 30 & 100\
& mean & 87 $\pm$ 27 & 87 $\pm$ 37 & 79 $\pm$ 26 & 50 $\pm$ 0 & 100 $\pm$ 0 & 70 $\pm$ 0 & 30 $\pm$ 0 & 100 $\pm$ 0\
& min & 0 & 0 & 0 & 10 & 10 & 30 & 10 & 20\
& mean & 11 $\pm$ 5 & 12 $\pm$ 6 & 11 $\pm$ 8 & 10 $\pm$ 0 & 10 $\pm$ 0 & 30 $\pm$ 0 & 10 $\pm$ 0 & 20 $\pm$ 0\
& min & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
& mean & 0 $\pm$ 2 & 0 $\pm$ 2 & 0 $\pm$ 2 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0\
& min & 10 & 10 & 10 & 20 & 20 & 20 & 20 & 30\
& mean & 21 $\pm$ 9 & 20 $\pm$ 8 & 20 $\pm$ 8 & 20 $\pm$ 0 & 20 $\pm$ 0 & 20 $\pm$ 0 & 20 $\pm$ 0 & 30 $\pm$ 0\
& min & 10 & 20 & 20 & 10 & 60 & 50 & 40 & 40\
& mean & 40 $\pm$ 19 & 40 $\pm$ 18 & 38 $\pm$ 17 & 10 $\pm$ 0 & 60 $\pm$ 0 & 50 $\pm$ 0 & 40 $\pm$ 0 & 40 $\pm$ 0\
& min & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
& mean & 0 $\pm$ 1 & 0 $\pm$ 1 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0\
& min & 0 & 0 & 0 & 10 & 0 & 0 & 10 & 0\
& mean & 6 $\pm$ 5 & 6 $\pm$ 5 & 6 $\pm$ 5 & 10 $\pm$ 0 & 0 $\pm$ 0 & 0 $\pm$ 0 & 10 $\pm$ 0 & 0 $\pm$ 0\

   Statistic   Criterion           `F`      `M`         `K`     `X`     `V`     `P`    `OV`        `OP`
  ----------- ------------ ----------- -------- ----------- ------- ------- ------- ------- -----------
      Min      Init. SSE         2.968    1.418       1.348   2.184   1.107   1.043   1.067   [1.002]{}
               Final SSE         1.001    1.003   [1.000]{}   1.163   1.019   1.018   1.031       1.005
               \# Iters.         1.488    1.284   [1.183]{}   2.978   2.469   2.013   2.034       1.793
     Mean      Init. SSE         3.250    2.171       1.831   2.184   1.107   1.043   1.067   [1.002]{}
               Final SSE         1.047    1.049       1.032   1.161   1.017   1.016   1.029   [1.003]{}
               \# Iters.         2.466    2.528       2.314   2.581   2.057   1.715   1.740   [1.481]{}
     Stdev     Init. SSE     [1.000]{}   13.392      12.093       –       –       –       –           –
               Final SSE     [1.013]{}    1.239       1.172       –       –       –       –           –
               \# Iters.     [1.000]{}    1.166       1.098       –       –       –       –           –

  : \[tab\_summary\] Overall performance comparison of the initialization methods

   Criterion     Worse than `V`   Same as `V`   Better than `V`
  ------------ ---------------- ------------- -----------------
   Init. SSE                  6             3                15
   Final SSE                  6            16                 2
   \# Iters.                  8             3                13

  : \[tab\_rel\_var\] Performance of Otsu Var-Part relative to Var-Part (`V`)

   Criterion     Worse than `P`   Same as `P`   Better than `P`
  ------------ ---------------- ------------- -----------------
   Init. SSE                  1             2                21
   Final SSE                  4            14                 6
   \# Iters.                  6             1                17

  : \[tab\_rel\_pca\] Performance of Otsu PCA-Part relative to PCA-Part (`P`)

\
\

[^1]: Given a set of $N$ points in a metric space, the goal of $K$-center clustering is to find $K$ representative points (centers) such that the maximum distance of a point to a center is minimized. Given a minimization problem, a *$2$-approximation* algorithm is one that finds a solution whose cost is at most twice the cost of the optimal solution.

[^2]: The first center is chosen as the centroid of the data set.

[^3]: Due to outliers, the ‘median’ statistic rather than the ‘mean’ was used to summarize the normalized standard deviation values.
