Multi-Objective Optimization Techniques with Evolutionary Algorithms, and Application to Better Data Clustering

This text is my final-year project (2022). The results cited at the end of section 7 are the ones published by the authors of MOCLE.

Summary

The beauty of data science lies in finding simple approaches or solutions to practical problems, which are first carefully modeled, for instance as an objective function for optimization problems.

For the simplest cases, meaning problems with a single objective function, very effective algorithms already exist, such as gradient descent algorithms, the simplex method, branch and bound…

But because most practical problems are multi-objective by nature, Multi-Objective Optimization stands out as a major research field. In other words, most real-world problems are not about optimizing a single criterion, but about optimizing several criteria at once, which are often contradictory. This generally means having to find a compromise between technical requirements and cost objectives.

In the same way, each conventional clustering method optimizes only a single grouping criterion (compactness, connectivity, density…) and therefore only recovers a single type of cluster. But many real-world datasets have a heterogeneous structure, where each group answers to a different criterion, and may even show several relevant structures at once.

Thus, for Multi-Objective Optimization, the task will first be to :

• learn about modeling multi-objective problems and existing Multi-Objective Optimization techniques, especially Pareto approaches ;
• understand the concept of evolutionary algorithms and how they are used to solve multi-objective problems following Pareto approaches.

And regarding clustering, it will be about :

• carrying out a thorough survey of the tools used for clustering today, whether the standard hard or soft clustering methods, or more advanced ones such as clustering ensembles ;
• understanding to what extent clustering problems can be translated into multi-objective problems ;
• finding out how the latter are solved with the help of evolutionary algorithms.

The end goal is to show how MOCLE manages to combine these threads to cluster data effectively.

The Optimization Problem

Definition

An optimization problem is defined by :

• a search (decision) space, made up of the set of solutions or configurations. Each solution consists of the different values taken by the decision variables, which can be scalar or vector-valued ;
• one or more so-called objective function(s), to be optimized (minimized or maximized) ;
• a set of constraints to satisfy.

An Example : The Production Plan

The company mx, which specializes in manufacturing computer hardware, offers hundreds of computer models in its catalog. To keep things simple, we will only look at two types of computers here : the MX1 and the MX2. Each of them has one processor (the same one), but the two models differ in particular in the number of memory sticks. Specifically, the MX1 has 2 sticks while the MX2 has 6.

The market for these components is such that no more than 10,000 processors can be bought from the usual suppliers for the coming quarter, and no more than 48,000 memory sticks.

Another constraint is likely to affect production. Assembly is characterized, in particular, by a delicate operation, which takes 3 minutes for the MX1 but only 1 minute for the MX2 ; a priori, only 24,000 minutes are available for assembling these two types of machines over the coming quarter.

Finally, given current market conditions, a profit of 400 euros can be expected on the MX1 and 800 euros on the MX2.

The problem is to determine the quantities of each of the two types of computers to manufacture so as to obtain the greatest possible profit.

Modeling and Solving

The decision variables. The decisions concern the quantities to manufacture, which are naturally represented by two positive numbers, x₁ for the MX1 and x₂ for the MX2.

The constraints. The first concerns the limit on the number of available processors : each machine uses one processor, and 10,000 are available. We must therefore impose : x₁ + x₂ ≤ 10,000. Likewise, the number of memory sticks is limited. Given the number of sticks in each of the 2 computers and the number of sticks available, this constraint translates to : 2x₁ + 6x₂ ≤ 48,000. Finally, the constraint on assembly time is written : 3x₁ + x₂ ≤ 24,000.

The set of possible decisions is therefore characterized by the set of values of x₁ and x₂ satisfying :

The objective function. We want to maximize profit, which is represented by : 400x₁ + 800x₂.

Full model :

The resulting model is an example of a linear programming problem, with a single objective function. Its optimal solution is x₁ = 3,000 and x₂ = 7,000, for a profit of 6,800,000 euros. Had this been a multi-objective problem, there would have been at least two objective functions.

The Basics of Multi-Objective Optimization

In Multi-Objective Optimization, the notion of a single optimal solution disappears in favor of the notion of a set of Pareto-optimal solutions.

Multi-Objective Optimization problems are much harder to handle than their single-objective counterparts. The difficulty lies in the absence of a total order relation between solutions. One solution can be better than another on some objectives and worse on the others. So there is generally no single solution that satisfies every objective function.

There are two different ways to classify approaches to this type of problem. The first classification takes a decision-maker's point of view : approaches are classified according to the intended use. The second takes a designer's point of view : approaches are sorted by how they handle the objective functions.

