Database Reference
In-Depth Information
there is no substantial change in the options for stopping criteria when we move from Euc-
lidean to non-Euclidean spaces.
7.2.5
Exercises for Section 7.2
EXERCISE 7.2.1 Perform a hierarchical clustering of the one-dimensional set of points 1, 4,
9, 16, 25, 36, 49, 64, 81, assuming clusters are represented by their centroid (average), and
at each step the clusters with the closest centroids are merged.
EXERCISE 7.2.2 How would the clustering of Example 7.2 change if we used for the dis-
tance between two clusters:
(a) The minimum of the distances between any two points, one from each cluster.
(b) The average of the distances between pairs of points, one from each of the two
clusters.
EXERCISE 7.2.3 Repeat the clustering of Example 7.2 if we choose to merge the two
clusters whose resulting cluster has:
(a) The smallest radius.
(b) The smallest diameter.
EXERCISE 7.2.4 Compute the density of each of the three clusters in Fig. 7.2 , if “density”
is defined to be the number of points divided by
(a) The square of the radius.
(b) The diameter (not squared).
What are the densities, according to (a) and (b), of the clusters that result from the merger of
any two of these three clusters. Does the difference in densities suggest the clusters should
or should not be merged?
EXERCISE 7.2.5 We can select clustroids for clusters, even if the space is Euclidean. Con-
sider the three natural clusters in Fig. 7.2 , and compute the clustroids of each, assuming the
criterion for selecting the clustroid is the point with the minimum sum of distances to the
other point in the cluster.
! EXERCISE 7.2.6 Consider the space of strings with edit distance as the distance measure.
Give an example of a set of strings such that if we choose the clustroid by minimizing the
sum of the distances to the other points we get one point as the clustroid, but if we choose
Search WWH ::




Custom Search