public class SquaredEuclideanSilhouette
extends Object
The Silhouette for each point i
is defined as:
$$ s_{i} = \frac{b_{i}a_{i}}{max\{a_{i},b_{i}\}} $$
which can be rewritten as
$$ s_{i}= \begin{cases} 1\frac{a_{i}}{b_{i}} & \text{if } a_{i} \leq b_{i} \\ \frac{b_{i}}{a_{i}}1 & \text{if } a_{i} \gt b_{i} \end{cases} $$
where $a_{i}$
is the average dissimilarity of i
with all other data
within the same cluster, $b_{i}$
is the lowest average dissimilarity
of i
to any other cluster, of which i
is not a member.
$a_{i}$
can be interpreted as how well i
is assigned to its cluster
(the smaller the value, the better the assignment), while $b_{i}$
is
a measure of how well i
has not been assigned to its "neighboring cluster",
ie. the nearest cluster to i
.
Unfortunately, the naive implementation of the algorithm requires to compute
the distance of each couple of points in the dataset. Since the computation of
the distance measure takes D
operations  if D
is the number of dimensions
of each point, the computational complexity of the algorithm is O(N^2^*D)
, where
N
is the cardinality of the dataset. Of course this is not scalable in N
,
which is the critical number in a Big Data context.
The algorithm which is implemented in this object, instead, is an efficient and parallel implementation of the Silhouette using the squared Euclidean distance measure.
With this assumption, the total distance of the point X
to the points $C_{i}$
belonging to the cluster $\Gamma$
is:
$$ \sum\limits_{i=1}^N d(X, C_{i} ) = \sum\limits_{i=1}^N \Big( \sum\limits_{j=1}^D (x_{j}c_{ij})^2 \Big) = \sum\limits_{i=1}^N \Big( \sum\limits_{j=1}^D x_{j}^2 + \sum\limits_{j=1}^D c_{ij}^2 2\sum\limits_{j=1}^D x_{j}c_{ij} \Big) = \sum\limits_{i=1}^N \sum\limits_{j=1}^D x_{j}^2 + \sum\limits_{i=1}^N \sum\limits_{j=1}^D c_{ij}^2 2 \sum\limits_{i=1}^N \sum\limits_{j=1}^D x_{j}c_{ij} $$
where $x_{j}$
is the j
th dimension of the point X
and
$c_{ij}$
is the j
th dimension of the i
th point in cluster $\Gamma$
.
Then, the first term of the equation can be rewritten as:
$$ \sum\limits_{i=1}^N \sum\limits_{j=1}^D x_{j}^2 = N \xi_{X} \text{ , with } \xi_{X} = \sum\limits_{j=1}^D x_{j}^2 $$
where $\xi_{X}$
is fixed for each point and it can be precomputed.
Moreover, the second term is fixed for each cluster too,
thus we can name it $\Psi_{\Gamma}$
$$ \sum\limits_{i=1}^N \sum\limits_{j=1}^D c_{ij}^2 = \sum\limits_{i=1}^N \xi_{C_{i}} = \Psi_{\Gamma} $$
Last, the third element becomes
$$ \sum\limits_{i=1}^N \sum\limits_{j=1}^D x_{j}c_{ij} = \sum\limits_{j=1}^D \Big(\sum\limits_{i=1}^N c_{ij} \Big) x_{j} $$
thus defining the vector
$$ Y_{\Gamma}:Y_{\Gamma j} = \sum\limits_{i=1}^N c_{ij} , j=0, ..., D $$
which is fixed for each cluster $\Gamma$
, we have
$$ \sum\limits_{j=1}^D \Big(\sum\limits_{i=1}^N c_{ij} \Big) x_{j} = \sum\limits_{j=1}^D Y_{\Gamma j} x_{j} $$
In this way, the previous equation becomes
$$ N\xi_{X} + \Psi_{\Gamma}  2 \sum\limits_{j=1}^D Y_{\Gamma j} x_{j} $$
and the average distance of a point to a cluster can be computed as
$$ \frac{\sum\limits_{i=1}^N d(X, C_{i} )}{N} = \frac{N\xi_{X} + \Psi_{\Gamma}  2 \sum\limits_{j=1}^D Y_{\Gamma j} x_{j}}{N} = \xi_{X} + \frac{\Psi_{\Gamma} }{N}  2 \frac{\sum\limits_{j=1}^D Y_{\Gamma j} x_{j}}{N} $$
Thus, it is enough to precompute: the constant $\xi_{X}$
for each point X
; the
constants $\Psi_{\Gamma}$
, N
and the vector $Y_{\Gamma}$
for
each cluster $\Gamma$
.
In the implementation, the precomputed values for the clusters are distributed among the worker nodes via broadcasted variables, because we can assume that the clusters are limited in number and anyway they are much fewer than the points.
The main strengths of this algorithm are the low computational complexity
and the intrinsic parallelism. The precomputed information for each point
and for each cluster can be computed with a computational complexity
which is O(N/W)
, where N
is the number of points in the dataset and
W
is the number of worker nodes. After that, every point can be
analyzed independently of the others.
For every point we need to compute the average distance to all the clusters.
Since the formula above requires O(D)
operations, this phase has a
computational complexity which is O(C*D*N/W)
where C
is the number of
clusters (which we assume quite low), D
is the number of dimensions,
N
is the number of points in the dataset and W
is the number
of worker nodes.
Modifier and Type  Class and Description 

