There is no catch-all metric that can be used for evaluation (internal or otherwise) of the clustering achieved. This is why machine learning is also art. There are no hard limits, many things depend on application, domain, and data themselves.
TL;DR
The purpose of the homework is to familiarise yourself with the problem of clustering, but also with the fact that there is no definite best method nor evaluation metric as panacea for all cases.
As such, you can try various criteria (see below references) on your data and algorithm results and ponder on their effectiveness for your problem at hand.
An Impossibility Theorem for Clustering
Although the study of clustering is centered around an intuitively
compelling goal,it has been very difficult to develop a unified
framework for reasoning about it at a technical level, and profoundly
diverse approaches to clustering abound in the research community.
Here we suggest a formal perspective on the difficulty in finding
such a unification, in the form of an impossibility theorem: for a set
of three simple properties, we show that there is no clustering
function satisfying all three. Relaxations of these properties expose
some of the interesting (and unavoidable) trade-offs at work in
well-studied clustering techniques such as single-linkage,
sum-of-pairs, k-means, and k-median.
Wikipedia has a nice summary of internal evaluation metrics:
Therefore, the internal evaluation measures are best suited to get
some insight into situations where one algorithm performs better than
another, but this shall not imply that one algorithm produces more
valid results than another. Validity as measured by such an index
depends on the claim that this kind of structure exists in the data
set. An algorithm designed for some kind of models has no chance if
the data set contains a radically different set of models, or if the
evaluation measures a radically different criterion. For example,
k-means clustering can only find convex clusters, and many evaluation
indexes assume convex clusters. On a data set with non-convex clusters
neither the use of k-means, nor of an evaluation criterion that
assumes convexity, is sound.
More than a dozen of internal evaluation measures exist, usually based
on the intuition that items in the same cluster should be more similar
than items in different clusters. For example, the following methods
can be used to assess the quality of clustering algorithms based on
internal criterion:
Davies–Bouldin index
The Davies–Bouldin index can be calculated by the following formula:
$$DB={\frac {1}{n}}\sum _{i=1}^{n}\max _{j\neq i}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{i},c_{j})}}\right)$$
where $n$ is the number of clusters, $c_{x}$ is the centroid of cluster $x$, $\sigma _{x}$ is the average distance of all elements in
cluster $x$ to centroid $c_{x}$, and $d(c_{i},c_{j})$ is the distance
between centroids $c_{i}$ and $c_{j}$. Since algorithms that produce
clusters with low intra-cluster distances (high intra-cluster
similarity) and high inter-cluster distances (low inter-cluster
similarity) will have a low Davies–Bouldin index, the clustering
algorithm that produces a collection of clusters with the smallest
Davies–Bouldin index is considered the best algorithm based on this
criterion.
Dunn index
The Dunn index aims to identify dense and well-separated clusters. It is defined as the ratio between the minimal inter-cluster distance
to maximal intra-cluster distance. For each cluster partition, the
Dunn index can be calculated by the following formula:
$$D={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,$$
where $d(i,j)$ represents the distance between clusters $i$ and $j$, and $d'(k)$ measures the intra-cluster distance of cluster $k$.
The inter-cluster distance $d(i,j)$ between two clusters may be any
number of distance measures, such as the distance between the
centroids of the clusters. Similarly, the intra-cluster distance
$d'(k)$ may be measured in a variety ways, such as the maximal
distance between any pair of elements in cluster $k$. Since internal
criterion seek clusters with high intra-cluster similarity and low
inter-cluster similarity, algorithms that produce clusters with high
Dunn index are more desirable.
Silhouette coefficient
The silhouette coefficient contrasts the average distance to elements in the same cluster with the average distance to elements in
other clusters. Objects with a high silhouette value are considered
well clustered, objects with a low value may be outliers. This index
works well with k-means clustering, and is also used to determine the
optimal number of clusters.
Furthermore:
An Evaluation of Criteria for Measuring the Quality of Clusters
An important problem in clustering is how to decide what is the best
set of clusters for a given data set, in terms of both the number of
clusters and the member-ship of those clusters. In this paper we
develop four criteria for measuring the quality of different sets
of clusters. These criteria are designed so that different criteria
prefer cluster sets that generalise at different levels of
granularity. We evaluate the suitability of these criteria for
non-hierarchical clustering of the results returned by a search
engine. We also compare the number of clusters chosen by these
criteria with the number of clusters chosen by a group of human
subjects. Our results demonstrate that our criteria match the
variability exhibited by human subjects, indicating there is no
single perfect criterion. Instead, it is necessary to select the
correct criterion to match a human subject's generalisation needs.
Evaluation Metrics for Unsupervised Learning Algorithms
Determining the quality of the results obtained by clustering
techniques is a key issue in unsupervised machine learning. Many
authors have discussed the desirable features of good clustering
algorithms. However, Jon Kleinberg established an impossibility
theorem for clustering. As a consequence, a wealth of studies have
proposed techniques to evaluate the quality of clustering results
depending on the characteristics of the clustering problem and the
algorithmic technique employed to cluster data.
Understanding of Internal Clustering Validation Measures
Clustering validation has long been recognized as one of the vital
issues essential to the success of clustering applications. In
general, clustering validation can be categorized into two classes,
external clustering validation and internal clustering validation. In
this paper, we focus on internal clustering validation and present a
detailed study of 11 widely used internal clustering validation
measures for crisp clustering. From five conventional aspects of
clustering, we investigate their validation properties. Experiment
results show that 𝑆_𝐷𝑏𝑤 is the only internal validation measure
which performs well in all five aspects, while other measures have
certain limitations in different application scenarios.