Classification from the Decision-Maker's Point of View

1. A priori approaches : the decision-maker steps in upstream of the optimization process, to define the aggregation function that models the compromise sought between the different objectives. In this case, the decision-maker is assumed to know the weight of each objective in advance, in order to blend them into a single function. This amounts to solving a single-objective problem. However, in most cases the decision-maker cannot clearly express their utility function, because the different objectives are not commensurable (expressed in different units).
2. Interactive approaches : they combine the decision and optimization processes cyclically and incrementally : the decision-maker steps in to modify certain variables or constraints in order to steer the optimization process. The decision-maker thus interactively adjusts the compromise between their preferences and the results. This approach therefore properly accounts for the decision-maker's preferences, but requires their presence throughout the search process.
3. A posteriori approaches : they aim to provide the decision-maker with a set of good, well-spread solutions. They can then, looking at the whole set of solutions, select the one that seems most appropriate. This way, there is no longer a need to model the decision-maker's preferences (which can prove difficult), but in exchange a set of solutions must be provided, which could be difficult and require significant computing time (but does not require the decision-maker's presence).

Classification from the Designer's Point of View

This classification takes a more theoretical view, built around the notions of aggregation and Pareto optimum. Approaches used to solve multi-objective problems can be sorted into two categories.

Non-Pareto Approaches

They do not treat the problem as a genuine multi-objective problem. They seek to reduce the original problem to one or more single-objective problems. The first question is how to merge the different objective functions when using genetic algorithms, since in the end, fitness is computed from a single formula.

• The weighted sum method : in this method, the different objective functions must be combined into a single expression, from which the fitness of individuals can be computed. It is the best known of the non-Pareto approaches. But first, the values of all objective functions must be brought to the same scale. For two objective functions, we can write :
  J = w₁ · OBJ₁ + w₂ · OBJ₂ = w₁ · OBJ₁ + (1 − w₁) · OBJ₂

  with OBJ₁ and OBJ₂ the two objective functions, weighted by w₁ and w₂ ; J is the final objective function to be used. Although the weighted sum method is simple and easy to use, it has two inherent problems. First, it is difficult to choose weights for objectives that have different orders of magnitude ; as a result, the search for a compromise solution is biased. Second, if the Pareto front is not convex, no set of weights can reach the solutions located in its non-convex parts.

• The global criterion method : it is used to turn the optimization of several objectives into the optimization of a single one, by minimizing the distance between the objective vector and a reference point. The reference point is an ideal solution.
• The ε-constraint method : it optimizes a single objective while the other objectives are turned into constraints. The vector ε sets the limit (an upper bound in the case of minimization) for each of these objectives. For a given vector ε, this method finds one optimal solution ; by changing ε, several optimal solutions can be obtained. The drawback of this method is that there is no feasible solution for certain vectors ε.
• The lexicographic method : decision-makers are asked to rank the objective functions by order of importance. The optimization process is carried out on each objective individually, following this order. After optimizing the most important objective (the first one), if a single solution is returned, then that solution is the optimal one. Otherwise, optimization continues on the second objective, with new constraints derived from the solution obtained for the first objective. This cycle continues until the last objective.

Pareto Approaches

They do not transform the problem's objectives : they are all treated alike throughout the solving process. In other words, fitness is computed from all the objective functions. For each of the retained solutions, it then becomes impossible to improve one objective without worsening at least one other. More precisely, the goal is to optimize k objective functions simultaneously.

• The k objective functions can all be maximization, all minimization, or a mix of both.
• The objective functions can be linear or non-linear, continuous or discrete.
• The objective function is a mapping from the vector of decision variables to the vector of objectives.

The task is therefore to find the vector x = [x₁, x₂, …, x_N] of decision variables such that it satisfies :

• the m inequality constraints : g_i(x) ≥ 0, i = 1, 2, …, m ;
• the p equality constraints : h_j(x) = 0, j = 1, 2, …, p ;

(defining the boundaries of the feasible domain) while optimizing the vector of functions f(x) = [f₁(x), f₂(x), …, f_k(x)]. This leaves us with a wide range of solutions, and the task is then to define an order relation between these elements. The most famous and most widely used is Pareto dominance.

Dominance and the Pareto Front

• Notion of dominance : a solution x is said to dominate a solution y if it is at least as good on every objective function, and strictly better on at least one of them. When all objective functions are expressed as minimization problems, this is written :
  • ∀ i ∈ {1, 2, …, k}, f_i(x) ≤ f_i(y)
  • ∃ i ∈ {1, 2, …, k}, f_i(x) < f_i(y)
