$(3)$ Clustering $(25$ marks$)$The class Clustering implements a k$-$means algorithm adapted from $[1,2].$ The class has a single public method:$>$ static Cluster$[]$ kmeans$($FeatureVector$[]$ examples, int k$)$This problem is known to be difficult to solve exactly when the number of examples is large. The k$-$means algorithm is an approximate method that makes the "best" local choice at each iteration without consideration of the global solution of the problem. We call this a "greedy" strategy.Comparing the examples to the centroid of the clusters reduces considerably the total number of comparisons as it avoids comparing all$-$against$-$all examples and the number of centroids $($clusters$)$ is generally small. This makes the k$-$means algorithm quite efficient.Input:The input consists of n examples $($objects of the class FeatureVector$)$ and k$,$ the number of clusters to be produced.Output:A partition of the n input examples into k groups $($clusters$).$ The partition is such that the elements of the same cluster are closer to the centroid of the group than they are from the centroid of other clusters.Algorithm:$*$ Initialization Create k clusters and let D designate this set of clusters such that Di is the i$-$th cluster of D$.$Randomly select, without replacement, k examples from the n input examples.Each randomly selected example becomes the centroid of a cluster. Repeat Create k clusters and let D$\text{'}$ designate this set of clusters. For each input example e: If the distance from e to the centroid of Di is minimum., assign e to D$\text{'}$i where D$\text{'}$i designates the i$-$th cluster of D$\text{'}.$ Updating D$.$Compare the corresponding clusters of D and D$\text{'}.$ If the size or the centroid has changed, then the respective cluster of D$\text{'}$ replaces that of D$.*$ If none of the clusters have changed, the algorithm terminates and returns the current clusters.$*$ Otherwise, the algorithm resumes