static class 
SquaredEuclideanSilhouette.ClusterStats 
static class 
SquaredEuclideanSilhouette.ClusterStats$ 
Constructor and Description 

SquaredEuclideanSilhouette() 
Modifier and Type  Method and Description 

static scala.collection.immutable.Map<Object,SquaredEuclideanSilhouette.ClusterStats> 
computeClusterStats(Dataset<Row> df,
String predictionCol,
String featuresCol)
The method takes the input dataset and computes the aggregated values
about a cluster which are needed by the algorithm.

static double 
computeSilhouetteCoefficient(Broadcast<scala.collection.immutable.Map<Object,SquaredEuclideanSilhouette.ClusterStats>> broadcastedClustersMap,
Vector features,
double clusterId,
double squaredNorm)
It computes the Silhouette coefficient for a point.

static double 
computeSilhouetteScore(Dataset<?> dataset,
String predictionCol,
String featuresCol)
Compute the mean Silhouette values of all samples.

static void 
registerKryoClasses(SparkContext sc)
This method registers the class
SquaredEuclideanSilhouette.ClusterStats
for kryo serialization. 
public static void registerKryoClasses(SparkContext sc)
SquaredEuclideanSilhouette.ClusterStats
for kryo serialization.
sc
 SparkContext
to be usedpublic static scala.collection.immutable.Map<Object,SquaredEuclideanSilhouette.ClusterStats> computeClusterStats(Dataset<Row> df, String predictionCol, String featuresCol)
df
 The DataFrame which contains the input datapredictionCol
 The name of the column which contains the predicted cluster id
for the point.featuresCol
 The name of the column which contains the feature vector of the point.Map
which associates each cluster id
to a SquaredEuclideanSilhouette.ClusterStats
object (which contains the precomputed values N
,
$\Psi_{\Gamma}$
and $Y_{\Gamma}$
for a cluster).public static double computeSilhouetteCoefficient(Broadcast<scala.collection.immutable.Map<Object,SquaredEuclideanSilhouette.ClusterStats>> broadcastedClustersMap, Vector features, double clusterId, double squaredNorm)
broadcastedClustersMap
 A map of the precomputed values for each cluster.features
 The Vector
representing the current point.clusterId
 The id of the cluster the current point belongs to.squaredNorm
 The $\Xi_{X}$
(which is the squared norm) precomputed for the point.public static double computeSilhouetteScore(Dataset<?> dataset, String predictionCol, String featuresCol)
dataset
 The input dataset (previously clustered) on which compute the Silhouette.predictionCol
 The name of the column which contains the predicted cluster id
for the point.featuresCol
 The name of the column which contains the feature vector of the point.