10.8 Exercises
10.1 Briefly describe and give examples of each of the following approaches to clustering: partitioning methods, hierarchical methods, density-based methods, and grid-based methods.
10.2 Suppose that the data mining task is to cluster points (with (x, y) representing location) into three clusters, where the points are
The distance function is Euclidean distance. Suppose initially we assign A1, B1, and C1 as the center of each cluster, respectively. Use the k-means algorithm to show only
(a) The three cluster centers after the first round of execution.
10.3 Use an example to show why the k-means algorithm may not find the global optimum, that is, optimizing the within-cluster variation.
10.4 For the k-means algorithm, it is interesting to note that by choosing the initial cluster centers carefully, we may be able to not only speed up the algorithm’s convergence, but also guarantee the quality of the final clustering. The k-means++ algorithm is a variant of k-means, which chooses the initial centers as follows. First, it selects one center uniformly at random from the objects in the data set. Iteratively, for each object p other than the chosen center, it chooses an object as the new center. This object is chosen at random with probability proportional to dist(p)2, where dist(p) is the distance from p to the closest center that has already been chosen. The iteration continues until k centers are selected.
Explain why this method will not only speed up the convergence of the k-means algorithm, but also guarantee the quality of the final clustering results.
10.5 Provide the pseudocode of the object reassignment step of the PAM algorithm.
10.6 Both k-means and k-medoids algorithms can perform effective clustering.
(a) Illustrate the strength and weakness of k-means in comparison with k-medoids.
(b) Illustrate the strength and weakness of these schemes in comparison with a hierarchical clustering scheme (e.g., AGNES).
10.7 Prove that in DBSCAN, the density-connectedness is an equivalence relation.
10.8 Prove that in DBSCAN, for a fixed MinPts value and two neighborhood thresholds, 
1 < 2, a cluster C with respect to 1 and MinPts must be a subset of a cluster C′ with respect to 2 and MinPts.
10.9 Provide the pseudocode of the OPTICS algorithm.
10.10 Why is it that BIRCH encounters difficulties in finding clusters of arbitrary shape but OPTICS does not? Propose modifications to BIRCH to help it find clusters of arbitrary shape.
10.11 Provide the pseudocode of the step in CLIQUE that finds dense cells in all subspaces.
10.12 Present conditions under which density-based clustering is more suitable than partitioning-based clustering and hierarchical clustering. Give application examples to support your argument.
10.13 Give an example of how specific clustering methods can be integrated, for example, where one clustering algorithm is used as a preprocessing step for another. In addition, provide reasoning as to why the integration of two methods may sometimes lead to improved clustering quality and efficiency.
10.14 Clustering is recognized as an important data mining task with broad applications. Give one application example for each of the following cases:
(a) An application that uses clustering as a major data mining function.
(b) An application that uses clustering as a preprocessing tool for data preparation for other data mining tasks.
10.15 Data cubes and multidimensional databases contain nominal, ordinal, and numeric data in hierarchical or aggregate forms. Based on what you have learned about the clustering methods, design a clustering method that finds clusters in large data cubes effectively and efficiently.
10.16 Describe each of the following clustering algorithms in terms of the following criteria: (1) shapes of clusters that can be determined; (2) input parameters that must be specified; and (3) limitations.
10.17 Human eyes are fast and effective at judging the quality of clustering methods for 2-D data. Can you design a data visualization method that may help humans visualize data clusters and judge the clustering quality for 3-D data? What about for even higher-dimensional data?
10.18 Suppose that you are to allocate a number of automatic teller machines (ATMs) in a given region so as to satisfy a number of constraints. Households or workplaces may be clustered so that typically one ATM is assigned per cluster. The clustering, however, may be constrained by two factors: (1) obstacle objects (i.e., there are bridges, rivers, and highways that can affect ATM accessibility), and (2) additional user-specified constraints such as that each ATM should serve at least 10,000 households. How can a clustering algorithm such as k-means be modified for quality clustering under both constraints?
10.19 For constraint-based clustering, aside from having the minimum number of customers in each cluster (for ATM allocation) as a constraint, there can be many other kinds of constraints. For example, a constraint could be in the form of the maximum number of customers per cluster, average income of customers per cluster, maximum distance between every two clusters, and so on. Categorize the kinds of constraints that can be imposed on the clusters produced and discuss how to perform clustering efficiently under such kinds of constraints.
10.20 Design a privacy-preserving clustering method so that a data owner would be able to ask a third party to mine the data for quality clustering without worrying about the potential inappropriate disclosure of certain private or sensitive information stored in the data.
10.21 Show that BCubed metrics satisfy the four essential requirements for extrinsic clustering evaluation methods.