• Notion of non-dominance : within a given set of solutions (for example a population), a solution x is said to be non-dominated if no other solution in that set dominates it.
• Pareto optimum : a solution x* is said to be Pareto-optimal if and only if there is no x that dominates it (with x ranging over the feasible solutions). A Pareto-optimal solution is therefore non-dominated within any set that contains it ; the converse is false. When Pareto points are plotted in objective space, the non-dominated solutions trace out the Pareto front.

Important points for determining the Pareto-optimal solution :

• Anchor point : the best solution for a single objective function taken in isolation. Anchor points form the endpoints of the Pareto front. They are the two outermost green points on the diagram.
• Utopia point (or ideal point) : the point obtained from the best value of one objective function and the best value of the other. It is the cross on the diagram. It is generally not feasible, but it plays a decisive role in the search for the optimal solution.
• Optimal point : every point on the front is Pareto-optimal ; if only one is to be kept, a common rule is to take the point on the front that minimizes its Euclidean distance to the utopia point. It is the circled point on the diagram.

But first, how is this set of solutions generated ?

Evolutionary Algorithms

Evolutionary algorithms are a family of algorithms whose principle draws on the theory of evolution to solve various problems. They are therefore computational methods inspired by how living beings behave in nature. It is one of the methods that offers us a wide range of optimal, or more or less optimal, solutions, depending on the case.

The idea is to evolve a set of solutions to a given problem, with a view to finding the best results. These are so-called stochastic algorithms, because they iteratively use random processes.

The Main Families

• Genetic algorithms : the most popular type. The solution to a problem is sought in the form of a list of numbers (traditionally binary). However, the best representations are generally those that truly reflect the problem being solved, for example decimal representations or character strings.
• Genetic programming : here, solutions take the form of computer programs, and their fitness is determined by their ability to solve a computational problem. Many variants exist.
• Evolutionary programming : similar to genetic programming, but the program's structure is fixed and its numerical parameters can evolve.
• Evolution strategies : work with vectors of real numbers as solution representations and generally use self-adaptive mutation rates.
• Differential evolution : based on vector differences, and therefore mainly suited to numerical optimization problems.
• Neuroevolution : similar to genetic programming, but the genomes represent artificial neural networks by describing their structure and connection weights. Genome encoding can be direct or indirect.
• Learning classifier systems : here, the solution is a set of classifiers (rules or conditions). A Michigan-style LCS evolves at the level of individual classifiers, while a Pittsburgh-style LCS works with populations of classifier sets.

The Four Steps

• Initialization : this starts by working out how to represent an individual (a potential solution), and then how to compute its fitness based on the objective function, in order to generate a population in the form of a list [individual → fitness].
• Selection : choosing which individuals in the population will serve as parents, favoring those with better fitness ; this is the step where the objective function steers the search. Methods vary : tournament selection (a few individuals are drawn at random and the best is kept), roulette-wheel selection (probability proportional to fitness), rank selection… Parents are then paired up.
• Crossover : crossing the genomes of each pair of parents, to create one or more new individuals : the offspring.
• Mutation : centered on the individual, it simply alters its genes according to given probability thresholds.

Given these principles, this is clearly a case of approximate search. The effectiveness of genetic algorithms rests on a balance : selection concentrates the search around the best individuals (intensification), while random initialization, crossover and mutation keep the population varied (diversification). Without this diversity, the population converges prematurely on a local optimum.

General Outline

Build and evaluate an initial population (initialization)
Until a stopping criterion is reached:
    select part of the population,
    cross the selected individuals,
    mutate the offspring,
    compute the fitness of each individual,
    update the population with the new individuals.

Convergence

The advantage of this type of algorithm is that a solution is guaranteed at the end. What can then be discussed is the optimality of that solution. But the fact is that the longer the algorithm is left to run, the higher the chances of landing on a good, better solution as iterations go by. Beyond that, given the complexity of the problem, a compromise has to be struck between the resources allocated to it and the desired level of optimality.

Evolutionary Algorithms in Multi-Objective Optimization

Because evolutionary algorithms are population-based, they are easy to extend to handle several objectives. By contrast, traditional search and optimization methods such as gradient descent are difficult to use for multi-objective problems, since they generally handle a single function and, likewise, a single solution.

Because of the growing interest in multi-objective problems, researchers have also developed new evolutionary algorithms suited to solving them.

NSGA (Non-Dominated Sorting Genetic Algorithm)

The "non-dominated" in its name already points to Pareto non-domination. NSGA is indeed a method for solving multi-objective problems based on evolutionary algorithms.

