# An initialization scheme for supervised K-means

Vincent Lemaire, Oumaima Alaoui Ismaili, Antoine Cornuéjols

## ► To cite this version:

Vincent Lemaire, Oumaima Alaoui Ismaili, Antoine Cornuéjols. An initialization scheme for supervised K-means. IJCNN 2015 International Joint Conference on Neural Networks, Jul 2015, Killarney, Ireland. 10.1109/IJCNN.2015.7280555. [hal-01558021](https://hal.science/hal-01558021)

HAL Id: hal-01558021

https://hal.science/hal-01558021

Submitted on 2 Jun 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# An Initialization Scheme for Supervized K-means

Vincent Lemaire, Oumaima Alaoui Ismaili, Antoine Cornuéjols

***Abstract***—Over the last years, researchers have focused their attention on a new approach, supervised clustering, that combines the main characteristics of both traditional clustering and supervised classification tasks. Motivated by the importance of the initialization in the traditional clustering context, this paper explores to what extent supervised initialization step could help traditional clustering to obtain better performances on supervised clustering tasks. This paper reports experiments which show that the simple proposed approach yields a good solution together with significant reduction of the computational cost.

## I. INTRODUCTION

To discover the internal structure of huge collections of data, clustering algorithms are quite useful. These algorithms aim to identify groups (or clusters) in a manner that instances inside each one share the same characteristics (see Figure 1. a). This clustering problem has motivated a huge body of work and has resulted in a large number of algorithms (see e.g. [1, 2]).

However, when an additional information (target class) is given, the classification algorithms are the most used (see Figure 1. b); Their principal objective is to learn the link between a set of input features and the output feature (target class) in the goal to predict class membership for new instances.

Recently, researchers have focused their attention on the combination of characteristics of both clustering and classification tasks. The goal behind this combination is to find the internal structure of the target classes. This research has given birth to a new approach called *Supervised clustering* (e.g. see [3, 4]). It aims to elaborate or modify clustering algorithms to find clusters where instances inside each cluster share the same characteristics and they are likely to have the same class label. The generated clusters are then labeled with the majority class of their instances (see Figure 1. c).

Among clustering methods (see e.g [1, 2]), many partitioning approaches such as K-means [5], K-medians [6], etc require an initialization step. The choice of an appropriate method of initialization is therefore important. Indeed, such step could have an impact on the quality of the obtained solution (intra-similarity) and on the computational efficiency [7]. In addition to this, by using a good method of centers initialization, clustering algorithms need a lower number of iterations to yield an optimal result (partition having a lowest intra-inertia value). It is thus natural to ask: *Could supervised initialization method help traditional clustering algorithms to*

<figure><img src="image_2.png" /><figcaption>Fig. 1: Classification processes</figcaption></figure>

*reach a good predictive performance in a supervised clustering context?* In other words, does introducing the information given by the target class in a centers initialization step produce a good supervised clustering, meaning exhibiting high value of the Adjusted Rand Index (ARI)<fnref n="1" /> [8] while at the same time uncovering interesting clusters in the data set.

To be able to answer the question above, we present firstly a supervised initialization method for the traditional K-means algorithm. This method uses the additional information given by the target class to get an appropriate initial vector of centers. Secondly, we compare this method with other unsupervised initialization methods from the literature using both supervised and unsupervised criteria such as the ARI and the Mean Squared error (MSE) (see Section V).

The remainder of this paper is organized as follows. Section 2 presents the main idea of the *K*-means clustering algorithm. Section 3 describes briefly related works about supervised *K*-means algorithm. Section 4 presents the proposed method of initialization for the traditional *K*-means algorithm and an illustration using a toy problem. Section 5 compares the performance of the generated partitions using supervised and unsupervised initialization steps with ARI, Accuracy (ACC) and MSE on a quite variety of datasets. Finally, a conclusion with future works is presented.

Oumaima Alaoui Ismaili and Vincent Lemaire are with Orange Labs, Lannion, France (email: firstname.name@orange.com); Antoine Cornuéjols is with AgroParisTech, Paris, France (email: firstname.name@agroparistech.fr)

<footnote n="1">¹ The ARI criterion is a member of the family of the external criteria which estimate the quality in reference to an additional variable, here the target variable. It is computed by comparing the partition of the target class labels with the partition of the *K*-means algorithm.</footnote>
## II. K-MEANS-ALGORITHMS

The purpose of the partitioning algorithms is to construct a partition of *N* objects into a set of *K* clusters. These algorithms require an initialization step where seeds are chosen. The most common algorithms of this category of clustering are: *K*-means [5], *K*-medians [6], *K*-modes [9] and *K*-medoids [10]. Each of these algorithms depends on the number of clusters *K* (a priori set), the input features, the initial vector of centers (*k*₁, ..., *k*ₖ), the similarity measure and the criterion used to evaluate the quality of the partition.

The choice of one of these algorithms depends on: (i) the nature of the datasets, (ii) the desired result (mean, medoid ...,), and (iii) the complexity of the algorithm. In this paper, we are focused on one of the most widely used algorithm: The *K*-means method.

### A. *K*-means algorithm

The *K*-means algorithm (KM) improves the quality of the partition:

K-means (K, input features, number of replicates²R)

for 1 to R (Replicates) do

Initialize K cluster centroids (see Section II-B).

while The centroid vectors change do

* Associate each data instance to the closest centroid using the Euclidean distance (L2 norm)

* Update each centroid vector by computing the average of its associated instances

end
end

Output: Return the best solution among the *R* results in the sense of the Mean Squared Error (MSE).

<caption>**Algorithm 1: K-means algorithm.**</caption>

### B. Unsupervised initialization

The initialization of the cluster centers has an impact on the quality of the generated partition and also on the computational efficiency [7]. In addition to this, the choice of an inappropriate initialization method could generate adverse effects such as: (i) empty clusters, (ii) slower convergence, and (iii) a higher chance of getting stuck in a bad local minimum and thus, the need to restart the algorithm. For all of these reasons, the choice of an initialization method has been well studied in the literature (e.g. for *K*-medians in [11], for *K*-medoids in [12] and for *K*-means in [13, 14, 15]).

In this section, we present a brief overview of the most common initialization methods for the *K*-means algorithm, with an emphasis on their computational efficiency (these methods are described in [13], [14] or [15]).

* **Random [16] (RAND):** The cluster centers are chosen randomly from the data set; The complexity of this scheme is $O(K)$.

* **Splitting [17] (SPLIT):** The first center $k_1$ is chosen as the centroid of the data set. At iteration $i$ ($i \in 1, 2, ..., \log_2 K$), each of the existing $2^{i-1}$ centers is split into two new centers by subtracting and adding a fixed perturbation vector $\epsilon$, i.e. $k_j - \epsilon$ and $k_j + \epsilon$, ($j \in \{1, 2, ..., 2^{i-1}\}$). These $2^i$ new centers are then refined using the KM algorithm. The complexity of this scheme is $O(NK)$.

* **Minmax [18] (MINMAX):** The first center $k_1$ is chosen randomly and the $i$-th ($i \in \{2, 3, ..., K\}$) center $k_i$ is chosen to be the point that has the largest minimum distance to the previously selected centers, i.e. $k_1, k_2, ..., k_{i-1}$. The complexity of this scheme is $O(NK)$.

* **Density-based [19] (DENS):** The data space is partitioned uniformly into *M* cells. From each of these cells, a number (that is proportional to the number of points in this cell) of centers is chosen randomly until *K* centers are obtained. The complexity of this scheme is $O(N)$.

* **Sample (SAMPLE):** This method consists in taking a sample, $N'$, of the data set (often 10%) and in applying the *K*-means algorithm to this sample. Then to take the centers found as initial centers. The complexity of this scheme is $O(N'kq)$, where *q* is the number of iteration.

