# Data Analysis for Information Discovery
## 5 Silhouette Method for Clustering Evaluation  
The performance evaluation of a clustering algorithm is not a trivial task. Indeed, when using a clustering algorithm, it is possible to be in one of the following situations:  
* The correct solution is known: in this case, the classification of each point is known a priori, and the classification performance of the clustering algorithm can be computed counting the number of misclassified patterns (error rate);
* The correct solution is subjective: in this case, there is no true ground against which to evaluate the results of the clustering algorithm. Since the classification is subjective, there is no universally acceptable solution, so the classification task falls into the problem of the semantic gap [38];
* The correct solution is unknown: also in this case, there is no true ground against which to evaluate the results of the clustering algorithm. To face this problem, there are various approaches as reported in [39]. On the other hand, in the latest years, the silhouette parameter has become a more commonly used method for assessing the quality of clusters [40].  
In this work the silhouette parameter has been used to evaluate the clustering performance. This method is based on a comparative evaluation of the similarity level of each object in relation to its cluster (tightness) and to the other clusters (separation). This parameter is defined as follows: if \(y\) is a point belonging to cluster A, then \(t(y)\) is the mean distance between \(y\) and all other points of A. Let us now consider any cluster B, different from A, and compute the average distance between \(y\) and all points of B(\(d(y,\) B)). Once we have computed \(d(y,\) B) for each cluster B such that B \(\
eq\) A, we select the smallest of these numbers and denote it by:  
\[v(y)=\underset{\text{A}\
eq\text{B}}{\text{min}}d(y,\text{B}) \tag{6}\]  
Starting from these considerations, the silhouette for the point \(y\) is defined as shown in the following formula:  
\[s(y)=\left\{\begin{array}{ll}1-\frac{t(y)}{v(y)}&\quad\text{if }t(y)<v(y)\\ 0&\quad\text{if }t(y)=v(y)\\ \frac{v(y)}{t(y)}-1&\quad\text{if }t(y)>v(y)\end{array}\right. \tag{7}\]  
From this definition, it is possible to say that for each point x into the dataset:  
\[-1<s(y)<+1\]  
An in-depth analysis of this parameter is reported in [40].  
On the other hand, using this method makes it possible to show the obtained results using a graphical representation highlighting, for each point, how well it has been classified. Furthermore, the flexibility of this method should be highlighted due to the fact that it is possible to use any kind of distance metric, such as Mahalanobis, Euclidean, Manattan, etc.  
All these features give to the silhouette parameters a strong appeal when it is required to evaluate the performance of a clustering algorithm applied to datasets for which there is no a-priori knowledge (this is also the case study of this paper).  
Another interesting application of the silhouette method is as a reference guide in discovering the optimal number of clusters for a given dataset. This task can be carried out by implementing an iterative process composed of the following steps:  
1. Run the clustering algorithm using a certain number of clusters \"C\";
2. Compute the silhouette for the obtained clusters.  
If there is a satisfying number of points with a good level of silhouette, then \"C\" can be considered a good number of clusters. Otherwise, change the value of \"C\" and return to Step 1.