The algorithm uses the classic evolutionary process, with its selection, genetic crossover and genetic mutation operators. The difference lies in selection : the population is first sorted into successive fronts by Pareto dominance, and an individual's fitness depends on its front. Then, within each front, similarity between members is evaluated and the fitness of individuals that are too close to one another is reduced (fitness sharing), to promote a diversified front of non-dominated solutions.

NSGA-II

This is an improved version of NSGA. Individuals are ranked and selected by front. In doing so, there will be cases where a front has to be split because not all of its individuals are allowed to survive. Within the front being split, solutions are selected based on crowding distance. Its algorithm runs as follows :

1. Population initialization : initialize the population according to the problem's range and constraint(s).
2. Non-dominated sorting : a sorting process based on non-domination criteria between individuals, who are then ranked across several fronts according to their rank in the sort. The first front consists of the individuals who are non-dominated in the current population, and individuals in the second front are only dominated by individuals in the first front. The goal is for front 1 to converge toward the Pareto front. In terms of ranking, individuals in the first front then hold rank 1, those in the second rank 2, and so on. For each individual p, we compute :
   • the domination count n_p, representing the number of individuals (solutions) that dominate the current p (the n_p of every individual in the first front is 0) ;
   • S_p, the set of solutions dominated by individual p.

3. Sorting based on crowding distance : the crowding distance of a solution provides an estimate of the density of solutions around it. For each objective, it is the distance between its two neighboring solutions, normalized by the objective's range ; these values are summed over all objectives. It is computed within a single front, and the front's two extreme solutions receive an infinite distance, which guarantees they are kept. Thus, for selection, each individual is characterized by two attributes : its non-domination rank and its crowding distance. Sorting favors higher distances, that is, individuals from less crowded regions, which pushes toward an even spread of solutions along the front. However, rank nd takes precedence over rank cd.

   NB : crowding distance between two individuals from different fronts is not defined. Read cd for crowding distance and nd for non-domination rank.

4. Selection : individuals are selected using binary tournament selection with the crowded-comparison operator ≺_n.
5. Genetic operators : genetic operators such as simulated binary crossover and polynomial mutation are used.
6. Replacement (elitism) : the offspring population and the current generation's population are merged, then re-sorted ; the N best individuals are kept (by rank, then by crowding distance). The process then repeats for a number of generations set as a parameter of the algorithm.

Clustering Techniques

Clustering algorithms are part of the unsupervised learning methods, letting the machine learn by itself from the data it is given. They pick out similarities in that data so it can then be structured. And studying the similarities between the individuals in a dataset makes it possible to split them into different groups : this partitioning of individuals is called clustering.

For each method, it is important to choose how to measure the similarity of two individuals, which can be represented as two points in d-dimensional real space. This is where distance functions come in (e.g., Euclidean distance).

Clustering methods fall into two broad categories : hard clustering and soft clustering. The difference between the two is that hard clustering only lets a point belong to a single cluster, while soft clustering allows the same point to belong to more than one cluster.

Hard Clustering

Hard clustering methods are the most widely used, and clustering methods are sorted into 4 categories according to what they consider a cluster to be :

Centroid-based methods. In this type of grouping method, each cluster is referenced by a vector of values, the centroid. The distance between the input point and each of the centroids is then computed. Each object joins the cluster whose centroid is closest, compared with the other clusters, but the main constraint of this type of algorithm is that the number of clusters must be set in advance.

E.g., K-Means : the most classic centroid method is K-Means. It only needs a single starting choice : k, the desired number of clusters.

1. The algorithm is initialized with k points picked at random among the n individuals.
2. These k points then represent the k clusters. Each of the (n − k) remaining points is then assigned to the closest "point-class". At the end of this step, each class is characterized by the mean of the values of each of its individuals. There are k means for k classes.
3. The third step evaluates the distance from each individual to each of the k means. Some individuals may change class here. At the end of this step, the k means are updated. These steps are then repeated until convergence, to obtain the final k clusters.

These final classes often depend heavily on the k individuals chosen for initialization. This is why some implementations of K-Means iterate the process several times with different initializations, in order to keep the partition that most minimizes within-class variance (the sum of squared distances between the individuals of a class and its centroid).

Density-based methods. These algorithms generate clusters based on the high density of a dataset's members at a given location. They use a notion of distance and a density threshold to group members into clusters. This type of process can perform worse when clusters have very different densities.

E.g., DBSCAN (Density-Based Spatial Clustering of Applications with Noise) : besides forming classes of individuals, the algorithm also picks out unusual values along the way, which are labeled as noise.