* **Kmeans++ [20] (K++):** This approach is based on four steps: (1) The first center $k_1$ is chosen randomly from instances, (2) For each data point $x$, compute $Q(x)$, the nearest prototype that has already been chosen, (3) Choose a new center from data points using the probability $\frac{Q(x)^2}{\sum_{i=1}^{n} Q(x_i)^2}$ and (4) Repeat steps 2 and 3 until *K* prototypes have been chosen. The complexity of this scheme is $O(NK)$.

## III. RELATED WORKS : SUPERVISED *K*-MEANS

Several algorithms have been developed to achieve the objective of supervised clustering (e.g. [21, 22, 23, 24, 25, 26, 27]).

In this section, we present two of the most cited methods for supervised *K*-means algorithms. These algorithms incorporate the additional information given by the target class within the algorithm (i.e. in the “while loop” of the Algorithm 1). However, to our knowledge, there are no methods which uses a *supervised* initialization step to choose the initial seeds.

Al-Harbi et al. [3] developed a *K*-means algorithm in such a way as to use it as a classifier algorithm. First of all, they replaced the Euclidean metric used in a standard *K*-means by a weighted Euclidean metric. The vector of weights is chosen in such a way as to maximize the confidence of the partitions generated by the k-means algorithm. This confidence is determined by calculating the percentage of correctly classified objects with respect to the total number of objects in the data set. In this algorithm, the number of clusters is an input.

Eick et al. [4] introduced four representative-based algorithms for supervised clustering: SRIDHCR, SPAM, TDS

<footnote n="2">² In this study, one replicate refers to the generated partition just after the convergence of the algorithm.</footnote>
and SCEC. In their experimentation, they used the first one (i.e SRIDHCR). The greedy algorithm SRIDHCR (or Single Representative Insertion/Deletion Steepest Decent Hill Climbing with Randomized Start) is mainly based on three phases. The first one is the initialization of a set of representatives that is randomly selected from the dataset. The second is the primary cluster creation phase, where instances are assigned to the cluster of their closest representative. The third one is the iteration phase where the algorithm is run *r* times: In each time 'r', the algorithm tries to improve the quality of clustering, for instance, by adding a non-representative instance or by deleting a representative instance. To measure this quality, the authors use a supervised criterion. It takes into account two points: (i) The impurity of the clustering which is defined as a percentage of misclassified observations in the different clusters and (ii) a penalty condition which is used in order to keep the lowest number of clusters. In this greedy algorithm, the number of clusters is an output.

## IV. PROPOSED METHOD: SUPERVISED INITIALIZATION

In this paper, we suggest that one way to help the traditional *K*-means in a supervised context is to integrate the target class information into the initialization process. That is, we believe that an efficient supervised initialization approach allows one to obtain a good performance in terms of (i) computational efficiency, and (ii) prediction quality. In addition to this, with such a supervised method, (i) the chance of falling in a bad local minima "in the sense of supervised clustering" is lower and (ii) the number of replicates is minimized (i.e. R in Algorithm 1). Therefore, we can obtain a good solution with only a small number of replicates. To test the validity of all these points, we propose a simple supervised initialization method.

The proposed method called **K++R** follows an "exploit and explore" mechanism: the information given by the class label is firstly exploited and then the density of the data distribution is explored. The main idea of this method is to dedicate one center per class (as a "Rochio" [28] solution). Each center is defined as the average vector of instances which have the same class label. If the predefined number of clusters (*K*) exceeds the number of classes (*C*), the initialization continues using the K-means++ [20] algorithm for the *K* − *C* remaining centers in such a way to add diversity. This initialization method could be performed just in the case<fnref n="3" /> *K* ≥ *C* since it takes into account the cardinality of data classes (*C*). The complexity of this scheme is $O((N + (K - C)N) < O(NK))$.

Clearly, this initialization approach is not suitable for a traditional clustering: it would deteriorate the quality of the generated partitions in terms of reconstruction error (the Mean Squared Error (MSE)). But, let us recall that the objective of a supervised clustering is to realize a trade-off between similarity and prediction. At this stage:

* the intra similarity "quality" is guaranteed by the standard *K*-means algorithm and measured by the MSE criterion.

* the supervised "quality" is guaranteed by the supervised initialization step (our suggestion) and measured by a suitable supervised criterion (to be defined below).

To be consistent with the definition of a supervised clustering, we select a criterion that allows one to choose the closest partition to the one given by the target class. For this, we use the Adjusted Rand Index (ARI) [8] to measure the quality of the obtained partition [29]. It measures the agreement between the generated partition for the *K*-means and the partition given by the target class.

We illustrate the standard *K*-means using both our proposed approach and the usual unsupervised initialization approaches on a toy dataset (see Figure 2). This dataset contains 510 instances, distributed among five classes (*C* = 5): 'ear left' (blue), 'ear right' (green), 'head' (red), 'shoulder' (cyan) and 'noise' (purple); Each class contains respectively 290, 100, 100, 10 and 10 instances. Here, the standard *K*-means is applied in the following conditions: L2 as a norm, mean as a centroid, Mean Squared Error (MSE) as a criterion to select the best replicates and statistical normalization (SN)<fnref n="4" /> as a preprocessing step.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Mouse dataset.</figcaption></figure>

**MSE criterion** : Using the standard K-means, the replacement of the initial center has often an impact on the quality of the generated partition.

