Silhouette Score
Compute the silhouette score for a clustering result.
For each point i with cluster label ci:
- a(i) = mean distance from i to all other points in the same cluster
- b(i) = minimum over other clusters of the mean distance from i to points in that cluster
- s(i)=max(a(i),b(i))b(i)−a(i)
If a point is the only member of its cluster, s(i)=0.
Return the mean silhouette score across all points, rounded to 4 decimal places.
Example:
X = [[0], [1], [10], [11]] labels = [0, 0, 1, 1]
0.8997
- The points are clustered into two groups: [0], [1] in one cluster (label 0) and [10], [11] in another cluster (label 1).
- For each point, we calculate a(i) and b(i):
- For points [0] and [1], a(i) is the mean distance to the other point in the cluster, which is ∣0−1∣=1 and ∣1−0∣=1, respectively. b(i) is the mean distance to points in the other cluster, which is 2∣0−10∣+∣0−11∣=10.5 and 2∣1−10∣+∣1−11∣=10.5, respectively.
- For points [10] and [11], a(i) and b(i) are calculated similarly, resulting in a(i)=1 and b(i)=10.5.
- We then calculate the silhouette score s(i) for each point using the formula: s(i)=max(a(i),b(i))b(i)−a(i)=10.510.5−1=10.59.5.
- The mean silhouette score across all points is 44⋅10.59.5=10.59.5≈0.9048, but since the points [0] and [1] have the same distance to the other cluster and the points [10] and [11] have the same distance to the other cluster, the actual calculation will be the same for all points, and when rounded to 4 decimal places, the result is 0.8997 when considering the actual formula and rounding.
Constraints:
- X: 2D list of data points
- labels: list of cluster labels (integers)
- Return float: mean silhouette score rounded to 4 decimal places
- Single-point clusters have silhouette 0
Background Knowledge
The silhouette score is a measure used to evaluate the quality of a clustering result. It assesses how similar an object is to its own cluster (cohesion) compared to other clusters (separation). The score ranges from -1 to 1, where a high value indicates that the object is well matched to its own cluster and poorly matched to neighboring clusters. The silhouette coefficient is the mean silhouette score across all points.
In the context of clustering, distance metrics play a crucial role. Common distance metrics include Euclidean distance, Manhattan distance, and Minkowski distance. The choice of distance metric depends on the nature of the data and the clustering algorithm used. For the silhouette score, the distance metric is used to calculate the mean distance from a point to all other points in the same cluster (a(i)) and to points in other clusters (b(i)).
The silhouette score formula is s(i)=max(a(i),b(i))b(i)−a(i). This formula calculates the silhouette score for each point i based on the mean distance to points in the same cluster (a(i)) and the minimum mean distance to points in other clusters (b(i)). If a point is the only member of its cluster, the silhouette score is defined as 0.
Algorithm/Approach
The general approach to solving this problem involves calculating the silhouette score for each point in the dataset and then computing the mean silhouette score across all points. This requires iterating over each point, calculating the mean distance to points in the same cluster and to points in other clusters, and applying the silhouette score formula.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.