Data Mining_ Concepts and Techniques - Jiawei Han [300]
(b) The final three clusters.
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.
(a) k-means
(b) k-medoids
(c) CLARA
(d) BIRCH
(e) CHAMELEON
(f) DBSCAN
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