Our supervised initialization approach requires at least an initial center per class ($K \ge C$). However, for this dataset, the initialization of a center in the minority class (i.e. 'cyan' class) could deteriorate the quality of the final solution in terms of MSE (the initial center couldn't move outside the cyan points).

Figure 3 illustrates this point: the generated partitions using the usual initialization approaches (Rand, Sample and K++) have a better performance in terms of MSE than the K++R approach where $K = C$. Note that, the difference between the MSE of K++ and K++R is only 8.9% (0.326 against 0.355) when the number of replicates is equal to 1000

<footnote n="3">³ In the context of supervised clustering there is no sense to cluster instances in *K* clusters where *K* < *C*</footnote>

<footnote n="4">⁴ This approach transforms data derived from any normal distribution into a standard normal distribution $N(0, 1)$. The formula that allows the transformation of feature $X_u$ is: $X'_u = \frac{X_u - \mu}{\sigma}$ where $\mu$ is the mean of the feature $u$, $\sigma$ is its standard deviation.</footnote>
and 1 respectively. This shows that the K++R is a faster
algorithm than the others.

<figure><img src="image_4.png" /><figcaption>Fig. 3: Mouse dataset: Reconstruction Error versus Number of replicates (K=5). The points represent the mean result obtained over 10 tries and the error bars the standard deviation ($\nu \pm \sigma$).</figcaption></figure>

**ARI criterion:** For this example, when the number of clusters is equal to the cardinality of the target class, using an unsupervised initialization approach, the chance to select more than one seed in the same class is high (especially in the majority class). Likewise, the chance to select one center in the minority class is lower. Consequently, the predictive performance of the generated partition could be deteriorated (e.g lower value of ARI).

<figure><img src="image_5.png" /><figcaption>Fig. 4: Mouse dataset: ARI versus Number of replicates (K=5). The points represent the mean result obtained over 10 tries and the error bars the standard deviation ($\nu \pm \sigma$).</figcaption></figure>

Figure 4 describes the evolution of the ARI versus the number of replicates (in the case where $K = C$) using both K++R and the usual initialization approaches. In this case, our approach is deterministic (i.e. it gives one unique value of ARI whatever the number of replicates). This result shows that, using the ARI criterion, the K++R approach is better than the other unsupervised approaches.

In the case where $K \ge C$, Figure 5 presents the evolution of the ARI versus the number of clusters. This result shows that, using the proposed approach, the optimal generated partition in terms of ARI is reached where $K = C$. Likewise, when $K > C$, the K++R has the same predictive performance 'quality' as the unsupervised approaches.

The preliminary experiment conducted on this dataset has
shown the following result: (1) the predictive performance

<figure><img src="image_6.png" /><figcaption>Fig. 5: Mouse dataset: ARI versus Number of clusters ($K$). The points represent the mean result obtained over 10 tries. The small error bars corresponding to the standard deviation ($\nu \pm \sigma$) is not visible.</figcaption></figure>

of the generated partition using the proposed initialization
method is better than the performance using the usual initial-
ization approaches (when $K = C = 5$), (2) K++R is faster
than the others approaches (reach a good performance with a
few number of replicates), and (3) unsupervised initialization
approaches are better than K++R in terms of MSE.

To further evaluate the efficiency of our proposed approach
in a supervised context, we propose an extensive comparison
with the usual initialization approaches for several bench-
mark datasets.

V. EXPERIMENTS

In this section, we present and compare the average
performance of the traditional *K*-means algorithm using both
supervised and unsupervised initialization approaches.

A. Protocol

1) *Initialization method:* To test the validity of our pro-
posal, we compare our supervised initialization approach
(K++R) to the three most popular unsupervised approaches
(see Section II-B) such as Rand (as a baseline), Sample
(which exhibits interesting performance as described in [14])
and K++ (which has theoretical foundations and a good
performance while keeping a reasonable complexity).

2) *Datasets:* To evaluate and compare the behavior of different initialization approaches in terms of their capacity to help the traditional clustering in a supervised context, we have performed tests on different datasets of the UCI repository [30], chosen for their diversity in terms of number of clusters, number of features (categorical and continuous) and number of instances (see Table I).

3) *Number of clusters:* In this paper<sup>5</sup>, we deal the case where *K* is an *input* (as in [3]): In this study, *K* is equal to the cardinality of the target class (*C*).

4) Preprocessing: In a previous paper [31], we showed that one way to help the standard K-means algorithm to reach a good predictive performance is to incorporate the additional information given by the target class in a pre-processing step.

<footnote n="5">⁵ For space place consideration, the case where *K* is an output (as in [4]) will be presented in a future publication</footnote>
<table><caption>TABLE I: The used datasets from UCI: $M_n$: Number of numerical variables; $M_c$: Number of categorical variables; $N$: Number of instances; $C$: number of Classes; Maj. acc: Baseline performance indication using a classifier based only on the majority class.</caption><thead><tr><th>Id</th><th>Name</th><th>$M_n$</th><th>$M_c$</th><th>$N$</th><th>$C$</th><th>Maj. acc.</th></tr></thead><tbody><tr><td>1</td><td>Iris</td><td>4</td><td>0</td><td>150</td><td>3</td><td>33.33</td></tr><tr><td>2</td><td>Hepatitis</td><td>6</td><td>13</td><td>155</td><td>2</td><td>79.35</td></tr><tr><td>3</td><td>Glass</td><td>10</td><td>0</td><td>214</td><td>6</td><td>35.51</td></tr><tr><td>4</td><td>Heart</td><td>10</td><td>3</td><td>270</td><td>2</td><td>55.56</td></tr><tr><td>5</td><td>Horsecolic</td><td>7</td><td>20</td><td>368</td><td>2</td><td>63.04</td></tr><tr><td>6</td><td>Soybean</td><td>0</td><td>35</td><td>376</td><td>19</td><td>13.83</td></tr><tr><td>7</td><td>Pima</td><td>8</td><td>0</td><td>768</td><td>2</td><td>65.10</td></tr><tr><td>8</td><td>Vehicle</td><td>18</td><td>0</td><td>846</td><td>4</td><td>25.77</td></tr><tr><td>9</td><td>Tictactoe</td><td>0</td><td>9</td><td>958</td><td>2</td><td>65.34</td></tr><tr><td>10</td><td>LED</td><td>7</td><td>0</td><td>1000</td><td>10</td><td>11.40</td></tr><tr><td>11</td><td>Phoneme</td><td>256</td><td>0</td><td>2254</td><td>5</td><td>25.95</td></tr><tr><td>12</td><td>Segmentation</td><td>19</td><td>0</td><td>2310</td><td>7</td><td>14.29</td></tr><tr><td>13</td><td>Abalone</td><td>7</td><td>1</td><td>4177</td><td>28</td><td>16.50</td></tr><tr><td>14</td><td>Waveform</td><td>21</td><td>0</td><td>5000</td><td>3</td><td>33.92</td></tr><tr><td>15</td><td>PenDigits</td><td>16</td><td>0</td><td>10992</td><td>10</td><td>10.41</td></tr></tbody></table>

In this study, we used one of these supervised preprocessing approaches, called "Conditional Info<fnref n="6" />".

The following notation is used below: Let $D = \{(X_i, Y_i)\}_{1}^{N}$ denote a training dataset of size $N$, where $X_i = \{X_i^1, ..., X_i^d\}$ is a vector of $d$ features and $Y_i \in \{1,...,N\} \in \{Class_1, ..., Class_C\}$ is the target class of size $C$. Let $K$ denote the number of clusters set by the user.

This preprocessing method is based on two steps: (1) supervised representation and (2) recoding. The first one aims at giving information about features distribution conditionally to a target class. To achieve this objective, the *MODL* (a bayes optimal pre-processing method for continuous and categorical features) approach is used. It seeks to estimate the univariate conditional density (i.e. $P(X_i^m|Class_j)$, where $m \in \{1, ..., d\}$ and $j \in \{1, ..., C\}$). To obtain this estimation a supervised discretization method is used for continuous features [32] and a supervised grouping method is used for categorical ones [33]. To exploit the information given by the first step, a recoding phase is then required.

Each feature from the instance $X_i$ is recoded in a qualitative attribute containing $I_C$ recoding values. As a result, the initial vector ($X_i$) containing $d$ features (continuous and categorical) becomes a new vector ($XR_i$) containing $d \times C$ real components: $log(P(X_i^m|Class_j)), j \in \{1,...,C\}, m \in \{1,...,d\}$.