Inputs :

• ε : the maximum distance that can define two individuals as neighbors ;
• minPts : the minimum number of points required for a region to be considered dense.

Outputs : density-based clusters (+ noise). Each point is either :

• a cluster's core point : has at least minPts points in its neighborhood ;
• a border point : not a core point, but has at least 1 core point in its neighborhood. In other words, it belongs to a given cluster ;
• a noise point : neither a core point nor a border point.

Steps :

Pick an unvisited point → is it a core point?
    If yes → create a cluster and expand it step by step
             to every point reachable from its core points
    If no → mark it provisionally as noise
             (it may later become a border point of a neighboring cluster)
Repeat until every point has been visited.
Points still marked as noise are discarded.

HDBSCAN (Hierarchical DBSCAN) was designed to address the main drawback of DBSCAN, the choice of ε (and its inability to find clusters of different densities) ; it builds a hierarchy of clusters across every density value and then extracts the most stable ones.

Connectivity-based methods (hierarchical methods). They build connections between individuals step by step, for agglomerative hierarchical clustering methods. For divisive hierarchical clustering methods, they break the groups apart into several (starting from the initial group containing every individual). In the first type, each object is linked to its neighbors, and clusters are defined by grouping the closest neighbors together based on the strength of this relationship and the distance separating them. The distance function between two groups varies according to the chosen linkage criterion (single linkage, complete linkage, average linkage, Ward's criterion). A dendrogram is used to bring out the clusters.

Distribution-based methods. This methodology groups together objects whose values appear to come from the same probability distribution, for example a Gaussian (a mixture of Gaussians fitted with the EM algorithm). Because of its probabilistic nature, this process requires a well-defined model to fit real data properly. Note that these methods actually produce membership probabilities : they belong to soft clustering, which is hardened by assigning each point to the most likely distribution.

Soft Clustering

There are various approaches that can be considered soft clustering. The best known is fuzzy clustering.

Fuzzy C-Means (Bezdek, 1981), or Soft K-Means (because of its similarity to K-Means). This flagship fuzzy clustering method assigns objects to clusters with degrees of membership in the unit interval, based on the dissimilarities between each object and every prototype.

For example, with hard clustering via K-Means, an individual can be classified as being of a single origin (represented as a class) : French or British. But a person can also be both French and British (fuzzy clustering). Here, the person can be French to a certain degree and British to a certain degree. Instead of the person belonging to British [British = 1] and not to the French class [French = 0], they can belong to French [French = 0.5] and also to British [British = 0.5].

These values lie between 0 and 1 ; in Fuzzy C-Means, they are constrained to add up to 1 for each individual (it is the possibilistic variant, Possibilistic C-Means, that relaxes this constraint). Principle :

• Choose a number of clusters.
• Choose the fuzziness parameter m > 1 (often m = 2 ; the larger m is, the more shared the memberships are) and ε, the convergence threshold.
• Randomly assign each point a membership coefficient for each cluster.
• Repeat these two sub-steps until the algorithm converges (the difference in coefficients between two iterations falls below ε) :
  • compute the center of each cluster ;
  • for each point, compute its membership coefficients for the clusters.

Advanced Clustering Methods

In the previous section, we saw that almost every existing clustering algorithm works from a single grouping criterion, that is, the selection of a structure (or a model) to represent the clusters that best fits the dataset being analyzed. For example, algorithms that look for compact clusters, such as K-Means, are biased toward spherical data.

What makes clustering even more complicated is that the same data can have more than one relevant structure, each representing a different interpretation of the data. Each of these structures may agree with a definition of a cluster or with a particular grouping criterion. Aside from robustness, which is one of their major challenges, clustering techniques face many other challenges and difficulties, such as predicting the right number of clusters, scalability, choosing the right similarity measure, and identifying noisy points.

To solve this problem, combining clustering results is considered a good alternative. This gives us different structures as output. A validation step then follows, to select the structure that best fits the data. Here too, the bias of validation methods has to be taken into account. And once we are talking about different conformations, we can start drawing a connection with the notion of multi-objective. Two approaches exist to address this.

Cluster Ensemble Principles

This single-objective method aims to combine several hard clustering models, to generate several partitions of individuals, each coming from a specific clustering, and to combine them to generate a consensus partition via a consensus function. An ensemble is said to be homogeneous if all base partitions are generated by the same clustering algorithm, otherwise it is heterogeneous.

Reminder : a partition of a set E is a family of non-empty subsets of E, pairwise disjoint, whose union is the set E.

The best known is the Strehl and Ghosh ensemble, detailed below. Consider a dataset of I points P = {P₁, P₂, …, P_I}, with i = 1…I. An ensemble combines J clusterings, and is represented as Π = {π₁, π₂, …, π_J}. Each clustering π_j (clustering solution) is simply a partition of the dataset P into K_j disjoint clusters of instances, with j = 1…J. Each π_j contains K_j groups and is represented as π_j = {G₁^j, G₂^j, …, G_Kj^j}, with G denoting the groups or clusters, k = 1…K_j.

Partition Formulation and Encoding

For Strehl and Ghosh, finding the consensus partition is treated as a combinatorial optimization problem : finding the partition that shares the most mutual information with the base partitions. Strehl and Ghosh solve it with heuristics (the consensus functions below) ; the combinatorial approach also lends itself to genetic algorithms for solving it, as in Luo, Jing and Xie (2006).

Modeling individuals. Let P = {P₁, P₂, …, P_n} be the set of points in the dataset, which will be partitioned differently by clustering. It is the shape of each of these partitions that matters here : this is what will represent the individuals. E.g. : suppose a dataset of 8 points P₁, …, P₈. Since a partition is the result of a clustering, suppose the latter generated 3 classes such that : P₁ → class 1, P₂ → class 3, P₃ → class 1, P₄ → class 3, P₅ → class 2, P₆ → class 3, P₇ → class 2, P₈ → class 3. This individual X_j would be represented as :

Such a modeling choice makes it easy to bring standard genetic-algorithm operations into the population.

Fitness computation :

NMI is a measure of the mutual information shared between two clusterings (two individuals), to be maximized. This suggests generating new clusterings from existing ones, in order to build a dense population capable of yielding good results through crossovers. This is applied when the number of base partitions is below 20, to densify the population. This choice follows Luo, Jing and Xie (2006), who found that GAs only produce good results when this number is 20 or higher.

Consensus Functions

All these groups are combined using a consensus function Γ, to reach a more representative partition. Examples include :

• CSPA (Cluster-based Similarity Partitioning Algorithm) : CSPA builds a new similarity matrix from the base partitions. The entries of this matrix indicate the fraction of partitions in which two objects are assigned to the same cluster. The matrix is then used to group the objects with any similarity-based clustering algorithm, producing the consensus partition.
• HGPA (Hyper-Graph Partitioning Algorithm) : in the HGPA algorithm, the combination is treated as a hypergraph partitioning problem. The clusters of the base partitions are represented as hyperedges ; the hypergraph is then partitioned by cutting a minimal number of hyperedges.
• MCLA (Meta-Clustering Algorithm) : the clusters of the base partitions are themselves grouped into meta-clusters, then each object is assigned to the meta-cluster where it is best represented. This is the operator MOCLE uses.

How consensus functions behave can always prompt a rethink of the ensemble generation process itself. There is another clustering ensemble method for this, based on graph partitioning, called HBGF (Fern and Brodley, 2004), which models objects and clusters as the two sides of a bipartite graph.

NB : CSPA, HGPA and MCLA belong to the family of hypergraph methods. But more broadly, the consensus-function approach is made up of six families of algorithms : hypergraph methods, voting approaches, information-theory methods, co-association-based methods, mixture models, and evolutionary algorithms.

Limits of a clustering ensemble :

• poor-quality base partitions, if numerous, degrade the consensus partition, even if a few are excellent ; likewise, a good cluster present in only one base partition gets "crushed" by the others, so the consensus cannot end up as a heterogeneous structure ;
• the result depends on fine parameter tuning, and the number of clusters often has to be supplied in advance ;
• only a single consensus partition is retained, and searching for a single structure limits the amount of knowledge that could otherwise be gained.

Multi-Objective Clustering

The multi-objective approach is often preferred because it considers different aspects of a dataset, in the form of various objectives. With NSGA and NSGA-II already presented, it should be kept in mind that the objectives need to be in conflict : minimizing within-class inertia and maximizing between-class inertia is not enough, since for a fixed k the two amount to the same thing (total inertia is constant).

MOCK (Multi-Objective Clustering with automatic K-determination), on the other hand, is an algorithm based on Pareto and the PESA-II evolutionary algorithm, able to simultaneously optimize two complementary clustering criteria : overall deviation and connectivity. These two criteria pull the number of clusters in opposite directions, which avoids trivial solutions. In addition, to obtain the best compromise solution from the Pareto front, MOCK compares the shape of the resulting front to that of control fronts computed on random data.

The real question is : with a single clustering, how can enough groups be generated to then choose between them ? True, NSGA diversifies the population, but is the problem really being tackled from the right angle ?

MOCLE : A Multi-Objective Clustering Ensemble

MOCLE stands for Multi-Objective Clustering Ensemble. MOCLE combines the two advanced clustering approaches, which helps offset their own limitations :

• it looks not for one, but for several consensus partitions, and the crossover that produces them can use any consensus function applicable to a pair of partitions ;
• it then combines pairs of partitions iteratively, within an optimization process, instead of the usual combination of all partitions at once. This iterative combination/selection of partitions avoids the negative influence of poor-quality base partitions, which can lower the quality of traditional ensembles' results.

Initial Population and Genetic Operators

Initial population. Let P = {P₁, P₂, …, P_I} be the set of points of the dataset, of size I, which will be partitioned differently by different clustering methods, each with several settings (in particular several values of k). All the resulting partitions are placed into an ensemble. An ensemble built from J clusterings takes the form Π = {π₁, π₂, …, π_J}, with j = 1…J. This ensemble is what forms the initial population.

Recap :

• each partition π_j is split into K_j groups G such that π_j = {G₁^j, G₂^j, …, G_Kj^j} ;
• each individual in our algorithm will be a partition π_j.

NB : the more diverse the algorithms (algorithms that look for compact clusters alongside algorithms that look for connected clusters), the higher the chances of producing a diverse set of clusters. As a result, MOCLE receives as much information as possible to find the largest possible number of existing structures.

Crossover and mutation. MOCLE contains a special crossover operator which, together with the initial population, is responsible for the ensemble-like character of the technique. This operator finds the consensus between two parent partitions. Any existing clustering ensemble method that can be applied to a pair of partitions can be used as the crossover operator (the authors use MCLA).

First, using a binary tournament, two parents are selected to be combined : π_a and π_b, with respectively K_a and K_b clusters. This produces a resulting partition π_c (consensus partition) with at most K_c clusters, K_c being drawn at random within the range of the parents' cluster counts : K_c ∈ [min(K_a, K_b), max(K_a, K_b)].

The consensus partitions generated at each iteration are also considered in later combinations. This iterative combination avoids the negative influence of partitions that do not represent reality well. These poor-quality partitions are gradually eliminated, while the best partitions and the best combinations are kept for later combination.

Up to this point, every group, however many there are, is effectively a cluster, and applying a genetic mutation would mean introducing arbitrary points into a given group : which would no longer reflect reality. Yet MOCLE's primary goal is to generate a concise set of solutions representative of the Pareto front. Because of this, there is no mutation operator, and the search space stays restricted to the base partitions and their combinations.

But When Is Multi-Objective Clustering Introduced ?

Up to this point, a clustering ensemble method is being used. With individuals fully modeled, following this same logic, we would use an objective function based on a score computed from the mutual information shared between two clusterings, that is, a single-objective function, with the clusters coming from hard clusterings.

Multi-objective clustering, on the other hand, even with few clusters, focuses on properly selecting them. It frames them as a multi-objective problem by evaluating each partition against several validation indices at once. What illustrates this is that clustering ensembles were limited to a single measure (NMI), whereas MOCLE reuses MOCK's two objective functions, both to be minimized, and lets NSGA-II (or SPEA) do the sorting on these two criteria :

• overall deviation : the sum of the distances between each object and the center of its cluster. It is biased toward spherical clusters and improves as the number of clusters increases ;
• connectivity : it measures how much neighboring objects are placed in the same cluster (a penalty for each object whose one of its L nearest neighbors is in a different cluster). It detects clusters of any shape, but handles overlapping clusters poorly, and improves as the number of clusters decreases.

Each offsets the other's tendency to change the number of clusters, which avoids convergence toward trivial solutions. Except that with the latter, the more good-quality candidate partitions it had, the more effective the algorithm would be.

Solution : we thus reach the point where the wide range of partitions generated by the clustering ensemble method can simply be handed to the multi-objective clustering problem, which was precisely lacking a set of relevant solutions. From there, trade-offs are made on the Pareto front within the multi-objective framework : the result is not a single partition, but a small set of partitions, each representing a region of the front, among which the domain expert chooses.

Results Published by the Authors

Faceli, de Carvalho and de Souto (2007) evaluate MOCLE on five datasets, each with one or more known structures E_j : a synthetic dataset (ds2c2sc13, 588 points, three nested structures with 2, 5 and 13 clusters), two UCI reference datasets (glass, iris) and two gene-expression datasets (leukemia, lung). The initial population comes from K-Means, average linkage, single linkage and SNN. Quality is measured by the corrected Rand index (CR) between each known structure and the closest partition in the solution set (1 : perfect match ; 0 : random partition), averaged over 30 runs for the non-deterministic methods (KM, MOCK, ES and MOCLE ; AL, SL and SNN only have a single solution set). KM, AL, SL and SNN are the individual algorithms, MK is MOCK (full front), ES is the Strehl and Ghosh ensemble, MN and MS are MOCLE with NSGA-II and with SPEA.

No individual algorithm is good everywhere : for each structure, a different algorithm gets the best score. MOCLE, without any algorithm having to be chosen, matches or beats the best individual algorithm in 60% of cases, MOCK in 70% and ES in 80%, according to the authors. It does fall noticeably short of the best on two structures, though : E3 of ds2c2sc13 (0.78 versus 1 for SNN) and E1 of leukemia (0.28 versus 0.68 for K-Means). Its solution set is also much more concise than MOCK's front (on ds2c2sc13 : 114 initial partitions, 81 in MOCK's front, 30 for MOCLE ; on iris : 20, 69 and 7) and stable from one run to the next.

