Clustering-Based Subset Selection in Evolutionary Multiobjective Optimization*

For a given data set $D=\{\bm{x}_{1},\bm{x}_{2},...,\bm{x}_{n}\}$, a clustering algorithm divides $D$ into $k$ clusters $C=\{C_{1},C_{2},...,C_{k}\}$ where $\forall i\neq j,C_{i}\cap C_{j}=\emptyset$ and $D=\cup_{i=1}^{k}C_{i}$.

Partition-based clustering algorithms, such as K-means [13], K-means++ [14], and K-medoids [15], are the most widely-used clustering algorithms. In this type of clustering algorithms, $k$ cluster centers are first initialized randomly as in K-means or based on some heuristics as in K-means++. Then, each data point is assigned to the closest cluster center. The data points assigned to the same cluster center belong to the same cluster. After that, the cluster center is updated. In K-means and K-means++, the center of each cluster is updated to the mean (centroid) of all data points in that cluster. In K-medoids, the data point with the smallest total distance to all the other points in each cluster is chosen as the new cluster center of the corresponding cluster. Therefore, the objective of K-medoids clustering is

$$\text{Minimize}\sum_{i=1}^{k}{\sum_{\bm{x}\in C_{i}}{\left\|\bm{x}-\bm{\mu}_{i}\right\|}},$$

(1)

where $\bm{\mu_{i}}\in C_{i}$.

The main disadvantage of partition-based clustering is that it is not suitable for non-convex clusters. In order to deal with clusters of arbitrary shapes, density-based methods (e.g., DBSCAN [16]) are proposed. This type of clustering algorithms assume that clusters in high-density areas are separated by low-density areas in the data space. These algorithms can obtain clusters with arbitrary shapes efficiently but clustering results are usually sensitive to the parameter setting.

Another popular approach is hierarchical clustering [17], which aims to construct a hierarchical relationship among the given points. The agglomerative approach is usually employed in hierarchical clustering. Each point is considered as a separate cluster at the initial stage. Then, in each iteration, two clusters that are closest to each other are found and merged. There are various criteria (i.e., linkage functions) to evaluate the distance between two clusters, such as single linkage, complete linkage, weighted average linkage [18] and Ward’s linkage [19]. Single linkage calculates the smallest distance between data points in two clusters while complete linkage calculates the largest distance between them. Weighted average linkage calculates the distance between two clusters in a recursive way. If cluster $r$ is obtained by merging clusters $p$ and $q$, the distance between clusters $r$ and $s$ is calculate by $d(r,s)=\frac{d(p,s)+d(q,s)}{2}$. The Ward’s linkage calculates the incremental sum of squares, which can be written as $d(r,s)=\sqrt{\frac{2n_{r}n_{s}}{n_{r}+n_{s}}}\left\|\bm{\mu}_{r}-\bm{\mu}_{s}\right\|,$ where $n_{r}$ and $n_{s}$ are the number of data points in clusters $r$ and $s$, respectively, and $\bm{\mu}_{r}$ and $\bm{\mu}_{s}$ are the cluster centers of clusters $r$ and $s$, respectively.

Besides, there are many other types of clustering algorithms that aim to deal with data sets with various characteristics, such as model-based clustering [20], grid-based clustering [21], fuzzy clustering [22]. For more details about clustering algorithms, please refer to [23].

Since clustering algorithms can divide a data set into a pre-specified number of clusters, clustering algorithms can be used for subset selection in EMO algorithms [10, 11, 5]. To select a subset of size $k$ from a given data set, we first apply a clustering algorithm to the data set. Based on the obtained $k$ clusters, a representative point will be selected from each cluster. These representative points compose the selected subset.

There are some differences between the general use of clustering algorithms and the use of clustering algorithms for subset selection in EMO algorithms. Firstly, since the subset size is usually pre-specified, clustering-based subset selection prefers algorithms that can obtain a fixed number of clusters instead of a variable number of clusters. Besides, some clustering algorithms are designed to deal with complicated cluster shapes or special distributions, which is of little use for subset selection. Additionally, the pre-specified number of clusters is usually much larger in clustering-based subset selection than that in standard applications of clustering algorithms.