To give an idea of the good impact of this preprocessing step, using the previous dataset (Figure 2), the obtained performance 'quality' (using ARI criterion) is equal to 0.792 compared to 0.514 (using SN preprocessing step.)

5) *Cross validation:* In order to compare the obtained results, a '10 × 5' fold cross validation has been performed on all datasets. Thus, the results are presented as an average of 50 tests (e.g. see table III).

## B. Results

1) *Evolution of the error reconstruction:* The generated partition contains $K$ centers ($k_1,...,k_K$). Each center is a vector of $Z$ features, where $Z$ is the number of features after the supervised preprocessing process. So, for a given dataset, the value of $Z$ is then equal to $d \times C = (M_n + M_c) \times C$ (see Table I).

To evaluate the quality of the generated partition in terms of instances similarity in each cluster, the Mean Squared Error is used (see equation 1).

$$MSE = \frac{1}{N} \frac{1}{Z} \frac{1}{K} \sum_{i=1}^{N} \sum_{z=1}^{Z} \sum_{t=1}^{K} \sum_{i \in K_t} (\mathrm{XR}_i^z - k_t^z)^2 \quad (1)$$

where $\mathrm{XR}_i$ is the new vector of the $i$-th instance after the preprocessing step (using Conditional Info); It contains $Z = d \times C$ components.

To our knowledge, the K++ method is quite used to initialize seeds for the K-means algorithm. For this reason, we compare it to our proposed method and other unsupervised methods using the MSE criterion. Table II presents the comparison results (in percentage) between the MSE of K++ and the other initialization approaches (i.e. Rand, Sample and K++R) when $R = 1$ (see Algorithm 1). A positive percentage from this table means that the performance (in terms of MSE) of the generated partition using 'K++' method is better than the performance using its corresponding initialization method. This results show that, for only one relicate, K++ is better than the two other unsupervised initialization methods and it is competitive to K++R.

<table><caption>TABLE II: Comparison in percentage between the MSE of K++ and the other methods when using a single replicate($R$)</caption><thead><tr><th>Database</th><th>K++/Rand</th><th>K++/Sample</th><th>K++/K++R</th></tr></thead><tbody><tr><td>Iris</td><td>56%</td><td>44%</td><td>0%</td></tr><tr><td>Hepatitis</td><td>0%</td><td>0%</td><td>0%</td></tr><tr><td>Glass</td><td>4%</td><td>2%</td><td>2%</td></tr><tr><td>Heart</td><td>4%</td><td>4%</td><td>0%</td></tr><tr><td>Horsecolic</td><td>0%</td><td>0%</td><td>-3%</td></tr><tr><td>Soybean</td><td>27%</td><td>27%</td><td>-12%</td></tr><tr><td>Pima</td><td>-2%</td><td>-2%</td><td>0%</td></tr><tr><td>Vehicle</td><td>8%</td><td>7%</td><td>2%</td></tr><tr><td>Tictactoe</td><td>0%</td><td>0%</td><td>-14%</td></tr><tr><td>LED</td><td>14%</td><td>11%</td><td>-17%</td></tr><tr><td>Phoneme</td><td>0%</td><td>0%</td><td>-1%</td></tr><tr><td>Segmentation</td><td>4%</td><td>4%</td><td>-3%</td></tr><tr><td>Abalone</td><td>19%</td><td>18%</td><td>30%</td></tr><tr><td>Waveform</td><td>0%</td><td>0%</td><td>0%</td></tr><tr><td>PenDigits</td><td>1%</td><td>1%</td><td>-2%</td></tr></tbody></table>

When the number of replicates increase (i.e. $R \in \{1, 10, 100, 1000\}$), the average value of MSE for the three unsupervised initialization methods decreases; especially for Random and Samples methods (see Table III). This improvement is important when going from one to 10 replicates, less important from 10 to 100 replicates and it remains nearly unchanged when going from 100 to 1000 for all datasets except for Soybean, LED and Abalone datasets.

Among the three unsupervised initialization method, K++ is the best one. However, it is recommended to use it with a

