Assignment
Data Mining 2
Date of submission: 19/11/25
1) Identify the clusters in Figure using the center-, contiguity-, and density-based definitions.
Also indicate the number of clusters for each case and give a brief indication of your
reasoning. Note that darkness or the number of dots indicates density. If it helps, assume
center-based means K-means, contiguity based means single link, and density-based
means DBSCAN.
2) For the following sets of two-dimensional points, (1) provide a sketch of how they would
be split into clusters by K-means for the given number of clusters and (2) indicate
approximately where the resulting centroids would be. Assume that we are using the
squared error objective function. If you think that there is more than one possible
solution, then please indicate whether each solution is a global or local minimum.
3) Use the similarity matrix in Table to perform single and complete link hierarchical
clustering. Show your results by drawing a dendrogram. The dendrogram should clearly
show the order in which the points are merged.
4) Hierarchical clustering is sometimes used to generate K clusters, K>1by taking the clusters
at the Kth level of the dendrogram. (Root is at level 1.) By looking at the clusters produced
in this way, we can evaluate the behavior of hierarchical clustering on different types of
data and clusters, and also compare hierarchical approaches to K-means. The following is
a set of one-dimensional points:
{6,12,18,24,30,42,48}.
(a) For each of the following sets of initial centroids, create two clusters by assigning each
point to the nearest centroid, and then calculate the total squared error for each set of
two clusters. Show both the clusters and the total squared error for each set of centroids.
i. {18,45}
ii. {15,40}
(b) Do both sets of centroids represent stable solutions, i.e., if the K-means algorithm was
run on this set of points using the given centroids as the starting centroids, would there
be any change in the clusters generated?
(c) What are the two clusters produced by single link?
(d) Which technique, K-means or single link, seems to produce the “most natural”
clustering in this situation? (For K-means, take the clustering with the lowest squared
error.)
(e) What definition(s) of clustering does this natural clustering correspond to? (Well-
separated, center-based, contiguous, or density.)
(f) What well-known characteristic of the K-means algorithm explains the previous
behavior?
5) Suppose we find K clusters using Ward’s method, bisecting K-means, and ordinary K-
means. Which of these solutions represents a local or global minimum? Explain.
6) Compute the entropy and purity for the confusion matrix in Table
7) You are given two sets of 100 points that fall within the unit square. One set of points is
arranged so that the points are uniformly spaced. The other set of points is generated
from a uniform distribution over the unit square.
(a) Is there a difference between the two sets of points?
(b) If so, which set of points will typically have a smaller SSE for K=10 clusters?
(c) What will be the behavior of DBSCAN on the uniform data set? The random data set?
8) Compute the hierarchical F-measure for the eight objects {p1, p2, p3, p4, p5, p6, p7, and
p8} and hierarchical clustering shown in Figure. Class A contains points p1, p2, and p3,
while p4, p5, p6, p7, and p8 belong to class B.