Solution Manual for Data Mining Chapter 11

Chapter 11 Advanced Cluster Analysis 11.1 Exercises 1. Traditional clustering methods are rigid in that they require each object to belong exclusively to only one cluster. Explain why this is a special case of fuzzy clustering. You may use k-means as an example. Answer: k-means can be regarded as a special case of fuzzy clustering. The corresponding partition matrix is that, if object oi belongs to cluster Cj , then wij = 1 and the other entries on the i-th row are 0. It is easy to verify that the partition matrix M defined as such satisfies all the three requirements for a partition matrix in fuzzy clustering. 2. AllElectronics carries 1, 000 products, P1 , . . . , P1000. Consider customers Ada, Bob, and Cathy such that Ada and Bob purchase three products in common, P1 , P2 , and P3 . For the other 997 products, Ada and Bob independently purchase seven of them randomly. Cathy purchases ten products, randomly selected from the 1, 000 products. In Euclidean distance, what is the probability that dist(Ada, Bob) > dist(Ada, Cathy)? What if Jaccard similarity (Chapter 2) is used? What can you learn from this example? Answer: The probability that Ada and Bob choose i (3 ≤ i ≤ 10) common products is ( )( )( ) ( )( ) 997 7 990 990 7 7 i−3 10 − i i−3 10 − i ( ) P r1 (i) = = ( )2 997 997 7 7 Varying i from 3 to 10, we have the following table. i dist(Ada, Bob) J(Ada, Bob) P r1 (i) i dist(Ada, Bob) J(Ada, Bob) P r1 (i) √ 3 14 = 3.7 3 = 0.18 17 0.95 √ 7 6 = 2.4 7 = 0.5 14 8.5 × 10−10 √ 4 12 = 3.5 4 = 0.25 16 6.8 × 10−3 √8 4=2 8 = 0.67 12 2.6 × 10−12 √ 5 10 = 3.2 5 = 0.33 15 4.1 × 10−5 √ 9 2 = 1.4 9 = 0.82 11 5.2 × 10−15 √ 6 8 = 2.8 6 = 0.43 14 2.1 × 10−7 √ 10 0=0 10 = 1 10 5.3 × 10−18 The probability that Cathy choose j 1 ≤ j ≤ 10 common products with Ada is ( )( )( ) ( )( ) 10 997 10 990 990 7 j 10 − j j 10 − j ) ) ( )( ( = P r2 (j) = 1000 997 1000 10 7 10 We have the following table. j dist(Ada, Cathy) J(Ada, Cathy) P r2 (j) j dist(Ada, Cathy) J(Ada, Cathy) P r2 (j) 1 18 = 4.2 = 0.052 9.2 × 10−3 √ 6 8 = 2.8 6 = 0.43 14 1.5 × 10−13 √ 1 19 √ 2 16 = 4 = 0.11 8.4 × 10−5 √ 7 6 = 2. 4 7 = 0.5 14 6.1 × 10−16 2 18 3 14 = 3.7 = 0.18 6.9 × 10−7 √ 8 4=2 8 = 0.67 12 1.9 × 10−18 √ 3 17 4 12 = 3.5 = 0.25 4.9 × 10−9 √ 9 2 = 1. 4 9 = 0.82 11 3.8 × 10−21 √ 4 16 5 10 = 3.2 = 0.33 3.0 × 10−11 √ 10 0=0 10 = 1 10 3.8 × 10−24 √ 5 15 The probability that dist(Ada, Bob) > dist(Ada, Cathy) is given by 9 ∑ (P r1 (i) i=3 10 ∑ j=i+1 P r2 (j)) = 4.7 × 10−9 The probability that J(Ada, Bob) > J (Ada, Cathy) is given by 10 ∑ i=3 (P r1 (i) i−1 ∑ j=1 P r2 (j)) = 8.9 × 10−3 This example shows the following. • The Euclidean distance is from 0 to infinite, while the Jaccard similarity is in range [0, 1]. When a space is of very high dimensionality and very sparse, Jaccard similarity is easier to use given the bounded range and more smooth trend. • The more different the two vector, the larger the Euclidean distance, but the smaller the Jaccard similarity. dist(Ada, Bob) > dist(Ada, Cathy) and J (Ada, Bob) > J (Ada, Cathy) carry completely different meaning. • The opportunity that two customers choose some common products among a large number of products is very small. 3. Show that I × J is a bi-cluster with coherent values if and only if, for any i1 , i2 ∈ I and j1 , j2 ∈ J , then ei1 j1 − ei2 j1 = ei1 j2 − ei2 j2 . Answer: (Direction only-if ) In a bi-cluster I × J, every entry eij = c + αi + βj , where αi and βj are the adjustments for row i and column j, respectively. (11.1) Applying Equation 11.1, we have ei1 j1 − ei2 j1 = c + αi1 + βj1 − c − αi2 − βj1 = αi1 − αi2 . Similarly, ei1 j2 − ei2 j2 = αi1 − αi2 . Thus, ei1 j1 − ei2 j1 = ei1 j2 − ei2 j2 . (Direction if) Let c = −e11 , αi = ei1 and βj = e1j . Since for any i1 , i2 ∈ I and j1 , j2 ∈ J, ei1 j1 − ei2 j1 = ei1 j2 − ei2 j2 , we have eij − e1j = ei1 − e11. That is, eij = −e11 + ei1 + e1j = c + αi + βj . I × J is a bi-cluster with coherent values. 4. Compare the MaPle algorithm (Section 11.2.3) with the frequent closed-itemset mining algorithm, CLOSET (Pei, Han, and Mao [PHM00]). What are the major similarities and differences? Answer: In frequent closed-itemset mining, we can start with frequent items. However, in maximal δ-pCluster mining, a δ-pCluster has at least two rows and two columns. We need a step to find all δ-pClusters of at least 2 rows or 2 columns. Moreover, while the two methods carry similar ideas in pruning, the technical details are different. 5. SimRank is a similarity measure for clustering graph and network data. (a) Prove lim si (u, v) = s(u, v) for SimRank computation. i→∞ (b) Show s(u, v) = p(u, v) for SimRank. Answer: Please refer to [JW02]. 6. In a large sparse graph where on average each node has a low degree, is the similarity matrix using SimRank still sparse? If so, in what sense? If not, why? Deliberate on your answer. Answer: Theoretically, even when the average degree is low, as long as the graph is connected, the similarity matrix is not sparse at all, since every entry in the matrix has a non-zero value. When an approximation is used wherein entries of very small values are set to 0, the similarity matrix using SimRank may be sparse when the average degree is low. In fact, the sparsity of the matrix is related to the average size of the k-neighborhoods of nodes, since if two nodes are k steps or more away, the SimRank between them can be set to 0, where k is a small number, such as 2 or 3. For the detailed discussion, please refer to [JW02]. 7. Compare the SCAN algorithm (Section 11.3.3) with DBSCAN (Chapter 6). What are their similarities and differences? Answer: Similarities Both methods are density-based, and follow similar frameworks. Both use the mechanisms of ϵ-neighborhoods and core objects/vertices to grow clusters. Differences The similarity between points in DBSCAN and that between vertices in SCAN are different, due to the different types of data. SCAN identifies hubs and outliers. DBSCAN does not find any hub points. 8. Consider partitioning clustering and the following constraint on clusters: the number of objects in each cluster must be between kn (1 − δ) and nk (1 + δ), where n is the total number of objects in the data set, k is the number of clusters desired, and δ in [0, 1) is a parameter. Can you extend the k-means method to handle this constraint? Discuss situations where the constraint is hard and soft. Answer: There may exist other feasible answers different from the following. If the constraint is hard, that is, cannot be violated, we can extend the k-means algorithm with the following changes in the assignment step. Suppose c1 , . . . , ck are the current k centers (means). k {dist(p, ci )}, (a) For each point p, calculate p.M inDist = minki=1 {dist(p, ci )}, and p.CI d = arg mini=1 that is, the distance to the closest center and the id of the closest center. (b) Process all points in M inDist increasing order. For a point p, if p.CI d has been assigned less than nk (1 − δ) points, assign p to p.CId. Otherwise, update p.M inDist to the distance between p and the next closest center that has been assigned less than nk (1 − δ) points, and let p.CId be that center. After this step, every center is assigned kn (1 − δ) points. k {dist(p, ci )}, and p.C Id = (c) For the remaining, unassigned points, calculate p.M inDist = mini=1 k {dist(p, ci )}, that is, the distance to the closest center and the id of the closest center. arg mini=1 Process all points in M inDist increasing order. For a point p, if p.CI d has been assigned less than nk (1 + δ) points, assign p to p.CId. Otherwise, update p.M inDist to the distance between p and the next closest center that has been assigned less than nk (1 + δ) points, and let p.CId be that center. After this step, every center is assigned at most kn (1 + δ) points. When the constraint is soft, we can use a penalty function that penalizes a clustering more if a center is assigned much less than kn(1 − δ) points or much more than nk (1 + δ) points. Such a penalty function can integrate the penalty with the within-cluster variation. For example, consider a clustering C whose within-cluster variation is E. Let c1 , . . . , ck are the centers, and |Ci | (1 ≤ i ≤ k) are the number of ∑k points assigned to ci . The penalty function can be E ′ = E + i=1 di , where  n n  ( k (1 − δ) − |Ci |) · avgdist if |Ci | < k (1 − δ ) di = (|Ci | − nk (1 + δ)) · avgdist if |C1 | > kn(1 + δ )   0 otherwise and avgdist is the average distance between two points in the data set. The revised k-means algorithm should try to minimize E ′ .