<footnote n="6">⁶ In this study, the Conditional Info is applied to all of datasets described in Table I.</footnote>
<table><caption>TABLE III: MSE versus the number of replicates (R)</caption><thead><tr><th>Dataset</th><th>Rand</th><th>Sample</th><th>K++</th><th>K++R</th></tr></thead><tbody><tr><td colspan="5" style="text-align:center; font-weight:bold;">R=1</td></tr><tr><td>Iris</td><td>4.74±3.62</td><td>4.37±3.61</td><td>3.03±1.59</td><td>3.04±1.43</td></tr><tr><td>Hepatitis</td><td>0.22±0.08</td><td>0.22±0.08</td><td>0.22±0.08</td><td>0.22±0.08</td></tr><tr><td>Glass</td><td>13.37±2.40</td><td>13.10±2.31</td><td>12.80±2.52</td><td>13.03±2.45</td></tr><tr><td>Heart</td><td>0.26±0.05</td><td>0.26±0.05</td><td>0.25±0.04</td><td>0.25±0.04</td></tr><tr><td>Horsecolic</td><td>0.30±0.05</td><td>0.30±0.05</td><td>0.30±0.05</td><td>0.29±0.05</td></tr><tr><td>Soybean</td><td>35.23±4.50</td><td>35.16±4.68</td><td>27.71±3.40</td><td>24.27±2.16</td></tr><tr><td>Pima</td><td>0.42±0.11</td><td>0.42±0.11</td><td>0.43±0.12</td><td>0.43±0.11</td></tr><tr><td>Vehicle</td><td>7.79±1.32</td><td>7.78±1.31</td><td>7.23±1.35</td><td>7.35±1.24</td></tr><tr><td>Tictactoe</td><td>0.07±0.02</td><td>0.07±0.02</td><td>0.07±0.02</td><td>0.06±0.02</td></tr><tr><td>LED</td><td>4.41±0.54</td><td>4.29±0.52</td><td>3.86±0.43</td><td>3.21±0.35</td></tr><tr><td>Phoneme</td><td>22.98±0.73</td><td>22.97±0.72</td><td>22.97±0.68</td><td>22.85±0.69</td></tr><tr><td>Segmentation</td><td>36.82±4.15</td><td>36.79±4.16</td><td>35.40±3.17</td><td>34.19±1.32</td></tr><tr><td>Abalone</td><td>33.95±3.65</td><td>33.67±3.64</td><td>28.59±2.51</td><td>37.08±4.03</td></tr><tr><td>Waveform</td><td>2.11±0.51</td><td>2.11±0.51</td><td>2.12±0.54</td><td>2.13±0.46</td></tr><tr><td>PenDigits</td><td>58.44±2.27</td><td>58.33±2.30</td><td>57.94±1.94</td><td>56.66±1.59</td></tr><tr><td colspan="5" style="text-align:center; font-weight:bold;">R=10</td></tr><tr><td>Iris</td><td>2.81±1.43</td><td>2.81±1.43</td><td>2.80±1.43</td><td>3.04±1.43</td></tr><tr><td>Hepatitis</td><td>0.21±0.08</td><td>0.21±0.08</td><td>0.21±0.08</td><td>0.22±0.08</td></tr><tr><td>Glass</td><td>12.22±2.39</td><td>12.25±2.41</td><td>12.15±2.37</td><td>13.03±2.45</td></tr><tr><td>Heart</td><td>0.25±0.04</td><td>0.25±0.04</td><td>0.25±0.04</td><td>0.25±0.04</td></tr><tr><td>Horsecolic</td><td>0.29±0.05</td><td>0.29±0.05</td><td>0.29±0.05</td><td>0.29±0.05</td></tr><tr><td>Soybean</td><td>29.43±2.32</td><td>29.16±2.27</td><td>25.06±1.95</td><td>24.27±2.16</td></tr><tr><td>Pima</td><td>0.40±0.10</td><td>0.40±0.10</td><td>0.39±0.07</td><td>0.43±0.11</td></tr><tr><td>Vehicle</td><td>6.46±0.83</td><td>6.48±0.82</td><td>6.41±0.83</td><td>7.35±1.24</td></tr><tr><td>Tictactoe</td><td>0.06±0.02</td><td>0.06±0.02</td><td>0.06±0.02</td><td>0.06±0.02</td></tr><tr><td>LED</td><td>3.68±0.42</td><td>3.64±0.39</td><td>3.50±0.34</td><td>3.21±0.35</td></tr><tr><td>Phoneme</td><td>22.85±0.69</td><td>22.85±0.69</td><td>22.85±0.69</td><td>22.85±0.69</td></tr><tr><td>Segmentation</td><td>33.95±1.33</td><td>33.93±1.33</td><td>33.71±1.26</td><td>34.19±1.32</td></tr><tr><td>Abalone</td><td>30.75±2.58</td><td>30.41±2.55</td><td>26.72±1.82</td><td>35.42±4.07</td></tr><tr><td>Waveform</td><td>2.06±0.45</td><td>2.06±0.45</td><td>2.06±0.45</td><td>2.13±0.46</td></tr><tr><td>PenDigits</td><td>56.41±1.62</td><td>56.43±1.63</td><td>56.39±1.61</td><td>56.66±1.59</td></tr><tr><td colspan="5" style="text-align:center; font-weight:bold;">R=100</td></tr><tr><td>Iris</td><td>2.80±1.43</td><td>2.80±1.43</td><td>2.80±1.43</td><td>3.04±1.43</td></tr><tr><td>Hepatitis</td><td>0.21±0.08</td><td>0.21±0.08</td><td>0.21±0.08</td><td>0.22±0.08</td></tr><tr><td>Glass</td><td>12.05±2.28</td><td>12.02±2.31</td><td>12.09±2.26</td><td>13.03±2.45</td></tr><tr><td>Heart</td><td>0.25±0.04</td><td>0.25±0.04</td><td>0.25±0.04</td><td>0.25±0.04</td></tr><tr><td>Horsecolic</td><td>0.29±0.05</td><td>0.29±0.05</td><td>0.29±0.05</td><td>0.29±0.05</td></tr><tr><td>Soybean</td><td>27.12±2.45</td><td>27.02±2.37</td><td>23.88±2.21</td><td>24.27±2.16</td></tr><tr><td>Pima</td><td>0.39±0.07</td><td>0.39±0.07</td><td>0.39±0.07</td><td>0.43±0.11</td></tr><tr><td>Vehicle</td><td>6.41±0.83</td><td>6.41±0.83</td><td>6.41±0.83</td><td>7.35±1.24</td></tr><tr><td>Tictactoe</td><td>0.06±0.02</td><td>0.06±0.02</td><td>0.06±0.02</td><td>0.06±0.02</td></tr><tr><td>LED</td><td>3.48±0.35</td><td>3.45±0.34</td><td>3.35±0.34</td><td>3.21±0.35</td></tr><tr><td>Phoneme</td><td>22.85±0.69</td><td>22.85±0.69</td><td>22.85±0.69</td><td>22.85±0.69</td></tr><tr><td>Segmentation</td><td>33.60±1.25</td><td>33.60±1.25</td><td>33.61±1.25</td><td>34.19±1.32</td></tr><tr><td>Abalone</td><td>28.92±2.32</td><td>28.65±2.27</td><td>25.76±1.78</td><td>34.94±4.27</td></tr><tr><td>Waveform</td><td>2.06±0.45</td><td>2.06±0.45</td><td>2.06±0.45</td><td>2.13±0.46</td></tr><tr><td>PenDigits</td><td>56.23±1.55</td><td>56.23±1.55</td><td>56.23±1.55</td><td>56.66±1.59</td></tr><tr><td colspan="5" style="text-align:center; font-weight:bold;">R=1000</td></tr><tr><td>Iris</td><td>2.80±1.43</td><td>2.80±1.43</td><td>2.80±1.43</td><td>3.04±1.43</td></tr><tr><td>Hepatitis</td><td>0.21±0.08</td><td>0.21±0.08</td><td>0.21±0.08</td><td>0.22±0.08</td></tr><tr><td>Glass</td><td>12.06±2.27</td><td>12.05±2.26</td><td>12.05±2.26</td><td>13.03±2.45</td></tr><tr><td>Heart</td><td>0.25±0.04</td><td>0.25±0.04</td><td>0.25±0.04</td><td>0.25±0.04</td></tr><tr><td>Horsecolic</td><td>0.29±0.05</td><td>0.29±0.05</td><td>0.29±0.05</td><td>0.29±0.05</td></tr><tr><td>Soybean</td><td>25.56±2.18</td><td>25.30±2.22</td><td>23.21±2.38</td><td>24.27±2.16</td></tr><tr><td>Pima</td><td>0.39±0.07</td><td>0.39±0.07</td><td>0.39±0.07</td><td>0.43±0.11</td></tr><tr><td>Vehicle</td><td>6.41±0.83</td><td>6.41±0.83</td><td>6.41±0.83</td><td>7.35±1.24</td></tr><tr><td>Tictactoe</td><td>0.06±0.02</td><td>0.06±0.02</td><td>0.06±0.02</td><td>0.06±0.02</td></tr><tr><td>LED</td><td>3.37±0.34</td><td>3.37±0.34</td><td>3.25±0.34</td><td>3.21±0.35</td></tr><tr><td>Phoneme</td><td>22.85±0.69</td><td>22.85±0.69</td><td>22.85±0.69</td><td>22.85±0.69</td></tr><tr><td>Segmentation</td><td>33.61±1.25</td><td>33.61±1.25</td><td>33.61±1.25</td><td>34.19±1.32</td></tr><tr><td>Abalone</td><td>28.07±1.80</td><td>27.72±1.87</td><td>25.32±1.90</td><td>34.79±4.40</td></tr><tr><td>Waveform</td><td>2.06±0.45</td><td>2.06±0.45</td><td>2.06±0.45</td><td>2.13±0.46</td></tr><tr><td>PenDigits</td><td>56.23±1.55</td><td>56.23±1.55</td><td>56.23±1.55</td><td>56.66±1.59</td></tr></tbody></table>

number of replicates at least equal to 10 or greater for certain datasets.