Due to these differences, clustering algorithms that perform well in their standard applications may not be suitable for clustering-based subset selection. The performance of clustering algorithms for subset selection are examined in some applications (e.g., NIR spectra analysis [24] and IT service [25]). In our paper, we focus on subset selection in EMO algorithms. More promising clustering algorithms are considered, and different methods for selecting a representative point in each cluster is discussed. To the best of our knowledge, this issue has not been examined in the literature.

Inverted generational distance (IGD) [26] is one of the most widely-used indicators to evaluate the performance of an EMO algorithm. It calculates the average distance from each point $r$ in the reference set $R$ to the closest point in the obtained solution set $P$. The IGD contribution of a solution $\bm{p}\in P$ to the solution set $P$ is defined as $IGDC(\bm{p},R)=IGD(P\setminus\bm{p},R)-IGD(P,R).$

Since the IGD indicator considers the convergence and diversity simultaneously, IGD-based subset selection can be used to select representative solutions from an archive. In this case, all solutions in the archive are used as the reference set for IGD calculation. It aims to select a subset $S$ of size $k$ with the smallest IGD value with respect to all solutions in the archive. Formally, the objective of IGD-based subset selection is

$$\text{Minimize }\frac{1}{n}\sum_{j=1}^{n}\min_{\bm{s}\in S}{\left\|\bm{x}_{j}-\bm{s}\right\|},$$

(2)

where $\bm{x}_{j}$ is a point in the objective space included in the archive, and $n$ is the number of points in the archive (i.e., $\{\bm{x}_{1},\bm{x}_{2},...,\bm{x}_{n}\}$ is the reference point set for IGD calculation). We can divide the whole data set into $k$ groups $G=\{G_{1},G_{2},...,G_{k}\}$ according to the closest point in the subset $S$ (where $|S|=k$). Let us define an indicator function as:

$$I(i,j)=\left\{\begin{aligned} 1&&if\ \bm{x_{j}}\in G_{i},\\ 0&&otherwise.\\ \end{aligned}\right.$$

(3)

Then, the objective of IGD-based subset selection can be re-written as

$$\text{Minimize }\frac{1}{n}\sum_{j=1}^{n}\sum_{i=1}^{k}\left\|\bm{x}_{j}-\bm{s}_{i}\right\|I(i,j)\\ =\frac{1}{n}\sum_{i=1}^{k}\sum_{j=1}^{n}\left\|\bm{x}_{j}-\bm{s}_{i}\right\|I(i,j)=\frac{1}{n}\sum_{i=1}^{k}{\sum_{\bm{x}\in G_{i}}{\left\|\bm{x}-\bm{s}_{i}\right\|}},$$

(4)

which is exactly the same as the objective of K-medoids clustering (i.e., Eq. (1)). Therefore, although IGD-based subset selection is usually classified as indicator-based subset selection, it can also be viewed as a clustering-based subset selection method.

Greedy inclusion is usually used in IGD-based subset selection from large data sets. A greedy inclusion algorithm starts from an empty subset. In each iteration, it selects the data point with the largest IGD contribution to the currently selected subset until a pre-specified number of data points are selected. On the contrary, a greedy removal algorithm starts with the whole data set and iteratively removes the solution with the smallest IGD contribution to the current subset. When the data set size is much larger than the subset size, the greedy removal strategy is not efficient.

Greedy inclusion IGD-based subset selection can be viewed as a top-down clustering approach. In the beginning, the entire data set is treated as a single cluster. Then, new cluster centers are added one by one until the pre-specified number of clusters is found. For example, Fig. 1 shows a data set with seven data points. Let us assume that we want to select three data points. In the initial stage, all the data points belong to a big cluster whose center is $D$. In the next iteration, the first cluster center $D$ is fixed, and the algorithm aims to find another point to minimize the objective in (4). The cluster center $B$ is found and fixed. Now the data set is divided into two clusters (shaded in green). In the same manner, the third cluster center $F$ is found and the data set is divided into three clusters (shown by three pink dashed circles).

In our experimental study, as a candidate solution set $D$, we consider randomly sampled data points on the true Pareto fronts of six test problems with various Pareto front shapes, including linear (DTLZ1 [27]), concave (DTLZ2 [27]), convex (MaF3 [28]), inverted (IDTLZ2 [29]), and disconnected (DTLZ7 [27] and WFG2 [30]).

Three candidate solution sets (i.e., $D$) of different size are generated for each test problem as follows. We first generate a large number of uniformly distributed points on the true Pareto front by the method in Tian et al. [31]. Note that this method cannot generate an arbitrary number of points. In our experiments, the number of generated points is specified as the number closest to 200,000 among the number of points that this method can generate. Then, we randomly select 200, 4,000, and 10,000 points from these uniformly generated points. The data set of size 200 is used to test the performance in the environmental selection scenario while the data sets of size 4,000 and 10,000 are used to test the performance in the final solution selection from the UEA scenario.

We examine six promising and well-known clustering algorithms on each candidate data set. The details of the examined algorithms are as follows.

1. 1.

   K-means++. An improved version of K-means with heuristic cluster center initialization. The maximum number of iterations is specified as 100.

2. 2.

   K-medoids. We use the same cluster center initialization method as K-means++. The maximum number of iterations is specified as 100.

3. 3.

   Greedy IGD-based subset selection (Greedy IGD). Since the select subset size $k$ is smaller than or equal to half of the data set size $n$, we choose greedy inclusion IGD-based subset selection. Lazy greedy inclusion IGD-based subset selection [32] is used to accelerate the selection. The obtained subset by the lazy greedy inclusion algorithm is exactly the same as the naive greedy inclusion algorithm.

4. 4.

   Three variants of of Hierarchical Clustering (HC). Following common practice, we use the agglomerative hierarchical clustering approach. Three linkage functions are tested, i.e., Ward’s linkage, weighted average linkage and single linkage.

Since density-based clustering algorithms and grid-based clustering algorithms cannot generate a pre-specified number of clusters, they are not examined in this paper. Model-based clustering algorithms are very expensive when the data set is large. Therefore, they are not suitable for our test scenarios.

In all experiments in this section, the number of clusters (i.e., subset size) is set to 100. The IGD value of the obtained subset with respect to the corresponding candidate data set (i.e., with respect to the reference point set for the IGD calculation) is used to evaluate the performance of each algorithm. All the experiments are carried out on the server equipped with Intel Xeon E5-2620.

In some clustering algorithms, such as K-medoids and IGD-based subset selection, the representative point of each cluster is obtained as the cluster center when the execution of the clustering algorithm is terminated. We can directly use these points (i.e., the obtained cluster centers) as the final subset. However, in K-means++, although a pre-specified number of cluster centers are determined, each cluster center is not a data point but the mean (centroid) of the data points in the cluster. In hierarchical clustering algorithms, no clear cluster center is determined. Therefore, we need to select a representative point for each cluster in those clustering algorithms where the cluster center is not a data point or no cluster center is explicitly calculated. We can choose the representative point using the following two strategies.

1. 1.

   Strategy 1: Choose the data point closest to the mean (centroid) of the data points in the cluster.

   $$r_{i}={argmin}_{\bm{x}\in C_{i}}\left\|\bm{x}-\bm{\bar{x}}\right\|$$

   (5)

2. 2.

   Strategy 2: Choose the point with the smallest total distance to all data points in the cluster.

   $$r_{i}={argmin}_{\bm{x}\in C_{i}}\sum_{\bm{y}\in C_{i}}\left\|\bm{y}-\bm{x}\right\|$$

   (6)

Table I shows the comparison results between these two strategies on the clusters obtained by K-means++ and hierarchical clustering with Ward’s linkage. We compare these two strategies using the Wilcoxon rank-sum test [33] with the significance level 0.1. The ”+” and ”-” in the table mean Strategy 2 is significantly better and significantly worse than Strategy 1, respectively, while ”=” means there is no statistically significant difference between the two strategies.

As shown in Table I, we can see that when the data set size is 200, there is no significant difference between these two strategies. The reason is that the expected number of data points in each cluster is two when the number of clusters $k$ is set to 100. For a cluster with two data points, if Strategy 1 is used, the cluster center $\bm{\bar{x}}$ is the midpoint of the two data points, and the distance from $\bm{\bar{x}}$ to each data point is the same. Therefore, one of the two points is randomly selected as the representative point. If Strategy 2 is used, the distance from one point to the other point is the same (independent of the choice of one of the two points). Thus, one of the two points is randomly selected as the representative point. Thus, the difference between these two strategies is not significant.

When the size of the data set is larger, we can see that Strategy 2 always has the better or equal performance to Strategy 1 since the objective of Strategy 2 is consistent with IGD minimization while the objective of Strategy 1 is slightly different from IGD minimization. Besides, Strategy 2 is more robust to outliers in the cluster. Therefore, we use Strategy 2 to select representative data points in the remaining experiments.

Table II shows the average IGD value of the subsets obtained by each algorithm on each three-objective data set over 11 runs. The number in parentheses shows the ranking of the corresponding algorithm (among the six algorithms) for the corresponding test problem.

When the data set size is 200, hierarchical clustering with weighted average linkage achieves the best average rank while K-means++ gets the worst average rank. However, when the data set size increases, which is similar to subset selection from the archive, the performance of K-means++ clearly improves and the performance of hierarchical clustering with weighted average linkage clearly degrades. When the data set size is 10,000, K-means++ always achieves the best performance. This shows that K-means++ is not suitable when the number of data points in a cluster is too small. This is because the distance between the cluster center of K-means++ and the selected representative point is large when the data set size is small. By increasing the data set size, this distance becomes small. As a result, the performance of K-means++ as a subset selection method is improved. For higher-dimensional problems (e.g., Table III on the 8-objective data sets), much more data points are needed to have a close data point to each cluster center. Thus, K-means++ is not the best even in the case of 10,000 data points.

Computation time is also important in evaluating clustering algorithms. Fig. 2 shows the relation between the average IGD value of the obtained subsets and the average computation time of each algorithm for different data set sizes. Since the IGD values of the selected subsets from data sets on different Pareto fronts have large differences (depending on the Pareto front shape), each IGD value is normalized by dividing the largest IGD value obtained for each data set before calculating the average value. To be consistent, we do the same normalization on the computation time. On the data sets of size 10,000, since the computation time of greedy IGD-based subset selection is much larger than that of the other algorithms, we use the log scale when plotting the figure.

As shown in Fig. 2(a), when the data set size is small (i.e., 200), hierarchical clustering with weighted average linkage dominates all the other algorithms (with respect to both the IGD value and the computation time), and hierarchical clustering with Ward’s linkage achieves similar performance. When the data set size is large (i.e., 10,000), we can observe from Fig. 2(b) that K-means++ is the most efficient one and achieves the best average IGD value. K-medoids and hierarchical clustering with Ward’s linkage are similar in terms of the IGD value and the computation time.

In general, on the three-objective data sets, if the data set size is small, hierarchical clustering with weighted average linkage is the best choice among the examined algorithms. If the data set size is large, K-means++, which can obtain the best IGD value in the shorted computation time is the best choice.

We use the eight-objective data sets to test the performance of each algorithm in many-objective scenarios. Table III shows the average IGD value of the subsets obtained by each algorithm on each eight-objective data set over 11 runs.

Although greedy IGD-based subset selection does not have very good performance in the three-objective case in Table II, it always achieves the best performance in the eight-objective case in Table III. We can see that in the three-objective case (Table II), hierarchical clustering with Ward’s linkage consistently outperforms greedy IGD-based subset selection. However, in the eight-objective case, greedy IGD-based subset selection always outperforms hierarchical clustering with Ward’s linkage. This is due to the curse of dimensionality. The linkage functions to measure the distance between two clusters are usually designed for clustering in two or three dimensions. Thus, the performance of hierarchical clustering tends to degrade as the number of dimensions increases. Such performance deterioration can also be observed on the other clustering algorithms from the comparison between Table II and Table III. Besides, we can observe in Table III that the rank of hierarchical clustering with weighted average linkage significantly decreases when the data set size increases as in Table II.

In Fig. 3, we show the relation between the average IGD value of the obtained subsets and the average computation time of each algorithm on the eight-objective data sets. The normalization is performed in the same manner as in Fig. 2.

We can see from Fig. 3(a) that greedy IGD-based subset selection and hierarchical clustering with weighted average linkage are non-dominated to each other. Although greedy IGD-based subset selection can achieve the best IGD performance, it uses a much longer computation time than hierarchical clustering. Hierarchical clustering with weighted average linkage is a cheaper alternative with a slight performance deterioration. In Fig. 3(b), we can see that K-means++ and greedy IGD-based subset selection are non-dominated to each other. All the other algorithms are dominated by K-means++ in Fig. 3(b).

On the eight-objective data sets, greedy IGD-based subset selection always achieves the best IGD performance among the examined algorithms. If the computation time is severely limited, hierarchical clustering with weighted average linkage is a cheaper alternative when the data set size is small, and K-means++ is a cheaper alternative when the data set size is large.