9
Cluster Analysis:
Additional Issues and
Algorithms
1. For sparse data, discuss why considering only the presence of non-zero values
might give a more accurate view of the objects than considering the actual
magnitudes of values. When would such an approach not be desirable?
Consider document data. Intuitively, two documents are similar if they con-
tain many of the same words. Although we can also include the frequency
with which those words occur in the similarity computation, this can some-
2. Describe the change in the time complexity of K-means as the number of
clusters to be found increases.
3. Consider a set of documents. Assume that all documents have been normal-
ized to have unit length of 1. What is the “shape” of a cluster that consists
of all documents whose cosine similarity to a centroid is greater than some
specified constant? In other words, cos(d, c)≥δ,where0<δ≤1.
148 Chapter 9 Cluster Analysis: Additional Issues and Algorithms
4. Discuss the advantages and disadvantages of treating clustering as an opti-
mization problem. Among other factors, consider efficiency, non-determinism,
and whether an optimization-based approach captures all types of clusterings
that are of interest.
Two key advantage to treating clustering as an optimization problem are
that (1) it provides a clear definition of what the clustering process is do-
ing, and (2) it allows the use of powerful optimization techniques that have
5. What is the time and space complexity of fuzzy c-means? Of SOM? How do
these complexities compare to those of K-means?
The time complexity of K-means O(I∗K∗m∗n), where Iis the number
6. Traditional K-means has a number of limitations, such as sensitivity to out-
liers and difficulty in handling clusters of different sizes and densities, or with
non-globular shapes. Comment on the ability of fuzzy c-means to handle
these situations.
7. For the fuzzy c-means algorithm described in this book, the sum of the mem-
bership degree of any point over all clusters is 1. Instead, we could only
require that the membership degree of a point in a cluster be between 0 and
1. What are the advantages and disadvantages of such an approach?
149
The main advantage of this approach occurs when a point is an outlier and
does not really belong very strongly to any cluster, since in that situation,
8. Explain the difference between likelihood and probability.
Probability is, according to one common statistical definition, the frequency
9. Equation 9.12 gives the likelihood for a set of points from a Gaussian dis-
tribution as a function of the mean μand the standard deviation σ. Show
mathematically that the maximum likelihood estimate of μand σare the
sample mean and the sample standard deviation, respectively.
First, we solve for μ.
∂((μ, σ)|X )
m
(xi−μ)2
10. We take a sample of adults and measure their heights. If we record the gender
of each person, we can calculate the average height and the variance of the
height, separately, for men and women. Suppose, however, that this informa-
tion was not recorded. Would it be possible to still obtain this information?
Explain.
11. Compare the membership weights and probabilities of Figures 9.1 and 9.4,
which come, respectively, from applying fuzzy and EM clustering to the same
set of data points. What differences do you detect, and how might you explain
these differences?
The fuzzy clustering approach only assigns very high weights to those points
in the center of the clusters. Those points that are close to two or three
12. Figure 9.1 shows a clustering of a two-dimensional point data set with two
clusters: The leftmost cluster, whose points are marked by asterisks, is some-
what diffuse, while the rightmost cluster, whose points are marked by circles,
is compact. To the right of the compact cluster, there is a single point
(marked by an arrow) that belongs to the diffuse cluster, whose center is
farther away than that of the compact cluster. Explain why this is possible
with EM clustering, but not K-means clustering.
In EM clustering, we compute the probability that a point belongs to a
cluster. In turn, this probability depends on both the distance from the
151
0
2
4
6
13. Show that the MST clustering technique of Section 9.4.2 produces the same
clusters as single link. To avoid complications and special cases, assume that
all the pairwise similarities are distinct.
In single link, we start with with clusters of individual points and then succes-
sively join two clusters that have the pair of points that are closest together.
Conceptually, we can view the merging of the clusters as putting an edge
between the two closest points of the two clusters. Note that if both clusters
14. One way to sparsify a proximity matrix is the following: For each object
(row in the matrix), set all entries to 0 except for those corresponding to
the objects k-nearest neighbors. However, the sparsified proximity matrix is
typically not symmetric.
(a) If object ais among the k-nearest neighbors of object b,whyisbnot
guaranteed to be among the k-nearest neighbors of a?
(b) Suggest at least two approaches that could be used to make the sparsi-
fied proximity matrix symmetric.
15. Give an example of a set of clusters in which merging based on the closeness
of clusters leads to a more natural set of clusters than merging based on the
strength of connection (interconnectedness) of clusters.
An example of this is given in the Chameleon paper that can be found at
16. Table 9.1 lists the two nearest neighbors of four points.
17. For the definition of SNN similarity provided by Algorithm 9.10, the cal-
culation of SNN distance does not take into account the position of shared
Table 9.1. Two nearest neighbors of four points.
Point First Neighbor Second Neighbor
1 4 3
2 3 4
3 4 2
4 3 1
Table 9.2. Two nearest neighbors of four points.
Point 1234
12001
20210
30120
41002
neighbors in the two nearest neighbor lists. In other words, it might be de-
sirable to give higher similarity to two points that share the same nearest
neighbors in the same or roughly the same order.
(a) Describe how you might modify the definition of SNN similarity to give
higher similarity to points whose shared neighbors are in roughly the
same order.
(b) Discuss the advantages and disadvantages of such a modification.
18. Name at least one situation in which you would not want to use clustering
based on SNN similarity or density.
19. Grid-clustering techniques are different from other clustering techniques in
that they partition space instead of sets of points.
(a) How does this affect such techniques in terms of the description of the
resulting clusters and the types of clusters that can be found?
154 Chapter 9 Cluster Analysis: Additional Issues and Algorithms
(b) What kind of cluster can be found with grid-based clusters that cannot
be found by other types of clustering approaches? (Hint: See Exercise
20 in Chapter 8, page 564.)
20. In CLIQUE, the threshold used to find cluster density remains constant,
even as the number of dimensions increases. This is a potential problem
since density drops as dimensionality increases; i.e., to find clusters in higher
dimensions the threshold has to be set at a level that may well result in the
merging of low-dimensional clusters. Comment on whether you feel this is
truly a problem and, if so, how you might modify CLIQUE to address this
problem.
This is a real problem. A similar problem exists in association analysis. In
21. Given a set of points in Euclidean space, which are being clustered using
the K-means algorithm with Euclidean distance, the triangle inequality can
be used in the assignment step to avoid calculating all the distances of each
point to each cluster centroid. Provide a general discussion of how this might
work.
155
Proof:
We know d(b, c)≤d(b, x)+d(x, c).
22. Instead of using the formula derived in CURE—see Equation 9.19—we could
run a Monte Carlo simulation to directly estimate the probability that a
sample of size swould contain at least a certain fraction of the points from
a cluster. Using a Monte Carlo simulation compute the probability that a
sample of size scontains 50% of the elements of a cluster of size 100, where
the total number of points is 1000, and where scan take the values 100, 200,
or 500.