For the K++R method, its average value of MSE remains unchanged for all datasets whatever the number of replicates (see Table III). Indeed, when the number of clusters is equal to the number of classes, the proposed method is a deterministic approach (i.e. it follows the Rochio solution (see

Section IV)).

<table><caption>TABLE IV: Comparison in percentage between the MSE of K++ and K++R for R=1, 10, 100, 1000.</caption><thead><tr><th>Database</th><th>R=1</th><th>R=10</th><th>R=100</th><th>R=1000</th></tr></thead><tbody><tr><td>Iris</td><td>0%</td><td>9%</td><td>9%</td><td>9%</td></tr><tr><td>Hepatitis</td><td>0%</td><td>5%</td><td>5%</td><td>5%</td></tr><tr><td>Glass</td><td>2%</td><td>7%</td><td>8%</td><td>8%</td></tr><tr><td>Heart</td><td>0%</td><td>0%</td><td>0%</td><td>0%</td></tr><tr><td>Horsecolic</td><td>-3%</td><td>0%</td><td>0%</td><td>0%</td></tr><tr><td>Soybean</td><td>-12%</td><td>-3%</td><td>2%</td><td>5%</td></tr><tr><td>Pima</td><td>0%</td><td>10%</td><td>10%</td><td>10%</td></tr><tr><td>Vehicle</td><td>2%</td><td>15%</td><td>15%</td><td>15%</td></tr><tr><td>Tictactoe</td><td>-14%</td><td>0%</td><td>0%</td><td>0%</td></tr><tr><td>LED</td><td>-17%</td><td>-8%</td><td>-4%</td><td>-1%</td></tr><tr><td>Phoneme</td><td>-1%</td><td>0%</td><td>0%</td><td>0%</td></tr><tr><td>Segmentation</td><td>-3%</td><td>1%</td><td>2%</td><td>2%</td></tr><tr><td>Abalone</td><td>30%</td><td>33%</td><td>36%</td><td>38%</td></tr><tr><td>Waveform</td><td>0%</td><td>3%</td><td>3%</td><td>3%</td></tr><tr><td>PenDigits</td><td>-2%</td><td>0%</td><td>1%</td><td>1%</td></tr></tbody></table>

We compare now the quality of the generated partition in terms of MSE, using in each time K++ and K++R. Table IV presents the comparison results (in percentage) for the MSE of K++R and K++R, for $R \in \{1, 10, 100, 1000\}$. This table shows that when we combine the proposed initialization method with the supervised preprocessing approach (see Section V-A), K++R is competitive to K++ method in terms of MSE when R=1 (i.e. it exhibits better or similar MSE than K++). When R increases, the K++R approach exhibits MSE not exceeding 5% for 10 datasets.

2) Evolution of the ARI: The above experiments show that the proposed method can reach a good performance in terms of MSE compared to the other popular unsupervised initialization methods. Now, to achieve the goal of the supervised clustering, we have to prove that the traditional K-means with the proposed method could also reach a good predictive performance (using a supervised criterion).

Table V presents the average predictive performance (using ARI criterion) of the partition of the traditional K-means using supervised and unsupervised initialization method. From this results, we can see that, whatever the number of replicates (R), the proposed method remains the best one for 9 datasets out of 15 and similar to the others but with one replicate (i.e the traditional K-means with the proposed method is 10 times (or more) faster than using K++).

Now, if we choose another supervised criterion to measure the quality of the generated partitions, the obtained conclusion remains the same. Figures 6 and 7 present respectively, for all used datasets, the quality of the generated partitions using Accuracy<fnref n="7" /> (ACC) and Balanced Accuracy<fnref n="8" /> (BACC) criterion, in the case R=1000 for 'Rand', 'Sample' and 'K++' and where R=1 for 'K++R'.

<footnote n="7">⁷ the accuracy criterion is computed by comparing the true class and the predicted class which is the majority class of the examples belonging to a cluster</footnote>