Conclusion

The no free lunch theorems (Wolpert and Macready, 1997) state that, averaged over every possible problem, no optimization method does better than another ; each is only good on a specific class of problems.

In light of all the above, MOCLE is a fine illustration of how several pre-existing methods can work together to produce a better one, one that best solves a given problem : here, clustering. This is achieved through the clustering ensemble method, which builds on existing hard clustering techniques and a consensus function to supply a diverse batch of clustering solutions, usable by multi-objective clustering, which in turn handles the validation procedure in detail, with two complementary validation indices and an algorithm such as NSGA-II that embraces not only the philosophy of genetic algorithms, but also optimization in the Pareto sense.

Bibliography

1. Optimisation multi-objectif et problèmes d'optimisation multi-objectifs
2. Overview and simple applications
3. A Hands On Intro To Multi Objective Optimisation
4. Review of Multiobjective methods
5. Optimum de Pareto
6. Evolutionary Algorithm (Wikipedia)
7. Genetic Algorithms and Multi-Objective Optimisation
8. Comparison between GA, NSGA and NSGA II
9. Multiobjective optimization of cluster measures in Microarray Cancer data using Genetic Algorithm Based Fuzzy Clustering (PDF)
10. Clustering Algorithms
11. Unsupervised soft clustering methods
12. Exploring Clustering Algorithms: Explanation and Use Cases
13. GA and K-means for clustering
14. Clustering ensemble method
15. A Weighted Consensus Function to Combine Soft Clusterings
16. Consensus functions for cluster ensembles
17. Multi-objective clustering
18. Multi-objective clustering
19. Multiobjective clustering algorithm for complex data
20. K. Faceli, A. C. P. L. F. de Carvalho, M. C. P. de Souto, "Multi-objective clustering ensemble", International Journal of Hybrid Intelligent Systems, vol. 4, no. 3, pp. 145–156, 2007.
21. MOCLE Implementation (GitHub)
22. N. Srinivas, K. Deb, "Multiobjective optimization using nondominated sorting in genetic algorithms", Evolutionary Computation, vol. 2, no. 3, pp. 221–248, 1994.
23. K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II", IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.
24. E. Zitzler, L. Thiele, "Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach", IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, pp. 257–271, 1999.
25. J. Handl, J. Knowles, "An evolutionary approach to multiobjective clustering", IEEE Transactions on Evolutionary Computation, vol. 11, no. 1, pp. 56–76, 2007.
26. A. Strehl, J. Ghosh, "Cluster ensembles – a knowledge reuse framework for combining multiple partitions", Journal of Machine Learning Research, vol. 3, pp. 583–617, 2002.
27. X. Z. Fern, C. E. Brodley, "Solving cluster ensemble problems by bipartite graph partitioning", Proceedings of the 21st International Conference on Machine Learning (ICML), 2004.
28. H. Luo, F. Jing, X. Xie, "Combining multiple clusterings using information theory based genetic algorithm", Proceedings of the International Conference on Computational Intelligence and Security, vol. 1, pp. 84–89, 2006.
29. M. H. C. Law, A. P. Topchy, A. K. Jain, "Multiobjective data clustering", Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2004.
30. D. H. Wolpert, W. G. Macready, "No free lunch theorems for optimization", IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 67–82, 1997.
31. J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, 1981.

Illustrations : all figures are redrawn as SVG from those in the report (synthetic data or the iris dataset, algorithms reimplemented for the comparison grid and for Fuzzy C-Means). Both NSGA-II diagrams are redrawn after Deb et al. (2002).