Demo for the PlutoCon 201

Author: Daniel Molina Cabrera

Talk: Teaching Computer Sciences and Metaheuristics Algorithms using Pluto

Grouping with constraints Problem

In this problem there is a dataset with N instances that represent numerical vectos, and it is wanted to group them in k clusters.

The target is select the clustering considering:

1. Fulfil as much as possible a number of constraints (several pairs of instances must be in the same clusters, they are listed in list ML, and another pairs of instances that have to be in different clusters, in list CL).

• ${\displaystyle infeasability=\begin{array}{l}{\displaystyle \sum _{i=0}^{|ML|}bool2int(hc(\overrightarrow{M{L}_{[i,1]}})\ne hc(\overrightarrow{M{L}_{[i,2]}}))}\\ +bool2int(hc(\overrightarrow{C{L}_{[i,1]}})=hc(\overrightarrow{C{L}_{[i,2]}}))\end{array}}$

2. Reduce the intra-cluster distance:

• For each cluster i it is calculated its centroid (median of the instances member of that cluster): ${\displaystyle \overrightarrow{{\mu }_i}=\frac{1}{c}\sum _{\overrightarrow{x_j}\in c_i}\overrightarrow{x_i}}$

• The instra-cluster distance is calculate with ${\displaystyle \overline{c_i}=\frac{1}{|c_i|}\sum _{\overrightarrow{x_j}\in c_i}||\overrightarrow{x_j}-\overrightarrow{{\mu }_i}|{|}_2}$.

Initial problem:

Giving several points like following:

n:

Problem: number k and constraints

k:

|ML|: |CL|:

There are several constraints between groups

ML: {(4, 2), (9, 4), (8, 3)}

CL: {(6, 2)}

We represent visually the constraints that have to be in the same cluster with a continuous line, and with a dashed line which have to be in different clusters.

Initial solution:

A initial solution is a partition, represented by a vector of length N, in which each position i has a value between 1 and k, the value represent the cluster assigned to the instance i.

We remark with different colors each clustering, indicating in the title how many constraints are violated, and the average inter-clustering distance.

Greedy Algorithm

The Greedy algorithm build a solution step by step. The process is as follow:

1. Randomly generate K clusters.

Seed:

2. For each element it is selected the cluster closer than violate less constraints.

clusters: {0.012378843419466268, 0.45516843007784, 0.9078498956593186, 0.971215649338451, 0.8445317509734542, 0.36848703579346}

3. If the centroids should be updated, recalculate it and go to step 2.

The final solution obtained is:

Meta-heuristic

To be able to apply the simple meta-heuristic we need a only objective function, thus we are going to join both criteria in a only fitness function.

The measure is defined as $\overrightarrow{C}+(infeasability\cdot \lambda )$, as a combination of the intra-cluster distance with a $\lambda$ penalty for each constraints that is not fullfil.

The first action is to calculate $\lambda$, defined ass the maximum distance between two points and divided by the total of constraints: ${\displaystyle \lambda =\frac{Max(Dis{t}_{ij})}{R},\mathrm{\forall }i,j\in \{1,...,n\}}$

$\lambda$ value: 0.23 = 0.9205 / 4

The local search procedure is to randomly choose one position, and change its value (maintaning that for each cluster has at least one member).

In the following there is the convergence graphic, that show the improvement of fitness through the run of the algorithm.