<footnote n="8">⁸ This criterion avoids inflated performance estimates on imbalanced datasets.</footnote>
<table><caption>TABLE V: ARI versus the number of replicates (R)</caption><thead><tr><th>Dataset</th><th>Rand</th><th>Sample</th><th>K++</th><th>K++R</th></tr></thead><tbody><tr><td colspan="5" style="text-align:center; font-weight:bold;">R=1</td></tr><tr><td>Iris</td><td>0.59±0.17</td><td>0.61±0.20</td><td>0.65±0.16</td><td>0.78±0.12</td></tr><tr><td>Hepatitis</td><td>0.15±0.16</td><td>0.15±0.16</td><td>0.17±0.18</td><td>0.21±0.15</td></tr><tr><td>Glass</td><td>0.47±0.15</td><td>0.48±0.14</td><td>0.48±0.15</td><td>0.78±0.10</td></tr><tr><td>Heart</td><td>0.32±0.18</td><td>0.32±0.18</td><td>0.29±0.18</td><td>0.36±0.15</td></tr><tr><td>Horsecolic</td><td>0.33±0.17</td><td>0.33±0.17</td><td>0.37±0.12</td><td>0.39±0.10</td></tr><tr><td>Soybean</td><td>0.45±0.08</td><td>0.44±0.07</td><td>0.50±0.07</td><td>0.63±0.07</td></tr><tr><td>Pima</td><td>0.04±0.08</td><td>0.04±0.08</td><td>0.05±0.08</td><td>0.10±0.12</td></tr><tr><td>Vehicle</td><td>0.16±0.04</td><td>0.16±0.04</td><td>0.16±0.03</td><td>0.20±0.09</td></tr><tr><td>Tictactoe</td><td>0.09±0.07</td><td>0.09±0.07</td><td>0.08±0.06</td><td>0.14±0.05</td></tr><tr><td>LED</td><td>0.37±0.06</td><td>0.37±0.06</td><td>0.40±0.05</td><td>0.52±0.05</td></tr><tr><td>Phoneme</td><td>0.71±0.04</td><td>0.71±0.04</td><td>0.71±0.04</td><td>0.72±0.02</td></tr><tr><td>Segmentation</td><td>0.59±0.08</td><td>0.59±0.08</td><td>0.60±0.07</td><td>0.70±0.04</td></tr><tr><td>Abalone</td><td>0.05±0.01</td><td>0.05±0.01</td><td>0.05±0.01</td><td>0.06±0.00</td></tr><tr><td>Waveform</td><td>0.20±0.06</td><td>0.20±0.06</td><td>0.20±0.06</td><td>0.22±0.08</td></tr><tr><td>PenDigits</td><td>0.53±0.05</td><td>0.53±0.05</td><td>0.53±0.04</td><td>0.62±0.02</td></tr><tr><td colspan="5" style="text-align:center; font-weight:bold;">R=10</td></tr><tr><td>Iris</td><td>0.68±0.15</td><td>0.68±0.15</td><td>0.67±0.15</td><td>0.78±0.12</td></tr><tr><td>Hepatitis</td><td>0.10±0.12</td><td>0.10±0.12</td><td>0.10±0.12</td><td>0.21±0.15</td></tr><tr><td>Glass</td><td>0.47±0.15</td><td>0.47±0.15</td><td>0.47±0.14</td><td>0.78±0.10</td></tr><tr><td>Heart</td><td>0.29±0.18</td><td>0.29±0.18</td><td>0.29±0.18</td><td>0.36±0.15</td></tr><tr><td>Horsecolic</td><td>0.39±0.10</td><td>0.39±0.10</td><td>0.39±0.10</td><td>0.39±0.10</td></tr><tr><td>Soybean</td><td>0.49±0.07</td><td>0.48±0.07</td><td>0.51±0.08</td><td>0.63±0.07</td></tr><tr><td>Pima</td><td>0.01±0.02</td><td>0.01±0.02</td><td>0.00±0.01</td><td>0.10±0.12</td></tr><tr><td>Vehicle</td><td>0.17±0.03</td><td>0.17±0.03</td><td>0.17±0.03</td><td>0.20±0.09</td></tr><tr><td>Tictactoe</td><td>0.13±0.06</td><td>0.13±0.06</td><td>0.13±0.06</td><td>0.14±0.05</td></tr><tr><td>LED</td><td>0.44±0.05</td><td>0.43±0.05</td><td>0.45±0.04</td><td>0.52±0.05</td></tr><tr><td>Phoneme</td><td>0.72±0.02</td><td>0.72±0.02</td><td>0.72±0.02</td><td>0.73±0.02</td></tr><tr><td>Segmentation</td><td>0.66±0.06</td><td>0.66±0.07</td><td>0.69±0.06</td><td>0.70±0.04</td></tr><tr><td>Abalone</td><td>0.05±0.01</td><td>0.05±0.01</td><td>0.05±0.01</td><td>0.06±0.01</td></tr><tr><td>Waveform</td><td>0.21±0.04</td><td>0.21±0.04</td><td>0.21±0.04</td><td>0.22±0.08</td></tr><tr><td>PenDigits</td><td>0.56±0.03</td><td>0.56±0.03</td><td>0.56±0.02</td><td>0.62±0.02</td></tr><tr><td colspan="5" style="text-align:center; font-weight:bold;">R=100</td></tr><tr><td>Iris</td><td>0.67±0.15</td><td>0.67±0.15</td><td>0.67±0.15</td><td>0.78±0.12</td></tr><tr><td>Hepatitis</td><td>0.10±0.13</td><td>0.10±0.13</td><td>0.10±0.13</td><td>0.21±0.15</td></tr><tr><td>Glass</td><td>0.48±0.14</td><td>0.49±0.13</td><td>0.47±0.14</td><td>0.78±0.10</td></tr><tr><td>Heart</td><td>0.29±0.18</td><td>0.29±0.18</td><td>0.29±0.18</td><td>0.36±0.15</td></tr><tr><td>Horsecolic</td><td>0.39±0.10</td><td>0.39±0.10</td><td>0.39±0.10</td><td>0.39±0.10</td></tr><tr><td>Soybean</td><td>0.52±0.09</td><td>0.51±0.08</td><td>0.55±0.07</td><td>0.63±0.07</td></tr><tr><td>Pima</td><td>0.00±0.01</td><td>0.00±0.01</td><td>0.00±0.01</td><td>0.10±0.12</td></tr><tr><td>Vehicle</td><td>0.17±0.03</td><td>0.17±0.03</td><td>0.17±0.03</td><td>0.20±0.09</td></tr><tr><td>Tictactoe</td><td>0.13±0.06</td><td>0.13±0.06</td><td>0.13±0.06</td><td>0.14±0.05</td></tr><tr><td>LED</td><td>0.46±0.04</td><td>0.46±0.04</td><td>0.48±0.04</td><td>0.52±0.05</td></tr><tr><td>Phoneme</td><td>0.72±0.02</td><td>0.72±0.02</td><td>0.72±0.02</td><td>0.73±0.02</td></tr><tr><td>Segmentation</td><td>0.70±0.05</td><td>0.70±0.05</td><td>0.70±0.05</td><td>0.70±0.04</td></tr><tr><td>Abalone</td><td>0.05±0.01</td><td>0.05±0.01</td><td>0.05±0.00</td><td>0.06±0.00</td></tr><tr><td>Waveform</td><td>0.21±0.04</td><td>0.21±0.04</td><td>0.21±0.04</td><td>0.22±0.08</td></tr><tr><td>PenDigits</td><td>0.55±0.01</td><td>0.55±0.01</td><td>0.55±0.01</td><td>0.62±0.02</td></tr><tr><td colspan="5" style="text-align:center; font-weight:bold;">R=1000</td></tr><tr><td>Iris</td><td>0.67±0.15</td><td>0.67±0.15</td><td>0.67±0.15</td><td>0.78±0.12</td></tr><tr><td>Hepatitis</td><td>0.10±0.13</td><td>0.10±0.13</td><td>0.10±0.13</td><td>0.21±0.15</td></tr><tr><td>Glass</td><td>0.48±0.14</td><td>0.48±0.14</td><td>0.48±0.14</td><td>0.78±0.10</td></tr><tr><td>Heart</td><td>0.29±0.18</td><td>0.29±0.18</td><td>0.29±0.18</td><td>0.36±0.15</td></tr><tr><td>Horsecolic</td><td>0.39±0.10</td><td>0.39±0.10</td><td>0.39±0.10</td><td>0.39±0.10</td></tr><tr><td>Soybean</td><td>0.53±0.08</td><td>0.53±0.08</td><td>0.55±0.08</td><td>0.63±0.07</td></tr><tr><td>Pima</td><td>0.00±0.01</td><td>0.00±0.01</td><td>0.00±0.01</td><td>0.10±0.12</td></tr><tr><td>Vehicle</td><td>0.17±0.03</td><td>0.17±0.03</td><td>0.17±0.03</td><td>0.20±0.09</td></tr><tr><td>Tictactoe</td><td>0.13±0.06</td><td>0.13±0.06</td><td>0.13±0.06</td><td>0.14±0.05</td></tr><tr><td>LED</td><td>0.48±0.04</td><td>0.48±0.04</td><td>0.50±0.05</td><td>0.52±0.05</td></tr><tr><td>Phoneme</td><td>0.72±0.02</td><td>0.72±0.02</td><td>0.72±0.02</td><td>0.72±0.02</td></tr><tr><td>Segmentation</td><td>0.70±0.05</td><td>0.70±0.05</td><td>0.70±0.05</td><td>0.70±0.04</td></tr><tr><td>Abalone</td><td>0.05±0.01</td><td>0.05±0.01</td><td>0.05±0.00</td><td>0.06±0.00</td></tr><tr><td>Waveform</td><td>0.21±0.04</td><td>0.21±0.04</td><td>0.21±0.04</td><td>0.22±0.08</td></tr><tr><td>PenDigits</td><td>0.55±0.01</td><td>0.55±0.01</td><td>0.55±0.01</td><td>0.62±0.02</td></tr></tbody></table>

<figure><img src="image_7.png" /><figcaption>Fig. 6: ACC on the different databases (R=1000 for 'Rand', 'Sample' and 'K++', R=1 for K++R).</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 7: BACC on the different databases (R=1000 for 'Rand', 'Sample' and 'K++', R=1 for K++R).</figcaption></figure>

