Solution Manual for Data Mining Chapter 10

Chapter 10 Cluster Analysis: Basic Concepts and Methods 10.1 Exercises 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. Answer: Clustering is the process of grouping data into classes, or clusters, so that objects within a cluster have high similarity in comparison to one another, but are very dissimilar to objects in other clusters. There are several approaches to clustering methods. Partitioning methods: Given a databases of n objects or data tuples, a partitioning methods constructs k partitions of data, where each partition represents a cluster and k ≤ n. Given k, the number of partitions to construct, it creates an initial partitioning. It then uses an iterative relocation technique that attempts to improve the partitioning by moving objects from one group to another. The general criterion of a good partitioning is that objects in the same cluster are “close” or related to each other, whereas objects of different clusters are “far apart”. For example, the k-means method is one of the partitioning methods commonly used. Hierarchical methods: A hierarchical method creates a hierarchical decomposition of the given set of data objects. It can be either agglomerative or divisive. The agglomerative (bottom-up) approach starts with each object forming a separate group. It successively merges the objects close to one another, until all of the groups are merged into one, or until a termination condition holds. The divisive (topdown) approach starts with all objects in the same cluster. In each successive iteration, a cluster is split up into smaller clusters, until eventually each object is in one cluster or until a termination condition holds. BIRCH is an example of integration of hierarchical method with distance-based clustering. Density-based methods: This method is based on density such as density-connected points. The main idea is to continue growing a given cluster as long as the density in its “neighborhood” exceeds some threshold. That is, for each data point within a given cluster, the neighborhood of a given radius has to contain at least a minimum number of points. This method can be used to filter out noise and discover clusters of arbitrary shape. DBSCAN is a typical example of density-based clustering method. Grid-based methods: Such methods quantize the object space into a finite number of cells that form a grid structure. All of the clustering operations are performed on the grid structure. The main advantage of this approach is its fast processing time, which is typically independent of the number of data objects and dependent only on the number of cells in each dimension in the quantized space. STING is an example of a grid-based method. Model-based methods: This approach hypothesizes a model for each of the clusters and finds the best fit of the data to the given model. It locates the clusters by constructing a density function that reflects the spatial distribution of the data points. It also leads to a way of automatically determining the number of clusters based on standard statistics, taking “noise” or outliers into account and thus yielding robust clustering methods. COBWEB is an example of a statistical approach of a model-based method. 2. Suppose that the data mining task is to cluster points (with (x, y) representing location) into three clusters, where the points are A1 (2, 10), A2 (2, 5), A3 (8, 4), B1 (5, 8), B2 (7, 5), B3 (6, 4), C1 (1, 2), C2 (4, 9). 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. Answer: After the first round, the three new clusters are: (1) {A1 }, (2) {B1 , A3 , B2 , B3 , C2 }, (3) {C1 , A2 }, and their centers are (1) (2, 10), (2) (6, 6), (3) (1.5, 3.5). (b) the final three clusters. Answer: The final three clusters are: (1) {A1 , C2 , B1 }, (2) {A3 , B2 , B3 }, (3) {C1 , A2 }. 3. Use an example to show why the k -means algorithm may not find the global optimum, that is, optimizing the within-cluster variation. Answer: Consider applying the k-means algorithm on the following points, and set k = 2. A(0, 1), B(0, −1), Ci (100, 50) (i = 1, . . . , 100), and Dj (100, −50) (j = 1, . . . , 100). If we use A and C1 as the initial cluster centers, then the clustering process will converge to two centers, (0, 0) and (100, 0). The within-cluster variation is E = 12 + 12 + 100 × 502 + 100 × 502 = 1 + 1 + 100 × 2500 + 100 × 2500 = 500002. However, if we use (100, 50) and (100, −50) as the cluster centers, the within-cluster variation is E = (1002 + 492 ) + (1002 + 492 ) + 100 × 0 + 100 × 0 = 24802, which is much smaller. This example shows k-means may be trapped by a local optimal, and cannot jump out to find the global optimum. 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 convergence of the algorithm, 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. Answer: Please refer to [AV07]. 5. Provide the pseudo-code of the object re-assignment step of the PAM algorithm. Answer: Let o1 , . . . , ok be the current medoids. Suppose we are considering to use object orandom to replace medoid object oi (1 ≤ i ≤ k). Then, we need to reassign all the other objects in the data set. The pseudo-code of the re-assignment step is as follows. 1: for each object o assigned to oj (1 ≤ j ≤ k, j = i) do 2: if dist(o, oj ) > dist(o, orandom ) then 3: assign o to orandom 4: else 5: still assign o to oj 6: end if 7: end for 8: for each object o assigned to oi , including oi do 9: j = arg min1≤l≤k,l=i  {dist(o, ol )} 10: if dist(o, orandom ) < dist(o, oj ) then 11: assign o to orandom 12: else 13: assign o to oj 14: end if 15: end for 6. Both k-means and k-medoids algorithms can perform effective clustering. (a) Illustrate the strength and weakness of k-means in comparison with the k-medoids algorithm. Answer: k-means vs. k medoids: more efficient but quality deteriorates by noise and outliers. (b) Illustrate the strength and weakness of these schemes in comparison with a hierarchical clustering scheme (such as AGNES). Answer: Partition: can undo what was done (by moving objects around clusters)—quality is good in general, require the number of clusters to be known; find only spherical shaped clusters. Hierarchical: cannot undo what was done—quality could be poor, does not require the number of clusters to be known; more efficient and parallel (divide and conquer), may find only arbitrary shaped clusters. 7. Prove that in DBSCAN, the density-connectedness is an equivalence relation. Answer: Given a radius of neighborhood ϵ > 0 and a density threshold M inP ts > 0, DBSCAN partitions a set of objects into density-based clusters. We show that the density-connectedness used in DBSCAN is an equivalence relation on the set of objects O, where for any object o ∈ O, o belongs to a cluster. Reflexivity For any object o ∈ O, since o belongs to a cluster, there must be an o′ ∈ O such that o and o′ are density-connected. Applying the definition of density-connectedness, trivially o and itself are density-connected. Symmetry Recall that two objects o1 , o2 ∈ O are density-connected with respect to ϵ and M inP ts, if there is an object o ∈ O such that both o1 and o2 are density-reachable from o with respect to ϵ and M inP ts. The symmetry follows with the definition immediately. Transitivity According to DBSCAN, all core objects in a cluster are density-reachable from each other. The set of objects inserted into N in the algorithm when a cluster is explored justifies the density-reachability of the core objects. Suppose o1 and o2 are density-connected, and so are o2 and o3 , determined by DBSCAN. Then, there are core objects o′ and o′′ such that o1 and o2 are density-reachable from o′ and o2 and o3 are density-reachable from o′′ . Moreover, o′ and o′′ must be assigned to the same density-based cluster by DBSCAN. Otherwise, DBSCAN does not explore the density-connectedness between o1 and o2 and that between o2 and o3 at the same time. Therefore, both o1 and o3 are density-reachable from o′ (and o′′ as well). That is, o1 and o3 are density-connected. Please note that, in general, the density-connectedness is NOT an equivalence relation. It is possible that an object o, which is not a core object, is directly density-reachable from two core objects o1 and o2 that belong to two different clusters. In such a case, DBSCAN arbitrarily assigns o to one cluster, say the cluster containing o1 , and does not regard o is density-reachable from o2 . 8. Prove that in DBSCAN, for a fixed M inP ts value and two neighborhood thresholds ϵ1 < ϵ2 , a cluster C with respect to ϵ1 and M inP ts must be a subset of a cluster C ′ with respect to ϵ2 and M inP ts. Answer: For any core object q and object p such that p is directly density-reachable from q with respect to ϵ1 , q is also directly density-reachable from q with respect to ϵ2 . Thus, if an object p is density-reachable from object q with respect to ϵ1 , p is still density-reachable from q with respect to ϵ2 . Therefore, if objects p and q are density-connected with respect to ϵ1 , they are density-connected with respect to ϵ2 . Consequently, all objects in cluster C with respect to ϵ1 must be grouped into a cluster C ′ with respect to ϵ2 . 9. Provide the pseudo-code of the OPTICS algorithm. Answer: Please refer to Figures 5-8 in [ABKS99]. 10. Why is it that BIRCH encounters difficulties in finding clusters of arbitrary shape but OPTICS does not? Can you propose some modifications to BIRCH to help it find clusters of arbitrary shape? Answer: BIRCH uses Euclidean distance and inter-cluster proximity as distance measure, which leads to spherical shaped clusters. OPTICS uses density-based (connectivity) measure, which grows clusters based on the connected points within a defined radius, and thus can find arbitrary shaped clusters. There could be several ways to modify BIRCH. One is to use density-based and connectivity-based distance measure to cluster low-level B+-trees and build levels of CF-tree which will lead to connectivitybased (arbitrary-shaped) cluster. 11. Provide the pseudo-code of the step in CLIQUE finding dense cells in all subspaces. Answer: Please refer to Section 3.1.1 in [AGGR98]. 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. Answer: Density-based clustering is more suitable if no or very limited domain knowledge is available to determine the appropriate values of the parameters, the clusters are expect of arbitrary shape including non convex shapes, and the efficiency is essential on large data sets. For example, consider the application of recognizing residential area on a map where buildings and their types are labeled. A user may not have the domain knowledge about how a residential area would look like. Moreover, a residential area may be of arbitrary shape, and may not be in convex, such as those built along a river. In a large city, there are hundreds of thousands of buildings. Efficiency on large data sets is important. 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. Answer: Consider building an ontology of queries for information retrieval and web search. A query is associated with a vector of web pages that are clicked when the query is asked. An effective approach is to first conduct density-based clustering to form small clusters as micro-clusters. Each micro-cluster is treated as a base unit, sometimes called a concept. Then, a hierarchical clustering method can be applied to build an ontology. To use density-based clustering as a pre-processing step can quickly merge synonyms, such as “University of Illinois at Urbana-Champaign” and “UIUC”, into one concept. This preprocessing step can reduce the data so that the ontology built later is more meaningful, and the ontology building process is faster. 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 takes clustering as a major data mining function Answer: For example, clustering is a major data mining function in community finding in social networks. (b) An application that takes clustering as a preprocessing tool for data preparation for other data mining tasks. Answer: Web search engines often provide query suggestion services. When a user inputs one or a series of queries, the search engine tries to suggest some queries that may capture the user’s information need. To overcome the data sparsity, that is, many queries are asked very few times, and many web pages are not clicked, clustering is often used as a preprocessing step to obtain micro-clusters of queries, which represent similar user intents, and web pages, which are about the same topics. 15. Data cubes and multidimensional databases contain categorical, ordinal, and numerical 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. Answer: For example, CLIQUE can be extended to a data cube. 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 Answer: (a) k-means 1. Compact clouds (clusters of non-convex shape cannot be determined); 2. Number of clusters; 3. Sensitive to noise and outliers, works good on small data sets only. (b) k-medoids 1. Compact clouds (clusters of non-convex shape cannot be determined); 2. Number of clusters; 3. Small data sets (not scalable). (c) CLARA 1. Convex-shaped clusters; 2. Number of clusters; 3. Sensitive to the selection of initial samples. (d) BIRCH 1. Spherical in shape clusters; 2. N d-dimensional data points; 3. Resulting clusters may be of unnatural shape. (e) CHAMELEON 1. Arbitrary shape; 2. N d-dimensional categorical points; 3. Quadratic time in the worst case. (f) DBSCAN 1. Arbitrary shape; 2. Maximum possible distance for a point to be considered density reachable and minimum number of points in a cluster. 3. Quadratic time in the worst case. 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? Answer: One method is as follows: We first use a clustering algorithm to obtain clusters from the threedimensional data. We then paint the clusters found. These can be “projected” onto two-dimensional data to obtain the clusters in the 2-D space, making it easier for humans to visualize. To help gain greater insight as to the quality of clusters for the 3-D data, we can then rotate the data space at different angles. Later, we can project onto another set of 2-D data, to similarly rotate the data space. By comparing the different 2-D space clusters, we have a better idea of the clusters in the 3-D data. For higher dimensional data we can use a method of coloring. First we transform the higher dimensional data into lower dimensional data and then use an arbitrary clustering algorithm to obtain the clusters at this lower level. We then paint the clusters into different colors, and continuously perform clustering on the higher dimensional data. Ideally, we gain greater insight as to the quality of the clusters by comparing the colors of the clusters. 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 places of work 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 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? Answer: Constraint algorithms can be modified in the following aspects to allow for constraint-based clustering as specified in the exercise. (We list only some examples): • Micro-cluster. Objects are clustered locally into micro-clusters. In a micro-cluster, no obstacle can appear between any two other objects in the micro-cluster. • Distance measurement. Distance between two objects should be adjusted if obstacles occur between them. In such cases, reachable distance, instead of direct distance, should be used. Reachable distance gives the minimal (or estimated minimal) distance between two objects with consideration of obstacles. • Medoid-based. For every district, initialize k clusters, where k is between the minimum and maximum number of ATMs allowed in the district. When a medoid is going to be moved across a district border, if after such a move the source district has fewer ATMs than required, or the destination district has more ATMs than expected, then the center can only be moved within the border to the point closest to the corresponding point in the other region. 19. For constraint-based clustering, aside from having the minimum number of customers in each cluster (for ATM allocation) as a constraint, there could 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. Answer: Pleaser refer to [THH01]. 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. Answer: Please refer to, for example, [VC03, AY08]. 21. Show that BCubed metrics satisfy the four essential requirements for extrinsic clustering evaluation methods. Answer: Cluster homogeneity Consider clustering C1 , wherein a cluster C ∈ C1 contains objects from two categories L1 , L2 in the ground truth. Moreover, consider clustering C2 , which is identical to C1 except that C is split into two clusters containing objects in L1 and L2 , respectively. Let C1 (o) and C2 (o) be the cluster-id of o in C1 and C2 , respectively. The BCubed precision of C1 is P rec(C1 ) = ∑ ∑ o∈C Correctness(o,o′ ) o′ =o,C1 (o)=C1 (o′ ) ∥{o′ =o  |C1 (o)=C1 (o′ )}∥ + ∑ ∑ o∈C ∑ o∈C Correctness(o,o′ ) o′ =o,C1 (o)=C1 (o′ ) ∥{o′ =o  |C1 (o)=C1 (o′ )}∥ total number of objects in the data set The BCubed precision of C2 is P rec(C2 ) = ∑ ∑ o∈C Correctness(o,o′ ) o′ =o,C2 (o)=C2 (o′ ) ∥{o′ =o  |C2 (o)=C2 (o′ )}∥ + ∑ Correctness(o,o′ ) o′ =o,C2 (o)=C2 (o′ ) ∥{o′ =o  |C2 (o)=C2 (o′ )}∥ total number of objects in the data set Since C1 and C2 are identical except for cluster C, we have ∑ ∑ ′ ′ ∑ ∑ o′ =o,  C1 (o)=C1 (o′ ) Correctness(o, o ) o′ =o,C2 (o)=C2 (o′ ) Correctness(o, o ) = ′ ′ ∥{o =  o|C1 (o) = C1 (o )}∥ ∥{o′ =  o|C2 (o) = C2 (o′ )}∥ o∈C o∈C In C1 , C is a mixture of the objects from two categories L1 and L2 . In C2 , C is divided into two clusters containing the objects in the two categories respectively. Therefore, ∑ ∑ ′ ′ ∑ ∑ o′ =o,  C1 (o)=C1 (o′ ) Correctness(o, o ) o′ =o,C2 (o)=C2 (o′ ) Correctness(o, o ) < ′ ′ ∥{o′ =  o|C2 (o) = C2 (o′ )}∥ ∥{o =  o|C1 (o) = C1 (o )}∥ o∈C o∈C Thus, we have P rec(C1 ) < P rec(C2 ). Similarly, we can show Recall(C1 ) < Recall(C2 ). Cluster completeness The proof of the cluster completeness is similar to that of the cluster homogeneity. Rag bag Consider a clustering C1 and a cluster C ∈ C1 such that all objects in C except for one, denoted by o, belong to the same category according to the ground truth. Consider a clustering C2 identical to C1 except that o is assigned to a cluster C ′ = C in C2 such that C ′ contains objects from various categories according to the ground truth. In other words, C ′ ∈ C2 is a rag bag. We show that the BCubed precision of C2 is greater than that of C1 . In the BCubed precision calculation, P rec(C1 ) and P rec(C2 ) are the same except for those object pairs involving o. P rec(C2 ) − P rec(C1 ) = = ≥ number of objects in C ′ in the same category of o 1 + ∥C ′ ∥ − 1 ∥C ′ ∥ − 1 1 ]/total number of objects in the data set −(∥C∥ − 1) ∥C∥ − 1 number of objects in C ′ in the same category of o (∥C ′ ∥ − 1) × total number of objects in the data set 0 [(∥C ′ ∥ − 1) In the worst case, there is no object in C ′ that is in the same category of o, P rec(C2 )−P rec(C1 ) = 0. As long as there is at least one object in C ′ that is in the same category of o, P rec(C2 )−P rec(C1 ) > 0. The BCubed recall can be analyzed in a similar way. Small cluster preservation Suppose there are two categories, L1 and L2 , in the ground truth such that ∥L1 ∥ > ∥L2 ∥. Consider a clustering C1 wherein the objects in L1 are divided into two clusters C11 and C12 , and the objects in L2 are contained in a cluster C2 . Consider a clustering C2 identical to C1 except that C11 and C12 are merged into one cluster C1 and the objects in L2 are divided into two clusters C21 and C22 . It is easy to verify that Rec(C2 ) > Rec(C1 ). 10.2 Supplementary Exercises 1. Briefly outline how to compute the dissimilarity between objects described by the following types of variables: (a) Asymmetric binary variables Answer: If all binary variables have the same weight, we have the contingency Table 10.1. Use object i 1 0 sum object j 1 0 q r s t q+s r+t sum q+r s+t p Table 10.1: A contingency table for binary variables. the Jaccard coefficient, where the number of negative matches, t, is considered unimportant and thus is ignored in the computation, that is, d(i, j) = r+s q+r+s (10.1) (b) Nominal variables Answer: A nominal variable is a generalization of the binary variable in that it can take on more than two states. The dissimilarity between two objects i and j can be computed using the simple matching approach as in (10.2): d(i, j) = p−m , p (10.2) where m is the number of matches (i.e., the number of variables for which i and j are in the same state), and p is the total number of variables. Alternatively, we can use a large number of binary variables by creating a new binary variable for each of the M nominal states. For an object with a given state value, the binary variable representing that state is set to 1, while the remaining binary variables are set to 0. (c) Ratio-scaled variables Answer: Three methods include: • Treat ratio-scaled variables as interval-scaled variables, so that the Minkowski, Manhattan, or Euclidean distance can be used to compute the dissimilarity. • Apply a logarithmic transformation to a ratio-scaled variable f having value xif for object i by using the formula yif = log(xif ). The yif values can be treated as interval-valued, • Treat xif as continuous ordinal data, and treat their ranks as interval-scaled variables. (d) Numerical (interval-scaled) variables Answer: Use Euclidean distance or Manhattan distance. Euclidean distance is defined as √ d(i, j) = |xi1 − xj1 |2 + |xi2 − xj2 |2 + · · · + |xip − xjp |2 . (10.3) where i = (xi1 , xi2 , . . . , xip ), and j = (xj1 , xj2 , . . . , xjp ), are two p-dimensional data objects. The Manhattan (or city block) distance, is defined as d(i, j) = |xi1 − xj1 | + |xi2 − xj2 | + · · · + |xip − xjp |. (10.4) 2. Given the following measurements for the variable age: 18, 22, 25, 42, 28, 43, 33, 35, 56, 28, standardize the variable by the following: (a) Compute the mean absolute deviation of age. Answer: The mean absolute deviation of age is 8.8, which is derived as follows. mf sf 1 1 (x1f + · · · + xnf ) = (18 + 22 + 25 + 42 + 28 + 43 + 33 + 35 + 56 + 28) = 33 n 10 1 = (|x1f − mf | + · · · + |xnf − mf |) n 1 = (|18 − 33| + |22 − 33| + |25 − 33| + |42 − 33| + |28 − 33| + |43 − 33| + |33 − 33| + |35 − 33| 10 +|56 − 33| + |28 − 33|) = 8. 8 = (b) Compute the z-score for the first four measurements. Answer: According to the z-score computation formula, zif = xif − mif . sf (10.5) We have z1f = z2f = z3f = z4f = 18 − 33 = −1.70 8.8 22 − 33 = −1.25 8.8 25 − 33 = −0.91 8.8 42 − 33 = 1.02 8.8 3. Given two objects represented by the tuples (22, 1, 42, 10) and (20, 0, 36, 8): (a) Compute the Euclidean distance between the two objects. Answer: √ d(i, j) = |xi1 − xj1 |2 + |xi2 − xj2 |2 + · · · + |xip − xjp |2 √ = |22 − 20|2 + |1 − 0|2 + |42 − 36|2 + |10 − 8|2 = 6.71 (b) Compute the Manhattan distance between the two objects. Answer: d(i, j) = |xi1 − xj1 | + |xi2 − xj2 | + · · · + |xip − xjp | = |22 − 20| + |1 − 0| + |42 − 36| + |10 − 8| = 11 (c) Compute the Minkowski distance between the two objects, using q = 3. Answer: d(i, j) = = (|xi1 − xj1 |q + |xi2 − xj2 |q + · · · + |xip − xjp |q )1/q (|22 − 20|3 + |1 − 0|3 + |42 − 36|3 + |10 − 8|3 )1/3 = 6.15 4. The following table contains the attributes name, gender, trait-1, trait-2, trait-3, and trait-4, where name is an object-id, gender is a symmetric attribute, and the remaining trait attributes are asymmetric, describing personal traits of individuals who desire a penpal. Suppose that a service exists that attempts to find pairs of compatible penpals. name Kevan Caroline Erik .. . gender M F M ... trait-1 N N P ... trait-2 P P N .. . trait-3 P P N ... trait-4 N N P .. . For asymmetric attribute values, let the value P be set to 1 and the value N be set to 0. Suppose that the distance between objects (potential penpals) is computed based only on the asymmetric variables. (a) Show the contingency matrix for each pair given Kevan, Caroline, and Erik. Answer: Table 10.2 is the contingency matrix between Kevan and Caroline. Caroline Kevan 1 0 1 2 0 0 0 2 sum 2 2 sum 2 2 4 Table 10.2: The contingency matrix for Kevan and Caroline. Erik 0 0 sum Kevan 1 0 sum 0 2 2 2 0 2 2 2 4 Table 10.3: The contingency matrix for Kevan and Erik. Table 10.3 is the contingency matrix between Kevan and Erik. Erik 1 0 sum Caroline 1 0 sum 0 2 2 2 0 2 2 2 4 Table 10.4: The contingency matrix between Caroline and Erik Table 10.4 is the contingency matrix between Caroline and Erik. (b) Compute the simple matching coefficient for each pair. Answer: The simple matching coefficient between Caroline and Kevan is: d(Caroline, K evan) = 0+0 =0 2+0+0+2 2+2 =1 The simple matching coefficient between Erik and Kevan is: d(Erik, Kevan) = 0+2+2+0 The simple matching coefficient between Erik and Caroline is: d(Erik, Caroline) = 2+2 0+2+2+0 =1 (c) Compute the Jaccard coefficient for each pair. Answer: 0+0 = 0 2+0+0 The Jaccard coefficient between Caroline and Kevan is: d(Caroline, Kevan) = The Jaccard coefficient between Erik and Kevan is: d(Erik, Kevan) = 2+2 0+2+2 The Jaccard coefficient between Erik and Caroline is: d(Erik, Caroline) = =1 2+2 0+2+2 =1 (d) Who do you suggest would make the best pair of penpals? Which pair of individuals would be the least compatible? Answer: According to the Jaccard coefficient, we see that Caroline and Kevan would be the best pair of penpals while Erik and Kevan, or Erik and Caroline would be the least compatible pairs of penpals. (e) Suppose that we are to include the symmetric variable gender in our analysis. Based on the Jaccard coefficient, who would be the most compatible pair, and why? Answer: The Jaccard coefficient for each pair are calculated as follows: 1 = 13 d(Caroline, Kevan) = 1+1+1 d(Erik, Kevan) = 1+1+1+1 1+1+1+1+1 = 54 =1 d(Erik, Caroline) = 1+1+1+1 1+1+1+1 Based on the above, Caroline and Kevan would still be the most compatible pair since the Jaccard coefficient between them is the smallest. 5. Use a diagram to illustrate how, for a constant MinPts value, density-based clusters with respect to a higher density (i.e., a lower value for ϵ, the neighborhood radius) are completely contained in densityconnected sets obtained with respect to a lower density. Answer: See the diagram of Figure 10.1. Note that C1 and C2 are density-based clusters with respect to ϵ2 < ϵ1 , and C is a density-based cluster with respect to ϵ1 which completely contains the sets C1 and C2. (MinPts = 3.) C1 C2 e2 e1 C Figure 10.1: A diagram illustrating concepts of density-based clusters. 6. Use an example to show why CLARA may not find good clustering even if the sample size is large and in an equal probability of selection design. 7. Jaccard coefficient has been used as a similarity measure for (asymmetric) binary and categorical data. However, we have shown that the link measure based on counting the number of common neighbors proposed in ROCK may lead to better clustering quality. Can you identify at what situations that the former (Jaccard coefficient) may lead to better quality cluster than the latter, and vice versa? 8. Many clustering algorithms handle either only numerical data, such as BIRCH, or only categorical data, such as ROCK, but not both. Analyze why this is the case. Note, however, that the EM clustering algorithm can easily be extended to handle data with both numerical and categorical attributes. Briefly explain why it can do so and how. Answer: EM clustering essentially uses an underlying mixture model to do clustering. It is due to the probabilistic nature of such models that we can easily extend EM clustering to handle data with both numerical attributes and categorical attributes. Under the assumption that each attribute is independent of each other, we we could model numerical attributes by using density functions such as Poission, Gaussian, etc, and model categorical attributes by associating discrete distribution over these attributes such as Multinomial, Binomial, etc. The total component density can be decomposed as a product of density functions over each attribute. By having such component density functions, we will be able to easily use EM clustering to cluster data with both numerical attributes and categorical attributes. Reference: Paul S. Bradley Usama M. Fayyad Cory A, Scaling EM (Expectation-Maximization) Clustering to Large Databases, Technical Report, Microsoft Research Microsoft Corporation, October 1999. 9. Give an example of how specific clustering methods may be integrated, for example, where one clustering algorithm is used as a preprocessing step for another. Answer: One example could be Birch, a method that integrates hierarchical clustering with other clustering techniques for multiple phase clustering. It begins by partitioning objects hierarchically using tree structures, and then applies other clustering algorithms to refine the clusters. BIRCH incrementally constructs a CF(Clustering Feature) tree, which is a height-balanced tree that stores the clustering features for a hierarchical clustering. This method consists of two phases. Phase 1 scans the database to build an initial in-memory CF tree, which can be viewed as a multilevel compression of the data that tries to preserve the inherent clustering structure of the data. Phase 2 applies an arbitrary clustering algorithm to cluster the leaf nodes of the CF-tree. It therefore uses the hierarchical clustering technique as a preprocessing step. 10. Clustering has been popularly recognized as an important data mining task with broad applications. Give one application example for each of the following cases: (a) An application that takes clustering as a major data mining function Answer: An example that takes clustering as a major data mining function could be a system that identifies groups of houses in a city according to house type, value, and geographical location. More specifically, a clustering algorithm like CLARANS can be used to discover that, say, the most expensive housing units in Vancouver can be grouped into just a few clusters. (b) An application that takes clustering as a preprocessing tool for data preparation for other data mining tasks Answer: An example application that takes clustering as a preprocessing tool for other data mining is spatial data mining. Spatial data mining is the discovery of interesting relationships and characteristics that may exist implicitly in spatial databases. We can apply cluster analysis only to spatial attributes, where natural notions of similarity exist. Various clustering algorithms, such as PAM, CLARA, or CLARANS may be used. The clusters obtained from the clustering algorithm may trigger the generation on non-spatial components in the next step if such a generation can group objects into interesting groups. 11. Data cubes and multidimensional databases contain categorical, ordinal, and numerical 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. Answer: We can use the idea of a grid-based clustering approach, such as the CLIQUE, to find the cluster in a large data cube since a data cube can be interpreted as a multiresolution grid data structure. We first need to preprocess and discretize existing data (such as ordinal, numerical data) in order to obtain a single dimensional discretization. We then can perform the multidimensional clustering in two steps. The first step involves partitioning of the n-dimensional data space into non-overlapping rectangular units, identifying the dense units among these. This is done in 1-D for each dimension. We then can generate candidate dense units in k-dimensional space from the dense units found in (k − 1)-dimensional space. In the second step, a minimal description for each cluster is generated. For each cluster, this determines the maximal region that covers the cluster of connected dense units. It then determines a minimal cover for each cluster. Using such a method, we can effectively find clusters from the data that are represented as a data cube. 12. Why is outlier mining important? Briefly describe the different approaches behind statistical-based outlier detection, distance-based outlier detection, and deviation-based outlier detection. Answer: Data objects that are grossly different from, or inconsistent with, the remaining set of data are called “outliers”. Outlier mining is useful for detecting fraudulent activity, (such as credit card or telecom fraud), as well as customer segmentation and medical analysis. Computer-based outlier analysis may be statistical-based, distance-based, or deviation-based. The statistical-based approach assumes a distribution or probability model for the given data set and then identifies outliers with respect to the model using a discordancy test. The discordancy test is based on data distribution, distribution parameters (e.g., mean, variance), and the number of expected outliers. The drawbacks of this method are that most tests are for single attributes, and in many cases, the data distribution may not be known. The distance-based approach was introduced to counter the limitations of the statistical-based approach. A DB(p, D)-outlier is an object O in a data set T such that at least a fraction p of the objects in T lies at a distance greater than D from O. In comparison with the statistical-based approach, the distance-based approach generalizes the idea behind discordancy testing for various standard distributions. Moreover, the distance-based outlier detection avoids the excessive computation that can be associated with fitting the observed distribution into some standard distribution and in selecting discordancy tests. The deviation-based outlier detection does not use statistical tests or distance-based measures to identify exceptional object. Instead, it identifies outliers by examining the main characteristics of objects in a group. Objects that “deviate” from this description are considered outliers. Two techniques for this method approach include a sequential exception technique and an OLAP data cube technique.