cessing step allow the standard K-means algorithm to reach a trade-off between similarity (using MSE criterion) and prediction (that is the objective of the supervised clustering). Future works will be done: (i) to improve the method in the case where the number of cluster exceeds to the number of classes and therefore the case where K is an output, (ii) to compare K++R to others unsupervised initialization methods, and (iii) to combine the K++R method with a supervised K-means algorithm.

## REFERENCES

[1] L. Kaufman and P. J. Rousseeuw, *Finding Groups in Data: An Introduction to Cluster Analysis*. John Wiley, 1990.

[2] A. K. Jain, M. N. Murty, and P. J. Flynn, “Data

# VI. CONCLUSION

This paper has presented the influence of the supervised initialization step on the performance of the traditional K-means algorithm in terms of predictions (using ARI and ACC criteria). The experimental results show that the proposed method of initialization (K++R) with a supervised prepro-
clustering: A review,” *ACM Comput. Surv.*, vol. 31, no. 3, pp. 264–323, 1999.

[3] S. H. Al-Harbi and V. J. Rayward-Smith, “Adapting k-means for supervised clustering,” *Applied Intelligence*, vol. 24, no. 3, pp. 219–226, Jun. 2006.

[4] C. F. Eick, N. Zeidat, and Z. Zhao, “Supervised clustering algorithms and benefits,” in *In proceedings of the 16th IEEE (ICTAI04)*, Boca, 2004, pp. 774–776.

[5] J. MacQueen, “Some methods for classification and analysis of multivariate observations,” in *5th Berkeley Symposium on Mathematical Statistics and Probability*, vol. 1, 1967, pp. 281–297.

[6] P. S. Bradley, O. L. Mangasarian, and W. N. Street, “Clustering via concave minimization,” in *Advances in Neural Information Processing Systems 9*. MIT Press, 1997, pp. 368–374.

[7] M. Meilä and D. Heckerman, “An experimental comparison of several clustering and initialization methods,” in *Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence*. Morgan Kaufmann Publishers Inc., 1998, pp. 386–395.

[8] L. Hubert and P. Arabie, “Comparing partitions,” *Journal of Classification*, vol. 2, no. 1, pp. 193–218, 1985.

[9] Z. Huang, “Extensions to the k-means algorithm for clustering large data sets with categorical values,” *Data Min. Knowl. Discov.*, vol. 2, pp. 283–304, 1998.

[10] L. Kaufman and P. J. Rousseeuw, *Finding Groups in Data: An Introduction to Cluster Analysis*. John Wiley, 1990.

[11] A. Juan and E. Vidal, “Comparison of Four Initialization Techniques for the $k$-MEDians Clustering Algorithm,” in *Proc. Joint IAPR International Workshops on Advances in Pattern Recognition*. London, UK: Springer-Verlag, 2000, pp. 842–852.

[12] H.-S. Park and C.-H. Jun, “A simple and fast algorithm for k-medoids clustering,” *Expert Syst. Appl.*, vol. 36, no. 2, pp. 3336–3341, 2009.

[13] M. E. Celebi, H. A. Kingravi, and P. A. Vela, “A comparative study of efficient initialization methods for the k-means clustering algorithm.” *Expert Syst. Appl.*, vol. 40, no. 1, pp. 200–210, 2013.

[14] R. Maitra, A. D. Peterson, and A. P. Ghosh, “A systematic evaluation of different methods for initializing the k-means clustering algorithm,” *IEEE Transactions on Knowledge and Data Engineering*, pp. 522–537, 2010.

[15] M. E. Celebi, “Improving the performance of k-means for color quantization,” *Image Vision Comput.*, vol. 29, no. 4, pp. 260–271, 2011.

[16] E. Forgy, “Cluster analysis of multivariate data: Efficiency vs. interpretability of classification,” *Biometrics*, vol. 21, no. 78, 1965.

[17] Y. Linde, A. Buzo, and R. Gray, “An Algorithm for Vector Quantizer Design,” *Communications, IEEE Transactions on*, vol. 28, no. 1, pp. 84–95, 1980.

[18] I. Katsavounidis, C. C. Jay Kuo, and Z. Zhang, “A new initialization technique for generalized Lloyd iteration,”

*IEEE Signal Processing Letters*, vol. 1, no. 10, pp. 144–146, 1994.

[19] M. B. Al-Daoud and S. A. Roberts, “New methods for the initialisation of clusters,” *Pattern Recognition Letters*, vol. 17, no. 5, pp. 451–455, 1996.

[20] D. Arthur and S. Vassilvitskii, “K-means++: The advantages of careful seeding,” in *Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms*, ser. SODA ’07. USA: Society for Industrial and Applied Mathematics, 2007, pp. 1027–1035.

[21] J. Sinkkonen, S. Kaski, and J. Nikkil, “Discriminative clustering: Optimal contingency tables by learning metrics.” in *ECML*, ser. Lecture Notes in Computer Science, vol. 2430. Springer, 2002, pp. 418–430.

[22] T. Finley and T. Joachims, “Supervised clustering with support vector machines,” ser. ICML ’05. USA: ACM, 2005, pp. 217–224.

[23] J. S. Aguilar-Ruiz, R. Ruiz, J. C. R. Santos, and R. Girldez, “Snn: A supervised clustering algorithm.” in *IEA/AIE*, ser. Lecture Notes in Computer Science, vol. 2070. Springer, 2001, pp. 207–216.

[24] Y. Qu and S. Xu, “Supervised cluster analysis for microarray data based on multivariate gaussian mixture,” *Bioinformatics*, vol. 20, no. 12, pp. 1905–1913, 2004.

[25] N. Slonim and N. Tishby, “Agglomerative information bottleneck,” in *Neural Information Processing Systems*, 2000, pp. 617–623.

[26] N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” in *37-th Annual Allerton Conference on Communication, Control and Computing*, 1999, pp. 368–377.

[27] P. Bungkomkhun and S. Auwatanamongkol, “Grid-based supervised clustering algorithm using greedy and gradient descent methods to build clusters,” *IJCSI International Journal of Computer Science*, 2012.

[28] C. D. Manning, P. Raghavan, and H. Schtze, *Introduction to Information Retrieval*. New York: Cambridge University Press, 2008.

[29] J. M. Santos and M. Embrechts, “On the use of the adjusted rand index as a metric for evaluating supervised classification,” ser. ICANN ’09. Springer-Verlag, 2009, pp. 175–184.

[30] D. N. A. Asuncion, “UCI machine learning repository,” 2007. [Online]. Available: http://www.ics.uci.edu/$\sim$sim$mlearn/{MLR}epository.html

[31] O. Alaoui Ismaili, V. Lemaire, and A. Cornuéjols, “Supervised pre-processings are useful for supervised clustering,” *Springer Series Studies in Classification, Data Analysis, and Knowledge Organization*, 2015.

[32] M. Boullé, “MODL: a Bayes optimal discretization method for continuous attributes,” *Machine Learning*, vol. 65, no. 1, pp. 131–165, 2006.

[33] ——, “A Bayes optimal approach for partitioning the values of categorical attributes,” *Journal of Machine Learning Research*, vol. 6, pp. 1431–1452, 2005.